Hard combinatorial optimization problems are often approximated using linear or semidefinite programming relaxations. In fact, most of the algorithms developed using such convex programs have special structure: the constraints imposed by these algorithms are local i.e. each constraint involves only few variables in the problem. In this thesis, we study the power of such local constraints in providing an approximation for various optimization problems.

We study various models of computation defined in terms of such programs with local constraints. The resource in question for these models is are the sizes of the constraints involved in the

program. Known algorithmic results relate this notion of resources to the time taken for computation in a natural way.

Such models are provided by the ``hierarchies" of linear and semidefinite programs, like the ones defined by Lov {a}sz and Schrijver; Sherali and Adams; and Lasserre. We study the complexity of approximating various optimization problems using each of these hierarchies.

This thesis contains various lower bounds in this computational model. We develop techniques for reasoning about each of these hierarchies and exhibiting various combinatorial objects whose local properties are very different from their global properties. Such lower bounds {\em unconditionally} rule out a large class of algorithms (which captures most known ones) for approximating the problems such as MAX 3-SAT, Minimum Vertex Cover, Chromatic Number and others studied in this thesis.

We also provide a positive result where a simple semidefinite relaxation is useful for approximating a constraint satisfaction problem defined on graphs, if the underlying graph is expanding. We show how expansion connects the local properties of the graph to the global properties of interest, thus providing a good algorithm.

NP-complete combinatorial optimization problems are important and well-studied, but remain largely enigmatic in fundamental ways. While efficiently finding the optimal solution to such a problem requires that P = NP, we can try to find approximately optimal solutions. To date, the most promising approach for approximating many combinatorial optimization problems has been semidefinite programming, a generalization of linear programming. However semidefinite programs are not as well understood as linear programs. An important question is whether semidefinite (or linear) programs can be improved to create better algorithms.

Several processes--Lovasz-Schrijver+ (LS+) and the stronger Lasserre hierarchy for semidefinite programs, and Lovasz-Schrijver (LS), and the stronger Sherali-Adams hierarchy for linear programs--were create to systematically improve semidefinite and linear programs at the cost of additional runtime. This thesis studies the question: ``What is the tradeoff between the efficiency and the guaranteed approximation in these hierarchies?" These systems proceed in rounds (and thus are usually referred to as hierarchies) and all have in common that after n rounds, where n is the number of variables, they find the optimal solution, and they take time n^{O(r)} to run until the rth round. An ``integrality gap" of α after r rounds for one of these hierarchies proves that the algorithms generated by the hierarchy cannot find an α approximate solution in time n^{Omega(r)}.

Unlike NP-hardness results, these results are unconditional, yet apply only to a large, but restricted, class of algorithms. However, very low levels of these hierarchies include some of the most celebrated approximation algorithms for NP-complete problems. For example, the first level of LS+ (and hence also Lasserre) for the IndependentSet problem implies the Lovasz theta-function and for the MaxCut problem gives the Goemans-Williamson relaxation. The ARV relaxation of the SparsestCut problem is no stronger than the relaxation given in the second level of LS+ (and hence also Lasserre).

This thesis shows an optimal integrality gap of 2-epsilon for Omega(n) rounds the LS hierarchy relaxation of the VertexCover and MaxCut problems. This result implies that a very large class of linear programs require exponential time to solve VertexCover (or MaxCut) to better than a factor of 2, even on random graphs. The previously best known 2-epsilon integrality gap for VertexCover only survived Omega(log(n)) round of LS, and the previously best known 1/2+epsilon integrality gap for MaxCut survived any constant number of rounds of SA (and for thus LS). These results were the first to illustrate the stark difference between linear program relaxations and semidefinite program relaxations (because MaxCut is better approximated after just one round by LS+).

Additionally this thesis shows that even after Omega(n) rounds, the Lasserre hierarchy cannot refute a random 3XOR formula. This is the first non-trivial integrality gap for the Lasserre hierarchy, the strongest of all the aforementioned hierarchies. As mentioned above, this result unconditionally rules out the possibility of a subexponential time algorithm for random 3-SAT over a large range of semidefinite programs. There are, additionally, many immediate corollaries such as a similar integrality gap of 7/6 - epsilon for VertexCover. The techniques in the thesis remain the only known way of obtaining integrality gaps for Lasserre.

In the first part of this thesis, we consider the construction of unconditional pseudorandom generators whose outputs look random to depth-2 boolean circuits. We prove the existence of a $poly(n,m)$-time computable pseudorandom generator which ``$1/poly(n,m)$-fools'' DNFs with $n$ variables and $m$ terms, and has seed length $O(log^2 nm cdot loglog nm)$. Previously, the best pseudorandom generator for depth-2 circuits had seed length $O(log^3 nm)$, and was due to Bazzi (FOCS 2007).

It follows from our proof that a $1/m^{tilde O(log mn)}$-biased distribution $1/poly(nm)$-fools DNFs with $m$ terms and $n$ variables. For inverse polynomial distinguishing probability this is nearly tight because we show that for every $m,delta$ there is a $1/m^{Omega(log 1/delta)}$-biased distribution $X$ and a DNF $phi$ with $m$ terms such that $phi$ is not $delta$-fooled by $X$.

For the case of {em read-once} DNFs, we show that seed length $O(log mn cdot log 1/delta)$ suffices, which is an improvement for large $delta$.

It also follows from our proof that a $1/m^{O(log 1/delta)}$-biased distribution $delta$-fools all read-once DNFs with $m$ terms. We show that this result too is nearly tight, by constructing a $1/m^{tilde Omega(log 1/delta)}$-biased distribution that does not $delta$-fool a certain $m$-term read-once DNF.

In the second part of this thesis, we consider Goldreich's (ECCC 2000) proposed candidate one-way function construction which is parameterized by the choice of a small predicate (over $d$ variables) and of a bipartite expanding graph of right-degree $d$. The function is computed by labeling the $n$ vertices on the left with the bits of the input, labeling each of the $n$ vertices on the right with the value of the predicate applied to the neighbors, and outputting the $n$-bit string of labels of the vertices on the right.

Inverting Goldreich's one-way function is equivalent to finding a solution for a certain constraint satisfaction problem with a ``planted solution.'' Such a problem easily reduces to SAT, and so the use of SAT solvers constitutes a natural class of attacks.

We initiate a rigorous study of the limitations of backtracking attacks against Goldreich's function. Results by Alekhnovich, Hirsch and Itsykson imply that Goldreich's function is secure against ``myopic'' backtracking algorithms (an interesting subclass) if the 3-ary parity predicate $P(x_1,x_2,x_3) = x_1 oplus x_2 oplus x_3$ is used. However, the construction must use non-linear predicates; otherwise inversion succumbs to a trivial attack via Gaussian elimination.

We generalize the work of Alekhnovich et al. to handle more general classes of predicates, and we present a lower bound for the construction that uses random predicates or predicates of the form ( P (x_1,ldots,x_d) = x_1 oplus x_2 oplus cdots oplus x_{d-h} oplus Q(x_{d-h+1}, ldots, x_d), )

and a random graph.

We also study how far Goldreich's function is from an injective function. We give upper bounds of the form $2^{2^{-Omega(d)} n}$ on the average size of preimages of Goldreich's function when the graph $G$ is random,

and the predicate $P$ is random or $P = x_1 oplus x_2 oplus cdots oplus x_{d-h} oplus Q(x_{d-h+1}, ldots, x_d)$ for $d-h=Omega(d)$.

In this dissertation, we study two problems that have the theme of extracting information from lower dimensional samples.

A number of recent works have studied algorithms for entrywise $\ell_p$-\emph{low rank approximation}, namely algorithms which given an $n \times d$ matrix $A$ (with $n \geq d$), output a rank-$k$ matrix $B$ minimizing $\|A-B\|_p^p=\sum_{i,j} |A_{i,j} - B_{i,j}|^p$ when $p > 0$; and $\|A-B\|_0 = \sum_{i,j} [A_{i,j} \neq B_{i,j}]$ for $p=0$, where $\|A-B\|_0$ denotes the number of entries $(i,j)$ for which $A_{i,j} \neq B_{i,j}$.

For $p = 1$, this is often considered more robust than the SVD, while for $p = 0$ this corresponds to minimizing the number of disagreements, or robust PCA. This problem is known to be NP-hard for $p \in \{0,1\}$, already for $k = 1$, and while there are polynomial time approximation algorithms, their approximation factor is at best $\poly(k)$. It was left open if there was a polynomial-time approximation scheme (PTAS) for $\ell_p$-approximation for any $p \geq 0$. We show the following:

\begin{enumerate}

\item On the algorithmic side, for $p \in (0,2)$, we use a technique called \emph{sketching} to give the first $n^{\poly(k/\eps)}$ time $(1+\eps)$-approximation algorithm. For $p = 0$, there are various problem formulations, a common one being the binary setting for which $A\in\{0,1\}^{n\times d}$ and $B = U \cdot V$, where $U\in\{0,1\}^{n \times k}$ and $V\in\{0,1\}^{k \times d}$. For this setting, we obtain an algorithm with time $n \cdot d^{\poly(k/\eps)}$.

\item On the hardness front, for $p \in (1,2)$, we show under the Small Set Expansion Hypothesis and Exponential Time Hypothesis (ETH), there is no constant factor approximation algorithm running in time $2^{k^{\delta}}$ for a constant $\delta > 0$, showing an exponential dependence on $k$ is necessary. We also show for finite fields of constant size, under the ETH, that any fixed constant factor approximation algorithm requires $2^{k^{\delta}}$ time for a constant $\delta > 0$.

\end{enumerate}

\emph{Population recovery} is the problem of learning an unknown distribution over an unknown set of $n$-bit strings, given access to independent \emph{traces} from the distribution that have been independently corrupted according to some noise channel. Recent work has intensively studied such problems both for the {bit-flip} noise channel and for the erasure noise channel.

In this dissertation we initiate the study of population recovery under the \emph{deletion channel}, in which each bit $b$ is independently \emph{deleted} with some fixed probability and the surviving bits are concatenated and transmitted. This is a far more challenging noise model than bit-flip~noise or erasure noise; indeed, even the simplest case in which the population is of size 1 (corresponding to a trivial probability distribution supported on a single string) corresponds to the \emph{trace reconstruction} problem, which is a challenging problem that has received much recent attention.

In this work we give algorithms and lower bounds for population recovery under the deletion channel when the population size is some value $\ell > 1$. As our main sample complexity upper bound, we show that for any population size $\ell = o(\log n / \log \log n)$, a population of $\ell$ strings from $\zo^n$ can be learned under deletion channel noise using $\smash{2^{n^{1/2 + o(1)}}}$ samples. On the lower bound side, we show that at least $n^{\Omega{(\ell)}}$ samples are required to perform population recovery under the deletion channel when the population size is $\ell$, for all $\ell \leq n^{1/2 - \epsilon}$.

This dissertation explores the multifaceted interplay between efficient computation and probability distributions. We organize the aspects of this interplay according to whether the randomness occurs primarily at the level of the problem or the level of the algorithm, and orthogonally according to whether the output is random or the input is random.

Part I concerns settings where the problem's output is random. A sampling problem associates to each input x a probability distribution D(x), and the goal is to output a sample from D(x) (or at least get statistically close) when given x. Although sampling algorithms are fundamental tools in statistical physics, combinatorial optimization, and cryptography, and algorithms for a wide variety of sampling problems have been discovered, there has been comparatively little research viewing sampling through the lens of computational complexity. We contribute to the understanding of the power and limitations of efficient sampling by proving a time hierarchy theorem which shows, roughly, that “a little more time gives a lot more power to sampling algorithms.”

Part II concerns settings where the algorithm's output is random. Even when the specification of a computational problem involves no randomness, one can still consider randomized algorithms that produce a correct output with high probability. A basic question is whether one can derandomize algorithms, i.e., reduce or eliminate their dependence on randomness without incurring much loss in efficiency. Although derandomizing arbitrary time-efficient algorithms can only be done assuming unproven complexity-theoretic conjectures, it is possible to unconditionally construct derandomization tools called pseudorandom generators for restricted classes of algorithms. We give an improved pseudorandom generator for a new class, which we call combinatorial checkerboards. The notion of pseudorandomness shows up in many contexts besides derandomization. The so-called Dense Model Theorem, which has its roots in the famous theorem of Green and Tao that the primes contain arbitrarily long arithmetic progressions, is a result about pseudorandomness that has turned out to be a useful tool in computational complexity and cryptography. At the heart of this theorem is a certain type of reduction, and in this dissertation we prove a strong lower bound on the advice complexity of such reductions, which is analogous to a list size lower bound for list-decoding of error-correcting codes.

Part III concerns settings where the problem's input is random. We focus on the topic of randomness extraction, which is the problem of transforming a sample from a high-entropy but non-uniform probability distribution (that represents an imperfect physical source of randomness) into a uniformly distributed sample (which would then be suitable for use by a randomized algorithm). It is natural to model the input distribution as being sampled by an efficient algorithm (since randomness is generated by efficient processes in nature), and we give a construction of an extractor for the case where the input distribution's sampler is extremely efficient in parallel time. A related problem is to estimate the min-entropy (“amount of randomness”) of a given parallel-time-efficient sampler, since this dictates how many uniformly random output bits one could hope to extract from it. We characterize the complexity of this problem, showing that it is “slightly harder than NP-complete.”

Part IV concerns settings where the algorithm's input is random. Average-case complexity is the study of the power of algorithms that are allowed to fail with small probability over a randomly chosen input. This topic is motivated by cryptography and by modeling heuristics. A fundamental open question is whether the average-case hardness of NP is implied by the worst-case hardness of NP. We exhibit a new barrier to showing this implication, by proving that a certain general technique (namely, “relativizing proofs by reduction”) cannot be used. We also prove results on hardness amplification, clarifying the quantitative relationship between the running time of an algorithm and the probability of failure over a random input (both of which are desirable to minimize).

The thesis explores efficient learning algorithms in settings which are more restrictive than the PAC model of learning (Valiant) in one of the following two senses: (i) The learning algorithm has a very weak access to the unknown function, as in, it does not get labeled samples for the unknown function (ii) The error guarantee required from the hypothesis is more stringent than the PAC model.

Ever since its introduction, the PAC model of learning is considered as the standard model of learning. However, there are many situations encountered in practice in which the PAC model does not adequately model the learning problem in hand. To meet this limitation, several other models have been introduced for e.g. the agnostic learning model, the restricted focus of attention model, the positive examples only model amongst others. The last two models are the ones which are most relevant to the work in this thesis.

Beyond the motivation of modeling learning problems, another reason to consider these alternate models is because of the rich interplay between the questions arising here and other areas like computational complexity theory and social choice theory. Further, the study of these models lead to interesting questions in discrete Fourier analysis and probability theory. In fact, the connections forged between these learning questions and Fourier analysis and probability theory are key to the results in this thesis.

Part~1 of this thesis is motivated by an easy theorem of C.K. Chow who showed that over the uniform distribution on the hypercube, a halfspace is uniquely identified (in the space of all Boolean functions) by its expectation and correlation with the input bits. Rephrased in the language of Fourier analysis, if f is a halfspace and g is any other Boolean function, such that the degree 0 and 1 Fourier coefficients of f and g are the same, then f and g are identical over the hypercube. The degree 0 and 1 Fourier coefficients of f are sometimes called the Chow parameters of f. Chow's result immediately gives rise to two questions: The first is whether this characterization is robust i.e.~ if the Chow parameters of f and g are close to each other and f is halfspace, then are f and g close to each other in Hamming distance? The second question is whether Chow's characterization is algorithmic. In other words, is there an efficient algorithm which given the Chow parameters of a halfspace f, can reconstruct the halfspace f (exactly or approximately)? Chapter 2 answers both these questions in the affirmative and in fact shows a strong connection between the answers to the two questions.

In Chapter 3, we consider a different generalization of the theorem of Chow. It is easy to extend the theorem of Chow that show over any distribution D on the hypercube (which has full support), a halfspace f is completely characterized within the space of all Boolean functions by its expectation and correlation with the input bits. Similar to Chapter 2, one can ask if this characterization can be made algorithmic and robust. While the question is interesting in its own right, for specific choices of distribution D, this problem has been investigated intensively in the social choice literature where it is known as Inverse power index problem. Informally speaking, the function f is viewed as a voting function and the correlation between f and an input bit is viewed as the influence of that input bit (The distribution D is dependent on the definition of influence that is used). Arguably the most popular choice for power indices in social choice literature is the Shapley-Shubik indices. Despite much interest in the Inverse power index problem for Shapley-Shubik indices, prior to our work, there was no rigorous algorithm for this problem. In Chapter 3, we give the first polynomial time approximation scheme for the Inverse power index problem for Shapley-Shubik indices.

Part 2 of this thesis is motivated by the problem of learning distributions over the hypercube. While the problem of learning distributions has a rich history in statistics and computer science, there has not been much work in learning distributions over the hypercube which are interesting from the point of view of Boolean functions. While most natural learning problems that can be framed in this context can easily shown to be hard (under cryptographic assumption), a sweet spot comes from the following kind of learning problems: Let C be an interesting class of Boolean functions (say halfspaces). Given an unknown f in C, the distribution learning problem we consider is to learn the uniform distribution over f^{-1}(1) provided we have access to random samples from this set. This question has interesting connections to questions in complexity theory like sampling NP solutions among others. In Chapter 3, we consider this problem for many different instantiations of the class C. While we give efficient algorithms for classes like halfspaces and DNFs, we show that classes like CNFs and degree-d polynomial threshold functions which are learnable in the standard PAC model, are cryptographically hard to learn in this context.

In this thesis we prove the following results.

1. We show that the multiplicity of the second normalized adjacency matrix eigenvalueof any connected graph of maximum degree Δ is bounded by nΔ^(7/5)/polylog(n) for any Δ, and n*polylog(d)/polylog(n) for simple d-regular graphs when d is sufficiently large.

2. Let G be a random d-regular graph. We prove that for every constant α > 0, withhigh probability every eigenvector of the adjacency matrix of G with eigenvalue less than −2√(d − 2) − α has Ω(n/polylog(n)) nodal domains.

3. For every d = p + 1 for prime p and infinitely many n, we exhibit an n-vertexd-regular graph with girth Ω(log_(d−1) n) and vertex expansion of sublinear sized sets upper bounded by (d+1)/2 whose nontrivial eigenvalues are bounded in magnitude by 2√(d − 1) + O(1/log n). This gives a high-girth version of Kahale’s example showing Ramanujan graphs can have poor vertex expansion.

4. Anantharaman and Le Masson proved that any family of eigenbases of the adjacencyoperators of a family of graphs is quantum ergodic, assuming the graphs satisfy conditions of expansion and high girth. We show that neither of these two conditions is sufficient by itself to imply quantum ergodicity (which is a form of delocalization).

These results although different in nature, all exhibit the utility of the structure of eigenvectors.The main ingredient in the first result is a polynomial (in k) lower bound on the typical support of a closed random walk of length 2k in any connected graph, which in turn relies on new lower bounds for the entries of the Perron eigenvector of submatrices of the normalized adjacency matrix. The second result suggests Gaussian behavior of eigenvectors of random regular graphs conjectured by Elon, a discrete analog of Berry’s conjecture. The third result shows that properties that are sufficient to imply eigenvector delocalization are not strong enough to imply vertex expansion. The theorems and examples in the fourth result show why Anantharaman and Le Masson’s quantum ergodicity result requires expansion both at a global scale (spectral expansion) and a local scale (high girth).

We show optimal (up to a constant factor) NP-hardness for maximum constraint satisfaction problem with k variables per constraint (Max-k-CSP), whenever k is larger than the domain size. This follows from our main result concerning CSPs given by a predicate: a CSP is approximation resistant if its predicate contains a subgroup that is balanced pairwise independent. Our main result is analogous to Austrin and Mossel's, bypassing their Unique-Games Conjecture assumption whenever the predicate is an abelian subgroup.

Our main ingredient is a new gap-amplification technique inspired by XOR-lemmas. Using this technique, we also improve the NP-hardness of approximating Independent-Set on bounded-degree graphs, Almost-Coloring, Two-Prover-One-Round-Game, and various other problems.

We study the connection between pebble games and complexity.

First, we derive complexity results using pebble games.

It is shown that three pebble games used for studying computational complexity are equivalent: namely, the two-person pebble game of Dymond-Tompa, the two-person pebble game of Raz-McKenzie, and the one-person reversible pebble game of Bennett have the same pebble costs over any directed acyclic graph.

The three pebble games have been used for studying parallel complexity and for proving lower bounds under restricted settings, and we show one more such lower bound on circuit-depth.

Second, the pebble costs are applied to proof complexity.

Concerning a family of unsatisfiable CNFs called pebbling contradictions, the pebble cost in any of the pebble games controls the scaling of some parameters of resolution refutations.

Namely, the pebble cost controls the minimum depth of resolution refutations and the minimum size of tree-like resolution refutations.

Finally, we study the space complexity of computing the pebble costs and of computing the minimum depth of resolution refutations.

It is PSPACE-complete to compute the pebble cost in any of the three pebble games, and to compute the minimum depth of resolution refutations.

The theory of NP-hardness of approximation has led to numerous tight characterizations of approximability of hard combinatorial optimization problems. Nonetheless, there are many fundamental problems which are out of reach for these techniques, such as problems that can be solved (or approximated) in quasi-polynomial time, parameterized problems and problems in P.

This dissertation continues the line of work that develops techniques to show inapproximability results for these problems. In the process, we provide hardness of approximation results for the following problems.

- Problems Between P and NP: Dense Constraint Satisfaction Problems (CSPs), Densest k-Subgraph with Perfect Completeness, VC Dimension, and Littlestone's Dimension.

- Parameterized Problems: k-Dominating Set, k-Clique, k-Biclique, Densest k-Subgraph, Parameterized 2-CSPs, Directed Steiner Network, k-Even Set, and k-Shortest Vector.

- Problems in P: Closest Pair, and Maximum Inner Product.

Some of our results, such as those for Densest k-Subgraph, Directed Steiner Network and Parameterized 2-CSP, also present the best known inapproximability factors for the problems, even in the (believed) NP-hard regime. Furthermore, our results for k-Dominating Set and k-Even Set resolve two long-standing open questions in the field of parameterized complexity.