waashk/dblp huggingface dataset:
iterated pushdown automata and complexity classes an iterated pushdown is a pushdown of pushdowns of ... of pushdowns. an iterated exponential function is 2 to the 2 to the ... to the 2 to some polynomial. the main result is that nondeterministic 2-way and multi-head iterated pushdown automata characterize deterministic iterated exponential time complexity classes. this is proved by investigating both nondeterministic and alternating auxiliary iterated pushdown automata, for which similar characterization results are given. in particular it is shown that alternation corresponds to one more iteration of pushdowns. these results are applied to the 1-way iterated pushdown automata: (1) they form a proper hierarchy with respect to the number of iterations, (2) their emptiness problem is complete in deterministic iterated exponential time.
tree transducers, l systems and two-way machines (extended abstract) this extended abstract is a condensed version of the results presented in two technical reports ([16] and [13]). in [16] a systematic treatment of the relationships between parallel rewriting systems (top-down tree transducer, etol system) and two-way machines (2-way gsm, tree-walking automaton, checking stack automaton) is given. particular attention is paid to the effect of restricting the copying power of these devices. in [13] the results of [16] are employed to show that the iteration of nondeterministic top-down tree transducers, of nondeterministic 2-way gsm's and of control on etol systems each gives rise to a proper hierarchy.
testing multivariate linear functions: overcoming the generator bottleneck. the problem of testing program correctness has received considerable attention in computer science. one approach to this problem is the notion of self-testing programs \cite{blumlubyrubinfeld}. self-testing usually becomes more costly in the case of testing multivariate functions. in this paper we present efficient methods for self-testing multivariate linear functions. we then apply these methods to several multivariate linear problems to construct efficient self-testers.
biased dictionaries with fast insert/deletes. a dictionary data structure supports efficient search, insert, and delete operations on n keys from a totally ordered universe. red-black trees, 2-3 trees, avl trees, skip lists and other classic data structures facilitate o(logn) time search, insert and deletes, matching the information theoretic lower bound when access probabilities are uniform i.i.d. if access probabilities are non-uniform but still i.i.d., there are other weighted data structures such as d-trees, biased search trees, splay trees and treaps which can achieve optimality.in many applications, however, the source of nonuniformity in access probabilities is locality of reference: examples include memory, cache, disk and buffer management and emerging applications in internetwork traffic management. in such applications, the access probability of any given key is not i.i.d., but decreases with idle time since the last access to the key.it is possible to adjust the weighted dictionaries to achieve optimal search time even under time dependent distributions; however insert/delete times will be suboptimal at o(logn). in this paper, we present a lazy updating scheme which can be applied to weighted dictionaries to improve their amortized insert/delete performance when access probabilities decrease with time; optimality of search time is preserved. more speci%cally, let r(k) be the number of distinct keys accessed since the last access to key k- that is r(k) is the move-to-front rank of k. let rmax(k) be the maximum rank of k during its lifetime. then our lazy update scheme enables the abovementioned data structures to perform search in o(log r(k)) time and insert/delete in o(log rmax(k)) time. we illustrate our lazy update scheme in the context of a new biased skip list data structure and show that our bounds are optimal.
lower bounds for noisy boolean decision trees. we present a new method for deriving lower bounds to the expected number of queries made by noisy decision trees computing boolean functions. the new method has the feature that expectations are taken with respect to a uniformly distributed random input, as well as with respect to the random noise, thus yielding stronger lower bounds. it also applies to many more functions than do previous results. the method yields a simple proof of the result (previously established by reischuk and schmeltz) that almost all boolean functions of n arguments require omega(n log n) queries, and strengthens this bound from the worst-case over inputs to the average over inputs. the method also yields bounds for specific boolean functions in terms of their spectra (their fourier transforms). the simplest instance of this spectral bound yields the result (previously established by feige, peleg, raghavan and upfal) that the parity function of n arguments requires omega(n log n) queries, and again strengthens this bound from the worst-case over inputs to the average over inputs. in its full generality, the spectral bound applies to the "highly resilient" functions introduced by chor, friedman, goldreich, hastad, rudich and smolensky, and it yields non-linear lower bounds whenever the resiliency is asymptotic to the number of arguments.
approximations of general independent distributions we describe efficient constructions of small probability spaces that approximate the independent distribution for general random variables. previous work on efficient constructions concentrate on approximations of the independent distribution for the special case of uniform boolean-valued random variables. our results yield efficient constructions of small sets with low discrepancy in high dimensional space and have applications to derandomizing randomized algorithms.
a combinatorial problem which is complete in polynomial space we consider a generalization, which we call the shannon switching game on vertices, of a familiar board game called hex. we show that determining who wins such a game if each player plays perfectly is very hard; in fact, it is as hard as carrying out any polynomial-space-bounded computation. this result suggests that the theory of combinatorial games is difficult.
the complexity of pure nash equilibria. we investigate from the computational viewpoint multi-player games that are guaranteed to have pure nash equilibria. we focus on congestion games, and show that a pure nash equilibrium can be computed in polynomial time in the symmetric network case, while the problem is pls-complete in general. we discuss implications to non-atomic congestion games, and we explore the scope of the potential function method for proving existence of pure nash equilibria.
horn clauses and database dependencies (extended abstract) in the last year or so, a number of generalizations of these dependencies have appeared: nicolas's mutual dependencies [ni], which say that a relation is the join of three of its projections; rissanen's and aho, beeri, and ullman's join dependencies ([ri], [abu]), which generalize further to an arbitrary number of projections; paradaens' transitive dependencies [pa], which generalize both fds and mvds; sagiv and walecka's subset dependencies [sw] which generalize embedded mvds; and sadri and ullman's template dependencies [su], which generalize embedded join dependencies. the purpose of this paper is to help bring order to the chaos by presenting certain mathematical properties shared by all of these dependencies. in section 2, we introduce the concept of &ldquo;faithfulness&rdquo; (with respect to direct product), and show that ids and eids are faithful, whereas slight variations are not necessarily faithful. in section 3, we discuss &ldquo;armstrong relations&rdquo;, which were known to exist in certain special cases (such as when the only sentences of interest were functional, multivalued, and join dependencies).in section 4, we discuss finite armstrong relations.in section 5, we present some more counterexamples about the existence of armstrong relations. in section 6, we discuss projections of classes of relations. although zaiddan [za] showed that projections of fd classes are not necessarily fd classes, it turns out that projections of fd classes (and, even more, of id classes) are id classes. in section 7, we discuss certain extensions of our results.
a tight bound on approximating arbitrary metrics by tree metrics. in this paper, we show that any n point metric space can be embedded into a distribution over dominating tree metrics such that the expected stretch of any edge is o(log n). this improves upon the result of bartal who gave a bound of o(log n log log n). moreover, our result is existentially tight; there exist metric spaces where any tree embedding must have distortion ω(log n)-distortion. this problem lies at the heart of numerous approximation and online algorithms including ones for group steiner tree, metric labeling, buy-at-bulk network design and metrical task system. our result improves the performance guarantees for all of these problems.
efficient algorithms for inverting evolution. evolution can be mathematically modelled by a stochastic process that operates on the dna of species. such models are based on the established theory that the dna sequences, or genomes, of all extant species have been derived from the genome of the common ancestor of all species by a process of random mutation and natural selection.a stochastic model of evolution can be used to construct phylogenies, or evolutionary trees, for a set of species. maximum likelihood estimation (mle) methods seek the evolutionary tree which is most likely to have produced the dna under consideration. while these methods are intellectually satisfying, they have not been widely accepted because of their computational intractability.in this paper, we address the intractability of mle methods as follows: we introduce a metric on stochastic process models of evolution. we show that this metric is meaningful by proving that in order for any algorithm to distinguish between two stochastic models that are close according to this metric, it needs to be given many observations. we complement this result with a simple and efficient algorithm for inverting the stochastic process of evolution, that is, for building a tree from observations on two-state characters. (we will use the same techniques in a subsequent paper to solve the problem for multistate characters, and hence for building a tree from dna sequence data.) the tree we build is provably close, in our metric, to the tree generating the data and gets closer as more observations become available.though there have been many heuristics suggested for the problem of finding good approximations to the most likely tree, our algorithm is the first one with a guaranteed convergence rate, and further, this rate is within a polynomial of the lower-bound rate we establish. ours is also the first polynomial-time algorithm that is proven to converge at all to the correct tree.
a tight time lower bound for space-optimal implementations of multi-writer snapshots. a snapshot object consists of a collection of m > 1 components, each capable of storing a value, shared by n processes in an asynchronous shared-memory distributed system. it supports two operations: a process can update any individual component or atomically scan the entire collection to obtain the values of all the components. it is possible to implement a snapshot object using m registers so that each operation takes o(mn) time.in a previous paper, we proved that m registers are necessary to implement a snapshot object with m < n-1 components. here we prove that, for any such space-optimal implementation, ω(mn) steps are required to perform a scan operation in the worst case, matching the upper bound. we also extend our space and time lower bounds to implementations that use single-writer registers in addition to the multi-writer registers. specifically, we prove that at least m multi-writer registers are still needed, provided the scans do not read a large fraction of the single-writer registers. we also prove that any implementation that uses single-writer registers in addition to $m$ multi-writer registers uses ω(√mn) steps in the worst case. our proof yields insight into the structure of any implementation that uses only m multi-writer registers, showing that processes must access the multi-writer registers in a very constrained way.
time-space tradeoffs for implementations of snapshots. a snapshot object is an abstraction of the fundamental problem of obtaining a consistent view of the contents of the shared memory in a distributed system while other processes may concurrently update those contents. a snapshot object stores an array of m components and can be accessed by two operations: an update that changes the value of an individual component and a powerful scan that returns the contents of the entire array.this paper proves time-space tradeoffs for fault-tolerant implementations of a snapshot object from registers that support only read and write operations. for anonymous implementations (where all processes are programmed identically), we prove that a scan requires ω(n/r) time, where n is the number of processes in the system and r is the number of registers used by the implementation. for the general non-anonymous case, we prove that, for any fixed r, the time required to do a scan grows without bound as n increases. these tradeoffs hold even in the case where the snapshot object has just two components.this is the first time a lower bound on the tradeoff between time complexity and the number of registers has been proved for any problem in asynchronous shared-memory systems. we introduce a new tool for proving distributed lower bounds: the notion of a shrinkable execution, from which an adversary can remove portions as necessary.
optimal algorithms for approximate clustering in a clustering problem, the aim is to partition a given set of n points in d-dimensional space into k groups, called clusters, so that points within each cluster are near each other. two objective functions frequently used to measure the performance of a clustering algorithm are, for any l4 metric, (a) the maximum distance between pairs of points in the same cluster, and (b) the maximum distance between points in each cluster and a chosen cluster center; we refer to either measure as the cluster size. we show that one cannot approximate the optimal cluster size for a fixed number of clusters within a factor close to 2 in polynomial time, for two or more dimensions, unless p=np. we also present an algorithm that achieves this factor of 2 in time &ogr;(n log k), and show that this running time is optimal in the algebraic decision tree model. for a fixed cluster size, on the other hand, we give a polynomial time approximation scheme that estimates the optimal number of clusters under the second measure of cluster size within factors arbitrarily close to 1. our approach is extended to provide approximation algorithms for the restricted centers, suppliers, and weighted suppliers problems that run in optimal &ogr;(n log k) time and achieve optimal or nearly optimal approximation bounds.
computing the median with uncertainty. we consider a new model for computing with uncertainty. it is desired to compute a function f(x1,. . .,xn), where x1, . . ., xn are unknown but guaranteed to lie in specified intervals i1, . . ., in. it is possible to query the precise value of any xj at a cost cj. the goal is to pin down the value of f to within a precision $\delta$ at a minimum possible cost. we focus on the selection function f which returns the value of the kth smallest argument. we present optimal offline and online algorithms for this problem.
relations between average case complexity and approximation complexity. we investigate relations between average case complexity and the complexity of approximation. under the assumption that refuting 3sat is hard on average on a natural distribution, we derive new hardness of approximation results.
on sums of independent random variables with unbounded variance, and estimating the average degree in a graph. we prove the following inequality: for every positive integer $n$ and every collection $x_1, \ldots, x_n$ of nonnegative independent random variables, each with expectation 1, the probability that their sum remains below $n+1$ is at least $\alpha > 0$. our proof produces a value of $\alpha = 1/13 \simeq 0.077$, but we conjecture that the inequality also holds with $\alpha = 1/e \simeq 0.368$.as an example for the use of the new inequality, we consider the problem of estimating the average degree of a graph by querying the degrees of some of its vertices. we show the following threshold behavior: approximation factors above 2 require far fewer queries than approximation factors below 2. the new inequality is used in order to get tight (up to multiplicative constant factors) relations between the number of queries and the quality of the approximation. we show how the degree approximation algorithm can be used in order to quickly find those edges in a network that belong to many shortest paths.
on maximizing welfare when utility functions are subadditive. we consider the problem of maximizing welfare when allocating $m$ items to $n$ players with subadditive utility functions. our main result is a way of rounding any fractional solution to a linear programming relaxation to this problem so as to give a feasible solution of welfare at least $1/2$ that of the value of the fractional solution. this approximation ratio of $1/2$ is an improvement over an $\omega(1/\log m)$ ratio of dobzinski, nisan, and schapira [proceedings of the 37th annual acm symposium on theory of computing (baltimore, md), acm, new york, 2005, pp. 610-618]. we also show an approximation ratio of $1-1/e$ when utility functions are fractionally subadditive. a result similar to this last result was previously obtained by dobzinski and schapira [proceedings of the 17th annual acm-siam symposium on discrete algorithms (miami, fl), siam, philadelphia, 2006, pp. 1064-1073], but via a different rounding technique that requires the use of a so-called &ldquo;xos oracle.&rdquo; the randomized rounding techniques that we use are oblivious in the sense that they only use the primal solution to the linear program relaxation, but have no access to the actual utility functions of the players.
zero knowledge proofs of identity in this paper we extend the notion of zero knowledge proofs of membership (which reveal one bit of information) to zero knowledge proofs of knowledge (which reveal no information whatsoever). after formally defining this notion, we show its relevance to identification schemes, in which parties prove their identity by demonstrating their knowledge rather than by proving the validity of assertions. we describe a novel scheme which is provably secure if factoring is difficult and whose practical implementations are about two orders of magnitude faster than rsa-based identification schemes. in the last part of the paper we consider the question of sequential versus parallel executions of zero knowledge protocols, define a new notion of &ldquo;transferable information&rdquo;, and prove that the parallel version of our identification scheme (which is not known to be zero knowledge) is secure since it reveals no transferable information.
improved approximation algorithms for minimum-weight vertex separators. we develop the algorithmic theory of vertex separators, and its relation to the embeddings of certain metric spaces. unlike in the edge case, we show that embeddings into l1 (and even euclidean embeddings) are insufficient, but that the additional structure provided by many embedding theorems does suffice for our purposes.we obtain an o(√log n) approximation for min-ratio vertex cuts in general graphs, based on a new semidefinite relaxation of the problem, and a tight analysis of the integrality gap which is shown to be θ(√log n). we also prove various approximate max-flow/min-vertex-cut theorems, which in particular give a constant-factor approximation for min-ratio vertex cuts in any excluded-minor family of graphs. previously, this was known only for planar graphs, and for general excluded-minor families the best-known ratio was o(log n).these results have a number of applications. we exhibit an o(√log n) pseudo-approximation for finding balanced vertex separators in general graphs. in fact, we achieve an approximation ratio of o(√log opt) where opt is the size of an optimal separator, improving over the previous best bound of o(log opt). likewise, we obtain improved approximation ratios for treewidth: in any graph of treewidth k, we show how to find a tree decomposition of width at most o(k √log k), whereas previous algorithms yielded o(k log k). for graphs excluding a fixed graph as a minor (which includes, e.g., bounded genus graphs), we give a constant-factor approximation for the treewidth; this can be used to obtain the first polynomial-time approximation schemes for problems like minimum feedback vertex set and minimum connected dominating set in such graphs.
two prover protocols: low error at affordable rates. we introduce the miss-match form for two-prover one-round proof systems. any two-prover one-round proof system can be easily modified so as to be in miss-match form. proof systems in miss-match form have the "projection" property that is important for deriving hardness of approximation results for np-hard combinatorial optimization problems.our main result is an upper bound on the number of parallel repetitions that suffice in order to reduce the error of miss-match proof systems from p to $\epsilon$. this upper bound depends only on p and on $\epsilon$ (polynomial in 1/(1-p) and in $1/\epsilon$). based on previous work, it follows that for any $\epsilon >0,$ np has two-prover one-round proof systems with logarithmic-sized questions, constant-sized answers, and error at most $\epsilon$.as part of our proof we prove upper bounds on the influence of random variables on multivariate functions, which may be of independent interest.
on the hardness of computing the permanent of random matrices (extended abstract) we study the complexity of computing the permanent on random inputs. we consider matrices drawn randomly from the space of n by n matrices with integer values between 0 and p&ndash;1, for any large enough prime p. we show that any polynomial time algorithm which computes the permanent correctly on even an exponentially small fraction of these matrices, implies the collapse of the polynomial-time hierarchy to its second level. we also show that it is hard to get partial information about the value of the permanent modulo p. we show that any balanced polynomial-time 0/1 predicate (e.g., the least significant bit, the parity of all the bits, the quadratic residuosity character) cannot be guessed with probability significantly greater than 1/2 (unless the polynomial hierarchy collapses). this result can be extended to showing simultaneous hardness for linear size groups of bits.
two-prover one-round proof systems: their power and their problems (extended abstract) we characterize the power of two-prover one-round (mip(2,1)) proof systems, showing that mip(2,1)=nexptime. however, the following intriguing question remains open: does parallel repetition decrease the error probability of mip(2,1) proof systems?. we use techniques based on quadratic programming to study this problem, and prove the parallel repetition conjecture in some special cases. interestingly, our work leads to a general polynomial time heuristic for any np-problem. we prove the effectiveness of this heuristic for several problems, such as computing the chromatic number of perfect graphs.