The video for Lecture 16 of the online course is available on the course web page.
|
||||||
|
This section is about the computational complexity of constraint satisfaction problems (CSPs), a fertile area of application for analysis of boolean functions. To study it we need to introduce a fair bit of background material; in fact, this section will mainly consist of definitions. The video for Lecture 15 of the online course is available on the course web page. The video for Lecture 14 of the online course is available on the course web page. The following message is from Elchanan Mossel at the Simons Institute: Dear Colleagues, The Simons Institute for Theory of computing will run a program on Real Analysis in Computer Science during the fall semester of 2013. Could you help spreading the word around, in particular to young scientists who may be interested to participate in the program as research fellows? More information about the fellowships (including how to apply) can be found here: http://simons.berkeley.edu/fellows.html More information about the program can be found here http://simons.berkeley.edu/program_realanalysis2013.html Yours, In the previous section we saw that every subproperty of the dictatorship property has a $3$-query local tester. In this section we will show that any property whatsoever has a $3$-query local tester — if an appropriate “proof” is provided. I originally planned for Chapter 9 of the book to be about additive combinatorics. However in the interests of completing the book before I die of old age, I am planning to make some cuts. It now looks like Chapter 9 (being a rather standalone topic in the context of the book) will hit the cutting room floor. Drafts of some parts of it are already written, and I decided to publish here a “deleted scene” — the Quasipolynomial Freiman–Ruzsa Theorem highlight. It seemed timely to me in light of several other very nice surveys/expositions/extensions that have appeared recently. Shachar Lovett has posted one survey here, and Eli Ben-Sasson, Noga Ron-Zewi, Madhur Tulsiani, and Julia Wolf have just posted a paper on the topic. Also, Sanders himself has a 1.5-page proof of his result in ${\mathbb F}_2^n$ in a manuscript called On the Bogolyubov–Ruzsa Lemma in ${\mathbb F}_2^n$; I don’t know if it’s appeared anywhere, but I’m sure he’ll send you a copy if you ask nicely Below is the draft of what was to appear in the book on this topic. I would like to emphasize that its interpretation/proof of the Croot–Sisask result is based on joint discussions with Eric Blais and Shachar Lovett. Continue reading Additive Combinatorics and the Polynomial Freiman–Rusza Conjecture The video for Lecture 13 of the online course is available on the course web page. The lectures and the book are now caught up In Chapter 1.6 we described the BLR property testing algorithm: given query access to an unknown function $f : \{0,1\}^n \to \{0,1\}$, this algorithm queries $f$ on a few random inputs and approximately determines whether $f$ has the property of being linear over ${\mathbb F}_2$. The field of property testing for boolean functions is concerned with coming up with similar algorithms for other properties. In this chapter we study several closely intertwined topics: property testing, probabilistically checkable proofs of proximity (PCPPs), and constraint satisfaction problems (CSPs). All of our work will be centred around the task of testing whether an unknown boolean function is a dictator. We begin by extending the BLR Test to give a $3$-query property testing algorithm for the class of dictator functions. This in turn allows us to give a $3$-query testing algorithm for any property, so long as the right “proof” is provided. We then introduce CSPs, which are in fact identical to string testing algorithms. Finally, we explain how dictator tests can be translated into computational complexity results for CSPs and we sketch the proofs of some of Håstad’s optimal inapproximability results. |
||||||
|
Copyright © 2013 Ryan O'Donnell -- All Rights Reserved |
||||||
Recent comments