No time for Gowers Uniformity
On Friday I give my second research talk, this time about the PCP results in this work done with Alex Samorodnitsky. This is the stuff that I have been most excited about in a long time. To analyse a certain PCP construction, it turns out that the ideal anlytic tool is the "Gowers uniformity" of a finite function. Gowers uniformity is a sort of measure of pseudorandomness, and there is a precise technical sense in which the use of this tool can be seen as "generalized Fourier analysis."
Gowers introduced this notion (obviously, he just called it "uniformity") to give an analytic proof of Szemeredi's Theorem on arithmetic progressions (not to be confused with Szemeredi's Regularity Lemma, which was developed as part of the proof of the Theorem). Previously, an analytic proof (with good quantitative bounds) based on Fourier analysis was known for the case of progressions of length 3, and for the general case the only known proofs were Szemeredi's one (that used the regularity Lemma and hence had a terrible quantitative form) and Furstenberg's proof based on ergodic theorey (that uses the axiom of choice and has no quantitative form at all). There is a very clear technical difficulty in using a Fourier-analytic approach for the case of longer sequences, and Gowers approach breaks very elegantly through it.
It is intiguing that the Fourier analytic expressions that one gets in the length-3 case of Szemeredi's theorem are similar to the expressions that one gets in the study of linearity testing and PCPs, and that the technical difficulty for progressions of length 4 is similar to a bottleneck that one encounters in defining PCPs that are very query-efficient.
So, perhaps it is not surprising that this notion has been useful in our analysis. In any case, Fourier analysis over finite Abelian groups is used in several other places in computer science, notably in learning and in circuit lower bounds, and I think it is likely that a technique that has "gone beyong Fourier analysis" in two such unrelated areas as additive combinatorics and PCP can find further powerful applications.
Unfortunately, I did not have time to tell this part of the story on Friday, as I wanted to spend some time explaining the PCP model and motivating the linearity testing and "influence testing" problems that we study.
Gowers introduced this notion (obviously, he just called it "uniformity") to give an analytic proof of Szemeredi's Theorem on arithmetic progressions (not to be confused with Szemeredi's Regularity Lemma, which was developed as part of the proof of the Theorem). Previously, an analytic proof (with good quantitative bounds) based on Fourier analysis was known for the case of progressions of length 3, and for the general case the only known proofs were Szemeredi's one (that used the regularity Lemma and hence had a terrible quantitative form) and Furstenberg's proof based on ergodic theorey (that uses the axiom of choice and has no quantitative form at all). There is a very clear technical difficulty in using a Fourier-analytic approach for the case of longer sequences, and Gowers approach breaks very elegantly through it.
It is intiguing that the Fourier analytic expressions that one gets in the length-3 case of Szemeredi's theorem are similar to the expressions that one gets in the study of linearity testing and PCPs, and that the technical difficulty for progressions of length 4 is similar to a bottleneck that one encounters in defining PCPs that are very query-efficient.
So, perhaps it is not surprising that this notion has been useful in our analysis. In any case, Fourier analysis over finite Abelian groups is used in several other places in computer science, notably in learning and in circuit lower bounds, and I think it is likely that a technique that has "gone beyong Fourier analysis" in two such unrelated areas as additive combinatorics and PCP can find further powerful applications.
Unfortunately, I did not have time to tell this part of the story on Friday, as I wanted to spend some time explaining the PCP model and motivating the linearity testing and "influence testing" problems that we study.
posted by Luca at 10:43 AM
0 Comments:
Post a Comment
<< Home