20 citations · 164 across the 63 of their papers we have counts for
31 papers · 1 filter
A simplified proof of polynomial improvements for 3SUM and APSP
Sankeerth Rao Karingula, Shachar Lovett
We give a simplified proof of the polynomial improvements for integer 3SUM and all-pairs shortest paths (APSP) established by Alman and Vassilevska Williams, with weaker exponents.…
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…
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…
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…
List Decoding Quotient Reed-Muller Codes
Omri Gotlib, Tali Kaufman, Shachar Lovett
Reed-Muller codes consist of evaluations of -variate polynomials over a finite field with degree at most . Much like every linear code, Reed-Muller codes can be…
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…
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)…
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…
High Dimensional Expanders: Eigenstripping, Pseudorandomness, and Unique Games
Mitali Bafna, Max Hopkins, Tali Kaufman +1
Higher order random walks (HD-walks) on high dimensional expanders (HDX) have seen an incredible amount of study and application since their introduction by Kaufman and Mass [KM16]…
Log-rank and lifting for AND-functions
Alexander Knop, Shachar Lovett, Sam McGuire +1
Let be a boolean function, and let denote the AND-function of , where denotes bit-wise AND. We study the…
Singularity of random integer matrices with large entries
Sankeerth Rao Karingula, Shachar Lovett
We study the singularity probability of random integer matrices. Concretely, the probability that a random matrix, with integer entries chosen uniformly from $\{-m,\ld…
Fractional Pseudorandom Generators from Any Fourier Level
Eshan Chattopadhyay, Jason Gaitonde, Chin Ho Lee +2
We prove new results on the polarizing random walk framework introduced in recent works of Chattopadhyay {et al.} [CHHL19,CHLT19] that exploit Fourier tail bounds for classes…
Decision list compression by mild random restrictions
Shachar Lovett, Kewen Wu, Jiapeng Zhang
A decision list is an ordered list of rules. Each rule is specified by a term, which is a conjunction of literals, and a value. Given an input, the output of a decision list is the…
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…
Nonclassical polynomials as a barrier to polynomial lower bounds
Abhishek Bhowmick, Shachar Lovett
The problem of constructing explicit functions which cannot be approximated by low degree polynomials has been extensively studied in computational complexity, motivated by applica…
List decoding Reed-Muller codes over small fields
Abhishek Bhowmick, Shachar Lovett
The list decoding problem for a code asks for the maximal radius up to which any ball of that radius contains only a constant number of codewords. The list decoding radius is not w…
0-1 Integer Linear Programming with a Linear Number of Constraints
Russell Impagliazzo, Shachar Lovett, Ramamohan Paturi +1
We give an exact algorithm for the 0-1 Integer Linear Programming problem with a linear number of constraints that improves over exhaustive search by an exponential factor. Specifi…
Estimating the distance from testable affine-invariant properties
Hamed Hatami, Shachar Lovett
Let be an affine invariant property of functions for fixed and . We show that if is locally testable with a constant number of q…
Communication is bounded by root of rank
Shachar Lovett
We prove that any total boolean function of rank can be computed by a deterministic communication protocol of complexity . Equivalently, any graph wh…
Every locally characterized affine-invariant property is testable
Arnab Bhattacharyya, Eldar Fischer, Hamed Hatami +2
Let F = F_p for any fixed prime p >= 2. An affine-invariant property is a property of functions on F^n that is closed under taking affine transformations of the domain. We prove th…
New Lower Bounds for Matching Vector Codes
Abhishek Bhowmick, Zeev Dvir, Shachar Lovett
A Matching Vector (MV) family modulo is a pair of ordered lists and where with the following inner product patt…