STOC 2016
48th Annual ACM SIGACT Symposium on the Theory of Computing (STOC 2016)
Powered by
Conference Publishing Consulting

48th Annual ACM SIGACT Symposium on the Theory of Computing (STOC 2016), June 19–21, 2016, Cambridge, MA, USA

STOC 2016 – Proceedings

Contents - Abstracts - Authors


Title Page

The papers in this volume were presented at the Forty-Eighth Annual ACM Symposium on Theory of Computing (STOC 2016), held in Cambridge, Massachusetts, June 19--June 21, 2016. The Symposium was sponsored by the ACM Special Interest Group on Algorithms and Computation Theory (SIGACT). On June 18, the day before STOC, there was a workshop and tutorial day held jointly with the 32nd International Symposium on Computational Geometry (SOCG 2016), which was organized by Alexandr Andoni, Chandra Chekuri, Suresh Venkatasubramanian and Yusu Wang. In response to a Call for Papers, 370 submissions were received by the submission deadline of November 2, 2015 (23:59pm EST). The Program Committee electronic deliberations continued until its meeting at MSR in New York, NY on January 29 -- January 31, 2016, where final decisions were made. The Program Committee meeting was attended by 24 (of the 25) Program Committee members and one member joined the discussions by phone. The Program Committee selected 92 papers for presentation. The submissions were not refereed, and many of these papers represent reports of continuing research. It is expected that most of them will appear in a more polished and complete form in scientific journals. The Program Committee would like to thank all authors who submitted papers for consideration. From among many excellent candidates, the papers ``Explicit Two-Source Extractors and Resilient Functions'' by Eshan Chattopadhyay and David Zuckerman, ``Graph Isomorphism in Quasipolynomial Time'' by Laszlo Babai and ``Reed-Muller Codes Achieve Capacity on Erasure Channels'' by Shrinivas Kudekar, Santhosh Kumar, Marco Mondelli, Henry D. Pfister, Eren Sasoglu and Rudiger Urbanke were selected for the STOC Best Paper Award. The papers ``The 4/3 Additive Spanner Exponent is Tight'' by Amir Abboud and Greg Bodwin, and ``A Tight Space Bound for Consensus'' by Leqi Zhu, were selected for the Danny Lewin Best Student Paper Award. The committee is very grateful to Shai Halevi for providing access to and support for his conference program committee software. The committee is also very grateful to the large number of members of the community (listed on a separate page) who assisted the committee in assessing the merits of the submissions. I am extremely grateful to Paul Beame and Michael Mitzenmacher, the SIGACT Executive Committee Chairs, for their useful guidance, advice, and help in the process. I would like to thank Daniel Wichs, the General Chair, for his help, responsiveness and hard work. I would like to thank the staff of MSR NYC, who provided many amenities during the Program Committee meeting. I am especially grateful to Ronitt Rubinfeld for her continuous support and guidance throughout the entire process. Last, but far from least, I wish to thank the Program Committee for their incredibly hard work, for their wisdom and for their devotion to our field. It was a great honor to work with them. Yishay Mansour MSR and Tel Aviv University STOC 2016 Program Chair

Conference Organization
Committee Listings

Sponsors and Supporters
Sponsors and Supporters

Session 1A

Almost Tight Bounds for Eliminating Depth Cycles in Three Dimensions
Boris Aronov and Micha Sharir
(New York University, USA; Tel Aviv University, Israel)
Given n non-vertical lines in 3-space, their vertical depth (above/below) relation can contain cycles. We show that the lines can be cut into O(n3/2polylog n) pieces, such that the depth relation among these pieces is now a proper partial order. This bound is nearly tight in the worst case. As a consequence, we deduce that the number of pairwise non-overlapping cycles, namely, cycles whose xy-projections do not overlap, is O(n3/2polylog n); this bound too is almost tight in the worst case.
Previous results on this topic could only handle restricted cases of the problem (such as handling only triangular cycles, by Aronov, Koltun, and Sharir, or only cycles in grid-like patterns, by Chazelle et al.), and the bounds were considerably weaker—much closer to the trivial quadratic bound.
Our proof uses a recent variant of the polynomial partitioning technique, due to Guth, and some simple tools from algebraic geometry. It is much more straightforward than the previous “purely combinatorial” methods.
Our approach extends to eliminating all cycles in the depth relation among segments, and among constant-degree algebraic arcs. We hope that a suitable extension of this technique could be used to handle the much more difficult case of pairwise-disjoint triangles as well.
Our results almost completely settle a long-standing (35 years old) open problem in computational geometry, motivated by hidden-surface removal in computer graphics.

Publisher's Version Article Search
Geometric Median in Nearly Linear Time
Michael B. Cohen, Yin Tat Lee, Gary Miller, Jakub Pachocki, and Aaron Sidford
(Massachusetts Institute of Technology, USA; Carnegie Mellon University, USA; Microsoft Research, USA)
In this paper we provide faster algorithms for solving the geometric median problem: given n points in d compute a point that minimizes the sum of Euclidean distances to the points. This is one of the oldest non-trivial problems in computational geometry yet despite a long history of research the previous fastest running times for computing a (1+є)-approximate geometric median were O(d· n4/3є−8/3) by Chin et. al, Õ(dexpє−4logє−1) by Badoiu et. al, O(nd+poly(d−1)) by Feldman and Langberg, and the polynomial running time of O((nd)O(1)log1/є) by Parrilo and Sturmfels and Xue and Ye.
In this paper we show how to compute such an approximate geometric median in time O(ndlog3n/є) and O(dє−2). While our O(dє−2) is a fairly straightforward application of stochastic subgradient descent, our O(ndlog3n/є) time algorithm is a novel long step interior point method. We start with a simple O((nd)O(1)log1/є) time interior point method and show how to improve it, ultimately building an algorithm that is quite non-standard from the perspective of interior point literature. Our result is one of few cases of outperforming standard interior point theory. Furthermore, it is the only case we know of where interior point methods yield a nearly linear time algorithm for a canonical optimization problem that traditionally requires superlinear time.

Publisher's Version Article Search
Separating Subadditive Euclidean Functionals
Alan Frieze and Wesley Pegden
(Carnegie Mellon University, USA)
The classical Beardwood-Halton-Hammersly theorem (1959) asserts the existence of an asymptotic formula of the form constant times square root n for the minimum length of a Traveling Salesperson Tour through n random points in the unit square, and in the decades since it was proved, the existence of such formulas has been shown for other such Euclidean functionals on random points in the unit square as well. Despite more than 50 years of attention, however, it remained unknown whether the minimum length TSP through n random points in the unit square was asymptotically distinct from its natural lower bounds, such as the minimum length spanning tree, the minimum length 2-factor, or, as raised by Goemans and Bertsimas, from its linear programming relaxation. We prove that the TSP on random points in Euclidean space is indeed asymptotically distinct from these and other natural lower bounds, and show that this separation implies that branch-and-bound algorithms based on these natural lower bounds must take nearly exponential time to solve the TSP to optimality, even in average case. This is the first average-case superpolynomial lower bound for these branch-and-bound algorithms.

Publisher's Version Article Search
Bounded Degree Cosystolic Expanders of Every Dimension
Shai Evra and Tali Kaufman
(Hebrew University of Jerusalem, Israel; Bar-Ilan University, Israel)
In recent years a high dimensional theory of expanders has emerged. The notion of combinatorial expansion of graphs (i.e. the Cheeger constant of a graph) has seen two generalizations to high dimensional simplicial complexes. One generalization, known as coboundary expansion, is due to Linial and Meshulem; the other, which we term here cosystolic expansion, is due to Gromov, who showed that cosystolic expanders have the topological overlapping property. No construction (either random or explicit) of bounded degree combinational expanders (according to either definition) were known until a recent work of Kaufman, Kazhdan and Lubotzky, which provided the first bounded degree cosystolic expanders of dimension two. No bounded degree combinatorial expanders are known in higher dimensions. In this work we present explicit bounded degree cosystolic expanders of every dimension. This solves affirmatively an open question raised by Gromov, who asked whether there exist bounded degree complexes with the topological overlapping property in every dimension. Moreover, we provide a local to global criterion on a complex that implies cosystolic expansion: Namely, for a d-dimensional complex, X, if its underlying graph is a good expander, and all its links are both coboundary expanders and good expander graphs, then the (d-1)-dimensional skeleton of the complex is a cosystolic expander.

Publisher's Version Article Search

Session 1B

Constant-Round Interactive Proofs for Delegating Computation
Omer Reingold, Guy N. Rothblum, and Ron D. Rothblum
(Samsung Research, USA; Massachusetts Institute of Technology, USA)
The celebrated IP=PSPACE Theorem of Lund et-al. (J.ACM 1992) and Shamir (J.ACM 1992), allows an all-powerful but untrusted prover to convince a polynomial-time verifier of the validity of extremely complicated statements (as long as they can be evaluated using polynomial space). The interactive proof system designed for this purpose requires a polynomial number of communication rounds and an exponential-time (polynomial-space complete) prover. In this paper, we study the power of more efficient interactive proof systems.
Our main result is that for every statement that can be evaluated in polynomial time and bounded-polynomial space there exists an interactive proof that satisfies the following strict efficiency requirements: (1) the honest prover runs in polynomial time, (2) the verifier is almost linear time (and under some conditions even sub linear), and (3) the interaction consists of only a constant number of communication rounds. Prior to this work, very little was known about the power of efficient, constant-round interactive proofs (rather than arguments). This result represents significant progress on the round complexity of interactive proofs (even if we ignore the running time of the honest prover), and on the expressive power of interactive proofs with polynomial-time honest prover (even if we ignore the round complexity). This result has several applications, and in particular it can be used for verifiable delegation of computation.
Our construction leverages several new notions of interactive proofs, which may be of independent interest. One of these notions is that of unambiguous interactive proofs where the prover has a unique successful strategy. Another notion is that of probabilistically checkable interactive proofs (PCIPs) where the verifier only reads a few bits of the transcript in checking the proof (this could be viewed as an interactive extension of PCPs).

Publisher's Version Article Search
Candidate Hard Unique Game
Subhash Khot and Dana Moshkovitz
(New York University, USA; Massachusetts Institute of Technology, USA)
We propose a candidate reduction for ruling out polynomial-time algorithms for unique games, either under plausible complexity assumptions, or unconditionally for Lasserre semi-definite programs with a constant number of rounds. We analyze the completeness and Lasserre solution of our construction, and provide a soundness analysis in a certain setting of interest. Addressing general settings is tightly connected to a question on Gaussian isoperimetry. Our construction is based on our previous work on the complexity of approximately solving a system of linear equations over reals, which we suggested as an avenue towards a (positive) resolution of the Unique Games Conjecture. The construction employs a new encoding scheme that we call the real code. The real code has two useful properties: like the long code, it has a unique local test, and like the Hadamard code, it has the so-called sub-code covering property.

Publisher's Version Article Search
On the Effect of Randomness on Planted 3-Coloring Models
Roee David and Uriel Feige
(Weizmann Institute of Science, Israel)
We present the hosted coloring framework for studying al- gorithmic and hardness results for the k-coloring problem. There is a class H of host graphs. One selects a graph H ∈ H and plants in it a balanced k-coloring (by partitioning the vertex set into k roughly equal parts, and removing all edges within each part). The resulting graph G is given as input to a polynomial time algorithm that needs to k-color G (any legal k-coloring would do – the algorithm is not required to recover the planted k-coloring). Earlier planted models correspond to the case that H is the class of all n-vertex d-regular graphs, a member H ∈ H is chosen at random, and then a balanced k-coloring is planted at random. Blum and Spencer [1995] designed algorithms for this model when d = n δ (for 0 < δ ≤ 1), and Alon and Kahale [1997] managed to do so even when d is a sufficiently large constant. The new aspect in our framework is that it need not in- volve randomness. In one model within the framework (with k = 3) H is a d regular spectral expander (meaning that ex- cept for the largest eigenvalue of its adjacency matrix, every other eigenvalue has absolute value much smaller than d) chosen by an adversary, and the planted 3-coloring is ran- dom. We show that the 3-coloring algorithm of Alon and Kahale [1997] can be modified to apply to this case. In an- other model H is a random d-regular graph but the planted balanced 3-coloring is chosen by an adversary, after seeing H. We show that for a certain range of average degrees somewhat below √ n, finding a 3-coloring is NP-hard. To- gether these results (and other results that we have) help clarify which aspects of randomness in the planted coloring model are the key to successful 3-coloring algorithms.

Publisher's Version Article Search
Matrix Rigidity of Random Toeplitz Matrices
Oded Goldreich and Avishay Tal
(Weizmann Institute of Science, Israel; Institute for Advanced Study at Princeton, USA)
We prove that random n-by-n Toeplitz (alternatively Hankel) matrices over F2 have rigidity Ω(n3/r2logn) for rank r ≥ √n, with high probability. For r = o(n/logn · loglogn), this improves over the Ω(n2/r · log(n/r)) bound that is known for many explicit matrices.
Our result implies that the explicit trilinear [n]× [n] × [2n] function defined by F(x,y,z) = ∑i,jxi yj zi+j has complexity Ω(n3/5) in the multilinear circuit model suggested by Goldreich and Wigderson (ECCC, 2013), which yields an exp(n3/5) lower bound on the size of the so-called canonical depth-three circuits for F. We also prove that F has complexity Ω(n2/3) if the multilinear circuits are further restricted to be of depth 2.
In addition, we show that a matrix whose entries are sampled from a 2n-biased distribution has complexity Ω(n2/3), regardless of depth restrictions, almost matching the known O(n2/3) upper bound for any matrix. We turn this randomized construction into an explicit 4-linear construction with similar lower bounds, using the quadratic small-biased construction of Mossel et al. (RS&A, 2006).

Publisher's Version Article Search

Session 2A

Complexity Theoretic Limitations on Learning Halfspaces
Amit Daniely
(Google, USA)
We study the problem of agnostically learning halfspaces which is defined by a fixed but unknown distribution D on Q^n X -1,1. We define Err_H(D) as the least error of a halfspace classifier for D. A learner who can access D has to return a hypothesis whose error is small compared to Err_H(D).
Using the recently developed method of Daniely, Linial and Shalev-Shwartz we prove hardness of learning results assuming that random K-XOR formulas are hard to (strongly) refute. We show that no efficient learning algorithm has non-trivial worst-case performance even under the guarantees that Err_H(D) <= eta for arbitrarily small constant eta>0, and that D is supported in the Boolean cube. Namely, even under these favorable conditions, and for every c>0, it is hard to return a hypothesis with error <= 1/2-n^-c. In particular, no efficient algorithm can achieve a constant approximation ratio. Under a stronger version of the assumption (where K can be poly-logarithmic in n), we can take eta = 2^-log^1-nu(n) for arbitrarily small nu>0. These results substantially improve on previously known results, that only show hardness of exact learning.

Publisher's Version Article Search
A Cost Function for Similarity-Based Hierarchical Clustering
Sanjoy Dasgupta
(University of California at San Diego, USA)
The development of algorithms for hierarchical clustering has been hampered by a shortage of precise objective functions. To help address this situation, we introduce a simple cost function on hierarchies over a set of points, given pairwise similarities between those points. We show that this criterion behaves sensibly in canonical instances and that it admits a top-down construction procedure with a provably good approximation ratio.

Publisher's Version Article Search
The Computational Power of Optimization in Online Learning
Elad Hazan and Tomer Koren
(Princeton University, USA; Technion, Israel)
We consider the fundamental problem of prediction with expert advice where the experts are “optimizable”: there is a black-box optimization oracle that can be used to compute, in constant time, the leading expert in retrospect at any point in time. In this setting, we give a novel online algorithm that attains vanishing regret with respect to N experts in total O(√N) computation time. We also give a lower bound showing that this running time cannot be improved (up to log factors) in the oracle model, thereby exhibiting a quadratic speedup as compared to the standard, oracle-free setting where the required time for vanishing regret is Θ(N). These results demonstrate an exponential gap between the power of optimization in online learning and its power in statistical learning: in the latter, an optimization oracle—i.e., an efficient empirical risk minimizer—allows to learn a finite hypothesis class of size N in time O(logN).
We also study the implications of our results to learning in repeated zero-sum games, in a setting where the players have access to oracles that compute, in constant time, their best-response to any mixed strategy of their opponent. We show that the runtime required for approximating the minimax value of the game in this setting is Θ(√N), yielding again a quadratic improvement upon the oracle-free setting, where Θ(N) is known to be tight.

Publisher's Version Article Search
Instance Optimal Learning of Discrete Distributions
Gregory Valiant and Paul Valiant
(Stanford University, USA; Brown University, USA)
We consider the following basic learning task: given independent draws from an unknown distribution over a discrete support, output an approximation of the distribution that is as accurate as possible in L1 distance (equivalently, total variation distance, or "statistical distance"). Perhaps surprisingly, it is often possible to "de-noise" the empirical distribution of the samples to return an approximation of the true distribution that is significantly more accurate than the empirical distribution, without relying on any prior assumptions on the distribution. We present an instance optimal learning algorithm which optimally performs this de-noising for every distribution for which such a de-noising is possible. More formally, given n independent draws from a distribution p, our algorithm returns a labelled vector whose expected distance from p is equal to the minimum possible expected error that could be obtained by any algorithm, even one that is given the true unlabeled vector of probabilities of distribution p and simply needs to assign labels---up to an additive subconstant term that is independent of p and goes to zero as n gets large. This somewhat surprising result has several conceptual implications, including the fact that, for any large sample from a distribution over discrete support, prior knowledge of the rates of decay of the tails of the distribution (e.g. power-law type assumptions) is not significantly helpful for the task of learning the distribution. As a consequence of our techniques, we also show that given a set of n samples from an arbitrary distribution, one can accurately estimate the expected number of distinct elements that will be observed in a sample of any size up to n log n. This sort of extrapolation is practically relevant, particularly to domains such as genomics where it is important to understand how much more might be discovered given larger sample sizes, and we are optimistic that our approach is practically viable.

Publisher's Version Article Search

Session 2B

Lift-and-Round to Improve Weighted Completion Time on Unrelated Machines
Nikhil Bansal, Aravind Srinivasan, and Ola Svensson
(Eindhoven University of Technology, Netherlands; University of Maryland, USA; EPFL, Switzerland)
We consider the problem of scheduling jobs on unrelated machines so as to minimize the sum of weighted completion times. Our main result is a (3/2-c)-approximation algorithm for some fixed c>0, improving upon the long-standing bound of 3/2. To do this, we first introduce a new lift-and-project based SDP relaxation for the problem. This is necessary as the previous convex programming relaxations have an integrality gap of 3/2. Second, we give a new general bipartite-rounding procedure that produces an assignment with certain strong negative correlation properties.

Publisher's Version Article Search
A (1+epsilon)-Approximation for Makespan Scheduling with Precedence Constraints using LP Hierarchies
Elaine Levey and Thomas Rothvoss
(University of Washington, USA)
In a classical problem in scheduling, one has n unit size jobs with a precedence order and the goal is to find a schedule of those jobs on m identical machines as to minimize the makespan. It is one of the remaining four open problems from the book of Garey & Johnson whether or not this problem is NP-hard for m=3.
We prove that for any fixed ε and m, an LP-hierarchy lift of the time-index LP with a slightly super poly-logarithmic number of r = (log(n))Θ(loglogn) rounds provides a (1 + ε)-approximation. For example Sherali-Adams suffices as hierarchy. This implies an algorithm that yields a (1+ε)-approximation in time nO(r). The previously best approximation algorithms guarantee a 2 − 7/3m+1-approximation in polynomial time for m ≥ 4 and 4/3 for m=3. Our algorithm is based on a recursive scheduling approach where in each step we reduce the correlation in form of long chains. Our method adds to the rather short list of examples where hierarchies are actually useful to obtain better approximation algorithms.

Publisher's Version Article Search
Fast Spectral Algorithms from Sum-of-Squares Proofs: Tensor Decomposition and Planted Sparse Vectors
Samuel B. Hopkins, Tselil Schramm, Jonathan Shi, and David Steurer
(Cornell University, USA; University of California at Berkeley, USA)
We consider two problems that arise in machine learning applications: the problem of recovering a planted sparse vector in a random linear subspace and the problem of decomposing a random low-rank overcomplete 3-tensor. For both problems, the best known guarantees are based on the sum-of-squares method. We develop new algorithms inspired by analyses of the sum-of-squares method. Our algorithms achieve the same or similar guarantees as sum-of-squares for these problems but the running time is significantly faster.
For the planted sparse vector problem, we give an algorithm with running time nearly linear in the input size that approximately recovers a planted sparse vector with up to constant relative sparsity in a random subspace of ℝn of dimension up to Ω(√n). These recovery guarantees match the best known ones of Barak, Kelner, and Steurer (STOC 2014) up to logarithmic factors.
For tensor decomposition, we give an algorithm with running time close to linear in the input size (with exponent ≈ 1.125) that approximately recovers a component of a random 3-tensor over ℝn of rank up to Ω(n4/3). The best previous algorithm for this problem due to Ge and Ma (RANDOM 2015) works up to rank Ω(n3/2) but requires quasipolynomial time.

Publisher's Version Article Search
Maximizing Determinants under Partition Constraints
Aleksandar Nikolov and Mohit Singh
(University of Toronto, Canada; Microsoft Research, USA)
Given a positive semidefinte matrix L whose columns and rows are indexed by a set U, and a partition matroid M=(U, I), we study the problem of selecting a basis B of M such that the determinant of the submatrix of L induced by the rows and columns in B is maximized. This problem appears in many areas including determinantal point processes in machine learning, experimental design, geographical placement problems, discrepancy theory and computational geometry to model subset selection problems that incorporate diversity.
Our main result is to give a geometric concave program for the problem which approximates the optimum value within a factor of er+o(r), where r denotes the rank of the partition matroid M. We bound the integrality gap of the geometric concave program by giving a polynomial time randomized rounding algorithm. To analyze the rounding algorithm, we relate the solution of our algorithm as well the objective value of the relaxation to a certain stable polynomial. To prove the approximation guarantee, we utilize a general inequality about stable polynomials proved by Gurvits in the context of estimating the permanent of a doubly stochastic matrix.

Publisher's Version Article Search

Session 3A

High-Rate Locally-Correctable and Locally-Testable Codes with Sub-polynomial Query Complexity
Swastik Kopparty, Or Meir, Noga Ron-Zewi, and Shubhangi Saraf
(Rutgers University, USA; Weizmann Institute of Science, Israel; Institute for Advanced Study at Princeton, USA)
In this work, we construct the first locally-correctable codes (LCCs), and locally-testable codes (LTCs) with constant rate, constant relative distance, and sub-polynomial query complexity. Specifically, we show that there exist LCCs and LTCs with block length n, constant rate (which can even be taken arbitrarily close to 1) and constant relative distance, whose query complexity is exp(Õ(√logn)) (for LCCs) and (logn)O(loglogn) (for LTCs). Previously such codes were known to exist only with Ω(nβ) query complexity (for constant β>0).
In addition to having small query complexity, our codes also achieve better trade-offs between the rate and the relative distance than were previously known to be achievable by LCCs or LTCs. Specifically, over large (but constant size) alphabet, our codes approach the Singleton bound, that is, they have almost the best-possible relationship between their rate and distance. This has the surprising consequence that asking for a large-alphabet error-correcting code to further be an LCC or LTC with sub-polynomial query complexity does not require any sacrifice in terms of rate and distance! Over the binary alphabet, our codes meet the Zyablov bound. Such trade-offs between the rate and the relative distance were previously not known for any o(n) query complexity. Our results on LCCs also immediately give locally-decodable codes (LDCs) with the same parameters.
Our codes are based on a technique of Alon, Edmonds and Luby. We observe that this technique can be used as a general distance-amplification method, and show that it interacts well with local correctors and testers. We obtain our main results by applying this method to suitably constructed LCCs and LTCs in the non-standard regime of sub-constant relative distance.

Publisher's Version Article Search
Repairing Reed-Solomon Codes
Venkatesan Guruswami and Mary Wootters
(Carnegie Mellon University, USA)
A fundamental fact about polynomial interpolation is that k evaluations of a degree-(k-1) polynomial f are sufficient to determine f. This is also necessary in a strong sense: given k-1 evaluations, we learn nothing about the value of f on any k'th point. In this paper, we study a variant of the polynomial interpolation problem. Instead of querying entire evaluations of f (which are elements of a large field F), we are allowed to query partial evaluations; that is, each evaluation delivers a few elements from a small subfield of F, rather than a single element from F. We show that in this model, one can do significantly better than in the traditional setting, in terms of the amount of information required to determine the missing evaluation. More precisely, we show that only O(k) bits are necessary to recover a missing evaluation. In contrast, the traditional method of looking at k evaluations requires Omega(k log(k)) bits. We also show that our result is optimal for linear methods, even up to the leading constants. Our motivation comes from the use of Reed-Solomon (RS) codes for distributed storage systems, in particular for the exact repair problem. The traditional use of RS codes in this setting is analogous to the traditional interpolation problem. Each node in a system stores an evaluation of f, and if one node fails we can recover it by reading k other nodes. However, each node is free to send less information, leading to the modified problem above. The quickly-developing field of regenerating codes has yielded several codes which take advantage of this freedom. However, these codes are not RS codes, and RS codes are still often used in practice; in 2011, Dimakis et al. asked how well RS codes could perform in this setting. Our results imply that RS codes can also take advantage of this freedom to download partial symbols. In some parameter regimes---those with small levels of sub-packetization---our scheme for RS codes outperforms all known regenerating codes. Even with a high degree of sub-packetization, our methods give non-trivial schemes, and we give an improved repair scheme for a specific (14,10)-RS code used in the Facebook Hadoop Analytics cluster.

Publisher's Version Article Search
Efficiently Decoding Reed-Muller Codes from Random Errors
Ramprasad Saptharishi, Amir Shpilka, and Ben Lee Volk
(Tel Aviv University, Israel)
Reed-Muller codes encode an m-variate polynomial of degree r by evaluating it on all points in {0,1}m. We denote this code by RM(m,r). The minimal distance of RM(m,r) is 2mr and so it cannot correct more than half that number of errors in the worst case. For random errors one may hope for a better result.
In this work we give an efficient algorithm (in the block length n=2m) for decoding random errors in Reed-Muller codes far beyond the minimal distance. Specifically, for low rate codes (of degree r=o(√m)) we can correct a random set of (1/2−o(1))n errors with high probability. For high rate codes (of degree mr for r=o(√m/logm)), we can correct roughly mr/2 errors.
More generally, for any integer r, our algorithm can correct any error pattern in RM(m,m−(2r+2)) for which the same erasure pattern can be corrected in RM(m,m−(r+1)). The results above are obtained by applying recent results of Abbe, Shpilka and Wigderson (STOC, 2015), Kumar and Pfister (2015) and Kudekar et al. (2015) regarding the ability of Reed-Muller codes to correct random erasures.
The algorithm is based on solving a carefully defined set of linear equations and thus it is significantly different than other algorithms for decoding Reed-Muller codes that are based on the recursive structure of the code. It can be seen as a more explicit proof of a result of Abbe et al. that shows a reduction from correcting erasures to correcting errors, and it also bares some similarities with the famous Berlekamp-Welch algorithm for decoding Reed-Solomon codes.

Publisher's Version Article Search

Session 3B

Optimal Principal Component Analysis in Distributed and Streaming Models
Christos Boutsidis, David P. Woodruff, and Peilin Zhong
(Goldman Sachs, USA; IBM Research, USA; Tsinghua University, China)
This paper studies the Principal Component Analysis (PCA) problem in the distributed and streaming models of computation. Given a matrix ARm×n, a rank parameter k<rank(A), and an accuracy parameter 0<ε<1, we want to output an m×k orthonormal matrix U for which ||A-UUTA||2F≤(1+ε)||A-Ak||2F where AkRm×n is the best rank-k approximation to A.
Our contributions are summarized as follows: 1. In the arbitrary partition distributed model of Kannan et al. (COLT 2014), each of s machines holds a matrix Ai and AAi. Each machine should output U. Kannan et al. achieve O(skm/ε)+poly(sk/ε) words (of O(log(nm)) bits) communication. We obtain the improved bound of O(skm)+poly(sk/ε) words, and show an optimal (up to low order terms) Ω(skm) lower bound. This resolves an open question in the literature. A poly(ε-1) dependence is known to be required, but we separate this dependence from m.
2. In a more specific distributed model where each server receives a subset of columns of A, we bypass the above lower bound when A is φ-sparse in each column. Here we obtain an O(skφ/ε)+poly(sk/ε) word protocol. Our communication is independent of the matrix dimensions, and achieves the guarantee that each server, in addition to outputting U, outputs a subset of O(k/ε) columns of A containing a U in its span (that is, for the first time, we solve distributed column subset selection). Additionally, we show a matching Ω(skφ/ε) lower bound for distributed column subset selection. Achieving our communication bound when A is sparse in general but not sparse in each column, is impossible.
3. In the streaming model of computation, in which the columns of the matrix A arrive one at a time, an algorithm of Liberty (KDD, 2013) with an improved analysis by Ghashami and Phillips (SODA, 2014) achieves O(km/ε) "real numbers" space complexity. We improve this result, since our one-pass streaming PCA algorithm achieves an O(km/ε)+poly(k/ε) word space upper bound. This almost matches a known Ω(km/ε) bit lower bound of Woodruff (NIPS, 2014). We show that with two passes over the columns of A one can achieve an O(km)+poly(k/ε) word space upper bound; another lower bound of Woodruff (NIPS, 2014) shows that this is optimal for any constant number of passes (up to the poly(k/ε) term and the distinction between words versus bits).
4. Finally, in turnstile streams, in which we receive entries of A one at a time in an arbitrary order, we describe an algorithm with O((m+n)kε-1) words of space. This improves the O((m+n)ε-2)kε-2) upper bound of Clarkson and Woodruff (STOC 2009), and matches their Ω((m+n)kε-1) word lower bound.
Notably, our results do not depend on the condition number or any singular value gaps of A.

Publisher's Version Article Search
Weighted Low Rank Approximations with Provable Guarantees
Ilya Razenshteyn, Zhao Song, and David P. Woodruff
(Massachusetts Institute of Technology, USA; University of Texas at Austin, USA; IBM Research, USA)
The classical low rank approximation problem is: given a matrix A, find a rank-k matrix B such that the Frobenius norm of AB is minimized. It can be solved efficiently using, for instance, the Singular Value Decomposition (SVD). If one allows randomization and approximation, it can be solved in time proportional to the number of non-zero entries of A with high probability.
Inspired by practical applications, we consider a weighted version of low rank approximation: for a non-negative weight matrix W we seek to minimize ∑i, j (Wi, j · (Ai,jBi,j))2. The classical problem is a special case of this problem when all weights are 1. Weighted low rank approximation is known to be NP-hard, so we are interested in a meaningful parametrization that would allow efficient algorithms.
In this paper we present several efficient algorithms for the case of small k and under the assumption that the weight matrix W is of low rank, or has a small number of distinct columns. An important feature of our algorithms is that they do not assume anything about the matrix A. We also obtain lower bounds that show that our algorithms are nearly optimal in these parameters. We give several applications in which these parameters are small. To the best of our knowledge, the present paper is the first to provide algorithms for the weighted low rank approximation problem with provable guarantees.
Perhaps even more importantly, our algorithms proceed via a new technique, which we call “guess the sketch”. The technique turns out to be general enough to give solutions to several other fundamental problems: adversarial matrix completion, weighted non-negative matrix factorization and tensor completion.

Publisher's Version Article Search
Sparse Fourier Transform in Any Constant Dimension with Nearly-Optimal Sample Complexity in Sublinear Time
Michael Kapralov
(EPFL, Switzerland)
We consider the problem of computing a k-sparse approximation to the Fourier transform of a length N signal. Our main result is a randomized algorithm for computing such an approximation (i.e. achieving ℓ2/ℓ2 sparse recovery guarantees using Fourier measurements) using Od(klogNloglogN) samples of the signal in time domain and Od(klogd+3 N) runtime, where d≥ 1 is the dimensionality of the Fourier transform. The sample complexity matches the Ω(klog(N/k)) lower bound for non-adaptive algorithms due to [DIPW] for any kN1−δ for a constant δ>0 up to an O(loglogN) factor. Prior to our work a result with comparable sample complexity klogN logO(1)logN and sublinear runtime was known for the Fourier transform on the line [IKP], but for any dimension d≥ 2 previously known techniques either suffered from a (logN) factor loss in sample complexity or required Ω(N) runtime.

Publisher's Version Article Search

Session 4A

Two-Source Dispersers for Polylogarithmic Entropy and Improved Ramsey Graphs
Gil Cohen
(Weizmann Institute of Science, Israel)
In his influential 1947 paper that inaugurated the probabilistic method, Erdős proved the existence of 2logn-Ramsey graphs on n vertices. Matching Erdős’ result with a constructive proof is considered a central problem in combinatorics, that has gained a significant attention in the literature. The state of the art result was obtained in the celebrated paper by Barak, Rao, Shaltiel, and Wigderson who constructed a 22(loglogn)1−α-Ramsey graph, for some small universal constant α > 0.
In this work, we significantly improve this result and construct 2(loglogn)c-Ramsey graphs, for some universal constant c. In the language of theoretical computer science, this resolves the problem of explicitly constructing dispersers for two n-bit sources with entropy (n). In fact, our disperser is a zero-error disperser that outputs a constant fraction of the entropy. Prior to this work, such dispersers could only support entropy Ω(n).

Publisher's Version Article Search
Non-malleable Extractors and Codes, with Their Many Tampered Extensions
Eshan Chattopadhyay, Vipul Goyal, and Xin Li
(University of Texas at Austin, USA; Microsoft Research, India; Johns Hopkins University, USA)
Randomness extractors and error correcting codes are fundamental objects in computer science. Recently, there have been several natural generalizations of these objects, in the context and study of tamper resilient cryptography. These are seeded non-malleable extractors, introduced by Dodis and Wichs; seedless non-malleable extractors, introduced by Cheraghchi and Guruswami; and non-malleable codes, introduced by Dziembowski, Pietrzak and Wichs. Besides being interesting on their own, they also have important applications in cryptography, e.g, privacy amplification with an active adversary, explicit non-malleable codes etc, and often have unexpected connections to their non-tampered analogues.
However, the known constructions are far behind their non-tampered counterparts. Indeed, the best known seeded non-malleable extractor requires min-entropy rate at least 0.49; while explicit constructions of non-malleable two-source extractors were not known even if both sources have full min-entropy, and was left as an open problem by Cheraghchi and Guruswami.
In this paper we make progress towards solving the above problems and other related generalizations. Our contributions are as follows.
(1) We construct an explicit seeded non-malleable extractor for polylogarithmic min-entropy. This dramatically improves all previous results and gives a simpler 2-round privacy amplification protocol with optimal entropy loss, matching the best known result. In fact, we construct more general seeded non-malleable extractors (that can handle multiple adversaries) which were used in the recent construction of explicit two-source extractors for polylogarithmic min-entropy.
(2) We construct the first explicit non-malleable two-source extractor for almost full min-entropy thus resolving the open question posed by Cheraghchi and Guruswami.
(3) We motivate and initiate the study of two natural generalizations of seedless non-malleable extractors and non-malleable codes, where the sources or the codeword may be tampered many times.
By using the connection found by Cheraghchi and Guruswami and providing efficient sampling algorithms, we obtain the first explicit non-malleable codes with tampering degree t, with near optimal rate and error. We call these stronger notions one-many and many-manynon-malleable codes. This provides a stronger information theoretic analogue of a primitive known as continuous non-malleable codes.
Our basic technique used in all of our constructions can be seen as inspired, in part, by the techniques previously used to construct cryptographic non-malleable commitments.

Publisher's Version Article Search
Extractors for Sumset Sources
Eshan Chattopadhyay and Xin Li
(University of Texas at Austin, USA; Johns Hopkins University, USA)
We propose a new model of weak random sources which we call sumset sources. A sumset source X is the sum of C independent sources, with each source on n bits source having min-entropy k. We show that extractors for this class of sources can be used to give extractors for most classes of weak sources that have been studied previously, including independent sources, affine sources (which generalizes oblivious bit-fixing sources), small space sources, total entropy independent sources, and interleaved sources. This provides a unified approach for randomness extraction.
A known extractor for this class of sources, prior to our work, is the Paley graph function introduced by Chor and Goldreich, which works for the sum of 2 independent sources, where one has min-entropy at least 0.51n and the other has logarithmic min-entropy. To the best of our knowledge, the only other known construction is from the work of Kamp, Rao, Vadhan and Zuckerman, which can extract from the sum of exponentially many independent sources.
Our main result is an explicit extractor for the sum of C independent sources for some large enough constant C, where each source has polylogarithmic min-entropy. We then use this extractor to obtain improved extractors for other well studied classes of sources including small-space sources, affine sources and interleaved sources.

Publisher's Version Article Search

Session 4B

Parallel Exhaustive Search without Coordination
Pierre Fraigniaud, Amos Korman, and Yoav Rodeh
(CNRS, France; University of Paris Diderot, France; Weizmann Institute of Science, Israel)
We analyse parallel algorithms in the context of exhaustive search over totally ordered sets. Imagine an infinite list of “boxes”, with a “treasure” hidden in one of them, where the boxes’ order reflects the importance of finding the treasure in a given box. At each time step, a search protocol executed by a searcher has the ability to peek into one box, and see whether the treasure is present or not. Clearly, the best strategy of a single searcher would be to open the boxes one by one, in increasing order. Moreover, by equally dividing the workload between them, k searchers can trivially find the treasure k times faster than one searcher. However, this straightforward strategy is very sensitive to failures (e.g., crashes of processors), and overcoming this issue seems to require a large amount of communication. We therefore address the question of designing parallel search algorithms maximizing their speed-up and maintaining high levels of robustness, while minimizing the amount of resources for coordination. Based on the observation that algorithms that avoid communication are inherently robust, we focus our attention on identifying the best running time performance of non-coordinating algorithms. Specifically, we devise non-coordinating algorithms that achieve a speed-up of 9/8 for two searchers, a speed-up of 4/3 for three searchers, and in general, a speed-up of k/4(1+1/k)2 for any k≥ 1 searchers. Thus, asymptotically, the speed-up is only four times worse compared to the case of full coordination. Moreover, these bounds are tight in a strong sense as no non-coordinating search algorithm can achieve better speed-ups. Our algorithms are surprisingly simple and hence applicable. However they are memory intensive and so we suggest a practical, memory efficient version, with a speed-up of (k2 − 1)/4k. That is, it is only a factor of (k+1)/(k−1) slower than the optimal algorithm. Overall, we highlight that, in faulty contexts in which coordination between the searchers is technically difficult to implement, intrusive with respect to privacy, and/or costly in term of resources, it might well be worth giving up on coordination, and simply run our non-coordinating exhaustive search algorithms.

Publisher's Version Article Search
Beyond Matroids: Secretary Problem and Prophet Inequality with General Constraints
Aviad Rubinstein
(University of California at Berkeley, USA)
We study generalizations of the ``Prophet Inequality'' and ``Secretary Problem'', where the algorithm is restricted to an arbitrary downward-closed set system. For 0,1 values, we give O(n)-competitive algorithms for both problems. This is close to the Omega(n/log n) lower bound due to Babaioff, Immorlica, and Kleinberg. For general values, our results translate to O(log(n) log(r))-competitive algorithms, where r is the cardinality of the largest feasible set. This resolves (up to the O(loglog(n) log(r)) factor) an open question posed to us by Bobby Kleinberg.

Publisher's Version Article Search
Online Matching: Haste Makes Waste!
Yuval Emek, Shay Kutten, and Roger Wattenhofer
(Technion, Israel; ETH Zurich, Switzerland)
This paper studies a new online problem, referred to as min-cost perfect matching with delays (MPMD), defined over a finite metric space (i.e., a complete graph with positive edge weights obeying the triangle inequality) M that is known to the algorithm in advance. Requests arrive in a continuous time online fashion at the points of M and should be served by matching them to each other. The algorithm is allowed to delay its request matching commitments, but this does not come for free: the total cost of the algorithm is the sum of metric distances between matched requests plus the sum of times each request waited since it arrived until it was matched. A randomized online MPMD algorithm is presented whose competitive ratio is O (log2 n + logΔ), where n is the number of points in M and Δ is its aspect ratio. The analysis is based on a machinery developed in the context of a new stochastic process that can be viewed as two interleaved Poisson processes; surprisingly, this new process captures precisely the behavior of our algorithm. A related problem in which the algorithm is allowed to clear any unmatched request at a fixed penalty is also addressed. It is suggested that the MPMD problem is merely the tip of the iceberg for a general framework of online problems with delayed service that captures many more natural problems.

Publisher's Version Article Search

Session 5

A Tight Space Bound for Consensus
Leqi Zhu
(University of Toronto, Canada)
Existing n-process randomized wait-free (and obstruction-free) consensus protocols from registers all use at least n registers. In 1992, it was proved that such protocols must use Omega(sqrt(n)) registers. Recently, this was improved to Omega(n) registers in the anonymous setting, where processes do not have identifiers. Closing the gap in the general case, however, remained an open problem. We resolve this problem by proving that every randomized wait-free (or obstruction-free) consensus protocol for n processes must use at least n-1 registers.

Publisher's Version Article Search
The 4/3 Additive Spanner Exponent Is Tight
Amir Abboud and Greg Bodwin
(Stanford University, USA)
A spanner is a sparse subgraph that approximately preserves the pairwise distances of the original graph. It is well known that there is a smooth tradeoff between the sparsity of a spanner and the quality of its approximation, so long as distance error is measured multiplicatively. A central open question in the field is to prove or disprove whether such a tradeoff exists also in the regime of additive error. That is, is it true that for all ε>0, there is a constant kε such that every graph has a spanner on O(n1+ε) edges that preserves its pairwise distances up to +kε? Previous lower bounds are consistent with a positive resolution to this question, while previous upper bounds exhibit the beginning of a tradeoff curve: all graphs have +2 spanners on O(n3/2) edges, +4 spanners on Õ(n7/5) edges, and +6 spanners on O(n4/3) edges. However, progress has mysteriously halted at the n4/3 bound, and despite significant effort from the community, the question has remained open for all 0 < ε < 1/3.
Our main result is a surprising negative resolution of the open question, even in a highly generalized setting. We show a new information theoretic incompressibility bound: there is no function that compresses graphs into O(n4/3 − ε) bits so that distance information can be recovered within +no(1) error. As a special case of our theorem, we get a tight lower bound on the sparsity of additive spanners: the +6 spanner on O(n4/3) edges cannot be improved in the exponent, even if any subpolynomial amount of additive error is allowed. Our theorem implies new lower bounds for related objects as well; for example, the twenty-year-old +4 emulator on O(n4/3) edges also cannot be improved in the exponent unless the error allowance is polynomial.
Central to our construction is a new type of graph product, which we call the Obstacle Product. Intuitively, it takes two graphs G,H and produces a new graph G H whose shortest paths structure looks locally like H but globally like G.

Publisher's Version Article Search

Session 6A

Cell-Probe Lower Bounds for Dynamic Problems via a New Communication Model
Huacheng Yu
(Stanford University, USA)
In this paper, we develop a new communication model to prove a data structure lower bound for the dynamic interval union problem. The problem is to maintain a multiset of intervals I over [0, n] with integer coordinates, supporting the following operations: 1) insert(a, b), add an interval [a, b] to I, provided that a and b are integers in [0, n]; 2) delete(a, b), delete an (existing) interval [a, b] from I; 3) query(), return the total length of the union of all intervals in I.
It is related to the two-dimensional case of Klee’s measure problem. We prove that there is a distribution over sequences of operations with O(n) insertions and deletions, and O(n0.01) queries, for which any data structure with any constant error probability requires Ω(nlogn) time in expectation. Interestingly, we use the sparse set disjointness protocol of Håstad and Wigderson to speed up a reduction from a new kind of nondeterministic communication games, for which we prove lower bounds.
For applications, we prove lower bounds for several dynamic graph problems by reducing them from dynamic interval union.

Publisher's Version Article Search
Simulating Branching Programs with Edit Distance and Friends: Or: A Polylog Shaved Is a Lower Bound Made
Amir Abboud, Thomas Dueholm Hansen, Virginia Vassilevska Williams, and Ryan Williams
(Stanford University, USA; Aarhus University, Denmark)
A recent, active line of work achieves tight lower bounds for fundamental problems under the Strong Exponential Time Hypothesis (SETH). A celebrated result of Backurs and Indyk (STOC’15) proves that computing the Edit Distance of two sequences of length n in truly subquadratic O(n2−ε) time, for some ε>0, is impossible under SETH. The result was extended by follow-up works to simpler looking problems like finding the Longest Common Subsequence (LCS).
SETH is a very strong assumption, asserting that even linear size CNF formulas cannot be analyzed for satisfiability with an exponential speedup over exhaustive search. We consider much safer assumptions, e.g. that such a speedup is impossible for SAT on more expressive representations, like subexponential-size NC circuits. Intuitively, this assumption is much more plausible: NC circuits can implement linear algebra and complex cryptographic primitives, while CNFs cannot even approximately compute an XOR of bits.
Our main result is a surprising reduction from SAT on Branching Programs to fundamental problems in P like Edit Distance, LCS, and many others. Truly subquadratic algorithms for these problems therefore have far more remarkable consequences than merely faster CNF-SAT algorithms. For example, SAT on arbitrary o(n)-depth bounded fan-in circuits (and therefore also NC-Circuit-SAT) can be solved in (2−ε)n time.
An interesting feature of our work is that we get major consequences even from mildly subquadratic algorithms for Edit Distance or LCS. For example, we show that if an arbitrarily large polylog factor is shaved from n2 for Edit Distance then NEXP does not have non-uniform NC1 circuits.

Publisher's Version Article Search
Deterministic Decremental Single Source Shortest Paths: Beyond the O(mn) Bound
Aaron Bernstein and Shiri Chechik
(Columbia University, USA; Tel Aviv University, Israel)
In this paper we consider the decremental single-source shortest paths (SSSP) problem, where given a graph G and a source node s the goal is to maintain shortest paths between s and all other nodes in G under a sequence of online adversarial edge deletions.
In their seminal work, Even and Shiloach [JACM 1981] presented an exact solution to the problem with only O(mn) total update time over all edge deletions. Their classic algorithm was the best known result for the decremental SSSP problem for three decades, even when approximate shortest paths are allowed.
The first improvement over the Even-Shiloach algorithm was given by Bernstein and Roditty [SODA 2011], who for the case of an unweighted and undirected graph presented an approximate (1+) algorithm with constant query time and a total update time of O(n2+O(1/√logn)). This work triggered a series of new results, culminating in a recent breakthrough of Henzinger, Krinninger and Nanongkai [FOCS 14], who presented a -approximate algorithm whose total update time is near linear O(m1+ O(1/√logn)). In this paper they posed as a major open problem the question of derandomizing their result.
In fact, all known improvements over the Even-Shiloach algorithm are randomized. All these algorithms maintain some truncated shortest path trees from a small subset of nodes. While in the randomized setting it is possible to “hide” these nodes from the adversary, in the deterministic setting this is impossible: the adversary can delete all edges touching these nodes, thus forcing the algorithm to choose a new set of nodes and incur a new computation of shortest paths.
In this paper we present the first deterministic decremental SSSP algorithm that breaks the Even-Shiloach bound of O(mn) total update time, for unweighted and undirected graphs. Our algorithm is (1 + є) approximate and achieves a total update time of Õ(n2). Our algorithm can also achieve the same bounds in the incremental setting. It is worth mentioning that for dense instances where m = Ω(n2 − 1/√log(n)), our algorithm is also faster than all existing randomized algorithms.

Publisher's Version Article Search
New Deterministic Approximation Algorithms for Fully Dynamic Matching
Sayan Bhattacharya, Monika Henzinger, and Danupon Nanongkai
(Institute of Mathematical Sciences at Chennai, India; University of Vienna, Austria; KTH, Sweden)
We present two deterministic dynamic algorithms for the maximum matching problem. (1) An algorithm that maintains a (2+є)-approximate maximum matching in general graphs with O(poly(logn, 1/є)) update time. (2) An algorithm that maintains an αK approximation of the value of the maximum matching with O(n2/K) update time in bipartite graphs, for every sufficiently large constant positive integer K. Here, 1≤ αK < 2 is a constant determined by the value of K. Result (1) is the first deterministic algorithm that can maintain an o(logn)-approximate maximum matching with polylogarithmic update time, improving the seminal result of Onak et al. [STOC 2010]. Its approximation guarantee almost matches the guarantee of the best randomized polylogarithmic update time algorithm [Baswana et al. FOCS 2011]. Result (2) achieves a better-than-two approximation with arbitrarily small polynomial update time on bipartite graphs. Previously the best update time for this problem was O(m1/4) [Bernstein et al. ICALP 2015], where m is the current number of edges in the graph.

Publisher's Version Article Search

Session 6B

Algorithmic Bayesian Persuasion
Shaddin Dughmi and Haifeng Xu
(University of Southern California, USA)
Persuasion, defined as the act of exploiting an informational advantage in order to effect the decisions of others, is ubiquitous. Indeed, persuasive communication has been estimated to account for almost a third of all economic activity in the US. This paper examines persuasion through a computational lens, focusing on what is perhaps the most basic and fundamental model in this space: the celebrated Bayesian persuasion model of Kamenica and Gentzkow. Here there are two players, a sender and a receiver. The receiver must take one of a number of actions with a-priori unknown payoff, and the sender has access to additional information regarding the payoffs of the various actions for both players. The sender can commit to revealing a noisy signal regarding the realization of the payoffs of various actions, and would like to do so as to maximize her own payoff in expectation assuming that the receiver rationally acts to maximize his own payoff. When the payoffs of various actions follow a joint distribution (the common prior), the sender's problem is nontrivial, and its computational complexity depends on the representation of this prior. We examine the sender's optimization task in three of the most natural input models for this problem, and essentially pin down its computational complexity in each. When the payoff distributions of the different actions are i.i.d. and given explicitly, we exhibit a polynomial-time (exact) algorithmic solution, and a ``simple'' (1-1/e)-approximation algorithm. Our optimal scheme for the i.i.d. setting involves an analogy to auction theory, and makes use of Border's characterization of the space of reduced-forms for single-item auctions. When action payoffs are independent but non-identical with marginal distributions given explicitly, we show that it is #P-hard to compute the optimal expected sender utility. In doing so, we rule out a generalized Border's theorem, as defined by Gopalan et al, for this setting. Finally, we consider a general (possibly correlated) joint distribution of action payoffs presented by a black box sampling oracle, and exhibit a fully polynomial-time approximation scheme (FPTAS) with a bi-criteria guarantee. Our FPTAS is based on Monte-Carlo sampling, and its analysis relies on the principle of deferred decisions. Moreover, we show that this result is the best possible in the black-box model for information-theoretic reasons.

Publisher's Version Article Search
The Sample Complexity of Auctions with Side Information
Nikhil R. Devanur, Zhiyi Huang, and Christos-Alexandros Psomas
(Microsoft Research, USA; University of Hong Kong, China; University of California at Berkeley, USA)
Traditionally, the Bayesian optimal auction design problem has been considered either when the bidder values are i.i.d, or when each bidder is individually identifiable via her value distribution. The latter is a reasonable approach when the bidders can be classified into a few categories, but there are many instances where the classification of bidders is a continuum. For example, the classification of the bidders may be based on their annual income, their propensity to buy an item based on past behavior, or in the case of ad auctions, the click through rate of their ads. We introduce an alternate model that captures this aspect, where bidders are a priori identical, but can be distinguished based (only) on some side information the auctioneer obtains at the time of the auction. We extend the sample complexity approach of Dhangwatnotai et al. and Cole and Roughgarden to this model and obtain almost matching upper and lower bounds. As an aside, we obtain a revenue monotonicity lemma which may be of independent interest. We also show how to use Empirical Risk Minimization techniques to improve the sample complexity bound of Cole and Roughgarden for the non-identical but independent value distribution case.

Publisher's Version Article Search
Do Prices Coordinate Markets?
Justin Hsu, Jamie Morgenstern, Ryan Rogers, Aaron Roth, and Rakesh Vohra
(University of Pennsylvania, USA)
Walrasian equilibrium prices have a remarkable property: they allow each buyer to purchase a bundle of goods that she finds the most desirable, while guaranteeing that the induced allocation over all buyers will globally maximize social welfare. However, this clean story has two caveats. * First, the prices may induce indifferences. In fact, the minimal equilibrium prices necessarily induce indifferences. Accordingly, buyers may need to coordinate with one another to arrive at a socially optimal outcome---the prices alone are not sufficient to coordinate the market. * Second, although natural procedures converge to Walrasian equilibrium prices on a fixed population, in practice buyers typically observe prices without participating in a price computation process. These prices cannot be perfect Walrasian equilibrium prices, but instead somehow reflect distributional information about the market. To better understand the performance of Walrasian prices when facing these two problems, we give two results. First, we propose a mild genericity condition on valuations under which the minimal Walrasian equilibrium prices induce allocations which result in low over-demand, no matter how the buyers break ties. In fact, under genericity the over-demand of any good can be bounded by 1, which is the best possible at the minimal prices. We demonstrate our results for unit demand valuations and give an extension to matroid based valuations (MBV), conjectured to be equivalent to gross substitute valuations (GS). Second, we use techniques from learning theory to argue that the over-demand and welfare induced by a price vector converge to their expectations uniformly over the class of all price vectors, with respective sample complexity linear and quadratic in the number of goods in the market. These results make no assumption on the form of the valuation functions. These two results imply that under a mild genericity condition, the exact Walrasian equilibrium prices computed in a market are guaranteed to induce both low over-demand and high welfare when used in a new market where agents are sampled independently from the same distribution, whenever the number of agents is larger than the number of commodities in the market.

Publisher's Version Article Search Video
A Discrete and Bounded Envy-Free Cake Cutting Protocol for Four Agents
Haris Aziz and Simon Mackenzie
(Data61, Australia; UNSW, Australia)
We consider the well-studied cake cutting problem in which the goal is to identify an envy-free allocation based on a minimal number of queries from the agents. The problem has attracted considerable attention within various branches of computer science, mathematics, and economics. Although, the elegant Selfridge-Conway envy-free protocol for three agents has been known since 1960, it has been a major open problem to obtain a bounded envy-free protocol for more than three agents. The problem has been termed the central open problem in cake cutting. We solve this problem by proposing a discrete and bounded envy-free protocol for four agents.

Publisher's Version Article Search

Session 7A

Distributed (Δ+1)-Coloring in Sublogarithmic Rounds
David G. Harris, Johannes Schneider, and Hsin-Hao Su
(University of Maryland, USA; ABB Corporate Research, USA; Massachusetts Institute of Technology, USA)
The (∆+1)-coloring problem is a fundamental symmetry breaking problem in distributed computing. We give a new randomized coloring algorithm for (∆+1)-coloring running in O(√log ∆)+ 2^O(√log log n) rounds with probability 1-1/n^Ω(1) in a graph with n nodes and maximum degree ∆. This implies that the (∆+1)-coloring problem is easier than the maximal independent set problem and the maximal matching problem, due to their lower bounds by Kuhn, Moscibroda, and Wattenhofer [PODC'04]. Our algorithm also extends to the list-coloring problem where the palette of each node contains ∆+1 colors.

Publisher's Version Article Search
A Lower Bound for the Distributed Lovász Local Lemma
Sebastian Brandt, Orr Fischer, Juho Hirvonen, Barbara Keller, Tuomo Lempiäinen, Joel Rybicki, Jukka Suomela, and Jara Uitto
(ETH Zurich, Switzerland; Tel Aviv University, Israel; Aalto University, Finland; Bitsplitters, Switzerland)
We show that any randomised Monte Carlo distributed algorithm for the Lovász local lemma requires Omega(log log n) communication rounds, assuming that it finds a correct assignment with high probability. Our result holds even in the special case of d = O(1), where d is the maximum degree of the dependency graph. By prior work, there are distributed algorithms for the Lovász local lemma with a running time of O(log n) rounds in bounded-degree graphs, and the best lower bound before our work was Omega(log* n) rounds [Chung et al. 2014].

Publisher's Version Article Search
A Deterministic Almost-Tight Distributed Algorithm for Approximating Single-Source Shortest Paths
Monika Henzinger, Sebastian Krinninger, and Danupon Nanongkai
(University of Vienna, Austria; Max Planck Institute for Informatics, Germany; KTH, Sweden)
We present a deterministic (1+o(1))-approximation O(n1/2+o(1)+D1+o(1))-time algorithm for solving the single-source shortest paths problem on distributed weighted networks (the CONGEST model); here n is the number of nodes in the network and D is its (hop) diameter. This is the first non-trivial deterministic algorithm for this problem. It also improves (i) the running time of the randomized (1+o(1))-approximation Õ(n1/2D1/4+D)-time algorithm of Nanongkai [STOC 2014] by a factor of as large as n1/8, and (ii) the O−1logє−1)-approximation factor of Lenzen and Patt-Shamir’s Õ(n1/2+є+D)-time algorithm [STOC 2013] within the same running time. Our running time matches the known time lower bound of Ω(n1/2/logn + D) [Das Sarma et al. STOC 2011] modulo some lower-order terms, thus essentially settling the status of this problem which was raised at least a decade ago [Elkin SIGACT News 2004]. It also implies a (2+o(1))-approximation O(n1/2+o(1)+D1+o(1))-time algorithm for approximating a network’s weighted diameter which almost matches the lower bound by Holzer et al. [PODC 2012].
In achieving this result, we develop two techniques which might be of independent interest and useful in other settings: (i) a deterministic process that replaces the “hitting set argument” commonly used for shortest paths computation in various settings, and (ii) a simple, deterministic, construction of an (no(1), o(1))-hop set of size O(n1+o(1)). We combine these techniques with many distributed algorithmic techniques, some of which from problems that are not directly related to shortest paths, e.g. ruling sets [Goldberg et al. STOC 1987], source detection [Lenzen, Peleg PODC 2013], and partial distance estimation [Lenzen, Patt-Shamir PODC 2015]. Our hop set construction also leads to single-source shortest paths algorithms in two other settings: (i) a (1+o(1))-approximation O(no(1))-time algorithm on congested cliques, and (ii) a (1+o(1))-approximation O(no(1)logW)-pass O(n1+o(1)logW)-space streaming algorithm, when edge weights are in {1, 2, …, W}. The first result answers an open problem in [Nanongkai, STOC 2014]. The second result partially answers an open problem raised by McGregor in 2006 [, Problem 14].

Publisher's Version Article Search
Contention Resolution with Log-Logstar Channel Accesses
Michael A. Bender, Tsvi Kopelowitz, Seth Pettie, and Maxwell Young
(Stony Brook University, USA; University of Michigan, USA; Mississippi State University, USA)
For decades, randomized exponential backoff has provided a critical algorithmic building block in situations where multiple devices seek access to a shared resource. Surprisingly, despite this history, the performance of standard backoff is poor under worst-case scheduling of demands on the resource: (i) subconstant throughput can occur under plausible scenarios, and (ii) each of N devices requires Omega(log N) access attempts before obtaining the resource.
In this paper, we address these shortcomings by offering a new backoff protocol for a shared communications channel that guarantees expected constant throughput with only O(log(log* N)) access attempts in expectation. Central to this result are new algorithms for approximate counting and leader election with the same performance guarantees.

Publisher's Version Article Search

Session 7B

Fault Tolerant Subgraph for Single Source Reachability: Generic and Optimal
Surender Baswana, Keerti Choudhary, and Liam Roditty
(IIT Kanpur, India; Bar-Ilan University, Israel)
Let G=(V,E) be an n-vertices m-edges directed graph. Let sV be any designated source vertex. We address the problem of single source reachability (SSR) from s in presence of failures of vertices/edges. We show that for every k≥ 1, there is a subgraph H of G with at most 2k n edges that preserves the reachability from s even after the failure of any k edges. Formally, given a set F of k edges, a vertex uV is reachable from s in GF if and only if u is reachable from s in HF. We call H a k-Fault Tolerant Reachability Subgraph (k-FTRS). We prove also a matching lower bound of Ω(2kn) for such subgraphs. Our results extend to vertex failures without any extra overhead. The general construction of k-FTRS is interesting from several different perspectives. From the Graph theory perspective it reveals a separation between SSR and single source shortest paths (SSSP) in directed graphs. More specifically, in the case of SSSP in weighted directed graphs, there is a lower bound of Ω(m) even for a single edge failure. In the case of unweighted graphs there is a lower bound of Ω(n3/2) edges, again, even for a single edge failure. There is also a matching upper bound but nothing is known for two or more failures in the directed graphs. From the Algorithms perspective it implies fault tolerant solutions to other interesting problems, namely, (i) verifying if the strong connectivity of a graph is preserved after k edge or vertex failures, (ii) computing a dominator tree of a graph after k-failures. From the perspective of Techniques it makes an interesting usage of the concept of farthest min-cut which was already introduced by Ford and Fulkerson in their pioneering work on flows and cuts. We show that there is a close relationship between the farthest min-cut and the k-FTRS. We believe that our new technique is of independent interest.

Publisher's Version Article Search
Deterministic and Probabilistic Binary Search in Graphs
Ehsan Emamjomeh-Zadeh, David Kempe, and Vikrant Singhal
(University of Southern California, USA)
We consider the following natural generalization of Binary Search: in a given undirected, positively weighted graph, one vertex is a target. The algorithm’s task is to identify the target by adaptively querying vertices. In response to querying a node q, the algorithm learns either that q is the target, or is given an edge out of q that lies on a shortest path from q to the target. We study this problem in a general noisy model in which each query independently receives a correct answer with probability p > 1/2 (a known constant), and an (adversarial) incorrect one with probability 1 − p.
Our main positive result is that when p = 1 (i.e., all answers are correct), log2 n queries are always sufficient. For general p, we give an (almost information-theoretically optimal) algorithm that uses, in expectation, no more than (1 − δ) logn/1 − H(p) + o(logn) + O(log2 (1/δ)) queries, and identifies the target correctly with probability at leas 1 − δ. Here, H(p) = −(p logp + (1 − p) log(1 − p)) denotes the entropy. The first bound is achieved by the algorithm that iteratively queries a 1-median of the nodes not ruled out yet; the second bound by careful repeated invocations of a multiplicative weights algorithm.
Even for p = 1, we show several hardness results for the problem of determining whether a target can be found using K queries. Our upper bound of log2 n implies a quasipolynomial-time algorithm for undirected connected graphs; we show that this is best-possible under the Strong Exponential Time Hypothesis (SETH). Furthermore, for directed graphs, or for undirected graphs with non-uniform node querying costs, the problem is PSPACE-complete. For a semi-adaptive version, in which one may query r nodes each in k rounds, we show membership in Σ2k−1 in the polynomial hierarchy, and hardness for Σ2k−5.

Publisher's Version Article Search
Ramanujan Coverings of Graphs
Chris Hall, Doron Puder, and William F. Sawin
(University of Wyoming, USA; Institute for Advanced Study at Princeton, USA; Princeton University, USA)
Let G be a finite connected graph, and let ρ be the spectral radius of its universal cover. For example, if G is k-regular then ρ=2√k−1. We show that for every r, there is an r-covering (a.k.a. an r-lift) of G where all the new eigenvalues are bounded from above by ρ. It follows that a bipartite Ramanujan graph has a Ramanujan r-covering for every r. This generalizes the r=2 case due to Marcus, Spielman and Srivastava (2013).
Every r-covering of G corresponds to a labeling of the edges of G by elements of the symmetric group Sr. We generalize this notion to labeling the edges by elements of various groups and present a broader scenario where Ramanujan coverings are guaranteed to exist.
In particular, this shows the existence of richer families of bipartite Ramanujan graphs than was known before. Inspired by Marcus-Spielman-Srivastava, a crucial component of our proof is the existence of interlacing families of polynomials for complex reflection groups. The core argument of this component is taken from Marcus-Spielman-Srivastava (2015).
Another important ingredient of our proof is a new generalization of the matching polynomial of a graph. We define the r-th matching polynomial of G to be the average matching polynomial of all r-coverings of G. We show this polynomial shares many properties with the original matching polynomial. For example, it is real rooted with all its roots inside [−ρ,ρ].

Publisher's Version Article Search Info
Enumerating Parametric Global Minimum Cuts by Random Interleaving
David R. Karger
(Massachusetts Institute of Technology, USA)
Recently, Aissi et al. gave new counting and algorithmic bounds for parametric minimum cuts in a graph, where each edge cost is a linear combination of multiple cost criteria and different cuts become minimum as the coefficients of the linear combination are varied. In this article, we derive better bounds using a mathematically simpler argument. We provide faster algorithms for enumerating these cuts. We give a lower bound showing our upper bounds have roughly the right degree. Our results also immediately generalize to parametric versions of other problems solved by the Contraction Algorithm, including approximate min-cuts, multi-way cuts, and a matroid optimization problem. We also give a first generalization to nonlinear parametric minimum cuts.

Publisher's Version Article Search

Session 8A

Improved Approximation for Node-Disjoint Paths in Planar Graphs
Julia Chuzhoy, David H. K. Kim, and Shi Li
(Toyota Technological Institute at Chicago, USA; University of Chicago, USA; State University of New York at Buffalo, USA)
We study the classical Node-Disjoint Paths (NDP) problem: given an n-vertex graph G and a collection =(s1,t1),…,(sk,tk) of pairs of vertices of G called demand pairs, find a maximum-cardinality set of node-disjoint paths connecting the demand pairs. NDP is one of the most basic routing problems, that has been studied extensively. Despite this, there are still wide gaps in our understanding of its approximability: the best currently known upper bound of O(√n) on its approximation ratio is achieved via a simple greedy algorithm, while the best current negative result shows that the problem does not have a better than Ω(log1/2−δn)-approximation for any constant δ, under standard complexity assumptions. Even for planar graphs no better approximation algorithms are known, and to the best of our knowledge, the best negative bound is APX-hardness. Perhaps the biggest obstacle to obtaining better approximation algorithms for NDP is that most currently known approximation algorithms for this type of problems rely on the standard multicommodity flow relaxation, whose integrality gap is Ω(√n) for NDP, even in planar graphs. In this paper, we break the barrier of O(√n) on the approximability of NDP in planar graphs and obtain an Õ(n9/19)-approximation. We introduce a new linear programming relaxation of the problem, and a number of new techniques, that we hope will be helpful in designing more powerful algorithms for this and related problems.

Publisher's Version Article Search Info
A PTAS for Planar Group Steiner Tree via Spanner Bootstrapping and Prize Collecting
MohammadHossein Bateni, Erik D. Demaine, MohammadTaghi Hajiaghayi, and Dániel Marx
(Google, USA; Massachusetts Institute of Technology, USA; University of Maryland at College Park, USA; Hungarian Academy of Sciences, Hungary)
We present the first polynomial-time approximation scheme (PTAS), i.e., (1+ε)-approximation algorithm for any constant ε> 0, for the planar group Steiner tree problem (in which each group lies on a boundary of a face). This result improves on the best previous approximation factor of O(logn (loglogn)O(1)). We achieve this result via a novel and powerful technique called spanner bootstrapping, which allows one to bootstrap from a superconstant approximation factor (even superpolynomial in the input size) all the way down to a PTAS. This is in contrast with the popular existing approach for planar PTASs of constructing light-weight spanners in one iteration, which notably requires a constant-factor approximate solution to start from. Spanner bootstrapping removes one of the main barriers for designing PTASs for problems which have no known constant-factor approximation (even on planar graphs), and thus can be used to obtain PTASs for several difficult-to-approximate problems.
Our second major contribution required for the planar group Steiner tree PTAS is a spanner construction, which reduces the graph to have total weight within a factor of the optimal solution while approximately preserving the optimal solution. This is particularly challenging because group Steiner tree requires deciding which terminal in each group to connect by the tree, making it much harder than recent previous approaches to construct spanners for planar TSP by Klein [SIAM J. Computing 2008], subset TSP by Klein [STOC 2006], Steiner tree by Borradaile, Klein, and Mathieu [ACM Trans. Algorithms 2009], and Steiner forest by Bateni, Hajiaghayi, and Marx [J. ACM 2011] (and its improvement to an efficient PTAS by Eisenstat, Klein, and Mathieu [SODA 2012]. The main conceptual contribution here is realizing that selecting which terminals may be relevant is essentially a complicated prize-collecting process: we have to carefully weigh the cost and benefits of reaching or avoiding certain terminals in the spanner. Via a sequence of involved prize-collecting procedures, we can construct a spanner that reaches a set of terminals that is sufficient for an almost-optimal solution.
Our PTAS for planar group Steiner tree implies the first PTAS for geometric Euclidean group Steiner tree with obstacles, as well as a (2+)-approximation algorithm for group TSP with obstacles, improving over the best previous constant-factor approximation algorithms. By contrast, we show that planar group Steiner forest, a slight generalization of planar group Steiner tree, is APX-hard on planar graphs of treewidth 3, even if the groups are pairwise disjoint and every group is a vertex or an edge.

Publisher's Version Article Search
Approximating Connectivity Domination in Weighted Bounded-Genus Graphs
Vincent Cohen-Addad, Éric Colin de Verdière, Philip N. Klein, Claire Mathieu, and David Meierfrankenfeld
(ENS, France; CNRS, France; Brown University, USA)
We present a framework for addressing several problems on weighted planar graphs and graphs of bounded genus. With that framework, we derive polynomial-time approximation schemes for the following problems in planar graphs or graphs of bounded genus: edge-weighted tree cover and tour cover; vertex-weighted connected dominating set, max-weight-leaf spanning tree, and connected vertex cover. In addition, we obtain a polynomial-time approximation scheme for feedback vertex set in planar graphs. These are the first polynomial-time approximation schemes for all those problems in weighted embedded graphs. (For unweighted versions of some of these problems, polynomial-time approximation schemes were previously given using bidimensionality.)

Publisher's Version Article Search
Routing under Balance
Alina Ene, Gary Miller, Jakub Pachocki, and Aaron Sidford
(University of Warwick, UK; Carnegie Mellon University, USA; Microsoft Research, USA)
We introduce the notion of balance for directed graphs: a weighted directed graph is α-balanced if for every cut SV, the total weight of edges going from S to VS is within factor α of the total weight of edges going from VS to S. Several important families of graphs are nearly balanced, in particular, Eulerian graphs (with α = 1) and residual graphs of (1+є)-approximate undirected maximum flows (with α=O(1/є)).
We use the notion of balance to give a more fine-grained understanding of several well-studied routing questions that are considerably harder in directed graphs. We first revisit oblivious routings in directed graphs. Our main algorithmic result is an oblivious routing scheme for single-source instances that achieve an O(α · log3 n / loglogn) competitive ratio. In the process, we make several technical contributions which may be of independent interest. In particular, we give an efficient algorithm for computing low-radius decompositions of directed graphs parameterized by balance. We also define and construct low-stretch arborescences, a generalization of low-stretch spanning trees to directed graphs.
On the negative side, we present new lower bounds for oblivious routing problems on directed graphs. We show that the competitive ratio of oblivious routing algorithms for directed graphs is Ω(n) in general; this result improves upon the long-standing best known lower bound of Ω(√n) by Hajiaghayi et al. We also show that our restriction to single-source instances is necessary by showing an Ω(√n) lower bound for multiple-source oblivious routing in Eulerian graphs.
We also study the maximum flow problem in balanced directed graphs with arbitrary capacities. We develop an efficient algorithm that finds an (1+є)-approximate maximum flows in α-balanced graphs in time O(m α2 / є2). We show that, using our approximate maximum flow algorithm, we can efficiently determine whether a given directed graph is α-balanced. Additionally, we give an application to the directed sparsest cut problem.

Publisher's Version Article Search

Session 8B

Near-Optimal Small-Depth Lower Bounds for Small Distance Connectivity
Xi Chen, Igor C. Oliveira, Rocco A. Servedio, and Li-Yang Tan
(Columbia University, USA; Charles University in Prague, Czechia; Toyota Technological Institute at Chicago, USA)
We show that any depth-d circuit for determining whether an n-node graph has an s-to-t path of length at most k must have size nΩ(k1/d/d) when k(n) ≤ n1/5, and nΩ(k1/5d/d) when k(n)≤ n. The previous best circuit size lower bounds were nkexp(−O(d)) (by Beame, Impagliazzo, and Pitassi (Computational Complexity 1998)) and nΩ((logk)/d) (following from a recent formula size lower bound of Rossman (STOC 2014)). Our lower bound is quite close to optimal, as a simple construction gives depth-d circuits of size nO(k2/d) for this problem (and strengthening our bound even to nkΩ(1/d) would require proving that undirected connectivity is not in NC1).
Our proof is by reduction to a new lower bound on the size of small-depth circuits computing a skewed variant of the “Sipser functions” that have played an important role in classical circuit lower bounds. A key ingredient in our proof of the required lower bound for these Sipser-like functions is the use of random projections, an extension of random restrictions which were recently employed by Rossman, Servedio, and Tan (FOCS 2015). Random projections allow us to obtain sharper quantitative bounds while employing simpler arguments, both conceptually and technically, than in the previous works.

Publisher's Version Article Search
On the Size of Homogeneous and of Depth Four Formulas with Low Individual Degree
Neeraj Kayal, Chandan Saha, and Sébastien Tavenas
(Microsoft Research, India; Indian Institute of Science, India)
Let r be an integer. Let us call a polynomial f as a multi-r-ic polynomial if the degree of f with respect to any variable is at most r (this generalizes the notion of multilinear polynomials). We investigate arithmetic circuits in which the output is syntactically forced to be a multi-r-ic polynomial and refer to these as multi-r-ic circuits. Specifically, first define the formal degree of a node a with respect to a variable x inductively as follows. For a leaf it is 1 if a is labelled with x and zero otherwise; for an internal node labelled with * (respectively +) it is the sum of (respectively the maximum of) the formal degrees of the children with respect to x. We call an arithmetic circuit as a multi-r-ic circuit if the formal degree of the output node with respect to any variable is at most r. We prove lower bounds for various subclasses of multi-r-ic circuits.

Publisher's Version Article Search
Super-Linear Gate and Super-Quadratic Wire Lower Bounds for Depth-Two and Depth-Three Threshold Circuits
Daniel M. Kane and Ryan Williams
(University of California at San Diego, USA; Stanford University, USA)
In order to formally understand the power of neural computing, we first need to crack the frontier of threshold circuits with two and three layers, a regime that has been surprisingly intractable to analyze. We prove the first super-linear gate lower bounds and the first super-quadratic wire lower bounds for depth-two linear threshold circuits with arbitrary weights, and depth-three majority circuits computing an explicit function. (1) We prove that for all ε ≪ √log(n)/n, the linear-time computable Andreev’s function cannot be computed on a (1/2+ε)-fraction of n-bit inputs by depth-two circuits of o3 n3/2/log3 n) gates, nor can it be computed with o3 n5/2/log7/2 n) wires. This establishes an average-case “size hierarchy” for threshold circuits, as Andreev’s function is computable by uniform depth-two circuits of o(n3) linear threshold gates, and by uniform depth-three circuits of O(n) majority gates. (2) We present a new function in P based on small-biased sets, which we prove cannot be computed by a majority vote of depth-two threshold circuits of o(n3/2/log3 n) gates, nor with o(n5/2/log7/2n) wires. (3) We give tight average-case (gate and wire) complexity results for computing PARITY with depth-two threshold circuits; the answer turns out to be the same as for depth-two majority circuits. The key is a new method for analyzing random restrictions to linear threshold functions. Our main analytical tool is the Littlewood-Offord Lemma from additive combinatorics.

Publisher's Version Article Search
Poly-logarithmic Frege Depth Lower Bounds via an Expander Switching Lemma
Toniann Pitassi, Benjamin Rossman, Rocco A. Servedio, and Li-Yang Tan
(University of Toronto, Canada; National Institute of Informatics, Japan; Columbia University, USA; Toyota Technological Institute at Chicago, USA)
We show that any polynomial-size Frege refutation of a certain linear-size unsatisfiable 3-CNF formula over n variables must have depth Ω(√logn). This is an exponential improvement over the previous best results (Pitassi et al. 1993, Krajíček et al. 1995, Ben-Sasson 2002) which give Ω(loglogn) lower bounds.
The 3-CNF formulas which we use to establish this result are Tseitin contradictions on 3-regular expander graphs. In more detail, our main result is a proof that for every d, any depth-d Frege refutation of the Tseitin contradiction over these n-node graphs must have size nΩ((logn)/d2). A key ingredient of our approach is a new switching lemma for a carefully designed random restriction process over these expanders. These random restrictions reduce a Tseitin instance on a 3-regular n-node expander to a Tseitin instance on a random subgraph which is a topological embedding of a 3-regular n′-node expander, for some n′ which is not too much less than n. Our result involves Ω(√logn) iterative applications of this type of random restriction.

Publisher's Version Article Search

Session 9

Reed-Muller Codes Achieve Capacity on Erasure Channels
Shrinivas Kudekar, Santhosh Kumar, Marco Mondelli, Henry D. Pfister, Eren Şaşoğlu, and Rüdiger Urbanke
(Qualcomm Research, USA; Texas A&M University, USA; EPFL, Switzerland; Duke University, USA; Intel, USA)
We introduce a new approach to proving that a sequence of deterministic linear codes achieves capacity on an erasure channel under maximum a posteriori decoding. Rather than relying on the precise structure of the codes, our method exploits code symmetry. In particular, the technique applies to any sequence of linear codes where the block lengths are strictly increasing, the code rates converge, and the permutation group of each code is doubly transitive. In a nutshell, we show that symmetry alone implies near-optimal performance.
An important consequence of this result is that a sequence of Reed-Muller codes with increasing block length and converging rate achieves capacity. This possibility has been suggested previously in the literature, but it has only been proven for cases where the limiting code rate is 0 or 1. Moreover, these results extend naturally to affine-invariant codes and, thus, to all extended primitive narrow-sense BCH codes. This is used to resolve, in the affirmative, the existence question for capacity-achieving sequences of binary cyclic codes. The primary tools used in the proofs are the sharp threshold property for symmetric monotone boolean functions and the area theorem for extrinsic information transfer (EXIT) functions.

Publisher's Version Article Search
Explicit Two-Source Extractors and Resilient Functions
Eshan Chattopadhyay and David Zuckerman
(University of Texas at Austin, USA)
We explicitly construct an extractor for two independent sources on n bits, each with polylogarithmic min-entropy. Our extractor outputs one bit and has polynomially small error. The best previous extractor, by Bourgain, required each source to have min-entropy .499n.
A key ingredient in our construction is an explicit construction of a monotone, almost-balanced Boolean functions that are resilient to coalitions. In fact, our construction is stronger in that it gives an explicit extractor for a generalization of non-oblivious bit-fixing sources on n bits, where some unknown n-q bits are chosen almost polylogarithmic-wise independently, and the remaining q bits are chosen by an adversary as an arbitrary function of the n-q bits. The best previous construction, by Viola, achieved q quadratically smaller than our result.
Our explicit two-source extractor directly implies improved constructions of a K-Ramsey graph over N vertices, improving bounds obtained by Barak et al. and matching independent work by Cohen.

Publisher's Version Article Search
Graph Isomorphism in Quasipolynomial Time [Extended Abstract]
László Babai
(University of Chicago, USA)
We show that the Graph Isomorphism (GI) problem and the more general problems of String Isomorphism (SI) andCoset Intersection (CI) can be solved in quasipolynomial(exp((logn)O(1))) time. The best previous bound for GI was exp(O( √n log n)), where n is the number of vertices (Luks, 1983); for the other two problems, the bound was similar, exp(O~(√ n)), where n is the size of the permutation domain (Babai, 1983). Following the approach of Luks’s seminal 1980/82 paper, the problem we actually address is SI. This problem takes two strings of length n and a permutation group G of degree n (the “ambient group”) as input (G is given by a list of generators) and asks whether or not one of the strings can be transformed into the other by some element of G. Luks’s divide-and-conquer algorithm for SI proceeds by recursion on the ambient group. We build on Luks’s framework and attack the obstructions to efficient Luks recurrence via an interplay between local and global symmetry. We construct group theoretic “local certificates” to certify the presence or absence of local symmetry, aggregate the negative certificates to canonical k-ary relations where k = O(log n), and employ combinatorial canonical partitioning techniques to split the k-ary relational structure for efficient divide-and- conquer. We show that in a well–defined sense, Johnson graphs are the only obstructions to effective canonical partitioning. The central element of the algorithm is the “local certificates” routine which is based on a new group theoretic result, the “Unaffected stabilizers lemma,” that allows us to construct global automorphisms out of local information.

Publisher's Version Article Search

Session 10A

Tight Bounds for Single-Pass Streaming Complexity of the Set Cover Problem
Sepehr Assadi, Sanjeev Khanna, and Yang Li
(University of Pennsylvania, USA)
We resolve the space complexity of single-pass streaming algorithms for approximating the classic set cover problem. For finding an α-approximate set cover (for α= o(√n)) via a single-pass streaming algorithm, we show that Θ(mn/α) space is both sufficient and necessary (up to an O(logn) factor); here m denotes number of the sets and n denotes size of the universe. This provides a strong negative answer to the open question posed by Indyk (2015) regarding the possibility of having a single-pass algorithm with a small approximation factor that uses sub-linear space. We further study the problem of estimating the size of a minimum set cover (as opposed to finding the actual sets), and establish that an additional factor of α saving in the space is achievable in this case and that this is the best possible. In other words, we show that Θ(mn2) space is both sufficient and necessary (up to logarithmic factors) for estimating the size of a minimum set cover to within a factor of α. Our algorithm in fact works for the more general problem of estimating the optimal value of a covering integer program. On the other hand, our lower bound holds even for set cover instances where the sets are presented in a random order.

Publisher's Version Article Search
Streaming Algorithms for Embedding and Computing Edit Distance in the Low Distance Regime
Diptarka Chakraborty, Elazar Goldenberg, and Michal Koucký
(IIT Kanpur, India; Charles University in Prague, Czechia)
The Hamming and the edit metrics are two common notions of measuring distances between pairs of strings x,y lying in the Boolean hypercube. The edit distance between x and y is defined as the minimum number of character insertion, deletion, and bit flips needed for converting x into y. Whereas, the Hamming distance between x and y is the number of bit flips needed for converting x to y. In this paper we study a randomized injective embedding of the edit distance into the Hamming distance with a small distortion. We show a randomized embedding with quadratic distortion. Namely, for any x,y satisfying that their edit distance equals k, the Hamming distance between the embedding of x and y is O(k2) with high probability. This improves over the distortion ratio of O( n * n) obtained by Jowhari (2012) for small values of k. Moreover, the embedding output size is linear in the input size and the embedding can be computed using a single pass over the input. We provide several applications for this embedding. Among our results we provide a one-pass (streaming) algorithm for edit distance running in space O(s) and computing edit distance exactly up-to distance s1/6. This algorithm is based on kernelization for edit distance that is of independent interest.

Publisher's Version Article Search
On Approximating Functions of the Singular Values in a Stream
Yi Li and David P. Woodruff
(Facebook, USA; IBM Research, USA)
For any real number p > 0, we nearly completely characterize the space complexity of estimating ||A||pp = ∑i=1n σip for n × n matrices A in which each row and each column has O(1) non-zero entries and whose entries are presented one at a time in a data stream model. Here the σi are the singular values of A, and when p ≥ 1, ||A||pp is the p-th power of the Schatten p-norm. We show that when p is not an even integer, to obtain a (1+є)-approximation to ||A||pp with constant probability, any 1-pass algorithm requires n1−g(є) bits of space, where g(є) → 0 as є → 0 and є > 0 is a constant independent of n. However, when p is an even integer, we give an upper bound of n1−2/p−1logn) bits of space, which holds even in the turnstile data stream model. The latter is optimal up to (є−1 logn) factors.
Our results considerably strengthen lower bounds in previous work for arbitrary (not necessarily sparse) matrices A: the previous best lower bound was Ω(logn) for p∈ (0,1), Ω(n1/p−1/2/logn) for p∈ [1,2) and Ω(n1−2/p) for p∈ (2,∞). We note for p ∈ (2, ∞), while our lower bound for even integers is the same, for other p in this range our lower bound is n1−g(є), which is considerably stronger than the previous n1−2/p for small enough constant є > 0. We obtain similar near-linear lower bounds for Ky-Fan norms, eigenvalue shrinkers, and M-estimators, many of which could have been solvable in logarithmic space prior to our work.

Publisher's Version Article Search
Beating CountSketch for Heavy Hitters in Insertion Streams
Vladimir Braverman, Stephen R. Chestnut, Nikita Ivkin, and David P. Woodruff
(Johns Hopkins University, USA; ETH Zurich, Switzerland; IBM Research, USA)
Given a stream p1, …, pm of items from a universe U, which, without loss of generality we identify with the set of integers {1, 2, …, n}, we consider the problem of returning all ℓ2-heavy hitters, i.e., those items j for which fj ≥ є √F2, where fj is the number of occurrences of item j in the stream, and F2 = ∑i ∈ [n] fi2. Such a guarantee is considerably stronger than the ℓ1-guarantee, which finds those j for which fj ≥ є m. In 2002, Charikar, Chen, and Farach-Colton suggested the CountSketch data structure, which finds all such j using Θ(log2 n) bits of space (for constant є > 0). The only known lower bound is Ω(logn) bits of space, which comes from the need to specify the identities of the items found.
In this paper we show one can achieve O(logn loglogn) bits of space for this problem. Our techniques, based on Gaussian processes, lead to a number of other new results for data streams, including: (1) The first algorithm for estimating F2 simultaneously at all points in a stream using only O(lognloglogn) bits of space, improving a natural union bound. (2) A way to estimate the ℓ norm of a stream up to additive error є √F2 with O(lognloglogn) bits of space, resolving Open Question 3 from the IITK 2006 list for insertion only streams.

Publisher's Version Article Search

Session 10B

Bipartite Perfect Matching Is in Quasi-NC
Stephen Fenner, Rohit Gurjar, and Thomas Thierauf
(University of South Carolina, USA; Aalen University, Germany)
We show that the bipartite perfect matching problem is in quasi- NC2. That is, it has uniform circuits of quasi-polynomial size nO(logn), and O(log2 n) depth. Previously, only an exponential upper bound was known on the size of such circuits with poly-logarithmic depth.
We obtain our result by an almost complete derandomization of the famous Isolation Lemma when applied to yield an efficient randomized parallel algorithm for the bipartite perfect matching problem.

Publisher's Version Article Search
Exact Algorithms via Monotone Local Search
Fedor V. Fomin, Serge Gaspers, Daniel Lokshtanov, and Saket Saurabh
(University of Bergen, Norway; UNSW, Australia; Data61, Australia; Institute of Mathematical Sciences at Chennai, India)
We give a new general approach for designing exact exponential-time algorithms for subset problems. In a subset problem the input implicitly describes a family of sets over a universe of size n and the task is to determine whether the family contains at least one set. A typical example of a subset problem is Weighted d-SAT. Here, the input is a CNF-formula with clauses of size at most d, and an integer W. The universe is the set of variables and the variables have integer weights. The family contains all the subsets S of variables such that the total weight of the variables in S does not exceed W, and setting the variables in S to 1 and the remaining variables to 0 satisfies the formula. Our approach is based on “monotone local search”, where the goal is to extend a partial solution to a solution by adding as few elements as possible. More formally, in the extension problem we are also given as input a subset X of the universe and an integer k. The task is to determine whether one can add at most k elements to X to obtain a set in the (implicitly defined) family. Our main result is that a cknO(1) time algorithm for the extension problem immediately yields a randomized algorithm for finding a solution of any size with running time O((2−1/c)n).
In many cases, the extension problem can be reduced to simply finding a solution of size at most k. Furthermore, efficient algorithms for finding small solutions have been extensively studied in the field of parameterized algorithms. Directly applying these algorithms, our theorem yields in one stroke significant improvements over the best known exponential-time algorithms for several well-studied problems, including d-Hitting Set, Feedback Vertex Set, Node Unique Label Cover, and Weighted d-SAT. Our results demonstrate an interesting and very concrete connection between parameterized algorithms and exact exponential-time algorithms.
We also show how to derandomize our algorithms at the cost of a subexponential multiplicative factor in the running time. Our derandomization is based on an efficient construction of a new pseudo-random object that might be of independent interest. Finally, we extend our methods to establish new combinatorial upper bounds and develop enumeration algorithms.

Publisher's Version Article Search
Basis Collapse for Holographic Algorithms over All Domain Sizes
Sitan Chen
(Harvard University, USA)
The theory of holographic algorithms introduced by Valiant represents a novel approach to achieving polynomial-time algorithms for seemingly intractable counting problems via a reduction to counting planar perfect matchings and a linear change of basis. Two fundamental parameters in holographic algorithms are the domain size and the basis size. Roughly, the domain size is the range of colors involved in the counting problem at hand (e.g. counting graph k-colorings is a problem over domain size k), while the basis size captures the dimensionality of the representation of those colors. A major open problem has been: for a given k, what is the smallest ℓ for which any holographic algorithm for a problem over domain size k ”collapses to” (can be simulated by) a holographic algorithm with basis size ℓ? Cai and Lu showed in 2008 that over domain size 2, basis size 1 suffices, opening the door to an extensive line of work on the structural theory of holographic algorithms over the Boolean domain. Cai and Fu later showed for signatures of full rank that over domain sizes 3 and 4, basis sizes 1 and 2, respectively, suffice, and they conjectured that over domain size k there is a collapse to basis size ⌊log2 k⌋. In this work, we resolve this conjecture in the affirmative for signatures of full rank for all k.

Publisher's Version Article Search
Base Collapse of Holographic Algorithms
Mingji Xia
(Institute of Software at Chinese Academy of Sciences, China)
A holographic algorithm solves a problem in a domain of size n, by reducing it to counting perfect matchings in planar graphs. It may simulate a n-value variable by a bunch of t matchgate bits, which has 2t values. The transformation in the simulation can be expressed as a n × 2t matrix M, called the base of the holographic algorithm. We wonder whether more matchgate bits bring us more powerful holographic algorithms. In another word, whether we can solve the same original problem, with a collapsed base of size n × 2r, where r<t.
Base collapse is discovered for small domain n=2,3,4. For n=3, 4, the base collapse is proved under the condition that there is a full rank generator. We prove for any n, the base collapse to a r≤ ⌊ logn ⌋, under some similar conditions. One of the conditions is that the original problem is defined by one symmetric function. In the proof, we utilize elementary matchgate transformations instead of matchgate identities.

Publisher's Version Article Search
Separations in Query Complexity Based on Pointer Functions
Andris Ambainis, Kaspars Balodis, Aleksandrs Belovs, Troy Lee, Miklos Santha, and Juris Smotrovs
(University of Latvia, Latvia; CWI, Netherlands; Nanyang Technological University, Singapore; National University of Singapore, Singapore; CNRS, France)
In 1986, Saks and Wigderson conjectured that the largest separation between deterministic and zero-error randomized query complexity for a total boolean function is given by the function f on n=2k bits defined by a complete binary tree of NAND gates of depth k, which achieves R0(f) = O(D(f)0.7537…). We show this is false by giving an example of a total boolean function f on n bits whose deterministic query complexity is Ω(n/log(n)) while its zero-error randomized query complexity is Õ(√n). We further show that the quantum query complexity of the same function is Õ(n1/4), giving the first example of a total function with a super-quadratic gap between its quantum and deterministic query complexities.
We also construct a total boolean function g on n variables that has zero-error randomized query complexity Ω(n/log(n)) and bounded-error randomized query complexity R(g) = Õ(√n). This is the first super-linear separation between these two complexity measures. The exact quantum query complexity of the same function is QE(g) = Õ(√n).
These functions show that the relations D(f) = O(R1(f)2) and R0(f) = Õ(R(f)2) are optimal, up to poly-logarithmic factors. Further variations of these functions give additional separations between other query complexity measures: a cubic separation between Q and R0, a 3/2-power separation between QE and R, and a 4th power separation between approximate degree and bounded-error randomized query complexity.
All of these examples are variants of a function recently introduced by Goos, Pitassi, and Watson which they used to separate the unambiguous 1-certificate complexity from deterministic query complexity and to resolve the famous Clique versus Independent Set problem in communication complexity.

Publisher's Version Article Search

Session 11A

Semidefinite Programs on Sparse Random Graphs and Their Application to Community Detection
Andrea Montanari and Subhabrata Sen
(Stanford University, USA)
Denote by A the adjacency matrix of an Erdos-Renyi graph with bounded average degree. We consider the problem of maximizing <A-EA,X> over the set of positive semidefinite matrices X with diagonal entries X_ii=1. We prove that for large (bounded) average degree d, the value of this semidefinite program (SDP) is --with high probability-- 2n*sqrt(d) + n, o(sqrt(d))+o(n). For a random regular graph of degree d, we prove that the SDP value is 2n*sqrt(d-1)+o(n), matching a spectral upper bound. Informally, Erdos-Renyi graphs appear to behave similarly to random regular graphs for semidefinite programming. We next consider the sparse, two-groups, symmetric community detection problem (also known as planted partition). We establish that SDP achieves the information-theoretically optimal detection threshold for large (bounded) degree. Namely, under this model, the vertex set is partitioned into subsets of size n/2, with edge probability a/n (within group) and b/n (across). We prove that SDP detects the partition with high probability provided (a-b)^2/(4d)> 1+o_d(1), with d= (a+b)/2. By comparison, the information theoretic threshold for detecting the hidden partition is (a-b)^2/(4d)> 1: SDP is nearly optimal for large bounded average degree. Our proof is based on tools from different research areas: (i) A new `higher-rank' Grothendieck inequality for symmetric matrices; (ii) An interpolation method inspired from statistical physics; (iii) An analysis of the eigenvectors of deformed Gaussian random matrices.

Publisher's Version Article Search
How Robust Are Reconstruction Thresholds for Community Detection?
Ankur Moitra, William Perry, and Alexander S. Wein
(Massachusetts Institute of Technology, USA)
The stochastic block model is one of the oldest and most ubiquitous models for studying clustering and community detection. In an exciting sequence of developments, motivated by deep but non-rigorous ideas from statistical physics, Decelle et al. conjectured a sharp threshold for when community detection is possible in the sparse regime. Mossel, Neeman and Sly and Massoulie proved the conjecture and gave matching algorithms and lower bounds.
Here we revisit the stochastic block model from the perspective of semirandom models where we allow an adversary to make `helpful' changes that strengthen ties within each community and break ties between them. We show a surprising result that these `helpful' changes can shift the information-theoretic threshold, making the community detection problem strictly harder. We complement this by showing that an algorithm based on semidefinite programming (which was known to get close to the threshold) continues to work in the semirandom model (even for partial recovery). This suggests that algorithms based on semidefinite programming are robust in ways that any algorithm meeting the information-theoretic threshold cannot be.
These results point to an interesting new direction: Can we find robust, semirandom analogues to some of the classical, average-case thresholds in statistics? We also explore this question in the broadcast tree model, and we show that the viewpoint of semirandom models can help explain why some algorithms are preferred to others in practice, in spite of the gaps in their statistical performance on random models.

Publisher's Version Article Search
Sparsified Cholesky and Multigrid Solvers for Connection Laplacians
Rasmus Kyng, Yin Tat Lee, Richard Peng, Sushant Sachdeva, and Daniel A. Spielman
(Yale University, USA; Massachusetts Institute of Technology, USA; Georgia Tech, USA)
We introduce the sparsified Cholesky and sparsified multigrid algorithms for solving systems of linear equations. These algorithms accelerate Gaussian elimination by sparsifying the nonzero matrix entries created by the elimination process. We use these new algorithms to derive the first nearly linear time algorithms for solving systems of equations in connection Laplacians---a generalization of Laplacian matrices that arise in many problems in image and signal processing. We also prove that every connection Laplacian has a linear sized approximate inverse. This is an LU factorization with a linear number of nonzero entries that is a strong approximation of the original matrix. Using such a factorization one can solve systems of equations in a connection Laplacian in linear time. Such a factorization was unknown even for ordinary graph Laplacians.

Publisher's Version Article Search
Parallel Algorithms for Select and Partition with Noisy Comparisons
Mark Braverman, Jieming Mao, and S. Matthew Weinberg
(Princeton University, USA)
We consider the problem of finding the kth highest element in a totally ordered set of n elements (Select), and partitioning a totally ordered set into the top k and bottom n − k elements (Partition) using pairwise comparisons. Motivated by settings like peer grading or crowdsourcing, where multiple rounds of interaction are costly and queried comparisons may be inconsistent with the ground truth, we evaluate algorithms based both on their total runtime and the number of interactive rounds in three comparison models: noiseless (where the comparisons are correct), erasure (where comparisons are erased with probability 1 − γ), and noisy (where comparisons are correct with probability 1/2 + γ/2 and incorrect otherwise). We provide numerous matching upper and lower bounds in all three models. Even our results in the noiseless model, which is quite well-studied in the TCS literature on parallel algorithms, are novel.

Publisher's Version Article Search

Session 11B

Separations in Query Complexity using Cheat Sheets
Scott Aaronson, Shalev Ben-David, and Robin Kothari
(Massachusetts Institute of Technology, USA)
We show a power 2.5 separation between bounded-error randomized and quantum query complexity for a total Boolean function, refuting the widely believed conjecture that the best such separation could only be quadratic (from Grover's algorithm). We also present a total function with a power 4 separation between quantum query complexity and approximate polynomial degree, showing severe limitations on the power of the polynomial method. Finally, we exhibit a total function with a quadratic gap between quantum query complexity and certificate complexity, which is optimal (up to log factors). These separations are shown using a new, general technique that we call the cheat sheet technique, which builds upon the techniques of Ambainis et al. [STOC 2016]. The technique is based on a generic transformation that converts any (possibly partial) function into a new total function with desirable properties for showing separations. The framework also allows many known separations, including some recent breakthrough results of Ambainis et al. [STOC 2016], to be shown in a unified manner.

Publisher's Version Article Search
Entangled Simultaneity versus Classical Interactivity in Communication Complexity
Dmitry Gavinsky
(Czech Academy of Sciences, Czechia)
In 1999 Raz demonstrated a partial function that had an efficient quantum two-way communication protocol but no efficient classical two-way protocol and asked, whether there existed a function with an efficient quantum one-way protocol, but still no efficient classical two-way protocol. In 2010 Klartag and Regev demonstrated such a function and asked, whether there existed a function with an efficient quantum simultaneous-messages protocol, but still no efficient classical two-way protocol. In this work we answer the latter question affirmatively and present a partial function Shape, which can be computed by a protocol sending entangled simultaneous messages of poly-logarithmic size, and whose classical two-way complexity is lower bounded by a polynomial.

Publisher's Version Article Search
Classical Verification of Quantum Proofs
Zhengfeng Ji
(University of Technology Sydney, Australia; University of Waterloo, Canada; Institute of Software at Chinese Academy of Sciences, China)
We present a classical interactive protocol that verifies the validity of a quantum witness state for the local Hamiltonian problem. It follows from this protocol that approximating the non-local value of a multi-player one-round game to inverse polynomial precision is QMA-hard. Our work makes an interesting connection between the theory of QMA-completeness and Hamiltonian complexity on one hand and the study of non-local games and Bell inequalities on the other.

Publisher's Version Article Search
Efficient Quantum Tomography
Ryan O'Donnell and John Wright
(Carnegie Mellon University, USA)
In the quantum state tomography problem, one wishes to estimate an unknown d-dimensional mixed quantum state ρ, given few copies. We show that O(d/ε) copies suffice to obtain an estimate ρ that satisfies ||ρ − ρ||F2 ≤ ε (with high probability). An immediate consequence is that O((ρ) · d2) ≤ O(d22) copies suffice to obtain an ε-accurate estimate in the standard trace distance. This improves on the best known prior result of O(d32) copies for full tomography, and even on the best known prior result of O(d2log(d/ε)/ε2) copies for spectrum estimation. Our result is the first to show that nontrivial tomography can be obtained using a number of copies that is just linear in the dimension.
Next, we generalize these results to show that one can perform efficient principal component analysis on ρ. Our main result is that O(k d2) copies suffice to output a rank-k approximation ρ whose trace-distance error is at most ε more than that of the best rank-k approximator to ρ. This subsumes our above trace distance tomography result and generalizes it to the case when ρ is not guaranteed to be of low rank. A key part of the proof is the analogous generalization of our spectrum-learning results: we show that the largest k eigenvalues of ρ can be estimated to trace-distance error ε using O(k22) copies. In turn, this result relies on a new coupling theorem concerning the Robinson–Schensted–Knuth algorithm that should be of independent combinatorial interest.

Publisher's Version Article Search
Sample-Optimal Tomography of Quantum States
Jeongwan Haah, Aram W. Harrow, Zhengfeng Ji, Xiaodi Wu, and Nengkun Yu
(Massachusetts Institute of Technology, USA; University of Technology Sydney, Australia; University of Waterloo, Canada; Institute of Software at Chinese Academy of Sciences, China; University of Oregon, USA; University of Guelph, Canada)
It is a fundamental problem to decide how many copies of an unknown mixed quantum state are necessary and sufficient to determine the state. This is the quantum analogue of the problem of estimating a probability distribution given some number of samples.
Previously, it was known only that estimating states to error є in trace distance required O(dr22) copies for a d-dimensional density matrix of rank r. Here, we give a measurement scheme (POVM) that uses O( (dr/ δ ) ln(d/δ) ) copies to estimate ρ to error δ in infidelity. This implies O( (dr / є2)· ln(d/є) ) copies suffice to achieve error є in trace distance. For fixed d, our measurement can be implemented on a quantum computer in time polynomial in n.
We also use the Holevo bound from quantum information theory to prove a lower bound of Ω(dr2)/ log(d/rє) copies needed to achieve error є in trace distance. This implies a lower bound Ω(dr/δ)/log(d/rδ) for the estimation error δ in infidelity. These match our upper bounds up to log factors.
Our techniques can also show an Ω(r2d/δ) lower bound for measurement strategies in which each copy is measured individually and then the outcomes are classically post-processed to produce an estimate. This matches the known achievability results and proves for the first time that such “product” measurements have asymptotically suboptimal scaling with d and r.

Publisher's Version Article Search

Session 12A

A Duality Based Unified Approach to Bayesian Mechanism Design
Yang Cai, Nikhil R. Devanur, and S. Matthew Weinberg
(McGill University, Canada; Microsoft Research, USA; Princeton University, USA)
We provide a unified view of many recent developments in Bayesian mechanism design, including the black-box reductions of Cai et. al., simple auctions for additive buyers, and posted-price mechanisms for unit-demand buyers. Additionally, we show that viewing these three previously disjoint lines of work through the same lens leads to new developments as well. First, we provide a duality framework for Bayesian mechanism design, which naturally accommodates multiple agents and arbitrary objectives/feasibility constraints. Using this, we prove that either a posted-price mechanism or the VCG auction with per-bidder entry fees achieves a constant-factor of the optimal Bayesian IC revenue whenever buyers are unit-demand or additive, unifying previous breakthroughs of Chawla et. al. and Yao, and improving both approximation ratios (from 33.75 to 24 and 69 to 8). Finally, we show that this view also leads to improved structural characterizations in the Cai et. al. framework.

Publisher's Version Article Search
Breaking the Logarithmic Barrier for Truthful Combinatorial Auctions with Submodular Bidders
Shahar Dobzinski
(Weizmann Institute of Science, Israel)
We study a central problem in Algorithmic Mechanism Design: constructing truthful mechanisms for welfare maximization in combinatorial auctions with submodular bidders. Dobzinski, Nisan, and Schapira provided the first mechanism that guarantees a non-trivial approximation ratio of O(log^2 m) [STOC'06], where m is the number of items. This was subsequently improved to O( log m log log m) [Dobzinski, APPROX'07] and then to O(m) [Krysta and Vocking, ICALP'12]. In this paper we develop the first mechanism that breaks the logarithmic barrier. Specifically, the mechanism provides an approximation ratio of O( m). Similarly to previous constructions, our mechanism uses polynomially many value and demand queries, and in fact provides the same approximation ratio for the larger class of XOS (a.k.a. fractionally subadditive) valuations. We also develop a computationally efficient implementation of the mechanism for combinatorial auctions with budget additive bidders. Although in general computing a demand query is NP-hard for budget additive valuations, we observe that the specific form of demand queries that our mechanism uses can be efficiently computed when bidders are budget additive.

Publisher's Version Article Search
Watch and Learn: Optimizing from Revealed Preferences Feedback
Aaron Roth, Jonathan Ullman, and Zhiwei Steven Wu
(University of Pennsylvania, USA; Northeastern University, USA)
A Stackelberg game is played between a leader and a follower. The leader first chooses an action, then the follower plays his best response. The goal of the leader is to pick the action that will maximize his payoff given the follower’s best response. In this paper we present an approach to solving for the leader’s optimal strategy in certain Stackelberg games where the follower’s utility function (and thus the subsequent best response of the follower) is unknown. Stackelberg games capture, for example, the following interaction between a producer and a consumer. The producer chooses the prices of the goods he produces, and then a consumer chooses to buy a utility maximizing bundle of goods. The goal of the seller here is to set prices to maximize his profit—his revenue, minus the production cost of the purchased bundle. It is quite natural that the seller in this example should not know the buyer’s utility function. However, he does have access to revealed preference feedback---he can set prices, and then observe the purchased bundle and his own profit. We give algorithms for efficiently solving, in terms of both computational and query complexity, a broad class of Stackelberg games in which the follower’s utility function is unknown, using only “revealed preference” access to it. This class includes in particular the profit maximization problem, as well as the optimal tolling problem in nonatomic congestion games, when the latency functions are unknown. Surprisingly, we are able to solve these problems even though the optimization problems are non-convex in the leader’s actions.

Publisher's Version Article Search
The Price of Anarchy in Large Games
Michal Feldman, Nicole Immorlica, Brendan Lucier, Tim Roughgarden, and Vasilis Syrgkanis
(Tel Aviv University, Israel; Microsoft Research, USA; Stanford University, USA)
We present an analysis framework for bounding the price of anarchy (POA) in games that have many players, as in many of the games most pertinent to computer science applications. We use this framework to demonstrate that, in many of the models in which the POA has been studied, the POA in large games is much smaller than the worst-case bound. Our framework also differentiates between mechanisms with similar worst-case performance, such as simultaneous uniform-price auctions and greedy combinatorial auctions, thereby providing new insights about which mechanisms are likely to perform well in realistic settings.

Publisher's Version Article Search

Session 12B

Exponential Separation of Communication and External Information
Anat Ganor, Gillat Kol, and Ran Raz
(Weizmann Institute of Science, Israel; Institute for Advanced Study at Princeton, USA)
We show an exponential gap between communication complexity and external information complexity, by analyzing a communication task suggested as a candidate by Braverman. Previously, only a separation of communication complexity and internal information complexity was known.
More precisely, we obtain an explicit example of a search problem with external information complexity ≤ O(k), with respect to any input distribution, and distributional communication complexity ≥ 2k, with respect to some input distribution. In particular, this shows that a communication protocol cannot always be compressed to its external information. By a result of Braverman, our gap is the largest possible.
Moreover, since the upper bound of O(k) on the external information complexity of the problem is obtained with respect to any input distribution, our result implies an exponential gap between communication complexity and information complexity (both internal and external) in the non-distributional setting of Braverman. In this setting, no gap was previously known, even for internal information complexity.

Publisher's Version Article Search
Interactive Compression for Product Distributions
Gillat Kol
(Institute for Advanced Study at Princeton, USA)
We study the interactive compression problem: Given a two-party communication protocol with small information cost, can it be compressed so that the total number of bits communicated is also small? We consider the case where the parties have inputs that are independent of each other, and give a simulation protocol that communicates I^2 * polylog(I) bits, where I is the information cost of the original protocol. Our protocol is the first simulation protocol whose communication complexity is bounded by a polynomial in the information cost of the original protocol.

Publisher's Version Article Search
Constant-Rate Coding for Multiparty Interactive Communication Is Impossible
Mark Braverman, Klim Efremenko, Ran Gelles, and Bernhard Haeupler
(Princeton University, USA; Tel Aviv University, Israel; Carnegie Mellon University, USA)
We study coding schemes for multiparty interactive communication over synchronous networks that suffer from stochastic noise, where each bit is independently flipped with probability ε. We analyze the minimal overhead that must be added by the coding scheme in order to succeed in performing the computation despite the noise. Our main result is a lower bound on the communication of any noise-resilient protocol over a synchronous star network with n-parties (where all parties communicate in every round). Specifically, we show a task that can be solved by communicating T bits over the noise-free network, but for which any protocol with success probability of 1-o(1) must communicate at least Ω(T log n / log log n) bits when the channels are noisy. By a 1994 result of Rajagopalan and Schulman, the slowdown we prove is the highest one can obtain on any topology, up to a log log n factor. We complete our lower bound with a matching coding scheme that achieves the same overhead; thus, the capacity of (synchronous) star networks is Θ(log log n / log n). Our bounds prove that, despite several previous coding schemes with rate Ω(1) for certain topologies, no coding scheme with constant rate Ω(1) exists for arbitrary n-party noisy networks.

Publisher's Version Article Search
Communication Lower Bounds for Statistical Estimation Problems via a Distributed Data Processing Inequality
Mark Braverman, Ankit Garg, Tengyu Ma, Huy L. Nguyen, and David P. Woodruff
(Princeton University, USA; Toyota Technological Institute at Chicago, USA; IBM Research, USA)
We study the tradeoff between the statistical error and communication cost of distributed statistical estimation problems in high dimensions. In the distributed sparse Gaussian mean estimation problem, each of the m machines receives n data points from a d-dimensional Gaussian distribution with unknown mean θ which is promised to be k-sparse. The machines communicate by message passing and aim to estimate the mean θ. We provide a tight (up to logarithmic factors) tradeoff between the estimation error and the number of bits communicated between the machines. This directly leads to a lower bound for the distributed sparse linear regression problem: to achieve the statistical minimax error, the total communication is at least Ω(minn,dm), where n is the number of observations that each machine receives and d is the ambient dimension. These lower results improve upon Shamir (NIPS’14) and Steinhardt-Duchi (COLT’15) by allowing multi-round iterative communication model. We also give the first optimal simultaneous protocol in the dense case for mean estimation. As our main technique, we prove a distributed data processing inequality, as a generalization of usual data processing inequalities, which might be of independent interest and useful for other problems.

Publisher's Version Article Search

Session 13A

A Polynomial Lower Bound for Testing Monotonicity
Aleksandrs Belovs and Eric Blais
(CWI, Netherlands; University of Waterloo, Canada)
We show that every algorithm for testing n-variate Boolean functions for monotonicity has query complexity Ω(n1/4). All previous lower bounds for this problem were designed for non-adaptive algorithms and, as a result, the best previous lower bound for general (possibly adaptive) monotonicity testers was only Ω(logn). Combined with the query complexity of the non-adaptive monotonicity tester of Khot, Minzer, and Safra (FOCS 2015), our lower bound shows that adaptivity can result in at most a quadratic reduction in the query complexity for testing monotonicity.
By contrast, we show that there is an exponential gap between the query complexity of adaptive and non-adaptive algorithms for testing regular linear threshold functions (LTFs) for monotonicity. Chen, De, Servedio, and Tan (STOC 2015) recently showed that non-adaptive algorithms require almost Ω(n1/2) queries for this task. We introduce a new adaptive monotonicity testing algorithm which has query complexity O(logn) when the input is a regular LTF.

Publisher's Version Article Search
Relating Two Property Testing Models for Bounded Degree Directed Graphs
Artur Czumaj, Pan Peng, and Christian Sohler
(University of Warwick, UK; TU Dortmund, Germany; Institute of Software at Chinese Academy of Sciences, China)
We study property testing algorithms in directed graphs (digraphs) with maximum indegree and maximum outdegree upper bounded by d. For directed graphs with bounded degree, there are two different models in property testing introduced by Bender and Ron (2002). In the bidirectional model, one can access both incoming and outgoing edges while in the unidirectional model one can only access outgoing edges. In our paper we provide a new relation between the two models: we prove that if a property can be tested with constant query complexity in the bidirectional model, then it can be tested with sublinear query complexity in the unidirectional model. A corollary of this result is that in the unidirectional model (the model allowing only queries to the outgoing neighbors), every property in hyperfinite digraphs is testable with sublinear query complexity.

Publisher's Version Article Search
Algorithmic Stability for Adaptive Data Analysis
Raef Bassily, Kobbi Nissim, Adam Smith, Thomas Steinke, Uri Stemmer, and Jonathan Ullman
(University of California at San Diego, USA; Ben-Gurion University of the Negev, Israel; Harvard University, USA; Pennsylvania State University, USA; Northeastern University, USA)
Adaptivity is an important feature of data analysis - the choice of questions to ask about a dataset often depends on previous interactions with the same dataset. However, statistical validity is typically studied in a nonadaptive model, where all questions are specified before the dataset is drawn. Recent work by Dwork et al. (STOC, 2015) and Hardt and Ullman (FOCS, 2014) initiated a general formal study of this problem, and gave the first upper and lower bounds on the achievable generalization error for adaptive data analysis.

Specifically, suppose there is an unknown distribution P and a set of n independent samples x is drawn from P. We seek an algorithm that, given x as input, accurately answers a sequence of adaptively chosen ``queries'' about the unknown distribution P. How many samples n must we draw from the distribution, as a function of the type of queries, the number of queries, and the desired level of accuracy?

In this work we make two new contributions towards resolving this question:
We give upper bounds on the number of samples n that are needed to answer statistical queries. The bounds improve and simplify the work of Dwork et al. (STOC, 2015), and have been applied in subsequent work by those authors (Science, 2015; NIPS, 2015). We prove the first upper bounds on the number of samples required to answer more general families of queries. These include arbitrary low-sensitivity queries and an important class of optimization queries (alternatively, risk minimization queries).

As in Dwork et al., our algorithms are based on a connection with algorithmic stability in the form of differential privacy. We extend their work by giving a quantitatively optimal, more general, and simpler proof of their main theorem that the stability notion guaranteed by differential privacy implies low generalization error. We also show that weaker stability guarantees such as bounded KL divergence and total variation distance lead to correspondingly weaker generalization guarantees.

Publisher's Version Article Search
The Fourier Transform of Poisson Multinomial Distributions and Its Algorithmic Applications
Ilias Diakonikolas, Daniel M. Kane, and Alistair Stewart
(University of Southern California, USA; University of California at San Diego, USA)
An (n, k)-Poisson Multinomial Distribution (PMD) is a random variable of the form X = ∑i=1n Xi, where the Xi’s are independent random vectors supported on the set of standard basis vectors in k. In this paper, we obtain a refined structural understanding of PMDs by analyzing their Fourier transform. As our core structural result, we prove that the Fourier transform of PMDs is approximately sparse, i.e., its L1-norm is small outside a small set. By building on this result, we obtain the following applications:

Learning Theory. We give the first computationally efficient learning algorithm for PMDs under the total variation distance. Our algorithm learns an (n, k)-PMD within variation distance ε using a near-optimal sample size of Ok(1/ε2), and runs in time Ok(1/ε2) · logn. Previously, no algorithm with a (1/ε) runtime was known, even for k=3.

Game Theory. We give the first efficient polynomial-time approximation scheme (EPTAS) for computing Nash equilibria in anonymous games. For normalized anonymous games with n players and k strategies, our algorithm computes a well-supported ε-Nash equilibrium in time nO(k3) · (k/ε)O(k3log(k/ε)/loglog(k/ε))k−1. The best previous algorithm for this problem [, ] had running time n(f(k)/ε)k, where f(k) = Ω(kk2), for any k>2.

Statistics. We prove a multivariate central limit theorem (CLT) that relates an arbitrary PMD to a discretized multivariate Gaussian with the same mean and covariance, in total variation distance. Our new CLT strengthens the CLT of Valiant and Valiant [, ] by removing the dependence on n in the error bound.

Along the way we prove several new structural results of independent interest about PMDs. These include: (i) a robust moment-matching lemma, roughly stating that two PMDs that approximately agree on their low-degree parameter moments are close in variation distance; (ii) near-optimal size proper ε-covers for PMDs in total variation distance (constructive upper bound and nearly-matching lower bound). In addition to Fourier analysis, we employ a number of analytic tools, including the saddlepoint method from complex analysis, that may find other applications.

Publisher's Version Article Search
A Size-Free CLT for Poisson Multinomials and Its Applications
Constantinos Daskalakis, Anindya De, Gautam Kamath, and Christos Tzamos
(Massachusetts Institute of Technology, USA; Northwestern University, USA)
An (n,k)-Poisson Multinomial Distribution (PMD) is the distribution of the sum of n independent random vectors supported on the set Bk={e1,…,ek} of standard basis vectors in ℝk. We show that any (n,k)-PMD is poly(k/σ)-close in total variation distance to the (appropriately discretized) multi-dimensional Gaussian with the same first two moments, removing the dependence on n from the Central Limit Theorem of Valiant and Valiant. Interestingly, our CLT is obtained by bootstrapping the Valiant-Valiant CLT itself through the structural characterization of PMDs shown in recent work by Daskalakis, Kamath and Tzamos. In turn, our stronger CLT can be leveraged to obtain an efficient PTAS for approximate Nash equilibria in anonymous games, significantly improving the state of the art, and matching qualitatively the running time dependence on n and 1/є of the best known algorithm for two-strategy anonymous games. Our new CLT also enables the construction of covers for the set of (n,k)-PMDs, which are proper and whose size is shown to be essentially optimal. Our cover construction combines our CLT with the Shapley-Folkman theorem and recent sparsification results for Laplacian matrices by Batson, Spielman, and Srivastava. Our cover size lower bound is based on an algebraic geometric construction. Finally, leveraging the structural properties of the Fourier spectrum of PMDs we show that these distributions can be learned from Ok(1/є2) samples in polyk(1/є)-time, removing the quasi-polynomial dependence of the running time on 1/є from prior work.

Publisher's Version Article Search Info

Session 13B

Algebraic Attacks against Random Local Functions and Their Countermeasures
Benny Applebaum and Shachar Lovett
(Tel Aviv University, Israel; University of California at San Diego, USA)
Suppose that you have n truly random bits x=(x1,…,xn) and you wish to use them to generate mn pseudorandom bits y=(y1,…, ym) using a local mapping, i.e., each yi should depend on at most d=O(1) bits of x. In the polynomial regime of m=ns, s>1, the only known solution, originates from (Goldreich, ECCC 2000), is based on Random Local Functions: Compute yi by applying some fixed (public) d-ary predicate P to a random (public) tuple of distinct inputs (xi1,…,xid). Our goal in this paper is to understand, for any value of s, how the pseudorandomness of the resulting sequence depends on the choice of the underlying predicate. We derive the following results:
(1) We show that pseudorandomness against F2-linear adversaries (i.e., the distribution y has low-bias) is achieved if the predicate is (a) k=Ω(s)-resilience, i.e., uncorrelated with any k-subset of its inputs, and (b) has algebraic degree of Ω(s) even after fixing Ω(s) of its inputs. We also show that these requirements are necessary, and so they form a tight characterization (up to constants) of security against linear attacks. Our positive result shows that a d-local low-bias generator can have output length of nΩ(d), answering an open question of Mossel, Shpilka and Trevisan (FOCS, 2003). Our negative result shows that a candidate for pseudorandom generator proposed by the first author (computational complexity, 2015) and by O’Donnell and Witmer (CCC 2014) is insecure. We use similar techniques to refute a conjecture of Feldman, Perkins and Vempala (STOC 2015) regarding the hardness of planted constraint satisfaction problems.
(2) Motivated by the cryptanalysis literature, we consider security against algebraic attacks. We provide the first theoretical treatment of such attacks by formalizing a general notion of algebraic inversion and distinguishing attacks based on the Polynomial Calculus proof system. We show that algebraic attacks succeed if and only if there exist a degree e=O(s) non-zero polynomial Q whose roots cover the roots of P or cover the roots of P’s complement. As a corollary, we obtain the first example of a predicate P for which the generated sequence y passes all linear tests but fails to pass some polynomial-time computable test, answering an open question posed by the first author (Question 4.9, computational complexity 2015).

Publisher's Version Article Search
Searchable Symmetric Encryption: Optimal Locality in Linear Space via Two-Dimensional Balanced Allocations
Gilad Asharov, Moni Naor, Gil Segev, and Ido Shahaf
(IBM Research, USA; Weizmann Institute of Science, Israel; Hebrew University of Jerusalem, Israel)
Searchable symmetric encryption (SSE) enables a client to store a database on an untrusted server while supporting keyword search in a secure manner. Despite the rapidly increasing interest in SSE technology, experiments indicate that the performance of the known schemes scales badly to large databases. Somewhat surprisingly, this is not due to their usage of cryptographic tools, but rather due to their poor locality (where locality is defined as the number of non-contiguous memory locations the server accesses with each query). The only known schemes that do not suffer from poor locality suffer either from an impractical space overhead or from an impractical read efficiency (where read efficiency is defined as the ratio between the number of bits the server reads with each query and the actual size of the answer).
We construct the first SSE schemes that simultaneously enjoy optimal locality, optimal space overhead, and nearly-optimal read efficiency. Specifically, for a database of size N, under the modest assumption that no keyword appears in more than N1 − 1/loglogN documents, we construct a scheme with read efficiency Õ(loglogN). This essentially matches the lower bound of Cash and Tessaro (EUROCRYPT ’14) showing that any SSE scheme must be sub-optimal in either its locality, its space overhead, or its read efficiency. In addition, even without making any assumptions on the structure of the database, we construct a scheme with read efficiency Õ(logN).
Our schemes are obtained via a two-dimensional generalization of the classic balanced allocations (“balls and bins”) problem that we put forward. We construct nearly-optimal two-dimensional balanced allocation schemes, and then combine their algorithmic structure with subtle cryptographic techniques.

Publisher's Version Article Search
Watermarking Cryptographic Capabilities
Aloni Cohen, Justin Holmgren, Ryo Nishimaki, Vinod Vaikuntanathan, and Daniel Wichs
(Massachusetts Institute of Technology, USA; NTT, Japan; Northeastern University, USA)
A watermarking scheme for programs embeds some information called a mark into a program while preserving its functionality. No adversary can remove the mark without damaging the functionality of the program. In this work, we study the problem of watermarking various cryptographic programs such as pseudorandom function (PRF) evaluation, decryption, and signing. For example, given a PRF key K, we create a marked program C that evaluates the PRF F(K,). An adversary that gets C cannot come up with any program C* in which the mark is removed but which still evaluates the PRF correctly on even a small fraction of the inputs. The work of Barak, Goldreich, Impagliazzo, Rudich, Sahai, Vadhan, and Yang (CRYPTO'01 and Journal of ACM 59(2)) shows that, assuming indistinguishability obfuscation (iO), such watermarking is impossible if the marked program C evaluates the original program with perfect correctness. In this work we show that, assuming iO, such watermarking is possible if the marked program C is allowed to err with even a negligible probability, which would be undetectable to the user. Our watermarking schemes are public key, namely we use a secret marking key to embed marks in programs, and a public detection key that allows anyone to detect marks in programs. Our schemes are secure against chosen program attacks, that is even if the adversary is given oracle access to the marking functionality. We emphasize that our security notion of watermark non-removability considers arbitrary adversarial strategies to modify the marked program, in contrast to the prior works (Nishimaki, EUROCRYPT '13).

Publisher's Version Article Search
Textbook Non-malleable Commitments
Vipul Goyal, Omkant Pandey, and Silas Richelson
(Microsoft Research, India; Drexel University, USA; Massachusetts Institute of Technology, USA)
We present a new non-malleable commitment protocol. Our protocol has the following features: itemize The protocol has only three rounds of interaction. Pass (TCC 2013) showed an impossibility result for a two-round non-malleable commitment scheme w.r.t. a black-box reduction to any ``standard" intractability reduction. Thus, this resolves the round complexity of non-malleable commitment at least w.r.t. black-box security reductions. Our construction is secure as per the standard notion of non-malleability w.r.t. commitment. Our protocol is truly efficient. In our basic protocol, the entire computation of the committer is dominated by just three invocations of a non-interactive statically binding commitment scheme, while, the receiver computation (in the commitment stage) is limited to just sampling a random string. Unlike many previous works, we directly construct a protocol for large tags and hence avoid any non-malleability amplification steps. Our protocol is based on a black-box use of any non-interactive statistically binding commitment scheme. Such schemes, in turn, can be based on any one-to-one one-way function (or any one-way function at the cost of an extra initialization round). Previously, the best known black-box construction of non-malleable commitments required a larger (constant) number of rounds. Our construction is public-coin and makes use of only black-box simulation. Prior to our work, no public-coin constant round non-malleable commitment schemes were known based on black-box simulation. itemize Our techniques depart significantly from the techniques used previously to construct non-malleable commitment schemes. As a main technical tool, we rely on non-malleable codes in the split state model. Our proofs of security are purely combinatorial in nature. In addition, we also present a simple construction of constant round non-malleable commitments from any one-way function. While this result is not new, the main feature is its simplicity compared to any previous construction of non-malleable commitments (in any number of rounds). We believe the construction is simple enough to be covered in a graduate level course on cryptography. The construction uses non-malleable codes in the split state model in a black-box way.

Publisher's Version Article Search

proc time: 39.1