List of Accepted Papers with Abstracts

Please find below a list of papers accepted to STOC09, including their authors and abstracts. This list is preliminary and subject to change. (The abstracts contain embedded latex, some of which has been converted to html by rather flaky software—apologies for any errors.)

If you would like your abstract omitted or would like to submit a revision (preferably in html), please send email to stoc2009-local@cs.umd.edu.

• Small-size ε-Nets for Axis-Parallel Rectangles and Boxes
  Boris Aronov, Esther Ezra and Micha Sharir
  

  We show the existence of ε-nets of size O((1/ε) log log (1/ε)) for planar point sets and axis-parallel rectangular ranges. The same bound holds for points in the plane with "fat" triangular ranges, and for point sets in 3-space and axis-parallel boxes; these are the first known non-trivial bounds for these range spaces. Our technique also yields improved bounds on the size of ε-nets in the more general context considered by Clarkson and Varadarajan. For example, we show the existence of ε-nets of size O((1/ε) log log log (1/ε)) for the "dual" range space of "fat" regions and planar point sets. Plugging our bounds into the technique of Brönnimann and Goodrich, we obtain improved approximation factors (computable in randomized polynomial time) for the hitting set or the set cover problems associated with the corresponding (primal or dual) range spaces.

• Non-monotone Submodular Maximization under Matroid and Knapsack Constraints
  Jon Lee, Vahab S. Mirrokni, Viswanath Nagarajan and Maxim Sviridenko
  

  Submodular function maximization is a central problem in combinatorial optimization, generalizing many important problems including Max Cut in directed/undirected graphs and in hypergraphs, certain constraint satisfaction problems, maximum entropy sampling, and maximum facility location problems. Unlike submodular minimization, submodular maximization is NP-hard. In this paper, we give the first constant-factor approximation algorithms for maximizing any non-negative submodular function subject to multiple matroid or nknapsack constraints. We emphasize that our results are for non-monotone submodular functions. In particular, for any constant k, we present a ({1\over k+2+{1\over k}+ε})-approximation for submodular maximization under k matroid constraints, and a ({1\over 5}-ε)-approximation algorithm for this problem subject to k knapsack constraints (ε>0 is any constant). We improve the approximation guarantee of our algorithm to {1\over k+1+{1\over k-1}+ε} for k≥ 2 partition matroid constraints. This idea also gives a ({1\over k+ε})-approximation for maximizing a monotone submodular function subject to k≥ 2 partition matroids, which improves over the previously best known guarantee of 1/(k+1).

• Private Coresets
  Dan Feldman, Amos Fiat, Haim Kaplan and Kobbi Nissim
  

  We forge a link between coresets, that have found use in a vast host of geometric settings, and differentially private databases that can answer any number of queries without compromising privacy — queries of the same class well approximated by the coreset. Such queries imply efficient privacy preserving optimization algorithms for a wide range of optimization problems but are also of independent interest. We give (computationally inefficient) transformations from any coreset for queries with low generalized sensitivity to differentially private databases for the same queries. This greatly extends the work of Blum, Ligett, and Roth [BLR08], and McSherry and Talwar [MT07].

  We define the notion of private coresets, which are simultaneously both coresets and differentially private. We produce computationally efficient private coresets for k-median and k-mean in R^d, i.e., efficient differentially private databases for such queries. Private coresets also imply efficient coalition proof mechanisms and error resilient data structures.

  Unlike coresets which only have a multiplicative approximation factor, we prove that private coresets must have a (small) additive error.

• Green's Conjecture and Testing Linear-Invariant Properties
  Asaf Shapira
  

  Given a set of linear equations Mx=b, we say that a set of integers S is (M,b)-free if it contains no solution to this system of equations. Motivated by questions related to testing linear-invariant properties of Boolean functions, as well as recent investigations in additive number theory, the following conjecture was raised (implicitly) by Green and by Bhattacharyya, Chen, Sudan and Xie: we say that a set of integers S ⊆ [n], is ε-far from being (M,b)-free if one needs to remove at least ε n elements from S in order to make it (M,b)-free. The conjecture was that for any system of homogeneous linear equations Mx=0 and for any ε > 0 there is a constant time randomized algorithm that can distinguish (with high probability) between sets of integers that are (M,0)-free from sets that are ε-far from being (M,0)-free. Or in other words, that for any M there is an efficient testing algorithm for the property of being (M,0)-free. In this paper we confirm the above conjecture by showing that such a testing algorithm exists even for non-homogeneous linear equations. An interesting aspect of our analysis is that as opposed to most results on testing Boolean functions, which rely on algebraic and analytic arguments, our proof relies on results from extremal hypergraph theory, such as the recent removal lemmas of Gowers, Rödl et al. and Austin and Tao.

• Distributed (Δ+1)-coloring in linear (in Δ) time
  Leonid Barenboim and Michael Elkin
  

  The distributed (Δ + 1)-coloring problem is one of most fundamental and well-studied problems of Distributed Algorithms. Starting with the work of Cole and Vishkin in 86, there was a long line of gradually improving algorithms published. The current state-of-the-art running time is O(Δ ⋅ log Δ + log* n), due to Kuhn and Wattenhofer, PODC'06. Linial (FOCS'87) has proved a lower bound of (1/2) ⋅ log* n for the problem, and Szegedy and Vishwanathan (STOC'93) provided a heuristic argument that shows that algorithms from a wide family of local iterative algorithms are unlikely to achieve running time smaller than Θ(Δ ⋅ log Δ).

  We present a deterministic (Δ + 1)-coloring distributed algorithm with running time O(Δ) + (1/2) ⋅ log* n. We also present a tradeoff between the running time and the number of colors, and devise an O(Δ^{1+ ε})-coloring algorithm with running time O(Δ^{1 - ε} + log* n), for any constant ε, 0 < ε < 1/4. Our algorithm breaks the heuristic barrier of Szegedy and Vishwanathan, and achieves running time which is linear in the maximum degree Δ. On the other hand, the conjecture of Szegedy and Vishwanathan may still be true, as our algorithm is not from the family of local iterative algorithms.

  On the way to this result we introduce a generalization of the notion of graph coloring, which we call relaxed coloring. In an m-relaxed p-coloring the vertices are colored with p colors so that each vertex has up to m neighbors with the same color. We show that an m-relaxed p-coloring with reasonably small m and p can be computed very efficiently. We also develop a technique to employ multiple relaxed colorings of various subgraphs of the original graph G for computing a (Δ+1)-coloring of G. We believe that these techniques and the notion of relaxed coloring are of independent interest.

• Affine Dispersers from Subspace Polynomials
  Eli Ben-Sasson, Swastik Kopparty
  

  An affine disperser over F₂ⁿ for sources of dimension d is a function f: F₂ⁿ → F₂ such that for any affine space S ⊆ F₂ⁿ of dimension at least d, we have {f(s) : s ∈ S} = F₂. Affine dispersers have been considered in the context of deterministic extraction of randomness from structured sources of imperfect randomness. Previously, explicit constructions of affine dispersers were known for every d = Ω(n), due to Barak et. al. [BKSSW] and Bourgain [Bourgain] (the latter in fact gives stronger objects called affine extractors).

  In this work we give the first explicit affine dispersers for sublinear dimension. Specifically, our dispersers work even when d = Ω(n^4/5). The main novelty in our construction lies in the method of proof, which relies on elementary properties of subspace polynomials. In contrast, the previous works mentioned above relied on sum-product theorems for finite fields.

• A new Line of Attack on the Dichotomy Conjecture
  Gabor Kun and Mario Szegedy
  

  The well known dichotomy conjecture of Feder and Vardi states that for every family F of constraints csp(F) is either polynomially solvable or NP-hard. Bulatov and Jeavons reformulated this conjecture in terms of the properties of the algebra Pol(F), where the latter is the collection of those m-ary operations (m= 1,2,...) that keep all constraints in F invariant. We show that the algebraic condition boils down to whether there are arbitrarily resilient functions in Pol(F). Equivalently, we can express this in the terms of the PCP theory: csp(F) is NP-hard iff all long code tests created from F that passes with zero error admits only juntas. Then, using this characterization and a result of Dinur, Friedgut and Regev, we give an entirely new and transparent proof to the Hell-Nesetril theorem, which states that for a simple connected undirected graph H, the problem csp(H) is NP-hard if and only if H is non-bipartite.

  We also introduce another notion of resilience (we call it strong resilience), and we use it in the investigation of csp problems that 'do not have the ability to count.' The complexity of this class is unknown. Several authors conjectured that csp problems without the ability to count have bounded width, or equivalently, that they can be characterized by existential k-pebble games. The resolution of this conjecture would be a major step towards the resolution of the dichotomy conjecture. We show that csp problems without the ability to count are exactly the ones with strongly resilient term operations, which might give a handier tool to attack the conjecture than the known algebraic characterizations.

• Exact Learning of Random DNF Formulas Under the Uniform Distribution
  Linda Sellie
  

  We show that randomly generated c log(n)-DNF formula can be learned exactly in probabilistic polynomial time using randomly generated examples. Our notion of randomly generated is with respect to a uniform distribution. To prove this we extend the concept of well behaved c log(n)-Monotone DNF formulae to c log(n)-DNF, and show that almost every DNF formula is well-behaved, and that there exists a probabilistic Turing machine that exactly learns all well behaved c log(n)-DNF formula. This is the first algorithm that learns a large class of DNF with a polynomial number of terms from random examples alone.

• On Proximity Oblivious Testing
  Oded Goldreich and Dana Ron
  

  We initiate a systematic study of a special type of property testers. These testers consist of repeating a basic test for a number of times that depends on the proximity parameter, whereas the basic test is oblivious of the proximity parameter. We refer to such basic tests by the term Proximity-Oblivious Testers.

  While proximity-oblivious testers were studied before - most notably in the algebraic setting - the current study seems to be the first one to focus on graph properties. We provide a mix of positive and negative results, and in particular characterizations of the graph properties that have constant-query proximity-oblivious testers in the two standard models (i.e., the adjacency matrix and the bounded-degree models). Furthermore, we show that constant-query proximity-oblivious testers do not exist for many easily testable properties, and that even when proximity-oblivious testers exist, repeating them does not necessarily yield the best standard testers for the corresponding property.

• Explicit construction of a small ε-net for linear threshold functions
  Yuval Rabani and Amir Shpilka
  

  We give explicit constructions of ε nets for linear threshold functions on the binary cube and on the unit sphere. The size of the constructed nets is polynomial in the dimension n and in 1/ε. To the best of our knowledge no such constructions were previously known. Our results match, up to the exponent of the polynomial, the bounds that are achieved by probabilistic arguments.

  As a corollary we also construct subsets of the binary cube that have size polynomial in n and covering radius of n/2 - c\sqrt{n log n}, for any constant c. This improves upon the well known construction of dual BCH codes that only guarantee covering radius of n/2 - c\sqrt{n}.

• Quantum Algorithms using the Curvelet Transform
  Yi-Kai Liu
  

  The curvelet transform is a directional wavelet transform over Rⁿ, originally due to Candes and Donoho (2002). It is used to analyze functions that have singularities along smooth surfaces. I demonstrate how this can lead to new quantum algorithms. I give an efficient implementation of a quantum curvelet transform, together with two applications: a single-shot measurement procedure for approximately finding the center of a ball in Rⁿ, given a quantum-sample over the ball; and, a quantum algorithm for finding the center of a radial function over Rⁿ, given oracle access to the function. I conjecture that algorithm (1) succeeds with constant probability using 1 quantum-sample, and algorithm (2) succeeds with constant probability using O(1) oracle queries. This holds independent of the dimension n — this can be interpreted as a quantum speed-up. Finally, I prove some rigorous bounds on the distribution of probability mass for the continuous curvelet transform. This almost proves my conjecture, except for issues of discretization.

• Multiple Intents Re-Ranking
  Yossi Azar, Iftah Gamzu and Xiaoxin Yin
  

  One of the most fundamental problems in web search is how to re-rank result web pages based on user logs. Most traditional models for re-ranking assume each query has a single intent. That is, they assume all users formulating the same query have similar preferences over the result web pages. It is clear that this is not true for a large portion of queries as different users may have different preferences over the result web pages. Accordingly, a more accurate model should assume that queries have multiple intents.

  In this paper, we introduce the multiple intents re-ranking problem. This problem captures scenarios in which some user makes a query, and there is no information about its real search intent. In such case, one would like to re-rank the search results in a way that minimizes the efforts of all users in finding their relevant web pages. More formally, the setting of this problem consists of various types of users, each of which interested in some subset of the search results. Furthermore, each user type has a non-negative profile vector. Consider some ordering of the search results. This order determines a position for each search result, and induces a position vector of the results relevant to each user type. The overhead of a user type is the dot product of its profile vector and its induced position vector. The goal is to order the search results as to minimize the average overhead of the users.

  Our main result is an O(log r)-approximation algorithm for the problem, where r is the maximum number of search results that are relevant to any user type. The algorithm is based on a new technique, which we call harmonic interpolation. In addition, we consider two important special cases. The first case is when the profile vector of each user type is non-increasing. This case is a generalization of the well-known min-sum set cover problem. We extend the techniques of Feige, Lovász and Tetali (Algorithmica '04), and present an algorithm achieving 4-approximation. The second case is when the profile vector of each user type is non-decreasing. This case generalizes the minimum latency set cover problem. We devise a LP-based algorithm that attains 2-approximation. In particular, this result improves the e-approximation for minimum latency set cover due to Hassin and Levin (ESA '05).

• A constructive proof of the Lovasz Local Lemma
  Robin A. Moser
  

  The Lovasz Local Lemma is a powerful tool to prove the existence of combinatorial objects meeting a prescribed collection of criteria. The technique can directly be applied to the satisfiability problem, yielding that a k-CNF formula in which each clause has common variables with at most 2^k−2 other clauses is always satisfiable. All hitherto known proofs of the Local Lemma are non-constructive and do thus not provide a recipe as to how a satisfying assignment to such a formula can be efficiently found. In his breakthrough paper, Beck demonstrated that if the neighbourhood of each clause be restricted to O(2^k/48), a polynomial time algorithm for the search problem exists. Alon simplified and randomized his procedure and improved the bound to O(2^k/8). Srinivasan presented a variant that achieves a bound of essentially O(2^k/4). In an earlier publication, we improved this to O(2^k/2). In the present paper, we give a randomized algorithm that finds a satisfying assignment to every k-CNF formula in which each clause has a neighbourhood of at most the asymptotic optimum of 2^k−5−1 other clauses and that runs in expected time polynomial in the size of the formula, irrespective of k. If k is considered a constant, we can also give a deterministic variant. In contrast to all previous approaches, our analysis does not anymore invoke the standard non-constructive versions of the Local Lemma and can therefore be considered an alternative, constructive proof of it.

• Holant Problems and Counting CSP
  Jin-Yi Cai, Pinyan Lu and Mingji Xia
  

  We propose and explore a novel alternative framework to study the complexity of counting problems, called Holant Problems. Compared to counting Constrained Satisfaction Problems (#CSP), it is a refinement with a more explicit role for the function constraints. Both graph homomorphism and #CSP can be viewed as special cases of Holant Problems. We prove complexity dichotomy theorems in this framework. Because the framework is more stringent, previous dichotomy theorems for #CSP problems no longer apply. Indeed, we discover surprising tractable subclasses of counting problems, which could not have been easily specified in the #CSP framework. The main technical tool we use and develop is holographic reductions. Another technical tool used in combination with holographic reductions is polynomial interpolations. The study of Holant Problems led us to discover and prove a complexity dichotomy theorem for the most general form of Boolean #CSP where every constraint function takes values in the complex number field C.

• Every planar graph is the intersection graph of segments in the plane
  Jeremie Chalopin and Daniel Goncalves
  

  Given a set S of segments in the plane, the intersection graph of S is the graph with vertex set S in which two vertices are adjacent if and only if the corresponding two segments intersect. We prove a conjecture of Scheinerman (PhD Thesis, Princeton University, 1984) that every planar graph is the intersection graph of some segments in the plane.

• 3-Query Locally Decodable Codes of Subexponential Length
  Klim Efremenko
  

  Locally Decodable Codes (LDC) allow one to decode any particular symbol of the input message by making a constant number of queries to a codeword, even if a constant fraction of the codeword is damaged. In recent work [Yekhanin08] Yekhanin constructs a 3-query LDC with sub-exponential length of size exp(exp(O((log n)/(log log n)))). However, this construction requires a conjecture that there are infinity many Mersenne primes. In this paper we give an unconditional 3-query LDC construction with shorter codeword length of exp(exp(O(\sqrt{log n loglog n}))). We also give a 2^r-query LDC with length of exp(exp(O(\sqrt[r]{log n loglog^r-1 n}))). The main ingredient in our construction is the existence of super-polynomial size set-systems with restricted intersections [Grolmusz00] which holds only over composite numbers.

• Fault-Tolerant Spanners for General Graphs
  S. Chechik, M. Langberg, D. Peleg and L. Roditty
  

  The paper concerns graph spanners that are resistant to vertex or edge failures. Given a weighted undirected n-vertex graph G=(V,E) and an integer k ≥ 1, the subgraph H=(V,E'), E'⊆ E, is a spanner of stretch k (or, a k-spanner) of G if δ_H(u,v) ≤ k ⋅ δ_G(u,v) for every u,v ∈ V, where δ_G'(u,v) denotes the distance between u and v in G'. Graph spanners were extensively studied since their introduction over two decades ago. It is known how to efficiently construct a (2k-1)-spanner of size O(n^1+1/k), and this size-stretch tradeoff is conjectured to be tight.

  The notion of fault tolerant spanners was introduced a decade ago in the geometric setting [Levcopoulos et al., STOC'98]. A subgraph H is an f-vertex fault tolerant k-spanner of the graph G if for any set F⊆ V of size at most f and any pair of vertices u,v ∈ V \ F, the distances in H satisfy δ_{H \ F}(u,v) ≤ k ⋅ δ_{G \ F}(u,v). Levcopoulos et al. presented an efficient algorithm that constructs an f-vertex fault tolerant geometric (1+ε)-spanner, that is, given a set S of n points in R^d, their algorithm finds a sparse graph H such that for every set F⊆ S of size f and any pair of points u,v ∈ S \ F it satisfies that δ_{H \ F}(u,v) ≤ (1+ε) |uv|, where |uv| is the Euclidean distance between u and v. A fault tolerant geometric spanner with optimal maximum degree and total weight was presented in [Czumaj and Zhao, SoCG'03]. This paper also raised as an open problem the question whether it is possible to obtain a fault tolerant spanner for an arbitrary undirected weighted graph.

  The current paper answers this question in the affirmative, presenting an f-vertex fault tolerant (2k-1)-spanner whose size is O(f³ k^f+1 ⋅ n^1+1/k log^1-1/kn). Interestingly, the stretch of the spanner remains unchanged while the size of the spanner only increases by a factor that depends on the stretch k, on the number of potential faults f, and on logarithmic terms in n. In addition, we consider the simpler setting of f-edge fault tolerant spanners (defined analogously). We present an f-edge fault tolerant 2k-1 spanner with edge set of size O(f ⋅ n^1+1/k) (only f times larger than standard spanners). For both edge and vertex faults, our results, are shown to hold when the given graph G is weighted.

• Bit-Probe Lower Bounds for Succinct Data Structures
  Emanuele Viola
  

  We prove lower bounds on the redundancy necessary to represent a set S of objects using a number of bits close to the information-theoretic minimum log₂ |S|, while answering various queries by probing few bits. Our main results are:

  • We prove that, to represent n ternary elements t ∈ \zotⁿ in terms of binary elements \zo^u while accessing a single element t_i ∈ \zot by non-adaptively probing q bits, one needs u ≥ (log₂ 3)n + n/2^{q^{O(1)}}. This matches a recent, exciting work by Patrascu (FOCS 2008) who gives a representation where u ≤ (log₂ 3)n + n/2^{q^{Ω(1)}} (also non-adaptive).
  • We also prove a similar lower bound for the dictionary problem of representing sets of size n/3 from a universe of n elements in terms of binary elements \zo^u while answering membership queries by non-adaptively probing q bits: one needs u ≥ log₂ \binom{n}{n/3} + n/2^{q^{O(1)}} - log n.

  Both results above hold when replacing the constant "3" with any other constant which is not a power of 2. They extend to randomized representations, and imply weaker yet interesting bounds for adaptive probes as well. Ours are the first lower bounds for these fundamental problems; we obtain them drawing on ideas used in lower bounds for locally decodable codes.

• A Nearly Optimal Oracle for Aoviding Failed Vertices and Edges
  Aaron Bernstein and David Karger
  

  We present an improved oracle for the distance sensitivity problem. The goal is to preprocess a directed graph G = (V,E) with non-negative edge weights to answer queries of the form: what is the length of the shortest path from x to y that does not go through some failed vertex or edge f. The state of the art algorithm produces an oracle of size \widetilde{O}(n²) that has an O(1) query time, and an \widetilde{O}(n²\sqrt{m}) construction time. It is a randomized Monte Carlo algorithm, so it works with high probability. Our oracle also has a constant query time and an \widetilde{O}(n²) space requirement, but it has an improved construction time of \widetilde{O}(mn), and it is deterministic. Note that O(1) query, O(n²) space, and O(mn) construction time is also the best known bound (up to logarithmic factors) for the simpler problem of finding all pairs shortest paths in a weighted, directed graph. Thus, barring an improvement in the all pairs shortest path problem, our oracle is optimal up to logarithmic factors.

• An Efficient Algorithm for Partial Order Production
  Jean Cardinal, Samuel Fiorini, Gwenael Joret, Raphael M. Jungers and J. Ian Munro
  

  We consider the problem of partial order production: arrange the elements of an unknown totally ordered T into a target partially ordered set S, by comparing a minimum number of pairs in T. Special cases of this problem include sorting by comparisons, selection, multiple selection, and heap construction. We give an algorithm performing ITLB + o(ITLB) + O(n) comparisons in the worst case. Here, n denotes the size of the ground sets, and ITLB denotes a natural information-theoretic lower bound on the number of comparisons needed to produce the target poset. The overall complexity of our algorithm is polynomial. This answers a question of Yao (SICOMP, 1989). Our strategy is to extend the poset S to a weak order W whose corresponding information-theoretic lower bound is provably not much larger than that for S. Taking W instead of S as a target poset, we then solve the problem by applying a multiple selection algorithm that performs not much more than ITLB comparisons. We base our analysis on the entropy of the target poset S, a quantity that can be efficiently computed and provides a good estimate of ITLB since the latter is, up to a linear error term, n times the entropy of S.

• On the Complexity of Communication Complexity
  Eyal Kushilevitz and Enav Weinreb
  

  We consider the following question: given a two-argument boolean function f, represented as an N × N binary matrix, how hard is to determine the (deterministic) communication complexity of f? We address two aspects of this question. On the computational side, we prove that, under appropriate cryptographic assumptions (such as the intractability of factoring), the deterministic communication complexity of f is hard to approximate to within some constant. Under stronger (yet arguably reasonable) assumptions, we obtains even stronger hardness results that match the best known approximation. On the analytic side, we present a family of functions for which determining the communication complexity (or even obtaining non-trivial lower bounds on it) imply proving circuit lower bounds for some corresponding problems. Such connections between circuit complexity and communication complexity were known before (Karchmer-Wigderson 1988) only in the more involved context of relations (search problems) and not in the context of functions (decision problems). This result, in particular, may explain the difficulty of analyzing the communication complexity of certain functions such as the "clique vs. independent-set" family of functions, introduced by Yannakakis (1988).

• List Decoding Tensor Products and Interleaved codes
  Parikshit Gopalan, Venkatesan Guruswami and Prasad Raghavendra
  

  We design the first efficient algorithms and prove new combinatorial bounds for list decoding tensor products of codes and interleaved codes. We show that for every code, the ratio of its list decoding radius to its minumum distance stays unchanged under the tensor product operation (rather than squaring, as one might expect). This gives the first efficient list decoders and new combinatorial bounds for some natural codes including multivariate polynomials where the degree in each variable is bounded. We show that for every code, its list decoding radius remains unchanged under m-wise interleaving for an integer m. This generalizes a recent result of Dinur et al. [DGKS], who proved such a result for interleaved Hadamard codes (equivalently, linear transformations). Using the notion of generalized Hamming weights, we give better list size bounds for both tensoring and interleaving of binary linear codes. By analyzing the weight distribution of these codes, we reduce the task of bounding the list size to bounding the number of close-by low-rank codewords. For decoding linear transformatons, using rank-reduction together with other ideas, we obtain list size bounds that are tight over small fields. Our results give better bounds on the list decoding radius than what is obtained from the Johnson bound, and yield rather general families of codes decodable beyond the Johnson bound.

• Non-Malleability Amplification
  Huijia Lin and Rafael Pass
  

  We show a technique for amplifying commitment schemes that are non-malleable with respect to identities of length t, into ones that are non-malleable with respect to identities of length Ω(2^t), while only incurring a constant overhead in round-complexity. As a result we obtain a construction of O(1)^{log* n}-round (i.e., "essentially" constant-round) non-malleable commitments from any one-way function, and using a black-box proof of security.

• Max Cut and the Smallest Eigenvalue
  Luca Trevisan
  

  We describe a new approximation algorithm for Max Cut. Our algorithm runs in \tilde O(n²) 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\sqrt{ε} + 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(\sqrt ε) 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 an \tilde O(n³) time algorithm that cuts 1/2 + e^-Ω(1/ε) fraction of edges in graphs in which the optimum is 1/2 + ε.

• Artin automorphisms, Cyclotomic function fields, and Folded list-decodable codes
  Venkatesan Guruswami
  

  Algebraic codes that achieve list decoding capacity were recently constructed by a careful "folding" of the Reed-Solomon code. The "low-degree" nature of this folding operation was crucial to the list decoding algorithm. We show how such folding schemes conducive to list decoding arise out of the Artin-Frobenius automorphism at primes in Galois extensions. Using this approach, we construct new folded algebraic-geometric codes for list decoding based on cyclotomic function fields with a cyclic Galois group. Such function fields are obtained by adjoining torsion points of the Carlitz action of an irreducible M ∈ F_q[T]. The Reed-Solomon case corresponds to the simplest such extension (corresponding to the case M=T). In the general case, we need to descend to the fixed field of a suitable Galois subgroup in order to ensure the existence of many degree one places that can be used for encoding.

  Our methods shed new light on algebraic codes and their list decoding, and lead to new codes achieving list decoding capacity. Quantitatively, these codes provide list decoding (and list recovery/soft decoding) guarantees similar to folded Reed-Solomon codes but with an alphabet size that is only polylogarithmic in the block length. In comparison, for folded RS codes, the alphabet size is a large polynomial in the block length. This has applications to fully explicit (with no brute-force search) binary concatenated codes for list decoding up to the Zyablov radius.

• The Extended BG-Simulation and the Characterization of t-Resiliency
  Eli Gafni
  

  A distributed task T on n processors is an input/output relation between a collection of processors' inputs and outputs. While all tasks are solvable if no processor will ever crash, the FLP result shows that the task of consensus is not solvable even if just a single processor may crash. What tasks are solvable if at most t<n processors may crash? I.e. what tasks are solvable t-resiliently?

  The Herlihy-Shavit condition characterize solvability when t=n-1, i.e. they characterized wait-free solvability. The Borowsky-Gafni (BG) simulation characterizes t-resilient solvability by reducing the question to wait-free solvability. Alas, the simulation applies only to "colorless" tasks - tasks like consensus in which one processor can adopt the output of any other processor.

  In this paper we amend the BG-simulation to result in the Extended-BG-simulation, an extension that yields a full characterization of t-resilient solvability: A task T on n processors p₀,...,p_n-1 is solvable t-resiliently iff all tasks T' on t+1 simulators s₀,...s_t created as follows are wait-free solvable. Simulator s_i is given an input of processor p_i as well as the inputs to a set of processors PI_i of size n-(t+1) where for all p_j ∈ PI_i, j>i. Simulator s_i outputs for p_i as well as for a set of processors PO_i of size n-(t+1) where for all p_j ∈ PO_i, j>i. Any processor whose output is in PO_i, its input is given to some simulator. The input/output of the simulators have to be a projection of a single original input/output tuple-pair in T of a size that correspond to all the given inputs.

  We demonstrate the convenience that the characterization provides, in two ways. First, we prove a new impossibility result: We show that n processes can solve t-resiliently weak renaming with n+(t+1)-2 names, where n>1 and 0<t<n, iff weak-renaming on t+1 processors is wait-free solvable with 2t names. Second, we reproduce the result that the solvability n-processors tasks, t-resiliently, for t>1 and n>2, is undecidable, by a simple reduction to the undecidability of the wait-free solvability of 3-processors tasks.

• Finding Sparse Cuts Locally Using Evolving Sets
  Reid Andersen and Yuval Peres
  

  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 algroithm 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. In this paper, we introduce a 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 set of vertices A that has conductance at most φ, for at least half of the starting vertices in A our algorithm will output (with probability at least half), a set of conductance O(φ^1/2 log^1/2 n). 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 O(φ^-1/2 polylog(n)). In comparison, the best previous local partitioning algorithm, due to Andersen, Chung, and Lang, has the same approximation guarantee, but a larger ratio of O(φ^-1 polylog(n) between the complexity and output volume. Using our local partitioning algorithm as a subroutine, we construct a fast algorithm for finding balanced cuts. Given a fixed value of φ, the resulting algorithm has complexity O(m+nφ^-1/2)*polylog(n) and returns a cut with conductance O(φ^1/2 log^1/2 n) and volume at least v_φ/2, where v_φ is the largest volume of any set with conductance at most φ.

• A Deterministic Reduction for the Gap Minimum Distance Problem
  Qi Cheng and Daqing Wan
  

  Determining the minimum distance of a linear code is one of the most important problems in algorithmic coding theory. The exact version of the problem was shown to be NP-complete in [Vardy97]. In [DumerMi03], the gap version of the problem was shown to be NP-hard for any constant factor under a randomized reduction. In this paper, we derandomize the reduction and thus prove that there is no deterministic polynomial time algorithm to approximate the minimum distance to any constant factor unless P=NP. We also prove that the minimum distance is not approximable in deterministic polynomial time to the factor 2^{log ^{1-ε} n} unless NP ⊆ DTIME(2^polylog(n)). As the main technical contribution, for any constant 2/3< ρ < 1, we present a deterministic algorithm that given a positive integer s, runs in time poly(s) and constructs a code \code of length poly(s) with an explicit Hamming ball of radius ρ d(\code) such that a projection at s coordinates sends the codewords in the ball surjectively onto a linear subspace of dimension s, where d(\code) denotes the minimum distance of \code.

• How long does it take to catch a wild kangaroo?
  Ravi Montenegro and Prasad Tetali
  

  The discrete logarithm problem asks to solve for the exponent x, given the generator g of a cyclic group G and an element h∈ G such that g^x=h. We give the first rigorous proof that Pollard's Kangaroo method finds the discrete logarithm in expected time (3+o(1))\sqrt{b-a} when the logarithm x∈[a,b], and (2+o(1))\sqrt{b-a} when x\in_{uar}[a,b]. This matches the conjectured time complexity and, rare among the analysis of algorithms based on Markov chains, even the lead constants 2 and 3 are correct.

• An Improved Constant-Time Approximation Algorithm for Maximum Matchings
  Yuichi Yoshida, Masaki Yamamoto and Hiro Ito
  

  This paper studies approximation algorithms for problems on degree-bounded graphs. Let n and d be the number of vertices and the degree bound, respectively. This paper presents an algorithm to approximate the size of some maximal independent set with additive error ε n whose running time is \cmpmisx. Using this algorithm, it also shows that there are approximation algorithms for many other problems, e.g., the maximum matching problem, the minimum vertex cover problem, and the minimum set cover problem, that run exponentially faster than existing algorithms with respect to d and 1/ε.

  Its approximation algorithm for the maximum matching problem can be transformed to a testing algorithm for the property of having a perfect matching with two-sided error. On the contrary, it also shows that every one-sided error tester for the property requires at least Ω(n) queries.

• A competitive algorithm for minimizing weighted flow time on unrelated machines with speed augmentation
  Jivitej S. Chadha, Naveen Garg, Amit Kumar and V. N. Muralidhara
  

  We consider the online problem of scheduling jobs on unrelated machines so as to minimize the total weighted flow time. This problem has an unbounded competitive ratio even for very restricted settings. In this paper we show that if we allow the machines of the online algorithm to have ε more speed than those of the offline algorithm then we can get an O(ε^-2)-competitive algorithm.

  Our algorithm schedules jobs preemptively but without migration. However, we compare our solution to an offline algorithm which allows migration. Our analysis uses a potential function argument which can also be extended to give a simpler and better proof of the randomized immediate dispatch algorithm of Chekuri-Goel-Khanna-Kumar for minimizing average flow time on parallel machines.

• Randomly supported independence and resistance
  Per Austrin and Johan Håstad
  

  We prove that for any positive integer k, there is a constant c_k such that a randomly selected set of c_k n^k log n Boolean vectors with high probability supports a balanced k-wise independent distribution. In the case of k≤ 2 a more elaborate argument gives the stronger bound c_k n^k. Using a recent result by Austrin and Mossel this shows that a predicate on t bits, chosen at random among predicates accepting c₂ t² input vectors, is, assuming the Unique Games Conjecture, likely to be approximation resistant. These results are close to tight: we show that there are other constants, c_k', such that a randomly selected set of cardinality c_k' n^k points is unlikely to support a balanced k-wise independent distribution and, for some c>0, a random predicate accepting ct²/ log t input vectors is non-trivially approximable with high probability. In a different application of the result of Austrin and Mossel we prove that, again assuming the Unique Games Conjecture, any predicate on t bits accepting at least (59/60) ⋅ 2^t inputs is approximation resistant. Essentially all results extend from the Boolean domain to larger finite domains.

• Random Graphs and the Parity Quantifier
  Phokion Kolaitis, Swastik Kopparty
  

  The classical zero-one law for first-order logic on random graphs says that for every first-order property φ in the theory of graphs and every p ∈ (0,1), the probability that the random graph G(n, p) satisfies φ approaches either 0 or 1 as n approaches infinity. It is well known that this law fails to hold for any formalism that can express the parity quantifier: for certain properties, the probability that G(n,p) satisfies the property need not converge, and for others the limit may be strictly between 0 and 1.

  In this work, we capture the limiting behavior of properties definable in first order logic augmented with the parity quantifier, FOP, over G(n,p), thus eluding the above hurdles. Specifically, we establish the following "modular convergence law": "For every FOP sentence φ, there are two explicitly computable rational numbers a₀, a₁, such that for i ∈ {0,1}, as n approaches infinity, the probability that the random graph G(2n+i, p) satisfies φ approaches a_i." Our results also extend appropriately to FO equipped with \Mod_q quantifiers for prime q.

  In the process of deriving the above theorem, we explore a new question that may be of interest in its own right. Specifically, we study the joint distribution of the subgraph statistics modulo 2 of G(n,p): namely, the number of copies, mod 2, of a fixed number of graphs F₁, ..., F_l of bounded size in G(n,p). We first show that every FOP property φ is almost surely determined by subgraph statistics modulo 2 of the above type. Next, we show that the limiting joint distribution of the subgraph statistics modulo 2 depends only on n mod 2, and we determine this limiting distribution completely. Interestingly, both these steps are based on a common technique using multivariate polynomials over finite fields and, in particular, on a new generalization of the Gowers norm that we introduce.

  The first step above is analogous to the Razborov-Smolensky method for lower bounds for AC0 with parity gates, yet stronger in certain ways. For instance, it allows us to obtain examples of simple graph properties that are exponentially uncorrelated with every FOP sentence, which is something that is not known for AC0[⊕].

• Differential Privacy and Robust Statistics
  Cynthia Dwork and Jing Lei
  

  In the past several years a promising approach to private data analysis has emerged, based on the notion of differential privacy. Informally, this ensures that any outcome of an analysis is "roughly as likely" to occur independent of whether any individual opts in to, or to opts out of, the database. In consequence, the specific data of any one individual can never greatly affect the outcome of the analysis, ensuring privacy regardless of any additional ("auxiliary") information known to the analyst. General techniques for ensuring differential privacy have now been proposed, and many datamining tasks can be carried out in a differentially private fashion, frequently with very accurate results.

  In this work we explore privacy-preserving parameter estimation. Privacy-preserving statistics would appear to be connected to robust statistics, the subfield of statistics that attempts to cope with several small errors due, for example, to rounding errors in measurements, as well as a few arbitrarily wild errors occurring, say, from data entry failures. In consequence, in a robust analysis the specific data for any one individual should not greatly affect the outcome of the analysis. It would therefore seem that robust statistical estimators, or procedures, might form a starting point for designing accurate differentially private statistical estimators, and the approach based on influence functions (Hampel et al.) is particularly suggestive of differential privacy. We report here on a successful attempt to instantiate this intuition.

  Our algorithms follow a new paradigm for differentially private mechanisms, which we call Propose-Test-Release (PTR). All previous differentially private algorithms are special cases of this framework. We give general composition theorems for PTR mechanisms, extending and refining previous analyses.

• Intrinsic Robustness of the Price of Anarchy
  Tim Roughgarden
  

  The price of anarchy is a worst-case measure of the inefficiency of selfish behavior, defined as the ratio of the objective function value of a worst Nash equilibrium of a game and that of an optimal outcome. The measure does, however, assume that players successfully reach some Nash equilibrium. This fact motivates the search for inefficiency guarantees that apply more generally to weaker notions of equilibria (such as mixed Nash and correlated equilibria), or to sequences of outcomes generated by natural experimentation strategies (such as successive best responses or simultaneous regret-minimization). Recently, researchers have identified a number of settings in which the known quantitative bounds on the price of anarchy carry over to other equilibrium notions and/or the results of natural dynamics.

  This paper proves a fundamental connection between the price of anarchy and its seemingly stronger relatives in classes of games with a sum objective, such as congestion games and variants thereof: an upper bound on the worst-case price of anarchy for pure Nash equilibria necessarily implies the exact same worst-case upper bound for mixed Nash equilibria, correlated equilibria, and the average objective function value of regret-minimizing players (or "price of total anarchy"). In this sense, price of anarchy guarantees in such games are "intrinsically robust". Under mild additional assumptions, our proof techniques also automatically yield performance guarantees for various forms of best-response dynamics, as well as bicriteria inefficiency bounds.

  Byproducts of our work include several significant new results for the inefficiency of equilibria in congestion games: tight bounds on the price of anarchy for all (not necessarily polynomial) cost functions; bicriteria bounds; and a structural characterization of games that are universal worst-case examples for the POA.

• On the convergence of regret minimization dynamics in concave games
  Eyal Even-Dar, Yishay Mansour and Uri Nadav
  

  We study a general sub-class of concave games, which we call socially concave games. We show that if each player follows any no-external regret minimization procedure then the dynamics converges in the sense that both the average action vector converges to a Nash equilibrium and that the utility of each player converges to her utility in that Nash equilibrium.

  We show that many natural games are socially concave games. Specifically, we show that linear Cournot competition and linear resource allocation games are socially-concave games, and therefore our convergence result applies to them. In addition, we show that a simple best response dynamic might diverge for linear resource allocation games, and is known to diverge for a linear Cournot competition. For the TCP congestion games we show that "near" the equilibrium these games are socially-concave, and using our general methodology we show convergence of specific regret minimization dynamics.

• CSP Gaps and Reductions in the Lasserre Hierarchy
  Madhur Tulsiani
  

  We study integrality gaps for SDP relaxations of constraint satisfaction problems, in the hierarchy of SDPs defined by Lasserre. Schoenebeck recently showed the first integrality gaps for these problems, showing that for MAX k-XOR, the ratio of the integer optimum to the SDP optimum may be as small as 1/2 even after Ω(n) rounds of the Lasserre hierarchy.

  We show that for the general MAX k-CSP problem over binary domain, the ratio of the value achieved by the optimal assignment to the SDP optimum, can be as small as 2k/2^k + ε even after Ω(n) rounds of the Lasserre hierarchy. For alphabet size q which is a prime, we show that the ratio for MAX k-CSP_q is at most kq(q-1)/q^k + ε even after Ω(n) rounds. The method of proof also gives optimal integrality gaps for a predicate chosen at random.

  We also explore how to translate integrality gaps for CSPs into integrality gaps for other problems using reductions. Starting from the gaps for CSPs, we establish SDP gaps for Maximum Independent Set, Approximate Graph Coloring, Chromatic Number and Vertex Cover. For Independent Set and Chromatic Number, we show that the integrality gap can be as large as n/2^{O(\sqrt{log n log log n})} even after 2^{Ω(\sqrt{log n log log n})} rounds. In case of Approximate Graph Coloring, for every constant l, we show examples of graphs which admit a vector l-coloring for the SDP obtained by Ω(n) rounds of Lasserre, even though the actual chromatic number is Ω(2^l/2/l²). For Vertex Cover, we show an integrality gap of 1.36 for Ω(n^δ) rounds, for a small constant δ.

  The results for CSPs provide the first examples of Ω(n) round integrality gaps matching hardness results known only under the Unique Games Conjecture. This and some additional properties of the integrality gap instance, allow us to prove gaps for Independent Set and Chromatic Number which are stronger than the NP-hardness results known even under the Unique Games Conjecture.

• A Constant-Factor Approximation for Stochastic Steiner Forest
  Anupam Gupta and Amit Kumar
  

  We consider the stochastic Steiner forest problem: here we were given a collection of Steiner forest instances, and were guaranteed that a random one of these instances would appear tomorrow; moreover, the cost of edges tomorrow will be λ times the cost of edges today. Which edges should we buy today so that we can extend it to a solution for the instance arriving tomorrow, to minimize the total cost? While very general results have been developed for many problems in stochastic discrete optimization over the past years, the approximation status of the stochastic Steiner Forest problem has remained tantalizingly open, with considerable effort yielding constant-factor approximations only for some special cases of this problem.

  We resolve the status of the stochastic Steiner Forest problem and give a constant-factor primal-dual based approximation algorithm. Since the previously-solved special cases had yielded very complicated primal-dual algorithms, our solution heavily relies on techniques to reduce the complexity of the dual-growth process. Indeed, a major technical contribution of our work is to show how to take an optimal solution to the linear program and use it to factor the problem into two simpler parts—and how to grow duals and primals for each of these parts in a non-smooth (but well-controlled fashion) to generate a constant-factor approximation.

• On the geometry of graphs with a forbidden minor
  James R. Lee and Anastasios Sidiropoulos
  

  We study the topological simplification of graphs via random embeddings, leading ultimately to a reduction of the Gupta-Newman-Rabinovich-Sinclair (GNRS) L₁ embedding conjecture to a pair of manifestly simpler conjectures. The GNRS conjecture characterizes all graphs that have an O(1)-approximate multi-commodity max-flow/min-cut theorem. In particular, its resolution would imply a constant factor approximation for the general Sparsest Cut problem in every family of graphs which forbids some minor. In the course of our study, we prove a number of results of independent interest.

  • Every metric on a graph of pathwidth k embeds into a distribution over trees with distortion depending only on k. This is equivalent to the statement that any family of graphs excluding a forest embeds into a distribution over trees. For graphs of treewidth k, GNRS showed that this is impossible even for k=2. In particular, we show that pathwidth-k metrics embed into L₁ with bounded distortion, which resolves an open question even for k=3.
  • We prove a generic peeling lemma which uses random Whitney decompositions to peel simple structures like handles and apices off of graphs. This allows a number of new topological reductions. For example, if X is any metric space in which the removal of O(1) points leaves a bounded genus metric, then X embeds into a distribution over planar graphs.
  • Using these techniques, we show that the GNRS embedding conjecture is equivalent to two simpler conjectures: (1) The well-known planar embedding conjecture, and (2) a conjecture about embeddings of k-sums of graphs.
  
  
• Resilient Knowledge-Based Mechanisms For Truly Combinatorial Auctions (and Implementation in Surviving Strategies)
  Jing Chen and Silvio Micali
  

  We put forward a new mechanism achieving a high benchmark for (both revenue and) the sum of revenue and efficiency, in truly combinatorial auctions. Notably, our mechanism guarantees its performance (1) in a very adversarial collusion model; (2) for any profile of strategies surviving the iterated elimination of dominated strategies; and (3) by leveraging the knowledge that the players have about each other (in a non-Bayesian setting). Our mechanism also is computationally efficient, and preserves the players' privacy to an unusual extent.

• Public-Key Cryptosystems from the Worst-Case Shortest Vector Problem
  Chris Peikert
  

  We construct public-key cryptosystems that are secure assuming the worst-case hardness of approximating the length of a shortest nonzero vector in an n-dimensional lattice to within a small poly(n) factor. Prior cryptosystems with worst-case connections were based either on the shortest vector problem for a special class of lattices (Ajtai and Dwork, STOC 1997; Regev, J. ACM 2004), or on the conjectured hardness of lattice problems for quantum algorithms (Regev, STOC 2005).

  Our main technical innovation is a reduction from certain variants of the shortest vector problem to corresponding versions of the "learning with errors" (\lwe) problem; previously, only a quantum reduction of this kind was known. In addition, we construct new cryptosystems based on the search version of \lwe, including a very natural chosen ciphertext-secure system that has a much simpler description and tighter underlying worst-case approximation factor than prior constructions.

• One-Round Authenticated Key Agreement from Weak Secrets
  Yevgeniy Dodis and Daniel Wichs
  

  We study the question of information-theoretically secure authenticated key agreement from weak secrets. In this setting, Alice and Bob share a n-bit secret W, which might not be uniformly random but the adversary has at least k bits of uncertainty about it (formalized using conditional min-entropy). Alice and Bob wish to use W to agree on a nearly uniform secret key R, over a public channel controlled by an active adversary Eve. We show that non-interactive (single-message) protocols do not work when k ≤ n/2, and require poor parameters even when n/2 < k << n.

  On the other hand, for arbitrary values of k, we design a communication efficient two-message (i.e, one-round!) protocol extracting nearly k random bits. This dramatically improves the only previously known protocol of Renner and Wolf [RennerW03], which required O(λ) rounds where λ is the security parameter. Our solution takes a new approach by studying and constructing "non-malleable" seeded randomness extractors — if an attacker sees a random seed X and comes up with an arbitrarily related seed X' then we bound the relationship between R= Ext(W;X) and R' = Ext(W;X').

  We also extend our one-round key agreement protocol to the "fuzzy" setting, where Alice and Bob share "close" (but not equal) secrets W_A and W_B, and to the Bounded Retrieval Model (BRM) where the size of the secret W is huge.

• Twice-Ramanujan Sparsifiers
  Joshua D. Batson, Daniel A. Spielman and Nikhil Srivastava
  

  We prove that for every d>1 and every undirected, weighted graph G(V,E) on n vertices, there exists a weighted subgraph H of G with at most dn edges that preserves the Laplacian quadratic form of G up to a multiplicative error of d+1 \pm 2\sqrt{d}. Thus, H approximates G spectrally at least as well as a Ramanujan expander with dn/2 edges approximates the complete graph. We give an elementary, deterministic polynomial time algorithm for constructing H.

• Conditional Hardness for Satisfiable-3CSPs
  Ryan O'Donnell and Yi Wu
  

  In this paper we study a fundamental open problem in the area of probabilistic checkable proofs: What is the smallest s such that NP ⊆ naPCP_1,s[O(log n),3]? In the language of hardness of approximation, this problem is equivalent to determining the smallest s such that getting an s-approximation for satisfiable 3-bit constraint satisfaction problems ("3-CSPs") is NP-hard. The previous best upper bound and lower bound for s are 20/27+ε by Khot and Saket [KS06], and 5/8 (assuming NP subseteq BPP) by Zwick [Zwi98]. In this paper we close the gap assuming Khot's d-to-1 Conjecture. Formally, we prove that if Khot's d-to-1 Conjecture holds for any finite constant integer d, then NP⊆ naPCP_{1,5/8+ ε}[O(log n),3] for any constant ε > 0. Our conditional result also solves Hastad's open question [Has01] on determining the inapproximability of satisfiable Max-NTW ("Not Two") instances and confirms Zwick's conjecture [Zwi98] that the 5/8-approximation algorithm for satisfiable 3-CSPs is optimal.

• Near-Perfect Load Balancing by Randomized Rounding
  Tobias Friedrich and Thomas Sauerwald
  

  We consider and analyze a new algorithm for balancing indivisible loads on a distributed network with n processors. The aim is minimizing the discrepancy between the maximum and minimum load. In every time-step paired processors balance their load as evenly as possible. The direction of the excess token is chosen according to a randomized rounding of the participating loads.

  We prove that in comparison to the corresponding model of Rabani, Sinclair, and Wanka with arbitrary roundings, the randomization yields an improvement of roughly a square root of the achieved discrepancy in the same number of time-steps on all graphs. For the important case of expanders we can even achieve a constant discrepancy in O(log n (log log n)³) rounds. This is optimal up to log log n-factors while the best previous algorithms in this setting either require Ω(log² n) time or can only achieve a logarithmic discrepancy. Our new result also demonstrates that with randomized rounding the difference between discrete and continuous load balancing vanishes almost completely.

• Homology Flows, Cohomology Cuts
  Erin W. Chambers, Jeff Erickson and Amir Nayyeri
  

  We describe the first algorithms to compute maximum flows in surface-embedded graphs in near-linear time. Specifically, given an undirected graph embedded on an orientable surface of genus g, with two specified vertices s and t, we can compute a maximum (s,t)-flow in O(g⁷ n log² n log² C) time for integer capacities that sum to C, or in (g log n)^O(g) n time for real capacities. Except for the special case of planar graphs, for which an O(n log n)-time algorithm has been known for 20 years, the best previous time bounds for maximum flows in surface-embedded graphs follow from algorithms for general sparse graphs. Our key insight is to optimize the relative homology class of the flow, rather than directly optimizing the flow itself. A dual formulation of our algorithm computes the minimum-cost cycle or circulation in a given (real or integer) homology class.

• Numerical Linear Algebra in the Streaming Model
  Kenneth L. Clarkson and David P. Woodruff
  

  We give near-optimal space bounds in the streaming model for linear algebra problems that include estimation of matrix products, linear regression, low-rank approximation, and approximation of matrix rank. In the streaming model, sketches of input matrices are maintained under updates of matrix entries; we prove results for turnstile updates, given in an arbitrary order. We prove the first lower bounds known for the space needed by the sketches, for a given estimation error ε. We sharpen prior upper bounds, with respect to combinations of space, failure probability, and number of passes. The sketch we use for matrix A is simply S^TA, where S is a sign matrix.

  Our results include the following upper and lower bounds on the bits of space needed for 1-pass algorithms. Here A is an n × d matrix, B is an n × d' matrix, and c := d+d'. These results are given for fixed failure probability; for failure probability δ>0, the upper bounds require a factor of log (1/δ) more space. We assume that the inputs have integer entries specified by O(log (nd)) bits.

  • (Matrix Product) Output matrix C with ||A^TB-C||_F ≤ ε ||A||_F ||B||_F. We show that Θ(cε^-2 log (nc)) space is needed.
  • (Linear Regression) For d'=1, so that B is a vector b, find x so that ||Ax-b||₂ ≤ (1+ε)min_{x' ∈ R^d} ||Ax'-b||₂. We show that Θ(d²ε^-1 log (nd)) space is needed.
  • (Rank-k Approximation) Find matrix \tA_k of rank no more than k, so that ||A-\tA_k||_F ≤ (1+ε) ||A-A_k||_F, where A_k is the best rank-k approximation to A. Our lower bound is Ω(kε^-1(n+d) log (nd)) space, and we give a one-pass algorithm matching this when A is given row-wise or column-wise. For general updates, we give a one-pass algorithm needing O(kε^-2(n + d/ε²) log (nd)) space. We also give upper and lower bounds for multiple-pass algorithms, and a sketching analog of the CUR decomposition.
  
  
• Testing Juntas Nearly Optimally
  Eric Blais
  

  A function on n variables is called a k-junta if it depends on at most k of its variables. In this article, we show that it is possible to test whether a function is a k-junta or is “far” from being a k-junta with O(k log k)/ε queries, where ε is the approximation parameter. This result improves on the previous best upper bound of O(k^1.5)/ε queries and is asymptotically optimal, up to a logarithmic factor.

  We obtain the improved upper bound by introducing a new algorithm with one-sided error for testing juntas. Notably, the new algorithm is a valid junta tester under very general conditions: it holds for functions with arbitrary finite domains and ranges, and it holds under any product distribution over the domain.

  A key component of the analysis of the algorithm is a new structural result on juntas: roughly, we show that if a function f is “far” from being a k-junta, then f is “far” from being determined by k parts in a random partition. The structural lemma is proved using the Efron-Stein decomposition method.

• Linear-time Approximation Schemes for the Gale-Berlekamp Game and Related Minimization Problems
  Marek Karpinski and Warren Schudy
  

  We design a linear time approximation scheme for the Gale-Berlekamp Switching Game and generalize it to a wider class of dense fragile minimization problems including the Nearest Codeword Problem (NCP) and Unique Games Problem. Further applications include, among other things, finding a constrained form of matrix rigidity and maximum likelihood decoding of an error correcting code. As another application of our method we give the first linear time approximation schemes for correlation clustering with a fixed number of clusters and its hierarchical generalization. Our results depend on a new technique of dealing with small objective function values of optimization problems and could be of independent interest.

• Direct Product Testing: Improved and Derandomized
  Russell Impagliazzo, Valentine Kabanets and Avi Wigderson
  

  The "direct product code" of a function f gives its values on all possible k-tuples (f(x₁),...,f(x_k)). This basic construct underlies "hardness amplification" in cryptography, circuit complexity and PCPs. A recent breakthrough by Dinur and Goldenberg (FOCS'08) enabled for the first time testing proximity to this important code in the "list-decoding" regime. In particular, they give a 2-query test which works for success probability 1/k^α, and show that no such test works below success probability 1/k.

  Our main result is a 3-query test which works for exponentially small success probability exp (- k^α). Our techniques (which are based on recent simplified decoding algorithms for the same code (Impagliazzo et al., STOC'08) also allow us to considerably simplify the analysis of the 2-query test of [DG08]. Furthermore we are able to derandomize it, allowing the code to be of polynomial rate independent of k, and success probability 1/k^α.

  Finally we show the applicability of the new tests to PCPs. Starting with a 2-query PCP of alphabet Σ of size 2^t and soundness error 1-δ, Raz's (k-fold) parallel repetition theorem (and Holenstein's proof) [Raz-parallel,Hol07] yields a new 2-query PCP with soundness error exp(-(δ³k)/t), with the dependence on the alphabet size essential [Feige-Verbitsky]. Our techniques yield a 3-query PCP with soundness error exp(-δ k^1/3). While using 3 queries and having a worse exponential decay, our error is independent of the alphabet size!

• An Axiomatic Approach to Algebrization
  Russell Impagliazzo, Valentine Kabanets and Antonina Kolokolova
  

  In this paper, building on the work of Arora, Impagliazzo, and Vazirani [AIV92], we propose an axiomatic approach to "algebrization", which complements and clarifies the approaches of Fortnow [For94] and Aaronson/Wigderson [AW08]. We add to the axiomatic characterization of the class P from [AIV92] a new axiom, Arithmetic Checkability, and argue that, in a certain sense, the resulting theory provides a characterization of "algebrizing" techniques. In particular, we show the following: (i) Fortnow's algebraic oracles from [For94] all satisfy Arithmetic Checkability (so arithmetic checkability holds relative to arbitrarily powerful oracles). (ii) Most of the algebrizing collapses and separations from [AW08], such as IP=PSPACE, NP ⊂ ZKIP if one-way functions exist, MA-EXP ot ⊂ P/poly, etc., are provable from Arithmetic Checkability. (iii) Many of the open complexity questions (shown to require non-algebrizing techniques in [AW08]), such as "P vs. NP", "NP vs. BPP", etc., cannot be proved from Arithmetic Checkability. (iv) Arithmetic Checkability is also insufficient to prove one known result, NEXP=MIP (although relative to an oracle satisfying Arithmetic Checkability, NEXP^O restricted to poly-length queries is contained in MIP^O, mirroring a similar result from [AW08]).

• Efficient discrete-time simulations of continuous-time quantum query algorithms
  Richard Cleve, Daniel Gottesman, Michele Mosca, Rolando Somma and David Yonge-Mallo
  

  Background: Most quantum algorithms can be cast in a query model, where some unknown function is computed by a black-box, and the goal is to determine some property of the function with as few queries as possible. One example is the main component of Shor's factoring algorithm, which essentially determines the period of an unknown function that is promised to be strictly periodic. Grover's algorithm is another example. The continuous-time query model is a variant of the discrete query model in which queries can be interleaved with known operations (called "driving operations") continuously in time. Interesting algorithms have been discovered in this model, such as an algorithm for evaluating NAND trees more efficiently than any classical algorithm. Subsequent work has shown that there also exists an efficient algorithm for NAND trees in the discrete query model.

  New result: An open question has been whether any quantum algorithm in the continuous-time query model can be efficiently simulated by a quantum algorithm in the discrete query model. We show that any quantum algorithm in the continuous-time query model whose total query time is T can be simulated by a quantum algorithm in the discrete query model that makes O(T log T / loglog T) queries. This is the first upper bound that is independent of the driving operations (i.e., it holds even if the norm of the driving Hamiltonian is very large). A corollary is that any lower bound of T queries for a problem in the discrete-time query model immediately carries over to a lower bound of Omega(T loglog T/log T) in the continuous-time query model.

• Tight Lower Bounds for Greedy Routing in Uniform Small World Rings
  Martin Dietzfelbinger and Philipp Woelfel
  

  We consider an augmented ring-based network with vertices 0,...,n-1, where each vertex is connected to its left and right neighbor and possibly to some further vertices (called long range contacts). The outgoing edges of a vertex v are obtained by choosing a subset C of {1,2,...,n-1} at random according to a probability distribution mu over all subsets C of {1,2,...,n-1} with 1,n-1 in C (in a uniform manner, i.e., the distribution is the same for each vertex) and then connecting v to (v+i) mod n for each i in C by a unidirectional link. The long range contacts are the links for i in C-{1,n-1}.

  Motivated by Kleinberg's (2000) Small World Graph model, and packet routing strategies for peer-to-peer networks, the greedy routing algorithm on augmented rings, where each node routes the package to the neighbor closest to the destination of the package has been investigated thoroughly, both for the "one-sided case", where packets can travel only in one direction through the interval between starting and target node, and the "two-sided case", where there is no such restriction.

  It has been an open problem for some years to determine the expected number of hops that are needed by the greedy strategy to route a package between two randomly chosen vertices, for the best possible probability distribution mu. Upper bounds and partial lower bound results were e.g. given by Kleinberg (2000), Aspnes et al. (2002), or by Giakkoupis and Hadzilacos (2007). Results for the two-sided case were achieved only for very restricted classes of distributions mu. In this paper we resolve the lower bound problem optimally for Omega(1) ≤ l ≤ O(log n), where l is the expected number of long range contacts of a node. For both, the two-sided and the one-sided case we prove a lower bound of Omega((log n)²/l) for an arbitrary distribution mu.

  Our lower bounds were conjectured by Giakkoupis and Hadzilacos (2007). They match the upper bounds of Aspnes et al. (2002), who for each l in the considered range suggested a suitable distribution mu.

• Sherali-Adams Relaxations of the Matching Polytope
  Claire Mathieu and Alistair Sinclair
  

  We study the Sherali-Adams lift-and-project hierarchy of linear programming relaxations of the matching polytope. Our main result is an asymptotically tight expression 1+1/k for the integrality gap after k rounds of this hierarchy. The result is derived by a detailed analysis of the LP after k rounds applied to the complete graph K_2d+1. We give an explicit recurrence for the value of this LP, and hence show that its gap exhibits a "phase transition," dropping from close to its maximum value 1+1/(2d) to close to 1 around the threshold k=2d-\sqrt{d}. We also show that the rank of the matching polytope (i.e., the number of Sherali-Adams rounds until the integer polytope is reached) is exactly 2d-1.

• Mixing time for the solid-on-solid model
  Fabio Martinelli and Alistair Sinclair
  

  We analyze the mixing time of a natural local Markov chain (the Glauber dynamics) on configurations of the solid-on-solid model of statistical physics. This model has been proposed, among other things, as an idealization of the behavior of contours in the Ising model at low temperatures. Our main result is an upper bound on the mixing time of \Otilde(n^3.5), which is tight within a factor of \Otilde(\sqrt{n}). The proof, which in addition gives some insight into the actual evolution of the contours, requires the introduction of a number of novel analytical techniques that we conjecture will have other applications.

• The Detectability Lemma and Quantum Gap Amplification
  Dorit Aharonov, Itai Arad, Zeph Landau and Umesh Vazirani
  

  The quantum analog of a constraint satisfaction problem is a sum of local Hamiltonians - each (term of the) Hamiltonian specifies a local constraint whose violation contributes to the energy of the given quantum state. Formalizing the intuitive connection between the ground (minimal) energy of the Hamiltonian and the minimum number of violated constraints is problematic, since the number of constraints being violated is not well defined when the terms in the Hamiltonian do not commute. The detectability lemma proved in this paper provides precisely such a quantitative connection. We apply the lemma to derive a quantum analogue of the classical gap amplification lemma of random walks on expander graphs. The quantum gap amplification lemma holds for local Hamiltonians with expander interaction graphs. Our proofs are based on a novel structure imposed on the Hilbert space, which we call the XY decomposition, which enables a reduction from the quantum non-commuting case to the commuting case (where many classical arguments go through).

  The results may have several interesting implications. First, proving a quantum analogue to the PCP theorem is one of the most important challenges in quantum complexity theory. Our quantum gap amplification lemma may be viewed as the quantum analogue of the first of the three main steps in Dinur's PCP proof. Quantum gap amplification may also be related to fault tolerance of adiabatic computation, a model which has attracted much attention but for which no fault tolerance theory was derived yet. Thirdly, the detectability lemma, and the XY decomposition provide a handle on the structure of local Hamiltonians and their ground states. This may prove useful in the study of those important objects, in particular in the fast growing area of "quantum Hamiltonian complexity" connecting quantum complexity to condensed matter physics.

• MaxMin allocation via degree lower-bounded arborescences
  MohammadHossein Bateni, Moses Charikar and Venkatesan Guruswami
  

  We consider the problem of MaxMin allocation of indivisible goods. There are m items to be distributed among n players. Each player i has a nonnegative valuation p_ij for an item j, and the goal is to allocate each item to a player so as to maximize the minimum total valuation received by a player. There is a large gap in our understanding of this problem. The best known positive result is an \tilde O(\sqrt n)-approximation algorithm, while there is only a factor 2 hardness known.

  Better algorithms are known for the restricted assignment case where each item has exactly one nonzero value for the players. We study the effect of bounded degree of items: each item has a nonzero value for at most B players. We show that essentially, the case B=3 is equivalent to the general case, and give a 4-approximation algorithm for B=2.

  The current algorithmic results for MaxMin Allocation are based on a complicated LP relaxation called the configuration LP. We present a much simpler LP which is equivalent in power to the configuration LP. We focus on a special case of MaxMin Allocation -- a family of instances on which this LP has a polynomially large gap. The technical core of our result for this case comes from an algorithm for an interesting new optimization problem on directed graphs: MaxMinDegree Arboresence, where the goal is to produce an arboresence of large outdegree. We develop an n^ε approximation for this problem that runs in n^O(1/ε) time and obtain a polylogarithmic approximation that runs in quasipolynomial time, using a lift-and-project inspired LP formulation. In fact, we show that our results imply a rounding algorithm for the relaxations obtained by t rounds of the Sherali-Adams hierarchy applied to a natural LP relaxation for the problem. Roughly speaking, the integrality gap of the relaxation obtained from t rounds of Sherali-Adams is at most n^1/t.

• Inaccessible Entropy
  Iftach Haitner, Omer Reingold, Salil Vadhan and Hoeteck Wee
  

  We put forth a new computational notion of entropy, which measures the (in)feasibility of sampling high entropy strings that are consistent with a given protocol. Specifically, we say that the ith round of a protocol (A,B) has accessible entropy at most k, if no polynomial-time strategy A* can generate messages for A such that the entropy of its message in the i’th round has entropy greater than k when conditioned both on prior messages of the protocol and on prior coin tosses of A*. As applications of this notion, we - Give a much simpler and more efficient construction of statistically hiding commitment schemes from arbitrary one-way functions, and - Prove that constant-round statistically hiding commitments are necessary for constructing constant-round zero-knowledge proof systems for NP that remain secure under parallel composition (assuming the existence of one-way functions).

• Hadwiger's Conjecture is Decidable
  Ken-ichi Kawarabayashi and Bruce Reed
  

  The famous Hadwiger's conjecture asserts that every graph with no K_t-minor is (t-1)-colorable. The case t=5 is known to be equivalent to the Four Color Theorem by Wagner, and the case t=6 is settled by Robertson, Seymour and Thomas. So far the cases t ≥ 7 are wide open. In this paper, we prove the following two theorems:

  • There is an O(n²) algorithm to decide Hadwiger's conjecture for the case t.
  • Every minimal counterexample to Hadwiger's conjecture for the case t has at most f(t) vertices for some explicit bound f(t).

  The bound f(t) is at most p^{p^{p^{t}}}, where p=10^{10^{10^{t}}}. Our proofs for both results use the well-known result by Thomassen for 5-list-coloring planar graphs, together with some results (but not the decomposition theorem) of Graph Minors. Concerning the first result, we prove the following stronger theorem:

  For a given graph G and any fixed t, there is an O(n²) algorithm to output one of the following:

  • a (t-1)-coloring of G, or
  • a K_t-minor of G, or
  • a minor H of G of order at most f(t) such that H does not have a K_t-minor nor is (t-1)-colorable.

  The last conclusion implies that H is a counterexample to Hadwiger's conjecture with at most f(t) vertices. The time complexity of the algorithm matches the best known algorithms for 4-coloring planar graphs (the Four Color Theorem), due to Appel and Hakken, and Robertson, Sanders, Seymour and Thomas, respectively. Let us observe that when t=5, the algorithm implies the Four Color Theorem.

• A Unified Framework for Concurrent Security: Universal Composability from Stand-alone Non-malleability
  Huijia Lin, Rafael Pass and Muthuramakrishnan Venkitasubramaniam
  

  We present a unified framework for obtaining Universally Composable (UC) protocols by relying on stand-alone secure non-malleable commitments. Essentially all results on concurrent secure computation—both in relaxed models (e.g., quasi-polynomial time simulation), or with trusted set-up assumptions (e.g., the CRS model, the imperfect CRS model, or the timing model)—are obtained as special cases of our framework. This not only leads to conceptually simpler solutions, but also to improved set-up assumptions, round-complexity, and computational assumptions.

  Additionally, this framework allows us to consider new relaxed models of security: we show that UC security where the adversary is a uniform PPT but the simulator is allowed to be a non-uniform PPT (i.e., essentially, traditional UC security, but with a non-uniform reduction) is possible without any trusted set-up. This gives the first results on concurrent secure computation without set-up, which can be used for securely computing "computationally-sensitive" functionalities (e.g., data-base queries, "proof of work"-protocols, or playing bridge on the Internet).

• Multiplicative updates outperform generic no-regret learning in congestion games
  Robert Kleinberg, Georgios Piliouras and Eva Tardos
  

  We study the outcome of natural learning algorithms in atomic congestion games. Atomic congestion games have a wide variety of equilibria often with vastly differing social costs. We show that in almost all such games, the well-known multiplicative-weights learning algorithm results in convergence to pure equilibria. Our results show that natural learning behavior can avoid bad outcomes predicted by the price of anarchy in atomic congestion games such as the load-balancing game introduced by Koutsoupias and Papadimitriou, which has super-constant price of anarchy and has correlated equilibria that are exponentially worse than any mixed Nash equilibrium.

  Our results identify a set of mixed Nash equilibria that we call weakly stable equilibria. Our notion of weakly stable is defined game-theoretically, but we show that this property holds whenever a stability criterion from the theory of dynamical systems is satisfied. This allows us to show that in every congestion game, the distribution of play converges to the set of weakly stable equilibria. Pure Nash equilibria are weakly stable, and we show using techniques from algebraic geometry that the converse is true with probability 1 when congestion costs are selected at random independently on each edge (from any monotonically parametrized distribution). We further extend our results to show that players can use algorithms with different (sufficiently small) learning rates, i.e. they can trade off convergence speed and long term average regret differently.

• Affiliation Networks
  Silvio Lattanzi and D. Sivakumar
  

  In the last decade, structural properties of several naturally arising networks (the Internet, social networks, the web graph, etc.) have been studied intensively with a view to understanding their evolution. In recent empirical work, Leskovec, Kleinberg, and Faloutsos identify two new and surprising properties of the evolution of many real-world networks: densification (the ratio of edges to vertices grows over time), and shrinking diameter (the diameter reduces over time to a constant). These properties run counter to conventional wisdom, and are certainly inconsistent with graph models prior to their work.

  In this paper, we present the first model that provides a simple, realistic, and mathematically tractable generative model that intrinsically explains all the well-known properties of the social networks, as well as densification and shrinking diameter. Our model is based on ideas studied empirically in the social sciences, primarily on the groundbreaking work of Breiger (1973) on bipartite models of social networks that capture the affiliation of agents to societies.

  We also present algorithms that harness the structural consequences of our model. Specifically, we show how to overcome the bottleneck of densification in computing shortest paths between vertices by producing sparse subgraphs that preserve or approximate shortest distances to all or a distinguished subset of vertices. This is a rare example of an algorithmic benefit derived from a realistic graph model.

  Finally, our work also presents a modular approach to connecting random graph paradigms (preferential attachment, edge-copying, etc.) to structural consequences (heavy-tailed degree distributions, shrinking diameter, etc.).

• Finding, Minimizing, and Counting Weighted Subgraphs
  Virginia Vassilevska and Ryan Williams
  

  For a pattern graph H on k nodes, we consider the problems of finding and counting the number of (not necessarily induced) copies of H in a given large graph G on n nodes, as well as finding minimum weight copies in both node-weighted and edge-weighted graphs. Our results include:

  • The number of copies of an H with an independent set of size s can be computed exactly in O^*(2^s n^k-s+3) time. A minimum weight copy of such an H (with arbitrary real weights on nodes and edges) can be found in O^*(4^s+o(s) n^k-s+3) time. (The O^* notation omits poly(k) factors.) These algorithms rely on fast algorithms for computing the permanent of a k x n matrix, over rings and semirings.
  • The number of copies of any H having minimum (or maximum) node-weight (with arbitrary real weights on nodes) can be found in O(n^wk/3 + n^2k/3+o(1)) time, where w < 2.4 is the matrix multiplication exponent and k is divisible by 3. Similar results hold for other values of k. Also, the number of copies having exactly a prescribed weight can be found within this time. These algorithms extend the technique of Czumaj and Lingas (SODA 2007) and give a new (algorithmic) application of multiparty communication complexity.
  • Finding an edge-weighted triangle of weight exactly 0 in general graphs requires (n^2.5-ε) time for all ε > 0, unless the 3SUM problem on N numbers can be solved in O(N^2-δ) time for some δ > 0. This suggests that the edge-weighted problem is much harder than its node-weighted version.
  
  
• Online and Stochastic Survivable Network Design
  Anupam Gupta, Ravishankar Krishnaswamy and R. Ravi
  

  Consider the edge-connectivity survivable network design problem: given a graph G = (V,E) with edge-costs, and edge-connectivity requirements r_ij ∈ Z_{≥ 0} for every pair of vertices i, j ∈ V, find an (approximately) minimum-cost network that provides the required connectivity. While this problem is known to admit excellent approximation algorithms in the offline case, no algorithms are known for this problem in the online setting. (In fact, there are instances where for a input sequence of length L = O(log n), one can show a lower bound of Ω(L), in contrast to the 1-connectivity case where Θ(log L)-competitive algorithms exist.) In this paper, we give a randomized O(r_max log³ n)-competitive online algorithm for this edge-connectivity network design problem, where r_max = max_ij r_ij. Apart from being the first results in this direction, we feel that our techniques are non-standard and interesting in their own right: somewhat surprisingly, we use the standard embeddings of graphs into their random subtrees (i.e., into singly-connected subgraphs) as a crucial step to get algorithms for k-connectivity.

  Our results for the online problem give us approximation algorithms that admit strict cost-shares with the same strictness value. This, in turn, implies approximation algorithms for (a) the rent-or-buy version and (b) the (two-stage) stochastic version of the edge-connected network design problem with independent arrivals. These are the first approximation algorithms known for these versions of network design problems with higher connectivity requirements. (The previous results known are either for simple connectivity, or for k-connectivity where all the demands share a common root note.)

  We improve our results for the case when the underlying graph is complete and the edge-costs are metric (i.e., satisfy the triangle inequality). For this case, we can give O(1)-strict cost shares, which gives constant-factor rent-or-buy and stochastic algorithms for these instances.

• Reconstruction for the Potts Model
  Allan Sly
  

  The reconstruction problem on the tree plays a key role in several important computational problems. Deep conjectures in statistical physics link the reconstruction problem to properties of random constraint satisfaction problems including random k-SAT and random colourings of random graphs. At this precise threshold the space of solutions is conjectured to undergo a phase transition from a single collected mass to exponentially many small clusters at which point local search algorithm must fail. In computational biology the reconstruction problem is central in phylogenetics. It has been shown [Mossel '04] that solvability of the reconstruction problem is equivalent to phylogenetic reconstruction with short sequences for the binary symmetric model.

  Rigorous reconstruction thresholds, however, have only been established in a small number of models. We confirm conjectures made by Mezard and Montanari for the Potts models proving the first exact reconstruction threshold in a non-binary model establishing the so-called Kesten-Stigum bound for the 3-state Potts model on regular trees of large degree. We further establish that the Kesten-Stigum bound is not tight for the q-state Potts model when q ≥ 5. Moreover, we determine asymptotics for these reconstruction thresholds.

• Approximating Edit Distance in Near-Linear Time
  Alexandr Andoni and Krzysztof Onak
  

  We show how to compute the edit distance between two strings of length n up to a factor of 2^{O(\sqrt{log n} log log n)} in n^{1+o(1)} time. This is the first sub-polynomial approximation algorithm for this problem that runs in near-linear time, improving on the state-of-the-art n^{1/3+o(1)} approximation. Previously, approximation of 2^{O(\sqrt{log n log log n})} was known only for embedding edit distance into l₁, and it is not known if that embedding can be computed in less than n² time.

• Universally Utility-Maximizing Privacy Mechanisms
  Arpita Ghosh, Tim Roughgarden and Mukund Sundararajan
  

  A mechanism for releasing information about a statistical database with sensitive data must resolve a trade-off between utility and privacy. Informally, publishing fully accurate information maximizes utility while minimizing privacy, while publishing random noise accomplishes the opposite. Formally, privacy can be rigorously quantified using the framework of differential privacy, which requires that a mechanism's output distribution is nearly the same (in a strong sense) whether or not a given database row is included or excluded. Thus far, (dis)utility has typically been quantified via the expected error of a (randomly perturbed) response to a query.

  In this paper, we pursue much stronger and more general utility guarantees. Just as differential privacy guarantees protection against every potential attacker, independent of its side information, we seek a mechanism that guarantees near-optimal utility to every potential user, independent of its side information. Formally, we model the side information of a potential user as a prior distribution over query results. An interaction between such a user and a mechanism induces a posterior distribution -- the utility of the mechanism for this user is defined as the accuracy of this posterior as quantified via a user-specific loss function. A differentially private mechanism M is (near-)optimal for a given user u if u derives (almost) as much utility from M as from any other differentially private mechanism.

  We prove that for each fixed counting query and differential privacy level, there is a geometric mechanism M* — a discrete variant of the well-studied Laplace mechanism — that is simultaneously utility-maximizing for every possible user, subject to the differential privacy constraint. This is an extremely strong utility guarantee: every potential user u, no matter what its side information and loss function, derives as much utility from M* as from interacting with a differentially private mechanism M_u that is optimally tailored to u. The first part of our proof characterizes the utility-maximizing differentially private mechanism for a fixed but arbitrary user in terms of a basic feasible solution to a linear program with constraints that encode differential privacy. The second part shows that all of the relevant vertices of this polytope (ranging over all possible users) are derivable from the geometric mechanism via suitable remappings of its range.

• Integrality Gaps for Sherali-Adams Relaxations
  Moses Charikar, Konstantin Makarychev and Yury Makarychev
  

  We prove strong lower bounds on integrality gaps of Sherali--Adams relaxations for MAX CUT, Vertex Cover, Sparsest Cut and other problems. Our constructions show gaps for Sherali-Adams relaxations that survive n^δ rounds of lift and project. For MAX CUT and Vertex Cover, these show that even n^δ rounds of Sherali-Adams do not yield a better than (2-ε) approximation.

  The main combinatorial challenge in constructing these gap examples is the construction of a fractional solution that is far from an integer solution, but yet admits consistent distributions of local solutions for all small subsets of variables. Satisfying this consistency requirement is one of the major hurdles to constructing Sherali-Adams gap examples. We present a modular recipe for achieving this, building on previous work on metrics with a local-global structure. We develop a conceptually simple geometric approach to constructing Sherali-Adams gap examples via constructions of consistent local SDP solutions.

  This geometric approach is surprisingly versatile. We construct Sherali-Adams gap examples for Unique Games based on our construction for MAX CUT together with a parallel repetition like procedure. This in turn allows us to obtain Sherali-Adams gap examples for any problem that has a Unique Games based hardness result (with some additional conditions on the reduction from Unique Games). Using this, we construct (2-ε) gap examples for Maximum Acyclic Subgraph that rules out any family of linear constraints with support at most n^δ.

• On Oblivious PTAS for Nash Equilibrium
  Constantinos Daskalakis and Christos H. Papadimitriou
  

  If a class of games is known to have a Nash equilibrium with probability values that are either zero or Omega(1) — and thus with support of bounded size — then obviously this equilibrium can be found exhaustively in polynomial time. Somewhat surprisingly, we show that there is a PTAS for the class of games whose equilibria are guaranteed to have small — O(1/n) — values, and therefore large — Omega(n) — supports. We also point out that there is a PTAS for games with sparse payoff matrices, a family for which the exact problem is known to be PPAD-complete [Chen,Deng,Teng '06]. Both algorithms are of a special kind that we call oblivious: The algorithm just samples a fixed distribution on pairs of mixed strategies, and the game is only used to determine whether the sampled strategies comprise an ε-Nash equilibrium; the answer is "yes" with inverse polynomial probability (in the second case, the algorithm is actually deterministic). These results bring about the question:Is there an oblivious PTAS for finding a Nash equilibrium in general games? We answer this question in the negative; our lower bound comes close to the quasi-polynomial upper bound of [Lipton Markakis, Mehta '03].

  Another recent PTAS for anonymous games [Daskalakis, Papadimitriou '07, '08, Daskalakis '08] is also oblivious in a weaker sense appropriate for this class of games (it samples from a fixed distribution on unordered collections of mixed strategies), but its running time is exponential in 1/ε. We prove that any oblivious PTAS for anonymous games with two strategies and three player types must have (1 / ε^α) in the exponent of the running time for some alpha >= 1/3, rendering the algorithm in [Daskalakis '08] (which works with any bounded number of player types) essentially optimal within oblivious algorithms. In contrast, we devise a poly(n)*(1/ ε)^{O(log{2}(1/ε))} non-oblivious PTAS for anonymous games with two strategies and any bounded number of player types. The key idea of our algorithm is to search not over unordered sets of mixed strategies, but over a carefully crafted set of collections of the first O(log(1/ ε)) moments of the distribution of the number of players playing strategy 1 at equilibrium. The algorithm works because of a probabilistic result of more general interest that we prove: the total variation distance between two sums of independent indicator random variables decreases exponentially with the number of moments of the two sums that are equal, independent of the number of indicators.

• Fully Homomorphic Encryption Using Ideal Lattices
  Craig Gentry
  

  We propose a fully homomorphic encryption scheme -- i.e., a scheme that would allow one to evaluate circuits over encrypted data without access to the decryption function. First, we provide a general preliminary result -- that, to construct an encryption scheme that permits evaluation of arbitrary circuits, it suffices to construct an encryption scheme that can evaluate (slightly augmented versions of) its own decryption circuit; we call a scheme that can evaluate its (augmented) decryption circuit bootstrappable. Next, we provide a bootstrappable public key encryption scheme using ideal lattices.

  Intuitively, ideal lattices are well-suited to construct bootstrappable encryption for two reasons. First, lattice-based cryptosystems typically have decryption algorithms with low circuit complexity, often dominated by an inner product computation that is in NC1. By contrast, exponentiation as used in RSA or ElGamal decryption is not even known to be in NC. Second, we show that ideal lattices provide both additive and multiplicative homomorphisms (modulo a public-key ideal in a polynomial ring that is represented as a lattice), as needed to evaluate general circuits.

  Unfortunately, our initial scheme is not quite bootstrappable -- i.e., the depth that the scheme can correctly evaluate can be logarithmic in the lattice dimension, just like the depth of the decryption circuit, but the latter is greater than the former. However, we show how to modify the scheme to reduce the depth of the decryption circuit, and thereby obtain a bootstrappable encryption scheme, without reducing the depth that the scheme can evaluate. Abstractly, we accomplish this by enabling the encrypter to start the decryption process, leaving less work for the decrypter, much like the server leaves less work for the decrypter in a server-aided cryptosystem. In more detail, we include a set of vectors in the public key that includes a hidden low-weight subset that is related to the secret key. This allows us to re-express decryption as a low-weight subset sum rather than a full matrix-vector product, where the former requires a circuit of lower depth.

• Random walks on polytopes and an affine interior point method for linear programming.
  Ravi Kannan and Hariharan Narayanan
  

  Let P be a polytope in Rⁿ defined by m linear inequalities. We give a new Markov Chain algorithm to draw a nearly uniform sample from P; the running time is strongly polynomial (this is the first algorithm with this property) given a "central" starting point x₀. If s is the supremum over all chords \overline{pq} passing through x₀ of (|p-x₀|)/(|q-x₀|) and ε is an upper bound on the total variation distance from the uniform we want, it is sufficient to take O(m n(n log (s m) + log (1/ε))) steps of the random walk. We use this result to design an affine interior point algorithm that does a single random walk to solve linear programs approximately. More precisely, suppose Q = {z | Bz ≤ \one} contains a point z such that c^T z ≥ d and r := sup_{z ∈ Q} ||Bz|| + 1, where B is an m × n matrix. Then, after τ = O(mn (n ln (mr/ε) + ln (1/δ))) steps, the random walk is at a point x_τ such that c^T x_τ ≥ d(1-ε) with probability greater than 1-δ. The fact that this algorithm has polynomial run-time is notable since the corresponding deterministic affine algorithm analyzed by Dikin has no known polynomial guarantees.

• When and How Can Data be Efficiently Released with Privacy?
  Cynthia Dwork, Moni Naor, Omer Reingold, Guy Rothblum and Salil Vadhan
  

  We consider private data analysis in the setting in which a trusted and trustworthy curator, having obtained a large data set containing private information, releases to the public a "sanitization" of the data set that simultaneously protects the privacy of the individual contributors of data and offers utility to the data analyst. The sanitization may be in the form of an arbitrary data structure, accompanied by a computational procedure for determining approximate answers to queries on the original data set, or it may be a "synthetic data set" consisting of data items drawn from the same universe as items in the original data set; queries are carried out as if the synthetic data set were the actual input. In either case the process is non-interactive; once the sanitization has been released the original data and the curator play no further role.

  Blum et al. (STOC `08) showed the remarkable result that, for any any set X of potential data items and any "concept" class C of functions f : X → {0,1}, the exponential mechanism of McSherry and Talwar (FOCS `07) can be used to (inefficiently) generate a synthetic data set that maintains approximately correct fractional counts for all concepts in C, while ensuring a strong privacy guarantee.

  In this work we investigate the computational complexity of non-interactive privacy mechanisms, mapping the boundary between feasibility and infeasibility. Let \secp be a computation parameter. We show

  • \label{alg} When |C| and |X| are both polynomial in \secp, it is possible to efficiently (in \secp) and privately construct synthetic data sets maintaining approximately correct counts, even when the original data set is very small (roughly, O(2^{\sqrt{log |C|}} log |X|)).
  • When either |C| or |X| is superpolynomial in \secp there exist distributions on data sets and a choice of C for which, assuming the existence of one-way functions, there is no efficient private construction of a synthetic data set maintaining approximately correct counts.
  • Turning to the potentially easier problem of privately generating a data structure from which it is possible to approximate counts, there is a tight connection between hardness of sanitization and the existence of traitor tracing schemes, a method of content distribution in which (short) key strings are assigned to subscribers in a way that, given any useful "pirate" key string constructed by a coalition of malicious subscribers, it is possible to identify at least one colluder. Using known schemes, we obtain a distribution on databases and a concept class permitting inefficient sanitization (via Blum et al.), but for which no efficient sanitization is possible (under certain complexity assumptions).

  Our algorithmic results give for the first time insight into the value of synthetic data sets beyond that of general data structures.

• On Cryptography with Auxiliary Input
  Yevgeniy Dodis, Yael Tauman Kalai and Shachar Lovett
  

  We study the question of designing cryptographic schemes which are secure even if an arbitrary function f(sk) of the secret key is leaked, as long as the secret key sk is still (exponentially) hard to compute from this auxiliary input. We note that this assumption on the auxiliary input is weaker than the more traditional assumption that sk has high min-entropy, and applies even to situations where f(sk) information-theoretically determines the entire secret key sk.

  As our main result, we construct CPA/CCA secure symmetric encryption schemes that remain secure with exponentially hard-to-invert auxiliary input. We give several applications of such schemes. (1) We construct an average-case obfuscator for the class of point functions, which remains secure with exponentially hard-to-invert auxiliary input, and is reusable. (2) We construct a reusable and robust extractor that remains secure with exponentially hard-to-invert auxiliary input.

  Our results rely on the existence of trapdoor permutations, and on a new cryptographic assumption, which is a generalized version of the learning parity-with-noise (LPN) assumption. We stress that this assumption is "efficiently falsifiable" and does not quantify over all auxiliary functions f.

• Polynomial-time Theory of Matrix Groups
  László Babai, Robert M. Beals and Ákos Seress
  

  It has been known since 1980 that basic manipulation of permutation groups, given by a list of generators, can be performed in polynomial time. In contrast, for matrix groups over finite fields, these problems present great difficulties. For starters, the one-by-one case requires factoring integers and discrete logarithms; so we cannot hope to avoid these obstacles in the general case. After 25 years of increasingly intensive study by the theoretical computer science and computational group theory communities, we have finally arrived at a definitive result on the basic questions: If G is a matrix group over a finite field of odd order then the order of G and membership in G can be determined in randomized polynomial time, using oracles for factoring and discrete log. Previously similar results were known for solvable matrix groups only (Luks, FOCS 1992). We are also able to claim that the obstacles to polynomial-time computability are purely "abelian:" If a matrix group G has no abelian normal subgroups then we can determine the order of G, and name all of its composition factors, in genuine randomized polynomial time (no oracles). This yields a natural problem in BPP not known to be in RP or coRP.

  The overall procedure combines new elementary algorithms with a large body of previous work, algorithmic as well as group theoretic. Some of the ingredients depend on detailed knowledge of the classification of finite simple groups. However, no such knowledge will be required for reading this paper.

• Message Passing Algorithms and Improved LP Decoding
  Sanjeev Arora, Constantinos Daskalakis and David Steurer
  

  Linear programming decoding for low-density parity check codes (and related domains such as compressed sensing) has received increased attention over recent years because of its practical performance (coming close to that of iterative decoding algorithms) and its amenability to finite-blocklength analysis. Several works starting with the work of Feldman et al. showed how to analyze LP decoding using properties of expander graphs. This line of analysis works for only low error rates, about a couple of orders of magnitude lower than the empirically observed performance. It is possible to do better for the case of random noise, as shown by Daskalakis et al. and Koetter and Vontobel.

  Building on work of Koetter and Vontobel, we obtain a novel understanding of LP decoding which allows us to establish a 0.047-fraction of correctable errors for rate-1/2 codes; this comes very close to the performance of iterative decoders and significantly higher than the best previously noted correctable bit error rates. Unlike other techniques, our analysis considers directly the primal linear program, and works by exploiting an explicit connection between LP decoding, Sherali-Adams relaxations, and message passing algorithms.

• A Fast and Efficient Algorithm for Low-rank Approximation of a Matrix
  Nam H. Nguyen, Thong T. Do and Trac D. Tran
  

  Low-rank matrix approximation is to find a rank k version of a m × n matrix A such that it is as "close" to the best SVD approximation version A_k of A at the same rank level as possible. Previous approaches approximate matrix A by non-uniformly adaptive sampling some columns (or rows) of A, hoping that this subset of columns contain enough information about A. The sub-matrix is then used for the approximation process. However, these approaches seem to be slow due to the complexity in the adaptive sampling. In this paper, we propose a fast and efficient algorithm which at first preprocess matrix A in order to spread out information (energy) of every columns (or rows) of A, then uniformly randomly select some of its columns (or rows). Finally, a rank-k approximation is generated from the row space of these selected set. The preprocessing step is performed by uniformly randomizing signs of entries of A and transforming all columns of A by an orthonormal matrix F with fast implementation (e.g. Hadamard, FFT, DCT ...) . Our main contribution is summarized as follows

  • We show that by uniformly selecting d rows of the preprocessed matrix with d = O((1/η) k log (2m/β)), we guarantee the relative Frobenius norm error approximation: (1 + η) ||A - A_k||_F with probability at least 1 - 5β.
  • With d above, we establish a spectral norm error approximation: (2 + \sqrt{2m/d}) ||A - A_k||₂ with probability at least 1 - 2β.
  • The algorithm requires 2 passes over the data and runs in time O(mn log d + (m+n) d²) which, as far as our knowledge, is one of the fastest algorithms when the matrix A is dense.
  
  
• Short seed extractors against quantum storage
  Amnon Ta-Shma
  

  In the classical privacy amplification problem Alice and Bob share information that is only partially secret towards an eavesdropper Charlie. Their goal is to distill this information to a shorter string that is completely secret. The classical privacy amplification problem can be solved almost optimally using extractors. An interesting variant of the problem, where the eavesdropper Charlie is allowed to keep quantum information rather than just classical information, was introduced by Konig, Maurer and Renner. In this setting, the eavesdropper Charlie may entangle himself with the input (without changing it) and the only limitation Charlie has is that it may keep at most b qubits of storage. A natural question is whether there are classical extractors that are good even against quantum storage.

  Recent work has shown that some classical extractors miserably fail against quantum storage. At the same time, it was shown that some other classical extractors work well even against quantum storage, but all these extractors had a large seed length that was either as large as the extractor output, or as large as the quantum storage available to the eavesdropper.

  In this paper we show that a modified version of Trevisan's extractor is good even against quantum storage, thereby giving the first such construction with logarithmic seed length. The technique we use is a combination of Trevisan's approach of constructing an extractor from a black-box pseudorandom generator, together with locally list-decodable codes and previous work done on quantum random access codes.