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
stoc2009local@cs.umd.edu.
 Smallsize εNets for AxisParallel 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 axisparallel rectangular ranges. The same bound holds for points in the plane with "fat" triangular ranges, and for point sets in 3space and axisparallel boxes; these are the first known nontrivial 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.
 Nonmonotone 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 NPhard. In this paper, we give the first constantfactor approximation algorithms for maximizing any nonnegative submodular function subject to multiple matroid or nknapsack constraints. We emphasize that our results are for nonmonotone 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 k1}+ε} 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 kmedian and kmean 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 LinearInvariant 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 linearinvariant 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 nonhomogeneous 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 wellstudied 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 stateoftheart 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 mrelaxed pcoloring the vertices are colored with p colors so that each vertex has up to m neighbors with the same color. We show that an mrelaxed pcoloring 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 BenSasson, Swastik Kopparty
An affine disperser over F_{2}^{n} for sources of dimension d is a function f: F_{2}^{n} → F_{2} such that for any affine space S ⊆ F_{2}^{n} of dimension at least d, we have {f(s) : s ∈ S} = F_{2}. 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 sumproduct 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 NPhard. Bulatov and Jeavons reformulated this conjecture in terms of the properties of the algebra Pol(F), where the latter is the collection of those mary 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 NPhard 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 HellNesetril theorem, which states that for a simple connected undirected graph H, the problem csp(H) is NPhard if and only if H is nonbipartite.
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 kpebble 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 wellbehaved, and that there exists a probabilistic Turing machine that exactly learns all well behaved c log(n)DNF formula. This is the ﬁrst 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 ProximityOblivious Testers.
While proximityoblivious 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 constantquery proximityoblivious testers in the two standard models (i.e., the adjacency matrix and the boundeddegree models). Furthermore, we show that constantquery proximityoblivious testers do not exist for many easily testable properties, and that even when proximityoblivious 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
YiKai Liu
The curvelet transform is a directional wavelet transform over R^{n}, 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 singleshot measurement procedure for approximately finding the center of a ball in R^{n}, given a quantumsample over the ball; and, a quantum algorithm for finding the center of a radial function over R^{n}, given oracle access to the function. I conjecture that algorithm (1) succeeds with constant probability using 1 quantumsample, 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 speedup. 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 ReRanking
Yossi Azar, Iftah Gamzu and Xiaoxin Yin
One of the most fundamental problems in web search is how to rerank result web pages based on user logs. Most traditional models for reranking 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 reranking 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 rerank 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 nonnegative 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 nonincreasing. This case is a generalization of the wellknown minsum set cover problem. We extend the techniques of Feige, Lovász and Tetali (Algorithmica '04), and present an algorithm achieving 4approximation. The second case is when the profile vector of each user type is nondecreasing. This case generalizes the minimum latency set cover problem. We devise a LPbased algorithm that attains 2approximation. In particular, this result improves the eapproximation 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 kCNF 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 nonconstructive 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 kCNF 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 nonconstructive versions of the Local Lemma and can therefore be considered an alternative, constructive proof of it.
 Holant Problems and Counting CSP
JinYi 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.
 3Query 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 3query LDC with subexponential 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 3query 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^{r1} n}))). The main ingredient in our construction is the existence of superpolynomial size setsystems with restricted intersections [Grolmusz00] which holds only over composite numbers.
 FaultTolerant 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 nvertex graph G=(V,E) and an integer k ≥ 1, the subgraph H=(V,E'), E'⊆ E, is a spanner of stretch k (or, a kspanner) 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 (2k1)spanner of size O(n^{1+1/k}), and this sizestretch 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 fvertex fault tolerant kspanner 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 fvertex 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 fvertex fault tolerant (2k1)spanner whose size is O(f^{3} k^{f+1} ⋅ n^{1+1/k} log^{11/k}n). 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 fedge fault tolerant spanners (defined analogously). We present an fedge fault tolerant 2k1 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.
 BitProbe 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 informationtheoretic minimum log_{2} S, while answering various queries by probing few bits. Our main results are:
 We prove that, to represent n ternary elements t ∈ \zot^{n} in terms of binary elements \zo^{u} while accessing a single element t_{i} ∈ \zot by nonadaptively probing q bits, one needs u ≥ (log_{2} 3)n + n/2^{q^{O(1)}}. This matches a recent, exciting work by Patrascu (FOCS 2008) who gives a representation where u ≤ (log_{2} 3)n + n/2^{q^{Ω(1)}} (also nonadaptive).
 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 nonadaptively probing q bits: one needs u ≥ log_{2} \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 nonnegative 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^{2}) that has an O(1) query time, and an \widetilde{O}(n^{2}\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^{2}) space requirement, but it has an improved construction time of \widetilde{O}(mn), and it is deterministic. Note that O(1) query, O(n^{2}) 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 informationtheoretic 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 informationtheoretic 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 twoargument 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 nontrivial lower bounds on it) imply proving circuit lower bounds for some corresponding problems. Such connections between circuit complexity and communication complexity were known before (KarchmerWigderson 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. independentset" 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 mwise 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 closeby lowrank codewords. For decoding linear transformatons, using rankreduction 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.
 NonMalleability Amplification
Huijia Lin and Rafael Pass
We show a technique for amplifying commitment schemes that are nonmalleable with respect to identities of length t, into ones that are nonmalleable with respect to identities of length Ω(2^{t}), while only incurring a constant overhead in roundcomplexity. As a result we obtain a construction of O(1)^{log* n}round (i.e., "essentially" constantround) nonmalleable commitments from any oneway function, and using a blackbox 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^{2}) 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 14\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=SL of S such that at least a 1O(\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^{3}) 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 listdecodable codes
Venkatesan Guruswami
Algebraic codes that achieve list decoding capacity were recently constructed by a careful "folding" of the ReedSolomon code. The "lowdegree" 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 ArtinFrobenius automorphism at primes in Galois extensions. Using this approach, we construct new folded algebraicgeometric 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 ReedSolomon 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 ReedSolomon 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 bruteforce search) binary concatenated codes for list decoding up to the Zyablov radius.
 The Extended BGSimulation and the Characterization of tResiliency
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 tresiliently?
The HerlihyShavit condition characterize solvability when t=n1, i.e. they characterized waitfree solvability. The BorowskyGafni (BG) simulation characterizes tresilient solvability by reducing the question to waitfree 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 BGsimulation to result in the ExtendedBGsimulation, an extension that yields a full characterization of tresilient solvability: A task T on n processors p_{0},...,p_{n1} is solvable tresiliently iff all tasks T' on t+1 simulators s_{0},...s_{t} created as follows are waitfree 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 tuplepair 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 tresiliently weak renaming with n+(t+1)2 names, where n>1 and 0<t<n, iff weakrenaming on t+1 processors is waitfree solvable with 2t names. Second, we reproduce the result that the solvability nprocessors tasks, tresiliently, for t>1 and n>2, is undecidable, by a simple reduction to the undecidability of the waitfree solvability of 3processors 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 volumebiased 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 NPcomplete in [Vardy97]. In [DumerMi03], the gap version of the problem was shown to be NPhard 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{ba} when the logarithm x∈[a,b], and (2+o(1))\sqrt{ba} 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 ConstantTime Approximation Algorithm for Maximum Matchings
Yuichi Yoshida, Masaki Yamamoto and Hiro Ito
This paper studies approximation algorithms for problems on degreebounded 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 twosided error. On the contrary, it also shows that every onesided 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 ChekuriGoelKhannaKumar 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 kwise 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_{2} t^{2} 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 kwise independent distribution and, for some c>0, a random predicate accepting ct^{2}/ log t input vectors is nontrivially 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 zeroone law for firstorder logic on random graphs says that for every firstorder 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_{0}, a_{1}, 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_{1}, ..., 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 RazborovSmolensky 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 privacypreserving parameter estimation. Privacypreserving 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 ProposeTestRelease (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 worstcase 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 regretminimization). 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 worstcase price of anarchy for pure Nash equilibria necessarily implies the exact same worstcase upper bound for mixed Nash equilibria, correlated equilibria, and the average objective function value of regretminimizing 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 bestresponse 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 worstcase examples for the POA.
 On the convergence of regret minimization dynamics in concave games
Eyal EvenDar, Yishay Mansour and Uri Nadav
We study a general subclass of concave games, which we call socially concave games. We show that if each player follows any noexternal 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 sociallyconcave 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 sociallyconcave, 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 kXOR, 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 kCSP 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 kCSP_{q} is at most kq(q1)/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 lcoloring for the SDP obtained by Ω(n) rounds of Lasserre, even though the actual chromatic number is Ω(2^{l/2}/l^{2}). 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 NPhardness results known even under the Unique Games Conjecture.
 A ConstantFactor 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 constantfactor approximations only for some special cases of this problem.
We resolve the status of the stochastic Steiner Forest problem and give a constantfactor primaldual based approximation algorithm. Since the previouslysolved special cases had yielded very complicated primaldual algorithms, our solution heavily relies on techniques to reduce the complexity of the dualgrowth 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 nonsmooth (but wellcontrolled fashion) to generate a constantfactor 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 GuptaNewmanRabinovichSinclair (GNRS) L_{1} embedding conjecture to a pair of manifestly simpler conjectures. The GNRS conjecture characterizes all graphs that have an O(1)approximate multicommodity maxflow/mincut 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 pathwidthk metrics embed into L_{1} 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 wellknown planar embedding conjecture, and (2) a conjecture about embeddings of ksums of graphs.
 Resilient KnowledgeBased 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 nonBayesian setting). Our mechanism also is computationally efficient, and preserves the players' privacy to an unusual extent.
 PublicKey Cryptosystems from the WorstCase Shortest Vector Problem
Chris Peikert
We construct publickey cryptosystems that are secure assuming the worstcase hardness of approximating the length of a shortest nonzero vector in an ndimensional lattice to within a small poly(n) factor. Prior cryptosystems with worstcase 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 ciphertextsecure system that has a much simpler description and tighter underlying worstcase approximation factor than prior constructions.
 OneRound Authenticated Key Agreement from Weak Secrets
Yevgeniy Dodis and Daniel Wichs
We study the question of informationtheoretically secure authenticated key agreement from weak secrets. In this setting, Alice and Bob share a nbit secret W, which might not be uniformly random but the adversary has at least k bits of uncertainty about it (formalized using conditional minentropy). 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 noninteractive (singlemessage) 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 twomessage (i.e, oneround!) 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 "nonmalleable" 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 oneround 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.
 TwiceRamanujan 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 Satisfiable3CSPs
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 sapproximation for satisfiable 3bit constraint satisfaction problems ("3CSPs") is NPhard. 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 dto1 Conjecture. Formally, we prove that if Khot's dto1 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 MaxNTW ("Not Two") instances and confirms Zwick's conjecture [Zwi98] that the 5/8approximation algorithm for satisfiable 3CSPs is optimal.
 NearPerfect 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 timestep 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 timesteps on all graphs. For the important case of expanders we can even achieve a constant discrepancy in O(log n (log log n)^{3}) rounds. This is optimal up to log log nfactors while the best previous algorithms in this setting either require Ω(log^{2} 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 surfaceembedded graphs in nearlinear 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^{7} n log^{2} n log^{2} 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 surfaceembedded 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 minimumcost 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 nearoptimal space bounds in the streaming model for linear algebra problems that include estimation of matrix products, linear regression, lowrank 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^{T}A, where S is a sign matrix.
Our results include the following upper and lower bounds on the bits of space needed for 1pass 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^{T}BC_{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 Axb_{2} ≤ (1+ε)min_{x' ∈ Rd} Ax'b_{2}. We show that Θ(d^{2}ε^{1} log (nd)) space is needed.
 (Rankk Approximation) Find matrix \tA_{k} of rank no more than k, so that A\tA_{k}_{F} ≤ (1+ε) AA_{k}_{F}, where A_{k} is the best rankk approximation to A. Our lower bound is Ω(kε^{1}(n+d) log (nd)) space, and we give a onepass algorithm matching this when A is given rowwise or columnwise. For general updates, we give a onepass algorithm needing O(kε^{2}(n + d/ε^{2}) log (nd)) space. We also give upper and lower bounds for multiplepass algorithms, and a sketching analog of the CUR decomposition.
 Testing Juntas Nearly Optimally
Eric Blais
A function on n variables is called a kjunta 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 kjunta or is “far” from being a kjunta 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 onesided error for testing juntas. Notably, the new algorithm is a valid junta tester under very general conditions: it holds for functions with arbitrary ﬁnite 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 kjunta, then f is “far” from being determined by k parts in a random partition. The structural lemma is proved using the EfronStein decomposition method.
 Lineartime Approximation Schemes for the GaleBerlekamp Game and Related Minimization Problems
Marek Karpinski and Warren Schudy
We design a linear time approximation scheme for the GaleBerlekamp 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 ktuples (f(x_{1}),...,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 "listdecoding" regime. In particular, they give a 2query 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 3query 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 2query 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 2query PCP of alphabet Σ of size 2^{t} and soundness error 1δ, Raz's (kfold) parallel repetition theorem (and Holenstein's proof) [Razparallel,Hol07] yields a new 2query PCP with soundness error exp((δ^{3}k)/t), with the dependence on the alphabet size essential [FeigeVerbitsky]. Our techniques yield a 3query 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 oneway functions exist, MAEXP ot ⊂ P/poly, etc., are provable from Arithmetic Checkability. (iii) Many of the open complexity questions (shown to require nonalgebrizing 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 polylength queries is contained in MIP^{O}, mirroring a similar result from [AW08]).
 Efficient discretetime simulations of continuoustime quantum query algorithms
Richard Cleve, Daniel Gottesman, Michele Mosca, Rolando Somma and David YongeMallo
Background: Most quantum algorithms can be cast in a query model, where some unknown function is computed by a blackbox, 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 continuoustime 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 continuoustime query model can be efficiently simulated by a quantum algorithm in the discrete query model. We show that any quantum algorithm in the continuoustime 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 discretetime query model immediately carries over to a lower bound of Omega(T loglog T/log T) in the continuoustime query model.
 Tight Lower Bounds for Greedy Routing in Uniform Small World Rings
Martin Dietzfelbinger and Philipp Woelfel
We consider an augmented ringbased network with vertices 0,...,n1, 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,...,n1} at random according to a probability distribution mu over all subsets C of {1,2,...,n1} with 1,n1 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,n1}.
Motivated by Kleinberg's (2000) Small World Graph model, and packet routing strategies for peertopeer 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 "onesided case", where packets can travel only in one direction through the interval between starting and target node, and the "twosided 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 twosided 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 twosided and the onesided case we prove a lower bound of Omega((log n)^{2}/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.
 SheraliAdams Relaxations of the Matching Polytope
Claire Mathieu and Alistair Sinclair
We study the SheraliAdams liftandproject 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 SheraliAdams rounds until the integer polytope is reached) is exactly 2d1.
 Mixing time for the solidonsolid model
Fabio Martinelli and Alistair Sinclair
We analyze the mixing time of a natural local Markov chain (the Glauber dynamics) on configurations of the solidonsolid 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 noncommuting 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 lowerbounded 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 4approximation 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 liftandproject inspired LP formulation. In fact, we show that our results imply a rounding algorithm for the relaxations obtained by t rounds of the SheraliAdams hierarchy applied to a natural LP relaxation for the problem. Roughly speaking, the integrality gap of the relaxation obtained from t rounds of SheraliAdams 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 polynomialtime 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 oneway functions, and  Prove that constantround statistically hiding commitments are necessary for constructing constantround zeroknowledge proof systems for NP that remain secure under parallel composition (assuming the existence of oneway functions).
 Hadwiger's Conjecture is Decidable
Kenichi Kawarabayashi and Bruce Reed
The famous Hadwiger's conjecture asserts that every graph with no K_{t}minor is (t1)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^{2}) 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 wellknown result by Thomassen for 5listcoloring 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^{2}) algorithm to output one of the following:
 a (t1)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 (t1)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 4coloring 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 Standalone Nonmalleability
Huijia Lin, Rafael Pass and Muthuramakrishnan Venkitasubramaniam
We present a unified framework for obtaining Universally Composable (UC) protocols by relying on standalone secure nonmalleable commitments. Essentially all results on concurrent secure computation—both in relaxed models (e.g., quasipolynomial time simulation), or with trusted setup 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 setup assumptions, roundcomplexity, 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 nonuniform PPT (i.e., essentially, traditional UC security, but with a nonuniform reduction) is possible without any trusted setup. This gives the first results on concurrent secure computation without setup, which can be used for securely computing "computationallysensitive" functionalities (e.g., database queries, "proof of work"protocols, or playing bridge on the Internet).
 Multiplicative updates outperform generic noregret 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 wellknown multiplicativeweights 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 loadbalancing game introduced by Koutsoupias and Papadimitriou, which has superconstant 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 gametheoretically, 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 realworld 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 wellknown 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, edgecopying, etc.) to structural consequences (heavytailed 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 nodeweighted and edgeweighted 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^{ks+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^{ks+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) nodeweight (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 edgeweighted 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 edgeweighted problem is much harder than its nodeweighted version.
 Online and Stochastic Survivable Network Design
Anupam Gupta, Ravishankar Krishnaswamy and R. Ravi
Consider the edgeconnectivity survivable network design problem: given a graph G = (V,E) with edgecosts, and edgeconnectivity requirements r_{ij} ∈ Z_{≥ 0} for every pair of vertices i, j ∈ V, find an (approximately) minimumcost 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 1connectivity case where Θ(log L)competitive algorithms exist.) In this paper, we give a randomized O(r_{max} log^{3} n)competitive online algorithm for this edgeconnectivity 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 nonstandard and interesting in their own right: somewhat surprisingly, we use the standard embeddings of graphs into their random subtrees (i.e., into singlyconnected subgraphs) as a crucial step to get algorithms for kconnectivity.
Our results for the online problem give us approximation algorithms that admit strict costshares with the same strictness value. This, in turn, implies approximation algorithms for (a) the rentorbuy version and (b) the (twostage) stochastic version of the edgeconnected 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 kconnectivity where all the demands share a common root note.)
We improve our results for the case when the underlying graph is complete and the edgecosts are metric (i.e., satisfy the triangle inequality). For this case, we can give O(1)strict cost shares, which gives constantfactor rentorbuy 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 kSAT 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 nonbinary model establishing the socalled KestenStigum bound for the 3state Potts model on regular trees of large degree. We further establish that the KestenStigum bound is not tight for the qstate Potts model when q ≥ 5. Moreover, we determine asymptotics for these reconstruction thresholds.
 Approximating Edit Distance in NearLinear 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 subpolynomial approximation algorithm for this problem that runs in nearlinear time, improving on the stateoftheart 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_{1}, and it is not known if that embedding can be computed in less than n^{2} time.
 Universally UtilityMaximizing Privacy Mechanisms
Arpita Ghosh, Tim Roughgarden and Mukund Sundararajan
A mechanism for releasing information about a statistical database with sensitive data must resolve a tradeoff 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 nearoptimal 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 userspecific 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 wellstudied Laplace mechanism — that is simultaneously utilitymaximizing 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 utilitymaximizing 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 SheraliAdams Relaxations
Moses Charikar, Konstantin Makarychev and Yury Makarychev
We prove strong lower bounds on integrality gaps of SheraliAdams relaxations for MAX CUT, Vertex Cover, Sparsest Cut and other problems. Our constructions show gaps for SheraliAdams relaxations that survive n^{δ} rounds of lift and project. For MAX CUT and Vertex Cover, these show that even n^{δ} rounds of SheraliAdams 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 SheraliAdams gap examples. We present a modular recipe for achieving this, building on previous work on metrics with a localglobal structure. We develop a conceptually simple geometric approach to constructing SheraliAdams gap examples via constructions of consistent local SDP solutions.
This geometric approach is surprisingly versatile. We construct SheraliAdams 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 SheraliAdams 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 PPADcomplete [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 quasipolynomial 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/ε))} nonoblivious 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 wellsuited to construct bootstrappable encryption for two reasons. First, latticebased 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 publickey 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 serveraided cryptosystem. In more detail, we include a set of vectors in the public key that includes a hidden lowweight subset that is related to the secret key. This allows us to reexpress decryption as a lowweight subset sum rather than a full matrixvector 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^{n} 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_{0}. If s is the supremum over all chords \overline{pq} passing through x_{0} of (px_{0})/(qx_{0}) 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 runtime 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 noninteractive; 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 noninteractive 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 oneway 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 minentropy, and applies even to situations where f(sk) informationtheoretically determines the entire secret key sk.
As our main result, we construct CPA/CCA secure symmetric encryption schemes that remain secure with exponentially hardtoinvert auxiliary input. We give several applications of such schemes. (1) We construct an averagecase obfuscator for the class of point functions, which remains secure with exponentially hardtoinvert auxiliary input, and is reusable. (2) We construct a reusable and robust extractor that remains secure with exponentially hardtoinvert 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 paritywithnoise (LPN) assumption. We stress that this assumption is "efficiently falsifiable" and does not quantify over all auxiliary functions f.
 Polynomialtime 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 onebyone 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 polynomialtime 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 lowdensity 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 finiteblocklength 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.047fraction of correctable errors for rate1/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, SheraliAdams relaxations, and message passing algorithms.
 A Fast and Efficient Algorithm for Lowrank Approximation of a Matrix
Nam H. Nguyen, Thong T. Do and Trac D. Tran
Lowrank 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 nonuniformly adaptive sampling some columns (or rows) of A, hoping that this subset of columns contain enough information about A. The submatrix 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 rankk 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}_{2} 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^{2}) 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 TaShma
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 blackbox pseudorandom generator, together with locally listdecodable codes and previous work done on quantum random access codes.
