20 citations · 164 across the 63 of their papers we have counts for
5 papers · 1 filter
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…
Group representations that resist random sampling
Shachar Lovett, Cristopher Moore, Alexander Russell
We show that there exists a family of groups and nontrivial irreducible representations such that, for any constant , the average of over uniformly random…
General systems of linear forms: equidistribution and true complexity
Hamed Hatami, Pooya Hatami, Shachar Lovett
The densities of small linear structures (such as arithmetic progressions) in subsets of Abelian groups can be expressed as certain analytic averages involving linear forms. Higher…
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…