We study query-efficient Probabilistically Checkable
Proofs (PCPs) and linearity tests. We focus on the number
of amortized query bits. A testing algorithm uses $q$ amortized
query bits if, for some constant $k$, it reads $qk$ bits and has
error probability at most $2^{-k}$. The best known ... more >>>

Gowers introduced, for d\geq 1, the notion of dimension-d uniformity U^d(f)
of a function f: G -> \C, where G is a finite abelian group and \C are the
complex numbers. Roughly speaking, if a function has small Gowers uniformity
of dimension d, then it ``looks random'' on ... more >>>

For Boolean functions that are $\epsilon$-far from the set of linear functions, we study the lower bound on the rejection probability (denoted $\textsc{rej}(\epsilon)$) of the linearity test suggested by Blum, Luby and Rubinfeld. The interest in this problem is partly due to its relation to PCP constructions and hardness of ... more >>>

In this paper, we consider the problem of approximately solving a system of homogeneous linear equations over reals, where each
equation contains at most three variables.

Since the all-zero assignment always satisfies all the equations exactly, we restrict the assignments to be ``non-trivial". Here is
an informal statement of our ... more >>>