257 citations · 271 across the 8 of their papers we have counts for
4 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…
Deterministic Extractors for Additive Sources
Abhishek Bhowmick, Ariel Gabizon, Thái Hoàng Lê +1
We propose a new model of a weakly random source that admits randomness extraction. Our model of additive sources includes such natural sources as uniform distributions on arithmet…
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…
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…