154 citations · 438 across the 55 of their papers we have counts for
5 papers · 1 filter
The gradient complexity of linear regression
Mark Braverman, Elad Hazan, Max Simchowitz +1
We investigate the computational complexity of several basic linear algebra primitives, including largest eigenvector computation and linear regression, in the computational model…
Convex Set Disjointness, Distributed Learning of Halfspaces, and LP Feasibility
Mark Braverman, Gillat Kol, Shay Moran +1
We study the Convex Set Disjointness (CSD) problem, where two players have input sets taken from an arbitrary fixed domain~ of size . T…
Sorted Top-k in Rounds
Mark Braverman, Jieming Mao, Yuval Peres
We consider the sorted top- problem whose goal is to recover the top- items with the correct order out of items using pairwise comparisons. In many applications, multiple…
Calibration, Entropy Rates, and Memory in Language Models
Mark Braverman, Xinyi Chen, Sham M. Kakade +3
Building accurate language models that capture meaningful long-term dependencies is a core challenge in natural language processing. Towards this end, we present a calibration-base…
Space-bounded Church-Turing thesis and computational tractability of closed systems
Mark Braverman, Cristobal Rojas, Jonathan Schneider
We report a new limitation on the ability of physical systems to perform computation -- one that is based on generalizing the notion of memory, or storage space, available to the s…