Questions for Lectures 1-3.
The first set of questions covers the first four lectures, dealing with parallel repetition, unique games, and spectral methods in geometry.
(Dirichlet boundary conditions, 1 pt) Let be a graph with and . Define
where is the combinatorial Laplacian of . Show that there exists a vector with for all , for every , and for .
(Tensorization of the SDP value, 1 pt) Consider the SDP of Figure 1 here. First find its SDP dual. Then show that the SDP value tensorizes, in the sense that for any unique game and , we have .
(Correlated rounding, 1pt) Let , and let be the Euclidean norm. Consider the following process: Let be uniformly random points, and for every , put , where is a Euclidean ball of radius about . Clearly partitions with probability 1. For any point , let be the index for which . Use an analysis similar to that in Lecture 2 to show that for every , we have
(Randomized Whitney decomposition, 2 pts) Using the preceding rounding scheme, solve the following problem. Let be any finite set. For any point and subset , let . Show that there exists a random mapping which satisfies the following three properties.
- for every
- With probability 1, for all , .
- For any , .
Notice that property (2) implies property (1). The map is like a random “retraction” of the space onto the subset (or think about it as a correlated way of every point in choosing a point of to associate itself with). The retraction has the property that no point is mapped too much further away than it has to be, and no pair of points gets mapped too far away from each other in expectation. [Hint: You will have to use many different values of from the preceding problem. Think first about obtaining a random map satisfying (1)-(3), where .]
(Non-independent repetition, 1-5 pts) Give a detailed discussion of how one might get gap amplification for unique games using a game with questions asked in parallel, but which are not necessarily chosen uniformly at random. Start with the odd-cycle game, and think about different ways of correlating the questions (e.g. with respect to a group other than ). Report on your findings.
(Improved SDP rounding, 5 pts) Show that one can take in this paper, instead of the bound which the authors achieve.
(Borsuk-Ulam, 1 dimension down, 1 pt) Do Exercise 5 on page 29 here.
(Basic spectral graph theory, 1 pt) Do problems 1-4 here.
Harmonic analysis of boolean functions.
Ryan’s lecture notes may help as a reference.
(Long code testing, 1pt) Do this homework set. We have done problems (2) and (3) in class, so those should be easy. Problem 1(c) may require you to lookup the definition of a long code.
(Around hypercontractivity, 1pt) Do problems 2, 3, and 5 here.
(Influences, 1pt) Do problems 2, 3, and 6 here.
(Full Bonami-Beckner?, 1pt) In class we showed how to compute a lower bound on for locality sensitive hashing, using a bound on where is a random walk run for steps started at a random point in . The argument here uses the Bonami-Beckner inequality to upper bound this probability. Previously, we saw a waker version . Does this version suffice to obtain the asymptotic lower bound ? Give a detailed explanation of why or why not.
(Random walks with two sets, 1pt) In class, we obtained an upper bound on using Fourier analysis and the Bonami-Beckner inequality (or see the argument here). Obtain a related upper bound on for general .
Structure vs. Randomness
(Progressions which correlate with characters, 1pt) Prove that for every , there exists an arithmetic progression such that and .