Luca Trevisan

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 >>>

Alex Samorodnitsky, Luca Trevisan

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 >>>

Tali Kaufman, Simon Litsyn, Ning Xie

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 >>>

Subhash Khot, Dana Moshkovitz

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 >>>