waashk/dblp huggingface dataset:
faster suffix tree construction with missing suffix links. we consider suffix tree construction for situations with missing suffix links. two examples of such situations are suffix trees for parameterized strings and suffix trees for two-dimensional arrays. these trees also have the property that the node degrees may be large. we add a new back-propagation component to mccreight's algorithm and also give a high probability hashing scheme for large degrees. we show that these two features enable construction of suffix trees for general situations with missing suffix links in o(n) time, with high probability. this gives the first randomized linear time algorithm for constructing suffix trees for parameterized strings.
verifying candidate matches in sparse and wildcard matching. (math) this paper obtains the following results on pattern matching problems in which the text has length n and the pattern has length man o(nlog m) time deterministic algorithm for the string matching with wildcards problems, even when the alphabet is large.an o(klog2 m) time las vegas algorithm for the sparse string matching with wildcards problem, where k&laquo;n is the number of non-zeros in the text. we also give las vegas algorithms for the higher dimensional version of this problem.as an application of the above, an o(nlog2 m) time las vegas algorithm for the subset matching and tree pattern matching problems, and a las vegas algorithm for the geometric pattern matching problem.finally, an o(nlog2 m) time deterministic algorithm for subset matching and tree pattern matching..the crucial new idea underlying the first three results above is that of confirming matches by convolving vectors obtained by coding characters in the alphabet with non-boolean (i.e., rational or even complex) entries; in contrast, almost all previous pattern matching algorithms consider only boolean codes for the alphabet. the crucial new idea underlying the fourth result is a simpler method of shifting characters which ensures that each character occurs as a singleton in some shift.
a fast algorithm for computing steiner edge connectivity. given an undirected graph or an eulerian directed graph g and a subset s of its vertices, we show how to determine the edge connectivity c of the vertices in s in time o(c3 n log n+m). this algorithm is based on an efficient construction of tree packings which generalizes edmonds' theorem. these packings also yield a characterization of all minimal steiner cuts of size c from which an efficient data structure for maintaining edge connectivity between vertices in s under edge insertion can be obtained. this data structure enables the efficient construction of a cactus tree for representing significant c-cuts among these vertices, called c-separations, in the same time bound. in turn, we use the cactus tree to give a fast implementation of an approximation algorithm for the survivable network design problem due to williamson, goemans, mihail and vazirani.
on k-hulls and related problems for any set x of points (in any dimension) and any k &equil; 1,2, ..., we introduce the concept of the k-hull of x. this unifies the well-known notion of 'convex hulls' with the notion of 'centers' recently introduced by f.f. yao. the concept is intimately related to some other concepts (k-belts, k-sets) studied by edelsbrunner, welzl, lov&aacute;sz, erd&ouml;s and others. several computational problems related to k-hulls are studied here. some of our algorithms are of interest in themselves because of the techniques employed; in particular, the 'parametric' searching technique of megiddo is used in a nontrivial way. we will also extend megiddo's technique to las vegas algorithms. our results have applications to a variety of problems in computational geometry: efficient computation of the 'cut' guaranteed by the classical 'ham sandwich theorem', faster preprocessing time for polygon retrieval, and theoretical improvements to a problem of intersecting lines and points posed by hopcroft.
on the size of programs in subrecursive formalisms this paper gives an overview of subrecursive hierarchy theory as it relates to computational complexity and applies some of the concepts to questions about the size of programs in subrecursive programming languages. the purpose is three-fold, to reveal in simple terms the workings of subrecursive hierarchies, to indicate new results in the area, and to point out ways that the fundamental ideas in hierarchy theory can lead to interesting questions about programming languages. a specific application yields new information about blum's results on the size of programs and about the relationship between size and efficiency.
loop schemata we define a class of program schemata arising from the subrecursive programming language loop. in this preliminary report on loop schemata we show how to assign functional expressions to these schemata (as one aspect of the problem of assigning meaning to these programs), and we outline a solution to the schemata equivalence problem. schemata equivalence is reduced to questions about formal expressions. certain subcases of the problem are easily shown solvable, and although we claim that the general problem is solvable, we do not present the complete solution here because of its complexity.
type two computational complexity a programming language for the partial computable functionals is used as the basis for a definition of the computational complexity of functionals (type2 functions). an axiomatic account in the spirit of blum is then provided. the novel features of this approach are justified by applying it to problems in abstract complexity, specifically operator speed-up, and by using it to define the illusive notion of the polynomial degree of an arbitrary function. new results are obtained for these degrees.
on the theory of programming logics a new logic for reasoning about programs is proposed here, and its metamathematics is investigated. no new primitive notions are needed for the logic beyond those used in elementary programming and mathematics, yet the combination of these notions is remarkably powerful. the logic includes a programming language, designed with michael o'donnell, for program verification. it forms the core of the pl/cv verifier at cornell. this study belongs to the discipline of algorithmic logic as conceived by engeler. the logic is related to park's mu-calculus based on functions instead of relations. the monadic quantifier free subset is developed in the style of the system in j.w. debakker's recursive procedures. but this logic is substantially different from either of these. it is intended to be a practical programming logic in the spirit of e. dijkstra's calculus. this paper proves the completeness and decidability of the monadic (iterative) programming logic. it discusses the polyadic logic and the programming language briefly, and considers general models for the iterative programming logic. the polyadic logic is shown to be incomplete with respect to standard models, but complete with respect to general models.
complexity of formal translations and speed-up results the purpose of this paper is to give a model for the study of quantitative problems about formal translations from one programming language into another, as well as derive some initial results about the speed of programs produced by translations. the paper also contains a new speed-up result which shows that in any computational complexity measure there exist functions which have arbitrarily large speed-ups but that the size of the speed-up programs must grow non-computably fast.
subrecursive program schemata i & ii: i. undecidable equivalence problems; ii. decidable equivalence problems the study of program schemata and the study of subrecursive programming languages are both concerned with limiting program structure in order to permit a more complete analysis of algorithms while retaining sufficiently rich computing power to allow interesting algorithms. in this paper we combine these approaches by defining classes of subrecursive program schemata and investigating their equivalence problems. since the languages are all subrecursive, any scheme written in any one of them must halt (as long as we assume the basic functions and predicates are all total). hence equivalence of schemes is the first question of interest we can ask about these languages. we consider schematic versions of various subrecursive programming languages similar to the loop language. we distinguish between pre-loop and post-loop languages on the basis of whether the exit condition in an iteration loop is tested before iteration, as in algol (pre-), or after iteration, as in fortran (post-). we show that at the program level all these languages have the same computing power (the primitive recursive functions) and all have unsolvable equivalence problems (of arithmetic degree &pgr;01). but at the level of schemes, pre-loop has an unsolvable equivalence problem, while at least one formulation of post-loop has a solvable equivalence problem.
variations on pushdown machines (detailed abstract) a class of machines called auxiliary pushdown machines is introduced. several types of pushdown automata, including stack automata, are characterized in terms of these machines. the computing power of each class of machines in question is characterized in terms of time bounded turing machines, and corollaries are derived which answer some open questions in the field.
path systems and language recognition our main result, theorem 2, gives a bound on the storage required for a turing machine to simulate certain time-bounded pushdown machines. the theorem is a generalization of the result appearing in [3] stating that any context-free language can be recognized by a deterministic turing machine within storage (log n)2. we introduce a combinatorial object, called a path system, develop its theory briefly, and use the theory to prove both the result on pushdown machines and the result on context free languages, as well as a third result. the third result is the theorem of savitch [5] stating that a non-deterministic l(n) - storage bounded turing machine can be simulated by a deterministic (l(n))2 - storage bounded turing machine.
the complexity of theorem-proving procedures it is shown that any recognition problem solved by a polynomial time-bounded nondeterministic turing machine can be &ldquo;reduced&rdquo; to the problem of determining whether a given propositional formula is a tautology. here &ldquo;reduced&rdquo; means, roughly speaking, that the first problem can be solved deterministically in polynomial time provided an oracle is available for solving the second. from this notion of reducible, polynomial degrees of difficulty are defined, and it is shown that the problem of determining tautologyhood has the same polynomial degree as the problem of determining whether the first of two given graphs is isomorphic to a subgraph of the second. other examples are discussed. a method of measuring the complexity of proof procedures for the predicate calculus is introduced and discussed.
a hierarchy for nondeterministic time complexity the purpose of this paper is to prove the following result: theorem 1 for any real numbers r1, r2, 1 &le; r1 < r2, there is a set a of strings which has nondeterministic time complexity nr2 but not nondeterministic time complexity nr1 the computing devices are non-deterministic multitape turing machines.
an observation on time-storage trade off recently there have been several attempts to prove that every set of strings in @@@@ (i.e., recognizable in deterministic polynomial time) can be recognized in deterministic storage (log n)2. the methods used in the attempts were based on that of [1], in which it is shown that every context free language can be accepted in storage (log n)2 our thesis in the present paper is that these attempts must fail. we define a specific set sp of strings which is clearly in @@@@, but in a certain well-defined sense cannot be recognized in storage (log n)2 using the techniques in [1]. we conjecture that no turing machine recognizes sp within storage (log n)2, and show that if this conjecture is false, then in fact every member of @@@@ can be recognized within storage (log n)2.
feasibly constructive proofs and the propositional calculus (preliminary version) the motivation for this work comes from two general sources. the first source is the basic open question in complexity theory of whether p equals np (see [1] and [2]). our approach is to try to show they are not equal, by trying to show that the set of tautologies is not in np (of course its complement is in np). this is equivalent to showing that no proof system (in the general sense defined in [3]) for the tautologies is &ldquo;super&rdquo; in the sense that there is a short proof for every tautology. extended resolution is an example of a powerful proof system for tautologies that can simulate most standard proof systems (see [3]). the main theorem (5.5) in this paper describes the power of extended resolution in a way that may provide a handle for showing it is not super. the second motivation comes from constructive mathematics. a constructive proof of, say, a statement @@@@&times;a must provide an effective means of finding a proof of a for each value of x, but nothing is said about how long this proof is as a function of x. if the function is exponential or super exponential, then for short values of x the length of the proof of the instance of a may exceed the number of electrons in the universe. in section 2, i introduce the system pv for number theory, and it is this system which i suggest properly formalizes the notion of a feasibly constructive proof.
deterministic cfl's are accepted simultaneously in polynomial time and log squared space we propose to prove the theorem in the title. let ploss be the class of sets recognizable on a deterministic turing machine simultaneously in polynomial time and log squared space. using the notation of bruss and meyer [1], ploss &equil; &ugr;k tisp(nk,k log2n).
bounds on the time for parallel ram's to compute simple functions we prove that a parallel ram with no write conflicts allowed requires -&-ohgr;(log n) steps to compute the boolean or of n bits stored in the first n global memory cells. we first argue that this result is subtler than it appears, and in fact the -&-ldquo;obvious-&-rdquo; lower bound of log2n steps can be beaten.
time-bounded random access machines in this paper we introduce a formal model for random access computers and argue that the model is a good one to use in the theory of computational complexity. results are proved which compare run times for recognizing sets using this model (which has a fixed program) with a stored program model and with turing machines. the main result, theorem 3, shows the existence of a time complexity hierarchy which is finer than that of any standard abstract computer model. an algol-like programming language is introduced which facilitates proofs of the theorems.
on the lengths of proofs in the propositional calculus (preliminary version) one of the most important open questions in the field of computational complexity is the question of whether there is a polynomial time decision procedure for the classical propositional calculus. the purpose of the present paper is to study a question related to the complexity of decision procedures for the propositional calculus; namely, the complexity of proof systems for the propositional calculus. the fundamental issue here is whether there exists any proof system, and a polynomial p(n) such that every valid formula has a proof of length not exceeding p(n), where n is the length of the formula. theorem 1 below helps establish the importance of this question. for the purposes of this theorem, we give the following definitions.
storage requirements for deterministic polynomial time recognizable languages a striking example of practical tradeoffs between storage space and execution time is provided by the ibm 1401 fortran compiler. on another level, there is an interesting relation between the time and storage required to recognize context free languages. the recognition algorithm in [y] requires time no more than 0(n3), but requires at least linear storage, whereas the algorithm in [li requires recognition space no more than 0((log n)2) and requires more than polynomial time. an intriguing question is whether (log n)2 space is enough to recognize all languages recognizable in deterministic polynomial time. the above question has been narrowed down in [c] to the storage required to recognize a particular language called sp. this paper presents further evidence in support of the conjecture that sp cannot be recognized using storage (log n)k for any k. in section 2 we consider a game on directed acyclic graphs (dags) and show that at least 0(n1/4) markers are needed to play the game on some n node dags. the 0(n1/4) bound is used in section 3 to show that a fairly general machine to recognize sp also requires 0(n1/4) storage.
reconstructing curves in three (and higher) dimensional space from noisy data. we consider the task of reconstructing a curve in constant dimensional space from noisy data. we consider curves of the form c = [(x,y1,•••,yc) | yj = pj(x)], where the pj's are polynomials of low degree. given n points in (c+1)-dimensional space, such that t of these lie on some such unknown curve c while the other n-t are chosen randomly and independently, we give an efficient algorithm to recover the curve c and the identity of the good points. the success of our algorithm depends on the relation between n, t, c and the degree of the curve c, requiring t = ω (n deg(c)) 1/(c+1). this generalizes, in the restricted setting of random errors, the work of sudan (j. complexity, 1997) and of guruswami and sudan (ieee trans. inf. th. 1999) that considered the case c=1.
matrix multiplication via arithmetic progressions we present a new method for accelerating matrix multiplication asymptotically. thiswork builds on recent ideas of volker strassen, by using a basic trilinear form which is not a matrix product. we make novel use of the salem-spencer theorem, which gives a fairly dense set of integers with no three-term arithmetic progression. our resulting matrix exponent is 2.376.
equational theories and database constraints we present a novel way to formulate database dependencies as sentences of first-order logic, using equational statements instead of horn clauses. dependency implication is directly reduced to equational implication. our approach is powerful enough to express functional and inclusion dependencies, which are the most common database constraints. we present a new proof procedure for these dependencies. we use our equational formulation to derive new upper and lower bounds for the complexity of their implication problems.
semantics and axiomatics of a simple recursive language in this paper, we provide a simple recursive programming language with a semantics and a formal proof system, along the lines of [5], [17] and [23]. we show that the semantics used is the &ldquo;best&rdquo; possible if one admits the validity of algol's copy rule, and that the proof system is complete with respect to the semantics. the definitions and methods used are meant to provide a basis for a broader theory of program schemas, which models parallel as well as sequential programs.
secure multi-party quantum computation. secure multi-party computing, also called secure function evaluation, has been extensively studied in classical cryptography. we consider the extension of this task to computation with quantum inputs and circuits. our protocols are information-theoretically secure, i.e. no assumptions are made on the computational power of the adversary. for the weaker task of verifiable quantum secret sharing, we give a protocol which tolerates any t &xi; n/4 cheating parties (out of n). this is shown to be optimal. we use this new tool to show how to perform any multi-party quantum computation as long as the number of dishonest players is less than n/6.
a polynomial-time algorithm to approximately count contingency tables when the number of rows is constant. we consider the problem of counting the number of contingency tables with given row and column sums. this problem is known to be #p-complete, even when there are only two rows (random structures algorithms 10(4) (1997) 487). in this paper we present the first fully polynomial randomized approximation scheme for counting contingency tables when the number of rows is constant. a novel feature of our algorithm is that it is a hybrid of an exact counting technique with an approximation algorithm, giving two distinct phases. in the first, the columns are partitioned into "small" and "large". we show that the number of contingency tables can be expressed as the weighted sum of a polynomial number of new instances of the problem, where each instance consists of some new row sums and the original large column sums. in the second phase, we show how to approximately count contingency tables when all the column sums are large. in this case, we show that the solution lies in approximating the volume of a single convex body, a problem which is known to be solvable in polynomial time (j. acm 38 (1) (1991) 1).
approximately counting integral flows and cell-bounded contingency tables. we consider the problem of approximately counting integral flows in a network. we show that there is an fpras based on volume estimation if all capacities are sufficiently large, generalising a result of dyer, kannan and mount (1997). we apply this to approximating the number of contingency tables with prescribed cell bounds when the number of rows is constant, but the row sums, column sums and cell bounds may be arbitrary. we provide an fpras for this problem via a combination of dynamic programming and volume estimation. this generalises an algorithm of cryan and dyer (2002) for standard contingency tables, but the analysis here is considerably more intricate.
on the sum-of-squares algorithm for bin packing. in this article we present a theoretical analysis of the online sum-of-squares algorithm (ss) for bin packing along with several new variants. ss is applicable to any instance of bin packing in which the bin capacity b and item sizes s(a) are integral (or can be scaled to be so), and runs in time o(nb). it performs remarkably well from an average case point of view: for any discrete distribution in which the optimal expected waste is sublinear, ss also has sublinear expected waste. for any discrete distribution where the optimal expected waste is bounded, ss has expected waste at most o(log n). we also discuss several interesting variants on ss, including a randomized o(nb log b)-time online algorithm ss&ast; whose expected behavior is essentially optimal for all discrete distributions. algorithm ss&ast; depends on a new linear-programming-based pseudopolynomial-time algorithm for solving the np-hard problem of determining, given a discrete distribution f, just what is the growth rate for the optimal expected waste.
the degree hierarchy of undecidable problems of formal grammars after a brief discussion of historical matters in &sect;1, twenty-seven predicates of formal grammers are introduced in &sect;2. the next two sections discuss recursively enumerable predicates and nonrecursively enumerable predicates, respectively. these results show that the degree of unsolvability of a predicate is determined by its domain of definition. the paper concludes with a degree diagram and suggestions for further development. from a more comprehensive point of view these results complement the computational complexity classification of solvable problems and extend that classification to unsolvable problems based on their degree of unsolvability.