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 is said to have low rank if it can be expressed as a composition of a few lower degree polynomials. Green and Tao [Contrib. Discrete Math 2009] and Kaufman and Lovett [FOCS 2008] showed that bias implies low rank for fixed degree polynomials over fixed prime fields. This lies at the heart of many tools in higher order Fourier analysis. In this work, we extend this result to all prime fields (of size possibly growing with$n$). We also provide a generalization to nonprime fields in the large characteristic case. However, we state all our applications in the prime field setting for the sake of simplicity of presentation. Using the above generalization to large fields as a starting point, we are also able to settle the list decoding radius of fixed degree Reed-Muller codes over growing fields. The case of fixed size fields was solved by Bhowmick and Lovett [STOC 2015], which resolved a conjecture of Gopalan-Klivans-Zuckerman [STOC 2008]. Here, we show that the list decoding radius is equal the minimum distance of the code for all fixed degrees, even when the field size is possibly growing with$n$. Additionally, we effectively resolve the weight distribution problem for Reed-Muller codes of fixed degree over all fields, first raised in 1977 in the classic textbook by MacWilliams and Sloane [Research Problem 15.1 in Theory of Error Correcting Codes].

As computational modeling, simulation, and predictions are becoming integral parts of biomedical pipelines, it behooves us to emphasize the reliability of the computational protocol. For any reported quantity of interest (QOI), one must also compute and report a measure of the uncertainty or error associated with the QOI. This is especially important in molecular modeling, since in most practical applications the inputs to the computational protocol are often noisy, incomplete, or low-resolution. Unfortunately, currently available modeling tools do not account for uncertainties and their effect on the final QOIs with sufficient rigor. We have developed a statistical framework that expresses the uncertainty of the QOI as the probability that the reported value deviates from the true value by more than some user-defined threshold. First, we provide a theoretical approach where this probability can be bounded using Azuma-Hoeffding like inequalities. Second, we approximate this probability empirically by sampling the space of uncertainties of the input and provide applications of our framework to bound uncertainties of several QOIs commonly used in molecular modeling. Finally, we also present several visualization techniques to effectively and quantitavely visualize the uncertainties: in the input, final QOIs, and also intermediate states.

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 F. The Reed-Muller code RMF(n, d) is defined by n-variate degree-d polynomials over F. In this paper, we study the list decoding radius of Reed-Muller codes over a constant prime field F = Fp, constant degree d, and large n. We show that the list decoding radius is equal to the minimal distance of the code. That is, if we denote by S(d) the normalized minimal distance of RMF(n, d), then the number of codewords in any ball of radius δ(d) - ε is bounded by c = c(p, d, e) independent of n. This resolves a conjecture of Gopalan et al., who among other results proved it in the special case of F = F2; and extends the work of Gopalan who proved the conjecture in the case of d = 2. We also analyse the number of codewords in balls of radius exceeding the minimal distance of the code. For e ≤ d, we show that the number of codewords of RMF(n, d) in a ball of radius δ(e)-ε is bounded by exp(c · nd-e), where c = c(p, d, ε) is independent of n. The dependence on n is tight. This extends the work of Kaufman et al. who proved similar bounds over F2. The proof relies on several new ingredients: an extension of the Frieze- Kannan weak regularity to general function spaces, higher order Fourier analysis, and an extension of the Schwartz-Zippel lemma to the compositions of polynomials.

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. * For any fixed finite field $\mathbb{K}$, we show that the list decoding radius of the generalized Reed Muller code over $\mathbb{K}$ equals the minimum distance of the code. Previously, this had been proved over prime fields [BL14] and for the case when $|\mathbb{K}|-1$ divides the order of the code [GKZ08]. * For any fixed finite field $\mathbb{K}$, we give a polynomial time algorithm to decide whether a given polynomial $P: \mathbb{K}^n \to \mathbb{K}$ can be decomposed as a particular composition of lesser degree polynomials. This had been previously established over prime fields [Bha14, BHT15]. * For any fixed finite field $\mathbb{K}$, we prove that all locally characterized affine-invariant properties of functions $f: \mathbb{K}^n \to \mathbb{K}$ are testable with one-sided error. The same result was known when $\mathbb{K}$ is prime [BFHHL13] and when the property is linear [KS08]. Moreover, we show that for any fixed finite field $\mathbb{F}$, an affine-invariant property of functions $f: \mathbb{K}^n \to \mathbb{F}$, where $\mathbb{K}$ is a growing field extension over $\mathbb{F}$, is testable if it is locally characterized by constraints of bounded weight.

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 super-logarithmic degree. Here, we suggest a new barrier explaining this phenomenon. We show that many of the existing lower bound proof techniques extend to nonclassical polynomials, an extension of classical polynomials which arose in higher order Fourier analysis. Moreover, these techniques are tight for nonclassical polynomials of logarithmic degree.

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 arithmetic progressions (APs), generalized arithmetic progressions (GAPs), and Bohr sets, each of which generalizes affine sources. We give an explicit extractor for additive sources with linear min-entropy over both Zp and Zn/p, for large prime p, although our results over Zn/p require that the source further satisfy a list-decodability condition. As a corollary, we obtain explicit extractors for APs, GAPs, and Bohr sources with linear min-entropy, although again our results over Zn/p require the list-decodability condition.

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 F. The Reed-Muller code RMF(n,d) is defined by n-variate degree-d polynomials over F. In this work, we study the list decoding radius of Reed-Muller codes over a constant prime field F=Fp, constant degree d and large n. We show that the list decoding radius is equal to the minimal distance of the code.

A matching vector (MV) family modulo $m$ is a pair of ordered lists $U=(u_1,\ldots,u_t)$ and $V=(v_1,\ldots,v_t)$ where $u_i$, $v_j \in \mathbb{Z}_m^n$ with the following inner product pattern: for any $i$, $\langle u_i,v_i\rangle=0$, and for any $i \ne j$, $\langle u_i,v_j\rangle \ne 0$. An MV family is called $q$-restricted if inner products $\langle u_i,v_j\rangle$ take at most $q$ different values. Our interest in MV families stems from their recent application in the construction of subexponential locally decodable codes (LDCs). There, $q$-restricted MV families are used to construct LDCs with $q$ queries, and there is special interest in the regime where $q$ is constant. When $m$ is a prime it is known that such constructions yield codes with exponential block length. However, for composite $m$ the behavior is dramatically different. A recent work by Efremenko [SIAM J. Comput., 40 (2011), pp. 1154--1178] (based on an approach initiated by Yekhanin [J. ACM, 55 (2008), pp. 1--16]) gives the first subexponential LDC with constant queries. It is based on a construction of an MV family of superpolynomial size by Grolmusz [Combinatorica, 20 (2000), pp. 71--86] modulo composite $m$. In this work, we prove two lower bounds on the block length of LDCs which are based on black box construction using MV families. When $q$ is constant (or sufficiently small), we prove that such LDCs must have a quadratic block length. When the modulus $m$ is constant (as it is in the construction of Efremenko) we prove a superpolynomial lower bound on the block-length of the LDCs, assuming a well-known conjecture in additive combinatorics, the polynomial Freiman--Ruzsa conjecture over $\mathbb{Z}_m$.

A Matching Vector (MV) family modulo m is a pair of ordered lists U=(u1,...,ut) and V=(v1,...,vt) where ui,vj ∈ Zmn with the following inner product pattern: for any i, {ui,vi}=0, and for any i ≠ j, {ui,vj} ≠ 0. A MV family is called q-restricted if inner products {ui,vj} take at most q different values.

This paper determines mechanisms for distributed storage that are simultaneously repair and update efficient. Repair efficiency demands that minimum information be downloaded from surviving nodes to reconstruct failed storage nodes. Update efficiency desires that changes in the original data require minimal updates at the storage nodes. These two requirements can be seen as counteracting one another, as the latter imposes a sparsity constraint on the encoding process that is not desirable for the former. In this paper we establish the existence of the codes that meet both requirements: require only logarithmic updates when data changes, while simultaneously minimizing repair bandwidth for exact reconstruction. To show this, we use a combination of KG codes for update efficiency with interference-alignment strategies for distributed storage.