waashk/dblp huggingface dataset:
time-space tradeoff lower bounds for integer multiplication and graphs of arithmetic functions. we prove exponential size lower bounds for nondeterministic and randomized read-k bps as well as a time-space tradeoff lower bound for unrestricted, deterministic multi-way bps computing the middle bit of integer multiplication. the lower bound for randomized read-k bps is superpolynomial as long as the error probability is superpolynomially small. for polynomially small error, we have a polynomial upper bound on the size of approximating read once bps for this function. the lower bounds follow from a more general result for the graphs of universal hash classes that is applicable to the graphs of arithmetic functions such as integer multiplication, convolution, and finite field multiplication.
smoothed analysis of algorithms: why the simplex algorithm usually takes polynomial time. we introduce the smoothed analysis of algorithms, which continuously interpolates between the worst-case and average-case analyses of algorithms. in smoothed analysis, we measure the maximum over inputs of the expected performance of an algorithm under small random perturbations of that input. we measure this performance in terms of both the input size and the magnitude of the perturbations. we show that the simplex algorithm has smoothed complexity polynomial in the input size and the standard deviation of gaussian perturbations.
deterministic simulation of non-deterministic turing machines (detailed abstract) computations of non-deterministic turing machines are shown to correspond to &ldquo;solving&rdquo; certain mazes. the storage needed to &ldquo;solve&rdquo; mazes is related to the storage needed to deterministically simulate non-deterministic turing machines. in particular, it is shown that a non-deterministic l(n)-tape bounded turing machine can be simulated by an (l(n))2-tape bounded turing machine, provided l(n)&ge;log2n.
nearly-linear time algorithms for graph partitioning, graph sparsification, and solving linear systems. we present algorithms for solving symmetric, diagonally-dominant linear systems to accuracy ε in time linear in their number of non-zeros and log (κf (a) ε), where κf (a) is the condition number of the matrix defining the linear system. our algorithm applies the preconditioned chebyshev iteration with preconditioners designed using nearly-linear time algorithms for graph sparsification and graph partitioning.
maze recognizing automata (extended abstract) in [2], computations of nondeterministic machines are shown to correspond to threadings of certain mazes. we briefly summarize these results and then obtain some new extentions of them. a new device called a maze-recognizing automaton is introduced. this is a type of finite-state device that crawls through mazes. the following statements are proven equivalent. (i) there is a maze-recognizing automaton which recognizes the threadable mazes. (ii) every nondeterministic l(n) tape-bounded turing machine is equivalent to some deterministic l(n) tape-bounded turing machine, provided l(n) &ge; log2n.
complexity of decision problems based on finite two-person perfect-information games we present a number of simply-structured combinatorial games for which the problem of determining the outcome of optimal play is complete in polynomial space&mdash;a condition which gives very strong assurance that these problems are hard. in addition to proving this completeness property for some particular games, we introduce a general technique for deriving games complete in polynomial space from np-complete problems.
the complexity of satisfiability problems the problem of deciding whether a given propositional formula in conjunctive normal form is satisfiable has been widely studied. i t is known that, when restricted to formulas having only two literals per clause, this problem has an efficient (polynomial-time) solution. but the same problem on formulas having three literals per clause is np-complete, and hence probably does not have any efficient solution. in this paper, we consider an infinite class of satisfiability problems which contains these two particular problems as special cases, and show that every member of this class is either polynomial-time decidable or np-complete. the infinite collection of new np-complete problems so obtained may prove very useful in finding other new np-complete problems. the classification of the polynomial-time decidable cases yields new problems that are complete in polynomial time and in nondeterministic log space. we also consider an analogous class of problems, involving quantified formulas, which has the property that every member is either polynomial time decidable or complete in polynomial space.
graph ramsey theory and the polynomial hierarchy. in the ramsey theory of graphs f arrows (g,h) means that for every way of coloring the edges of f red and blue f will contain either a red g or a blue h. the problem arrowing of deciding whether f arrows (g,h) lies in conp^np and it was shown to be conp-hard by burr in 1990. we prove that arrowing is actually conp^np-complete, simultaneously settling a conjecture of burr and providing a rare natural example of a problem complete for a higher level of the polynomial hierarchy. we also show that strong arrowing, the version for induced subgraphs, is complete for conp^np under turing-reductions.
decidability of string graphs. we show that string graphs can be recognized in nondeterministic exponential time by giving an exponential upper bound on the number of intersections for a drawing realizing the string graph in the plane. this upper bound confirms a conjecture by kratochv\'{\i}l and matou\v{s}ek~\cite{km91} and settles the long-standing open problem of the decidability of string graph recognition (sinden~\cite{s66}, graham~\cite{g76}). finally we show how to apply the result to solve another old open problem: deciding the existence of euler diagrams, a central problem of topological inference (grigni, papadias, papadimitriou~\cite{gpp95}).
optimal rate-based scheduling on multiprocessors. the pd2 pfair/erfair scheduling algorithm is the most efficient known algorithm for optimally scheduling periodic tasks on multiprocessors. in this paper, we prove that pd2 is also optimal for scheduling "rate-based" tasks whose processing steps may be highly jittered. the rate-based task model we consider generalizes the widely-studied sporadic task model.
recognizing string graphs in np. a string graph is the intersection graph of a set of curves in the plane. each curve is represented by a vertex, and an edge between two vertices means that the corresponding curves intersect. we show that string graphs can be recognized in np. the recognition problem was not known to be decidable until very recently, when two independent papers established exponential upper bounds on the number of intersections needed to realize a string graph (mutzel (ed.), graph drawing 2001, lecture notes in computer science, springer, berlin; proceedings of the 33rd annual acm symposium on theory of computing (stoc-2001)). these results implied that the recognition problem lies in nexp. in the present paper we improve this by showing that the recognition problem for string graphs is in np, and therefore np-complete, since kratochvíl showed that the recognition problem is np-hard (j. combin theory, ser. b 52). the result has consequences for the computational complexity of problems in graph drawing, and topological inference. we also show that the string graph problem is decidable for surfaces of arbitrary genus.
a constant-factor approximation algorithm for packet routing, and balancing local vs. global criteria. we present the first constant-factor approximation algorithm for a fundamental problem: the store-and-forward packet routing problem on arbitrary networks. furthermore, the queue sizes required at the edges are bounded by an absolute constant. thus, this algorithm balances a global criterion (routing time) with a local criterion (maximum queue size) and shows how to get simultaneous good bounds for both. for this particular problem, approximating the routing time well, even without considering the queue sizes, was open. we then consider a class of such local vs. global problems in the context of covering integer programs and show how to improve the local criterion by a logarithmic factor by losing a constant factor in the global criterion.
on the power of quantum fingerprinting. in the simultaneous message model, two parties holding n-bit integers x,y send messages to a third party, the referee, enabling him to compute a boolean function f(x,y). buhrman et al [3] proved the remarkable result that, when f is the equality function, the referee can solve this problem by comparing short "quantum fingerprints" sent by the two parties, i.e., there exists a quantum protocol using only o(log n) bits. this is in contrast to the well-known classical case for which ω(n1/2) bits are provably necessary for the same problem even with randomization. in this paper we show that short quantum fingerprints can be used to solve the problem for a much larger class of functions. let r<??par line>,pub(f) denote the number of bits needed in the classical case, assuming in addition a common sequence of random bits is known to all parties (the public coin model). we prove that, if r<??par line>,pub(f)=o(1), then there exists a quantum protocol for f using only o(log n) bits. as an application we show that o(log n) quantum bits suffice for the bounded hamming distance function, defined by f(x,y)=1 if and only if x and y have a constant hamming distance d or less.
a new average case analysis for completion time scheduling. we present a new average case analysis for the problem of scheduling n jobs on m machines so that the sum of job completion times is minimized. our goal is to use the concept of competitive ratio---which is a typical worst case notion---also within an average case analysis. we show that the classic sept scheduling strategy with &omega;(n) worst-case competitive ratio achieves an average of o(1) under several natural distributions, among them the exponential distribution. our analysis technique allows to also roughly estimate the probability distribution of the competitive ratio. thus, our result bridges the gap between worst case and average case performance guarantee.
formal languages and power series section 1 of this paper presents the basic mathematical definitions for our work. section 2 defines the notion of a weighted phrase-structure grammar over either a semiring or zero monoid coefficient structure. the notion of canonical derivations (from griffiths [1968]) and top-down derivations is defined in section 3, along with some of their basic properties. equivalence relations over weighted phrase-structure grammars are defined in section 4 as well as power series representations of the associated languages. section 5 shows that every weighted type 0 grammar is equivalent to a grammar in standard form. section 6 describes the equations associated with a grammar in standard form and describes a process of iteratively obtaining approximations to the language.
how to spread adversarial nodes?: rotate! in this paper we study the problem of how to keep a dynamic system of nodes well-mixed even under adversarial behavior. this problem is very important in the context of distributed systems.more specifically, we consider the following game: there are n white pebbles and ε n black pebbles for some fixed constant ε < 1. initially, all of the white pebbles are laid down in a ring, and the adversary has all of the black pebbles in its bag. in each round, the adversary can look at the entire ring and can select to add a black pebble to the ring (if its bag is not empty) or to take any black pebble from the ring and put it back into its bag (i.e. we consider adaptive adversaries). however, the adversary cannot place a black pebble into any position it likes. this is handled by a join strategy to be specified by the system. the goal is to find an oblivious join strategy, i.e. a strategy that cannot distinguish between the white and black pebbles in the ring, that integrates the black pebbles into this ring and may do some further rearrangements so that for a polynomial number of rounds the adversary will not manage to include its black pebbles into the ring so that there is a sequence of s=θ(log n) consecutive pebbles in which at least half of the pebbles are black. if this is achieved by the join strategy, it wins. otherwise, the adversary wins.of course, the brute-force strategy of rearranging all of the pebbles in the ring at random after each insertion of a black pebble will achieve the stated goal, with high probability, but this would be a very expensive strategy. the challenge is to find a join strategy that needs as little randomness and as few rearrangements as possible in order to win with high probability. in this paper, we present and analyze a very simple strategy called k-rotation that chooses k-1 existing positions uniformly at random in the ring, creates a new position uniformly at random in the ring, and then rotates the new pebble and the k-1 old pebbles along these positions. interestingly, even if the adversary has just $s$ pebbles, it can still win for k=2. but the k-rotation rule wins with high probability for k=3 as long as ε<2/3, demonstrating that there is a sharp threshold for keeping pebbles in a sufficiently perturbed state.
from static to dynamic routing: efficient transformations of store-and-forward protocols. we investigate how static store-and-forward routing algorithms can be transformed into efficient dynamic algorithms, that is, how algorithms that have been designed for the case that all packets are injected at the same time can be adapted to more realistic scenarios in which packets are continuously injected into the network. besides describing specific transformations for well-known static routing algorithms, we present a black box transformation scheme applicable to every static, oblivious routing algorithm. we analyze the performance of our protocols under a stochastic and an adversarial model of packet injections.one result of our specific transformations is the first dynamic routing algorithm for leveled networks that is stable for arbitrary admissible injection rates and that works with packet buffers of size depending solely on the injection rate and the node degree, but not on the size of the network. furthermore, we prove strong delay bounds for the packets. our results imply, for example, that a throughput of 99% can be achieved on an n-input butterfly network with buffers of constant size while each packet is delivered in time o(log n), with high probability.our black box transformation ensures that if the static algorithm is pure (i.e., no extra packets apart from the original packets are routed), its dynamic variant is stable up to a maximum possible injection rate. furthermore, in the stochastic model, the routing time of a packet depends on local parameters such as the length of its routing path, rather than on the maximum possible path length, even if the static algorithm chosen for the transformation does not provide this locality feature and is not pure. in the adversarial model, the delay bound of the packets is closely related to the time bound given for the static algorithm.
word problems requiring exponential time: preliminary report the equivalence problem for kleene's regular expressions has several effective solutions, all of which are computationally inefficient. in [1], we showed that this inefficiency is an inherent property of the problem by showing that the problem of membership in any arbitrary context-sensitive language was easily reducible to the equivalence problem for regular expressions. we also showed that with a squaring abbreviation ( writing (e)2 for e&times;e) the equivalence problem for expressions required computing space exponential in the size of the expressions. in this paper we consider a number of similar decidable word problems from automata theory and logic whose inherent computational complexity can be precisely characterized in terms of time or space requirements on deterministic or nondeterministic turing machines. the definitions of the word problems and a table summarizing their complexity appears in the next section. more detailed comments and an outline of some of the proofs follows in the remaining sections. complete proofs will appear in the forthcoming papers [9, 10, 13]. in the final section we describe some open problems.
the node cost measure for embedding graphs on the planar grid (extended abstract) the two major cost measures used in the past for grid embeddings are area (or the area of the smallest square or rectangle that contains the embedding) and total edge length. this paper is primarily concerned with a third measure, total number of nodes. to embed a graph on the planar grid, it may be necessary to &ldquo;bend&rdquo; edges. this can be modeled by allowing the insertion of nodes along edges of the graph and then insisting that the embedding may not bend edges.
the macro model for data compression (extended abstract) a general model for data compression is presented which includes most data compression systems in the literature as special cases. all macro schemes are based on the principle of finding redundant strings or patterns and replacing them by pointers to a common copy. different varieties of macro schemes may be defined by varying the interpretation of pointers, for instance, a pointer may indicate a substring of the compressed string, a substring of the original string, or a substring of some other string such as an external dictionary. other varieties of macros schemes may be defined by restricting the type of overlapping or recursion that may be used. trade-offs between different varieties of macro schemes, exact lower bounds on the amount of compression obtainable, and the complexity of encoding and decoding are discussed as well as how the work of other authors (such as lempel-ziv) relates to this model.
polynomial time quantum algorithm for the computation of the unit group of a number field. we present a quantum algorithm for the computation of the irrational period lattice of a function on zn which is periodic in a relaxed sense. this algorithm is applied to compute the unit group of finite extensions of q. execution time for fixed field degree over q is polynomial in the discriminant of the field. our algorithms generalize and improve upon hallgren's work [9] for the one-dimensional case corresponding to real-quadratic fields.
topological matching there is a lot of practical and theoretical interest in designing algorithms to process digital pictures. of particular interest are problems arising when one starts with an nxn array of pixels and stores it, one pixel per processor, in some sort of array-like parallel computer. in this paper we give an optimal &thgr;(n) time solution, based on a simpler &thgr;(n) time solution for a more powerful computer called a mesh computer. beyer suggested that this problem was a prime candidate for a non-linear recognition problem, but our result shows that this is not true.
the process complexity and effective random tests we propose a variant of the kolmogorov concept of complexity which yields a common theory of finite and infinite random sequences. the process complexity does not oscillate. we establish some concepts of effective tests which are proved to be equivalent.
propositional dynamic logic of looping and converse propositional dynamic logic can be extended to include both an infinitary iteration construct delta and a backtracking construct converse. the resulting logic does not satisfy the finite model property, but is nevertheless elementarily decidable. in order to establish this decidability result, deterministic two-way automata on infinite trees are defined and shown to be reducible to nondeterministic one-way automata on infinite trees. the decision procedure suggests a nonstandard semantics for the extended logic for which the finite model property does hold.
translating recursion equations into flow charts this paper proposes the foundations for a systematic study of the translation of recursive function definitions into flow charts (often called the removal of recursions). several notions of translation are presented. emphasis is placed on translation which could be performed mechanically, operating only on the syntactical structure of the recursion equations. systems of recursion equations are classified by structure and by the dynamics of their implicit computations. theorems on the limitations of translation are based on these classifications. an effective first approximation to a syntactic characterization of one notion of translatability is presented. finally, open problems are discussed. space limitations prevent the inclusion of proofs or lengthy definitions.
vector execution of flow graphs (extended abstract) given a vector of tasks intended to execute the same program simultaneously on a machine which can execute only one instruction at a time, but can execute that instruction for any specified subset of the vector, the object is to schedule the execution to take maximal advantage of parallelism. such a scheduling is called a vector execution scheme. a class of &ldquo;perfect&rdquo; programs is characterized for which such scheduling is easy and on which many vector execution schemes are optimal. this characterization shows that scheduling difficulties arise from unrestricted use of gotos producing irreducible programs, from branches in loops, and from nested loops. once the path through the program is known for each task, it is a finite problem to find an optimal schedule; so there is an optimal vector execution scheme, even over imperfect programs. however, there is no implementable vector execution scheme which does not make use of knowledge of the future and which is optimal with respect to length of execution sequences. some implementable vector execution schemes based on priority ordering and node sequence approaches are studied and compared as to worst case behavior on imperfect programs.
sample spaces uniform on neighborhoods let a universe of m elements be given, along with a family of subsets of the universe (neighborhoods), each of size at most k. we describe methods for assigning the m elements to points in a small-dimensional vector space (over gf(2)), in such a way that the elements in each neighborhood are assigned to an independent set of vectors. such constructions lead, through a standard correspondence between linear and statistical independence, to the construction of small sample spaces which restrict to the uniform distribution in each neighborhood. (the sample space is a uniformly-weighted family of binary m-vectors). the size of such a small space will be a function of the number of neighborhoods; and for sparse families, will be substantially smaller than any space which restricts to the uniform distribution in all k-sets. previous work on small spaces with limited independence focused on providing independence or near-independence in every k-set of the universe. we show how to construct the sample spaces efficiently both sequentially and in parallel. in case there are polynomially many (in m) neighborhoods, each of size o(log m), the parallel construction is in nc. these spaces provide a new derandomization technique for algorithms; particularly, algorithms related to the lova&acute;sz local lemma. we also describe applications to the exhaustive testing of vlsi circuits, and to coding for burst errors on noisy channels.