waashk/dblp huggingface dataset:
bounded-error quantum state identification and exponential separations in communication complexity. we consider the following problem of bounded-error quantum state identification: given either state $\alpha_0$ or state $\alpha_1$, we are required to output &ldquo;0&rdquo;, &ldquo;1&rdquo;, or &ldquo;?&rdquo; (&ldquo;don't know"), such that conditioned on outputting &ldquo;0&rdquo; or &ldquo;1&rdquo;, our guess is correct with high probability. the goal is to maximize the probability of not outputting &ldquo;?&rdquo;. we prove the following direct product theorem: if we are given two such problems, with optimal probabilities $a$ and $b$, respectively, and the states in the first problem are pure, then the optimal probability for the joint bounded-error state identification problem is $o(ab)$. our proof is based on semidefinite programming duality. using this result, we present two exponential separations in the simultaneous message passing model of communication complexity. first, we describe a relation that can be computed with $o(\log n)$ classical bits of communication in the presence of shared randomness, but needs $\omega(n^{1/3})$ communication if the parties don't share randomness, even if communication is quantum. this shows the optimality of yao's recent exponential simulation of shared-randomness protocols by quantum protocols without shared randomness. combined with an earlier separation in the other direction due to bar-yossef, jayram, and kerenidis, this shows that the quantum simultaneous message passing (smp) model is incomparable with the classical shared-randomness smp model. second, we describe a relation that can be computed with $o(\log n)$ classical bits of communication in the presence of shared entanglement, but needs $\omega((n/\log n)^{1/3})$ communication if the parties share randomness but no entanglement, even if communication is quantum. this is the first example in communication complexity of a situation where entanglement buys much more than quantum communication.
lower bounds on the efficiency of encryption and digital signature schemes. a central focus of modern cryptography is to investigate the weakest possible assumptions under which various cryptographic algorithms exist. typically, a proof that a "weak" primitive (e.g., a one-way function) implies the existence of a "strong" algorithm (e.g., a private-key encryption scheme) proceeds by giving an explicit construction of the latter from the former. in addition to showing the existence of such a construction, an equally important research direction is to explore the efficiency of such constructions.among the most fundamental cryptographic algorithms are digital signature schemes and schemes for public- or private-key encryption. here, we show the first lower bounds on the efficiency of any encryption or signature construction based on black-box access to one-way or trapdoor one-way permutations. if s is the assumed security of the permutation π (i.e., no adversary of size s can invert π on a fraction larger than 1/s of its inputs), our results show that:any public-key encryption scheme for m-bit messages must query π at least ω(m log s) times.any private-key encryption scheme for m-bit messages (with k-bit keys) must query π at least ω(m-k/log s) times.any signature verification algorithm for m-bit messages must query π at least ω(m log s) times.our bounds match known upper bounds for the case of encryption.we prove our results in an extension of the impagliazzo-rudich model. that is, we show that any black-box construction beating our lower bounds would imply the unconditional existence of a one-way function.
the round complexity of verifiable secret sharing and secure multicast. the round complexity of interactive protocols is one of their most important complexity measures. in this work we study the exact round complexity of two basic secure computation tasks: verifiable secret sharing (vss) and secure multicast.vss allows a dealer to share a secret among several players in a way that would later allow a unique reconstruction of the secret. it is a well-studied primitive, which is used as a building block in virtually every general protocol for secure multi-party computation. secure multicast is perhaps the simplest non-trivial instance of a secure computation. it allows a dealer to securely distribute an identical message to all players in a prescribed subset m. both types of protocols are parameterized by the number of players, n, and a security threshold, t, which bounds the total number of malicious players (possibly including the dealer).we focus on a standard setting of perfect information-theoretic security, where all players have access to secure point-to-point channels and a common broadcast medium. for both types of primitives we prove, using related techniques, tight tradeoffs between the round complexity and the achievable security threshold. specifically, for the vss problem we show:2-round vss is possible iff n>4t, where the ``if'' direction is realized by an efficient protocol.3-round vss is possible iff n>3t, where the ``if'' direction is realized by an inefficient protocol.4-round efficient vss is possible if n>3t.for the secure multicast problem we show:2-round secure multicast is (efficiently) possible iff
analysis of algorithms, a case study: determinants of polynomials we consider the problem of computing the determinant of a matrix of polynomials; we compare two algorithms (expansion by minors and gaussian elimination), examining each under two models for polynomial computation (dense univariate and totally sparse). the results, while interesting in themselves, also serve to display two points: 1. asymptotic results are sometimes misleading for noninfinite (e.g., practical) problems. 2. models of computation are by definition simplifications of reality: algorithmic analysis should be carried out under several distinct computational models, and should be supported by empirical data.
work-competitive scheduling for cooperative computing with dynamic groups. the problem of cooperatively performing a set of t tasks in a decentralized computing environment subject to failures is one of the fundamental problems in distributed computing. the setting with partitionable networks is especially challenging, as algorithmic solutions must accommodate the possibility that groups of processors become disconnected (and, perhaps, reconnected) during the computation. the efficiency of task-performing algorithms is often assessed in terms of work: the total number of tasks, counting multiplicities, performed by all of the processors during the computation. in general, the scenario where the processors are partitioned into g disconnected components causes any task-performing algorithm to have work $\omega(t\cdot g)$ even if each group of processors performs no more than the optimal number of $\theta(t)$ tasks. given that such pessimistic lower bounds apply to any scheduling algorithm, we pursue a competitive analysis. specifically, this paper studies a simple randomized scheduling algorithm for p asynchronous processors, connected by a dynamically changing communication medium, to complete t known tasks. the performance of this algorithm is compared against that of an omniscient off-line algorithm with full knowledge of the future changes in the communication medium. the paper describes a notion of computation width, which associates a natural number with a history of changes in the communication medium, and shows both upper and lower bounds on work-competitiveness in terms of this quantity. specifically, it is shown that the simple randomized algorithm obtains the competitive ratio $(1+\mathbf{cw}/e)$, where $\mathbf{cw}$ is the computation width and $e$ is the base of the natural logarithm ($e=2.7182\ldots$); this competitive ratio is then shown to be tight.
transition logic: how to reason about temporal properties in a compositional way this paper addresses the problem of obtaining formal proof systems that support reasoning about temporal properties of parallel programs in a way that is compositional or 'syntax directed' - the distinctive feature of e.g. hoare style proof systems. now, temporal properties of programs express properties about execution traces of these programs. in the presence of concurrency, compositionality is obtained by concentrating exclusively on the execution traces associated with the atomic actions of programs - the so-called transitions of those programs. to reason about such transitions in a compositional way, 'transition logic' is proposed, expressing properties of the form &ldquo;every transition of a program, say &agr;, that starts in a state satisfying assertion p, must end in a state validating &rdquo;: [p]&agr;[q]. essential is that these assertions can express properties of control locations of programs, too. for this logic, a compositional proof system is obtained which is proved to be sound and relatively complete. an interesting feature of the proof system is the axiomatization of the flow-of-control of programs. the relevance of this logic is supported by the fact that the temporal behaviour of a program is ultimately provable in terms of properties of its transitions, as shown by the work of z. manna and a. pnueli [16].
tight analyses of two local load balancing algorithms. this paper presents an analysis of the following load balancing algorithm. at each step, each node in a network examines the number of tokens at each of its neighbors and sends a token to each neighbor with at least 2d+1 fewer tokens, where d is the maximum degree of any node in the network. we show that within $o(\delta / \alpha)$ steps, the algorithm reduces the maximum difference in tokens between any two nodes to at most $o((d^2 \log n)/\alpha)$, where $\delta$ is the global imbalance in tokens (i.e., the maximum difference between the number of tokens at any node initially and the average number of tokens), n is the number of nodes in the network, and $\alpha$ is the edge expansion of the network. the time bound is tight in the sense that for any graph with edge expansion $\alpha$, and for any value $\delta$, there exists an initial distribution of tokens with imbalance $\delta$ for which the time to reduce the imbalance to even $\delta/2$ is at least $\omega(\delta/\alpha)$. the bound on the final imbalance is tight in the sense that there exists a class of networks that can be locally balanced everywhere (i.e., the maximum difference in tokens between any two neighbors is at most 2d), while the global imbalance remains $\omega((d^2 \log n) / \alpha)$. furthermore, we show that upon reaching a state with a global imbalance of $o((d^2 \log n)/\alpha)$, the time for this algorithm to locally balance the network can be as large as $\omega(n^{1/2})$. we extend our analysis to a variant of this algorithm for dynamic and asynchronous networks. we also present tight bounds for a randomized algorithm in which each node sends at most one token in each step.
fast, small-space algorithms for approximate histogram maintenance. (math) a vector a of length n is defined implicitly, via a stream of updates of the form "add 5 to a3." we give a sketching algorithm, that constructs a small sketch from the stream of updates, and a reconstruction algorithm, that produces a b-bucket piecewise-constant representation (histogram) h for a from the sketch, such that ||a&mdash;h||&xie;(1+&egr;)||a&mdash;hopt|&#124, where the error ||a&mdash;h|| is either $\ell_1$ (absolute) or $\ell_2$ (root-mean-square) error. the time to process a single update, time to reconstruct the histogram, and size of the sketch are each bounded by poly(b,log(n),log||a,1/&egr;. our result is obtained in two steps. first we obtain what we call a robust histogram approximation for a, a histogram such that adding a small number of buckets does not help improve the representation quality significantly. from the robust histogram, we cull a histogram of desired accruacy and b buckets in the second step. this technique also provides similar results for haar wavelet representations, under $\ell_2$ error. our results have applications in summarizing data distributions fast and succinctly even in distributed settings.
near-optimal sparse fourier representations via sampling. (math) we give an algorithm for finding a fourier representation r of b terms for a given discrete signal signal a of length n, such that $\|\signal-\repn\|_2^2$ is within the factor (1 +&egr;) of best possible $\|\signal-\repn_\opt\|_2^2$. our algorithm can access a by reading its values on a sample set t &sube;[0,n), chosen randomly from a (non-product) distribution of our choice, independent of a. that is, we sample non-adaptively. the total time cost of the algorithm is polynomial in b log(n)log(m)&egr; (where m is the ratio of largest to smallest numerical quantity encountered), which implies a similar bound for the number of samples.
on the fractal behavior of tcp. we propose a natural, mathematically tractable model of tcp which captures both its additive-increase, multiplicative-decrease behavior and its feedback mechanism. neither a fluid nor a mean-field model, our model does not explicitly model the loss process; the losses are entirely determined by the rates of the sources at the time of buffer overflow. the system involves two sources competing to send packets into one recipient buffer of size b, from which bytes are drained at the rate of d per step. we prove that for many choices of the pairs (b,d), the long term behavior of the system is fractal. we conjecture that this fact continues to hold for all b > d and d > 2.
the pebbling problem is complete in polynomial space we examine a pebbling problem which has been used to study the storage requirements of various models of computation. sethi has shown this problem to be np-hard and lingas has shown a generalization to be p-space complete. we prove the original problem p-space complete by employing a modification of lingas's proof. the pebbling problem is one of the few examples of a p-space complete problem not exhibiting any obvious quantifier alternation.
computational complexity of probabilistic turing machines probabilistic turing machines are turing machines with the ability to flip coins in order to make random decisions. we allow probabilistic turing machines small but nonzero error probability in computing number-theoretic functions. an example is given of a function computable more quickly by probabilistic turing machines than by deterministic turing machines. it is shown how probabilistic linear-bounded automata can simulate nondeterministic linear-bounded automata.
intersection-closed full afl and the recursively enumerable languages a study is made of conditions on a language l which ensure that the smallest intersection-closed full afl containing l (written @@@@ @@@@(l)) does or does not contain all recursively enumerable languages. for example, it is shown that if l &euil; {ani/i @@@@ 0}and [equation]inf ni+1/ni>1, then [equation](l) contains all recursively enumerable languages. on the other hand, it is shown that if l @@@@ a* and the ratio of the number of words in l of length less than n to n goes to 1 as [equation], then [equation] does not contain all recursively enumerable languages.
comparative complexity of grammar forms the definition of &ldquo;grammar form&rdquo; introduced in [cg] makes it possible to state and prove results about various types of grammars in a uniform way. among questions naturally formalizable in this framework are many about the complexity or efficiency of grammars of different kinds. grammar forms provide a reasonable way of considering the totality of other forms we might use, and so answering the question with both upper and lower bound results. the general question considered in this paper is the following: which grammar forms are more efficient than other grammar forms for the expression of classes of languages, and how much gain in efficiency is possible? our results deal solely with context-free grammars, and use both derivation complexity and size of grammars as complexity measures.
scheduling data transfers in a network and the set scheduling problem. in this paper we consider the online ftp problem. the goal is to service a sequence of file transfer requests given bandwidth constraints of the underlying communication network. the main result of the paper is a technique that leads to algorithms that optimize several natural metrics, such as max-stretch, total flow time, max flow time, and total completion time. in particular, we show how to achieve optimum total flow time and optimum max-stretch if we increase the capacity of the underlying network by a logarithmic factor. we show that the resource augmentation is necessary by proving polynomial lower bounds on the max-stretch and total flow time for the case where online and offline algorithms are using same-capacity edges. moreover, we also give polylogarithmic lower bounds on the resource augmentation factor necessary in order to keep the total flow time and max-stretch within a constant factor of optimum.
sharp thresholds for monotone properties in random geometric graphs. random geometric graphs result from taking n uniformly distributed points in the unit cube, [0,1]d, and connecting two points if their euclidean distance is at most r, for some prescribed r. we show that monotone properties for this class of graphs have sharp thresholds by reducing the problem to bounding the bottleneck matching on two sets of $n$ points distributed uniformly in [0,1]d. we present upper bounds on the threshold width, and show that our bound is sharp for d = 1 and at most a sublogarithmic factor away for d ≥ 2. interestingly, the threshold width is much sharper for random geometric graphs than for bernoulli random graphs. further, a random geometric graph is shown to be a subgraph, with high probability, of another independently drawn random geometric graph with a slightly larger radius; this property is shown to have no analogue for bernoulli random graphs.
approximation algorithms for max-3-cut and other problems via complex semidefinite programming. a number of recent papers on approximation algorithms have used the square roots of unity, - 1 and 1, to represent binary decision variables for problems in combinatorial optimization, and have relaxed these to unit vectors in real space using semidefinite programming in order to obtain near optimum solutions to these problems. in this paper, we consider using the cube roots of unity, 1, ei2π/3, and ei4π/3, to represent ternary decision variables for problems in combinatorial optimization. here the natural relaxation is that of unit vectors in complex space. we use an extension of semidefinite programming to complex space to solve the natural relaxation, and use a natural extension of the random hyperplane technique introduced by the authors in goemans and williamson (j. acm 42 (1995) 1115-1145) to obtain near-optimum solutions to the problems. in particular, we consider the problem of maximizing the total weight of satisfied equations xu - xv ≡ c (mod 3) and inequations xu - xv ≢ c (mod 3), where xu ∈ {0, 1, 2} for all u. this problem can be used to model the max-3-cut problem and a directed variant we call max-3-dicut. for the general problem, we obtain a 0.793733-approximation algorithm. if the instance contains only inequations (as it does for max-3-cut), we obtain a performance guarantee of 7/12 + 3/4π2 arccos2(-1/4) - ε > 0.836008. this compares with proven performance guarantees of 0.800217 for max-3-cut (by frieze and jerrum (algorithmica 18 (1997) 67-81) and 1/3 + 10-8 for the general problem (by andersson et al. (j. algorithms 39 (2001) 162-204)). it matches the guarantee of 0.836008 for max-3-cut found independently by de klerk et al. (on approximate graph colouring and max-k-cut algorithms based on the ℓ-function, manuscript, october 2000). we show that all these algorithms are in fact equivalent in the case of max-3- cut, and that our algorithm is the same as that of anderson et al. in the general case.
the complexity of choosing an h-colouring (nearly) uniformly at random. cooper, dyer, and frieze [j. algorithms, 39 (2001), pp. 117--134] studied the problem of sampling h-colorings (nearly) uniformly at random. special cases of this problem include sampling colorings and independent sets and sampling from statistical physics models such as the widom--rowlinson model, the beach model, the potts model and the hard-core lattice gas model. cooper et al. considered the family of "cautious" ergodic markov chains with uniform stationary distribution and showed that, for every fixed connected "nontrivial " graph h, every such chain mixes slowly. in this paper, we give a complexity result for the problem. namely, we show that for any fixed graph h with no trivial components, there is unlikely to be any polynomial almost uniform sampler (paus) for h-colorings. we show that if there were a paus for the h-coloring problem, there would also be a paus for sampling independent sets in bipartite graphs, and, by the self-reducibility of the latter problem, there would be a fully polynomial randomized approximation scheme (fpras) for #bis---the problem of counting independent sets in bipartite graphs. dyer, goldberg, greenhill, and jerrum have shown that #bis is complete in a certain logically defined complexity class. thus, a paus for sampling h-colorings would give an fpras for the entire complexity class. in order to achieve our result we introduce the new notion of sampling-preserving reduction which seems to be more useful in certain settings than approximation-preserving reduction.
on finding the exact solution of a zero-one knapsack problem given a 0-1 knapsack problem with input drawn from a certain probability distribution, we show that for every &egr; > 0, there is a self-checking polynomial-time algorithm that finds an optimal solution with probability at least 1 -&egr;. we also prove some upper and lower bounds on random variables related to the problem.
reducibility among equilibrium problems. we address the fundamental question of whether the nash equilibria of a game can be computed in polynomial time. we describe certain efficient reductions between this problem for normal form games with a fixed number of players and graphical games with fixed degree. our main result is that the problem of solving a game for any constant number of players, is reducible to solving a 4-player game.
parallel symmetry-breaking in sparse graphs we describe efficient deterministic techniques for breaking symmetry in parallel. the techniques work well on rooted trees and graphs of constant degree or genus. our primary technique allows us to 3-color a rooted tree in &ogr;(lg*n) time on an erew pram using a linear number of processors. we apply these techniques to construct fast linear processor algorithms for several problems, including (&dgr; + 1)-coloring constant-degree graphs, 5-coloring planar graphs, and finding depth-first-search trees in planar graphs. we also prove lower bounds for 2-coloring directed lists and for finding maximal independent sets in arbitrary graphs.
compression and ranking a complexity-theoretic approach to the classical data compression problem is to define a notion of language compression by a machine in a certain complexity class, and to study language classes compressible under the above definition. languages that can be compressed efficiently (e.g. by a probabilistic polynomial time machine) are of special interest. we define the notion of language compressibility, and show that sufficiently sparse &ldquo;easy&rdquo; languages (e.g. polynomial time) can be compressed efficiently. we also define a notion of ranking (which is an optimal compression) and show that some &ldquo;very easy&rdquo; languages (e.g. unambiguous context-free languages) can be ranked efficiently. we exhibit languages which cannot be compressed or ranked efficiently. the notion of compressibility is closely related to kolmogorov complexity and randomness. we discuss this relationship and the complexity-theoretic implications of our results.