3 citations · 6 across the 6 of their papers we have counts for
3 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…
Optimality of Linear Sketching under Modular Updates
Kaave Hosseini, Shachar Lovett, Grigory Yaroslavtsev
We study the relation between streaming algorithms and linear sketching algorithms, in the context of binary updates. We show that for inputs in dimensions, the existence of ef…
Torus polynomials: an algebraic approach to ACC lower bounds
Abhishek Bhrushundi, Kaave Hosseini, Shachar Lovett +1
We propose an algebraic approach to proving circuit lower bounds for ACC0 by defining and studying the notion of torus polynomials. We show how currently known polynomial-based app…