All reports by Author Abhishek Bhowmick:

__
TR15-096
| 5th June 2015
__

Abhishek Bhowmick, Shachar Lovett#### Bias vs structure of polynomials in large fields, and applications in effective algebraic geometry and coding theory

__
TR15-077
| 4th May 2015
__

Arnab Bhattacharyya, Abhishek Bhowmick#### Using higher-order Fourier analysis over general fields

__
TR14-175
| 15th December 2014
__

Abhishek Bhowmick, Shachar Lovett#### Nonclassical polynomials as a barrier to polynomial lower bounds

__
TR14-087
| 12th July 2014
__

Abhishek Bhowmick, Shachar Lovett#### List decoding Reed-Muller codes over small fields

Revisions: 1

__
TR12-034
| 5th April 2012
__

Abhishek Bhowmick, Zeev Dvir, Shachar Lovett#### New Lower Bounds for Matching Vector Codes

Revisions: 5

Abhishek Bhowmick, Shachar Lovett

Let $f$ be a polynomial of degree $d$ in $n$ variables over a finite field $\mathbb{F}$. The polynomial is said to be unbiased if the distribution of $f(x)$ for a uniform input $x \in \mathbb{F}^n$ is close to the uniform distribution over $\mathbb{F}$, and is called biased otherwise. The polynomial ... more >>>

Arnab Bhattacharyya, Abhishek Bhowmick

Higher-order Fourier analysis, developed over prime fields, has been recently used in different areas of computer science, including list decoding, algorithmic decomposition and testing. We extend the tools of higher-order Fourier analysis to analyze functions over general fields. Using these new tools, we revisit the results in the above areas.

... more >>>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 applications in circuit lower bounds, pseudo-randomness, constructions of Ramsey graphs and locally decodable codes. Still, most of the known lower bounds become trivial for polynomials of ...
more >>>

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 well understood even for well studied codes, like Reed-Solomon or Reed-Muller codes.

Fix a finite field $\mathbb{F}$. ... more >>>

Abhishek Bhowmick, Zeev Dvir, Shachar Lovett

We prove new lower bounds on the encoding length of Matching Vector (MV) codes. These recently discovered families of Locally Decodable Codes (LDCs) originate in the works of Yekhanin [Yek] and Efremenko [Efr] and are the only known families of LDCs with a constant number of queries and sub-exponential encoding ... more >>>