Arkadev Chattopadhyay

Let m,q > 1 be two integers that are co-prime and A be any subset of Z_m. Let P be any multi-linear polynomial of degree d in n variables over Z_m. We show that the MOD_q boolean function on n variables has correlation at most exp(-\Omega(n/(m2^{m-1})^d)) with the boolean function ... more >>>

Scott Aaronson, Avi Wigderson

Any proof of P!=NP will have to overcome two barriers: relativization

and natural proofs. Yet over the last decade, we have seen circuit

lower bounds (for example, that PP does not have linear-size circuits)

that overcome both barriers simultaneously. So the question arises of

whether there ...
more >>>

Shachar Lovett

We study the density of the weights of Generalized Reed--Muller codes. Let $RM_p(r,m)$ denote the code of multivariate polynomials over $\F_p$ in $m$ variables of total degree at most $r$. We consider the case of fixed degree $r$, when we let the number of variables $m$ tend to infinity. We ... more >>>

Arnab Bhattacharyya, Swastik Kopparty, Grant Schoenebeck, Madhu Sudan, David Zuckerman

We consider the problem of testing if a given function

$f : \F_2^n \rightarrow \F_2$ is close to any degree $d$ polynomial

in $n$ variables, also known as the Reed-Muller testing problem.

Alon et al.~\cite{AKKLR} proposed and analyzed a natural

$2^{d+1}$-query test for this property and showed that it accepts

more >>>

Shachar Lovett, Partha Mukhopadhyay, Amir Shpilka

In this paper we give the first construction of a pseudorandom generator, with seed length $O(\log n)$, for $\mathrm{CC}_0[p]$, the class of constant-depth circuits with unbounded fan-in $\mathrm{MOD}_p$ gates, for some prime $p$. More accurately, the seed length of our generator is $O(\log n)$ for any constant error $\epsilon>0$. In ... more >>>

Albert Atserias, Anuj Dawar

Kolaitis and Kopparty have shown that for any first-order formula with

parity quantifiers over the language of graphs there is a family of

multi-variate polynomials of constant-degree that agree with the

formula on all but a $2^{-\Omega(n)}$-fraction of the graphs with $n$

vertices. The proof yields a bound on the ...
more >>>

Badih Ghazi, Pritish Kamath, Prasad Raghavendra

In this work we introduce a new technique for reducing the dimension of the ambient space of low-degree polynomials in the Gaussian space while preserving their relative correlation structure. As applications, we address the following problems:

(I) Computability of the Approximately Optimal Noise Stable function over Gaussian space:

The goal ... more >>>

Srikanth Srinivasan, Madhu Sudan

The well-known DeMillo-Lipton-Schwartz-Zippel lemma says that $n$-variate

polynomials of total degree at most $d$ over

grids, i.e. sets of the form $A_1 \times A_2 \times \cdots \times A_n$, form

error-correcting codes (of distance at least $2^{-d}$ provided $\min_i\{|A_i|\}\geq 2$).

In this work we explore their local

decodability and local testability. ...
more >>>

Marshall Ball, Eshan Chattopadhyay, Jyun-Jie Liao, Tal Malkin, Li-Yang Tan

We present the first explicit construction of a non-malleable code that can handle tampering functions that are bounded-degree polynomials.

Prior to our work, this was only known for degree-1 polynomials (affine tampering functions), due to Chattopadhyay and Li (STOC 2017). As a direct corollary, we obtain an explicit non-malleable ... more >>>

Omar Alrabiah, Eshan Chattopadhyay, Jesse Goodman, Xin Li, João Ribeiro

We continue a line of work on extracting random bits from weak sources that are generated by simple processes. We focus on the model of locally samplable sources, where each bit in the source depends on a small number of (hidden) uniformly random input bits. Also known as local sources, ... more >>>

Eshan Chattopadhyay, Jesse Goodman, Mohit Gurumukhani

We explicitly construct the first nontrivial extractors for degree $d \ge 2$ polynomial sources over $\mathbb{F}_2^n$. Our extractor requires min-entropy $k\geq n - \frac{\sqrt{\log n}}{(d\log \log n)^{d/2}}$. Previously, no constructions were known, even for min-entropy $k\geq n-1$. A key ingredient in our construction is an input reduction lemma, which allows ... more >>>

Ashish Dwivedi, Zeyu Guo, Ben Lee Volk

We construct explicit pseudorandom generators that fool $n$-variate polynomials of degree at most $d$ over a finite field $\mathbb{F}_q$. The seed length of our generators is $O(d \log n + \log q)$, over fields of size exponential in $d$ and characteristic at least $d(d-1)+1$. Previous constructions such as Bogdanov's (STOC ... more >>>

Omar Alrabiah, Jesse Goodman, Jonathan Mosheiff, Joao Ribeiro

We prove that random low-degree polynomials (over $\mathbb{F}_2$) are unbiased, in an extremely general sense. That is, we show that random low-degree polynomials are good randomness extractors for a wide class of distributions. Prior to our work, such results were only known for the small families of (1) uniform sources, ... more >>>

Prashanth Amireddy, Amik Raj Behera, Manaswi Paraashar, Srikanth Srinivasan, Madhu Sudan

In this work, we show that the class of multivariate degree-$d$ polynomials mapping $\{0,1\}^{n}$ to any Abelian group $G$ is locally correctable with $\widetilde{O}_{d}((\log n)^{d})$ queries for up to a fraction of errors approaching half the minimum distance of the underlying code. In particular, this result holds even for polynomials ... more >>>