waashk/dblp huggingface dataset:
qip = pspace. we prove that the complexity class qip, which consists of all problems having quantum interactive proof systems, is contained in pspace. this containment is proved by applying a parallelized form of the matrix multiplicative weights update method to a class of semidefinite programs that captures the computational power of quantum interactive proofs. as the containment of pspace in qip follows immediately from the well-known equality ip = pspace, the equality qip = pspace follows.
a shorter proof of the graph minor algorithm: the unique linkage theorem. at the core of the seminal graph minor theory of robertson and seymour is a powerful theorem which describes the structure of graphs excluding a fixed minor. this result is used to prove wagner's conjecture and provide a polynomial time algorithm for the disjoint paths problem when the number of the terminals is fixed (i.e, the graph minor algorithm). however, both results require the full power of the graph minor theory, i.e, the structure theorem. in this paper, we show that this is not true in the latter case. namely, we provide a new and much simpler proof of the correctness of the graph minor algorithm. specifically, we prove the "unique linkage theorem" without using graph minors structure theorem. the new argument, in addition to being simpler, is much shorter, cutting the proof by at least 200 pages. we also give a new full proof of correctness of an algorithm for the well-known edge-disjoint paths problem when the number of the terminals is fixed, which is at most 25 pages long.
extensions and limits to vertex sparsification. suppose we are given a graph g = (v, e) and a set of terminals k ⊂ v. we consider the problem of constructing a graph h = (k, eh) that approximately preserves the congestion of every multicommodity flow with endpoints supported in k. we refer to such a graph as a flow sparsifier. we prove that there exist flow sparsifiers that simultaneously preserve the congestion of all multicommodity flows within an o(log k / log log k)-factor where |k| = k. this bound improves to o(1) if g excludes any fixed minor. this is a strengthening of previous results, which consider the problem of finding a graph h = (k, eh) (a cut sparsifier) that approximately preserves the value of minimum cuts separating any partition of the terminals. indirectly our result also allows us to give a construction for better quality cut sparsifiers (and flow sparsifiers). thereby, we immediately improve all approximation ratios derived using vertex sparsification in [14]. we also prove an ω(log log k) lower bound for how well a flow sparsifier can simultaneously approximate the congestion of every multicommodity flow in the original graph. the proof of this theorem relies on a technique (which we refer to as oblivious dual certifcates) for proving super-constant congestion lower bounds against many multicommodity flows at once. our result implies that approximation algorithms for multicommodity flow-type problems designed by a black box reduction to a "uniform" case on k nodes (see [14] for examples) must incur a super-constant cost in the approximation ratio.
improved algorithms for computing fisher's market clearing prices: computing fisher's market clearing prices. we give the first strongly polynomial time algorithm for computing an equilibrium for the linear utilities case of fisher's market model. we consider a problem with a set b of buyers and a set g of divisible goods. each buyer i starts with an initial integral allocation ei of money. the integral utility for buyer i of good j is uij. we first develop a weakly polynomial time algorithm that runs in o(n4 log umax + n3 emax) time, where n = |b| + |g|. we further modify the algorithm so that it runs in o(n4 log n) time. these algorithms improve upon the previous best running time of o(n8 log umax + n7 log emax), due to devanur et al.
public-key cryptography from different assumptions. this paper attempts to broaden the foundations of public-key cryptography. we construct new public-key encryption schemes based on new hardness-on-average assumptions for natural combinatorial np-hard optimization problems. we consider the following assumptions: it is infeasible to solve a random set of sparse linear equations mod 2, of which a small fraction is noisy. it is infeasible to distinguish between a random unbalanced bipartite graph, and such a graph in which we "plant" at random in the large side a set s with only |s|/3 neighbors. there is a pseudorandom generator in ncz where every output depends on a random constant-size subset of the inputs. we obtain semantically secure public key encryption schemes based on several combinations of these assumptions with different parameters. in particular we obtain public key encryption from assumption~1 on its own, yielding the first noisy-equations type public key scheme in which the noise rate is higher than one over the square root of the number of equations. we also obtain public-key encryption based on a combination of assumptions~2 and~3. these are arguably of more "combinatorial"/"private-key" nature than any assumptions used before for public-key cryptography. our proof involves novel "search to decision" and "search to prediction" reductions for sparse noisy linear equations. the strength of our assumptions raise new algorithmic and pseudorandomness questions (and new parameters for old ones). we give some evidence for these assumptions by studying their resistance to certain classes of natural algorithms, including semi-definite programs, aco circuits, low-degree polynomials, and cycle counting. we also relate our assumptions to other problems such as planted clique and learning juntas.
almost tight bounds for rumour spreading with conductance. we show that if a connected graph with $n$ nodes has conductance φ then rumour spreading, also known as randomized broadcast, successfully broadcasts a message within ~o(φ-1 • log n), many rounds with high probability, regardless of the source, by using the push-pull strategy. the ~o(••) notation hides a polylog φ-1 factor. this result is almost tight since there exists graph of n nodes, and conductance φ, with diameter ω(φ-1 • log n). if, in addition, the network satisfies some kind of uniformity condition on the degrees, our analysis implies that both both push and pull, by themselves, successfully broadcast the message to every node in the same number of rounds.
a sparse johnson: lindenstrauss transform. dimension reduction is a key algorithmic tool with many applications including nearest-neighbor search, compressed sensing and linear algebra in the streaming model. in this work we obtain a sparse version of the fundamental tool in dimension reduction -- the johnson-lindenstrauss transform. using hashing and local densification, we construct a sparse projection matrix with just ~o(1/ε) non-zero entries per column. we also show a matching lower bound on the sparsity for a large class of projection matrices. our bounds are somewhat surprising, given the known lower bounds of ω(1/ε2) both on the number of rows of any projection matrix and on the sparsity of projection matrices generated by natural constructions. using this, we achieve an ~o(1/ε) update time per non-zero element for a (1 ε)-approximate projection, thereby substantially outperforming the ~o(1/ε2) update time required by prior approaches. a variant of our method offers the same guarantees for sparse vectors, yet its ~o(d) worst case running time matches the best approach of ailon and liberty.
oblivious rams without cryptogrpahic assumptions. ithmic increase in the time and space requirements is possible on a probabilistic (coin flipping) ram without using any cryptographic assumptions. the simulation will fail with a negligible probability. if n memory locations are used, then the probability of failure is at most n-log n. pippenger and fischer has shown in 1979, see [7], that a turing machine with one-dimensional tapes, performing a computation of length n can be simulated on-line by an oblivious turing machine with two dimensional tapes, in time o(n log n), where a turing machine is oblivious if the movements of it heads as a function of time are independent of its input. for rams the notion of obliviousness was defined by goldreich in 1987 in [2], and he proved a simulation theorem about it. a ram is oblivious if the distribution of its memory access pattern, which memory cells are accessed at which time, is independent of the program running on the ram, provided that the time used by the program is fixed. that is, an adversary watching the memory access will not know anything about the program running on the machine apart from its total time. ostrovsky, improving goldreich's theorem, has shown in 1990, see [4], [5], [3], that a ram using n memory cells can a be simulated by an oblivious ram with a random oracle (where the random bits can be accessed repeatedly) so that the increase of the space and time requirement is only about a factor of ln (goldreich's factor was about exp[(log n)1/2]). in both cases the oblivious ram with a random oracle, can be replaced, by an oblivious probabilistic (coin-flipping) ram, provided that we accept some unproven cryptographic assumptions, e.g., the existence of a one-way function. in this paper we show that simulation with an oblivious, coin-flipping ram, with only a factor of ln increase in time and space requirements, is possible, even without any cryptographic assumptions.
towards polynomial lower bounds for dynamic problems. we consider a number of dynamic problems with no known poly-logarithmic upper bounds, and show that they require nω(1) time per operation, unless 3sum has strongly subquadratic algorithms. our result is modular: (1) we describe a carefully-chosen dynamic version of set disjointness (the "multiphase problem"), and conjecture that it requires n^omega(1) time per operation. all our lower bounds follow by easy reduction. (2) we reduce 3sum to the multiphase problem. ours is the first nonalgebraic reduction from 3sum, and allows 3sum-hardness results for combinatorial problems. for instance, it implies hardness of reporting all triangles in a graph. (3) it is plausible that an unconditional lower bound for the multiphase problem can be established via a number-on-forehead communication game.
conditional hardness of precedence constrained scheduling on identical machines. already in 1966, graham showed that a simple procedure called list scheduling yields a 2-approximation algorithm for the central problem of scheduling precedence constrained jobs on identical machines to minimize makespan. till this date it has remained the best algorithm and whether it can or cannot be improved has become a major open problem in scheduling theory. we address this problem by establishing a quite surprising relation between the approximability of the considered problem and that of scheduling precedence constrained jobs on a single machine to minimize weighted completion time. more specifically, we prove that if the single machine problem is hard to approximate within a factor of 2-ε then the considered parallel machine problem, even in the case of unit processing times, is hard to approximate within a factor of 2-ζ, where ζ tends to 0 as ε tends to 0. combining this with bansal & khot's recent hardness result for the single machine problem gives that it is np-hard to improve upon the approximation ratio obtained by graham, assuming a new variant of the unique games conjecture.
deterministic identity testing of depth-4 multilinear circuits with bounded top fan-in. we give the first sub-exponential time deterministic polynomial identity testing algorithm for depth-4 multilinear circuits with a small top fan-in. more accurately, our algorithm works for depth-4 circuits with a plus gate at the top (also known as σπσπ circuits) and has a running time of exp(poly(log(n),log(s),k)) where n is the number of variables, s is the size of the circuit and k is the fan-in of the top gate. in particular, when the circuit is of polynomial (or quasi-polynomial) size, our algorithm runs in quasi-polynomial time. in [av08], it was shown that derandomizing polynomial identity testing for general σπσπ circuits implies a derandomization of polynomial identity testing in general arithmetic circuits. prior to this work sub-exponential time deterministic algorithms were known for depth-$3$ circuits with small top fan-in and for very restricted versions of depth-4 circuits. the main ingredient in our proof is a new structural theorem for multilinear σπσπ(k) circuits. roughly, this theorem shows that any nonzero multilinear σπσπ(k) circuit contains an `embedded' nonzero multilinear σπς(k) circuit. using ideas from previous works on identity testing of sums of read-once formulas and of depth-3 multilinear circuits, we are able to exploit this structure and obtain an identity testing algorithm for multilinear σπσπ(k) circuits.
local list-decoding and testing of random linear codes from high error. in this paper, we give surprisingly efficient algorithms for list-decoding and testing random linear codes. our main result is that random sparse linear codes are locally list-decodable and locally testable in the high-error regime with only a constant number of queries. more precisely, we show that for all constants c> 0 and γ > 0, and for every linear code c ⊆ 0,1n which is: sparse: |c| ≤ nc, and unbiased: each nonzero codeword in c has weight in (1/2 - n-γ, 1/2 + n-γ), c is locally testable and locally list-decodable from (1/2 - ε)-fraction worst-case errors using only poly(1/ε) queries to a received word. we also give subexponential time algorithms for list-decoding arbitrary unbiased (but not necessarily sparse) linear codes in the high-error regime. in particular, this yields the first subexponential time algorithm even for the problem of (unique) decoding random linear codes of inverse-polynomial rate from a fixed positive fraction of errors. earlier, kaufman and sudan had shown that sparse, unbiased codes can be locally (unique) decoded and locally tested from a constant fraction of errors, where this constant fraction tends to 0 as the number of codewords grows. our results significantly strengthen their results, while also having significantly simpler proofs. at the heart of our algorithms is a natural "self-correcting" operation defined on codes and received words. this self-correcting operation transforms a code c with a received word w into a simpler code c' and a related received word w', such that w is close to c if and only if w' is close to c'. starting with a sparse, unbiased code c and an arbitrary received word w, a constant number of applications of the self-correcting operation reduces us to the case of local list-decoding and testing for the hadamard code, for which the well known algorithms of goldreich-levin and blum-luby-rubinfeld are available. this yields the constant-query local algorithms for the original code c. our algorithm for decoding unbiased linear codes in subexponential time proceeds similarly. applying the self-correcting operation to an unbiased code c and an arbitrary received word a super-constant number of times, we get reduced to the problem of learning noisy parities, for which non-trivial subexponential time algorithms were recently given by blum-kalai-wasserman and feldman-gopalan-khot-ponnuswami. our result generalizes a result of lyubashevsky, which gave a subexponential time algorithm for decoding random linear codes of inverse-polynomial rate from random errors.
efficiency improvements in constructing pseudorandom generators from one-way functions. we give a new construction of pseudorandom generators from any one-way function. the construction achieves better parameters and is simpler than that given in the seminal work of hastad, impagliazzo, levin, and luby [sicomp '99]. the key to our construction is a new notion of "next-block pseudoentropy", which is inspired by the notion of "inaccessible entropy" recently introduced in [haitner, reingold, vadhan, wee, stoc '09]. an additional advantage over previous constructions is that our pseudorandom generators are parallelizable and invoke the one-way function in a non-adaptive manner. using [applebaum, ishai, kushilevitz, sicomp '06], this implies the existence of pseudorandom generators in nc^0 based on the existence of one-way functions in nc^1.
differential privacy under continual observation. differential privacy is a recent notion of privacy tailored to privacy-preserving data analysis [11]. up to this point, research on differentially private data analysis has focused on the setting of a trusted curator holding a large, static, data set; thus every computation is a "one-shot" object: there is no point in computing something twice, since the result will be unchanged, up to any randomness introduced for privacy. however, many applications of data analysis involve repeated computations, either because the entire goal is one of monitoring, e.g., of traffic conditions, search trends, or incidence of influenza, or because the goal is some kind of adaptive optimization, e.g., placement of data to minimize access costs. in these cases, the algorithm must permit continual observation of the system's state. we therefore initiate a study of differential privacy under continual observation. we identify the problem of maintaining a counter in a privacy preserving manner and show its wide applicability to many different problems.
how to compress interactive communication. we describe new ways to simulate 2-party communication protocols to get protocols with potentially smaller communication. we show that every communication protocol that communicates c bits and reveals i bits of information about the inputs to the participating parties can be simulated by a new protocol involving at most ~o(√ci) bits of communication. if the protocol reveals i bits of information about the inputs to an observer that watches the communication in the protocol, we show how to carry out the simulation with ~o(i) bits of communication. these results lead to a direct sum theorem for randomized communication complexity. ignoring polylogarithmic factors, we show that for worst case computation, computing n copies of a function requires √n times the communication required for computing one copy of the function. for average case complexity, given any distribution μ on inputs, computing n copies of the function on n inputs sampled independently according to μ requires √n times the communication for computing one copy. if μ is a product distribution, computing n copies on n independent inputs sampled according to μ requires n times the communication required for computing the function. we also study the complexity of computing the sum (or parity) of n evaluations of f, and obtain results analogous to those above.
message passing algorithms: a success looking for theoreticians. message passing algorithms have emerged as a powerful heuristic for addressing hard problems in a variety of applied fields. interesting and successful examples can be found in domain as diverse as coding and communications, signal processing, artificial intelligence, game theory, high-dimensional statistics. at least four reasons can be found for this success: 1. they are widely applicable whenever the underlying problem has a 'local' structure with respect to a suitable graph; 2. they are easy to implement and have linear or next-to-linear complexity (within coding they are widely implemented in hardware); 4. they often subsume existing heuristics as special cases; 5. on some random instance distributions which are important in practice, they can be analyzed precisely and tuned to achieve near-optimal performances. each of these five points can be argued through examples. it would be highly desirable to make sense of them (of any subset of them)in a consistent theory.
matroid matching: the power of local search. we consider the classical matroid matching problem. unweighted matroid matching for linear matroids was solved by lovasz, and the problem is known to be intractable for general matroids. we present a ptas for unweighted matroid matching for general matroids. in contrast, we show that natural lp relaxations have an ω(n) integrality gap and moreover, ω(n) rounds of the sherali-adams hierarchy are necessary to bring the gap down to a constant. more generally, for any fixed k>=2 and ε>0, we obtain a (k/2+ε)-approximation for matroid matching in k-uniform hypergraphs, also known as the matroid k-parity problem. as a consequence, we obtain a (k/2+ε)-approximation for the problem of finding the maximum-cardinality set in the intersection of k matroids. we have also designed a 3/2-approximation for the weighted version of a special case of matroid matching, the matchoid problem.
privacy amplification with asymptotically optimal entropy loss. we study the problem of "privacy amplification": key agreement between two parties who both know a weak secret w, such as a password. (such a setting is ubiquitous on the internet, where passwords are the most commonly used security device.) we assume that the key agreement protocol is taking place in the presence of an active computationally unbounded adversary eve. the adversary may have partial knowledge about w, so we assume only that w has some entropy from eve's point of view. thus, the goal of the protocol is to convert this non-uniform secret w into a uniformly distributed string r that is fully secret from eve. r may then be used as a key for running symmetric cryptographic protocols (such as encryption, authentication, etc.). because we make no computational assumptions, the entropy in r can come only from w. thus such a protocol must minimize the entropy loss during its execution, so that r is as long as possible. the best previous results have entropy loss of θ(κ2), where κ is the security parameter, thus requiring the password to be very long even for small values of κ. in this work, we present the first protocol for information-theoretic key agreement that has entropy loss linear in the security parameter. the result is optimal up to constant factors. we achieve our improvement through a somewhat surprising application of error-correcting codes for the edit distance.
multi-parameter mechanism design and sequential posted pricing. we study the classic mathematical economics problem of bayesian optimal mechanism design where a principal aims to optimize expected revenue when allocating resources to self-interested agents with preferences drawn from a known distribution. in single parameter settings (i.e., where each agent's preference is given by a single private value for being served and zero for not being served) this problem is solved [20]. unfortunately, these single parameter optimal mechanisms are impractical and rarely employed [1], and furthermore the underlying economic theory fails to generalize to the important, relevant, and unsolved multi-dimensional setting (i.e., where each agent's preference is given by multiple values for each of the multiple services available) [25]. in contrast to the theory of optimal mechanisms we develop a theory of sequential posted price mechanisms, where agents in sequence are offered take-it-or-leave-it prices. we prove that these mechanisms are approximately optimal in single-dimensional settings. these posted-price mechanisms avoid many of the properties of optimal mechanisms that make the latter impractical. furthermore, these mechanisms generalize naturally to multi-dimensional settings where they give the first known approximations to the elusive optimal multi-dimensional mechanism design problem. in particular, we solve multi-dimensional multi-unit auction problems and generalizations to matroid feasibility constraints. the constant approximations we obtain range from 1.5 to 8. for all but one case, our posted price sequences can be computed in polynomial time. this work can be viewed as an extension and improvement of the single-agent algorithmic pricing work of [9] to the setting of multiple agents where the designer has combinatorial feasibility constraints on which agents can simultaneously obtain each service.