STOC

We show new lower bounds on the sample complexity of (ε, δ)-differentially private algorithms that accurately answer large sets of counting queries. A counting query on a database D ∈ ({0, 1}^d)ⁿ has the form "What fraction of the individual records in ...

We consider the problem of privately releasing a low dimensional approximation to a set of data records, represented as a matrix A in which each row corresponds to an individual and each column to an attribute. Our goal is to compute a subspace that ...

We consider a private variant of the classical allocation problem: given k goods and n agents with individual, private valuation functions over bundles of goods, how can we partition the goods amongst the agents to maximize social welfare? An important ...

We present a general approach to rounding semidefinite programming relaxations obtained by the Sum-of-Squares method (Lasserre hierarchy). Our approach is based on using the connection between these relaxations and the Sum-of-Squares proof system to ...

We propose and study a new semi-random semi-adversarial model for Balanced Cut, a planted model with permutation invariant random edges (PIE). Our model is much more general than planted models considered previously. Consider a set of vertices V ...

We study the problem of computing max-entropy distributions over a discrete set of objects subject to observed marginals. There has been a tremendous amount of interest in such distributions due to their applicability in areas such as statistical ...

One of the key results in Robertson and Seymour's seminal work on graph minors is the Grid-Minor Theorem (also called the Excluded Grid Theorem). The theorem states that for every fixed-size grid H, every graph whose treewidth is large enough, contains ...

The excluded grid theorem, originally proved by Robertson and Seymour in Graph Minors V, is one of the most central results in the study of graph minors. It has found numerous applications in algorithmic graph structure theory, for instance as the basis ...

We prove that any graph excluding K_r as a minor has can be partitioned into clusters of diameter at most Δ while removing at most O(r/Δ) fraction of the edges. This improves over the results of Fakcharoenphol and Talwar, who building on the work of ...

Nowhere dense graph classes, introduced by Nešetřil and Ossona de Mendez [30], form a large variety of classes of "sparse graphs" including the class of planar graphs, actually all classes with excluded minors, and also bounded degree graphs and graph ...

A sampling procedure for a distribution P over {0, 1}^ℓ, is a function C: {0, 1}ⁿ → {0, 1}^ℓ such that the distribution C(U_n) (obtained by applying C on the uniform distribution U_n) is the "desired distribution" P. Let n > r ≥ ℓ = n^Ω(1). An nb-PRG (...

Does derandomization of probabilistic algorithms become easier when the number of "bad" random inputs is extremely small?

In relation to the above question, we put forward the following quantified derandomization challenge: For a class of circuits C (...

We show that any depth-4 homogeneous arithmetic formula computing the Iterated Matrix Multiplication polynomial IMM_n,d -- the (1, 1)-th entry of the product of d generic n × n matrices -- has size n^{Ω(log n}), if d = Ω (log² n). More-over, any depth-4 ...

We study the arithmetic complexity of iterated matrix multiplication. We show that any multilinear homogeneous depth 4 arithmetic formula computing the product of d generic matrices of size n × n, IMM_n,d, has size n^Ω(√d) as long as d = n^O(1). This ...

In recent years, a very exciting and promising method for proving lower bounds for arithmetic circuits has been proposed. This method combines the method of depth reduction developed in the works of Agrawal and Vinay[1], Koiran [11] and Tavenas [16], ...

We consider arithmetic formulas consisting of alternating layers of addition (+) and multiplication (×) gates such that the fanin of all the gates in any fixed layer is the same. Such a formula Φ which additionally has the property that its formal/...

Let P be a property of function F^np → {0, 1} for a fixed prime p. An algorithm is called a tester for P if, given a query access to the input function f, with high probability, it accepts when f satisfies P and rejects when f is "far" from satisfying P. ...

We initiate a systematic study of sublinear algorithms for approximately testing properties of real-valued data with respect to L_p distances for p = 1, 2. Such algorithms distinguish datasets which either have (or are close to having) a certain property ...

In the turnstile model of data streams, an underlying vector x ∈ {--m,--m+1,..., m--1,m}ⁿ is presented as a long sequence of positive and negative integer updates to its coordinates. A randomized algorithm seeks to approximate a function f(x) with ...

We show that the compressed suffix array and the compressed suffix tree for a string of length n over an integer alphabet of size σ ≤ n can both be built in O(n) (randomized) time using only O(n log σ) bits of working space. The previously fastest ...

Let ACC o THR be the class of constant-depth circuits comprised of AND, OR, and MODm gates (for some constant m > 1), with a bottom layer of gates computing arbitrary linear threshold functions. This class of circuits can be seen as a "midpoint" between ...

We give the first super-polynomial separation in the power of bounded-depth boolean formulas vs. circuits. Specifically, we consider the problem Distance k(n) Connectivity, which asks whether two specified nodes in a graph of size n are connected by a ...

One of the major open problems in complexity theory is proving super-logarithmic lower bounds on the depth of circuits (i.e., P ⊈ NC¹). This problem is interesting for two reasons: first, it is tightly related to understanding the power of parallel ...

The threshold degree of a Boolean function f is the minimum degree of a real polynomial p that represents f in sign: f(x) ≡ sgn p(x). In a seminal 1969 monograph, Minsky and Papert constructed a polynomial-size constant-depth {∧, ∨)-circuit in n ...

We study the necessity of interaction between individuals for obtaining approximately efficient economic allocations. We view this as a formalization of Hayek's classic point of view that focuses on the information transfer advantages that markets have ...

In the design and analysis of revenue-maximizing auctions, auction performance is typically measured with respect to a prior distribution over inputs. The most obvious source for such a distribution is past data. The goal of this paper is to understand ...

We study the design of truthful auctions for selling identical items in unlimited supply (e.g., digital goods) to n unit demand buyers. This classic problem stands out from profit-maximizing auction design literature as it requires no probabilistic ...

A popular method in combinatorial optimization is to express polytopes P, which may potentially have exponentially many facets, as solutions of linear programs that use few extra variables to reduce the number of constraints down to a polynomial. After ...

Quantum codes with low-weight stabilizers known as LDPC codes have been actively studied recently due to their potential applications in fault-tolerant quantum computing. However, all families of quantum LDPC codes known to this date suffer from a poor ...

We provide a quantum algorithm for simulating the dynamics of sparse Hamiltonians with complexity sublogarithmic in the inverse error, an exponential improvement over previous methods. Specifically, we show that a d-sparse Hamiltonian H on n qubits can ...