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