20 citations · 164 across the 63 of their papers we have counts for
83 papers
Exponential Correlation Bounds for Polynomials
Eshan Chattopadhyay, Pooya Hatami, Chin Ho Lee +3
We prove that the XOR of majorities on disjoint blocks of bits has correlation at most with every Boolean-valued degree- polynomial over an arbit…
Limitations of the slice rank method in additive combinatorics
Sankeerth Rao Karingula, Shachar Lovett
The slice rank method gives exponential bounds for sets with no three-term arithmetic progression in finite vector spaces of odd characteristic and for three-sunflower-free familie…
An elementary proof of the Komlós conjecture
Sankeerth Rao Karingula, Shachar Lovett
We give an elementary proof of the Komlós conjecture by simplifying the recent proof of Guo, Fang, and Lu. We show that any vectors with $\|v_i\|_2\…
Quantum-Classical Equivalence for AND-Functions
Sreejata Kishor Bhattacharya, Farzan Byramji, Arkadev Chattopadhyay +2
A major open problem in quantum communication complexity is whether quantum protocols can be exponentially more efficient than classical protocols for computing total Boolean funct…
Improved Parallel Repetition for GHZ-Supported Games via Spreadness
Yang P. Liu, Shachar Lovett, Kunal Mittal
We prove that for any 3-player game , whose query distribution has the same support as the GHZ game (i.e., all satisfying ), the val…
The Log-Rank Conjecture: New Equivalent Formulations
Lianna Hambardzumyan, Shachar Lovett, Morgan Shirley
The log-rank conjecture is a longstanding open problem with multiple equivalent formulations in complexity theory and mathematics. In its linear-algebraic form, it asserts that the…