# Expanders, Property Testing and the PCP theorem

## Student presentation # 2

Posted in presentations by atri on January 13, 2009

(Guest post by Steve Uurtamo)

I presented the result by Omer Reingold that the decision problem of determining whether two given vertices ($s$ and $t$) are connected in a given graph can be determined in space logarithmic in the size of the graph.

The approach given in the paper was to transform each connected component of the graph into an subgraph with good expansion properties (using an iterated transformation that respects the original connectivity properties), and then simply to walk the vertices of the expander starting at $s$, either arriving at $t$ or proving that no such path exists.  Because the new graph has small diameter, it is possible to enumerate and check all such possible paths in logarithmic space.

## Student Presentation #3

Posted in presentations by atri on November 17, 2008

(Guest post by Nathan Russell)

I presented the first half of the paper On-Line Algorithms for Path Selection in a Nonblocking Network, by Arora, Leighton and Maggs.

Broadly speaking, nonblocking networks are networks of switches (represented by vertices) such that it is possible for any set of inputs to be pairwise connected to any set of outputs without conflict.  The authors, in my part of the paper, set up background to present a network in which $N$ inputs can be connected to $N$ outputs by $O(N \log N)$ switches of bounded degree, using only $O(\log N)$ bit steps.  All of these bounds are known to be optimal. Additionally, the network can do this for multiple  connections simultaneously.

I presented the butterfly and Benes networks, as well as the multi-butterfly and multi-Benes networks constructed by combining them, and gave intuition and prepatory proofs to set up for the authors’ eventual proof of how the networks are nonblocking when a series of splitters is combined with a series of mergers, each built out of multi-Benes networks.

## Property Testing Lecture 4

Posted in lectures by atri on November 17, 2008

In the last lecture, we finished the proof of the soundness for the natural tester for testing graph bipartiteness. The main idea in the proof was to divide up the set of random vertices $S$ into two subsets $U$ and $W$. The analysis proceeded by showing that with high probability over the choices of $U$ and $W$, $W$ forms a “witness” to the fact that no bipartition of $U$ can be extended to a biparitiion of the input graph (which in turns implies that the input graph is not bipartite). The gain in this approach over the naive analysis is that $U$ has constant size and hence, one can take union bound over all possible partitions of $U$.

In the second part of the lecture, we studied Locally Decodable Codes (LDCs). In particular a $(q,\delta,\epsilon)$-locally decodable code $C\subseteq\Sigma^m$ has a local decoder with the following property. For any input $\mathbf{y}\in\Sigma^m$ (such that $\Delta(\mathbf{y},\mathbf{c})\le \delta m$ for a unique $\mathbf{c}\in C$) and $i\in [m]$, the decoder outputs the value $c_i$ with constant probability. We had already seen that the Hamming code is a $(2,\delta,1-2\delta)$-LDC for any $\delta<1/4$. Hamming code has the optimal block length for any 2-query LDC. We then saw a construction of a $(q,\delta,1-q\delta)$-LDC over $\mathbb{F}_r$ for $r\ge q+1$ based on Reed-Muller codes. The first chapter in Sergey Yekhanin‘s thesis has a nice introduction to these results.

## Student Presentation #4

Posted in presentations by atri on November 17, 2008

(Guest post by Swapnoneel Roy)

I presented the first algorithmic result in the paper Online Algorithms for Path Selection in a Nonblocking Network by Sanjeev Arora, Tom Leighton and Bruce Maggs. The algorithm was applied on a Multi-Butterfly network with $N$ inputs and outputs with the $(\alpha, \delta)$ unshared neighbor property. In the algorithm, all the paths were extended from level $\ell$ to level $\ell+1$ (for any level $\ell$) of the network by performing the following steps:

1. every path that waits to be extended sends out a “proposal” to each of its output level $\ell+1$  neighbors in the desired direction (up or down),
2. every output node that receives one proposal sends back its acceptance to that proposal,
3. every path that receives an acceptance advances to one of its accepting outputs on level $\ell+1$.

Going by this way, the algorithm extends the paths from level 0 to level $\log N$. The time taken to extend the paths from one level to the next was shown to be $O(\log N)$. This makes the total running time of the algorithm $O(\log^2{N})$.

## Student Presentations

Posted in annoucements, presentations by atri on November 9, 2008

Here is the schedule of the student presentation (all of them start at 10:30am in Bell 224):

1. Yang (Nov 17): Towards 3-query locally decodable codes of subexponential length (Yekhanin)
2. Nathan+Swapnoneel (Nov 21+24): Bounds on 2-query codeword testing (Ben-Sasson, Goldreich, Sudan).
3. Steve (Dec 1)
4. Than (Dec 5): Approximating the Minimum Spanning Tree Weight in Sublinear Time (Chazelle, Rubinfeld, Trevisan).

Please let us know once you choose your paper and we will update the list above.

## Property Testing Lecture 3

Posted in lectures by atri on November 9, 2008

On Friday, we started  talking about property testing and in particular, testing whether the input graph (represented by a vector corresponding to its adjacency matrix) is bipartite.  (The queries ask whether an edge exists between a pair of vertices in the graph.)

Before talking about the tester for graph bipartiteness, we discussed some high level connections of property testing to learning and decision tree complexity. In particular, property testing is easier than learning as it is only a decision problem (whereas a learning algorithm has to output an approximation to the function being learnt) whereas it is harder than learning as it also has to deal with inputs that are far from having the property (while learning only has to deal with functions that are from a fixed concept class). The decision tree complexity of a property is the stricter version of property testing where the tester has to determine whether the input satisfies the property or not. Graph (non)-bipartitness is a monotone graph property. The Andreaa-Karp-Rosenberg conjecture states that all monotone graph properties require any (deterministic) algorithm to probe all possible edges (this conjecture is also known as the graph evasiveness conjecture). For a quick overview of the problem and notes on a result by Kahn, Saks and Strutevant that proves the conjecture for prime number of vertices and uses topology, refer to these notes by James Lee.

We then looked at the following very natural tester for graph bipartiteness: pick a random subgraph of the input graph and accept if and only if the subgraph is bipartite. This tester obviously has perfect completeness. We saw that the naive analysis of the tester does not work well. In the next lecture, we will see a more sophisticated analysis of the soundness.

The notion of property testing was first defined in the classic paper by Oded Goldreich, Shafi Goldwasser and Dana Ron titled Property Testing and its Connection to Learning and Approximation. This paper also pioneered testing of graph properties. The tester above was first analyzed in this paper. I followed the presentation from these notes by Dana Ron. For more on property testing (especially on graph property testing) see this page by Oded Goldreich.

## Property Testing Lectures 1 and 2

Posted in lectures by atri on November 9, 2008

In the first two lectures on property testing, we started with codeword testing. A codeword tester for a code $C\subseteq \Sigma^m$, with query complexity $q$, is a randomized algorithm that given an input $\mathbf{y}\in\Sigma^m$ does the following:

1. If $\mathbf{y}\in C$, then the tester accepts with probability $1$,
2. If $\delta(\mathbf{y},C)\ge \epsilon$ then the tester rejects with probability $s>0$ (where $s$ can depend on $\epsilon$).
3. Makes at most $q$ oracle queries to $\mathbf{y}$.

We studied the Hadamard code $Had:\{0,1\}^n\rightarrow\{0,1\}^{2^n}$, where every codeword corresponds to the evaluation vector of a linear function $f:\{0,1\}^n\rightarrow\{0,1\}$ ($f$ being linear implies that for every $\mathbf{x},\mathbf{y}\in\{0,1\}^n$, $f(\mathbf{x})+f(\mathbf{y})=f(\mathbf{x}+\mathbf{y})$). This definition suggests a natural tester for the Hadamard code: think of the input from $\{0,1\}^{2^n}$as a function $g:\{0,1\}^n\rightarrow\{0,1\}$, pick random inputs $\mathbf{x},\mathbf{y}\in\{0,1\}^n$ and accept if and only if $g(\mathbf{x})+g(\mathbf{y})=g(\mathbf{x}+\mathbf{y})$. The tester makes only $3$ queries and obviously has perfect completeness. We saw an analysis using Fourier analysis in the lecture that showed that this tester rejects with probability at least $\delta(g,Had)$.

The “linearity tester” above was first analyzed in a paper titled Self-Testing/Correcting with Applications to Numerical Problems by Manuel Blum, Mike Luby and Ronitt Rubinfeld. The analysis of the soundess of the tester using Fourier analysis first appeared in the paper by Mihir Bellare, Don Coppersmith, Johan Hastad, Marcos Kiwi and Madhu Sudan titled Linearity Testing in Characteristic Two. I followed the presentation from these notes by Venkat Guruswami and Ryan O’Donnell.

## Student Presentation #1

Posted in presentations by atri on November 9, 2008

(Guest post by Than Nguyen)

I presented the paper by Paul Feldman, Joel Friedman and Nichloas Pippenger titled Wide-sense nonblocking networks.

A network is an acyclic directed graph that allows connections to be made between a set of vertices, called inputs, to another disjoint set of vertices, called outputs. A network is called wide-sense nonblocking (WSNB) if a request from an idle input to an idle output can be always satisfied. This paper suggests a new way to construct “generalized concentrators” by using certain expanders. From this, they build WSNB generalized connectors with size $O(n \log n)$, where $n$ is the number of inputs and outputs. In addition, with a given depth $k$, they get a  WSNB generalized connectors with size $O(n^{1+1/k} (\log n))^{1- 1/k}$.

## Student Presentation #5

Posted in presentations by atri on November 9, 2008

(Guest post by Yang Wang)

I presented the paper on linear time encodable and decodable code. We get a good error correcting code by using error reduction code. Because of limited time, I mainly talked about the decoding of  error reduction codes. Note that the codes we talked about is a little different from usual codes in that they can be represented as bipartite graphs where the left side stands for message nodes, right side stands for check nodes and left side and right side together make up the codeword of the code. The first result was a simple explicit  $(c,d)$-regular bipartite graph where each node in the right side stands for just one check bit. We proved that this construction can reduce errors to half as long as the number of errors are bounded. The second explicit construction was more complicated. We first start with a $d$-regular expander and then get the corresponding bipartite graph as edge vertex incident graph. Now every check node in the right side of the bipartite graph stands for several check bits and every check node together with these message node neighbors is a word of another code. In fact we used a small code and an expander to construct the error reduction code we wanted.

## Schedule for rest of the semester

Posted in annoucements by atri on October 23, 2008

Below is the planned schedule for the rest of the semester (it is your responsibility to be aware of the meeting times even if we forget to mention them in the previous class):

• Oct 24 (Fri): 10am-noon. Property Testing: Lecture 1 (Atri)
• Oct 27 (Mon): No class.
• Oct 31 (Fri): 11am-noon. Theory seminar (Muthu Venkitsubramaniam)
• Nov 3 (Mon): 10am-noon. Property Testing: Lecture 2 (Atri)
• Nov 7 (Fri): 10am-noon. Property Testing: Lecture 3 (Atri)
• Nov 10 (Mon): 10am-noon. Property Testing: Lecture 4 (Atri)
• Nov 14 (Fri): No class.
• Nov 17 (Mon): 10:30am-noon. Student Presentation 1 (Yang)
• Nov 21 (Fri): 10:30am-noon. Student Presentation 2 (Nathan)
• Nov 24 (Mon): 10:30am-noon. Student Presentation 3 (Swapnoneel)
• Nov 27 (Fri): No class.
• Dec 1 (Mon): 10:30am-noon. Student Presentation 4 (Steve)
• Dec 5 (Fri): 10:30am-noon. Student Presentation 5 (Than) Last meeting.

Some suggestions for presentations (all of which have to be on property testing) are now online. We very strongly recommend that you start looking at the papers ASAP and make your choice soon. (Almost all of the papers in the list will most probably turn out to be a harder read than most of the stuff you guys presented in the first half of the seminar.)