waashk/dblp huggingface dataset:
a full characterization of quantum advice. we prove the following surprising result: given any quantum state rho on n qubits, there exists a local hamiltonian h on poly(n) qubits (e.g., a sum of two-qubit interactions), such that any ground state of h can be used to simulate rho on all quantum circuits of fixed polynomial size. in terms of complexity classes, this implies that bqp/qpoly is contained in qma/poly, which supersedes the previous result of aaronson that bqp/qpoly is contained in pp/poly. indeed, we can exactly characterize quantum advice, as equivalent in power to untrusted quantum advice combined with trusted classical advice. proving our main result requires combining a large number of previous tools -- including a result of alon et al. on learning of real-valued concept classes, a result of aaronson on the learnability of quantum states, and a result of aharonov and regev on "qma+ super-verifiers" -- and also creating some new ones. the main new tool is a so-called majority-certificates lemma, which is closely related to boosting in machine learning, and which seems likely to find independent applications. in its simplest version, this lemma says the following. given any set s of boolean functions on n variables, any function f in s can be expressed as the pointwise majority of m=o(n) functions f1,...,fm in s, such that each fi is the unique function in s compatible with o(log|s|) input/output constraints.
the maximum multiflow problems with bounded fractionality. this paper addresses a fundamental issue in the multicommodity flow theory. for an undirected capacitated supply graph (g,c) having commodity graph h, the maximum multiflow problem is to maximize the total flow-value of multicommodity flows with respect to (g,c;h). for a commodity graph h, the fractionality of h is the least positive integer k with property that there exists a 1/k-integral optimal multiflow in the maximum multiflow problem for every integer-capacitated supply graph (g,c) having h as a commodity graph. if such a positive integer k does not exist, then the fractionality is defined to be infinity. around 1990, karzanov raised the problem of classifying commodity graphs with finite fractionality, gave a necessary condition (property p) for the finiteness of fractionality, and conjectured that the property p is also sufficient. our main result affirmatively solves karzanov's conjecture in algorithmic form: if h has property p, then there exists a 1/24-integral optimal multiflow in maximum multiflow problem for every integer-capacitated supply graph having h as a commodity graph, and there exists a strongly polynomial time algorithm to find it. our proof is based on a special combinatorial duality relation involving a class of cat(0) complexes, and on a fractional version of the splitting-off method for finding an optimal multiflow with a bounded denominator.
erratum for: on basing one-way functions on np-hardness. this is an errata for our stoc'06 paper, "on basing one-way functions on np-hardness". there is a gap in the proof of our results regarding adaptive reductions, and we currently do not know whether theorem 3 (as stated in section 2) holds.
on the structure of cubic and quartic polynomials. in this paper we study the structure of polynomials of degree three and four that have high bias or high gowers norm, over arbitrary prime fields. in particular we obtain the following results. 1. we give a canonical representation for degree three or four polynomials that have a significant bias (i.e. they are not equidistributed). this result generalizes the corresponding results from the theory of quadratic forms. this significantly improves previous results for such polynomials. 2. for the case of degree four polynomials with high gowers norm we show that (a subspace of constant co-dimension of) fn can be partitioned to subspaces of dimension omega(n) such that on each of the subspaces the polynomial is equal to some degree three polynomial. it was previously shown that a quartic polynomial with a high gowers norm is not necessarily correlated with any cubic polynomial. our result shows that a slightly weaker statement does hold. the proof is based on finding a structure in the space of partial derivatives of the underlying polynomial.
on the searchability of small-world networks with arbitrary underlying structure. revisiting the "small-world" experiments of the '60s, kleinberg observed that individuals are very effective at constructing short chains of acquaintances between any two people, and he proposed a mathematical model of this phenomenon. in this model, individuals are the nodes of a base graph, the square grid, capturing the underlying structure of the social network; and this base graph is augmented with additional edges from each node to a few long-range contacts of this node, chosen according to some natural distance-based distribution. in this augmented graph, a greedy search algorithm takes only a polylogarithmic number of steps in the graph size. following this work, several papers investigated the correlations between underlying structure and long-range connections that yield efficient decentralized search, generalizing kleinberg's results to broad classes of underlying structures, such as metrics of bounded doubling dimension, and minor-excluding graphs. we focus on the case of arbitrary base graphs. we show that for a simple long-range contact distribution consistent with empirical observations on social networks, a slight variation of greedy search, where the next hop is to a distant node only if it yields sufficient progress towards the target, requires no(1) steps, where $n$ is the number of nodes. precisely, the expected number of steps for any source-target pair is at most 2(log n)1/2+o(1). this bound almost matches the best known lower bound of ω(2√log n) steps, which applies to a general class of search algorithms. in the context of social networks, our result could be interpreted as: individuals may well be able to construct short chains between people regardless of the underlying structure of the social network.
the limits of buffering: a tight lower bound for dynamic membership in the external memory model. we study the dynamic membership (or dynamic dictionary) problem, which is one of the most fundamental problems in data structures. we study the problem in the external memory model with cell size b bits and cache size m bits. we prove that if the amortized cost of updates is at most 0.999 (or any other constant b log n(n/m)), where n is the number of elements in the dictionary. in contrast, when the update time is allowed to be 1 + o(1), then a bit vector or hash table give query time o(1). thus, this is a threshold phenomenon for data structures. this lower bound answers a folklore conjecture of the external memory community. since almost any data structure task can solve membership, our lower bound implies a dichotomy between two alternatives: (i) make the amortized update time at least 1 (so the data structure does not buffer, and we lose one of the main potential advantages of the cache), or (ii) make the query time at least roughly logarithmic in n. our result holds even when the updates and queries are chosen uniformly at random and there are no deletions; it holds for randomized data structures, holds when the universe size is o(n), and does not make any restrictive assumptions such as indivisibility. all of the lower bounds we prove hold regardless of the space consumption of the data structure, while the upper bounds only need linear space. the lower bound has some striking implications for external memory data structures. it shows that the query complexities of many problems such as 1d-range counting, predecessor, rank-select, and many others, are all the same in the regime where the amortized update time is less than 1, as long as the cell size is large enough (b = polylog(n) suffices). the proof of our lower bound is based on a new combinatorial lemma called the lemma of surprising intersections (losi) which allows us to use a proof methodology where we first analyze the intersection structure of the positive queries by using encoding arguments, and then use statistical arguments to deduce properties of the intersection structure of all queries, even the negative ones. in most other data structure arguments that we know, it is difficult to argue anything about the negative queries. therefore we believe that the losi and this proof methodology might find future uses for other problems.
a quantum lovász local lemma. the lovasz local lemma (lll) is a powerful tool in probability theory to show the existence of combinatorial objects meeting a prescribed collection of "weakly dependent" criteria. we show that the lll extends to a much more general geometric setting, where events are replaced with subspaces and probability is replaced with relative dimension, which allows to lower bound the dimension of the intersection of vector spaces under certain independence conditions. our result immediately applies to the k-qsat problem: for instance we show that any collection of rank 1 projectors with the property that each qubit appears in at most 2k/(e*k) of them, has a joint satisfiable state. we then apply our results to the recently studied model of random k-qsat. recent works have shown that the satisfiable region extends up to a density of 1 in the large k limit, where the density is the ratio of projectors to qubits. using a hybrid approach building on work by laumann et al. we greatly extend the known satisfiable region for random k-qsat to a density of ω(2k/k2). since our tool allows us to show the existence of joint satisfying states without the need to construct them, we are able to penetrate into regions where the satisfying states are conjectured to be entangled, avoiding the need to construct them, which has limited previous approaches to product states.
distributed computation in dynamic networks. in this paper we investigate distributed computation in dynamic networks in which the network topology changes from round to round. we consider a worst-case model in which the communication links for each round are chosen by an adversary, and nodes do not know who their neighbors for the current round are before they broadcast their messages. the model captures mobile networks and wireless networks, in which mobility and interference render communication unpredictable. in contrast to much of the existing work on dynamic networks, we do not assume that the network eventually stops changing; we require correctness and termination even in networks that change continually. we introduce a stability property called t -interval connectivity (for t >= 1), which stipulates that for every t consecutive rounds there exists a stable connected spanning subgraph. for t = 1 this means that the graph is connected in every round, but changes arbitrarily between rounds. we show that in 1-interval connected graphs it is possible for nodes to determine the size of the network and compute any com- putable function of their initial inputs in o(n2) rounds using messages of size o(log n + d), where d is the size of the input to a single node. further, if the graph is t-interval connected for t > 1, the computation can be sped up by a factor of t, and any function can be computed in o(n + n2/t) rounds using messages of size o(log n + d). we also give two lower bounds on the token dissemination problem, which requires the nodes to disseminate k pieces of information to all the nodes in the network. the t-interval connected dynamic graph model is a novel model, which we believe opens new avenues for research in the theory of distributed computing in wireless, mobile and dynamic networks.
an improved lp-based approximation for steiner tree. the steiner tree problem is one of the most fundamental np-hard problems: given a weighted undirected graph and a subset of terminal nodes, find a minimum-cost tree spanning the terminals. in a sequence of papers, the approximation ratio for this problem was improved from 2 to the current best 1.55 [robins,zelikovsky-sidma'05]. all these algorithms are purely combinatorial. a long-standing open problem is whether there is an lp-relaxation for steiner tree with integrality gap smaller than 2 [vazirani,rajagopalan-soda'99]. in this paper we improve the approximation factor for steiner tree, developing an lp-based approximation algorithm. our algorithm is based on a, seemingly novel, iterative randomized rounding technique. we consider a directed-component cut relaxation for the k-restricted steiner tree problem. we sample one of these components with probability proportional to the value of the associated variable in the optimal fractional solution and contract it. we iterate this process for a proper number of times and finally output the sampled components together with a minimum-cost terminal spanning tree in the remaining graph. our algorithm delivers a solution of cost at most ln(4) times the cost of an optimal k-restricted steiner tree. this directly implies a ln(4)+ε
bilipschitz snowflakes and metrics of negative type. we show that there exists a metric space (x,d) such that (x,√d) admits a bilipschitz embedding into l2, but (x,d) does not admit an equivalent metric of negative type. in fact, we exhibit a strong quantitative bound: there are n-point subsets yn ⊆ x such that mapping (yn, d) to a metric of negative type requires distortion ~ω(log n)1/4. in a formal sense, this is the first lower bound specifically against bilipschitz embeddings into negative-type metrics, and therefore unlike other lower bounds, ours cannot be derived from a 1-dimensional poincare inequality. this answers an open question about the strength of strong vs. weak triangle inequalities in a number of semi-definite programs. our construction sheds light on the power of various notions of "dual flows" that arise in algorithms for approximating the sparsest cut problem. it also has other interesting implications for bilipschitz embeddings of finite metric spaces.
satisfiability allows no nontrivial sparsification unless the polynomial-time hierarchy collapses. consider the following two-player communication process to decide a language l: the first player holds the entire input x but is polynomially bounded; the second player is computationally unbounded but does not know any part of x; their goal is to cooperatively decide whether x belongs to l at small cost, where the cost measure is the number of bits of communication from the first player to the second player. for any integer d ≥ 3 and positive real ε we show that if satisfiability for n-variable d-cnf formulas has a protocol of cost o(nd-ε) then conp is in np/poly, which implies that the polynomial-time hierarchy collapses to its third level. the result even holds when the first player is conondeterministic, and is tight as there exists a trivial protocol for ε = 0. under the hypothesis that conp is not in np/poly, our result implies tight lower bounds for parameters of interest in several areas, namely sparsification, kernelization in parameterized complexity, lossy compression, and probabilistically checkable proofs. by reduction, similar results hold for other np-complete problems. for the vertex cover problem on n-vertex d-uniform hypergraphs, the above statement holds for any integer d ≥ 2. the case d=2 implies that no np-hard vertex deletion problem based on a graph property that is inherited by subgraphs can have kernels consisting of o(k2-ε) edges unless conp is in np/poly, where k denotes the size of the deletion set. kernels consisting of o(k^2) edges are known for several problems in the class, including vertex cover, feedback vertex set, and bounded-degree deletion.
the price of privately releasing contingency tables and the spectra of random matrices with correlated rows. marginal (contingency) tables are the method of choice for government agencies releasing statistical summaries of categorical data. in this paper, we derive lower bounds on how much distortion (noise) is necessary in these tables to ensure the privacy of sensitive data. we extend a line of recent work on impossibility results for private data analysis [9, 12, 13, 15] to a natural and important class of functionalities. consider a database consisting of n rows (one per individual), each row comprising d binary attributes. for any subset of t attributes of size |t|=k, the marginal table for t has 2k entries; each entry counts how many times in the database a particular setting of these attributes occurs. we provide lower bounds for releasing all d k k-attribute marginal tables under several different notions of privacy. (1) we give efficient polynomial time attacks which allow an adversary to reconstruct sensitive information given insufficiently perturbed marginal table releases. in particular, for a constant k, we obtain a tight bound of ~ω(min √n, √dk-1) on the average distortion per entry for any mechanism that releases all k-attribute marginals while providing "attribute" privacy (a weak notion implied by most privacy definitions). (2) our reconstruction attacks require a new lower bound on the least singular value of a random matrix with correlated rows. let m(k) be a matrix with d k rows formed by taking all possible k-way entry-wise products of an underlying set of d random vectors from {0,1}n. for constant k, we show that the least singular value of m(k) is ~ω(√dk) with high probability (the same asymptotic bound as for independent rows). (3) we obtain stronger lower bounds for marginal tables satisfying differential privacy. we give a lower bound of ~ω(min {√n, √ dk), which is tight for n ~ω (dk). we extend our analysis to obtain stronger results for mechanisms that add instance-independent noise and weaker results when k is super-constant.
solving polynomial equations in smoothed polynomial time and a near solution to smale's 17th problem. the 17th of the problems proposed by steve smale for the 21st century asks for the existence of a deterministic algorithm computing an approximate solution of a system of n complex polynomials in $n$ unknowns in time polynomial, on the average, in the size n of the input system. a partial solution to this problem was given by carlos beltran and luis miguel pardo who exhibited a randomized algorithm, call it lv, doing so. in this paper we further extend this result in several directions. firstly, we perform a smoothed analysis (in the sense of spielman and teng) of algorithm lv and prove that its smoothed complexity is polynomial in the input size and σ-1, where σ controls the size of the random perturbation of the input systems. secondly, we perform a condition-based analysis of lv. that is, we give a bound, for each system f, of the expected running time of lv with input f. in addition to its dependence on n this bound also depends on the condition of f. thirdly, and to conclude, we return to smale's 17th problem as originally formulated for deterministic algorithms. we exhibit such an algorithm and show that its average complexity is no(log log n). this is nearly a solution to smale's 17th problem.
non-commutative circuits and the sum-of-squares problem. we initiate a direction for proving lower bounds on the size of non-commutative arithmetic circuits. this direction is based on a connection between lower bounds on the size of non-commutative arithmetic circuits and a problem about commutative degree four polynomials, the classical sum-of-squares problem: find the smallest n such that there exists an identity (x12+x22+•• + xk2)• (y1^2+y22+•• + yk2)= f12+f22+ ... +fn2, where each fi = fi(x,y) is bilinear in x={x1,... ,xk} and y={y1,..., yk}. over the complex numbers, we show that a sufficiently strong super-linear lower bound on n in, namely, n ≥ k1+ε with ε >0, implies an exponential lower bound on the size of arithmetic circuits computing the non-commutative permanent. more generally, we consider such sum-of-squares identities for any m polynomial h(x,y), namely: h(x,y) = f12+f22+...+fn2. again, proving n ≥ k1+ε in for any explicit h over the complex numbers gives an exponential lower bound for the non-commutative permanent. our proofs relies on several new structure theorems for non-commutative circuits, as well as a non-commutative analog of valiant's completeness of the permanent. we proceed to prove such super-linear bounds in some restricted cases. we prove that n ≥ ω(k6/5) in (1), if f1,..., fn are required to have integer coefficients. over the real numbers, we construct an explicit m polynomial h such that n in (2) must be at least ω(k2). unfortunately, these results do not imply circuit lower bounds. we also present other structural results about non-commutative arithmetic circuits. we show that any non-commutative circuit computing an ordered non-commutative polynomial can be efficiently transformed to a syntactically multilinear circuit computing that polynomial. the permanent, for example, is ordered. hence, lower bounds on the size of syntactically multilinear circuits computing the permanent imply unrestricted non-commutative lower bounds. we also prove an exponential lower bound on the size of non-commutative syntactically multilinear circuit computing an explicit polynomial. this polynomial is, however, not ordered and an unrestricted circuit lower bound does not follow.
graph expansion and the unique games conjecture. the edge expansion of a subset of vertices s ⊆ v in a graph g measures the fraction of edges that leave s. in a d-regular graph, the edge expansion/conductance φ(s) of a subset s ⊆ v is defined as φ(s) = (|e(s, v\s)|)/(d|s|). approximating the conductance of small linear sized sets (size δ n) is a natural optimization question that is a variant of the well-studied sparsest cut problem. however, there are no known algorithms to even distinguish between almost complete edge expansion (φ(s) = 1-ε), and close to 0 expansion. in this work, we investigate the connection between graph expansion and the unique games conjecture. specifically, we show the following: we show that a simple decision version of the problem of approximating small set expansion reduces to unique games. thus if approximating edge expansion of small sets is hard, then unique games is hard. alternatively, a refutation of the ugc will yield better algorithms to approximate edge expansion in graphs. this is the first non-trivial "reverse" reduction from a natural optimization problem to unique games. under a slightly stronger ugc that assumes mild expansion of small sets, we show that it is ug-hard to approximate small set expansion. on instances with sufficiently good expansion of small sets, we show that unique games is easy by extending the techniques of [4].
on the complexity of #csp. bulatov (2008) has given a dichotomy for the counting constraint satisfaction problem, #csp. a problem from #csp is characterized by a constraint language γ, which is a fixed, finite set of relations over a finite domain. an instance of the problem uses these relations to constrain the values taken by a finite set of variables. bulatov showed that, for any fixed γ, the problem of counting the satisfying assignments of instances of any problem from #csp is either in polynomial time (fp) or #p-complete, according on the structure of the constraint language γ. his proof draws heavily on techniques from universal algebra and cannot be understood without a secure grasp of that field. we give an elementary proof of bulatov's dichotomy, based on succinct representations, which we call frames, of a class of highly structured relations, which we call strongly rectangular. we show that these are precisely the relations that are invariant under a mal'tsev polymorphism. en route, we give a simplification of a decision algorithm for strongly rectangular constraint languages due to bulatov and dalmau (2006). out proof uses no universal algebra, except for the straightforward concept of the mal'tsev polymorphism and is accessible to readers with little background in #csp.