|
Poster
|
Tue 14:00
|
Sub-exponential time Sum-of-Squares lower bounds for Principal Components Analysis
Aaron Potechin · Goutham Rajendran
|
|
|
Poster
|
Wed 14:00
|
Optimal Weak to Strong Learning
Kasper Green Larsen · Martin Ritzert
|
|
|
Poster
|
Tue 9:00
|
The Query Complexity of Cake Cutting
Simina Branzei · Noam Nisan
|
|
|
Poster
|
Thu 14:00
|
SQ Lower Bounds for Learning Single Neurons with Massart Noise
Ilias Diakonikolas · Daniel Kane · Lisheng Ren · Yuxin Sun
|
|
|
Poster
|
Tue 9:00
|
Will Bilevel Optimizers Benefit from Loops
Kaiyi Ji · Mingrui Liu · Yingbin Liang · Lei Ying
|
|
|
Poster
|
Tue 9:00
|
Hardness of Noise-Free Learning for Two-Hidden-Layer Neural Networks
Sitan Chen · Aravind Gollakota · Adam Klivans · Raghu Meka
|
|
|
Poster
|
Wed 14:00
|
Optimal Query Complexities for Dynamic Trace Estimation
David Woodruff · Fred Zhang · Richard Zhang
|
|
|
Workshop
|
|
Lower Bounds on 0-1 Loss for Multi-class Classification with a Test-time Attacker
Sihui Dai · Wenxin Ding · Arjun Nitin Bhagoji · Daniel Cullina · Prateek Mittal · Ben Zhao
|
|
|
Poster
|
Tue 14:00
|
Estimating the Arc Length of the Optimal ROC Curve and Lower Bounding the Maximal AUC
Song Liu
|
|
|
Poster
|
Thu 14:00
|
Reconstruction on Trees and Low-Degree Polynomials
Frederic Koehler · Elchanan Mossel
|
|
|
Poster
|
Thu 9:00
|
Single-pass Streaming Lower Bounds for Multi-armed Bandits Exploration with Instance-sensitive Sample Complexity
Sepehr Assadi · Chen Wang
|
|
|
Poster
|
Thu 9:00
|
Lower Bounds on Randomly Preconditioned Lasso via Robust Sparse Designs
Jonathan Kelner · Frederic Koehler · Raghu Meka · Dhruv Rohatgi
|
|
