The problem of recovering planted community structure in random graphs has received a lot of attention in the literature on the stochastic block model, where the input is a random graph in which edges crossing between different communities appear with smaller probability than edges induced by communities. The communities themselves form a collection of vertex-disjoint sparse cuts in the expected graph, and can be recovered, often exactly, from a sample as long as a separation condition on the intra- and inter-community edge probabilities is satisfied. In this paper, we ask whether the presence of a large number of overlapping sparsest cuts in the expected graph still allows recovery. For example, the d-dimensional hypercube graph admits d distinct (balanced) sparsest cuts, one for every coordinate. Can these cuts be identified given a random sample of the edges of the hypercube where each edge is present independently with some probability p ∈ (0, 1)? We show that this is the case, in a very strong sense: the sparsest balanced cut in a sample of the hypercube at rate p = Clog d/d for a sufficiently large constant C is 1/poly(d)-close to a coordinate cut with high probability. This is asymptotically optimal and allows approximate recovery of all d cuts simultaneously. Furthermore, for an appropriate sample of hypercube-like graphs recovery can be made exact. The proof is essentially a strong hypercube cut sparsification bound that combines a theorem of Friedgut, Kalai and Naor on boolean functions whose Fourier transform concentrates on the first level of the Fourier spectrum with Karger’s cut counting argument.

We study the minority-opinion dynamics over a fully-connected network of n nodes with binary opinions. Upon activation, a node receives a sample of opinions from a limited number of neighbors chosen uniformly at random. Each activated node then adopts the opinion that is least common within the received sample.

We give new rounding schemes for SDP relaxations for the problems of maximizing cubic polynomials over the unit sphere and the n-dimensional hypercube. In both cases, the resulting algorithms yield a multiplicative approximation in 2O(k) poly(n) time. In particular, we obtain a approximation in polynomial time. For the unit sphere, this improves on the rounding algorithms of [5] that need quasi-polynomial time to obtain a similar approximation guarantee. Over the n-dimensional hypercube, our results match the guarantee of a search algorithm of Khot and Naor [19] that obtains a similar approximation ratio via techniques from convex geometry. Unlike their method, our algorithm obtains an upper bound on the integrality gap of SDP relaxations for the problem and as a result, also yields a certificate on the optimum value of the input instance. Our results naturally generalize to homogeneous polynomials of higher degree and imply improved algorithms for approximating satisfiable instances of Max-3SAT.

We define a novel notion of "non-backtracking" matrix associated to any symmetric matrix, and we prove a "Ihara-Bass" type formula for it. We use this theory to prove new results on polynomial-time strong refutations of random constraint satisfaction problems with k variables per constraints (k-CSPs). For a random k-CSP instance constructed out of a constraint that is satisfied by a p fraction of assignments, if the instance contains n variables and n^{k/2} / ε² constraints, we can efficiently compute a certificate that the optimum satisfies at most a p+O_k(ε) fraction of constraints. Previously, this was known for even k, but for odd k one needed n^{k/2} (log n)^{O(1)} / ε² random constraints to achieve the same conclusion. Although the improvement is only polylogarithmic, it overcomes a significant barrier to these types of results. Strong refutation results based on current approaches construct a certificate that a certain matrix associated to the k-CSP instance is quasirandom. Such certificate can come from a Feige-Ofek type argument, from an application of Grothendieck’s inequality, or from a spectral bound obtained with a trace argument. The first two approaches require a union bound that cannot work when the number of constraints is o(n^⌈k/2⌉) and the third one cannot work when the number of constraints is o(n^{k/2} √{log n}). We further apply our techniques to obtain a new PTAS finding assignments for k-CSP instances with n^{k/2} / ε² constraints in the semi-random settings where the constraints are random, but the sign patterns are adversarial.

We investigate opinion dynamics in a fully-connected system, consisting of n agents, where one of the opinions, called correct, represents a piece of information to disseminate. One source agent initially holds the correct opinion and remains with this opinion throughout the execution. The goal of the remaining agents is to quickly agree on this correct opinion. At each round, one agent chosen uniformly at random is activated: unless it is the source, the agent pulls the opinions of l random agents and then updates its opinion according to some rule. We consider a restricted setting, in which agents have no memory and they only revise their opinions on the basis of those of the agents they currently sample. This setting encompasses very popular opinion dynamics, such as the voter model and best-of-k majority rules. Qualitatively speaking, we show that lack of memory prevents efficient convergence. Specifically, we prove that any dynamics requires Omega(n^2) expected time, even under a strong version of the model in which activated agents have complete access to the current configuration of the entire system, i.e., the case l=n. Conversely, we prove that the simple voter model (in which l=1) correctly solves the problem, while almost matching the aforementioned lower bound. These results suggest that, in contrast to symmetric consensus problems (that do not involve a notion of correct opinion), fast convergence on the correct opinion using stochastic opinion dynamics may require the use of memory.

Correlation Clustering is an important clustering problem with many applications. We study the reconstruction version of this problem, in which one seeks to reconstruct a latent clustering that has been corrupted by random noise and adversarial modifications. Concerning the latter, there is a standard "post-adversarial" model in the literature, in which adversarial modifications come after the noise. Here, we introduce and analyse a "pre-adversarial" model, in which adversarial modifications come before the noise. Given an input coming from such a semi-adversarial generative model, the goal is to approximately reconstruct with high probability the latent clustering. We focus on the case where the hidden clusters have nearly equal size and show the following. In the pre-adversarial setting, spectral algorithms are optimal, in the sense that they reconstruct all the way to the information-theoretic threshold beyond which no reconstruction is possible. This is in contrast to the post-adversarial setting, in which their ability to restore the hidden clusters stops before the threshold, but the gap is optimally filled by SDP-based algorithms. These results highlight a heretofore unknown robustness of spectral algorithms, showing them less brittle than previously thought.

We prove that a random d-regular graph, with high probability, is a cut sparsifier of the clique with approximation error at most , where = 1.595 … and on,d(1) denotes an error term that depends on n and d and goes to zero if we first take the limit n → ∞ and then the limit d → ∞. This is established by analyzing linear-size cuts using techniques of Jagannath and Sen [13] derived from ideas in statistical physics, and analyzing small cuts via martingale inequalities. We also prove new lower bounds on spectral sparsification of the clique. If G is a spectral sparsifier of the clique and G has average degree d, we prove that the approximation error is at least the “Ramanujan bound” , which is met by d-regular Ramanujan graphs, provided that either the weighted adjacency matrix of G is a (multiple of) a doubly stochastic matrix, or that G satisfies a certain high “odd pseudo-girth” property. The first case can be seen as an “Alon-Boppana theorem for symmetric doubly stochastic matrices,” showing that a symmetric doubly stochastic matrix with dn non-zero entries has a non-trivial eigenvalue of magnitude at least ; the second case generalizes a lower bound of Srivastava and Trevisan [23], which requires a large girth assumption. Together, these results imply a separation between spectral sparsification and cut sparsification. If G is a random log n-regular graph on n vertices (this is to ensure that G, and consequently any d-regular subgraph, has high pseudogirth), we show that, with high probability, G admits a (weighted subgraph) cut sparsifier of average degree d and approximation error at most , while every (weighted subgraph) spectral sparsifier of G having average degree d has approximation error at least .

We study expansion and information diffusion properties of dynamic networks, i.e., networks whose topologies evolve over time as nodes enter or leave the system and edges are continuously created or destroyed. In this scenario, we investigate flooding as a basic information diffusion mechanism. We are interested in models that are likely to result in sparse networks, i.e., in networks containing$O(n)$edges, with$n$the number of nodes that are present at any given time of interest, with a focus on models in which edges are created randomly according to simple probabilistic mechanisms, rather than according to carefully designed distributed algorithms. In this perspective, in all models we consider, upon joining the network, a node connects to$d=O(1)$random nodes currently in the system. On the other hand, an edge remains alive as long as both its endpoints are. For the case in which edges that fail (because one endpoint left the network) are not replaced, we show that, although the network is likely to contain$\Omega_{d}(n)$isolated nodes, flooding still informs a fraction$1-\exp(-\Omega(d))$of the nodes in time$\mathrm{O}(\log n)$with large, constant probability. Moreover, we are able to show, that at any given time, the graph exhibits a “large-set expansion” property. We further investigate models that exhibit edge regeneration, meaning that, whenever an edge$(v, w)$established by$v$fails because$w$leaves the network, it is replaced by a new random edge$(v, z)$. We show that models with edge regeneration result in evolving networks that, at any given time, are vertex expanders with high probability, so that flooding takes$\mathrm{O}(\log n)$time. The above results hold both for a simplfied streaming model of node churn and in a more realistic, continuous-time setting, in which the interval between two consecutive node arrivals follows a Poisson distribution, while nodes' lifetimes follow an exponential distribution. Previous work considered models in which either the vertex set is fixed or edges are established according to more or less sophisticated algorithms. Our motivation for studying models with simple and random edge creation mechanisms is to move one step further towards models that may eventually capture key aspects of the formation of social or peer-to-peer networks.

For a graph $G$, let $f(G)$ denote the size of the maximum cut in $G$. The problem of estimating $f(G)$ as a function of the number of vertices and edges of $G$ has a long history and was extensively studied in the last fifty years. In this paper we propose an approach, based on semidefinite programming, to prove lower bounds on $f(G)$. We use this approach to find large cuts in graphs with few triangles and in $K_r$-free graphs.

We show that for every ε > 0, the degree-nεSherali-Adams linear program (with exp(Õ(nε)) variables and constraints) approximates the maximum cut problem within a factor of ([1/2]+ε'), for some ε'(ε)>0. Our result provides a surprising converse to known lower bounds against all linear programming relaxations of Max-Cut [1], [2], and hence resolves the extension complexity of approximate Max-Cut for approximation factors close to [1/2] (up to the function ε'(ε)). Previously, only semidefinite programs and spectral methods were known to yield approximation factors better than [1/2] for Max-Cut in time 2o(n). We also show that constant-degree Sherali-Adams linear programs (with poly(n) variables and constraints) can solve Max-Cut with approximation factor close to 1 on graphs of small threshold rank: this is the first connection of which we are aware between threshold rank and linear programming-based algorithms. Our results separate the power of Sherali-Adams versus Lovász-Schrijver hierarchies for approximating Max-Cut, since it is known [3] that ([1/2]+ε) approximation of Max Cut requires Ωε(n) rounds in the Lovász-Schrijver hierarchy. We also provide a subexponential time approximation for Khot's Unique Games problem [4]: we show that for every ε>0 the degree-(nεlog q) Sherali-Adams linear program distinguishes instances of Unique Games of value ≥ 1-ε'from instances of value ≤ ε', for some ε'(ε)>0, where q is the alphabet size. Such guarantees are qualitatively similar to those of previous subexponential-time algorithms for Unique Games but our algorithm does not rely on semidefinite programming or subspace enumeration techniques [5]-[6]-[7].

Consensus and Broadcast are two fundamental problems in distributed computing, whose solutions have several applications. Intuitively, Consensus should be no harder than Broadcast, and this can be rigorously established in several models. Can Consensus be easier than Broadcast? In models that allow noiseless communication, we prove a reduction of (a suitable variant of) Broadcast to binary Consensus, that preserves the communication model and all complexity parameters such as randomness, number of rounds, communication per round, etc., while there is a loss in the success probability of the protocol. Using this reduction, we get, among other applications, the first logarithmic lower bound on the number of rounds needed to achieve Consensus in the uniform GOSSIP model on the complete graph. The lower bound is tight and, in this model, Consensus and Broadcast are equivalent. We then turn to distributed models with noisy communication channels that have been studied in the context of some bio-inspired systems. In such models, only one noisy bit is exchanged when a communication channel is established between two nodes, and so one cannot easily simulate a noiseless protocol by using error-correcting codes. An Ω(ε^{-2} n) lower bound is proved by Boczkowski et al. [PLOS Comp. Bio. 2018] on the convergence time of binary Broadcast in one such model (noisy uniform PULL), where ε is a parameter that measures the amount of noise). We prove an O(ε^{-2} log n) upper bound on the convergence time of binary Consensus in such model, thus establishing an exponential complexity gap between Consensus versus Broadcast. We also prove our upper bound above is tight and this implies, for binary Consensus, a further strong complexity gap between noisy uniform PULL and noisy uniform PUSH. Finally, we show a Θ(ε^{-2} n log n) bound for Broadcast in the noisy uniform PULL.

It follows from the Marcus-Spielman-Srivastava proof of the Kadison-Singer conjecture that if G = (V, E) is a Δ-regular dense expander then there is an edge-induced subgraph H = (V, Eh) of G of constant maximum degree which is also an expander. As with other consequences of the MSS theorem, it is not clear how one would explicitly construct such a subgraph. We show that such a subgraph (although with quantitatively weaker expansion and near-regularity properties than those predicted by MSS) can be constructed with high probability in linear time, via a simple algorithm. Our algorithm allows a distributed implementation that runs in O(log n) rounds and does O(n) total work with high probability. The analysis of the algorithm is complicated by the complex dependencies that arise between edges and between choices made in different rounds. We sidestep these difficulties by following the combinatorial approach of counting the number of possible random choices of the algorithm which lead to failure. We do so by a compression argument showing that such random choices can be encoded with a non-trivial compression. Our algorithm bears some similarity to the way agents construct a communication graph in a peer-to-peer network, and, in the bipartite case, to the way agents select servers in blockchain protocols.

We study the independent set problem in a semi-random model proposed by Feige and Kilian. This model selects a graph with a planted independent set of size k and then allows an adversary to modify a large fraction of edges: the subgraph induced by the complement of the independent set can be modified arbitrarily, and the adversary may add (but not delete) edges from the independent set to its complement. In particular, the adversary can create a graph in which the initial planted independent set is not the largest independent set. Feige and Kilian presented a randomized algorithm, which with high probability recovers an independent set of size at least k (which may not be the planted one) when k = an where a is a constant, and the probability of a random edge p > (1 + ϵ) ln n/αn. We give a new deterministic algorithm in the Feige-Kilian model that finds an independent set of size at least .99k provided that the planted set has size k = Ω(n2/3/p1/3), and finds a list of independent sets, one of which is the planted one provided that k = Ω(n2/3/p). This improves on the algorithm of Feige and Kilian by working for smaller k if p = Ω(1/n1/3), and improves on an algorithm of Steinhardt by working for slightly smaller k and by working against a stronger adversarial model. The ability to find a good approximation of the largest independent set is new when p < ln n/k.

Given an underlying graph, we consider the following dynamics: Initially, each node locally chooses a value in $\{-1,1\}$, uniformly at random and independently of other nodes. Then, in each consecutive round, every node updates its local value to the average of the values held by its neighbors, at the same time applying an elementary, local clustering rule that only depends on the current and the previous values held by the node. We prove that the process resulting from this dynamics produces a clustering that exactly or approximately (depending on the graph) reflects the underlying cut in logarithmic time, under various graph models that exhibit a sparse balanced cut, including the stochastic block model. We also prove that a natural extension of this dynamics performs community detection on a regularized version of the stochastic block model with multiple communities. Rather surprisingly, our results provide rigorous evidence for the ability of an extremely simple and natural dynamics to perform community detection, a computational problem which is nontrivial even in a centralized setting.

We consider questions that arise from the intersection between the areas of polynomial-time approximation algorithms, subexponential-time algorithms, and fixed-parameter tractable (FPT) algorithms. The questions, which have been asked several times, are whether there is a nontrivial FPT-approximation algorithm for the Maximum Clique $({\sf Clique})$ and Minimum Dominating Set $({\sf DomSet})$ problems parameterized by the size of the optimal solution. In particular, letting ${\sf OPT}$ be the optimum and $N$ be the size of the input, is there an algorithm that runs in $t({\sf OPT}){\operatorname{poly}}(N)$ time and outputs a solution of size $f({\sf OPT})$ for any computable functions $t$ and $f$ that are independent of $N$ (for ${\sf Clique}$, we want $f({\sf OPT})=\omega(1)$)? In this paper, we show that both ${\sf Clique}$ and ${\sf DomSet}$ admit no nontrivial FPT-approximation algorithm, i.e., there is no $o({\sf OPT})$-FPT-approximation algorithm for ${\sf Clique}$ and no $f({\sf OPT})$-FPT-approximation algorithm for ${\sf DomSet}$ for any function $f$. In fact, our results imply something even stronger: The best way to solve ${\sf Clique}$ and ${\sf DomSet}$, even approximately, is to essentially enumerate all possibilities. Our results hold under the Gap Exponential Time Hypothesis [I. Dinur. ECCC, TR16-128, 2016; P. Manurangsi and P. Raghavendra, preprint, arXiv:1607.02986, 2016], which states that no $2^{o(n)}$-time algorithm can distinguish between a satisfiable 3 \sf SAT formula and one which is not even $(1 - \varepsilon)$-satisfiable for some constant $\varepsilon > 0$. Besides ${\sf Clique}$ and ${\sf DomSet}$, we also rule out nontrivial FPT-approximation for the Maximum Biclique problem, the problem of finding maximum subgraphs with hereditary properties (e.g., Maximum Induced Planar Subgraph), and Maximum Induced Matching in bipartite graphs, and we rule out the $k^{o(1)}$-FPT-approximation algorithm for the Densest $k$-Subgraph problem.

A sparsifier of a graph G (Benczúr and Karger; Spielman and Teng) is a sparse weighted subgraph G that approximately retains the same cut structure of G. For general graphs, non-trivial sparsification is possible only by using weighted graphs in which different edges have different weights. Even for graphs that admit unweighted sparsifiers (that is, sparsifiers in which all the edge weights are equal to the same scaling factor), there are no known polynomial time algorithms that find such unweighted sparsifiers. We study a weaker notion of sparsification suggested by Oveis Gharan, in which the number of cut edges in each cut (S, S) is not approximated within a multiplicative factor (1+ε), but is, instead, approximated up to an additive term bounded by ε times d·|S| + vol (S), where d is the average degree of the graph and vol (S) is the sum of the degrees of the vertices in S. We provide a probabilistic polynomial time construction of such sparsifiers for every graph, and our sparsifiers have a near-optimal number of edges O(ε-2npolylog (1/ε)). We also provide a deterministic polynomial time construction that constructs sparsifiers with a weaker property having the optimal number of edges O(ε-2n). Our constructions also satisfy a spectral version of the “additive sparsification'' property. Notions of sparsification have also been studied for hypergraphs. Our construction of “additive sparsifiers'' with Oε(n) edges also works for hypergraphs, and provides the first non-trivial notion of sparsification for hypergraphs achievable with O(n) hyperedges when ε and the rank r of the hyperedges are constant. Finally, we provide a new construction of spectral hypergraph sparsifiers, according to the standard definition, with poly (ε-1, r) · n log n hyperedges, improving over the previous spectral construction (Soma and Yoshida) that used Õ(n3) hyperedges even for constant r and ε.

We study the space complexity of sketching cuts and Laplacian quadratic forms of graphs. We show that any data structure which approximately stores the sizes of all cuts in an undirected graph on n vertices up to a 1 + ∊ error must use Ω(n log n/∊2) bits of space in the worst case, improving the Ω(n/∊2) bound of [ACK+16] and matching the best known upper bound achieved by spectral sparsifiers [BSS12]. Our proof is based on a rigidity phenomenon for cut (and spectral) approximation which may be of independent interest: any two d–regular graphs which approximate each other's cuts significantly better than a random graph approximates the complete graph must overlap in a constant fraction of their edges.

In this work, we study the trade-off between the running time of approximation algorithms and their approximation guarantees. By leveraging a structure of the `hard' instances of the Arora-Rao-Vazirani lemma [JACM'09], we show that the Sum-of-Squares hierarchy can be adapted to provide `fast', but still exponential time, approximation algorithms for several problems in the regime where they are believed to be NP-hard. Specifically, our framework yields the following algorithms; here $n$ denote the number of vertices of the graph and $r$ can be any positive real number greater than 1 (possibly depending on $n$). (i) A $\left(2 - \frac{1}{O(r)}\right)$-approximation algorithm for Vertex Cover that runs in $\exp\left(\frac{n}{2^{r^2}}\right)n^{O(1)}$ time. (ii) An $O(r)$-approximation algorithms for Uniform Sparsest Cut, Balanced Separator, Minimum UnCut and Minimum 2CNF Deletion that runs in $\exp\left(\frac{n}{2^{r^2}}\right)n^{O(1)}$ time. Our algorithm for Vertex Cover improves upon Bansal et al.'s algorithm [arXiv:1708.03515] which achieves $\left(2 - \frac{1}{O(r)}\right)$-approximation in time $\exp\left(\frac{n}{r^r}\right)n^{O(1)}$. For the remaining problems, our algorithms improve upon $O(r)$-approximation $\exp\left(\frac{n}{2^r}\right)n^{O(1)}$-time algorithms that follow from a work of Charikar et al. [SIAM J. Comput.'10].

Consider the following asynchronous, opportunistic communication model over a graph $G$: in each round, one edge is activated uniformly and independently at random and (only) its two endpoints can exchange messages and perform local computations. Under this model, we study the following random process: The first time a vertex is an endpoint of an active edge, it chooses a random number, say $\pm 1$ with probability $1/2$; then, in each round, the two endpoints of the currently active edge update their values to their average. We show that, if $G$ exhibits a two-community structure (for example, two expanders connected by a sparse cut), the values held by the nodes will collectively reflect the underlying community structure over a suitable phase of the above process, allowing efficient and effective recovery in important cases. In more detail, we first provide a first-moment analysis showing that, for a large class of almost-regular clustered graphs that includes the stochastic block model, the expected values held by all but a negligible fraction of the nodes eventually reflect the underlying cut signal. We prove this property emerges after a mixing period of length $\mathcal O(n\log n)$. We further provide a second-moment analysis for a more restricted class of regular clustered graphs that includes the regular stochastic block model. For this case, we are able to show that most nodes can efficiently and locally identify their community of reference over a suitable time window. This results in the first opportunistic protocols that approximately recover community structure using only polylogarithmic work per node. Even for the above class of regular graphs, our second moment analysis requires new concentration bounds on the product of certain random matrices that are technically challenging and possibly of independent interest.

We prove the following Alon-Boppana type theorem for general (not necessarily regular) weighted graphs: if G is an n-node weighted undirected graph of average combinatorial degree d (that is, G has dn/2 edges) and girth g > 2d1/8 + 1, and if λ1 ≤ λ2 ≤ · · · λn are the eigenvalues of the (non-normalized) Laplacian of G, then (The Alon-Boppana theorem implies that if G is unweighted and d-regular, then if the diameter is at least d1.5.) Our result implies a lower bound for spectral sparsifiers. A graph H is a spectral є-sparsifier of a graph G if where L(G) is the Laplacian matrix of G and L(H) is the Laplacian matrix of H. Batson, Spielman and Srivastava proved that for every G there is an є-sparsifier H of average degree d where and the edges of H are a (weighted) subset of the edges of G. Batson, Spielman and Srivastava also show that the bound on є cannot be reduced below when G is a clique; our Alon-Boppana-type result implies that є cannot be reduced below when G comes from a family of expanders of super-constant degree and superconstant girth. The method of Batson, Spielman and Srivastava proves a more general result, about sparsifying sums of rank-one matrices, and their method applies to an “online” setting. We show that for the online matrix setting the bound is tight, up to lower order terms.

We consider questions that arise from the intersection between the areas of approximation algorithms, subexponential-time algorithms, and fixed-parameter tractable algorithms. The questions, which have been asked several times (e.g., [1], [2], [3]) are whether there is a non-trivial FPT-approximation algorithm for the Maximum Clique (Clique) and Minimum Dominating Set (DomSet) problems parameterized by the size of the optimal solution. In particular, letting OPT be the optimum and N be the size of the input, is there an algorithm that runs in t(OPT) poly(N) time and outputs a solution of size f(OPT), for any functions t and f that are independent of N (for Clique, we want f(OPT) = ω(1))? In this paper, we show that both Clique and DomSet admit no non-trivial FPT-approximation algorithm, i.e., there is no o(OPT)-FPT-approximation algorithm for Clique and no f(OPT)-FPT-approximation algorithm for DomSet, for any function f (e.g., this holds even if f is an exponential or the Ackermann function). In fact, our results imply something even stronger: The best way to solve Clique and DomSet, even approximately, is to essentially enumerate all possibilities. Our results hold under the Gap Exponential Time Hypothesis (GapETH) [4], [5], which states that no 2o(n)-time algorithm can distinguish between a satisfiable 3SAT formula and one which is not even (1 - ε)-satisfiable for some constant ε > 0. Besides Clique and DomSet, we also rule out non-trivial FPT-approximation for Maximum Balanced Biclique, the problem of finding maximum subgraphs with hereditary properties (e.g., Maximum Induced Planar Subgraph), and Maximum Induced Matching in bipartite graphs. Previously only exact versions of these problems were known to be W[1]-hard [6], [7], [8]. Additionally, we rule out ko(1)-FPT-approximation algorithm for Densest k-Subgraph although this ratio does not yet match the trivial O(k)-approximation algorithm. To the best of our knowledge, prior results only rule out constant factor approximation for Clique [9], [10] and log1/4+ε(OPT) approximation for DomSet for any constant ε > 0 [11]. Our result on Clique significantly improves on [9], [10]. However, our result on DomSet is incomparable to [11] since their results hold under ETH while our results hold under Gap-ETH, which is a stronger assumption.

Given an underlying graph, we consider the following dynamics: Initially, each node locally chooses a value in {-1,1}, uniformly at random and independently of other nodes. Then, in each consecutive round, every node updates its local value to the average of the values held by its neighbors, at the same time applying an elementary, local clustering rule that only depends on the current and the previous values held by the node. We prove that the process resulting from this dynamics produces a clustering that exactly or approximately (depending on the graph) reflects the underlying cut in logarithmic time, under various graph models that exhibit a sparse balanced cut, including the stochastic block model. We also prove that a natural extension of this dynamics performs community detection on a regularized version of the stochastic block model with multiple communities. Rather surprisingly, our results provide rigorous evidence for the ability of an extremely simple and natural dynamics to address a computational problem that is non-trivial even in a centralized setting. Distributed Algorithms, Averaging Dynamics, Community Detection, Spectral Analysis, Stochastic Block Models.

In recent years, researchers proposed several algorithms that compute metric quantities of real-world complex networks, and that are very efficient in practice, although there is no worst-case guarantee. In this work, we propose an axiomatic framework to analyze the performances of these algorithms, by proving that they are efficient on the class of graphs satisfying certain properties. Furthermore, we prove that these properties are verified asymptotically almost surely by several probabilistic models that generate power law random graphs, such as the Configuration Model, the Chung-Lu model, and the Norros-Reittu model. Thus, our results imply average-case analyses in these models. For example, in our framework, existing algorithms can compute the diameter and the radius of a graph in subquadratic time, and sometimes even in time n1+o(1). Moreover, in some regimes, it is possible to compute the k most central vertices according to closeness centrality in subquadratic time, and to design a distance oracle with sublinear query time and subquadratic space occupancy. In the worst case, it is impossible to obtain comparable results for any of these problems, unless widely- believed conjectures are false.

In this paper, we prove an almost-optimal hardness for Max k-CSP_R based on Khot's Unique Games Conjecture (UGC). In Max k-CSP_R, we are given a set of predicates each of which depends on exactly k variables. Each variable can take any value from 1, 2, ..., R. The goal is to find an assignment to variables that maximizes the number of satisfied predicates. Assuming the Unique Games Conjecture, we show that it is NP-hard to approximate Max k-CSP_R to within factor 2^{O(k log k)}(log R)^{k/2}/R^{k - 1} for any k, R. To the best of our knowledge, this result improves on all the known hardness of approximation results when 3 <= k = o(log R/log log R). In this case, the previous best hardness result was NP-hardness of approximating within a factor O(k/R^{k-2}) by Chan. When k = 2, our result matches the best known UGC-hardness result of Khot, Kindler, Mossel and O'Donnell. In addition, by extending an algorithm for Max 2-CSP_R by Kindler, Kolla and Trevisan, we provide an Omega(log R/R^{k - 1})-approximation algorithm for Max k-CSP_R. This algorithm implies that our inapproximability result is tight up to a factor of 2^{O(k \log k)}(\log R)^{k/2 - 1}. In comparison, when 3 <= k is a constant, the previously known gap was $O(R)$, which is significantly larger than our gap of O(polylog R). Finally, we show that we can replace the Unique Games Conjecture assumption with Khot's d-to-1 Conjecture and still get asymptotically the same hardness of approximation.

We consider the following distributed consensus problem: Each node in a complete communication network of size n initially holds an opinion, which is chosen arbitrarily from a finite set Σ. The system must converge toward a consensus state in which all, or almost all nodes, hold the same opinion. Moreover, this opinion should be valid, i.e., it should be one among those initially present in the system. This condition should be met even in the presence of a malicious adversary who can modify the opinions of a bounded subset of nodes, adaptively chosen in every round. We consider the 3-majority dynamics: At every round, every node pulls the opinion from three random neighbors and sets his new opinion to the majority one (ties are broken arbitrarily). Let k be the number of valid opinions. We show that, if k ≤ nα, where α is a suitable positive constant, the 3-majority dynamics converges in time polynomial in k and log n with high probability even in the presence of an adversary who can affect up to nodes at each round. Previously, the convergence of the 3-majority protocol was known for |Σ| = 2 only, with an argument that is robust to adversarial errors. On the other hand, no anonymous, uniform-gossip protocol that is robust to adversarial errors was known for |Σ| > 2.

We develop a polynomial time Ω ( log R) approximate algorithm for Max 2CSP-R, the problem where we are given a collection of constraints, each involving two variables, where each variable ranges over a set of size R, and we want to find an assignment to the variables that maximizes the number of satisfied constraints. Assuming the Unique Games Conjecture, this is the best possible approximation up to constant factors. Previously, a 1/R-approximate algorithm was known, based on linear programming. Our algorithm is based on semidefinite programming. The Semidefinite Program that we use has an almost-matching integrality gap. For the more general Max kCSP-R, in which each constraint involves k variables, each ranging over a set of size R, it was known that the best possible approximation is of the order of k/Rk – 1, provided that k is sufficiently large compared to R; our algorithm shows that the bound k/Rk – 1 is not tight for k = 2.

Spectral partitioning is a simple, nearly linear time algorithm to find sparse cuts, and the Cheeger inequalities provide a worst-case guarantee for the quality of the approximation found by the algorithm. A local graph partitioning algorithm finds a set of vertices with small conductance (i.e., a sparse cut) by adaptively exploring part of a large graph G , starting from a specified vertex. For the algorithm to be local, its complexity must be bounded in terms of the size of the set that it outputs, with at most a weak dependence on the number n of vertices in G . Previous local partitioning algorithms find sparse cuts using random walks and personalized PageRank [Spielman and Teng 2013; Andersen et al. 2006]. In this article, we introduce a simple randomized local partitioning algorithm that finds a sparse cut by simulating the volume-biased evolving set process , which is a Markov chain on sets of vertices. We prove that for any ϵ > 0, and any set of vertices A that has conductance at most φ, for at least half of the starting vertices in A our algorithm will output (with constant probability) a set of conductance O (√φ /ϵ). We prove that for a given run of the algorithm, the expected ratio between its computational complexity and the volume of the set that it outputs is vol( A ) ϵ φ -1/2 polylog( n ), where vol( A ) = Σ v ∈ A d ( v ) is the volume of the set A . This gives an algorithm with the same guarantee (up to a constant factor) as the Cheeger's inequality that runs in time slightly superlinear in the size of the output. This is the first sublinear (in the size of the input) time algorithm with almost the same guarantee as the Cheeger's inequality. In comparison, the best previous local partitioning algorithm, by Andersen et al. [2006], has a worse approximation guarantee of O (√φ log n ) and a larger ratio of φ -1 polylog( n ) between the complexity and output volume. As a by-product of our results, we prove a bicriteria approximation algorithm for the expansion profile of any graph. For 0 < k ≤ vol( V )/2, let φ( k ) : min S : vol( S ) ≤ k φ( S ). There is a polynomial time algorithm that, for any k , ϵ > 0, finds a set S of volume vol( S ) ≤ O ( k 1 + ϵ ) and expansion φ( S )≤ O (√φ ( k )/ϵ). As a new technical tool, we show that for any set S of vertices of a graph, a lazy t -step random walk started from a randomly chosen vertex of S will remain entirely inside S with probability at least (1 - φ( S )/2) t . This itself provides a new lower bound to the uniform mixing time of any finite state reversible Markov chain.

We show that for any odd k and any instance I of the max-kXOR constraint satisfaction problem, there is an efficient algorithm that finds an assignment satisfying at least a 1/2 + Omega(1/sqrt(D)) fraction of I's constraints, where D is a bound on the number of constraints that each variable occurs in. This improves both qualitatively and quantitatively on the recent work of Farhi, Goldstone, and Gutmann (2014), which gave a quantum algorithm to find an assignment satisfying a 1/2 Omega(D^{-3/4}) fraction of the equations. For arbitrary constraint satisfaction problems, we give a similar result for "triangle-free" instances; i.e., an efficient algorithm that finds an assignment satisfying at least a mu + Omega(1/sqrt(degree)) fraction of constraints, where mu is the fraction that would be satisfied by a uniformly random assignment.

Let G = (V, E) be an undirected graph, λk be the kth smallest eigenvalue of the normalized laplacian matrix of G. There is a basic fact in algebraic graph theory that λk > 0 if and only if G has at most k – 1 connected components. We prove a robust version of this fact. If λk > 0, then for some 1 ≤ ℓ ≤ k – 1, V can be partitioned into ℓ sets P1, …, Pℓ such that each Pi is a low-conductance set in G and induces a high conductance induced subgraph. In particular, and G[Pi] ≳ λk/k2-expander. We make our results algorithmic by designing a simple polynomial time spectral algorithm to find such partitioning of G with a quadratic loss in the inside conductance of Pi's. Unlike the recent results on higher order Cheeger's inequality [6, 9], our results does not use higher order eigenfunctions of G. If there is a sufficiently large gap between λk and λk+1, more precisely if then our algorithm finds a k partitioning of V into sets P1, …, Pk such that the induced subgraph G[Pi] has a singnificantly larger conductance than the conductance of Pi in G. Such a partitioning may represent the best k clusterings of G. Our algorithm is a simple local search that only uses the Spectral Partitioning algorithm as a subroutine. We expect to see further applications of this simple algorithm in clustering applications. Let ρ(k) = mindisjoint max1≤i≤k φ(Ai) be the order k conductance constant of G, in words, ρ(k) is the smallest value of the maximum conductance of any k disjoint subsets of V. Our main technical lemma shows that if (1 + ∊)ρ(k) < ρ(k+1), then V can be partitioned into k sets P1, …, Pk such that for each 1 ≤ i ≤ k, φ(G[Pi]) ≳ ∊ · ρ(k + 1)/k and φ(Pi) ≤ k · ρ(k). This significantly improves a recent result of Tanaka [13] who assumed an exponential (in k) gap between ρ(k) and ρ(k + 1).

We study a Plurality Consensus process in which each of n anonymous agents of a communication network supports an initial opinion (a colorchosen from a finite set [k]) and, at every time step, he can revise his color according to a random sample of neighbors.

A basic fact in spectral graph theory is that the number of connected components in an undirected graph is equal to the multiplicity of the eigenvalue zero in the Laplacian matrix of the graph. In particular, the graph is disconnected if and only if there are at least two eigenvalues equal to zero. Cheeger's inequality and its variants provide an approximate version of the latter fact; they state that a graph has a sparse cut if and only if there are at least two eigenvalues that are close to zero. It has been conjectured that an analogous characterization holds for higher multiplicities: There are k eigenvalues close to zero if and only if the vertex set can be partitioned into k subsets, each defining a sparse cut. We resolve this conjecture positively. Our result provides a theoretical justification for clustering algorithms that use the bottom k eigenvectors to embed the vertices into R k , and then apply geometric considerations to the embedding. We also show that these techniques yield a nearly optimal quantitative connection between the expansion of sets of size ≈ n / k and λ k , the k th smallest eigenvalue of the normalized Laplacian, where n is the number of vertices. In particular, we show that in every graph there are at least k /2 disjoint sets (one of which will have size at most 2 n / k ), each having expansion at most O (√λ k log k ). Louis, Raghavendra, Tetali, and Vempala have independently proved a slightly weaker version of this last result. The √log k bound is tight, up to constant factors, for the “noisy hypercube” graphs.

This special section contains five selected papers from the 50th Annual Symposium on Foundations of Computer Science (FOCS 2010) sponsored by the IEEE Technical Committee on Mathematical Foundations of Computing. The conference was held in Las Vegas, Nevada, October 23-26, 2010. The conference program consisted of 81 papers, which the program committee selected from 270 submissions. The program committee was composed of Scott Aaronson, Dorit Aharonov, Eli Ben-Sasson, Julia Chuzhoy, Ryan O'Donnell, Roberto Grossi, Nick Harvey, Adam Kalai, Nicole Immorlica, Yuval Ishai, Lap Chi Lau, James Lee, Tal Malkin, Joe Mitchell, Dana Moshkovitz, S. Muthukrishnan, Christos Papadimitriou, Sofya Raskhodnikova, Steve Skiena, Mikkel Thorup, Luca Trevisan, and Eric Vigoda. Each of the five papers appearing in this issue was subject to the standard refereeing process of the SIAM Journal on Computing. In “The Monotone Complexity of $k$-Clique on Random Graphs," Ben Rossman proves that monotone circuits that solve the $k$-clique problem in random graphs must have size $\omega(n^{k/4})$, establishing the first average-case monotone lower bound. Andreas Björklund, in the paper “Determinant Sums for Undirected Hamiltonicity," develops the first improvement to the $\tilde O(2^n)$ dynamic programming algorithm for Hamiltonian circuit: Björklund's algorithm runs in time $\tilde O(1.657^n)$. The paper “Distance Oracles Beyond the Thorup--Zwick Bound" by Mihai Pătraşcu and Liam Roditty presents the first improvement in ten years for the problem of compactly representing an approximation to all-pairs shortest path distances in a graph. Shaddin Dughmi and Tim Roughgarden show how to convert any approximation algorithm for a certain class of problems into a truthful mechanism in the paper “Black-Box Randomized Reductions in Algorithmic Mechanism Design." Ioannis Koutis, Gary Miller, and Richard Peng, in the paper “Approaching Optimality for Solving SDD Linear Systems," present a new nearly linear time algorithm for the problem of solving systems of linear equations that are symmetric and diagonally dominant. We wish to thank Madhu Sudan and Leonard Schulman, the former and current Editors-in-Chief of SICOMP, for being very generous with their time as they helped us in this project. We also wish to thank Heather Blythe of SIAM and the anonymous referees.

We describe a new pseudorandom generator for AC0. Our generator $\epsilon$-fools circuits of depth $d$ and size $M$ and uses a seed of length $\tilde O( \log^{d+4} M/\epsilon)$. The previous best construction for $d \geq 3$ was due to Nisan, and had seed length $O(\log^{2d+6} M/\epsilon)$. A seed length of $O(\log^{2d + \Omega(1)} M)$ is best possible given Nisan-type generators and the current state of circuit lower bounds. Seed length $\Omega(\log^d M/\epsilon)$ is a barrier for any pseudorandom generator construction given the current state of circuit lower bounds. For $d=2$, a pseudorandom generator of seed length $\tilde O(\log^2 M/\epsilon)$ was known. Our generator is based on a ``pseudorandom restriction'' generator which outputs restrictions that satisfy the conclusions of the H\aa stad Switching Lemma and that uses a seed of polylogarithmic length.

Let φ(G) be the minimum conductance of an undirected graph G, and let 0=λ1 ≤ λ2 ≤ ... ≤ λn ≤ 2 be the eigenvalues of the normalized Laplacian matrix of G. We prove that for any graph G and any k ≥ 2, [φ(G) = O(k) l2/√lk,] and this performance guarantee is achieved by the spectral partitioning algorithm. This improves Cheeger's inequality, and the bound is optimal up to a constant factor for any $k$. Our result shows that the spectral partitioning algorithm is a constant factor approximation algorithm for finding a sparse cut if lk is a constant for some constant k. This provides some theoretical justification to its empirical performance in image segmentation and clustering problems. We extend the analysis to spectral algorithms for other graph partitioning problems, including multi-way partition, balanced separator, and maximum cut.

Spectral partitioning is a simple, nearly-linear time, algorithm to find sparse cuts, and the Cheeger inequalities provide a worst-case guarantee of the quality of the approximation found by the algorithm. Local graph partitioning algorithms [1], [2], [3] run in time that is nearly linear in the size of the output set, and their approximation guarantee is worse than the guarantee provided by the Cheeger inequalities by a poly-logarithmic logΩ(1)n factor. It has been an open problem to design a local graph clustering algorithm with an approximation guarantee close to the guarantee of the Cheeger inequalities and with a running time nearly linear in the size of the output. In this paper we solve this problem; we design an algorithm with the same guarantee (up to a constant factor) as the Cheeger inequality, that runs in time slightly super linear in the size of the output. This is the first sublinear (in the size of the input) time algorithm with almost the same guarantee as the Cheeger's inequality. As a byproduct of our results, we prove a bicriteria approximation algorithm for the expansion profile of any graph. Let μ(S) = Σv∈Sd(v) be the volume, and φ(S) := |E(S, S̅)|/μ(S), be the conductance of a set S of vertices. If there is a set of volume at most γ and conductance φ, we can find a set of volume at most γ1+ϵand conductance V at most O(√φ/ϵ), for any ϵ >; 0. Our proof techniques also provide a simpler proof of the structural result of Arora, Barak, Steurer [4], that can be applied to irregular graphs. Our main technical tool is a lemma stating that, for any set S of vertices of a graph, a lazy t-step random walk started from a randomly chosen vertex of S, will remain entirely inside S with probability at least (1-φ(S)/2)t. The lemma also implies a new lower bound to the uniform mixing time of any finite states reversible markov chain.

We present an iterative approach to constructing pseudorandom generators, based on the repeated application of mild pseudorandom restrictions. We use this template to construct pseudorandom generators for combinatorial rectangles and read-once CNFs and a hitting set generator for width-3 branching programs, all of which achieve near-optimal seed-length even in the low-error regime: We get seed-length Õ(log (n/ε)) for error ε. Previously, only constructions with seed-length O(log3/2n) or O(log2n) were known for these classes with error ε = 1/poly(n). The (pseudo)random restrictions we use are milder than those typically used for proving circuit lower bounds in that we only set a constant fraction of the bits at a time. While such restrictions do not simplify the functions drastically, we show that they can be derandomized using small-bias spaces.

We present a general approach to study the flooding time (a measure of how fast information spreads) in dynamic graphs (graphs whose topology changes with time according to a random process). We consider arbitrary ergodic Markovian dynamic graph process, that is, processes in which the topology of the graph at time t depends only on its topology at time t-1 and which have a unique stationary distribution. The most well studied models of dynamic graphs are all Markovian and ergodic.

A basic fact in spectral graph theory is that the number of connected components in an undirected graph is equal to the multiplicity of the eigenvalue zero in the Laplacian matrix of the graph. In particular, the graph is disconnected if and only if there are at least two eigenvalues equal to zero. Cheeger's inequality and its variants provide an approximate version of the latter fact; they state that a graph has a sparse cut if and only if there are at least two eigenvalues that are close to zero.

We describe a new approximation algorithm for Max Cut. Our algorithm runs in $\tilde O(n^2)$ time, where $n$ is the number of vertices, and achieves an approximation ratio of $.531$. In instances in which an optimal solution cuts a $1-\varepsilon$ fraction of edges, our algorithm finds a solution that cuts a $1-4\sqrt{\varepsilon} + 8\varepsilon-o(1)$ fraction of edges. Our main result is a variant of spectral partitioning, which can be implemented in nearly linear time. Given a graph in which the Max Cut optimum is a $1-\varepsilon$ fraction of edges, our spectral partitioning algorithm finds a set $S$ of vertices and a bipartition $L,R=S-L$ of $S$ such that at least a $1-O(\sqrt \varepsilon)$ fraction of the edges incident on $S$ have one endpoint in $L$ and one endpoint in $R$. (This can be seen as an analogue of Cheeger's inequality for the smallest eigenvalue of the adjacency matrix of a graph.) Iterating this procedure yields the approximation results stated above. A different, more complicated, variant of spectral partitioning leads to a polynomial time algorithm that cuts a $1/2 + e^{-\Omega(1/\varepsilon)}$ fraction of edges in graphs in which the optimum is $1/2 + \varepsilon$.

Three fundamental results of Levin involve algorithms or reductions whose running time is exponential in the length of certain programs. We study the question of whether such dependency can be made polynomial. 1) Levin's "optimal search algorithm" performs at most a constant factor more slowly than any other fixed algorithm. The constant, however, is exponential in the length of the competing algorithm. We note that the running time of a universal search cannot be made "fully polynomial" (that is, the relation between slowdown and program length cannot be made polynomial), unless P=NP. 2) Levin's "universal one-way function" result has the following structure: there is a polynomial time computable function fLevinsuch that if there is a polynomial time computable adversary A that inverts fLevinon an inverse polynomial fraction of inputs, then for every polynomial time computable function g there also is a polynomial time adversary Agthat inverts g on an inverse polynomial fraction of inputs. Unfortunately, again the running time of Agdepends exponentially on the bit length of the program that computes g in polynomial time. We show that a fully polynomial uniform reduction from an arbitrary one-way function to a specific one-way function is not possible relative to an oracle that we construct, and so no "universal one-way function" can have a fully polynomial security analysis via relativizing techniques. 3) Levin's completeness result for distributional NP problems implies that if a specific problem in NP is easy on average under the uniform distribution, then every language L in NP is also easy on average under any polynomial time computable distribution. The running time of the implied algorithm for L, however, depends exponentially on the bit length of the non-deterministic polynomial time Turing machine that decides L. We show that if a completeness result for distributional NP can be proved via a "fully uniform" and "fully polynomial" time reduction, then there is a worst-case to average-case reduction for NP-complete problems. In particular, this means that a fully polynomial completeness result for distributional NP is impossible, even via randomized truth-table reductions, unless the polynomial hierarchy collapses.

We show that every bounded function g: {0,1}nrarr [0,1] admits an efficiently computable "simulator" function h: {0,1}nrarr [0,1] such that every fixed polynomial size circuit has approximately the same correlation with g as with h. If g describes (up to scaling) a high min-entropy distribution D, then h can be used to efficiently sample a distribution D' of the same min-entropy that is indistinguishable from D by circuits of fixed polynomial size. We state and prove our result in a more abstract setting, in which we allow arbitrary finite domains instead of {0,1}n, and arbitrary families of distinguishers, instead of fixed polynomial size circuits. Our result implies (a) the weak Szemeredi regularity Lemma of Frieze and Kannan (b) a constructive version of the dense model theorem of Green, Tao and Ziegler with better quantitative parameters (polynomial rather than exponential in the distinguishing probability), and (c) the Impagliazzo hardcore set Lemma. It appears to be the general result underlying the known connections between "regularity" results in graph theory, "decomposition" results in additive combinatorics, and the hardcore Lemma in complexity theory. We present two proofs of our result, one in the spirit of Nisan's proof of the hardcore Lemma via duality of linear programming, and one similar to Impagliazzo's "boosting" proof. A third proof by iterative partitioning, which gives the complexity of the sampler to be exponential in the distinguishing probability, is also implicit in the Green-Tao-Ziegler proofs of the dense model theorem.

We describe a new approximation algorithm for Max Cut. Our algorithm runs in ~O(n2) time, where n is the number of vertices, and achieves an approximation ratio of .531. On instances in which an optimal solution cuts a 1-ε fraction of edges, our algorithm finds a solution that cuts a 1-4√ε + 8ε-o(1) fraction of edges. Our main result is a variant of spectral partitioning, which can be implemented in nearly linear time. Given a graph in which the Max Cut optimum is a 1-ε fraction of edges, our spectral partitioning algorithm finds a set S of vertices and a bipartition L,R=S-L of S such that at least a 1-O(√ε) fraction of the edges incident on S have one endpoint in L and one endpoint in R. (This can be seen as an analog of Cheeger's inequality for the smallest eigenvalue of the adjacency matrix of a graph.) Iterating this procedure yields the approximation results stated above. A different, more complicated, variant of spectral partitioning leads to a polynomial time algorithm that cuts a 1/2 + e-Ω(1/ε) fraction of edges in graphs in which the optimum is 1/2 + ε.

We study the relation of query complexity and soundness in probabilistically checkable proofs (PCPs). We present a PCP verifier for languages that are Unique-Games-Hard and such that the verifier makes q queries, has almost perfect completeness, and has soundness error at most $2q/2^q+\varepsilon$ for arbitrarily small $\varepsilon>0$. For values of q of the form $2^t-1$, the soundness error is $(q+1)/2^q+\varepsilon$. Charikar, Makarychev, and Makarychev show that there is a constant $\beta$ such that every language that has a verifier of query complexity q and a ratio of soundness error to completeness smaller than $\beta q/2^q$ is decidable in polynomial time. Up to the value of the multiplicative constant and to the validity of the Unique Games Conjecture, our result is therefore tight. As a corollary, we show that approximating the Maximum Independent Set problem in graphs of degree $\Delta$ within a factor better than $\Delta/(\log\Delta)^\alpha$ is Unique-Games-Hard for a certain constant $\alpha>0$. Our main technical results are (i) a connection between the Gowers uniformity of a boolean function and the influence of its variables and (ii) the proof that “Gowers uniform” functions pass the “hypergraph linearity test” approximately with the same probability of a random function. The connection between Gowers uniformity and influence might have other applications.

A theorem of Green, Tao, and Ziegler can be stated (roughly) as follows: ifR is a pseudorandom set, and D is a dense subset of R, then D may be modeled by a set M that is dense in the entire domain such that D and M are indistinguishable. (The precise statement refers to"measures" or distributions rather than sets.) The proof of this theorem is very general, and it applies to notions of pseudo-randomness and indistinguishability defined in terms of any family of distinguishers with some mild closure properties. The proof proceeds via iterative partitioning and an energy increment argument, in the spirit of the proof of the weak Szemeredi regularity lemma. The "reduction" involved in the proof has exponential complexity in the distinguishing probability. We present a new proof inspired by Nisan's proof of Impagliazzo's hardcore set theorem. The reduction in our proof has polynomial complexity in the distinguishing probability and provides a new characterization of the notion of "pseudoentropy" of a distribution. A proof similar to ours has also been independently discovered by Gowers [2]. We also follow the connection between the two theorems and obtain a new proof of Impagliazzo's hardcore set theorem via iterative partitioning and energy increment. While our reduction has exponential complexity in some parameters, it has the advantage that the hardcore set is efficiently recognizable.

We review the many open questions and the few things that are known about the average-case complexity of computational problems. We shall follow the presentations of Impagliazzo, of Goldreich, and of Bogdanov and the author, and focus on the following subjects. (i). Average-case tractability. What does it mean for a problem to have an "efficient on average'' algorithm with respect to a distribution of instances? There is more than one ``correct'' answer to this question, and a numberof subtleties arise, which are interesting to discuss. (ii) Worst case versus average-case. Is the existence of hard-on-averageproblems in a complexity class equivalent to the existence of worst-case-hardproblems? This is the case for complexity classes like PSPACE and EXP, but it is openfor NP, with partial evidence pointing to a negative answer. (To be sure, we believethat hard-on-average, and also worst-case hard problems, exist in NP, and if so theirexistence is ``equivalent'' in the way two true statements are logically equivalent. There is, however, partial evidence that such an equivalence cannot be establishedvia reductions. It is also known that such an equivalence cannot be established viaany relativizing technique.) (iii) Amplification of average-case hardness. A weak sense in which aproblem may be hard-on-average is that every efficient algorithm fails on a noticeable(at least inverse polynomial) fraction of inputs; a strong sense is that noalgorithm can do much better than guess the answer at random. In many settings,the existence of problems of weak average-case complexity implies the existenceof problems, in the same complexity class, of strong average-case complexity.It remains open to prove such equivalence in the setting of uniform algorithmsfor problems in NP. (Some partial results are known even in this setting.) (iv) Reductions and Completeness. Levin initiated a theoryof completeness for distributional problems under reductions that preserveaverage-case tractability. Even establishing the existence of an NP-completeproblem in this theory is a non-trivial (and interesting) result.

We study semidefinite programming relaxations of Vertex Cover arising from repeated applications of the LS+ "lift-and-project" method of Lovasz and Schrijver starting from the standard linear programming relaxation. Goemans and Kleinberg prove that after one round of LS+ the integrality gap remains arbitrarily close to 2. Charikar proves an integrality gap of 2, later strengthened by Hatami, Magen, and Markakis, for stronger relaxations that are, however, incomparable with two rounds of LS+. Subsequent work by Georgiou, Magen, Pitassi, and Tourlakis shows that the integrality gap remains 2 -epsiv after Omega (radiclog n-log log n ) rounds [?]. We prove that the integrality gap remains at least 7/6 - epsiv after cepsivn rounds, where n is the number of vertices and cepsiv> 0 is a constant that depends only on epsiv.

We study linear programming relaxations of Vertex Cover and Max Cutarising from repeated applications of the "lift-and-project" method of Lovasz and Schrijver starting from the standard linear programming relaxation.

Impagliazzo and Wigderson (1998) gave the first construction of pseudorandom generators from a uniform complexity assumption on EXP (namely EXP ≠ BPP). Unlike results in the nonuniform setting, their result does not provide a continuous trade-off between worst-case hardness and pseudorandomness, nor does it explicitly establish an average-case hardness result. In this paper: We obtain an optimal worst-case to average-case connection for EXP: if EXP $$\nsubseteq$$ BPTIME(t(n)), then EXP has problems that cannot be solved on a fraction $$1/2 + 1/t^{\prime}(n)$$ of the inputs by BPTIME $$(t^{\prime}(n))$$ algorithms, for $$t^{\prime}= t^{\Omega(1)}$$ . We exhibit a PSPACE-complete self-correctible and downward self-reducible problem. This slightly simplifies and strengthens the proof of Impagliazzo and Wigderson, which used a #P-complete problem with these properties. We argue that the results of Impagliazzo and Wigderson, and the ones in this paper, cannot be proved via “black-box” uniform reductions.

We revisit the general RL vs. L question, obtaining the following results.

We return to the study of the relation of query complexity and soundness in probabilistically checkable proofs.We present a PCP verifier for languages that are Unique-Games-Hard and such that the verifier makes q queries, has almost perfect completeness, and has soundness error at most 2q/2q+ε, for arbitrarily small ε>0. For values of q of the form 2t-1, the soundness error is (q+1)/2q+ε.Charikar et al. show that there is a constant c such that for every language that has a verifier of query complexity q, and a ratio of soundness error to completeness smaller than cq/2q is decidable in polynomial time. Up to the value of the multiplicative constant and to the validity of the Unique Games Conjecture, our result is therefore tight.As a corollary, we show that approximating the Maximum Independent Set problem in graphs of degree Δ within a factor better than Δ/(log Δ)c is Unique-Games-Hard for a certain constant c>0.Our main technical results are (i) a connection between the Gowers uniformity of a Boolean function and the influence of its variables and (ii) the proof that "Gowers uniform" functions pass the "hypergraph linearity test" approximately with the same probability of a random function. The connection between Gowers uniformity and influence might have other applications.

We prove that if a linear error-correcting code C:{0, 1} n →{0, 1} m is such that a bit of the message can be probabilistically reconstructed by looking at two entries of a corrupted codeword, then m = 2Ω (n). We also present several extensions of this result. We show a reduction from the complexity of one-round, information-theoretic Private Information Retrieval Systems (with two servers) to Locally Decodable Codes, and conclude that if all the servers’ answers are linear combinations of the database content, then t = Ω (n/2 a ), where t is the length of the user’s query and a is the length of the servers’ answers. Actually, 2 a can be replaced by O(a k ), where k is the number of bit locations in the answer that are actually inspected in the reconstruction.

We present a polynomial time algorithm based on semidefinite programming that, given a unique game of value 1 - O(1/logn), satisfies a constant fraction of constraints, where n is the number of variables. For sufficiently large alphabets, it improves an algorithm of Khot (STOC'02) that satisfies a constant fraction of constraints in unique games of value 1 -O(1/(k/sup 10/(log k)/sup 5/)), where k is the size of the alphabet. We also present a simpler algorithm for the special case of unique games with linear constraints. Finally, we present a simple approximation algorithm for 2-to-1 games.

We show that for any constant a, ZPP/b(n) strictly contains ZPTIME(na)/b(n) for some b(n) = O(log n log log n). Our techniques are very general and give the same hierarchy for all common semantic time classes including RTIME, NTIME ∩ coNTIME, UTIME, MATIME, AMTIME and BQTIME.We show a stronger hierarchy for RTIME: For every constant c, RP/1 is not contained in RTIME(nc)/(log n)1/2c. To prove this result we first prove a similar statement for NP by building on Zák's proof of the nondeterministic time hierarchy.

We continue the study of amplification of average-case complexity within NP, and we focus on the uniform case.We prove that if every problem in NP admits an efficient uniform algorithm that (averaged over random inputs and over the internal coin tosses of the algorithm) succeeds with probability at least 1 ⁄ 2 +1 (log n )α, then for every problem in NP there is an efficient uniform algorithm that succeeds with probability at least 1 - 1 poly(n). Above, α > 0 is an absolute constant.Previously, Trevisan (FOCS'03) presented a similar redution between success 3⁄4 + 1 (log n) and 1 - 1 (log n)α Stronger reductions, due to O'Donnell (STOC'02) and Healy, Vadhan and Viola (FOCS'04) are known in the non-uniform case.

We study the compression of polynomially samplable sources. In particular, we give efficient prefix-free compression and decompression algorithms for three classes of such sources (whose support is a subset of {0, 1} n ). 1. We show how to compress sources X samplable by logspace machines to expected length H(X) + O(1). Our next results concern flat sources whose support is in P. 2. If H(X) ≤ k = n − O(log n), we show how to compress to expected length k + polylog(n − k). 3. If the support of X is the witness set for a self-reducible NP relation, then we show how to compress to expected length H(X) + 5.

We study the approximability of the version of MAXSAT where exponentially large instances are succinctly represented using circuits. First, we prove that the NP-hardness for approximating MAXSAT can be lifted to a corresponding NEXP-hardness for approximating circuit-succinct MAXSAT for some constant performance ratio. Second, we consider the approximability of circuit-succinct MAXSAT with respect to lower complexity classes: in particular, we prove that computing (2 − ϵ)-approximate solutions for circuit-succinct MAXSAT is at least as hard as inverting one-way permutations. On the other hand, a simple randomized approximation algorithm computes a (2 + ϵ)-approximate solution with high probability. Recall that the standard (not succinctly represented) version of the MAXSAT problem is approximable to within a 0.78 factor and that the MAX3SAT problem is approximable to within a 7/8 factor.

We present a probabilistic algorithm that, given a connected graph G (represented by adjacency lists) of average degree d, with edge weights in the set{1,...,w}, and given a parameter $0 < \eps < 1/2$, estimates in time $O( dw \varepsilon^{-2} \log{\frac{dw}\varepsilon})$ the weight of the minimum spanning tree (MST) of G with a relative error of at most $\eps$. Note that the running time does not depend on the number of vertices in G. We also prove a nearly matching lower bound of $\Omega( dw \varepsilon^{-2} )$ on the probe and time complexity of any approximation algorithm for MST weight. The essential component of our algorithm is a procedure for estimating in time $O(d\eps^{-2}\log \frac{d}\varepsilon)$ the number of connected components of an unweighted graph to within an additive error of $\varepsilon n$. (This becomes $O(\eps^{-2}\log \frac{1}\varepsilon)$ for $d=O(1)$.) The time bound is shown to be tight up to within the $\log \frac{d}\varepsilon$ factor. Our connected-components algorithm picks $O(1/\varepsilon^2)$ vertices in the graph and then grows "local spanning trees" whose sizes are specified by a stochastic process. From the local information collected in this way, the algorithm is able to infer, with high confidence, an estimate of the number of connected components. We then show how estimates on the number of components in various subgraphs of G can be used to estimate the weight of its MST.

A central focus of modern cryptography is the construction of efficient, high-level cryptographic tools (e.g., encryption schemes) from weaker, low-level cryptographic primitives (e.g., one-way functions). Of interest are both the existence of such constructions and their efficiency. Here, we show essentially tight lower bounds on the best possible efficiency of any black-box construction of some fundamental cryptographic tools from the most basic and widely used cryptographic primitives. Our results hold in an extension of the model introduced by Impagliazzo and Rudich and improve and extend earlier results of Kim, Simon, and Tetali. We focus on constructions of pseudorandom generators, universal one-way hash functions, and digital signatures based on one-way permutations, as well as constructions of public- and private-key encryption schemes based on trapdoor permutations. In each case, we show that any black-box construction beating our efficiency bound would yield the unconditional existence of a one-way function and thus, in particular, prove $P \neq NP$.

We consider the problem of testing bipartiteness in the adjacency matrix model. The best known algorithm, due to Alon and Krivelevich, distinguishes between bipartite graphs and graphs that are /spl epsi/-far from bipartite using 0(1//spl epsi//sup 2/) queries. We show that this is optimal for non-adaptive algorithms, up to polylogarithmic factors. We also show a lower bound of /spl Omega/(1//spl epsi//sup 3/2/) for adaptive algorithms.

We study the compression of polynomially samplable sources. In particular, we give efficient prefix-free compression and decompression algorithms for three classes of such sources (whose support is a subset of {0, l}/sup n/). 1) We show how to compress sources X samplable by logspace machines to expected length H(X) + O(1). Our next results concern flat sources whose support is in P. 2) If H(X) /spl les/ k = n - O(log n), we show how to compress to length k + /spl delta//spl middot/ (n - k) for any constant /spl delta/ > 0; in quasi-polynomial time we show how to compress to length k + O(polylog log (n - k)) even if k = n -polylog(n). 3) If the support of X is the witness set for a self-reducible NP relation, then we show how to compress to expected length H(X) + 4.

We prove an extremal combinatorial result regarding the fraction of satisfiable clauses in Boolean conjunctive normal form (CNF) formulae enjoying a locally checkable property, thus solving a problem that has been open for several years. We then generalize the problem to arbitrary constraint satisfaction problems. We prove a tight result even in the generalized case.

We show that if an NP-complete problem has a non-adaptive self-corrector with respect to a distribution that can be sampled then coNP is contained in AM/poly and the polynomial hierarchy collapses to the third level. Feigenbaum and Fortnow show the same conclusion under the stronger assumption that an NP-complete problem has a non-adaptive random self-reduction. Our result shows it is impossible (using non-adaptive reductions) to base the average-case hardness of a problem in NP or the security of a one-way function on the worst-case complexity of an NP-complete problem (unless the polynomial hierarchy collapses).

M. Cryan and P.B. Miltersen (2001) recently considered the question of whether there can be a pseudorandom generator in NC/sup 0/, that is, a pseudorandom generator that maps n bits strings to m bits strings and such that every bit of the output depends on a constant number k of bits of the seed. They show that for k = 3, if m /spl ges/ 4n + 1, there is a distinguisher; in fact, they show that in this case it is possible to break the generator with a linear test, that is, there is a subset of bits of the output whose XOR has a noticeable bias. They leave the question open for k /spl ges/ 4. In fact they ask whether every NC/sup 0/ generator can be broken by a statistical test that simply XORs some bits of the input. Equivalently, is it the case that no NC/sup 0/ generator can sample an /spl epsiv/-biased space with negligible /spl epsiv/? We give a generator for k = 5 that maps n bits into cn bits, so that every bit of the output depends on 5 bits of the seed, and the XOR of every subset of the bits of the output has bias 2/sup -/spl Omega/(n/c4)/. For large values of k, we construct generators that map n bits to n/sup /spl Omega/(/spl radic/k)/ bits and such that every XOR of outputs has bias 2/sup -n1/(2/spl radic/k)/. We also present a polynomial-time distinguisher for k = 4, m /spl ges/ 24n having constant distinguishing probability. For large values of k we show that a linear distinguisher with a constant distinguishing probability exists once m /spl ges/ /spl Omega/(2/sup k/n/sup [k/2]/). Finally, we consider a variant of the problem where each of the output bits is a degree k polynomial in the inputs. We show there exists a degree k = 2 pseudorandom generator for which the XOR of every subset of the outputs has bias 2/sup -/spl Omega/(n)/ and which map n bits to /spl Omega/(n/sup 2/) bits.

We show that Yao's XOR Lemma, and its essentially equivalent rephrasing as a Direct Product Lemma, can be re-interpreted as a way of obtaining error-correcting codes with good list-decoding algorithms from error-correcting codes having weak unique-decoding algorithms. To get codes with good rate and efficient list decoding algorithms, one needs a proof of the Direct Product Lemma that, respectively, is strongly derandomized, and uses very small advice. We show how to reduce advice in Impagliazzo's proof of the Direct Product Lemma for pairwise independent inputs, which leads to error-correcting codes with O(n/sup 2/) encoding length, 0/sup /spl tilde//(n/sup 2/) encoding time, and probabilistic 0/sup /spl tilde//(n) list-decoding time. (Note that the decoding time is sub-linear in the length of the encoding.) Back to complexity theory, our advice-efficient proof of Impagliazzo's hard-core set results yields a (weak) uniform version of O'Donnell results on amplification of hardness in NP. We show that if there is a problem in NP that cannot be solved by BPP algorithms on more than a 1 - 1/(log n)/sup c/ fraction of inputs, then there is a problem in NP that cannot be solved by BPP algorithms on more than a 3/4 + 1/(log n)/sup c/ fraction of inputs, where c > 0 is an absolute constant.

We prove (mostly tight) space lower bounds for "streaming" (or "on-line") computations of four fundamental combinatorial objects: error-correcting codes, universal hash functions, extractors, and dispersers. Streaming computations for these objects are motivated algorithmically by massive data set applications and complexity-theoretically by pseudorandomness and derandomization for space-bounded probabilistic algorithms. Our results reveal a surprising separation of extractors and dispersers in terms of the space required to compute them in the streaming model. While online extractors require space linear in their output length, we construct dispersers that are computable online with exponentially less space. We also present several explicit constructions of online extractors that match the lower bound. We show that online universal and almost-universal hash functions require space linear in their output length (this bound was known previously only for "pure" universal hash functions). Finally, we show that both online encoding and online decoding of error-correcting codes require space proportional to the product of the length of the encoded message and the code's relative minimum distance. Block encoding trivially matches the lower bounds for constant rate codes.

Impagliazzo and Wigderson (1998) gave the first construction of pseudorandom generators from a uniform complexity assumption on EXP (namely EXP = BPP). Unlike results in the nonuniform setting, their result does not provide a continuous trade-off between worst-case hardness and pseudorandomness, nor does it explicitly establish an average-case hardness result. We obtain an optimal worst-case to average-case connection for EXP: if EXP BPTIME(( )), EXP has problems that are cannot be solved on a fraction 1/2 1/'( ) of the inputs by BPTIME('( )) algorithms, for ' = /sup 1/. We exhibit a PSPACE-complete downward self-reducible and random self-reducible problem. This slightly simplifies and strengthens the proof of Impagliazzo and Wigderson (1998), which used a a P-complete problem with these properties. We argue that the results in Impagliazzo and Wigderson (1998) and in this paper cannot be proved via "black-box" uniform reductions.

We consider the problem of testing 3-colorability in the bounded-degree model. We show that, for small enough /spl epsiv/, every tester for 3-colorability must have query complexity /spl Omega/(n). This is the first linear lower bound for testing a natural graph property in the bounded-degree model. An /spl Omega/(/spl radic/n) lower bound was previously known. For one-sided error testers, we also show an /spl Omega/(n) lower bound for testers that distinguish 3-colorable graphs from graphs that are (1/3 - /spl alpha/)-far from 3-colorable, for arbitrarily small /spl alpha/. In contrast, a polynomial time algorithm by Frieze and Jerrum (1997) distinguishes 3-colorable graphs from graphs that are 1/5-far from 3-colorable. As a by-product of our techniques, we obtain tight unconditional lower bounds on the approximation ratios achievable by sublinear time algorithms for Max E3SAT, Max E3LIN-2 and other problems.

Property testing is a relaxation of decision problems in which it is required to distinguish YES-instances (i.e., objects having a predetermined property) from instances that are far from any YES-instance. We present three theorems regarding testing graph properties in the adjacency matrix representation. More specifically, these theorems relate to the project of characterizing graph properties according to the complexity of testing them (in the adjacency matrix representation). The first theorem is that there exist monotone graph properties in /spl Nscr//spl Pscr/ for which testing is very hard (i.e., requires one to examine a constant fraction of the entries in the matrix). The second theorem is that every graph property that can be tested making a number of queries that is independent of the size of the graph, can be so tested by uniformly selecting a set of vertices and accepting iff the induced subgraph has some fixed graph property (which is not necessarily the same as the one being tested). The third theorem refers to the framework of graph partition problems, and is a characterization of the subclass of properties that can be tested using a one-sided error tester, making a number of queries that is independent of the size of the graph.

par>We prove some non-approximability results for restrictions of basic combinatorial optimization problems to instances of bounded “degree&r dquo;or bounded “width.” Specifically:

We introduce a new approach to constructing extractors. Extractors are algorithms that transform a “weakly random” distribution into an almost uniform distribution. Explicit constructions of extractors have a variety of important applications, and tend to be very difficult to obtain.We demonstrate an unsuspected connection between extractors and pseudorandom generators. In fact, we show that every pseudorandom generator of a certain kind is an extractor.A pseudorandom generator construction due to Impagliazzo and Wigderson, once reinterpreted via our connection, is already an extractor that beats most known constructions and solves an important open question. We also show that, using the simpler Nisan--Wigderson generator and standard error-correcting codes, one can build even better extractors with the additional advantage that both the construction and the analysis are simple and admit a short self-contained description.

Probabilistically checkable proofs (PCPs) define a model of computation that is quite interesting in its own right, and that is an extremely powerful tool to study the complexity of finding approximate solutions for combinatorial optimization. Since U. Feige et al. (1996) suggested a connection between proof-checking and approximation, this connection has been generalized and exploited to an amazing extent. In this paper we focus on efficient PCP constructions in five settings, for three of which essentially tight results are known, with useful applications, and for two of which tight results are still exciting open questions.

We present lower bounds on the efficiency of constructions for Pseudo-Random Generators (PRGs) and Universal One-Way Hash Functions (UOWHFs) based on black-box access to one-way permutations. Our lower bounds are tight as they match the efficiency of known constructions. A PRG (resp. UOWHF) construction based on black-box access is a machine that is given oracle access to a permutation. Whenever the permutation is hard to invert, the construction is hard to break. In this paper we give lower bounds on the number of invocations to the oracle by the construction. If S is the assumed security of the oracle permutation /spl pi/ (i.e. no adversary of size S can invert /spl pi/ on a fraction larger than 1/S of its inputs) then a PRG (resp. UOWHF) construction that stretches (resp. compresses) its input by k bits must query /spl pi/ in q=/spl Omega/(k/log S) points. This matches known constructions. Our results are given in an extension of the Impagliazzo-Rudich model. That is, we prove that a proof of the existence of PRG (resp. UOWHF) black-box constructions that beat our lower bound would imply a proof of the unconditional existence of such construction (which would also imply P/spl ne/NP).

The standard notion of a randomness extractor is a procedure which converts any weak source of randomness into an almost uniform distribution. The conversion necessarily uses a small amount of pure randomness, which can be eliminated by complete enumeration in some, but not all, applications. We consider the problem of deterministically converting a weak source of randomness into an almost uniform distribution. Previously, deterministic extraction procedures were known only for sources satisfying strong independence requirements. We look at sources which are samplable, i.e. can be generated by an efficient sampling algorithm. We seek an efficient deterministic procedure that, given a sample from any samplable distribution of sufficiently large min-entropy, gives an almost uniformly distributed output. We explore the conditions under which such deterministic extractors exist. We observe that no deterministic extractor exists if the sampler is allowed to use more computational resources than the extractor. On the other hand, if the extractor is allowed (polynomially) more resources than the sampler, we show that deterministic extraction becomes possible. This is true unconditionally in the nonuniform setting (i.e., when the extractor can be computed by a small circuit), and (necessarily) relies on complexity assumptions in the uniform setting.

We consider error-correcting codes where a bit of the message can be probabilistically recovered by looking at a limited number of bits (or blocks of bits) of a (possibly) corrupted encoding.Such codes can be derived from multivariate polynomial encodings, and have several applications in complexity theory, such as worst-case to average-case reductions, probabilistically checkable proofs, and private information retrieval.Such codes could have practical applications if they had at the same time constant information rate, the ability to correct a linear number of errors, and very efficient (ideally, constant-time) reconstruction procedures.In particular they would give fault-tolerant data storage with unlimited scalability.We show a negative result on the existence of such codes; namely, that linear encoding length is incompatible with a decoding procedure making a constant number of queries (which is necessary if one is to have constant reconstruction time).In particular, if a bit of a message of length n can be retrieved by looking at q blocks of length l, and the reconstruction procedure is robust to a fraction 5 of errors, then the encoding is made of m = f/(poly(1/q, 6, e)(n/l) q/(q-t))blocks of length I.This is the first lower bound for this class of codes.Our bound is far from the known (exponential) upper bound when q is a constant.Closing this gap remains a challenge.

Article A PCP characterization of NP with optimal amortized query complexity Share on Authors: Alex Samorodnitsky Institute for Advanced Study and DIMACS Institute for Advanced Study and DIMACSView Profile , Luca Trevisan Columbia University and DIMACS Columbia University and DIMACSView Profile Authors Info & Claims STOC '00: Proceedings of the thirty-second annual ACM symposium on Theory of computingMay 2000 Pages 191–199https://doi.org/10.1145/335305.335329Online:01 May 2000Publication History 101citation487DownloadsMetricsTotal Citations101Total Downloads487Last 12 Months17Last 6 weeks1 Get Citation AlertsNew Citation Alert added!This alert has been successfully added and will be sent to:You will be notified whenever a record that you have chosen has been cited.To manage your alert preferences, click on the button below.Manage my AlertsNew Citation Alert!Please log in to your account Save to BinderSave to BinderCreate a New BinderNameCancelCreateExport CitationPublisher SiteGet Access

The notion of efficient proof-checking has always been central to complexity theory, and it gave rise to the definition of the class NP. In the last 15 years there has been a number of exciting, unexpected and deep developments in complexity theory that exploited the notion of randomized and interactive proof-checking. Results developed along this line of research have diverse and powerful applications in complexity theory, cryptography, and the theory of approximation algorithms for combinatorial optimization problems. In this paper we survey the main lines of developments in interactive and probabilistic proof-checking, with an emphasis on open questions.

We study optimization problems that may be expressed as "Boolean constraint satisfaction problems." An instance of a Boolean constraint satisfaction problem is given by m constraints applied to n Boolean variables. Different computational problems arise from constraint satisfaction problems depending on the nature of the "underlying" constraints as well as on the goal of the optimization task. Here we consider four possible goals: Max CSP (Min CSP) is the class of problems where the goal is to find an assignment maximizing the number of satisfied constraints (minimizing the number of unsatisfied constraints). Max Ones (Min Ones) is the class of optimization problems where the goal is to find an assignment satisfying all constraints with maximum (minimum) number of variables set to 1. Each class consists of infinitely many problems and a problem within a class is specified by a finite collection of finite Boolean functions that describe the possible constraints that may be used. Tight bounds on the approximability of every problem in Max CSP were obtained by Creignou [ J. Comput. System Sci., 51 (1995), pp. 511--522]. In this work we determine tight bounds on the "approximability" (i.e., the ratio to within which each problem may be approximated in polynomial time) of every problem in Max Ones, Min CSP, and Min Ones. Combined with the result of Creignou, this completely classifies all optimization problems derived from Boolean constraint satisfaction. Our results capture a diverse collection of optimization problems such as MAX 3-SAT, Max Cut, Max Clique, Min Cut, Nearest Codeword, etc. Our results unify recent results on the (in-)approximability of these optimization problems and yield a compact presentation of most known results. Moreover, these results provide a formal basis to many statements on the behavior of natural optimization problems that have so far been observed only empirically.

We prove that the traveling salesman problem ({\sc Min TSP}) is {\sf Max SNP}-hard (and thus {\sf NP}-hard to approximate within some constant r>1) even if all cities lie in a Euclidean space of dimension $\log n$ (n is the number of cities) and distances are computed with respect to any l p norm. The running time of recent approximation schemes for geometric {\sc Min TSP} is doubly exponential in the number of dimensions. Our result implies that this dependence is necessary unless NP has subexponential algorithms. As an intermediate step, we also prove the hardness of approximating {\sc Min TSP} in Hamming spaces. Finally, we prove a similar, but weaker, inapproximability result for the Steiner minimal tree problem ({\sc Min ST}). The reduction for {\sc Min TSP} uses error-correcting codes; the reduction for {\sc Min ST} uses the integrality property of {\sc Min-Cut} linear programming relaxations. The only previous inapproximability results for metric {\sc Min TSP} involved metrics where all distances are 1 or 2.

We present a linear programming-based method for finding "gadgets," i.e., combinatorial structures reducing constraints of one optimization problem to constraints of another. A key step in this method is a simple observation which limits the search space to a finite one. Using this new method we present a number of new, computer-constructed gadgets for several different reductions. This method also answers a question posed by Bellare, Goldreich, and Sudan [SIAM J. Comput., 27 (1998), pp. 804--915] of how to prove the optimality of gadgets: linear programming duality gives such proofs. The new gadgets, when combined with recent results of Håstad [ Proceedings of the 29th ACM Symposium on Theory of Computing, 1997, pp. 1--10], improve the known inapproximability results for MAX CUT and MAX DICUT, showing that approximating these problems to within factors of $16/17 + ε$ and $12/13+ ε,$ respectively, is NP-hard for every ε > 0. Prior to this work, the best-known inapproximability thresholds for both problems were 71/72 (M. Bellare, O. Goldreich, and M. Sudan [ SIAM J. Comput., 27 (1998), pp. 804--915]). Without using the gadgets from this paper, the best possible hardness that would follow from Bellare, Goldreich, and Sudan and Håstad is 18/19. We also use the gadgets to obtain an improved approximation algorithm for MAX3 SAT which guarantees an approximation ratio of .801. This improves upon the previous best bound (implicit from M. X. Goemans and D. P. Williamson [J. ACM, 42 (1995), pp. 1115--1145]; U. Feige and M. X. Goemans [Proceedings of the Third Israel Symposium on Theory of Computing and Systems, 1995, pp. 182--189]) of .7704.

Summary form only given. R. Impagliazzo and A. Wigderson (1997) have recently shown that if there exists a decision problem solvable in time 2/sup O(n)/ and having circuit complexity 2/sup /spl Omega/(n)/ (for all but finitely many n) then P=BPP. This result is a culmination of a series of works showing connections between the existence of hard predicates and the existence of good pseudorandom generators. The construction of Impagliazzo and Wigderson goes through three phases of "hardness amplification" (a multivariate polynomial encoding, a first derandomized XOR Lemma, and a second derandomized XOR Lemma) that are composed with the Nisan-Wigderson (1994) generator. In this paper we present two different approaches to proving the main result of Impagliazzo and Wigderson. In developing each approach, we introduce new techniques and prove new results that could be useful in future improvements and/or applications of hardness-randomness trade-offs.

] Madhu Sudan y Luca Trevisan z Salil Vadhan x Abstract Impagliazzo and Wigderson [IW97] have recently shown that if there exists a decision problem solvable in time 2 O(n) and having circuit complexity 2 \\Omega\\Gamma n) (for all but finitely many n) then P = BPP. This result is a culmination of a series of works showing connections between the existence of hard predicates and the existence of good pseudorandom generators. The construction of Impagliazzo and Wigderson goes through three phases of "hardness amplification" (a multivariate polynomial encoding, a first derandomized XOR Lemma, and a second derandomized XOR Lemma) that are composed with the Nisan-- Wigderson [NW94] generator. In this paper we present two different approaches to proving the main result of Impagliazzo and Wigderson. In developing each approach, we introduce new techniques and prove new results that could be useful in future improvements and/or applications of hardness-randomness trade-offs. Our firs...

We introduce a new approach to construct extractors.Extractors are algorithms that transform a "weakly random" distribution into au almost uniform distribution.Explicit constructions of extractors have a variety of important applications, and tend to be very difficult to achieve.We demonstrate an unsuspected connection between extractors and pseudorandom generators.In fact, we show that every pseudorandom generator of a certain kind is an extractor.A pseudprandom generator construction due to Impagliazzo and Wigderson, once reinterpreted via our connection, is already an extractor that beats most known constructions and solves an important open question.We also show that, using the simpler Nisan-Wigderson generator and standard error-correcting codes, one can build even better extractors with the additional advantage that both the construction and the analysis are extremely simple and admit a short self-contained treatment.

We show how to simulate any BPP algorithm in polynomial time by using a weak random source of r bits and min-entropy $r^{\gamma}$ for any $\gamma >0$. This follows from a more general result about sampling with weak random sources. Our result matches an information-theoretic lower bound and solves a question that has been open for some years. The previous best results were a polynomial time simulation of RP [M. Saks, A. Srinivasan, and S. Zhou, Proc. 27th ACM Symp. on Theory of Computing, 1995, pp. 479--488] and a quasi-polynomial time simulation of BPP [A. Ta-Shma, Proc. 28th ACM Symp. on Theory of Computing, 1996, pp. 276--285]. Departing significantly from previous related works, we do not use extractors; instead, we use the OR-disperser of Saks, Srinivasan, and Zhou in combination with a tricky use of hitting sets borrowed from [Andreev, Clementi, and Rolim, J. ACM, 45 (1998), pp. 179--213].

The study of the approximability properties of NP-hard optimization problems has recently made great advances mainly due to the results obtained in the field of proof checking. The last important breakthrough proves the APX-completeness of several important optimization problems and thus reconciles "two distinct views of approximation classes: syntactic and computational" [S. Khanna et al., in Proc. 35th IEEE Symp. on Foundations of Computer Science, IEEE Computer Society Press, Los Alamitos, CA, 1994, pp. 819--830]. In this paper we obtain new results on the structure of several computationally-defined approximation classes. In particular, after defining a new approximation preserving reducibility to be used for asmany approximation classes as possible, we give the first examples of natural NPO-complete problems and the first examples of natural APX-intermediate problems. Moreover, we state new connections between the approximability properties and the query complexity of NPO problems.

It is known that there exists a PCP characterization of NP where the verifier makes 3 queries and has a one-sided error that is bounded away from 1; and also that 2 queries do not suffice for such a characterization. Thus PCPs with 3 queries possess non-trivial verification power and motivate the task of determining the lowest error that can be achieved with a 3-query PCP. Recently, Hastad (1997) has shown a tight characterization of NP by constructing a 3-query PCP verifier with "error" arbitrarily close to 1/2. Unfortunately this verifier makes two-sided error and Hastad makes essential use of this feature. One-sided error, on the other hand, is a natural notion to associate with a proof system, since it has the desirable property that every rejected proof has a short counterexample. The question of determining the smallest error for which there exists a 3-query PCP verifier making one-sided error and accepting an NP-complete language, however, remained open. We resolve this question by showing that NP has a 3-query PCP with a one-sided error that is arbitrarily close to 1/2. This characterization is tight, i.e., the error cannot be lower. This result is in seeming contradiction with the results of Trevisan (1997) and Zwick (1998) who show that in order to recognize an NP-complete language, the error probability of a PCP verifier making 3 non-adaptive queries and having one-sided error must be at least 5/8. We get around this bottleneck by designing an adaptive 3-query PCP for NP. Our result yields the first tight analysis of an adaptive PCP; and reveals a previously unsuspected separation between the powers of adaptive and non-adaptive PCPs. Our design and analysis of adaptive PCPs can be extended to higher number of queries as well and we give an example of such a proof system with 5 queries. Our adaptive verifiers yield proof systems whose error probabilities match those of previous constructions, while also achieving one-sidedness in the error. This raises new questions about the power of adaptive PCPs, which deserve further study.

The error probability of Probabilistically Checkable Proof (PCP) systems can be made exponentially small in the number of queries by using sequential repetition. In this paper we are interested in determining the precise rate at which the error goes down in an optimal protocol, and we make substantial progress toward a tight resolution of this question. A PCP verifier uses q~ amortized query bits if, for some t, it makes q~t queries and has error probability at most 2/sup -t/. A PCP characterization of NP using 2.5 amortized query bits is known, and, unless P=NP, no such characterization is possible using 1 amortized query bits. We present a PCP characterization of NP that uses roughly 1.5 amortized query bits. Our result has two main implications. Separating PCP from 2-Provers 1-Round: In the 2-Provers 1-Round (2P1R) model the verifier has access to two oracles (or provers) and can make one query to each oracle. Each answer is a string of l bits (l is called the answer size). A 2P1R protocol with answer size l can be simulated by a PCP that reads 21 bits; we show that the converse does not hold for l/spl ges/7, unless P=NP. No such separation was known before. The Max kCSP problem: The Boolean constraint satisfaction problem with constraints involving at most k variables, usually called Max kCSP, is known to be hard to approximate within a factor 2/sup -4k/, and a 2.2/sup -k/-approximation algorithm is also known. We prove that Max kCSP is NP-hard to approximate within a factor of roughly 2/sup -2k/3/.

WC study query-efficient Probabilistically Checkable Proofs (PCPs) and linearity tests.We focus on the number of amor- rlzed query bits, A testing algorithm uses g amortized query bita if, for some constant k, it reads qh bits and has error probability at most 2 'I;, The best known PCP construction for NP in this respect uses 3 amortized query bits [13]; at least one amortized query bit is necessary, unless P = NP [S], This parameter is a fairly natural one and has applications to proving non-approximability results for constraint satisfaction problems, Furthermore, a PCP characterization of NP with less than 2 amortized query bits implies a separation of the PCP model from the 2-Prover l-Round model.Our approach is to take an atomic verification procedure and then iterate it several times, saving queries by recycling them between different iterations of the atomic test.We first apply this ideain order to develop query-efficient llnearlty tests, Linearity testing is a problem closely related to testing the Long Code and making PCP constructions.It in also a significant combinatorial problem still lacking tight characterizations, except for the case of three queries [4].The best known linearity test uses 3 amortized query bits 141; a different one achieves 1 amortized free bit (a different parameter related to the Max Clique problem) but uses an unbounded number of amortized query bits [5].We develop a general analysis technique and a linearity test achieving simultaneously amortized query complexity 1.5 and amortized free bit complexity .6.This test answers an open question raised by Bellare, Goldreich and Sudan.We then show how to adapt a weaker result to the PCP setting, and we obtain a PCP for NP that makes 5 queries 'MIT Luborutory for

This paper continues the work initiated by N. Creignou (1995) and S. Khanna et al. (1997) who classify maximization problems derived from Boolean constraint satisfaction. We study the approximability of minimization problems derived thence. A problem in this framework is characterized by a collection F of "constraints" (i.e., functions f: {0,1}/sup k//spl rarr/{0,1}) and an instance of a problem is constraints drawn from F applied to specified subsets of n Boolean variables. We study the two minimization analogs of classes studied by S. Khanna et al.: in one variant, namely MIN CSP (F), the objective is to find an assignment to minimize the number of unsatisfied constraints, while in the other namely MIN ONES (F), the goal is to find a satisfying assignment with minimum number of ones. These two classes together capture an entire spectrum of important minimization problems including s-t Min Cut, vertex cover hitting set with bounded size sets, integer programs with two variables per inequality graph bipartization, clause deletion in CNF formulae, and nearest codeword. Our main result is that there exists a finite partition of the space of all constraint sets such that for any given F, the approximability of MIN CSP (F) and MIN ONES (F) is completely determined by the partition containing it. Moreover we present a compact set of rules that determines which partition contains a given family F. Our classification identifies the central elements governing the approximability of problems in these classes, by unifying a large collection algorithmic and hardness of approximation results.

We show how to simulate any BPP algorithm in polynomial time using a weak random source of min-entropy r/sup /spl gamma// for any /spl gamma/>0. This follows from a more general result about sampling with weak random sources. Our result matches an information-theoretic lower bound and solves a question that has been open for some years. The previous best results were a polynomial time simulation of RP (Saks et al., 1995) and a n(log/sup (k)/n)-time simulation of BPP for fixed k (Ta-Shma, 1996). Departing significantly from previous related works, we do not use extractors; instead we use the OR-disperser of (Saks et al., 1995) in combination with a tricky use of hitting sets borrowed from Andreev et al. (1996). Of independent interest is our new (simplified) proof of the main result of Andreev et al., (1996). Our proof also gives some new hardness/randomness trade-offs for parallel classes.

Article When Hamming meets Euclid: the approximability of geometric TSP and MST (extended abstract) Share on Author: Luca Trevisan Dept. of Computer Science, University of Geneva, Rue General-Dufour 24, CH 1211 Geneva, Switzerland Dept. of Computer Science, University of Geneva, Rue General-Dufour 24, CH 1211 Geneva, SwitzerlandView Profile Authors Info & Claims STOC '97: Proceedings of the twenty-ninth annual ACM symposium on Theory of computingMay 1997 Pages 21–29https://doi.org/10.1145/258533.258541Published:04 May 1997 22citation506DownloadsMetricsTotal Citations22Total Downloads506Last 12 Months10Last 6 weeks2 Get Citation AlertsNew Citation Alert added!This alert has been successfully added and will be sent to:You will be notified whenever a record that you have chosen has been cited.To manage your alert preferences, click on the button below.Manage my AlertsNew Citation Alert!Please log in to your account Save to BinderSave to BinderCreate a New BinderNameCancelCreateExport CitationPublisher SiteGet Access

The authors present a linear-programming based method for finding "gadgets", i.e., combinatorial structures reducing constraints of one optimization problem to constraints of another. A key step in this method is a simple observation which limits the search space to a finite one. Using this new method they present a number of new, computer-constructed gadgets for several different reductions. This method also answers the question of how to prove the optimality of gadgets-they show how LP duality gives such proofs. The new gadgets improve hardness results for MAX CUT and MAX DICUT, showing that approximating these problems to within factors of 60/61 and 44/45 respectively is NP-hard (improving upon the previous hardness of 71/72 for both problems). They also use the gadgets to obtain an improved approximation algorithm for MAX 3SAT which guarantees an approximation ratio of 0.801, This improves upon the previous best bound of 0.7704.

The study of the approximability properties of NP-hard optimization problems has recently made great advances mainly due to the results obtained in the field of proof checking. The last important breakthrough proves the APX-completeness of several important optimization problems and thus reconciles "two distinct views of approximation classes: syntactic and computational" [S. Khanna et al., in Proc. 35th IEEE Symp. on Foundations of Computer Science, IEEE Computer Society Press, Los Alamitos, CA, 1994, pp. 819--830]. In this paper we obtain new results on the structure of several computationally-defined approximation classes. In particular, after defining a new approximation preserving reducibility to be used for asmany approximation classes as possible, we give the first examples of natural NPO-complete problems and the first examples of natural APX-intermediate problems. Moreover, we state new connections between the approximability properties and the query complexity of NPO problems.