20 citations · 164 across the 63 of their papers we have counts for
6 papers · 1 filter
Refuting approaches to the log-rank conjecture for XOR functions
Hamed Hatami, Kaave Hosseini, Shachar Lovett +1
The log-rank conjecture, a longstanding problem in communication complexity, has persistently eluded resolution for decades. Consequently, some recent efforts have focused on poten…
New Graph Decompositions and Combinatorial Boolean Matrix Multiplication Algorithms
Amir Abboud, Nick Fischer, Zander Kelley +2
We revisit the fundamental Boolean Matrix Multiplication (BMM) problem. With the invention of algebraic fast matrix multiplication over 50 years ago, it also became known that BMM…
Explicit separations between randomized and deterministic Number-on-Forehead communication
Zander Kelley, Shachar Lovett, Raghu Meka
We study the power of randomness in the Number-on-Forehead (NOF) model in communication complexity. We construct an explicit 3-player function , such that: (i)…
Exponential Hardness of Reinforcement Learning with Linear Function Approximation
Daniel Kane, Sihan Liu, Shachar Lovett +3
A fundamental question in reinforcement learning theory is: suppose the optimal value functions are linear in given features, can we learn them efficiently? This problem's counterp…
Do PAC-Learners Learn the Marginal Distribution?
Max Hopkins, Daniel M. Kane, Shachar Lovett +1
The Fundamental Theorem of PAC Learning asserts that learnability of a concept class is equivalent to the of empirical error in to its mean,…
Streaming Lower Bounds and Asymmetric Set-Disjointness
Shachar Lovett, Jiapeng Zhang
Frequency estimation in data streams is one of the classical problems in streaming algorithms. Following much research, there are now almost matching upper and lower bounds for the…