9 papers
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…
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…
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…
Strong Bounds for Skew-Corner-Free Sets
Michael Jaber, Shachar Lovett, Anthony Ostuni
Motivated by applications to matrix multiplication algorithms, Pratt asked (ITCS'24) how large a subset of could be without containing a skew-corner: three points…
Exact versus Approximate Representations of Boolean Functions in the De Morgan Basis
Arkadev Chattopadhyay, Yogesh Dahiya, Shachar Lovett
A seminal result of Nisan and Szegedy (STOC, 1992) shows that for any total Boolean function, the degree of the real polynomial that computes the function, and the minimal degree o…
Quasipolynomial bounds for the corners theorem
Michael Jaber, Yang P. Liu, Shachar Lovett +2
Let be a finite abelian group and be a subset of which is corner--free, meaning that there are no and such that …