waashk/dblp huggingface dataset:
on deterministic context-free languages, multihead automata, and the power of an auxiliary pushdown store a deterministic context-free language l0 is described which is log(n)-complete for the family of languages recognized by deterministic log(n)- tape bounded auxiliary pushdown automata in polynomial time. it follows that l0 is a &ldquo;hardest&rdquo; deterministic context-free language (dcfl), since all dcfl's are recognized in polynomial time by deterministic pushdown automata. l0 is, moreover, a simple precedence language and a simple ll(1) language. thus the tape complexities of these proper subfamilies are essentially the same as the tape complexity of all dcfl's. we show that an auxiliary pushdown store does, in fact, add some power to some restricted families of log(n)-tape bounded turing machines. the basic result is that every two-way 2k-head nondeterministic finite automation can be replaced by an equivalent two-way k-head nondeterministic pushdown automation. this indicates, also, that every 2k-head nondeterministic finite automation language can be recognized in 0(n3k) steps. other results relate multihead automata classes with other multihead automata classes, with families recognized by log(n)-tape bounded turing machines with restricted tape alphabets, and with time-bounded complexity classes.
separating tape bounded auxiliary pushdown automata classes previous results in the literature which describe separation theorems for time bounded complexity classes serve also to separate classes defined by tape bounded auxiliary pushdown automata. results described here refine these basic relationships between classes defined by tape bounded auxpda. it is shown that, for auxiliary pda fully constructable functions s0 and s1 satisfying s1 (n+1) &egr; o,(s0 (n)), s0 tape bounded auxpda are more powerful than s1 tape bounded auxpda. further results refine the resulting separation by the number of worktape symbols and the number of worktape heads. results are also described for separating classes defined by tape bounded auxpda with one pushdown store symbol, i.e. auxiliary counter automata (auxca). refinements of the known equivalence of nondeterministic l(n)-tape bounded auxpda and deterministic l(n)-tape bounded auxpda are also described. one corollary is that every two-way nondeterministic pda can be simulated by a two-way deterministic pda with four input tape heads and that every context-free language can be recognized by a deterministic two-way pda with three heads. another corollary of these results shows that there are languages over a single letter alphabet which are recognized by (k+1)-head two-way pda but cannot be recognized by any k-head two-way pda. it is shown also that auxpda and auxca can fully construct very slow growing functions so that even small amounts of worktape space (e.g. that bounded by log*n) increase their computational power.
unique binary search tree representations and equality-testing of sets and sequences this paper studies the problem of representing sets over an ordered universe by unique binary search trees, so that dictionary operations can be performed efficiently on any set. although efficient randomized solutions to the problem are known, its deterministic complexity has been open. the paper exhibits representations that permit the execution of dictionary operations in optimal deterministic time when the dictionary is sufficiently sparse or sufficiently dense. the results demonstrate an exponential separation between the deterministic and randomized complexities of the problem. unique representations are applied to obtain efficient data structures for maintaining a dynamic collection of sets/sequences under queries that test the equality of a pair of objects. the data structure for set equality testing tests equality of sets in constant time and processes set updates in $o(\log m)$ amortized time and $o(\log m)$ space, where $m$ denotes the total number of updates performed. it is based on an efficient implementation of cascades of c{\vipt ons} operations on uniquely stored s-expressions. the data structure for sequence equality testing tests equality of sequences in constant time and processes updates in $o(\sqrt{n \log m}\, + \log m)$ amortized time and $o(\sqrt{n})$ amortized space where $n$ denotes the length of the sequence that is updated and $m$ denotes the total number of updates performed.
heuristics for weighted perfect matching the problem of finding near optimal perfect matchings of an even number n of vertices is considered. when the distances between the vertices satisfy the triangle inequality it is possible to get within a constant multiplicative factor of the optimal matching in time o(n2 log k) where k is the ratio of the longest to the shortest distance between vertices. other heuristics are analyzed as well, including one that gets within a logarithmic factor of the optimal matching in time o(n2 log n). finding an optimal weighted matching requires &thgr;(n3) time by the fastest known algorithm, so these heuristics are quite useful. when the n vertices lie in the unit (euclidean) square, no heuristic can be guaranteed to produce a matching of cost less than [equation] in the worst case. we analyze various heuristics for this case, including one that always produces a matching costing at most [equation]. in addition, this heuristic also finds a traveling salesman tour of the n vertices costing at most [equation]. a different one of the heuristics analyzed produces asymptotically optimal results. it is also shown that asymptotically optimal traveling salesman tours can be found in o(n log n) time in the unit square.
computability theory in admissible domains denotational semantics was introduced by strachey as a means of defining semantics of programming languages. it's mathematical foundation was justified by scott [14] in 1969 when he introduced continuous lattices to model data types and showed how to solve reflexive domain equations. it is not the case that any solution of a given reflexive domain equation is a suitable model for studying denotational semantics. in programming languages, the constructs that we deal with can all be realizable by some machines, hence their meanings, considered as mathematical objects in a lattice, should be computable. in other words, we need a solution where we can formalize the notion of computability. of course, this means that many continuous lattices are irrelevant to the study of denotational semantics of programming languages. it is the purpose of this paper to isolate those lattices which are relevant.
multicommodity flows in planar undirected graphs and shortest paths this paper deals with the multicommodity flow problems for two classes of planar undirected graphs. the first class c12 consists of graphs in which each source-sink pair is located on one of two specified face boundaries. the second class c01 consists of graphs in which some of the source-sink pairs are located on a specified face boundary and all the other pairs share a common sink located on the boundary. we show that the multicommodity flow problem for a graph in c12 (resp. c01) can be reduced to the shortest path problem for an undirected (resp. a directed) graph obtained from the dual of the original undirected graph.
the complexity of finding periods given a function f over a finite domain d and an arbitrary starting point x, the sequence x,f(x),f(f(x)),... is ultimately periodic. such sequences typically are used for constructing random number generators. the cycle problem is to determine the first repeated element fn(x) in the sequence. previous algorithms for this problem have required 3n operations. in this paper we present an algorithm which only requires n(1+o(1/(@@@@)m)) steps, if m memory cells are available to store values of the function. by increasing m, this running time can be made arbitrarily close to the information-theoretic lower bound on the running time of any algorithm for the cycle problem. our treatment is novel in that we explicitly consider the performance of the algorithm as a function of the amount of memory available as well as the relative cost of evaluating f and comparing sequence elements for equality.
the computation of finite functions this paper discusses the computation of finite functions with the aim of investigating ways of judging the relative worth of the different methods for computing a given finite function. any finite function may, of course, be computed in a number of ways, including a &ldquo;brute-force&rdquo; method of table look-up and methods which exploit some pattern which may exist in the function. how &ldquo;good&rdquo; we judge each of the several methods to be will depend on which criteria we wish to apply, and here we will be considering two: size of program and cost of computation, first of all separately, and then together. the latter case gives rise to the notion of a &ldquo;reasonable&rdquo; way of computing a finite function, and certain considerations with respect to this notion suggest a modified notion of &ldquo;relatively reasonable&rdquo;. some properties of these concepts, in particular some of the differences between them, are developed. the spirit of the paper is machine-independent except for the last paragraph which suggests a need for some idea of &ldquo;program structure&rdquo; to be introduced into the formulation.
the dlt priority sampling is essentially optimal. the priority sampling procedure of n. duffield, c. lund and m. thorup is not only an exciting new approach to sampling weighted data streams, but it has also proven to be highly successful in a variety of practical applications. we resolve the two major issues related to its performance. first we solve the main conjecture of n. alon, n. duffield, c. lund and m. thorup in [1], which states that the standard deviation for the subset sum estimator obtained from k priority samples is upper bounded by w/√k-1, where w denotes the actual subset sum that the estimator estimates. although alon et al. give an o(w/√k-1) upper bound on the standard deviation of the estimator, their formula cannot be used as a performance guarantee in an applied setting, because the constants coming up in their proof are very large. our constant cannot be improved. we also resolve the conjecture of duffield, c. lund and m. thorup which states that the variance of the priority sampling procedure is not larger than the variance of the threshold sampling procedure with sample size only one smaller. this is the main conjecture in [7]. the conjecture's significance is that the latter procedure is provably optimal within a very general class of sampling algorithms, but unlike priority sampling, it is not practical. our result therefore certifies that priority sampling offers the unlikely feat of uniting mathematical elegance, (essential) optimality and applicability. our proof is based on a new integral formula and on very finely tuned telescopic sums.
observations on nondeterministic multidimensional iterative arrays let nia(d) be the family of languages accepted within linear time by nondeterministic d-dimensional iterative arrays. (on-line deterministic multidimensional iterative arrays have been studied by cole [2].) it has been observed [8] that every language accepted by a one-dimensional single-head turing machine simultaneously within time n2 and space n is in nia(2). our main result (theorem 2) generalizes this observation to ntime(nd) @@@@ nia(d), where ntime(t(n)) is the family of languages accepted within time t(n) by nondeterministic one-dimensional multihead turing machines. conversely, we show that nia(d) @@@@ ntime(nd+l) (theorem 3). the two facts together show [equation]nia(d) = [equation]ntime(nd), which is the same as karp's class np [6]. we also use both facts in a proof that nia(d) @@@@ nia(d+2). let ntm(d) be the family of languages accepted within linear time by nondeterministic d-dimensional multihead turing machines. a real-time simulation of turing machines by iterative arrays gives ntm(d) @@@@ nia(d) (theorem 1), but a less direct simulation (using theorem 2) gives the stronger result [equation] ntm(d) @@@@ nia(2). thus, in the nondeterministic case, two-dimensional iterative arrays outperform all multi-dimensional multihead turing machines. finally, in section 7, we examine related deterministic questions and summarize.
validating register allocations for straight line programs straight line programs are essentially sequences of assignment statements. a general program consists of straight line segments with flow of control between these segments. the interfaces between a straight line segment and the rest of the program place constraints on register allocations for the segment. these constraints may render a register allocation for a straight line program unrealizable. an algorithm is given to determine if a register allocation for a straight line program is realizable. it is shown that the algorithm takes 0(n3) steps, where n is the number of statements in the program. an unrealizable assignment may be made realizable by introducing stores into memory at appropriate points. it is shown how the minimum number of such stores may be found.
loss-less condensers, unbalanced expanders, and extractors. an extractor is a procedure which extracts randomness from a detective random source using a few additional random bits. explicit extractor constructions have numerous applications and obtaining such constructions is an important derandomization goal. trevisan recently introduced an elegant extractor construction, but the number of truly random bits required is suboptimal when the input source has low-min-entropy. significant progress toward overcoming this bottleneck has been made, but so far has required complicated recursive techniques that lose the simplicity of trevisan's construction. we give a clean method for overcoming this bottleneck by constructing {\em loss-less condensers}. which compress the n-bit input source without losing any min-entropy, using o(\log n) additional random bits. our condensers are built using a simple modification of trevisan's construction, and yield the best extractor constructions to date. loss-less condensers also produce unbalanced bipartite expander graphs with small (polylogarithmic) degree d and very strong expansion of (1-\epilon)d. we give other applications of our construction, including dispersers with entropy loss o(\log n), depth two super-concentrators whose size is within a polylog of optimal, and an improved hardness of approximation result.
complete register allocation problems the search for efficient algorithms for register allocation dates back to the time of the first fortran compiler for the ibm 704. since then, many variants of the problem have been considered; depending on two factors: (1) the particular model for registers, and (2) the definition of the term &ldquo;computation of a program&rdquo; e.g. whether values may be computed more than once. we will show that several variants of the register allocation problem for straight line programs are polynomial complete. in particular we consider, (1) the case when each value is computed exactly once, and (2) the case when values may be recomputed as necessary. the completeness of the third problem considered is surprising. a straight line program starts with a set of initial values, and computes intermediate and final values. suppose, for each value, the register that value must be computed into is preassigned. then, (3) the problem of determining if there is a computation of the straight line program, that computes values into the assigned registers, is polynomial complete.
extractor codes. we define new error correcting codes based on extractors. we show that for certain choices of parameters these codes have better list decoding properties than are known for other codes, and are provably better than reed-solomon codes. we further show that codes with strong list decoding properties are equivalent to slice extractors, a variant of extractors. we give an application of extractor codes to extracting many hardcore bits from a one-way function, using few auxiliary random bits. finally, we show that explicit slice extractors for certain other parameters would yield optimal bipartite ramsey graphs.
on the cryptocomplexity of knapsack systems a recent trend in cryptographic systems is to base their encryption/decryption functions on np-complete problems, and in particular on the knapsack problem. to analyze the security of these systems, we need a complexity theory which is less worst-case oriented and which takes into account the extra conditions imposed on the problems to make them cryptographically useful. in this paper we consider the two classes of one-to-one and onto knapsack systems, analyze the complexity of recognizing them and of solving their instances, introduce a new complexity measure (median complexity), and show that this complexity is inversely proportional to the density of the knapsack system. the tradeoff result is based on a fast probabilistic knapsack solving algorithm which is applicable only to one-to-one systems, and it indicates that knapsack-based cryptographic systems in which one can both encrypt and sign messages are relatively insecure. we end the paper with new results about the security of some specific knapsack systems.
bypassing the embedding: algorithms for low dimensional metrics. the doubling dimension of a metric is the smallest k such that any ball of radius 2r can be covered using 2k balls of radius r. this concept for abstract metrics has been proposed as a natural analog to the dimension of a euclidean space. if we could embed metrics with low doubling dimension into low dimensional euclidean spaces, they would inherit several algorithmic and structural properties of the euclidean spaces. unfortunately however, such a restriction on dimension does not suffice to guarantee embeddibility in a normed space.in this paper we explore the option of bypassing the embedding. in particular we show the following for low dimensional metrics: quasi-polynomial time (1+ε)-approximation algorithm for various optimization problems such as tsp, k-median and facility location. (1+ε)-approximate distance labeling scheme with optimal label length. (1+ε)-stretch polylogarithmic storage routing scheme.
geometric complexity the complexity of a number of fundamental problems in computational geometry is examined and a number of new fast algorithms are presented and analyzed. general methods for obtaining results in geometric complexity are given and upper and lower bounds are obtained for problems involving sets of points, lines, and polygons in the plane. an effort is made to recast classical theorems into a useful computational form and analogies are developed between constructibility questions in euclidean geometry and computability questions in modern computational complexity.
on random pm 1 matrices: singularity and determinant. we proved several results concerning the determinant of a random pm 1 matrix. in particular, we show that with high probability, the determinant has absolute value very close to √n!.
a combinatorial characterization of the testable graph properties: it's all about regularity. a common thread in all of the recent results concerning the testing of dense graphs is the use of szemer&eacute;di's regularity lemma. in this paper we show that in some sense this is not a coincidence. our first result is that the property defined by having any given szemer&eacute;di-partition is testable with a constant number of queries. our second and main result is a purely combinatorial characterization of the graph properties that are testable with a constant number of queries. this characterization (roughly) says that a graph property ${\cal p}$ can be tested with a constant number of queries if and only if testing ${\cal p}$ can be reduced to testing the property of satisfying one of finitely many szemer&eacute;di-partitions. this means that in some sense, testing for szemer&eacute;di-partitions is as hard as testing any testable graph property. we thus resolve one of the main open problems in the area of property-testing, which was first raised by goldreich, goldwasser, and ron [j. acm, 45 (1998), pp. 653-750] in the paper that initiated the study of graph property-testing. this characterization also gives an intuitive explanation as to what makes a graph property testable.
optimal probabilistic fingerprint codes. we construct binary codes for fingerprinting digital documents. our codes for n users that are &epsi;-secure against c pirates have length o(c2log(n/&epsi;)). this improves the codes proposed by boneh and shaw &lsqb;1998&rsqb; whose length is approximately the square of this length. the improvement carries over to works using the boneh--shaw code as a primitive, for example, to the dynamic traitor tracing scheme of tassa &lsqb;2005&rsqb;. by proving matching lower bounds we establish that the length of our codes is best within a constant factor for reasonable error probabilities. this lower bound generalizes the bound found independently by peikert et al. &lsqb;2003&rsqb; that applies to a limited class of codes. our results also imply that randomized fingerprint codes over a binary alphabet are as powerful as over an arbitrary alphabet and the equal strength of two distinct models for fingerprinting.
on shortest paths in polyhedral spaces we consider the problem of computing the shortest path between two points in two- or three-dimensional space bounded by polyhedral surfaces. in the 2-d case the problem is easily solved in time o(n2 log n).in the general 3-d case the problem is quite hard to solve, and is not even discrete; we present a doubly-exponential procedure for solving the discrete subproblem of determining the sequence of boundary edges through which the shortest path passes. the main result of this paper involves a favorable special case of the 3-d shortest path problem, namely that of finding the shortest path between two points along the surface of a convex polyhedron. we analyze this problem and solve it in time o(n3 log n).
testing flow graph reducibility many problems in program optimization have been solved by applying a technique called interval analysis to the flow graph of the program. a flow graph which is susceptible to this type of analysis is called reducible. this paper describes an algorithm for testing whether a flow graph is reducible. the algorithm uses depth-first search to reveal the structure of the flow graph and a good method for computing disjoint set unions to determine reducibility from the search information. when the algorithm is implemented on a random access computer, it requires o(e log* e) time to analyze a graph with e edges, where log* x &equil; min{i/logix&le;1}. the time bound compares favorably with the o(e log e) bound of a previously known algorithm.
threshold spectra for random graphs let g = g(n, p) be the random graph with n vertices and edge probability p and &fnof;(n, p, a) be the probability that g has a, where a is a first order property of graphs. the evolution of the random graph is discussed in terms of a spectrum of p = p(n) where &fnof;(n, p, a) changes. a partial characterization of possible spectra is given. when p = n-a, a irrational, and a is any first order statement, it is shown that lim &fnof;(n, p, a) = 0 or 1.
testing graph connectivity an algorithm proposed by dinic for finding maximum flows in networks and by hopcroft and karp for finding maximum bipartite matchings is applied to graph connectivity problems. it is shown that the algorithm requires 0(v1/2e) time to find a maximum set of node-disjoint paths in a graph, and 0(v2/3e) time to find a maximum set of edge disjoint paths. these bounds are tight. thus the node connectivity of a graph may be tested in 0(v5/2e) time, and the edge connectivity of a graph may be tested in 0(v5/3e) time.