Eldar Fischer

Let $P$ be a property of graphs. An $\epsilon$-test for $P$ is a

randomized algorithm which, given the ability to make queries whether

a desired pair of vertices of an input graph $G$ with $n$ vertices are

adjacent or not, distinguishes, with high probability, between the

case of $G$ satisfying ...
more >>>

Asaf Shapira, Noga Alon

Property-testers are fast randomized algorithms for distinguishing

between graphs (and other combinatorial structures) satisfying a

certain property, from those that are far from satisfying it. In

many cases one can design property-testers whose running time is in

fact {\em independent} of the size of the input. In this paper we

more >>>

Luca Trevisan, Madhur Tulsiani, Salil Vadhan

We show that every high-entropy distribution is indistinguishable from an

efficiently samplable distribution of the same entropy. Specifically, we prove

that if $D$ is a distribution over $\{ 0,1\}^n$ of min-entropy at least $n-k$,

then for every $S$ and $\epsilon$ there is a circuit $C$ of size at most

$S\cdot ...
more >>>

Arnab Bhattacharyya, Victor Chen, Madhu Sudan, Ning Xie

The rich collection of successes in property testing raises a natural question: Why are so many different properties turning out to be locally testable? Are there some broad "features" of properties that make them testable? Kaufman and Sudan (STOC 2008) proposed the study of the relationship between the invariances satisfied ... more >>>

Arnab Bhattacharyya, Elena Grigorescu, Asaf Shapira

The study of the interplay between the testability of properties of Boolean functions and the invariances acting on their domain which preserve the property was initiated by Kaufman and Sudan (STOC 2008). Invariance with respect to F_2-linear transformations is arguably the most common symmetry exhibited by natural properties of Boolean ... more >>>

Jiapeng Zhang

A theorem of Green, Tao, and Ziegler can be stated as follows: if $R$ is a pseudorandom distribution, and $D$ is a dense distribution of $R,$ then $D$ can be modeled as a distribution $M$ which is dense in uniform distribution such that $D$ and $M$ are indistinguishable. The reduction ... more >>>

Arnab Bhattacharyya, Eldar Fischer, Shachar Lovett

Invariance with respect to linear or affine transformations of the domain is arguably the most common symmetry exhibited by natural algebraic properties. In this work, we show that any low complexity affine-invariant property of multivariate functions over finite fields is testable with a constant number of queries. This immediately reproves, ... more >>>

Lior Gishboliner, Asaf Shapira

A graph property P is said to be testable if one can check if a graph is close or far from satisfying P using few random local inspections. Property P is said to be non-deterministically testable if one can supply a "certificate" to the fact that a graph satisfies P ... more >>>

Badih Ghazi, Pritish Kamath, Madhu Sudan

We present decidability results for a sub-class of "non-interactive" simulation problems, a well-studied class of problems in information theory. A non-interactive simulation problem is specified by two distributions $P(x,y)$ and $Q(u,v)$: The goal is to determine if two players, Alice and Bob, that observe sequences $X^n$ and $Y^n$ respectively where ... more >>>

Arnab Bhattacharyya, Sivakanth Gopi

A locally correctable code (LCC) is an error correcting code that allows correction of any arbitrary coordinate of a corrupted codeword by querying only a few coordinates.

We show that any zero-error $2$-query locally correctable code $\mathcal{C}: \{0,1\}^k \to \Sigma^n$ that can correct a constant fraction of corrupted symbols must ...
more >>>

Venkatesan Guruswami, Xiaoyu He, Ray Li

We prove that there exists an absolute constant $\delta>0$ such any binary code $C\subset\{0,1\}^N$ tolerating $(1/2-\delta)N$ adversarial deletions must satisfy $|C|\le 2^{\poly\log N}$ and thus have rate asymptotically approaching $0$. This is the first constant fraction improvement over the trivial bound that codes tolerating $N/2$ adversarial deletions must have rate ... more >>>