2

Near-Optimal Lower Bounds For Convex Optimization For All Orders of Smoothness
We study the complexity of optimizing highly smooth convex functions. For a positive integer $p$, we want to find an …
Ankit Garg, Robin Kothari, Praneeth Netrapalli, Suhail Sherif
Cite arXiv Talk Video
The Log-Approximate-Rank Conjecture Is False
We construct a simple and total Boolean function $F = f \circ \mathsf{XOR}$ on $2n$ variables that has only $O(\sqrt{n})$ spectral …
Arkadev Chattopadhyay, Nikhil S. Mande, Suhail Sherif
Cite ECCC Talk Slides
The Log-Approximate-Rank Conjecture Is False