Tag Archives: Codes

Next Week in Jerusalem: Special Day on Quantum PCP, Quantum Codes, Simplicial Complexes and Locally Testable Codes

Special Quantum PCP and/or Quantum Codes: Simplicial Complexes and Locally Testable CodesDay

24 Jul 2014 – 09:30 to 17:00

room B-220, 2nd floor, Rothberg B Building

On Thursday, the 24th of July we will host a SC-LTC (simplicial complexes and classical and quantum locally testable codes) at the Hebrew university, Rothberg building B room 202 (second floor) in the Givat Ram campus. Please join us, we are hoping for a fruitful and enjoyable day, with lots of interactions. Coffee and refreshments will be provided throughout the day, as well as free “tickets” for lunch on campus
There is no registration fee, but please email dorit.aharonov@gmail.com preferably by next Tuesday if there is a reasonable probability that you attend –  so that we have some estimation regarding the number of people, for food planning

Program:SC-LTC day – simplicial complexes and locally testable classical and quantum codes –Rothberg building B202
9:00 gathering: coffee and refreshments

9:30 Irit Dinur: Locally testable codes, a bird’s eye view

10:15: coffee break

10:45 Tali Kaufman, High dimensional expanders and property testing

11:30 15 minutes break

11:45 Dorit Aharonov, quantum codes and local testability

12:30 lunch break

2:00 Alex Lubotzky: Ramanujan complexes

2:50 coffee break

3:15 Lior Eldar: Open questions about quantum locally testable codes and quantum entanglement

3:45 Guy Kindler: direct sum testing and relations to simplicial complexes ( Based on David, Dinur, Goldenberg, Kindler, and Shinkar, 2014)

4:15-5 free discussion, fruit and coffee


Analysis of Boolean Functions – Week 7

Lecture 11

The Cap Set problem

We presented Meshulam’s  bound 3^n/n for the maximum number of elements in a subset A of (\mathbb{Z}/3Z)^n not containing a triple x,y,x of distinct elements whose sum is 0.

The theorem is analogous to Roth’s theorem for 3-term arithmetic progressions and, in fact, it is a sort of purified analog to Roth’s proof, as some difficulties over the integers are not presented here.  There are two ingredients in the proof: One can be referred to as the “Hardy-Littlewood circle method” and the other is the “density increasing” argument.

We first talked about density-increasing method and showed how KKL’s theorem for influence of sets follows from KKL’s theorem for the maximum individual influence. I mentioned what is known about influence of large sets and what is still open. (I will devote to this topic a separate post.)

Then we went over Meshulam’s proof in full details. A good place to see a detailed sketch of the proof is in this post  on Gowers’ blog.

Let me copy Tim’s sketch over here:

Sketch of proof (from Gowers’s blog).

Next, here is a brief sketch of the Roth/Meshulam argument. I am giving it not so much for the benefit of people who have never seen it before, but because I shall need to refer to it. Recall that the Fourier transform of a function f:\mathbb{F}_3^n\to\mathbb{C} is defined by the formula


where \mathbb{E} is short for 3^{-n}\sum, \omega stands for \exp(2\pi i/3) and r.x is short for \sum_ir_ix_i. Now


(Here \mathbb{E} stands for 3^{-2n}\sum, since there are 3^{2n} solutions of x+y+z=0.) By the convolution identity and the inversion formula, this is equal to \sum_r\hat{f}(r)^3.

Now let f be the characteristic function of a subset A\subset\mathbb{F}_3^n of density \delta. Then \hat{f}(0)=\delta. Therefore, if A contains no solutions of x+y+z=0 (apart from degenerate ones — I’ll ignore that slight qualification for the purposes of this sketch as it makes the argument slightly less neat without affecting its substance) we may deduce that

\sum_{r\ne 0}|\hat{f}(r)|^3\geq\delta^3.

Now Parseval’s identity tells us that


from which it follows that \max_{r\ne 0}|\hat{f}(r)|\geq\delta^2.

Recall that \hat{f}(r)=\mathbb{E}_xf(x)\omega^{r.x}. The function x\mapsto\omega^{r.x} is constant on each of the three hyperplanes r.x=b (here I interpret r.x as an element of \mathbb{F}_3). From this it is easy to show that there is a hyperplane H such that \mathbb{E}_{x\in H}f(x)\geq\delta+c\delta^2 for some absolute constant c. (If you can’t be bothered to do the calculation, the basic point to take away is that if \hat{f}(r)\geq\alpha then there is a hyperplane perpendicular to r on which A has density at least \delta+c\alpha, where c is an absolute constant. The converse holds too, though you recover the original bound for the Fourier coefficient only up to an absolute constant, so non-trivial Fourier coefficients and density increases on hyperplanes are essentially the same thing in this context.)

Thus, if A contains no arithmetic progression of length 3, there is a hyperplane inside which the density of A is at least \delta+c\delta^2. If we iterate this argument 1/c\delta times, then we can double the (relative) density of A. If we iterate it another 1/2c\delta times, we can double it again, and so on. The number of iterations is at most 2/c\delta, so by that time there must be an arithmetic progression of length 3. This tells us that we need lose only 2/c\delta dimensions, so for the argument to work we need n\geq 2/c\delta, or equivalently \delta\geq C/n.


Lecture 12

Error-Correcting Codes

We discussed error-correcting codes. A binary code C is simply a subset of the discrete n-dimensional cube. This is a familiar object but in coding theory we asked different questions about it. A code is linear if it forms a vector space over (Z/2Z)^n. The minimal distance of a code is the minimum Hamming distance between two distinct elements, and in the case of linear codes it is simply the minimum weight of a non-zero element of the codes. We mentioned codes over larger alphabets, spherical codes and even codes in more general metric spaces. Error-correcting codes are among the most glorious applications of mathematics and their theory is related to many topics in pure mathematics and theoretical computer science.

1) An extremal problem for codes: What is the maximum size of a binary code of length n with minimal distance d. We mentioned the volume (or Hamming) upper bound and the Gilbert-Varshamov lower bound. We concentrated on the case of codes of positive rate.

2) Examples of codes: We mentioned the Hamming code and the Hadamard code and considered some of their basic properties. Then we mentioned the long code which is very important in the study of Hardness of computation.

3) Linearity testing. Linearity testing is closely related to the Hadamard code. We described Blum-Luby-Rubinfeld linearity test and analyzed it. This is very similar to the Fourier theoretic formula and argument we saw last time for the cap problem.

We start to describe Delsartes linear Programming method to be continued next week.

Fractional Sylvester-Gallai

Avi Wigderson was in town and gave a beautiful talk about an extension of Sylvester-Gallai theorem. Here is a link to the paper: Rank bounds for design matrices with applications to combinatorial geometry and locally correctable codes by Boaz Barak, Zeev Dvir, Avi Wigderson, and Amir Yehudayoff.


The Sylvester-Gallai Theorem:  Let X be a finite set of n points in an eulidean space such that for every two distinct points x,y \in X the line through x and y contains a third point z \in X. Then all points in X are contained in a line. 

I heard about this result when I took Benjy Weiss’s mathematics course for high-school students in 1970/1. a  The Sylvester-Gallai theorem was the last question marked with (*) in the first week’s homework. In one of the next meetings Benjy listened carefully to our ideas on how to prove it and then explained to us why our attempts of proving it are doomed to fail: What we tried to do only relied on the very basic incidence axioms of Euclidean geometry but the Sylvester-Gallai theorem does not hold for finite projective planes. (Sylvester conjectured the result in 1893. The first proof was given by Mechior in 1940 and Gallai proved it in 1945.)

My MO question

Befor describing the new results let me mention my third ever MathOverflow question that was about potential extensions of the G-S theorem. The question was roughly this:

Suppose that V is an r dimensional variety embedded into n space so that if the intersection of every j-dimensional subspace with V is full dimensional then this intersection  is “complicated”. Then n cannot be too large.

I will not reproduce the full question here but only a memorable remark made by Greg Kuperberg:

If you claimed that Gil is short for Gilvester (which is a real first name although rare), then you could say that any of your results is the “Gilvester Kalai theorem”. – Greg Kuperberg Nov 24 2009 at 5:13

The result by Barak, Dvir, Wigderson and Yehudayoff

Theorem:  Let X be a finite set of n points in an Euclidean space such that for every point x \in X the number of y, y\in X,y \ne x such that the line through x and y contains another point of X is at least \delta (n-1). Then

\dim (Aff(X))\le 13/\delta^2

Some remarks:

1) The proof: The first ingredient of the proof is a translation of the theorem into a question about ranks of matrices with a certain combinatorial structure. The next thing is to observe is that when the non zero entries of the matrix are 1’s the claim is simple. The second surprising ingredient of the proof is to use scaling in order to “tame” the entries of the matrix.

2)  The context – locally correctable codes:  A q-query locally correctable (q,\delta)-code over a field F is a subspace of F^n so that, given any element \tilde y that disagrees with some y \in C in at most \delta n positions and an index i, 1 \le i \le n we can recover y_i with probability 3/4 by reading at most q coordinates of \tilde y.  The theorem stated above imply that, for two queries,  over the real numbers (and also over the complex numbers), such codes do not exist when n is large. Another context where the result is of interest is the hot area of sum product theorems and related questions in the geometry of incidences.

3) Some open problems: Is there a more detailed structure theorem for configurations of points satisfying the condition of the theorem? Can the result be improved to \dim (Aff(X))=O(1/\delta )? Can a similar result be proved on locally correctable codes with more than two queries? This also translates into an interesting Sylvester-Gallai type question but it will require, Avi said, new ideas.