STOC '13: Proceedings of the forty-fifth annual ACM symposium on Theory of Computing

We give improved pseudorandom generators (PRGs) for Lipschitz functions of low-degree polynomials over the hypercube. These are functions of the form ψ(P(x)), where P:{1,-1}ⁿ -> R is a low-degree polynomial and ψ:R -> R is a function with small ...

Let φ(G) be the minimum conductance of an undirected graph G, and let 0=λ₁ ≤ λ₂ ≤ ... ≤ λ_n ≤ 2 be the eigenvalues of the normalized Laplacian matrix of G. We prove that for any graph G and any k ≥ 2, [φ(G) = O(k) l₂/√l_k,] and this performance guarantee ...

We study connections between Natural Proofs, derandomization, and the problem of proving "weak" circuit lower bounds such as NEXP ⊄ TC⁰, which are still wide open. Natural Proofs have three properties: they are constructive (an efficient algorithm A is ...

Motivated by certain applications from physics, biochemistry, economics, and computer science in which the objects under investigation are unknown or not directly accessible because of various limitations, we propose a trial-and-error model to examine ...

We present game-theoretic models of opinion formation in social networks where opinions themselves co-evolve with friendships. In these models, nodes form their opinions by maximizing agreements with friends weighted by the strength of the relationships,...

We study the makespan minimization problem with unrelated selfish machines under the assumption that job sizes are stochastic. We design simple truthful mechanisms that under different distributional assumptions provide constant and sublogarithmic ...

We study a combinatorial market design problem, where a collection of indivisible objects is to be priced and sold to potential buyers subject to equilibrium constraints. The classic solution concept for such problems is Walrasian Equilibrium (WE), ...

The classical Grothendieck inequality has applications to the design of approximation algorithms for NP-hard optimization problems. We show that an algorithmic interpretation may also be given for a noncommutative generalization of the Grothendieck ...

We design a new distribution over poly(r ε^-1) x n matrices S so that for any fixed n x d matrix A of rank r, with probability at least 9/10, SAx₂ = (1 pm ε)Ax₂ simultaneously for all x ∈ R^d. Such a matrix S is called a subspace embedding. Furthermore, ...

Low-distortion embeddings are critical building blocks for developing random sampling and random projection algorithms for common linear algebra problems. We show that, given a matrix A ∈ R^{n x d} with n >> d and a p ∈ [1, 2), with a constant probability, ...

We give near-tight lower bounds for the sparsity required in several dimensionality reducing linear maps. First, consider the Johnson-Lindenstrauss (JL) lemma which states that for any set of n vectors in R^d there is an A∈R^{m x d} with m = O(ε^-2log n) ...

Succinct non-interactive arguments of knowledge (SNARKs) enable verifying NP statements with complexity that is essentially independent of that required for classical NP verification. In particular, they provide strong solutions to the problem of ...

Linear sketches are powerful algorithmic tools that turn an n-dimensional input into a concise lower-dimensional representation via a linear transformation. Such sketches have seen a wide range of applications including norm estimation over data streams,...

We prove that language equivalence of deterministic one-counter automata is NL-complete. This improves the superpolynomial time complexity upper bound shown by Valiant and Paterson in 1975. Our main contribution is to prove that two deterministic one-...

We prove the lower bound R M_m) ≥ 3/2 m²-2 on the border rank of m x m matrix multiplication by exhibiting explicit representation theoretic (occurence) obstructions in the sense of Mulmuley and Sohoni's geometric complexity theory (GCT) program. While ...

We develop a new local characterization of the zero-error information complexity function for two-party communication problems, and use it to compute the exact internal and external information complexity of the 2-bit AND function: IC(AND,0) = C_∧≅ ...

We prove an unconditional lower bound that any linear program that achieves an O(n^1-ε) approximation for clique has size 2^Ω(nε). There has been considerable recent interest in proving unconditional lower bounds against any linear program. Fiorini et al. ...

We give an explicit function h:{0,1}ⁿ->{0,1} such that any deMorgan formula of size O(n^2.499) agrees with h on at most 1/2 + ε fraction of the inputs, where ε is exponentially small (i.e. ε = 2^-nΩ(1)). We also show, using the same technique, that any ...

We introduce the notion of non-monotone utilities, which covers a wide variety of utility functions in economic theory. We show that it is PPAD-hard to compute an approximate Arrow-Debreu market equilibrium in markets with linear and non-monotone ...

Tatonnement is a simple and natural rule for updating prices in Exchange (Arrow-Debreu) markets. In this paper we define a class of markets for which tatonnement is equivalent to gradient descent. This is the class of markets for which there is a convex ...

Simultaneous item auctions are simple and practical procedures for allocating items to bidders with potentially complex preferences. In a simultaneous auction, every bidder submits independent bids on all items simultaneously. The allocation and prices ...

We initiate the study of efficient mechanism design with guaranteed good properties even when players participate in multiple mechanisms simultaneously or sequentially. We define the class of smooth mechanisms, related to smooth games defined by ...

We present a new zero-knowledge argument protocol by relying on the non-black-box simulation technique of Barak (FOCS'01). Similar to the protocol of Barak, ours is public-coin, is based on the existence of collision-resistant hash functions, and, is ...

The simulation paradigm, introduced by Goldwasser, Micali and Rackoff, is of fundamental importance to modern cryptography. In a breakthrough work from 2001, Barak (FOCS'01) introduced a novel non-black-box simulation technique. This technique enabled ...

The traditional notion of program obfuscation requires that an obfuscation ~Prog of a program Prog computes the exact same function as Prog, but beyond that, the code of ~Prog should not leak any information about Prog. This strong notion of virtual ...

We show how to efficiently compile any given circuit C into a leakage-resistant circuit C' such that any function on the wires of C' that leaks information during a computation C'(x) yields advantage in computing the product of |C'|^Ω(1) elements of the ...

A Steiner 2-design is a finite geometry consisting of a set of "points" together with a set of "lines" (subsets of points of uniform cardinality) such that each pair of points belongs to exactly one line. In this paper we analyse the individualization/...

A standard heuristic for testing graph isomorphism is to first assign distinct labels to a small set of vertices of an input graph, and then propagate to create new vertex labels across the graph, aiming to assign distinct and isomorphism-invariant ...

We give a 2-approximation algorithm for the non-uniform Sparsest Cut problem that runs in time n^O(k), where k is the treewidth of the graph. This improves on the previous 2^2k-approximation in time poly(n) 2^O(k) due to Chlamtac et al. [18].

To complement ...

Treewidth is a graph parameter that plays a fundamental role in several structural and algorithmic results. We study the problem of decomposing a given graph G into node-disjoint subgraphs, where each subgraph has sufficiently large treewidth. We prove ...

For an even integer t ≥ 2, the Matching Connectivity matrix H_t is a matrix that has rows and columns both labeled by all perfect matchings of the complete graph K_t on t vertices; an entry H_t[M₁,M₂] is 1 if M₁∪ M₂ is a Hamiltonian cycle and 0 otherwise. ...

Let H be a k-graph on n vertices, with minimum codegree at least n/k + cn for some fixed c > 0. In this paper we construct a polynomial-time algorithm which finds either a perfect matching in H or a certificate that none exists. This essentially solves ...

We call a depth-4 formula C set-depth-4 if there exists a (unknown) partition X₁⊔⋅⋅⋅⊔ X_d of the variable indices [n] that the top product layer respects, i.e. C(term{x})=∑_i=1^k ∏_j=1^d f_i,j(term{x}_Xj), where f_i,j is a sparse polynomial in F[term{x}_Xj]. ...

We consider differentially private approximate singular vector computation. Known worst-case lower bounds show that the error of any differentially private algorithm must scale polynomially with the dimension of the singular vector. We are able to ...

We give new mechanisms for answering exponentially many queries from multiple analysts on a private database, while protecting dif- ferential privacy both for the individuals in the database and for the analysts. That is, our mechanism's answer to each ...

We study trade-offs between accuracy and privacy in the context of linear queries over histograms. This is a rich class of queries that includes contingency tables and range queries and has been the focus of a long line of work. For a given set of d ...

A central problem in differentially private data analysis is how to design efficient algorithms capable of answering large numbers of counting queries on a sensitive database. Counting queries are of the form "What fraction of individual records in the ...

We consider bottom-k sampling for a set X, picking a sample S_k(X) consisting of the k elements that are smallest according to a given hash function h. With this sample we can estimate the relative size f=|Y|/|X| of any subset Y as |S_k(X) intersect Y|/k. ...

We describe a distributed randomized algorithm to construct routing tables. Given 0< ε <= 1/2, the algorithm runs in time ~O(n^1/2+ε + HD), where n is the number of nodes and HD denotes the diameter of the network in hops (i.e., as if the network is ...

The problem of ε-approximate agreement in Byzantine asynchronous systems is well-understood when all values lie on the real line. In this paper, we generalize the problem to consider values that lie in R^m, for m ≥ 1, and present an optimal protocol in ...

In the classic asynchronous Byzantine agreement problem, communication is via asynchronous message-passing and the adversary is adaptive with full information. In particular, the adversary can adaptively determine which processors to corrupt and what ...

Given oracle access to a Boolean function f:{0,1}ⁿ -> {0,1}, we design a randomized tester that takes as input a parameter ε>0, and outputs Yes if the function is monotonically non-increasing, and outputs No with probability >2/3, if the function is ε-...

The problem of monotonicity testing over the hypergrid and its special case, the hypercube, is a classic question in property testing. We are given query access to f:[k]ⁿ -> R (for some ordered range R). The hypergrid/cube has a natural partial order ...

Set F = F_p for any fixed prime p ≥ 2. An affine-invariant property is a property of functions over Fⁿ that is closed under taking affine transformations of the domain. We prove that all affine-invariant properties having local characterizations are ...

Testing a property P of graphs in the bounded-degree model deals with the following problem: given a graph G of bounded degree d, we should distinguish (with probability 2/3, say) between the case that G satisfies P and the case that one should add/...

We show optimal (up to constant factor) NP-hardness for Max-k-CSP over any domain, whenever k is larger than the domain size. This follows from our main result concerning predicates over abelian groups. We show that a predicate is approximation ...

We prove that for all integer k ≥ 3, there is a predicate P on k Boolean variables with 2^~O(k1/3) accepting assignments that is approximation resistant even on satisfiable instances. That is, given a satisfiable CSP instance with constraint P, we cannot ...

We put forth the concept of witness encryption. A witness encryption scheme is defined for an NP language L (with corresponding witness relation R). In such a scheme, a user can encrypt a message M to a particular problem instance x to produce a ...

The Majority is Stablest Theorem has numerous applications in hardness of approximation and social choice theory. We give a new proof of the Majority is Stablest Theorem by induction on the dimension of the discrete cube. Unlike the previous proof, it ...

We obtain asymptotically sharper lower bounds on resolution complexity for k-CNF's than was known previously. We show that for any large enough k there are k-CNF's which require resolution width (1-~O(k^-1/4))n, regular resolution size 2^{(1-~O(k-1/4))n}, ...

The classical Okamura-Seymour theorem states that for an edge-capacitated, multi-commodity flow instance in which all terminals lie on a single face of a planar graph, there exists a feasible concurrent flow if and only if the cut conditions are ...

Given a triangulated planar graph G on n vertices and an integer r<n, an r--division of G with few holes is a decomposition of G into O(n/r) regions of size at most r such that each region contains at most a constant number of faces that are not faces ...

The diameter and the radius of a graph are fundamental topological parameters that have many important practical applications in real world networks. The fastest combinatorial algorithm for both parameters works by solving the all-pairs shortest paths ...

In the online Steiner tree problem, a sequence of points is revealed one-by-one: when a point arrives, we only have time to add a single edge connecting this point to the previous ones, and we want to minimize the total length of edges added. Here, a ...

The Multiway-Cut problem is a fundamental graph partitioning problem in which the objective is to find a minimum weight set of edges disconnecting a given set of special vertices called terminals. This problem is NP-hard and there is a well known ...

In an attribute-based encryption (ABE) scheme, a ciphertext is associated with an l-bit public index pind and a message m, and a secret key is associated with a Boolean predicate P. The secret key allows to decrypt the ciphertext and learn m iff P(pind) ...

Garbled circuits, introduced by Yao in the mid 80s, allow computing a function f on an input x without leaking anything about f or x besides f(x). Garbled circuits found numerous applications, but every known construction suffers from one limitation: it ...

We construct a 1-round delegation scheme for every language computable in time t=t(n) and space s=s(n), where the running time of the prover is poly(t) and the running time of the verifier is ~O(n + poly(s)) (where ~O hides polylog(t) factors).

The ...

We show that the Learning with Errors (LWE) problem is classically at least as hard as standard worst-case lattice problems. Previously this was only known under quantum reductions.

Our techniques capture the tradeoff between the dimension and the ...

Probabilistically-Checkable Proofs (PCPs) form the algorithmic core that enables fast verification of long computations in many cryptographic constructions. Yet, despite the wonderful asymptotic savings they bring, PCPs are also the infamous ...

We consider several basic problems of algebraic topology, with connections to combinatorial and geometric questions, from the point of view of computational complexity.

The extension problem asks, given topological spaces X,Y, a subspace A ⊆ X, and a (...

We provide a general framework for getting linear time constant factor approximations (and in many cases FPTAS's) to a copious amount of well known and well studied problems in Computational Geometry, such as k-center clustering and furthest nearest ...

The paper concerns lattice triangulations, i.e., triangulations of the integer points in a polygon in R² whose vertices are also integer points. Lattice triangulations have been studied extensively both as geometric objects in their own right and by ...

We study the complexity of computing average quantities related to spin systems, such as the mean magnetization and susceptibility in the ferromagnetic Ising model, and the average dimer count (or average size of a matching) in the monomer-dimer model. ...

We prove a complexity dichotomy theorem for Holant problems over an arbitrary set of complex-valued symmetric constraint functions {F} on Boolean variables. This extends and unifies all previous dichotomies for Holant problems on symmetric constraint ...

Spectral Graph Theory is the interplay between linear algebra and combinatorial graph theory. One application of this interplay is a nearly linear time solver for Symmetric Diagonally Dominate systems (SDD). This seemingly restrictive class of systems ...

The degree, the (hop-)diameter, and the weight are the most basic and well-studied parameters of geometric spanners. In a seminal STOC'95 paper, titled "Euclidean spanners: short, thin and lanky", Arya et al. [2] devised a construction of Euclidean (1+ε)...

We introduce a framework for proving lower bounds on computational problems over distributions, based on a class of algorithms called statistical algorithms. For such algorithms, access to the input distribution is limited to obtaining an estimate of ...

Alternating minimization represents a widely applicable and empirically successful approach for finding low-rank matrices that best fit the given data. For example, for the problem of low-rank matrix completion, this method is believed to be one of the ...

We study the ε-rank of a real matrix A, defined for any ε > 0 as the minimum rank over matrices that approximate every entry of A to within an additive ε. This parameter is connected to other notions of approximate rank and is motivated by problems from ...

Constraint-satisfaction problems (CSPs) form a basic family of NP-hard optimization problems that includes satisfiability. Motivated by the sufficient condition for the satisfiability of SAT formulae that is offered by the Lovasz Local Lemma, we seek ...

Let Γ be a set of rational-valued functions on a fixed finite domain; such a set is called a finite-valued constraint language. The valued constraint satisfaction problem, VCSP(Γ), is the problem of minimising a function given as a sum of functions from ...

Random k-SAT is the single most intensely studied example of a random constraint satisfaction problem. But despite substantial progress over the past decade, the threshold for the existence of satisfying assignments is not known precisely for any k≥3. ...

We study the interactive channel capacity of an ε-noisy channel. The interactive channel capacity C(ε) is defined as the minimal ratio between the communication complexity of a problem (over a non-noisy channel), and the communication complexity of the ...

We present an improved algorithm for maintaining all-pairs 1 + ε approximate shortest paths under deletions and weight-increases. The previous state of the art for this problem was total update time ~O (n²√m/ε) for directed, unweighted graphs [2], and ~...

We give simple linear-time algorithms for two problems in planar graphs: max st-flow in directed graphs with unit capacities, and multiple-source shortest paths in undirected graphs with unit lengths.

A maximal matching can be maintained in fully dynamic (supporting both addition and deletion of edges) n-vertex graphs using a trivial deterministic algorithm with a worst-case update time of O(n). No deterministic algorithm that outperforms the naive O(...

We give an algorithm which computes a (1-ε)-approximately maximum st-flow in an undirected uncapacitated graph in time O(1/ε√m/F⋅ m log² n) where F is the flow value. By trading this off against the Karger-Levine algorithm for undirected graphs which ...

In this paper, we present improved polynomial time algorithms for the max flow problem defined on sparse networks with n nodes and m arcs. We show how to solve the max flow problem in O(nm + m^31/16 log² n) time. In the case that m = O(n^1.06), this ...

We revisit the classic problem of sampling from a discrete distribution: Given n non-negative w-bit integers x₁,..,x_n, the task is to build a data structure that allows sampling i with probability proportional to x_i. The classic solution is Walker's ...

We study the problem of constructing explicit extractors for independent general weak random sources. For weak sources on n bits with min-entropy k, perviously the best known extractor needs to use at least log n/log k independent sources [22, 3]. In ...

We study interactive proofs with sublinear-time verifiers. These proof systems can be used to ensure approximate correctness for the results of computations delegated to an untrusted server. Following the literature on property testing, we seek proof ...

For each natural number d we consider a finite structure M_d whose universe is the set of all 0,1-sequence of length n=2^d, each representing a natural number in the set {0,1,...,2ⁿ-1} in binary form. The operations included in the structure are the four ...

We present size-space trade-offs for the polynomial calculus (PC) and polynomial calculus resolution (PCR) proof systems. These are the first true size-space trade-offs in any algebraic proof system, showing that size and space cannot be simultaneously ...

A Matching Vector (MV) family modulo m is a pair of ordered lists U=(u₁,...,u_t) and V=(v₁,...,v_t) where u_i,v_j ∈ Z_mⁿ with the following inner product pattern: for any i, {u_i,v_i}=0, and for any i ≠ j, {u_i,v_j} ≠ 0. A MV family is called q-restricted if ...

We describe new constructions of error correcting codes, obtained by "degree-lifting" a short algebraic geometry base-code of block-length q to a lifted-code of block-length q^m, for arbitrary integer m. The construction generalizes the way degree-d, ...

We consider Reed-Solomon (RS) codes whose evaluation points belong to a subfield, and give a linear-algebraic list decoding algorithm that can correct a fraction of errors approaching the code distance, while pinning down the candidate messages to a ...

It is well known that a random q-ary code of rate Ω(ε²) is list decodable up to radius (1 - 1/q - ε) with list sizes on the order of 1/ε², with probability 1 - o(1). However, until recently, a similar statement about random linear codes has until ...

Quantum de Finetti theorems are a useful tool in the study of correlations in quantum multipartite states. In this paper we prove two new quantum de Finetti theorems, both showing that under tests formed by local measurements in each of the subsystems ...

The local Hamiltonian problem consists of estimating the ground-state energy (given by the minimum eigenvalue) of a local quantum Hamiltonian. It can be considered as a quantum generalization of constraint satisfaction problems (CSPs) and has a key role ...

We show that quantum computers improve on the best known classical algorithms for matrix inversion (and singular value decomposition) as far as space is concerned. This adds to the (still short) list of important problems where quantum computers are of ...

A quantum algorithm is exact if, on any input data, it outputs the correct answer with certainty (probability 1). A key question is: how big is the advantage of exact quantum algorithms over their classical counterparts: deterministic algorithms. For ...

We present a novel approximation algorithm for k-median that achieves an approximation guarantee of 1+√3+ε, improving upon the decade-old ratio of 3+ε. Our approach is based on two components, each of which, we believe, is of independent interest. First,...

In this paper, we present a simple combinatorial algorithm that solves symmetric diagonally dominant (SDD) linear systems in nearly-linear time. It uses little of the machinery that previously appeared to be necessary for a such an algorithm. It does ...

We study the set disjointness problem in the most powerful bounded-error model: the number-on-the-forehead model with k parties and arbitrary classical or quantum communication. We obtain a communication lower bound of Omega(√(n)/2^k*k) bits, which is ...

Fingerprinting is a widely-used technique for efficiently verifying that two files are identical. More generally, linear sketching is a form of lossy compression (based on random projections) that also enables the "dissimilarity" of non-identical files ...

We consider higher-dimensional versions of Kannan and Lipton's Orbit Problem---determining whether a target vector space V may be reached from a starting point x under repeated applications of a linear transformation A. Answering two questions posed by ...

We study the following balls and bins stochastic process: There is a buffer with B bins, and there is a stream of balls X = {X₁, X₂, ... ,X_T} such that X_i is the number of balls that arrive before time i but after time i-1. Once a ball arrives, it is ...

In the d-dimensional bin packing problem (VBP), one is given vectors x₁,x₂, ... ,x_n ∈ R^d and the goal is to find a partition into a minimum number of feasible sets: {1,2 ... ,n} = ∪_i^s B_i. A set B_i is feasible if ∑_{j ∈ Bi} x_j ≤ 1, where 1 denotes the all 1'...

We study several stochastic combinatorial problems, including the expected utility maximization problem, the stochastic knapsack problem and the stochastic bin packing problem. A common technical challenge in these problems is to optimize some function (...