On Sparsest Cut and Parallel Repetition

We consider the following three problems in the areas of Algorithms, Complexity theory and  Streaming algorithms respectively.

1) Given a graph $G=(V,E)$, the Sparsest Cut problem asks for a partition of the vertices (i.e. a  cut) $S \subseteq V$ with minimum \emph{sparsity}: $\phi(S) = \frac{|E(S, \bar{S})|}{|S||\bar{S}|}$. We investigate the power of using a well-known semi-definite programming  (SDP) relaxation to solve for the Sparsest Cut on \emph{expander-like} graphs, and give an intuitive algorithm that has good guarantees for this class of graphs. Furthermore, we show that our result on expander-like graphs suitably generalizes a theorem due to Goemans on embedding certain metrics into $\ell_1$-space.

2) The Parallel Repetition theorem proven by Raz is a key result that yields a PCP theorem statement useful for proving many hardness of approximation results. Recently, Moshkovitz gave a simple proof of a version of the Parallel Repetition theorem  that suffices for many hardness results, by using a transformation called `fortification'. We investigate this technique further and prove new results about fortification in our work.  In particular, we propose a method for fortification using spectral expanders, and prove its optimality. This has important consequences: it rules out the possibility of proving stronger hardness results via fortification than the ones known earlier.

3) A $n$-uniform hypergraph $H=(V,E)$ is said to be two-colorable if we can find a function (coloring) $\chi: V \rightarrow \{Red, Blue\}$ on its vertices such that no hyperedge is monochromatic. For $n=2$, the problem of checking if $H$ is two-colorable is just the problem of determining if a graph is bipartite, but even for $n=3$, this is NP-hard. Inspired by work in graph streaming algorithms, we consider the problem of finding a two-coloring for hypergraphs (which are given to be two-colorable) in the \emph{streaming model}. Using communication complexity techniques, we prove strong lower bounds on the space requirements of deterministic one-pass streaming algorithms that find a two-coloring of $H$. We also provide efficient communication protocols that utilize two-passes, indicating that proving multi-pass lower bounds will require new insights.