The standard LP relaxation of the asymmetric traveling salesman problem has been conjectured to have a constant integrality gap in the metric case. We prove this conjecture when restricted to shortest path metrics of node-weighted digraphs. Our arguments are constructive and give a constant factor approximation algorithm for these metrics. We remark that the considered case is more general than the directed analog of the special case of the symmetric traveling salesman problem for which there were recent improvements on Christofides' algorithm. The main idea of our approach is to first consider an easier problem obtained by significantly relaxing the general connectivity requirements into local connectivity conditions. For this relaxed problem, it is quite easy to give an algorithm with a guarantee of 3 on node-weighted shortest path metrics. More surprisingly, we then show that any algorithm (irrespective of the metric) for the relaxed problem can be turned into an algorithm for the asymmetric traveling salesman problem by only losing a small constant factor in the performance guarantee. This leaves open the intriguing task of designing a "good" algorithm for the relaxed problem on general metrics.
We show that the integrality gap of the natural LP relaxation of the Asymmetric Traveling Salesman Problem is polyloglog(n). In other words, there is a polynomial time algorithm that approximates the value of the optimum tour within a factor of polyloglog(n), where polyloglog(n) is a bounded degree polynomial of loglog(n).We prove this by showing that any k-edge-connected unweighted graph has a polyloglog(n)/k-thin spanning tree.Our main new ingredient is a procedure, albeit an exponentially sized convex program, that "transforms" graphs that do not admit any spectrally thin trees into those that provably have spectrally thin trees. More precisely, given a k-edge-connected graph G=(V,E) where k>= 7log(n),we show that there is a matrix D that "preserves" the structure of all cuts of G such that for a subset F of E that induces an Omega(k)-edge-connected graph, the effective resistance of every edge in F w.r.t. D is at most polylog(k)/k. Then, we use our recent extension of the seminal work of Marcus, Spielman, and Srivastava [MSS13] to prove the existence of a polylog(k)/k-spectrally thin tree with respect to D. Such a treeis polylog(k)/k-combinatorially thin with respect to G as D preserves the structure of cuts of G.
In this work we study the quantitative relation between VC-dimension and two other basic parameters related to learning and teaching. Namely, the quality of sample compression schemes and of teaching sets for classes of low VC-dimension. Let C be a binary concept class of size m and VC-dimension d. Prior to this work, the best known upper bounds for both parameters were log(m), while the best lower bounds are linear in d. We present significantly better upper bounds on both as follows.We construct sample compression schemes of size exp(d) for C. This resolves a question of Littlestone and Warmuth (1986).Roughly speaking, we show that given an arbitrary set of labeled examples from an unknown concept in C, one can retain only a subset of exp(d) of them, in a way that allows to recover the labels of all other examples in the set, using additional exp(d) information bits.We further show that there always exists a concept c in C with a teaching set (i.e. a list of c-labeled examples uniquely identifying c in C) of size exp(d) loglog(m). This problem was studied by Kuhlmann (1999). Our construction also implies that the recursive teaching (RT) dimension of C is at most exp(d) loglog(m) as well. The RT-dimension was suggested byZilles et al. and Doliwa et al. (2010). The same notion (under the name partial-ID width) was independently studied by Wigderson and Yehudayoff (2013). An upper bound on this parameter that depends only on d is known just for the very simple case d=1, and is open even for d=2. We also make small progress towards this seemingly modest goal.
We show a directed and robust analogue of a boolean isoperimetric type theorem of Talagrand. As an application, wegive a monotonicity testing algorithm that makes, up to polylog factors, (square root of n)/epsilon^2 non-adaptive queries to a function f:{0,1}^n -> {0,1},always accepts a monotone function and rejects a function that is epsilon-far from being monotone with constant probability.
Quadratic Conditional Lower Bounds for String Problems and Dynamic Time Warping: Classic similarity measures of strings are longest common subsequence and Levenshtein distance (i.e., the classic edit distance). A classic similarity measure of curves is dynamic time warping. These measures can be computed by simple O(n^2) dynamic programming algorithms, and despite much effort no algorithms with significantly better running time are known. We prove that, even restricted to binary strings or one-dimensional curves, respectively, these measures do not have strongly subquadratic time algorithms, i.e., no algorithms with running time O(n^{2-\eps}) for any \eps > 0, unless the Strong Exponential Time Hypothesis fails. We generalize the result to edit distance for arbitrary fixed costs of the four operations (deletion in one of the two strings, matching, substitution), by identifying trivial cases that can be solved in constant time, and proving quadratic-time hardness on binary strings for all other cost choices. This improves and generalizes the known hardness result for Levenshtein distance [Backurs,Indyk STOC'15] by the restriction to binary strings and the generalization to arbitrary costs, and adds important problems to a recent line of research showing conditional lower bounds for a growing number of quadratic time problems.As our main technical contribution, we introduce a framework for proving quadratic-time hardness of similarity measures. To apply the framework it suffices to construct a single gadget, which encapsulates all the expressive power necessary to emulate a reduction from satisfiability. Finally, we prove quadratic-time hardness for longest palindromic subsequence and longest tandem subsequence via reductions from longest common subsequence, showing that conditional lower bounds based on the Strong Exponential Time Hypothesis also apply to string problems that are not necessarily similarity measures.
Tight Hardness Results for LCS and other Sequence Similarity Measures: Two important similarity measures between sequences are the longest common subsequence (LCS) and the dynamic time warping distance (DTWD). The computations of these measures for two given sequences are central tasks in a variety of applications. Simple dynamic programming algorithms solve these tasks in O(n^2) time, and despite an extensive amount of research, no algorithms with significantly better worst case upper bounds are known.In this paper, we show that for any constant epsilon>0, an O(n^(2-epsilon)) time algorithm for computing the LCS or the DTWD of two sequences of length n over a constant size alphabet, refutes the popular Strong Exponential Time Hypothesis (SETH).
The CFG recognition problem is: given a context-free grammar G and a string w of length n, decide if w can be obtained from G. This is the most basic parsing question and is a core computer science problem. Valiant's parser from 1975 solves the problem in O(n^omega) time, where omega is the exponent of matrix multiplication. The best combinatorial algorithms have mildly subcubic O(n^3/\log^3{n}) complexity. Evidence for the nonexistence of efficient algorithms was given in a result of Lee (JACM'01), who showed that any algorithm for a more general parsing problem with running time O(|G| n^{3-eps}), that works even in the unusual case that |G|=Omega(n^6), can be converted into a surprising subcubic algorithm for Boolean Matrix Multiplication. However, nothing was known for the more relevant case of constant size grammars. In this work, we make the first progress on the constant size grammar case in 40 years, and prove that any improvement on Valiant's algorithm, either in terms of runtime or by avoiding the inefficiencies of fast matrix multiplication, would imply a breakthrough algorithm for the k-Clique problem: given a graph of n nodes, decide if there are k that form a clique. Besides classifying the complexity of a fundamental problem, our reduction has led us to similar lower bounds for more modern and well-studied cubic time problems for which faster algorithms are highly desirable in practice: RNA Folding, a central problem in computational biology, and Dyck Language Edit Distance, answering an open question of Saha (FOCS'14).
Given a context free language G over alphabet \Sigma and a string s, the language edit distance problem seeks the minimum number of edits (insertions, deletions and substitutions) required to convert s into a valid member of the language L(G). The well-known dynamic programming algorithm solves this problem in cubic time in string length [Aho, Peterson 1972, Myers 1985]. Despite its numerous applications, to date there exists no algorithm that computes the exact or approximate language edit distance problem in true subcubic time.In this paper we give the first such truly sub-cubic algorithm that computes language edit distance almost optimally. We further solve the local alignment problem; for all substrings of s, we can estimate their language edit distance near-optimally in same time with high probability. Next, we design the very first subcubic algorithm that given an arbitrary stochastic context free grammar, and a string returns a nearly-optimal maximum likelihood parsing of that string. Stochastic context free grammars significantly generalize hidden Markov models; they lie at the foundation of statistical natural language processing, and have found widespread applications in many other fields.To complement our upper bound result, we show that exact computation of maximum likelihood parsing of stochastic grammars or language edit distance in true subcubic time will imply a truly subcubic algorithm for all-pairs shortest paths, a long-standing open question. This will result in a breakthrough for a large range of problems in graphs and matrices due to subcubic equivalence. By a known lower bound result [Lee 2002], and a recent development [Abboud et al. 2015] even the much simpler problem of parsing a context free grammar requires fast matrix multiplication time. Therefore any nontrivial multiplicative approximation algorithms for either of the two problems in time less than matrix-multiplication are unlikely to exist.
We show how to compute any symmetric Boolean function on n variables over any field (as well as the integers) with a probabilistic polynomial of degree O(sqrt(n log(1/epsilon))) and error at most epsilon.The degree dependence on n and epsilon is optimal, matching a lower bound of Razborov (1987) and Smolensky (1987) for the MAJORITY function. The proof is constructive: a low-degree polynomial can be efficiently sampled from the distribution.This polynomial construction is combined with other algebraic ideas to give the first subquadratic time algorithm for computing a (worst-case) batch of Hamming distances in superlogarithmic dimensions, exactly. To illustrate, let c(n) : N -> N. Suppose we are given a database D of n vectors in {0,1}^(c(n) log n) and a collection of n query vectors Q in the same dimension. For all u in Q, we wish to compute a v in D with minimum Hamming distance from u. We solve this problem in n^(2-1/O(c(n) log^2 c(n))) randomized time. Hence, the problem is in ``truly subquadratic'' time for O(log n) dimensions, and in subquadratic time for d = o((log^2 n)/(log log n)^2). We apply the algorithm to computing pairs with maximum inner product, closest pair in l_1 for vectors with bounded integer entries, and pairs with maximum Jaccard coefficients.
In this paper, we consider the following \emph{inverse maintenance problem}: given $A \in R^{n\times d}$ and a number of rounds $r$, at round $k$, we receive a $n\times n$ diagonal matrix $D^{(k)}$ and we wish to maintain an efficient linear system solver for $A^{T}D^{(k)}A$ under the assumption $D^{(k)}$ does not change too rapidly. Thisinverse maintenance problem is the computational bottleneck in solving multiple optimization problems. We show how to solve this problem with $\tilde{O}\left(nnz(A)+d^{\omega}\right)$ preprocessing time and amortized $\tilde{O}(nnz(A)+d^{2})$ time per round, improving upon previous running times.Consequently, we obtain the fastest known running times for solving multiple problems including, linear programming, computing a rounding of a polytope, and sampling a point in a polytope. In particular given a feasible point in a linear program with $n$ variables, $d$ constraints, and constraint matrix $A \in R^{d\times n}$, we show how to solvethe linear program in time $\tilde{O}((nnz(A)+d^{2})\sqrt{d}\log(\epsilon^{-1}))$. We achieve our results through a novel combination of classic numerical techniques of low rank update, preconditioning, and fast matrix multiplication as well as recent work on subspace embeddings and spectral sparsification that we hope will be of independent interest.
We present the first almost-linear time algorithm for constructing linear-sized spectral sparsification for graphs. This improves all previous constructions of linear-sized spectral sparsification, which requires $\Omega(n^2)$ time.A key ingredient in our algorithm is a novel combination of two techniques used in literature for constructing spectral sparsification: Random sampling by effective resistance, and adaptive constructions based on barrier functions.
Matrix factorization is a popular approach for large-scale matrix completion. In this approach, the unknown low-rank matrix is expressed as the product of two much smaller matrices so that the low-rank property is automatically fulfilled. The resulting optimization problem, even with huge size, can be solved (to stationary points) very efficiently through standard optimization algorithms such as alternating minimization and stochastic gradient descent (SGD).However, due to the non-convexity caused by the factorization model, there is a limited theoretical understanding of whether these algorithms will generate a good solution. In this paper, we establish a theoretical guarantee for the factorization based formulation to correctly recover the underlying low-rank matrix. In particular, we show that under similar conditions to those in previous works,many standard optimization algorithms converge to the global optima of the factorization based formulation, and recover the true low-rank matrix. A major difference of our work from the existing results is that we do not need resampling (i.e., using independent samples at each iteration) in either the algorithm or its analysis. To the best of our knowledge, our result is the first one that provides exact recovery guarantee for many standard algorithms such as gradient descent, SGD and block coordinate gradient descent.
Independent component analysis (ICA) is the problem of efficiently recovering a matrix A in R^{n times n} from i.i.d. observations of X=AS where S in R^n is a random vector with mutually independent coordinates.This problem has been intensively studied, but all existing efficient algorithms with provable guarantees require that the coordinates Si have finite fourth moments.We consider the heavy-tailed ICA problem where we do not make this assumption, about the second moment.This problem also has received considerable attention in the applied literature.In the present work, we first give a provably efficient algorithm that works under the assumption that for constant gamma > 0$, each Si has finite (1+gamma)-moment, thus substantially weakening the moment requirement condition for the ICA problem to be solvable.We then give an algorithm that works under the assumption that matrix A has orthogonal columns but requires no moment assumptions.Our techniques draw ideas from convex geometry and exploit standard properties of the multivariate spherical Gaussian distribution in a novel way.
In the subspace approximation problem, we seek a $k$-dimensional subspace $F$ of $\mathbb{R}^d$ that minimizesthe sum of $p$-th powers of Euclidean distances to a given set of $n$ points $a_1, \ldots, a_n \in \mathbb{R}^d$, for $p \geq 1$. More generally than minimizing $\sum_i \dist(a_i,F)^p$,we may wish to minimize $\sum_i M(\dist(a_i,F))$ for some loss function $M()$, for example, $M$-Estimators, whichinclude the Huber and Tukey loss functions. Such subspaces provide alternativesto the singular value decomposition (SVD), which is the $p=2$ case, findingsuch an $F$ that minimizes the sum of squares of distances. For $p \in [1,2)$,and for typical $M$-Estimators, the minimizing $F$ gives a solution that is more robust tooutliers than that provided by the SVD.We give several algorithmic results for these robust subspace approximation problems.We state our results as follows, thinking of the $n$ points as forming an $n \times d$ matrix $A$, and letting $\nnz(A)$denote the number of non-zero entries of $A$. Our results hold for $p\in [1,2)$.We use $\poly(n)$ to denote $n^{O(1)}$ as $n\rightarrow\infty$.\begin{enumerate}\item For minimizing $\sum_i \dist(a_i,F)^p$, we give an algorithm running in\[O(\nnz(A) + (n+d)\poly(k/\eps) + \exp(\poly(k/\eps)))\]time which outputs a $k$-dimensional subspace $F$ whose cost is at most a $(1+\eps)$-factor larger than the optimum.\item We show that the problem of minimizing $\sum_i \dist(a_i, F)^p$ is NP-hard, even to output a $(1+1/\poly(d))$-approximation. This extends work of Deshpande et al. (SODA, 2011) which could onlyshow NP-hardness or UGC-hardness for $p > 2$; their proofs critically rely on $p > 2$. Our work resolves an open questionof [Kannan Vempala, NOW, 2009]. Thus, there cannot be an algorithm running in time polynomial in $k$ and $1/\eps$ unless P = NP.Together with prior work, this implies that the problem is NP-hard for all $p \neq 2$. \item For loss functions for a wide class of $M$-Estimators, we give a problem-size reduction:for a parameter $K=(\log n)^{O(\log k)}$, our reduction takes\[O(\nnz(A)\log n + (n+d)\poly(K/\eps))\]time to reduce the problem to a constrained version involving matrices whose dimensionsare $\poly(K\eps^{-1}\log n)$. We also give bicriteria solutions.\item Our techniques lead to the first $O(\nnz(A) + \poly(d/\eps))$ time algorithms for $(1+\eps)$-approximateregression for a wide class of convex $M$-Estimators. This improves prior results \cite{cw15}, which were $(1+\eps)$-approximation for Huber regression only,and $O(1)$-approximation for a general class of $M$-Estimators.\end{enumerate}
We show that unbounded fan-in boolean formulas of depth d + 1 and size s have average sensitivity O(log s/d)^d. In particular, this gives a tight 2^Ω(d(n^{1/d}−1)) lower bound on the size of depth d + 1 formulas computing the PARITY function. These results strengthen the corresponding O(logs)d and 2^Ω(n^{1/d}) bounds for circuits due to Boppana (1997) and Hastad (1986). Our proof technique studies a random process associated with formulas, in which the Switching Lemma is efficiently applied to subformulas.
The threshold degree of a Boolean function f is the minimum degree of a real polynomial p that represents f in sign: f(x)=sgn p(x). Introduced in the seminal work of Minsky and Papert (1969), this notion is central to some of the strongest algorithmic and complexity-theoretic results for constant-depth circuits. One problem that has remained open for several decades, with applications to computational learning and communication complexity, is to determine the maximum threshold degree of a polynomial-size constant-depth circuit in n variables. The best lower bound prior to our work was Omega(n^((d-1)/(2d-1))) for circuits of depth d. We obtain a polynomial improvement for every depth d, with a lower bound of Omega(n^(3/7)) for depth 3 and Omega(n^(1/2)) for depth d>=4. The proof contributes an approximation-theoretic technique of independent interest, which exploits asymmetry in circuits to prove their hardness for polynomials.
Kayal has recently introduced the method of shifted partial derivatives as a way to give the first exponential lower bound for computing an explicit polynomial as a sum of powers of constant-degree polynomials. This method has garnered further attention because of the work of Gupta, Kamath, Kayal and Saptharishi who used this method to obtain lower bounds that approach the "chasm at depth-4". In this work, we investigate to what extent this method can be used to obtain deterministic polynomial identity testing (PIT) algorithms, which are algorithms that decide whether a given algebraic circuit computes the zero polynomial. In particular, we give a poly(s)^(log s)-time deterministic black-box PIT algorithm for a size-s sum of powers of constant-degree polynomials. This is the first sub-exponential deterministic PIT algorithm for this model of computation and the first PIT algorithm based on the method of shifted partial derivatives.We also study the problem of divisibility testing, which when given multivariate polynomials f and g (as algebraic circuits) asks to decide whether f divides g. Using Strassen's technique for the elimination of divisions, we show that one can obtain deterministic divisibility testing algorithms via deterministic PIT algorithms, and this reduction does not dramatically increase the complexity of the underlying algebraic circuits. Using this reduction, we show that deciding divisibility of a constant-degree polynomial f into a sparse polynomial g reduces to PIT of sums of a monomial multiplied by a power of constant-degree polynomials. We then extend the method of shifted partial derivatives to give a poly(s)^(log s)-time deterministic black-box PIT algorithm for this model of computation, and thus derive a corresponding deterministic divisibility algorithm. This is the first non-trivial deterministic algorithm for this problem.Previous work on multivariate divisibility testing due to Saha, Saptharishi and Saxena gave algorithms for when f is linear and g is sparse, and essentially worked via PIT algorithms for read-once (oblivious) algebraic branching programs (roABPs). We give explicit sums of powers of quadratic polynomials that require exponentially-large roABPs in a strong sense, showing that techniques known for roABPs have limited applicability in our regime.Finally, by combining our results with the algorithm of Forbes, Shpilka and Saptharishi we obtain poly(s)^(loglog s)-time deterministic black-box PIT algorithms for various models (translations of sparse polynomials, and sums of monomials multiplied by a power of a linear polynomial) where only \poly(s)^(Theta(log s))-time such algorithms were previously known.
We consider the pebble game on DAGs with bounded fan-in introduced in [Paterson and Hewitt '70] and the reversible version of this game in [Bennett '89], and study the question of how hard it is to decide exactly or approximately the number of pebbles needed for a given DAG in these games.We prove that the problem of deciding whether s pebbles suffice to reversibly pebble a DAG G is PSPACE-complete, as was previously shown for the standard pebble game in [Gilbert, Lengauer and Tarjan '80]. Via two different graph product constructions we then strengthen these results to establish that both standard and reversible pebbling space are PSPACE-hard to approximate to within any additive constant. To the best of our knowledge, these are the first hardness of approximation results for pebble games in an unrestricted setting (even for polynomial time). Also, since [Chan '13] proved that reversible pebbling is equivalent to the games in [Dymond and Tompa '85] and [Raz and McKenzie '99], our results apply to the Dymond--Tompa and Raz--McKenzie games as well, and from the same paper it follows that resolution depth is PSPACE-hard to determine up to any additive constant.We also obtain a multiplicative logarithmic separation between reversible and standard pebbling space. This improves on the additive logarithmic separation previously known and could plausibly be tight, although we are not able to prove this.We leave as an interesting open problem whether our additive hardness of approximation result could be strengthened to a multiplicative bound if the computational resources are decreased from polynomial space to the more common setting of polynomial time.
We revisit the question of constructing secure general-purpose indistinguishability obfuscation,with a security reduction based on explicit computational assumptions over multilinear maps.Previous to our work, such reductions were only known to exist based on meta-assumptions and/or ad-hoc assumptions: In the original constructive work of Garg et al. (FOCS 2013), the underlying explicitcomputational assumption encapsulated an exponential family of assumptions for each pair of circuits to be obfuscated.In the more recent work of Pass et al. (Crypto 2014), the underlying assumption is a \emph{meta-assumption} thatalso encapsulates an exponential family of assumptions, and this meta-assumption is invoked in a manner thatcaptures the specific pair of circuits to be obfuscated. The assumptions underlying both these works substantiallycapture (either explicitly or implicitly) the actual structure of the obfuscation mechanism itself.In our work, we provide the first construction of general-purpose indistinguishability obfuscationproven secure via a reduction to a natural computational assumption overmultilinear maps, namely, the Multilinear Subgroup Elimination Assumption.This assumption does not depend on the circuits to be obfuscated (except for its size),and does not correspond to the underlying structure of our obfuscator. The technical heart of our paperis our reduction, which gives a new way to argue about the security of indistinguishability obfuscation.
Indistinguishability obfuscation (IO) is a tremendous notion, powerful enough to give rise to almost any known cryptographic object. So far, candidate IO constructions were based on specific assumptions on algebraic objects called multi-linear graded encodings.We present a generic construction of indistinguishability obfuscation from public-key functional encryption with succinct ciphertexts and sub-exponential security. This shows the equivalence of indistinguishability obfuscation and public-key functional encryption, a primitive that has so far seemed to be much weaker, lacking the power and the staggering range of applications of indistinguishability obfuscation.As an application, we obtain a new candidate IO construction based on the functional encryption scheme of Garg, Gentry, Halevi, and Zhandry [Eprint 14] under their assumptions on multi-linear graded encodings. We also show that, under the Learning with Errors assumptions, our techniques imply that any indistinguishability obfuscator can be converted to one where obfuscated circuits are of linear size in the size of the original circuit plus a polynomial overhead in its depth.Our reduction highlights the importance of ciphertext succinctness in functional encryption schemes, which we hope will serve as a pathway to new IO constructions based on solid cryptographic foundations.
Recent breakthroughs in cryptography have positioned indistinguishability obfuscation as a "central hub" for almost all known cryptographic tasks, and as an extremely powerful building block for new cryptographic tasks resolving long-standing and foundational open problems. However, constructions based on indistinguishability obfuscation almost always rely on non-black-box techniques, and thus the extent to which it can be used as a building block in cryptographic constructions has been completely unexplored so far.We present a framework for proving meaningful negative results on the power of indistinguishability obfuscation. By considering indistinguishability obfuscation for oracle-aided circuits, we capture the common techniques that have been used so far in constructions based on indistinguishability obfuscation. These include, in particular, non-black-box techniques such as the punctured programming approach of Sahai and Waters (STOC '14) and its variants, as well as sub-exponential security assumptions.Within our framework we prove the first negative results on the power of indistinguishability obfuscation and of the tightly related notion of functional encryption. Our results are as follows:-- There is no fully black-box construction of a collision-resistant function family from an indistinguishability obfuscator for oracle-aided circuits.-- There is no fully black-box construction of a key-agreement protocol with perfect completeness from a private-key functional encryption scheme for oracle-aided circuits.Specifically, we prove that any such potential constructions must suffer from an exponential security loss, and thus our results cannot be circumvented using sub-exponential security assumptions. Our framework captures constructions that may rely on a wide variety of primitives in a non-black-box manner (e.g., obfuscating or generating a functional key for a function that uses the evaluation circuit of a puncturable pseudorandom function), and we only assume that the underlying indistinguishability obfuscator or functional encryption scheme themselves are used in a black-box manner.
Garbled RAM, introduced by Lu and Ostrovsky, enables the task of garbling a RAM (Random Access Machine) program directly, there by avoiding the inefficient process of first converting it into a circuit. Garbled RAM can be seen as a RAM analogue of Yao's garbled circuit construction, except that known realizations of Garbled RAM make non-black-box use of the underlying cryptographic primitives.In this paper we remove this limitation and provide the first black-box construction of Garbled RAM with polylogarithmic overhead. Our scheme allows for garbling multiple RAM programs being executed on a persistent database and its security is based only on the existence of one-way functions. We also obtain the first secure RAM computation protocol that is both constant round and makes only black-box use of one-way functions in the Oblivious Transfer hybrid model.
Theoretical study of optimization problems in wireless communication often deals with zero-dimensional tasks.For example, the power control problem requires computing a power assignmentguaranteeing that each transmitting station is successfullyreceived at a single receiver point.This paper aims at addressing communication applications that require handling 2-dimensional tasks (e.g., guaranteeing successful transmission inentire regions rather than in specific points).A natural approach to such tasks is to discretize the $2$-dimensional optimization domain, e.g., by sampling points within the domain.This approach, however, might incur high time and memory requirements,and moreover, it cannot guarantee exact solutions.Towards this goal, we establish the minimum principle for the SINRfunction with free-space path loss (i.e., when the signal decays in proportion to the square of the distance between the transmitter and receiver).We then utilize it as a discretization technique for solvingtwo-dimensional problems in the SINR model.This approach is shown to be useful for handling optimization problems over two dimensions (e.g., power control, energy minimization);in providing tight bounds on the number of null-cells in the reception map;and in approximating geometrical and topological propertiesof the wireless reception map (e.g., maximum inscribed sphere).Essentially, the minimum principle allows us to reduce the dimensionof the optimization domain without losing anything in the accuracyor quality of the solution.More specifically, when the two dimensional optimization domain is bounded and free from any interfering station, the minimum principle implies thatit is sufficient to optimize over the boundary of the domain,as the ``hardest" points to be satisfied reside on boundaryand not in the interior.We believe that the minimum principle, as well as the interplay betweencontinuous and discrete analysis presented in this paper,may pave the way to future study of algorithmic SINR in higher dimensions.
Motivated by the need for designing efficient and robust fully-distributed computation in highly dynamic networks such as Peer-to-Peer (P2P) networks, we study distributed protocols for constructing and maintaining dynamic network topologies with good expansion properties. Our goal is to maintain a sparse (bounded degree) expander topology despite heavy churn (i.e., nodes joining and leaving the network continuously over time). We assume that the churn is controlled by an adversary that has complete knowledge and control of what nodes join and leave and at what time and has unlimited computational power, but is oblivious to the random choices made by the algorithm. Our main contribution is a randomized distributed protocol that guarantees with high probability the maintenance of a constant degree graph with high expansion even under continuous high adversarial churn. Our protocol can tolerate a churn rate ofup to O(n/polylog(n)) per round (where n is the stable network size). Ourprotocol is efficient, lightweight, and scalable, and it incurs onlyO(polylog(n)) overhead for topology maintenance: only polylogarithmic(in n) bits needs to be processed and sent by each node per round and anynode's computation cost per round is also polylogarithmic. The given protocolis a fundamental ingredient that is needed for the design of efficientfully-distributed algorithms for solving fundamental distributed computingproblems such as agreement, leader election, search, and storage in highlydynamic P2P networks and enables fast and scalable algorithms for theseproblems that can tolerate a large amount of churn.
We show how to represent a planar digraph in linear space so that reachability queries can be answered in constant time. The data structure can be constructed in linear time. This representation of reachability is thus optimal in both time and space, and has optimal construction time. The previous bestsolution used O(n log n) space for constant query time [Thorup FOCS’01].
We describe a fully dynamic linear-space data structure for point location in connected planar subdivisions, or more generally vertical ray shooting among non-intersecting line segments, that supports queries in $O(\log n(\log\log n)^2)$ time and updates in $O(\log n\log\log n)$ time. This is the first data structure that achieves close to logarithmic query and update time simultaneously, ignoring $\log\log n$ factors. We further show how to reduce the query time to $O(\log n\log\log n)$ in the RAM model with randomization. Alternatively, the query time can be lowered to $O(\log n)$ if the update time is increased to $O(\log^{1+\varepsilon}n)$ for any constant $\varepsilon>0$, or vice versa.
The dynamic optimality conjecture is perhaps the most fundamental open question about binary search trees (BST). It postulates the existence of an asymptotically optimal online BST, i.e. one that is constant factor competitivewith any BST on any input access sequence. The two main candidates for dynamic optimality in the literature are splay trees [Sleator and Tarjan, 1985], and Greedy [Lucas, 1988; Munro, 2000; Demaine et al. 2009]. Despite BSTsbeing among the simplest data structures in computer science, and despite extensive effort over the past three decades, the conjecture remains elusive. Dynamic optimality is trivial for almost all sequences: the optimum access cost of most length-n sequences is Theta(n log n), achievable by any balanced BST. Thus, the obvious missing step towards the conjecture is an understanding of the “easy” access sequences, and indeed the most fruitful research direction so far has been the study of specific sequences, whose “easiness” is captured by a parameter of interest. For instance, splay provably achieves the bound of O(nd) when d roughly measures the distances between consecutive accesses (dynamic finger), the average entropy (static optimality), or the delays between multiple accesses of an element (working set). The difficulty of proving dynamic optimality is witnessed by other highly restricted special cases that remain unresolved; one prominent example is the traversal conjecture [Sleator and Tarjan, 1985], which states that preorder sequences (whose optimum is linear) are linear-time accessed by splay trees; no online BST is known tosatisfy this conjecture.In this paper, we prove two different relaxations of the traversal conjecture for Greedy: (i) Greedy is almost linear for preorder traversal, (ii) if a linear-time preprocessing is allowed, Greedy is in fact linear. These statementsare corollaries of our more general results that express the complexity of access sequences in terms of a pattern avoidance parameter k. Pattern avoidance is a well-established concept in combinatorics, and the classes of input sequences thus defined are rich, e.g. the k = 3 case includes preorder sequences. For any sequence X with parameter k, our most general result shows that Greedy achieves the cost n*2^(alpha(n))^O(k) where alpha is the inverse Ackermann function. Furthermore, a broad subclass of parameter-k sequences has a natural combinatorial interpretation as k-decomposable sequences. For this class of inputs, we obtain an n*2^O(k) bound for Greedy when preprocessing is allowed. For k = 3, these results imply (i) and (ii). To our knowledge, these are the first upper bounds for Greedy that are not known to hold for any other online BST. To obtain these results we identify an input-revealing property of Greedy. Informally, this means that the execution log partially reveals the structure of the access sequence. This property facilitates the use of rich technical tools from forbidden submatrix theory.Further studying the intrinsic complexity of k-decomposable sequences, we make several observations. First, in order to obtain an offline optimal BST, it is enough to bound Greedy on non-decomposable access sequences.Furthermore, we show that the optimal cost for k-decomposable sequences is Theta(n log k), which is well below the proven performance of all known BST algorithms. Hence, sequences in this class can be seen as a "candidatecounterexample" to dynamic optimality.
During the last decade, the matroid secretary problem (MSP) became one of the most prominent classes of online selection problems. The interest in MSP is twofold: on the one hand, there are many interesting applications of MSP; and on the other hand, there is strong hope that MSP admits O(1)-competitive algorithms, which is the claim of the well-known matroid secretary conjecture. Partially linked to its numerous applications in mechanism design, substantial interest arose also in the study of nonlinear versions of MSP, with a focus on the submodular matroid secretary problem (SMSP). The fact that submodularity captures the property of diminishing returns, a very natural property for valuation functions, is a key reason for the interest in SMSP. So far, O(1)-competitive algorithms have been obtained for SMSP over some basic matroid classes. This created some hope that, analogously to the matroid secretary conjecture, one may even obtain O(1)-competitive algorithms for SMSP over any matroid. However, up to now, most questions related to SMSP remained open, including whether SMSP may be substantially more difficult than MSP; and more generally, to what extend MSP and SMSP are related.Our goal is to address these points by presenting general black-box reductions from SMSP to MSP. In particular, we show that any O(1)-competitive algorithm for MSP, even restricted to a particular matroid class, can be transformed in a black-box way to an O(1)-competitive algorithm for SMSP over the same matroid class. This implies that the matroid secretary conjecture is equivalent to the same conjecture for SMSP. Hence, in this sense SMSP is not harder than MSP. Also, to find O(1)-competitive algorithms for SMSP over a particular matroid class, it suffices to consider MSP over the same matroid class. Using our reductions we obtain many first and improved O(1)-competitive algorithms for SMSP over various matroid classes by leveraging known algorithms for MSP. Moreover, our reductions imply an O(loglog(rank))-competitive algorithm for SMSP, thus, matching the currently best asymptotic algorithm for MSP, and substantially improving on the previously best O(log(rank))-competitive algorithm for SMSP.
Many scheduling problems can be viewed as allocating rates to jobs, subject to convex packing constraints on the rates. In this paper, we consider the problem of rate allocation when jobs of unknown size arrive online (non-clairvoyant setting), with the goal of minimizing weighted delay or flow time. Though this problem has strong lower bounds on competitive ratio in its full generality, we show positive results for natural and fairly broad sub-classes. More specifically, the subclasses we consider not only generalize several well-studied models such as scheduling with speedup curves and related machine scheduling, but also capture as special cases hitherto unstudied scheduling problems such as routing multi-commodity flows, routing multicast (video-on-demand) trees, and multi-dimensional resource allocation. We establish several first positive results by making connections with two disparate disciplines: Economics and Queueing theory. First, we view the instantaneous allocation of rates as a resource allocation problem. We analyze the natural proportional fairness algorithm from economics. To do this, we extend results from market clearing literature, particularly the Eisenberg-Gale markets and the notions of Walrasian equilibria and Gross Substitutes. This yields the first constant competitive algorithm with constant speed augmentation for single-sink flow routing, routing multicast trees, and multidimensional resource allocation with substitutes resources. Next, we consider the general scheduling problem with packing constraints on rates, but with the restriction that the number of different {\em job types} is fixed. We model this problem as a non-stochastic queueing problem. We generalize a natural algorithm from queueing literature and analyze it by extending queueing theoretic ideas. We show that the competitive ratio, for any constant speed, depends polynomially only on the number of job types. Further, such a dependence on the number of job types is unavoidable for non-clairvoyant algorithms. This yields the first algorithm for scheduling multicommodity flows whose competitive ratio depends polynomially on the size of the underlying graph, and not on the number of jobs.
Modern data centers face a key challenge of effectively serving user requests that arrive online. Such requests are inherently multi-dimensional and characterized by demand vectors over multiple resources such as processor cycles, storage space, and network bandwidth. Typically, different resources require different objectives to be optimized, and Lr norms of loads are among the most popular objectives considered. Furthermore, the server clusters are also often heterogeneous making the scheduling problem more challenging.To address these problems, we consider the online vector scheduling problem in this paper. Introduced by Chekuri and Khanna (SIAM J. of Comp. 2006), vector scheduling is a generalization of classical load balancing, where every job has a vector load instead of a scalar load. The scalar problem, introduced by Graham in 1966, and its many variants (identical and unrelated machines, makespan and Lr-norm optimization, offline and online jobs, etc.) have been extensively studied over the last 50 years. In this paper, we resolve the online complexity of the vector scheduling problem and its important generalizations — for all Lr norms and in both the identical and unrelated machines settings. Our main results are:• For identical machines, we show that the optimal competitive ratio is Θ(log d/ log log d) by giving an online lower bound and an algorithm with an asymptotically matching competitive ratio. The lower bound is technically challenging, and is obtained via an online lower bound for the minimum mono-chromatic clique problem using a novel online coloring game and randomized coding scheme. Our techniques also extend to asymptotically tight upper and lower bounds for general Lr norms.• For unrelated machines, we show that the optimal competitive ratio is Θ(log m + log d) by giving an online lower bound that matches a previously known upper bound. Unlike identical machines, however, extending these results, particularly the upper bound, to general Lr norms requires new ideas. In particular, we use a carefully constructed potential function that balances the individual Lr objectives with the overall (convexified) min-max objective to guide the online algorithm and track the changes in potential to bound the competitive ratio.
We present the first non-trivial online algorithms for the non-uniform, multicommodity buy-at-bulk (MC-BB) network design problem. Our competitive ratios qualitatively match the best known approximation factors for the corresponding offline problems. In particular, we show:1. A polynomial time online algorithm with a poly-logarithmic competitive ratio for the MC-BB problem in undirected edge-weighted graphs.2. A quasi-polynomial time online algorithm with a poly-logarithmic competitive ratio for the MC-BB problem in undirected node-weighted graphs.3. For any fixed epsilon > 0, a polynomial time online algorithm with a competitive ratio of O(k^{1/2+epsilon} polylog(n)) (where k is the number of demands) for MC-BB in directed graphs.4. Algorithms with matching competitive ratios for the prize-collecting variants of all the above problems.Prior to our work, a logarithmic competitive ratio wasknown for undirected, edge-weighted graphs only for the special case of uniform costs (Awerbuch and Azar,FOCS 1997), and a polylogarithmic competitive ratio was known for the edge-weighted single-sink problem (Meyerson, SPAA 2004). To the best of our knowledge, no previous online algorithm was known, even for uniform costs, in the node-weighted and directed settings. Our main engine for the results above is an online reduction theorem of MC-BB problems to their single-sink (SS-BB) counterparts. We use the concept of junction-tree solutions (Chekuri et al., FOCS 2006) that play an important role in solving the offline versions of the problem via a greedy subroutine -- an inherently offline procedure. Our main technical contribution is in designing an online algorithm using only the existence of good junction-trees to reduce an MC-BB instance to multiple SS-BB sub-instances. Along the way, we also give the first non-trivial online node-weighted/directed single-sink buy-at-bulk algorithms. In addition to the new results, our generic reduction also yields new proofs of recent results for the online node-weighted Steiner forest and online group Steiner forest problems.
We give a 2^{n+o(n)}-time and space randomized algorithm for solving the exact Closest Vector Problem (CVP) on n-dimensional Euclidean lattices. This improves on the previous fastest algorithm, the deterministic \tilde{O}(4^n)-time and \tilde{O}(2^n)-space algorithm of Micciancio and Voulgaris.We achieve our main result in three steps. First, we show how to modify the sampling algorithm due to Aggarwal, Dadush, Regev, and Stephens-Davidowitz (ADRS) to solve the problem of discrete Gaussian sampling over lattice shifts, L-t, with very low parameters. While the actual algorithm is a natural generalization of ADRS, the analysis uses substantial new ideas. This yields a 2^{n+o(n)}-time algorithm for approximate CVP with the very good approximation factor \gamma = 1+2^{-o(n/\log n)}. Second, we show that the approximate closest vectors to a target vector can be grouped into "lower-dimensional clusters," and we use this to obtain a recursive reduction from exact CVP to a variant of approximate CVP that "behaves well with these clusters." Third, we show that our discrete Gaussian sampling algorithm can be used to solve this variant of approximate CVP.The analysis depends crucially on some new properties of the discrete Gaussian distribution and approximate closest vectors, which might be of independent interest.
In recent years, a number of works have studied methods for computing the Fourier transform in sublinear time if the output is sparse. Most of these have focused on the discrete setting, even though in many applications the input signal is continuous and naive discretization significantly worsens the sparsity level. We present an algorithm for robustly computing sparse Fourier transforms in the continuous setting. Let $x(t) = x^*(t) + g(t)$, where $x^*$ has a $k$-sparse Fourier transform and $g$ is an arbitrary noise term. Given sample access to $x(t)$ for some duration $T$, we show how to find a $k$-Fourier-sparse reconstruction $x'(t)$ with \[ \frac{1}{T}\int_0^T \abs{x'(t) - x(t)}^2 \mathrm{d} t \lesssim \frac{1}{T}\int_0^T \abs{g(t)}^2 \mathrm{d}t. \] The sample complexity is linear in $k$ and logarithmic in the signal-to-noise ratio and the frequency resolution. Previous results with similar sample complexities could not tolerate an infinitesimal amount of i.i.d. Gaussian noise, and even algorithms with higher sample complexities increased the noise by a polynomial factor. We also give new results for how precisely the individual frequencies of $x^*$ can be recovered.
The algorithmic tasks of computing the Hamming distance between a given pattern P of length m and each location in a text T of length n is one of the most fundamental algorithmic tasks in string algorithms. Karloff [IPL 1999] showed that if one is willing to suffer a 1+epsilon approximation, then it is possible to solve the problem with high probability, in O~(n/epsilon^2) time.Due to related lower bounds for computing the Hamming distance of two strings in the one-way communication complexity model, it is strongly believed that obtaining an algorithm for solving the approximation version cannot be done much faster as a function of 1/epsilon. We show here that this belief is false by introducing a new O~(n/epsilon) time algorithm that succeeds with high probability.The main idea behind our algorithm, which is common in sparse recovery problems, is to reduce the variance of a specific randomized experiment by (approximately) separating heavy hitters from non-heavy hitters. However, while known sparse recovery techniques work very well on vectors, they do not seem to apply here, where we are dealing withmismatches between pairs of characters.We introduce two main algorithmic ingredients. The first is a new sparse recovery method that applies for pair inputs (such as in our setting). The second is a new construction of hash/projection functions, for which have whichallows us to count the number of projections that induce mismatchesbetween two characters exponentially faster than brute force. We expect that these algorithmic techniques will be of independent interest.
We consider the problem of estimating the number of triangles in a graph. This problem has been extensively studied in both theory and practice, but all existing algorithms read the entire graph. In this work we design a {\em sublinear-time\/} algorithm for approximating the number of triangles in a graph, where the algorithm is given query access to the graph. The allowed queries are degree queries, vertex-pair queries and neighbor queries. We show that for any given approximation parameter 0\textless epsilon\textless1, the algorithm provides an estimate hat\{t\} such that with high constant probability, (1-epsilon) t\textless hat\{t\}\textless(1+epsilon)t, where t is the number of triangles in the graph G. The expected query complexity of the algorithm is O(n/t\textasciicircum \{1/3\} + min \{m, m\textasciicircum\{3/2\}/t\}) poly(log n, 1/epsilon), where n is the number of vertices in the graph and m is the number of edges, and the expected running time is (n/t\textasciicircum \{1/3\} + m\textasciicircum\{3/2\}/t) poly(log n, 1/epsilon). We also prove that Omega(n/t\textasciicircum \{1/3\} + min \{m, m\textasciicircum\{3/2\}/t\}) queries are necessary, thus establishing that the query complexity of this algorithm is optimal up to polylogarithmic factors in n (and the dependence on 1/epsilon).
Network interdiction problems are a natural way to study the sensitivity of a network optimization problem with respect to the removal of a limited set of edges or vertices. One of the oldest and best-studied interdiction problems is minimum spanning tree (MST) interdiction. Here, an undirected multigraph with nonnegative edge weights and positive interdiction costs on its edges is given, together with a positive budget B. The goal is to find a subset of edges R, whose total interdiction cost does not exceed B, such that removing R leads to a graph where the weight of an MST is as large as possible. Frederickson and Solis-Oba (SODA 1996) presented an O(log m)-approximation for MST interdiction, where m is the number of edges. Since then, no further progress has been made regarding approximations, and the question whether MST interdiction admits an O(1)-approximation remained open.We answer this question in the affirmative, by presenting a 14-approximation that overcomes two main hurdles that hindered further progress so far. Moreover, based on a well-known 2-approximation for the metric traveling salesman problem (TSP), we show that our O(1)-approximation for MST interdiction implies an O(1)-approximation for a natural interdiction version of metric TSP.
We describe algorithms for the problem of minimum distortion embeddings of finite metric spaces into the real line (or a finite subset of the line). The time complexities of our algorithms are parametrized by the values of the minimum distortion, $\delta$, and the spread, $\Delta$, of the point set we are embedding.We consider the problem of finding the minimum distortion bijection between two finite subsets of the Euclidean line. This problem was known to have an exact polynomial time solution when $\delta$ is below a specific small constant, and hard to approximate within a factor of $\delta^{1-\epsilon}$, when $\delta$ is polynomially large. Let $D$ be the largest adjacent pair distance, a value potentially much smaller than $\Delta$. Then we provide a $\delta^{O(\delta^2 \log^2 D)} n^{O(1)}$ time exact algorithm for this problem, which in particular yields a quasipolynomial running time for constant $\delta$, and polynomial $D$.For the more general problem of embedding any finite metric space $(X,d_X)$ into a finite subset of the line, $Y$, we provide a $\Delta^{O(\delta^2)} (mn)^{O(1)}$ time $O(1)$-approximation algorithm (where $|X|=n$ and $|Y|=m$), which runs in polynomial time provided $\delta$ is a constant and $\Delta$ is polynomial. This in turn allows us to get a $\Delta^{O(\delta^2)} (n)^{O(1)}$ time $O(1)$-approximation algorithm for embedding $(X,d_X)$ into the continuous real line.
A single-sink {\em confluent flow} is a routing of multiple demands to a sink $r$ such thatany flow exiting a node $v$ must use a single arc. Hence, a confluent flow routes on a tree within the network.In uncapacitated (or uniform-capacity) networks, there is an O(1)-approximation algorithm for demand maximizationand a logarithmic approximation algorithm for congestion minimization (Chen et al.).We study the case of capacitated networks, where each node $v$ has its own capacity $\mu(v)$.Indeed, it was recently shown that demand maximization is inapproximable to within polynomial factorsin capacitated networks (Shepherd and Vetta). We circumvent this lower bound in two ways.First, we prove that there is a polylogarithmicapproximation algorithm fordemand maximization in networks that satisfy the ubiquitous {\em no-bottleneck assumption} (nba).Second, we show a bicriteria result for capacitated networkswithout the \nba: there is a polylog factorapproximation guarantee fordemand maximization provided we allow congestion 2.We model the capacitated confluent flows problem using a multilayer linear programming formulation.At the heart of our approach for demand maximization is a rounding procedure for flows on multilayer networkswhich can be viewed as a proposal algorithm for an extension of stable matchings.In addition, the demand maximization algorithms require, as a subroutine, an algorithm forapproximate congestion minimization in a special class of capacitated networks that may be of independentinterest. Specifically, we present apolylogarithmic approximation algorithm forcongestion minimization in monotonic networks -- those networks with theproperty that $\mu(u) \le \mu(v)$ for each arc $(u,v)$.
It has long been known that d-dimensional Euclidean point sets admit (1+ε)-stretch spanners with lightness W_E = (1/ε)^O(d), that is the total edge weight is at most W_E times the weight of the minimum spanning tree of theset [DHN93]. Whether or not a similar result holds for metric spaces with low doubling dimension has remainedan open problem. In this paper, we resolve the question in the affirmative, and show that doubling spaces admit(1 + ε)-stretch spanners with lightness WD = (ddim /ε)O(ddim).
We introduce and construct a pseudorandom object which we call a local correlation breaker (LCB). Informally speaking, an LCB is a function that gets as input a sequence of r (arbitrarily correlated) random variables and an independent weak-source. The output of the LCB is a sequence of r random variables with the following property. If the i'th input random variable is uniform then the i'th output variable is uniform even given a bounded number of any other output variables. That is, an LCB uses the weak-source to break local correlations between random variables. Our construction of LCBs has applications to three-source extractors, mergers with weak-seeds, and a variant of non-malleable extractors, that we introduce.
We continue the study of constructing explicit extractors for independent general weak random sources. The ultimate goal is to give a construction that matches what is given by the probabilistic method --- an extractor for two independent n-bit weak random sources with min-entropy as small as log n+O(1). Previously, the best known result in the two-source case is an extractor by Bourgain {Bourgain05}, which works for min-entropy 0.49n; and the best known result in the general case is an earlier work of the author {Li13b}, which gives an extractor for a constant number of independent sources with min-entropy polylog(n). However, the constant in the construction of {Li13b} depends on the hidden constant in the best known seeded extractor, and can be large; moreover the error in that construction is only 1/poly(n).In this paper, we make two important improvements over the result in {Li13b}. First, we construct an explicit extractor for three independent sources on n bits with min-entropy k >= polylog(n). In fact, our extractor works for one source with poly-logarithmic min-entropy and another independent block source with two blocks each having poly-logarithmic min-entropy. This significantly improves previous constructions, and the next step would be to break the 0.49n barrier in two-source extractors. Second, we improve the error of the extractor from 1/poly(n) to 2^{-k^{Omega(1)}}, which is almost optimal and crucial for cryptographic applications. Some of our techniques may be of independent interests.
We prove a new asymptotic expansion in the central limit theorem for sums of discrete independent random variables. The classical central limit theorem asserts that if Xi is a sequence of n i.i.d. random variables, then S= sum Xi converges to a Gaussian whose first two momentsmatch those of S. Further, the rate of convergence is 1/n^0.5Roughly speaking, asymptotic expansions of the central limit theorem show that by considering a family of limiting distributions specified by k moments (k=2 corresponds toGaussians) and matching the first k moments of S to such a limiting distribution, one can achieve a convergence of n^-(k-1)/2. While such asymptotic expansions have been known since Cramer, they did not apply to discrete and non-identical random variables. Further, the error bounds in nearly all cases was non-explicit (in their dependence on Xi), thus limiting their applicability. In this work, we prove a new asymptotic expansions of the central limit theoremwhich applies to discrete and non-identical random variables and the error bounds are fully explicit.Given the wide applicability of the central limit theorem in probability theory and theoretical computer science, we believe that this new asymptotic expansion theorem will beapplicable in several settings. As a main application in this paper, we give an application in derandomization: Namely, we construct PRGs for the class of combinatorial sums, a class of functions first studied by [GMRZ13] and which generalize many previously studied classes such as combinatorial rectangles, small-biased spaces and modular sums among others. A function f is said to be a combinatorial sum if there exists functions f1, .., fn mapping to Boolean outputs such that f(x1, ..., xn) =f1(x1) +.. + fn(xn). For this class, we give a seed length of O(log m + log^1.5(n/epsilon)), thus improving upon previous results.
We present a new approach to constructing unconditional pseudorandom generators against classes of functions that involve computing a linear function of the inputs. We give an explicit construction of a pseudorandom generator that fools the discrete Fourier transforms of linear functions with seed-length that is nearly logarithmic (up to polyloglog factors) in the input size and the desired error parameter. Our result gives a single pseudorandom generator that fools several important classes of tests computable in logspace that have been considered in the literature, including halfspaces (over general domains), modular tests and combinatorial shapes. For all these classes, our generator is the first that achieves near logarithmic seed-length in both the input length and the error parameter. Getting such a seed-length is a natural challenge in its own right, which needs to be overcome in order to derandomize RL — a central question in complexity theory.Our construction combines ideas from a large body of prior work, ranging from a classical construction of [1] to the recent gradually increasing independence paradigm of [2]–[4], while also introducing some novel analytic machinery which might find other applications.
Submodular and fractionally subadditive (or equivalently XOS) functions play a fundamental role in combinatorial optimization, algorithmic game theory and machine learning. Motivated by learnability of these classes of functions from random examples, we consider the question of how well such functions can be approximated by low-degree polynomials in L_2 norm over the uniform distribution. This question is equivalent to understanding of the concentration of Fourier weight on low-degree coefficients, a central concept in Fourier analysis. We show that 1. For any submodular function f:{0,1}^n -> [0,1], there is a polynomial of degree O(log (1/epsilon) / epsilon^{4/5}) approximating f within epsilon in L_2, and there is a submodular function that requires degree Omega(1/epsilon^{4/5}). 2. For any XOS function f:{0,1}^n -> [0,1], there is a polynomial of degree O(1/epsilon) and there exists an XOS function that requires degree Omega(1/epsilon). This improves on previous approaches that all showed an upper bound of O(1/epsilon^2) for submodular and XOS functions. The best previous lower bound was Omega(1/epsilon^{2/3}) for monotone submodular functions. Our techniques reveal new structural properties of submodular and XOS functions and the upper bounds lead to nearly optimal PAC learning algorithms for these classes of functions.
We prove an average-case depth hierarchy theorem for Boolean circuits over the standard basis of AND, OR, and NOT gates. Our hierarchy theorem says that for every d ≥ 2, there is an explicit n-variable Boolean function f, computed by a linear-size depth-d formula, which is such that any depth-(d − 1) circuit that agrees with f on (1/2 + o^n(1)) fraction of all inputs must have size exp(n^Ω(1/d)). This answers an open question posed by Hastad in his Ph.D. thesis [Has86b].Our average-case depth hierarchy theorem implies that the polynomial hierarchy is infinite relative to a random oracle with probability 1, confirming a conjecture of Hastad [Has86a], Cai [Cai86], and Babai [Bab87]. We also use our result to show that there is no “approximate converse” to the results of Linial, Mansour, Nisan [LMN93] and Boppana [Bop97] on the total influence of constant-depth circuits, thus answering a question posed by Kalai [Kal12] and Hatami [Hat14].A key ingredient in our proof is a notion of random projections which generalize random restrictions.
In this paper we improve upon the running time for finding a point in a convex set given a separation oracle. In particular, given a separation oracle for a convex set $K\subset\mathbb{R}^{n}$ that is contained in a box of radius $R$ we show how to either compute a point in $K$ or prove that $K$ does not contain a ball of radius $\epsilon$ using an expected $O(n\log(nR/\epsilon))$ evaluations of the oracle and additional time $O(n^{3}\log^{O(1)}(nR/\epsilon))$. This matches the oracle complexity and improves upon the $O(n^{\omega+1}\log(nR/\epsilon))$ additional time of the previous fastest algorithm achieved over 25 years ago by Vaidya for the current value of the matrix multiplication constant $\omega
We prove a superlogarithmic lower bound on the conondeterministic communication complexity of the Clique vs. Independent Set problem introduced by Yannakakis (STOC 1988, JCSS 1991). As a corollary, this implies superpolynomial lower bounds for the Alon--Saks--Seymour conjecture in graph theory. Our approach is to first exhibit a query complexity separation for the decision tree analogue of the UP vs. coNP question---namely, unambiguous DNF width vs. CNF width---and then "lift" this separation over to communication complexity using a result from prior work.
We prove new upper and lower bounds on the sample complexity of (epsilon, delta) differentially private algorithms for releasing approximate answers to threshold functions. A threshold function c_x over a totally ordered domain X evaluates to c_x(y) = 1 if y = Omega(log^∗ |X|), which grows with the size of the domain. Inspired by the techniques used to prove this lower bound, we give an algorithm for releasing thresholds with n = Omega(l \cdot log^∗ |X|).To obtain our results, we give reductions in both directions from releasing and properly learning thresholds and the simpler interior point problem. Given a database D of elements from X, the interior point problem asks for an element between the smallest and largest elements in D. We introduce new recursive constructions for bounding the sample complexity of the interior point problem, as well as further reductions and techniques for proving impossibility results for other basic problems in differential privacy.
The privacy risks inherent in the release of a large number of summary statistics were illustrated by Homer et al. (PLoS Genetics, 2008), who considered the case of 1-way marginals of SNP allele frequencies obtained in a genome-wide association study: Given a large number of minor allele frequencies from a case group of individuals diagnosed with a particular disease, together with the genomic data of a single target individual and statistics from a sizable reference dataset independently drawn from the same population, an attacker can determine with high confidence whether or not the target is in the case group. In this work we describe and analyze a simple attack that succeeds even if the summary statistics are significantly distorted, whether due to measurement error or noise intentionally introduced to protect privacy. Our attack only requires that the vector of distorted summary statistics is close to the vector of true marginals in L1 norm. Moreover, the reference pool required by previous attacks can be replacedby a single sample drawn from the underlying population. The new attack, which is not specific to genomics and which handles Gaussian as well as Bernouilli data, significantly generalizes recent lower bounds on the noise needed to ensure differential privacy (Bun, Ullman, and Vadhan, STOC 2014; Steinke and Ullman, 2015), obviating the need for the attacker to control the exact distribution of the data.
New phase transition phenomena have recently been discovered for the stochastic block model, for the special case of two non-overlapping symmetric communities. This gives raise in particular to new algorithmic challenges driven by the thresholds. This paper investigates whether a general phenomenon takes place for multiple communities, without imposing symmetry.In the general stochastic block model SBM(n,p,W), n vertices are split into k communities of relative size {p_i}_{i \in [k]}, and vertices in community i and j connect independently with probability {W_{i,j}}_{i,j \in [k]}. This paper investigates the partial and exact recovery of communities in the general SBM (in the constant and logarithmic degree regimes), and uses the generality of the results to tackle overlapping communities.The contributions of the paper are: (i) an explicit characterization of the recovery threshold in the general SBM in terms of a new f-divergence function D_+, which generalizes the Hellinger and Chernoff divergences, and which provides an operational meaning to a divergence function analog to the KL-divergence in the channel coding theorem, (ii) the development of an algorithm that recovers the communities all the way down to the optimal threshold and runs in quasi-linear time, showing that exact recovery has no information-theoretic to computational gap for multiple communities, (iii) the development of an efficient algorithm that detects communities in the constant degree regime with an explicit accuracy bound that can be made arbitrarily close to 1 when a prescribed signal-to-noise ratio (defined in term of the spectrum of diag(p)W tends to infinity.
Let P be a k-ary predicate over a finite alphabet. Consider a random CSP(P) instance I over n variables with m constraints. When m >> n the instance will be unsatisfiable with high probability and we want to find a certificate of unsatisfiability. When P is the 3-ary OR predicate, this is the well-studied problem of refuting random 3-SAT formulas and an efficient algorithm is known only when m >> n^{3/2}. Understanding the density required for refutation of other predicates is important in cryptography, proof complexity, and learning theory. Previously, it was known that for a k-ary predicate, having m >> n^{\lceil k/2\rceil} constraints suffices for refutation. We give a criterion for predicates that often yields efficient refutation algorithms at much lower densities. Specifically, if P fails to support a t-wise uniform distribution, then there is an efficient algorithm that refutes random CSP(P) instances whp when m >> n^{t/2}. Indeed, our algorithm will ``somewhat strongly" refute the instance I, certifying Opt(I) \le 1−\Omega_k(1), if t=k then we get the strongest possible refutation, certifying Opt(I) \le E[P]+o(1). This last result is new even in the context of random k-SAT. Regarding the optimality of our m \gg nt/2 requirement, prior work on SDP hierarchies has given some evidence that efficient refutation of random CSP(P) may be impossible when m\ll nt/2. Thus there is an indication our algorithm's dependence on m is optimal for every P, at least in the context of SDP hierarchies. Along these lines, we show that our refutation algorithm can be carried out by the O(1)-round SOS SDP hierarchy. Finally, as an application of our result, we falsify assumptions used to show hardness-of-learning results in recent work of Daniely, Linial, and Shalev-Shwartz.
We prove a near optimal round-communication tradeoff for the two-party quantum communication complexity of disjointness. For protocols with r rounds, we prove a lower bound of Omega(n/r) on the communication required for computing disjointness of input size n, which is optimal up to logarithmic factors. The previous best lower bound was Omega(n/rˆ2) due to Jain, Radhakrishnan and Sen. Along the way, we develop several tools for quantum information complexity, one of which is a lower bound for quantum information complexity in terms of the generalized discrepancy method. As a corollary, we get that the quantum communication complexity of any boolean function f is at most 2ˆO(QIC(f)), where QIC(f) is the prior-free quantum information complexity of f (with error 1/3).
We present an algorithm for sparse Hamiltonian simulation whose complexity is optimal (up to log factors) as a function of all parameters of interest. Previous algorithms had optimal or near-optimal scaling in some parameters at the cost of poor scaling in others. Hamiltonian simulation via a quantum walk has optimal dependence on the sparsity at the expense of poor scaling in the allowed error. In contrast, an approach based on fractional-query simulation provides optimal scaling in the error at the expense of poor scaling in the sparsity. Here we combine the two approaches, achieving the best features of both. By implementing a linear combination of quantum walk steps with coefficients given by Bessel functions, our algorithm's complexity (as measured by the number of queries and 2-qubit gates) is logarithmic in the inverse error, and nearly linear in the product tau of the evolution time, the sparsity, and the magnitude of the largest entry of the Hamiltonian. Our dependence on the error is optimal, and we prove a new lower bound showing that no algorithm can have sublinear dependence on tau.
We present an efficient decoding algorithm for constant rate quantum hypergraph-product LDPC codes which provably corrects adversarial errors of weight proportional to the code minimum distance, or equivalently to the square-root of the blocklength.The algorithm runs in time linear in the number of qubits, which makes its performance the strongest to date for linear-time decoding of quantum codes. The algorithm relies on expanding properties, not of the quantum code's factor graph directly, but of the factor graph of the original classical code it is constructed from.
A local tester for a code probabilistically views a small set of coordinates of a given word and based on this local view accepts codewords with probability one while rejecting words far from the code with constant probability. A local tester for a code is said to be ``robust'' if the local views of the tester are far from acceptable views when the word being tested is far from the code. Robust testability of codes play a fundamental role in constructions of probabilistically checkable proofs where robustness is a critical element in composition. In this work we consider a broad class of codes, called lifted codes, that include codes formed by low-degree polynomials, and show that an almost natural test, extending a low-degree test proposed by Raz and Safra (STOC 1997), is robust. Our result is clean and general --- the robustness of the test depends only on the distance of the code being lifted, and is positive whenever the distance is positive.We use our result to get the first robust low-degree test that works when the degree of the polynomial being tested is more than half the field size. Our results also show that the high-rate codes of Guo et al.\ (ITCS 2013) are robustly locally testable with sublinear query complexity. Guo et al. also show several other interesting classes of locally testable codes that can be derived from lifting and our result shows all such codes have robust testers, at the cost of a quadratic blowup in the query complexity of the tester. Of technical interest is an intriguing relationship between tensor product codes and lifted codes that we explore and exploit.
We show that equivalence of deterministic top-down tree-to-string transducersis decidable, thus solving a long standing open problem in formal language theory.We also present efficient algorithms for subclasses:polynomial time for total transducers with unary output alphabet (over a given top-down regular domain language), and co-randomized polynomial time for linear transducers;these results are obtained using techniques from multi-linear algebra.For our main result, we prove that equivalence can be certified by means of inductive invariants using polynomial ideals. This allows us to construct two semi-algorithms, one searching for aproof of equivalence, one for a witness of non-equivalence.
Over the past two decades the main focus of research into first-order (FO) model checking algorithms have been sparse relational structures - culminating in the FPT-algorithm by Grohe, Kreutzer and Siebertz forFO model checking of nowhere dense classes of graphs [STOC'14], with dense structures starting to attract attention only recently. Bova, Ganian and Szeider [CSL-LICS'14] initiated the study of the complexity of FO model checkingon partially ordered sets (posets). Bova, Ganian and Szeider showed that model checking {\em existential} FO logic is fixed-parameter tractable (FPT) on posets of bounded width, where the width of a poset is the size of the largest antichain in the poset. The existence of an FPT algorithm for general FO model checking on posets of bounded width, however, remained open. We resolve this question in the positive by giving an algorithm that takes as its input an n-element poset P of width w and an FO logic formula phi, and determines whether phi holds on P in time f(phi,w).n^2
We study the satisfiability of ordering constraint satisfaction problems (CSPs) above average. We prove the conjecture of Gutin, van Iersel, Mnich, and Yeo that the satisfiability above average of ordering CSPs of arity k is fixed-parameter tractable for every k. Previously, this was only known for k=2 and k=3. We also generalize this result to more general classes of CSPs, including CSPs with predicates defined by linear equations.To obtain our results, we prove a new Bonami-type inequality for the Efron—Stein decomposition. The inequality applies to functions defined on arbitrary product probability spaces. In contrast to other variants of the Bonami Inequality, it does not depend on the mass of the smallest atom in the probability space. We believe that this inequality is of independent interest.
We identify and study relevant structural parameters for the problem of counting perfect matchings in a given input graph G. These generalize the well-known tractable planar case, and they include the genus of G, its apex number (the minimum number of vertices whose removal renders G planar), and its Hadwiger number (the size of a largest clique minor).To study these parameters, we first introduce the notion of combined matchgates, a general technique that bridges parameterized counting problems and the theory of so-called Holants and matchgates: Using combined matchgates, we can simulate certain non-existing gadgets F as linear combinations of t=O(1) existing gadgets. If a graph G features k occurrences of F, we can then reduce G to t^k graphs that feature only existing gadgets, thus enabling parameterized reductions.As applications of this technique, we simplify known 4^g*n^3 time algorithms for counting perfect matchings on graphs of genus g. Orthogonally to this, we show #W[1]-hardness of the permanent on k-apex graphs, implying its #W[1]-hardness under the Hadwiger number. Additionally, we rule out n^o(k/log k) time algorithms under the counting exponential-time hypothesis #ETH.Finally, we use combined matchgates to prove parity-W[1]-hardness of evaluating the permanent modulo 2^k, complementing an O(n^4k) time algorithm by Valiant and answering an open question of Björklund. We also obtain a lower bound of n^Omega(k/log k) under the parity version of the exponential-time hypothesis.
We give an algorithm that, for every fixed k, decides isomorphism of graphs of rank width at most k in polynomial time. As the rank width of a graph is bounded in terms of its clique width, we also obtain a polynomial time isomorphism test for graph classes of bounded clique width.
We show that deterministic communication complexity can be superlogarithmic in the partition number of the associated communication matrix. We also obtain near-optimal deterministic lower bounds for the Clique vs. Independent Set problem, which in particular yields new lower bounds for the log-rank conjecture. All these results follow from a simple adaptation of a communication-to-query simulation theorem of Raz and McKenzie (Combinatorica 1999) together with lower bounds for the analogous query complexity questions.
There has been a resurgence of interest in lower bounds whose truth rests on the conjectured hardness of well known computational problems. These conditional lower bounds have become important and popular due to the painfully slow progress on proving strong unconditional lower bounds. Nevertheless, the long term goal is to replace these conditional bounds with unconditional ones. In this paper we make progress in this direction by studying the cell probe complexity of two conjectured to be hard problems of particular importance: matrix-vector multiplication and a version of dynamic set disjointness known as \Patrascu's Multiphase Problem. We give improved unconditional lower bounds for these problems as well as introducing new proof techniques of independent interest. These include a technique capable of proving strong threshold lower bounds of the following form: If we insist on having a very fast query time, then the update time has to be slow enough to compute a lookup table with the answer to every possible query. This is the first time a lower bound of this type has been proven.
We prove that it is NP-hard to approximate the non-commutative Grothendieck problem to within any constant factor larger than one-half, which matches the approximation ratio of the algorithm of Naor, Regev, and Vidick (STOC’13). Our proof uses an embedding of finite-dimensional Hilbert spaces into the space of matrices endowed with the trace norm with the property that the image of standard basis vectors is longer than that of unit vectors with no large coordinates.
The vertex cover problem is one of the most important and intensively studied combinatorial optimization problems. Khot and Regevproved that the problem is NP-hard to approximate within a factor2 - epsilon, assuming the Unique Games Conjecture (UGC). This istight because the problem has an easy 2-approximation algorithm.Without resorting to the UGC, the best inapproximability result for theproblem is due to Dinur and Safra: vertex cover is NP-hard to approximate within a factor 1.3606. We prove the following unconditional result about linear programming (LP)relaxations of the problem: every LP relaxation that approximates vertex cover within a factor of 2-epsilon has super-polynomially many inequalities. As a direct consequence of our methods, we also establish that LP relaxations (as well as SDP relaxations) that approximate the independent set problem within any constant factor have super-polynomially many inequalities.
We develop a new approach for uniform generation of combinatorial objects, and apply it to derive a uniform sampler A for d-regular graphs. A can be implemented such that each graph is generated in expected time O(nd^3), provided that d grows more slowly than the square root of n. Our result significantly improves the previously best uniform sampler, which works efficiently only when d is about the one-third power of n, with essentially the same running time for the same d. We also give a linear-time approximate sampler B, which generates a random d-regular graph whose distribution differs from the uniform by o(1) in total variation distance, when d grows more slowly than the square root of n.
We study the computational complexity of several natural problems arising in statistical physics and combinatorics. In particular, we consider the following problems: the mean magnetization and mean energy of the Ising model (both the ferromagnetic and the anti-ferromagnetic settings), the average size of an independent set in the hard core model, and the average size of a matching in the monomer-dimer model. We prove that for all non-trivial values of the underlying model parameters, exactly computing these averages is #P-hard.In contrast to previous results of Sinclair and Srivastava (2013) for the mean magnetization of the ferromagnetic Ising model, our approach does not use any Lee-Yang type theorems about the complex zeros of partition functions. Indeed, it was due to the lack of suitable Lee-Yang theorems for models such as the anti-ferromagnetic Ising model that some of the problems we study here were left open by Sinclair and Srivastava. In this paper, we instead use some relatively simple and well-known ideas from the theory of automatic symbolic integration to complete our hardness reductions.
An instance of the Valued Constraint Satisfaction Problem (VCSP) is given by a finite set of variables, a finite domain of labels, and a sum of functions, each function depending on a subset of the variables. Each function can take finite values specifying costs of assignments of labels to its variables or the infinite value, which indicates infeasible assignments. The goal is to find an assignment of labels to the variables that minimizes the sum.We study (assuming that $P \ne NP$) how the complexity of this very general problem depends on the set of functions allowed in the instances, the so-called constraint language. The case when all allowed functions take values in $\{0,\infty\}$ corresponds to ordinary CSPs, where one deals only with the feasibility issue and there is no optimization. This case is the subject of the Algebraic CSP Dichotomy Conjecture predicting for which constraint languages CSPs are tractable and for which NP-hard. The case when all allowed functions take only finite values corresponds to finite-valued CSP, where the feasibility aspect is trivial and one deals only with the optimization issue. The complexity of finite-valued CSPs was fully classified by Thapper and Zivny.An algebraic necessary condition for tractability of a general-valued CSP with a fixed constraint language was recently given by Kozik and Ochremiak. As our main result, we prove that if a constraint language satisfies this algebraic necessary condition, and the feasibility CSP corresponding to the VCSP with this language is tractable, then the VCSP is tractable. The algorithm is a simple combination of the assumed algorithm for the feasibility CSP and the standard LP relaxation. As a corollary, we obtain that a dichotomy for ordinary CSPs would imply a dichotomy for general-valued CSPs.
We prove a complexity dichotomy for complex-weighted Holant problems with an arbitrary set of symmetric constraint functions on Boolean variables.In the study of counting complexity, such as #CSP, there are problems which are #P-hard over general graphs but P-time solvable over planar graphs. A recurring theme has been that a holographic reduction [Val08] to FKT precisely captures these problems. This dichotomy answers the question: Is this a universal strategy? Surprisingly, we discover new planar tractable problems in the Holant framework (which generalizes #CSP) that are not expressible by a holographic reduction to FKT. In particular, the putative form of a dichotomy for planar Holant problems is false. Nevertheless, we prove a dichotomy for #CSP^2, a variant of #CSP where every variable appears even times, that the presumed universality holds for #CSP^2. This becomes an important tool in the proof of the full dichotomy, which refutes this universality in general. The full dichotomy says that the new P-time algorithms and the strategy of holographic reductions to FKT together are universal for these locally defined counting problems.As a special case of our new planar tractable problems, counting perfect matchings (#PM) over k-uniform hypergraphs is P-time computable when the incidence graph is planar and k >= 5. The same problem is #P-hard when k=3 or k=4, also a consequence of the dichotomy. More generally, over hypergraphs with specified hyperedge sizes and the same planarity assumption, #PM is P-time computable if the greatest common divisor (gcd) of all hyperedge sizes is at least 5.
A non-backtracking walk on a graph is a directed path such that noedge is the inverse of its preceding edge. The non-backtracking matrixof a graph is indexed by its directed edges and can be used to countnon-backtracking walks of a given length. It has been used recently inthe context of community detection and has appeared previously inconnection with the Ihara zeta function and in some generalizations ofRamanujan graphs. In this work, we study the largest eigenvalues ofthe non-backtracking matrix of the Erdos-Renyi random graph andof the Stochastic Block Model in the regime where the number of edgesis proportional to the number of vertices. Our results confirm the"spectral redemption conjecture" that community detection can be madeon the basis of the leading eigenvectors above the feasibilitythreshold.
We prove that there exist bipartite Ramanujan graphs of every degree and every number of vertices.The proof is based on analyzing the expected characteristic polynomial of a union of random perfect matchings, and involves three ingredients: (1) a formula for the expected characteristic polynomial of the sum of a regular graph with a random permutation of another regular graph, (2) a proof that this expected polynomial is real rooted and that the family of polynomials considered in this sum is an interlacing family, and (3) strong bounds on the roots of the expected characteristic polynomial of a union of random perfect matchings, established using the framework of finite free convolutions introduced recently by the authors.
We show that the number of incidences between m distinct pointsand n distinct lines in R^4 is O(2^{c sqrt{logm}} (m^{2/5}n^{4/5}+m) + m^{1/2}n^{1/2}q^{1/4} +m^{2/3}n^{1/3}s^{1/3} + n), for a suitable absolute constantc, provided that no 2-plane contains more than s input lines,and no hyperplane or quadric contains more than q lines. The bound holds without the extra factor 2^{c sqrt{log m}} when m\len^{6/7} or m \ge n^{5/3}. Except for this possible factor, thebound is tight in the worst case.The context of this work is incidence geometry, a topic that hasbeen widely studied for more than three decades, with strongconnections to a variety of topics, from range searching incomputational geometry to the Kakeya problem in harmonic analysisand geometric measure theory. The area has picked up considerablemomentum in the past seven years, following the seminal works ofGuth and Katz, where the later work solves the point-line incidence problem in three dimensions, using new toolsand techniques from algebraic geometry. This work extends theirresult to four dimensions. In doing so, it had to overcome many new technical hurdles that arise from the higher-dimensional context, by developing and adapting more advanced tools from algebraic geometry.
Smoothing properties of the noise operator on the discrete cube and on Gaussian space haveplayed a pivotal role in many fields. In particular, these smoothing effects have seena broad range of applications in theoretical computer science.We exhibit new regularization properties of the noise operator on Gaussian space.More specifically,we show that the mass on level sets of a probability density decays uniformlyunder the Ornstein-Uhlenbeck semigroup. This confirms positively the Gaussian caseof Talagrand's convolution conjecture (1989)on the discrete cube.A major theme is our use of an It\^o process (the ``F\"ollmer drift'')which can be seen as an entropy-optimal coupling between the Gaussian measure and another given measure on Gaussian space.To analyze this process, we employ stochastic calculus and Girsanov's change of measure formula.The ideas and tools employed here provide a new perspective on hypercontractivityin Gaussian space and the discrete cube.In particular, our work gives a new way of studying ``small'' sets in product spaces (e.g.,sets of size $2^{o(n)}$ in the discrete cube) using a form of regularized online gradient descent.
Let X be a sparse random matrix of size n by p (p >> n). We prove that if p > C n log^4 n, then with probability 1-o(1), | X^T v|_1 is close to its expectation for all vectors v in R^n (simultaneously). The bound on p is sharp up to the polylogarithmic factor. The study of this problem is directly motivated by an application. Let A be an n by n matrix, X be an n by p matrix and Y = AX. A challenging and important problem in data analysis, motivated by dictionary learning and other practical problems, is to recover both A and X, given Y. Under normal circumstances, it is clear that this problem is underdetermined. However, in the case when X is sparse and random, Spielman, Wang and Wright showed that one can recover both A and X efficiently from Y with high probability, given that p (the number of samples) is sufficiently large. Their method works for p > C n^2 log^2 n and they conjectured that p > C n log n suffices. The bound n log n is sharp for an obvious information theoretical reason. The matrix concentration result verifies the Spielman et. al. conjecture up to a log^3 n factor. Our proof of the concentration result is based on two ideas. The first is an economical way to apply the union bound. The second is a refined version of Bernstein's concentration inequality for a sum of independent variables. Both have nothing to do with random matrices and are applicable in general settings.
A set function on a ground set of size $n$ is approximately modular if it satisfies every modularity requirement to within an additive error; approximate modularity is the set analog of approximate linearity. In this paper we study how close, in additive error, can approximately modular functions be to truly modular functions. We first obtain a polynomial time algorithm that makes $O(n^2 \log n)$ queries to any approximately modular function to reconstruct a modular function that is $O(\sqrt{n})$-close. We also show an almost matching lower bound: any algorithm would need superpolynomially many queries to construct a modular function that is $o\left(\sqrt{n / \log n}\right)$-close. In a striking contrast to these near-tight computational reconstruction bounds, we then show that for any approximately modular function, there exists a modular function that is $O(\log n)$-close.
We show that every non-adaptive property testing algorithm making a constant number of queries, over a fixed alphabet, can be converted to a sample-based (as per [Goldreich and Ron, 2015]) testing algorithm whose average number of queries is a fixed, smaller than 1, power of n. Since the query distribution of the sample-based algorithm is not dependent at all on the property, or the original algorithm, this has many implications in scenarios where there are many properties that need to be tested for concurrently, such as testing (relatively large) unions of properties, or converting a Merlin-Arthur Proximity proof (as per [Gur and Rothblum, 2013]) to a proper testing algorithm.The proof method involves preparing the original testing algorithm for a combinatorial analysis. For the analysis we develop a structural lemma for hypergraphs that may be of independent interest. When analyzing a hypergraph that was extracted from a 2-sided test, it allows for finding generalized sunflowers that provide for a large-deviation type analysis. For 1-sided tests the bounds can be improved further by applying Janson's inequality directly over our structures.
We give a general unified method that can be used for $L_1$ {\em closeness testing} of a wide range of univariate structured distribution families. More specifically, we design a sample optimal and computationally efficient algorithm for testingthe equivalence of two unknown (potentially arbitrary) univariate distributions under the $\mathcal{A}_k$-distance metric:Given sample access to distributions with density functions $p, q: I \to \R$, we want to distinguish between the cases that $p=q$ and $\|p-q\|_{\mathcal{A}_k} \ge \eps$ with probability at least $2/3$.We show that for any $k \ge 2, \eps>0$, the {\em optimal} sample complexity of the $\mathcal{A}_k$-closeness testingproblem is $\Theta(\max\{ k^{4/5}/\eps^{6/5}, k^{1/2}/\eps^2 \})$.This is the first $o(k)$ sample algorithm for this problem, and yieldsnew, simple $L_1$ closeness testers, in most cases with optimal sample complexity, for broad classes of structured distributions.
An (n,k)-Poisson Multinomial Distribution (PMD) is the distribution of the sum of n independent random vectors supported on the set B_k={e_1,...,e_k} of standard basis vectors in R^k. We prove a structural characterization of these distributions, showing that, for all epsilon > 0, any (n, k)-Poisson multinomial random vector is epsilon-close, in total variation distance, to the sum of a discretized multidimensional Gaussian and an independent (poly(k/epsilon), k)-Poisson multinomial random vector. Our structural characterization extends the multi-dimensional CLT of Valiant and Valiant, by simultaneously applying to all approximation requirements epsilon. In particular, it overcomes factors depending on log n and, importantly, the minimum eigenvalue of the PMD's covariance matrix.We use our structural characterization to obtain an epsilon-cover, in total variation distance, of the set of all (n,k)-PMDs, significantly improving the cover size of Daskalakis and Papadimitriou, and obtaining the same qualitative dependence of the cover size on n and epsilon as the k=2 cover of Daskalakis and Papadimitriou. We further exploit this structure to show that (n,k)-PMDs can be learned to within epsilon in total variation distance from ~O_k(1/epsilon^2) samples, which is near-optimal in terms of dependence on epsilon and independent of n. In particular, our result generalizes the single-dimensional result of Daskalakis, Diakonikolas and Servedio for Poisson binomials to arbitrary dimension. Finally, as a corollary of our results on PMDs, we give a ~O_k(1/epsilon^2) sample algorithm for learning (n,k)-sums of independent integer random variables (SIIRVs), which is near-optimal for constant k.
A random sampling function Sample:U->{0,1} for a key universe U is a distinguisher with probability P if for any given assignment of values v(x) to the keys x in U, including at least one non-zero v(x) != 0, the sampled sum, that is, sum{v(x) | x in U, Sample(x)=1}, is non-zerowith probability at least P. Here the key values may come from anycommutative monoid (addition is commutative and associative and zero is neutral). Such distinguishers were introduced by Vazirani [PhD thesis 1986], and Naor and Naor used them for their small bias probability spaces [STOC'90]. Constant probability distinguishers areused for testing in contexts where the key values are not computeddirectly, yet where the sum is easily computed. A simple example iswhen we get a stream of key value pairs (x_1,v_1),(x_2,v_2),...,(x_n,v_n) where the same key may appear many times. The accumulated value of key x is v(x)=sum{v_i | x_i=x}. For space reasons, we may not be able to maintain v(x) for every key x, but the sampled sum is easily maintained as the single value sum{v_i | Sample(x_i)}.Here we show that when dealing with w-bit integers, if a is a uniform odd w-bit integer and t is a uniform w-bit integer, then Sample(x)=[ax mod 2^w
In this paper we analyze a hash function for k-partitioning a set into bins,obtaining strong concentration bounds for standard algorithms combiningstatistics from each bin.This generic method was originally introduced byFlajolet and Martin [FOCS'83] in order to save a factor Omega(k) of time perelement over k independent samples when estimating the number of distinctelements in a data stream. It was also used in the widely used HyperLogLogalgorithm of Flajolet et al. [AOFA'97] and in large-scale machine learning byLi et al. [NIPS'12] for minwise estimation of set similarity.The main issue of k-partition, is that the contents of different bins may behighly correlated when using popular hash functions. This means thatmethods of analyzing the marginal distribution for a single bin do not apply.Here we show that a tabulation based hash function, mixed tabulation, doesyield strong concentration bounds on the most popular applications ofk-partitioning similar to those we would get using a truly random hashfunction.The analysis is very involved and implies several new results of independentinterest for both simple and double tabulation, e.g. a simple andefficient construction for invertible bloom filters and uniform hashing ona given set.
We show that there exists a graph G with O(n) nodes, where any forest of n nodes is a node-induced subgraph of G. Furthermore, for constant arboricity k, the result implies the existence of a graphwith O(n^k) nodes that contains all n-node graphs as node-induced subgraphs, matching a Omega(n^k) lower bound. The lower bound and previously best upper bounds were presented in Alstrup and Rauhe (FOCS'02). Our upper bounds are obtained through a log_2(n) + O(1) labeling scheme for adjacency queries in forests.We hereby solve an openproblem being raised repeatedly over decades, e.g. in Kannan, Naor, Rudich (STOC 1988), Chung (J. of Graph Theory 1990), Fraigniaud and Korman (SODA 2010).
The Lovasz Local Lemma is a seminal result in probabilistic combinatorics. It gives a sufficient condition on a probability space and a collection of events for the existence of an outcome that simultaneously avoids all of those events. Finding such an outcome by an efficient algorithm has been an active research topic for decades. Breakthrough work of Moser and Tardos (2009) presented an efficient algorithm for a general setting primarily characterized by a product structure on the probability space.In this work we present an efficient algorithm for a much more general setting. Our main assumption is that there exist certain functions, called resampling oracles, that can be invoked to address the undesired occurrence of the events. We show that, in all scenarios to which the original Lovasz Local Lemma applies, there exist resampling oracles, although they are not necessarily efficient. Nevertheless, for essentially all known applications of the Lovasz Local Lemma and its generalizations, we have designed efficient resampling oracles. As applications of these techniques, we present new results for packings of Latin transversals, rainbow matchings and rainbow spanning trees.
We pose and study a fundamental algorithmic problem which we term mixture selection, arising as a building block in a number of game-theoretic applications:Given a function $g$ from the $n$-dimensional hypercube to the bounded interval $[-1,1]$, and an $n \times m$ matrix $A$ with bounded entries, maximize $g(Ax)$ over $x$ in the $m$-dimensional simplex.This problem arises naturally when one seeks to design a lottery over items for sale in an auction, or craft the posterior beliefs for agents in a Bayesian game through the provision of information (a.k.a. signaling).We present an approximation algorithm for this problem when $g$ simultaneously satisfies two ``smoothness'' properties:Lipschitz continuity with respect to the $L^\infty$ norm, and noise stability.The latter notion, which we define and cater to our setting, controls the degree to which low-probability -- and possibly correlated -- errors in the inputs of $g$ can impact its output.The approximation guarantee of our algorithm degrades gracefully as a function of the Lipschitz continuity and noise stability of $g$.In particular, when $g$ is both $O(1)$-Lipschitz continuous and $O(1)$-stable, we obtain an (additive) polynomial-time approximation scheme (PTAS) for mixture selection.We also show that neither assumption suffices by itself for an additive PTAS, and both assumptions together do not suffice for an additive fully polynomial-time approximation scheme (FPTAS).We apply our algorithm for mixture selection to a number of different game-theoretic applications, focusing on problems from mechanism design and optimal signaling.In particular, we make progress on a number of open problems suggested in prior work by easily reducing them to mixture selection:we resolve an important special case of the small-menu lottery design problem posed by Dughmi, Han, and Nisan;we resolve the problem of revenue-maximizing signaling in Bayesian second-price auctions posed by Emek et al. and Miltersen and Sheffet;we design a quasipolynomial-time approximation scheme for the optimal signaling problem in normal form games suggested by Dughmi;and we design an approximation algorithm for the optimal signaling problem in the voting model of Alonso and C\^{a}mara.
For selling a single item to agents with independent but non-identically distributed values, the revenue optimal auction is complex. With respect to it, Hartline and Roughgarden showed that the approximation factor of the second-price auction with an anonymous reserve is between two and four. We consider the more demanding problem of approximating the revenue of the ex ante relaxation of the auction problem by posting an anonymous price (while supplies last) and prove that their worst-case ratio is e. As a corollary, the upper-bound of anonymous pricing or anonymous reserves versus the optimal auction improves from four to e. We conclude that, up to an e factor, discrimination and simultaneity are unimportant for driving revenue in single-item auctions.
We study the optimal lottery problem and the optimal mechanism design problem in the setting of a single unit-demand buyer with item values drawn from independent distributions. Optimal solutions to both problems are characterized by a linear program with exponentially many variables.For the menu size complexity of the optimal lottery problem, we present an explicit, simple instance with distributions of support size 2, and show that exponentially many lotteries are required to achieve the optimal revenue. We also show that, when distributions have support size 2 and share the same high value, the simpler scheme of item pricing can achieve the same revenue as the optimal menu of lotteries. The same holds for the case of two items with support size 2 (but not necessarily the same high value).For the computational complexity of the optimal mechanism design problem, we show that unless the polynomial-time hierarchy collapses (more exactly, P^NP = P^#P), there is no universal efficient randomized algorithm to implement an optimal mechanism even when distributions have support size 3.
We prove that finding a Nash equilibrium of a game is hard, assuming the existence of indistinguishability obfuscation and one-way functions with sub-exponential hardness. We do so by showing how these cryptographic primitives give rise to a hard computational problem that lies in the complexity class PPAD, for which finding Nash equilibrium is complete.Previous proposals for basing PPAD-hardness on program obfuscation considered a strong ``virtual black-box" notion that is subject to severe limitations and is unlikely to be realizable for the programs in question. In contrast, for indistinguishability obfuscation no such limitations are known, and recently, several candidate constructions of indistinguishability obfuscation were suggested based on different hardness assumptions on multilinear maps.Our result provides further evidence of the intractability of finding a Nash equilibrium, one that is extrinsic to the evidence presented so far.
We continue the study of welfare maximization in unit-demand (matching) markets, in a distributed information model where agent's valuations are unknown to the central planner, and therefore communication is required to determine an efficient allocation. Dobzinski, Nisan and Oren (STOC'14) showed that if the market size is n, then r rounds of interaction (with logarithmic bandwidth) suffice to obtain an n^(1/(r+1))-approximation to the optimal social welfare. In particular, this implies that such markets converge to a stable state (constant approximation) in time logarithmic in the market size.We obtain the first multi-round lower bound for this setup. We show that even if the allowable per-round bandwidth of each agent is n^epsilon(r), the approximation ratio of any r-round (randomized) protocol is no better than Omega(n^(exp(-r)),implying an Omega(log log n) lower bound on the rate of convergence of the market to equilibrium.Our construction and technique may be of interest to round-communication tradeoffs in the more general setting of combinatorial auctions, for which the only known lower bound is for simultaneous (r=1) protocols [DNO14].