20 citations · 164 across the 63 of their papers we have counts for
3 papers · 2 filters
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…