Homework questions for CSE599S

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 $G=(V,E)$ be a graph with $V = \{1,2,\ldots,n\}$ and $S \subseteq V$ . Define

$\displaystyle \lambda_1^S = \min_{\substack{0 \neq v \in \mathbb R^n \\ v|_S = 0}} \frac{\langle v, \Delta v\rangle}{\langle v,v\rangle},$

where $\Delta$ is the combinatorial Laplacian of $G$ . Show that there exists a vector $v \in \mathbb R^n$ with $(\Delta v)_i = \lambda_1^S v_i$ for all $i \notin S$ , $v_i \geq 0$ for every $i \in V$ , and $v_i = 0$ for $i \in S$ .

(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 $\mathcal G$ and $k \in \mathbb N$ , we have $\mathsf{sdpval}(\mathcal G^{\otimes k}) = \mathsf{sdpval}(\mathcal G)^k$ .

(Correlated rounding, 1pt) Let $X = [0,1]^d$ , and let $\|\cdot\|$ be the Euclidean norm. Consider the following process: Let $x_1, x_2, \ldots \in [0,1]^d$ be uniformly random points, and for every $i \geq 1$ , put $C_i = [B(x_i, r) \cap X] \setminus \bigcup_{j < i} C_j$ , where $B(x_i,r)$ is a Euclidean ball of radius $r$ about $x_i$ . Clearly $C_1 \cup C_2 \cup \cdots$ partitions $X$ with probability 1. For any point $x \in X$ , let $i(x)$ be the index $i$ for which $x \in C_i$ . Use an analysis similar to that in Lecture 2 to show that for every $x,y \in X$ , we have

$\displaystyle \Pr[i(x) \neq i(y)] \leq O(\sqrt{d}) \frac{\|x-y\|}{r}$

(Randomized Whitney decomposition, 2 pts) Using the preceding rounding scheme, solve the following problem. Let $S \subseteq X$ be any finite set. For any point $x \in X$ and subset $A \subseteq X$ , let $\mathsf{dist}(x,A) = \inf_{y \in A} \|x-y\|$ . Show that there exists a random mapping $F : X \to S$ which satisfies the following three properties.

$F(x)=x$ for every $x \in S$
With probability 1, for all $x \in X$ , $\|x-F(x)\| \leq O(\mathsf{dist}(x, S))$ .
For any $x,y \in X$ , $\displaystyle \mathbb E[\|F(x)-F(y)\|] \leq O(\sqrt{d}) \|x-y\|$ .

Notice that property (2) implies property (1). The map $F$ is like a random “retraction” of the space $X$ onto the subset $S$ (or think about it as a correlated way of every point in $\lbrack 0,1\rbrack^d$ choosing a point of $S$ 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 $r$ from the preceding problem. Think first about obtaining a random map $F : X' \to S$ satisfying (1)-(3), where $X' = \{ x \in X : \mathsf{dist}(x,A) = 0.1\}$ .]

(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 $\mathbb Z_m^k$ ). Report on your findings.

(Improved SDP rounding, 5 pts) Show that one can take $s = O(\log k)$ in this paper, instead of the bound $s =O(\log(k/\delta))$ which the authors achieve.

Topology.

(Borsuk-Ulam, 1 dimension down, 1 pt) Do Exercise 5 on page 29 here.

Spectral analysis.

(Intro, 1pt) Do problems 1-5 (the “undergraduate” problems) here. It may help to look at the course notes.

(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.

(Basic properties, 1pt) Do problems 1, 4, and 6 here and 1 and 2 here.

(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 $\rho_1(c)$ for locality sensitive hashing, using a bound on $\Pr[Q_B \in B]$ where $Q_B$ is a random walk run for $r$ steps started at a random point in $B \in \{0,1\}^d$ . The argument here uses the Bonami-Beckner inequality $\|T_{\varepsilon} f\|_2 \leq \|f\|_{1+\varepsilon^2}$ to upper bound this probability. Previously, we saw a waker version $\|T_{1/2} f\|_2 \leq 4 \|f\|_{4/3}$ . Does this version suffice to obtain the asymptotic lower bound $\rho_1(c) \gtrsim 1/c$ ? Give a detailed explanation of why or why not.

(Random walks with two sets, 1pt) In class, we obtained an upper bound on $\Pr[Q_B \in B]$ using Fourier analysis and the Bonami-Beckner inequality (or see the argument here). Obtain a related upper bound on $\Pr[Q_B \in A]$ for general $A,B \subseteq \{0,1\}^n$ .

Structure vs. Randomness

(Progressions which correlate with characters, 1pt) Prove that for every $\alpha \in \mathbb Z_N$ , there exists an arithmetic progression $P \subseteq \mathbb Z_N$ such that $|P| \geq \sqrt{N}/4$ and $|\hat P(\alpha)| \geq \frac{1}{2N} |P|$ .

Leave a Comment »

No comments yet.

RSS feed for comments on this post. TrackBack URI

	Nguyen Van Phuc on No frills proof of higher-orde…
	Nguyen Van Phuc on No frills proof of higher-orde…
	Nguyen Van Phuc_Viet… on No frills proof of higher-orde…
	Nguyen Van Phuc_Viet… on No frills proof of higher-orde…
	http://iwriteadirtyb… on Expanders from the action of…

tcs math – some mathematics of theoretical computer science