waashk/dblp huggingface dataset:
integrality gaps for sherali-adams relaxations. we prove strong lower bounds on integrality gaps of sherali-adams relaxations for max cut, vertex cover, sparsest cut and other problems. our constructions show gaps for sherali-adams relaxations that survive nδ rounds of lift and project. for max cut and vertex cover, these show that even nδ rounds of sherali-adams do not yield a better than 2-ε approximation. the main combinatorial challenge in constructing these gap examples is the construction of a fractional solution that is far from an integer solution, but yet admits consistent distributions of local solutions for all small subsets of variables. satisfying this consistency requirement is one of the major hurdles to constructing sherali-adams gap examples. we present a modular recipe for achieving this, building on previous work on metrics with a local-global structure. we develop a conceptually simple geometric approach to constructing sherali-adams gap examples via constructions of consistent local sdp solutions. this geometric approach is surprisingly versatile. we construct sherali-adams gap examples for unique games based on our construction for max cut together with a parallel repetition like procedure. this in turn allows us to obtain sherali-adams gap examples for any problem that has a unique games based hardness result (with some additional conditions on the reduction from unique games). using this, we construct 2-ε gap examples for maximum acyclic subgraph that rules out any family of linear constraints with support at most nδ.
sherali-adams relaxations of the matching polytope. we study the sherali-adams lift-and-project hierarchy of linear programming relaxations of the matching polytope. our main result is an asymptotically tight expression 1+1/k for the integrality gap after k rounds of this hierarchy. the result is derived by a detailed analysis of the lp after k rounds applied to the complete graph k_{2d+1}. we give an explicit recurrence for the value of this lp, and hence show that its gap exhibits a "phase transition," dropping from close to its maximum value 1+1/2d to close to 1 around the threshold k=2d-θ(√d). we also show that the rank of the matching polytope (i.e., the number of sherali-adams rounds until the integer polytope is reached) is exactly 2d-1.
affine dispersers from subspace polynomials. an affine disperser over f2n for sources of dimension d is a function f: f2n → f2 such that for any affine space s ⊆ f2n of dimension at least d, we have {f(s) : s in s} = f2. affine dispersers have been considered in the context of deterministic extraction of randomness from structured sources of imperfect randomness. previously, explicit constructions of affine dispersers were known for every d = ω(n), due to barak et. al.[2] and bourgain[10] (the latter in fact gives stronger objects called affine extractors). in this work we give the first explicit affine dispersers for sublinear dimension. specifically, our dispersers work even when d = ω(n4/5). the main novelty in our construction lies in the method of proof, which relies on elementary properties of subspace polynomials. in contrast, the previous works mentioned above relied on sum-product theorems for finite fields.
max cut and the smallest eigenvalue. we describe a new approximation algorithm for max cut. our algorithm runs in ~o(n2) time, where n is the number of vertices, and achieves an approximation ratio of .531. on instances in which an optimal solution cuts a 1-ε fraction of edges, our algorithm finds a solution that cuts a 1-4√ε + 8ε-o(1) fraction of edges. our main result is a variant of spectral partitioning, which can be implemented in nearly linear time. given a graph in which the max cut optimum is a 1-ε fraction of edges, our spectral partitioning algorithm finds a set s of vertices and a bipartition l,r=s-l of s such that at least a 1-o(√ε) fraction of the edges incident on s have one endpoint in l and one endpoint in r. (this can be seen as an analog of cheeger's inequality for the smallest eigenvalue of the adjacency matrix of a graph.) iterating this procedure yields the approximation results stated above. a different, more complicated, variant of spectral partitioning leads to a polynomial time algorithm that cuts a 1/2 + e-ω(1/ε) fraction of edges in graphs in which the optimum is 1/2 + ε.
online and stochastic survivable network design. consider the edge-connectivity survivable network design problem: given a graph g = (v,e) with edge-costs, and edge-connectivity requirements rij for every pair of vertices i,j, find an (approximately) minimum-cost network that provides the required connectivity. while this problem is known to admit good approximation algorithms in the offline case, no algorithms were known for this problem in the online setting. in this paper, we give a randomized o(rmax log3 n) competitive online algorithm for this edge-connectivity network design problem, where rmax = maxij rij. our algorithms use the standard embeddings of graphs into random subtrees (i.e., into singly connected subgraphs) as an intermediate step to get algorithms for higher connectivity. our results for the online problem give us approximation algorithms that admit strict cost-shares with the same strictness value. this, in turn, implies approximation algorithms for (a) the rent-or-buy version and (b) the (two-stage) stochastic version of the edge-connected network design problem with independent arrivals. for these two problems, if we are in the case when the underlying graph is complete and the edge-costs are metric (i.e., satisfy the triangle inequality), we improve our results to give o(1)-strict cost shares, which gives constant-factor rent-or-buy and stochastic algorithms for these instances.
a new approach to auctions and resilient mechanism design. we put forward a new approach to mechanism design, and exemplify it via a new mechanism guaranteeing significant revenue in unrestricted combinatorial auctions. our mechanism (1) succeeds in a new and very adversarial collusion model; (2) works in a new, equilibrium-less, and very strong solution concept; (3) benchmarks its performance against the knowledge that the players have about each other; (4) is computationally efficient and preserves the players' privacy to an unusual extent.
numerical linear algebra in the streaming model. we give near-optimal space bounds in the streaming model for linear algebra problems that include estimation of matrix products, linear regression, low-rank approximation, and approximation of matrix rank. in the streaming model, sketches of input matrices are maintained under updates of matrix entries; we prove results for turnstile updates, given in an arbitrary order. we give the first lower bounds known for the space needed by the sketches, for a given estimation error ε. we sharpen prior upper bounds, with respect to combinations of space, failure probability, and number of passes. the sketch we use for matrix a is simply sta, where s is a sign matrix. our results include the following upper and lower bounds on the bits of space needed for 1-pass algorithms. here a is an n x d matrix, b is an n x d' matrix, and c := d+d'. these results are given for fixed failure probability; for failure probability δ>0, the upper bounds require a factor of log(1/δ) more space. we assume the inputs have integer entries specified by o(log(nc)) bits, or o(log(nd)) bits. (matrix product) output matrix c with f(atb-c) ≤ ε f(a) f(b). we show that θ(cε-2log(nc)) space is needed. (linear regression) for d'=1, so that b is a vector b, find x so that ax-b ≤ (1+ε) minx' ∈ reald ax'-b. we show that θ(d2ε-1 log(nd)) space is needed. (rank-k approximation) find matrix tak of rank no more than k, so that f(a-tak) ≤ (1+ε) f{a-ak}, where ak is the best rank-k approximation to a. our lower bound is ω(kε-1(n+d)log(nd)) space, and we give a one-pass algorithm matching this when a is given row-wise or column-wise. for general updates, we give a one-pass algorithm needing [o(kε-2(n + d/ε2)log(nd))] space. we also give upper and lower bounds for algorithms using multiple passes, and a sketching analog of the cur decomposition.
short seed extractors against quantum storage. in the classical privacy amplification problem alice and bob share information that is only partially secret towards an eavesdropper charlie. their goal is to distill this information to a shorter string that is completely secret. the classical privacy amplification problem can be solved almost optimally using extractors. an interesting variant of the problem, where the eavesdropper charlie is allowed to keep quantum information rather than just classical information, was introduced by konig, maurer and renner. in this setting, the eavesdropper charlie may entangle himself with the input (without changing it) and the only limitation charlie has is that it may keep at most b qubits of storage. a natural question is whether there are classical extractors that are good even against quantum storage. recent work has shown that some classical extractors miserably fail against quantum storage. at the same time, it was shown that some other classical extractors work well even against quantum storage, but all these extractors had a large seed length that was either as large as the extractor output, or as large as the quantum storage available to the eavesdropper. in this paper we show that a modified version of trevisan's extractor is good even against quantum storage, thereby giving the first such construction with logarithmic seed length. the technique we use is a combination of trevisan's approach of constructing an extractor from a black-box pseudorandom generator, together with locally list-decodable codes and previous work done on quantum random access codes.
the detectability lemma and quantum gap amplification. the quantum analogue of the constraint satisfaction problem is the fundamental physics question of finding the minimal energy state of a local hamiltonian --- each term of the hamiltonian specifies a local constraint whose violation contributes to the energy of the given quantum state. however, in general it is not meaningful to ask for the probability that a given quantum state violates at least one constraint; the difficulty being that the terms of the hamiltonian do not commute. we show how to make sense of this notion under mild restrictions on the form of the hamiltonian. we then provide two main results. we first prove the quantum detectability lemma, which states that the probability of detecting a violation of a constraint in a local hamiltonian system is bounded from below by some constant times the minimal energy of the system. the proof reveals some intrinsic structure of the hilbert space of local hamiltonians, which is captured in the "exponential decay" lemma, and formalized using a novel decomposition of the hilbert space called the xy decomposition. as an application of the detectability lemma, we prove our second main result: a quantum analogue of the classical gap amplification lemma using random walks over expander graphs, which was the seed for dinur's celebrated new proof of the pcp theorem [6]. we hope that these results will pave the way to better understandings of the computational properties of local hamiltonians systems, and to the evolving field of quantum hamiltonian complexity.
conditional hardness for satisfiable 3-csps. in this paper we study a fundamental open problem in the area of probabilistic checkable proofs: what is the smallest s such that np ⊆ napcp1,s[o(log n),3]? in the language of hardness of approximation, this problem is equivalent to determining the smallest s such that getting an s-approximation for satisfiable 3-bit constraint satisfaction problems ("3-csps") is np-hard. the previous best upper bound and lower bound for s are 20/27+µ by khot and saket [ks06], and 5/8 (assuming np subseteq bpp) by zwick [zwi98]. in this paper we close the gap assuming khot's d-to-1 conjecture. formally, we prove that if khot's d-to-1 conjecture holds for any finite constant integer d, then np napcp1,5/8+ µ[o(log n),3] for any constant µ > 0. our conditional result also solves hastad's open question [has01] on determining the inapproximability of satisfiable max-ntw ("not two") instances and confirms zwick's conjecture [zwi98] that the 5/8-approximation algorithm for satisfiable 3-csps is optimal.
random walks on polytopes and an affine interior point method for linear programming. let k be a polytope in rn defined by m linear inequalities. we give a new markov chain algorithm to draw a nearly uniform sample from k. the underlying markov chain is the first to have a mixing time that is strongly polynomial when started from a "central" point x0. if s is the supremum over all chords pq passing through x0 of (|p-x0|)/(|q-x0|) and ε is an upper bound on the desired total variation distance from the uniform, it is sufficient to take o(m n( n log (s m) + log 1/ε)) steps of the random walk. we use this result to design an affine interior point algorithm that does a single random walk to solve linear programs approximately. more precisely, suppose q = {z | bz ≤ 1} contains a point z such that ct z ≥ d and r := supz ∈ q |bz| + 1, where b is an m x n matrix. then, after τ = o(mn (n ln(mr/ε) + ln 1/δ)) steps, the random walk is at a point xτ for which ct xτ ≥ d(1-ε) with probability greater than 1-δ. the fact that this algorithm has a run-time that is provably polynomial is notable since the analogous deterministic affine algorithm analyzed by dikin has no known polynomial guarantees.
a deterministic reduction for the gap minimum distance problem: [extended abstract]. determining the minimum distance of a linear code is one of the most important problems in algorithmic coding theory. the exact version of the problem was shown to be np-complete in [14]. in [8], the gap version of the problem was shown to be np-hard for any constant factor under a randomized reduction. it was shown in the same paper that the minimum distance problem is not approximable in randomized polynomial time to the factor 2log1-ε n unless np ⊆ rtime(2polylog(n)). in this paper, we derandomize the reduction and thus prove that there is no deterministic polynomial time algorithm to approximate the minimum distance to any constant factor unless p=np. we also prove that the minimum distance is not approximable in deterministic polynomial time to the factor 2log1-εn unless np ⊆ dtime(2polylog(n)). as the main technical contribution, for any constant 2/3
testing juntas nearly optimally. a function on n variables is called a k-junta if it depends on at most k of its variables. in this article, we show that it is possible to test whether a function is a k-junta or is "far" from being a k-junta with o(kε + k log k ) queries, where epsilon is the approximation parameter. this result improves on the previous best upper bound of o (k3/2)ε queries and is asymptotically optimal, up to a logarithmic factor. we obtain the improved upper bound by introducing a new algorithm with one-sided error for testing juntas. notably, the algorithm is a valid junta tester under very general conditions: it holds for functions with arbitrary finite domains and ranges, and it holds under any product distribution over the domain. a key component of the analysis of the new algorithm is a new structural result on juntas: roughly, we show that if a function f is "far" from being a k-junta, then f is "far" from being determined by k parts in a random partition of the variables. the structural lemma is proved using the efron-stein decomposition method.
fully homomorphic encryption using ideal lattices. we propose a fully homomorphic encryption scheme -- i.e., a scheme that allows one to evaluate circuits over encrypted data without being able to decrypt. our solution comes in three steps. first, we provide a general result -- that, to construct an encryption scheme that permits evaluation of arbitrary circuits, it suffices to construct an encryption scheme that can evaluate (slightly augmented versions of) its own decryption circuit; we call a scheme that can evaluate its (augmented) decryption circuit bootstrappable. next, we describe a public key encryption scheme using ideal lattices that is almost bootstrappable. lattice-based cryptosystems typically have decryption algorithms with low circuit complexity, often dominated by an inner product computation that is in nc1. also, ideal lattices provide both additive and multiplicative homomorphisms (modulo a public-key ideal in a polynomial ring that is represented as a lattice), as needed to evaluate general circuits. unfortunately, our initial scheme is not quite bootstrappable -- i.e., the depth that the scheme can correctly evaluate can be logarithmic in the lattice dimension, just like the depth of the decryption circuit, but the latter is greater than the former. in the final step, we show how to modify the scheme to reduce the depth of the decryption circuit, and thereby obtain a bootstrappable encryption scheme, without reducing the depth that the scheme can evaluate. abstractly, we accomplish this by enabling the encrypter to start the decryption process, leaving less work for the decrypter, much like the server leaves less work for the decrypter in a server-aided cryptosystem.
the extended bg-simulation and the characterization of t-resiliency. a distributed task t on n processors is an input/output relation between a collection of processors' inputs and outputs. while all tasks are solvable if no processor may ever crash, the flp result revealed that the possibility of a failure of just a single processor precludes a solution to the task of consensus. that is consensus is not solvable 1-resiliently. yet, some nontrivial tasks are wait-free solvable, i.e. n-1-resiliently. what tasks are solvable if at most t processors may crash? i.e. what tasks are solvable t-resiliently? the herlihy-shavit condition characterizes wait-free solvability, i.e., when t=n-1. the borowsky-gafni (bg) simulation extends this characterization to the t-resilient case for the case "colorless" tasks - tasks like consensus in which one processor can adopt the output of any other processor. it does this by reducing questions about t-resilient solvability, to a question of wait-free solvability. the latter question has been characterized. in this paper, we amend the bg-simulation to result in the extended-bg-simulation, an extension that yields a full characterization of t-resilient solvability: a task t on n processors is solvable t-resiliently iff all tasks t' on t+1 simulators s0,..., st created as follows are wait-free solvable. simulator si is given an input of processor pi as well as the input to a set of processors of size n-(t+1) with ids higher than i. simulator si outputs for pi as well as for a (possibly different) set of processors of size n-(t+1) with ids higher than i. the input/output of the t+1 simulators have to be a projection of a single original input/output tuple-pair in t. we demonstrate the convenience that the characterization provides, in two ways. first, we prove a new equivalence result: we show that n processes can solve t-resiliently weak renaming with n+(t+1)-2 names, where n>1 and 0
on oblivious ptas's for nash equilibrium. if a class of games is known to have a nash equilibrium with probability values that are either zero or ω(1) -- and thus with support of bounded size -- then obviously this equilibrium can be found exhaustively in polynomial time. somewhat surprisingly, we show that there is a ptas for the class of games whose equilibria are guaranteed to have small --- o(1/n) -- values, and therefore large -- ω(n) -- supports. we also point out that there is a ptas for games with sparse payoff matrices, a family for which the exact problem is known to be ppad-complete [chen, deng, teng 2006]. both algorithms are of a special kind that we call oblivious: the algorithm just samples a fixed distribution on pairs of mixed strategies, and the game is only used to determine whether the sampled strategies comprise an ε-nash equilibrium; the answer is "yes" with inverse polynomial probability (in the second case, the algorithm is actually deterministic). these results bring about the question: is there an oblivious ptas for finding a nash equilibrium in general games? we answer this question in the negative; our lower bound comes close to the quasi-polynomial upper bound of [lipton, markakis, mehta 2003]. another recent ptas for anonymous games [daskalakis, papadimitriou 2007 and 2008, daskalakis 2008] is also oblivious in a weaker sense appropriate for this class of games (it samples from a fixed distribution on unordered collections of mixed strategies), but its running time is exponential in 1/ε. we prove that any oblivious ptas for anonymous games with two strategies and three player types must have 1/εα in the exponent of the running time for some α ≥ 1/3, rendering the algorithm in [daskalakis 2008] (which works with any bounded number of player types) essentially optimal within oblivious algorithms. in contrast, we devise a poly n • (1/ε)o(\log2(1/ε)) non-oblivious ptas for anonymous games with two strategies and any bounded number of player types. the key idea of our algorithm is to search not over unordered sets of mixed strategies, but over a carefully crafted set of collections of the first o(log 1/ε) moments of the distribution of the number of players playing strategy 1 at equilibrium. the algorithm works because of a probabilistic result of more general interest that we prove: the total variation distance between two sums of independent indicator random variables decreases exponentially with the number of moments of the two sums that are equal, independent of the number of indicators.
maxmin allocation via degree lower-bounded arborescences. we consider the problem of maxmin allocation of indivisible goods. there are m items to be distributed among n players. each player $i$ has a nonnegative valuation pij for an item j, and the goal is to allocate items to players so as to maximize the minimum total valuation received by each player. there is a large gap in our understanding of this problem. the best known positive result is an ~o(√ n)-approximation algorithm, while there is only a factor 2 hardness known. better algorithms are known for the restricted assignment case where each item has exactly one nonzero value for the players. we study the effect of bounded degree for items: each item has a nonzero value for at most d players. we show that essentially the case d = 3 is equivalent to the general case, and give a 4-approximation algorithm for d = 2. the current algorithmic results for maxmin allocation are based on a complicated lp relaxation called the configuration lp. we present a much simpler lp which is equivalent in power to the configuration lp. we focus on a special case of maxmin allocation-a family of instances on which this lp has a polynomially large gap. the technical core of our result for this case comes from an algorithm for an interesting new optimization problem on directed graphs, maxmindegree arborescence, where the goal is to produce an arborescence of large outdegree. we develop an nε-approximation for this problem that runs in no(1/ε) time and obtain a a polylogarithmic approximation that runs in quasipolynomial time, using a lift-and-project inspired lp formulation. in fact, we show that our results imply a rounding algorithm for the relaxations obtained by t rounds of the sherali-adams hierarchy applied to a natural lp relaxation of the problem. roughly speaking, the integrality gap of the relaxation obtained from t rounds of sherali-adams is at most n1/t. we are able to extend the latter result to a more general class of instances. along the way, we prove a result about the existence of a perfect matching in a probabilistically pruned graph which may be of independent interest.