waashk/acm huggingface dataset:
many hard examples for resolution  for every choice of positive integers c and k such that k ≥ 3 and c< /italic>2-k ≥ 0.7, there is a positive number ε such that, with probability tending to 1 as n tends to ∞, a randomly chosen family of cn clauses of size k over n variables is unsatisfiable, but every resolution proof of its unsatisfiability must generate at least (1 + ε)n clauses.  vasek chvatal endre szemeredi
sparse dynamic programming ii: convex and concave cost functions  dynamic programming solutions to two recurrence equations, used to compute a sequence alignment from a set of matching fragments between two strings, and to predict rna secondary structure, are considered. these recurrences are defined over a number of points that is quadratic in the input size; however, only a sparse set matters for the result. efficient algorithms are given for solving these problems, when the cost of a gap in the alignment or a loop in the secondary structure is taken as a convex or concave function of the gap or loop length. the time complexity of our algorithms depends almost linearly on the number of points that need to be considered; when the problems are sparse, this results in a substantial speed-up over known algorithms.  david eppstein zvi galil raffaele giancarlo giuseppe f. italiano
orthologic and quantum logic: models and computational elements  motivated by a growing need to understand the computational potential of quantum devices we suggest an approach to the relevant issues via quantum logic and its model theory. by isolating such notions as quantum parallelism and interference within a model-theoretic setting, quite divorced from their customary physical trappings, we seek to lay bare their logical underpinnings and possible computational ramifications.  in the first part of the paper, a brief account of the relevant model theory is given, and some new results are derived. in the second part, we model the simplest classical gate, namely the n-gate, propose a quantization scheme (which translates between classical and quantum models, and from which emerges a logical interpretation of the notion of quantum parallelism), and apply it to the classical n-gate model. a class of physical instantiations of the resulting quantum n-gate model is also briefly discussed.  j. p. rawling s. a. selesnick
finding minimum-cost circulations by canceling negative cycles  a classical algorithm for finding a minimum-cost circulation consists of repeatedly finding a residual cycle of negative cost and canceling it by pushing enough flow around the cycle to saturate an arc. we show that a judicious choice of cycles for canceling leads to a polynomial bound on the number of iterations in this algorithm. this gives a very simple strongly polynomial algorithm that uses no scaling. a variant of the algorithm that uses dynamic trees runs in o(nm(log n) min{log(nc), mlog n}) time on a network of n vertices, m arcs, and arc costs of maximum absolute value c. this bound is comparable to those of the fastest previously known algorithms.  andrew goldberg robert tarjan
range searching with efficient hierarchical cuttings  we present an improved space/query time tradeoff for the general simplex range searching problem, matching known lower bounds up to small polylogarithmic factors. in particular, we construct a linear-space simplex range searching data structure with o(n1 \--1/d) query time, which is optimal for d=2 and probably also for d>2\\. further we show that multilevel range searching data structures can be built with only a polylogarithmic overhead in space and query time per level (the previous solutions require at least a small fixed power of n). we show that hopcroft's problem (detecting an incidence among n lines and n points) can be solved in time n&amp;l; t;/italic>4/32(log n). in all these algorithms, we apply chazelle's results on computing optimal cuttings.  jiri matousek
logic programming as constructivism: a formalization and its application to databases  the features of logic programming that seem unconventional from the viewpoint of classical logic can be explained in terms of constructivistic logic. we motivate and propose a constructivistic proof theory of non-horn logic programming. then, we apply this formalization for establishing results of practical interest. first, we show that 'stratification' can be motivated in a simple and intuitive way. relying on similar motivations, we introduce the larger classes of 'loosely stratified' and 'constructively consistent' programs. second, we give a formal basis for introducing quantifiers into queries and logic programs by defining 'constructively domain independent' formulas. third, we extend the generalized magic sets procedure to loosely stratified and constructively consistent programs, by relying on a 'conditional fixpoint' procedure.  f. bry
proof verification and the hardness of approximation problems  we show that every language in np has a probablistic verifier that checks membership proofs for it using logarithmic number of random bits and by examining a constant number of bits in the proof. if a string is in the language, then there exists a proof such that the verifier accepts with probability 1 (i.e., for every choice of its random string). for strings not in the language, the verifier rejects every provided "proof" with probability at least 1/2. our result builds upon and improves a recent result of arora and safra [1998] whose verifiers examine a nonconstant number of bits in the proof (though this number is a very slowly growing function of the input length).  as a consequence, we prove that no max snp-hard problem has a polynomial time approximation scheme, unless np = p. the class max snp was defined by papadimitriou and yannakakis [1991] and hard problems for this class include vertex cover, maximum satisfiability, maximum cut, metric tsp, steiner trees and shortest superstring. we also improve upon the clique hardness results of feige et al. [1996] and arora and safra [1998] and show that there exists a positive ε such that approximating the maximum clique size in an n-vertex graph to within a factor of nε is np-hard.  sanjeev arora carsten lund rajeev motwani madhu sudan mario szegedy
monotone circuits for connectivity require super-logarithmic depth  we prove that every monotone circuit which tests st-connectivity of an undirected graph on n nodes has depth (log2n). this implies a superpolynomial (n (log n)) lower bound on the size of any monotone formula for st- connectivity.  the proof draws intuition from a new characterization of circuit depth in terms of communication complexity. it uses counting arguments and extremal set theory.  within the same framework, we also give a very simple and intuitive proof of a depth analogue of a theorem of krapchenko concerning formula size lower bounds.  mauricio karchmer avi wigderson
a new class of heuristic algorithms for weighted perfect matching  the minimum-weight perfect matching problem for complete graphs of n vertices with edge weights satisfying the triangle inequality is considered. for each nonnegative integer k ≤ log3n, and for any perfect matching algorithm that runs in t(n) time and has an error bound of (n) times the optimal weight, an & lt;italic>o(max{n, t(3-kn)})-time heuristic algorithm with an error bound of (7/3)k(1 + (3 kn)) - 1 is given. by the selection of k as appropriate functions of n, heuristics that have better running times and/or error bounds than existing ones are derived.  m. d. grigoriadis b. kalantari
on the arithmetic power of context-free languages  our research focuses on characterizing the computational limits of context- free languages based on a non-classical definition of "computation". in our study we identify a computation as a process of recognizing a string of a's and b's in which the number b's is a function of the number of a's. we feel that this ability to "compute" arithmetic functions in this sense is a fundamental property that should be examined for all models of computation. our poster presents a proof of what we have called the arithmetic power theorem for context-free languages that we state as follows:  _arithmetic power theorem for context-free languages_: a language l of the form l=ai bf(i) is context-free only if f(i)= (i) or f(i) = (1).  our approach in proving this theorem was directed towards a reformulation of our question based on subsets of l that we called pumping sets. the notion of a pumping set is a generalization, and in many ways is an extension, of the well-known pumping lemma that exposes the ability to "pump" a given string in a context-free language into another string in the same language via replication. pumping sets are not found in the standard textbooks on computational theory [1][2][3] and to our knowledge are absent from the existing research on context-free grammars. however, the study of sets of pumped strings (known as _paired loops_) has yielded interesting results in the area of _slender languages_ [4].  we define a pumping set as follows: a pumping set of a derivation is the set of all strings obtained by replicating a path between two occurrences of some non- terminal in the derivation tree. this is illustrated in the following example:  we call the derivation in the definition of pumping set a generator of a pumping set. it was necessary to establish several properties which would allow us to use pumping sets to characterize the ability of a production rule in a grammar (or a sequence of such rules) to affect the growth of b's in the strings of our language l.  albert goldfain
analytic constraint solving and interval arithmetic  in this paper we describe the syntax, semantics, and implementation of the constraint logic programming language clp(f) and we prove that the implementation is sound. a clp(f) constraint is a conjunction of equations and inequations in a first order theory of analytic univariate functions over the reals. the theory allows vector-valued functions over closed intervals to be constrained in several ways, including specifying functional equations (possibly involving the differentiation operator) that must hold at each point in the domain, arithmetic constraints on the value of a function at a particular point in its domain, and bounds on the range of a function over its domain. after describing the syntax and semantics of the constraint language for clp(f) and giving several examples, we show how to convert these analytic constraints into a subclass of simpler functional constraints which involve neither differentiation nor evaluation of functions. we then present an algorithm for solving these latter constraints and prove that it is sound. this implies the soundness of the clp(f) interpreter. we also provide some timing results from an implementation of clp(f) based on gnu prolog. the current implementation is able to solve a wide variety of analytic constraints, but on particular classes of constraints (such as initial value problems for autonomous odes), it is not competitive with other non-constraint based, interval solvers such as lohner's awa system. clp(f) should be viewed as a first step toward the long term goal of developing a practical, declarative, logic-based approach to numerical analysis.  timothy j. hickey
a generalized class of polynomials that are hard to factor  a class of univariate polynomials is defined which make the berlekamp-hensel factorization algorithm take an exponential amount of time. the class contains as subclasses the swinnerton-dyer polynomials discussed by berlekamp and a subset of the cyclotomic polynomials. aside from shedding light on the complexity of polynomial factorization this class is also useful in testing implementations of the berlekamp-hensel and related algorithms.  erich kaltofen david r. musser b. david saunders
reversal complexity of counter machines  it has long been known that deterministic 1-way counter machines recognize exactly all r.e. sets. here we investigate counter machines with general recursive bounds on counter reversals. our main result is that for bounds which are at least linear, counter reversal is polynomially related to turing machine time, for both 1-way and 2-way counter machines and in both the deterministic and the nondeterministic cases. this leads to natural characterizations of the classes p and np, and hence of the p ? np question, on the counter machine model. we also establish reversal complexity hierarchies for counter machines, using a variety of techniques which include translation of turing machine time hierarchies, padding arguments as well as more ad hoc counting arguments.  tat-hung chan
parallel rams with owned global memory and deterministic context-free language recognition  we identify and study a natural and frequently occurring subclass of concurrent read, exclusive write parallel random access machines (crew-prams). called concurrent read, owner write, or crow-prams, these are machines in which each global memory location is assigned a unique "owner" processor, which is the only processor allowed to write into it. considering the difficulties that would be involved in physically realizinga full crew-pram model and demonstrate its stability under several definitional changes. second, we precisely characterize the power of the crow-pram by showing that the class of languages recognizable by it in time o(log n) (and implicity with a polynomial number of processors) is exactly the class logdcfl of languages log space reducible to deterministic context-free languages. third, using the same basic machinery, we show that the recognition problem for deterministic context-free languages can be solved quickly on a deterministic auxilliary pushdown automation having random access to its input tape, a log n space work tape, and pushdown store of small maximum height. for example, time o(n1 \+ ε) is achievable with pushdown height o(log2 n). these result extend and unify work of von braunmohl, cook, mehlhorn, and verbeek, klein and reif; and rytter.  patrick w. dymond walter l. ruzzo
on efficient unsuccessful search  this paper introduces a general technique for speeding up unsuccessful search using very little extra space (2 bits per key). this technique is applicable to many data structures including linear lists, and search trees. for linear lists we get on-line algorithms for processing a sequence of successful and unsuccessful searches which are competitive with strong off-line algorithms. in a virtual memory environment our self-adjusting algorithm for multi-way search trees is competitive with an optimal static multi-way tree and will often outperform the static tree.  lucas chi kwong hui charles martel
some distributions that allow perfect packing  a probability distribution μ on [0, 1] allows perfect packing if n items of size x1, … , xn , independent and identically distributed according to μ can be packed in unit size bins in such a way that the expected wasted space is o(n). a large class of distributions that allow perfect packing is exhibited. as a corollary, the intervals [a, b] for which the uniform distribution on [a, b] allows perfect packing are determined.  wansoo t. rhee michel talagrand
when do extra majority gates help?  suppose that f is computed by a constant depth circuit with 2m and-, or-, and not-gates, and m majority-gates. we prove that f is computed by a constant depth circuit with 2& lt;supscrpt>m o(1) and-, or-, and not-gates, and a single majority-gate, which is at the root.  one consequence is that if f is computed by and ac0 circuit plus polylog majority-gates, then f is computed by a probabilistic perceptron having polylog order. another consequence is that if f agrees with the parity function of three- fourths of all inputs, then fcannot be computed by a constant depth circuit with 2no(1) and-, or-, and not- gates, and no(1) majority-gates.  richard beigel
fast programs for initial segments and polynomial time computation in weak models of arithmetic (preliminary abstract)  in this paper we study two alternative approaches for investigating whether np complete sets have fast algorithms. one is to ask whether there are long initial segments on which such sets are easily decidable by relatively short programs. the other approach is to ask whether there are weak fragments of arithmetic for which it is consistent to believe that p np. we show, perhaps surprisingly, that the two questions are equivalent: it is consistent to believe that p np in certain models of weak arithmetic theories iff it is true (in the standard model of computation) that there are infinitely many initial segments on which satisfiability is polynomially decidable by programs that are much shorter than the length of the initial segment.  deborah joseph paul young
on the complexity of functions for random access machines  tight bounds are proved for sort, merge, insert, gcd of integers, gcd of polynomials, and rational functions over a finite inputs domain, in a random access machine with arithmetic operations, direct and indirect addressing, unlimited power for answering yes/no questions, branching, and tables with bounded size. these bounds are also true even if additions, subtractions, multiplications, and divisions of elements by elements of the field are not counted.  in a random access machine with finitely many constants and a bounded number of types of instructions, it is proved that the complexity of a function over a countable infinite domain is equal to the complexity of the function in a sufficiently large finite subdomain.  nader h. bshouty
inverse currying transformation on attribute grammars  inverse currying transformation of an attribute grammar moves a context condition to places in the grammar where the violation of the condition can be detected as soon as the semantic information used in the condition is computed. it thereby takes into account the evaluation order chosen for the attribute grammar. inverse currying transformations can be used to enhance context sensitive parsing using predicates on attributes, to eliminate sources of backtrack when parsing according to ambiguous grammars, and to facilitate semantics-supported error correction.  reinhard wilhelm
convex decompositions of polyhedra  an important direction of research in computational geometry has been to find methods for decomposing complex structures into simpler components. in this paper, we examine the problem of decomposing a three-dimensional polyhedron p into a minimal number of convex pieces. letting n be the number of vertices in p and n the number of edges which exhibit a reflex angle (i.e. the notches of p), our main result is an o(nn3) time algorithm for computing a convex decomposition of p. the algorithm produces o(n2) convex parts, which is optimal in the worst case. in most situations where the problem arises (e.g. graphics, tool design, pattern recognition), the number of notches n seems greatly dominated by the number of vertices n; the algorithm is therefore viable in practice.  bernard m. chazelle
bounded quantification is undecidable  f≤ is a typed λ-calculus with subtyping and bounded second-order polymorphism. first proposed by cardelli and wegner, it has been widely studied as a core calculus for type systems with subtyping.  curien and ghelli proved the partial correctness of a recursive procedure for computing minimal types of f≤ terms and showed that the termination of this procedure is equivalent to the termination of this procedure is equivalent to the termination of its major component, a procedure for checking the subtype relation between f≤ types. this procedure was thought to terminate on all inputs, but the discovery of a subtle bug in a purported proof of this claim recently reopened the question of the decidability of subtyping, and hence of typechecking.  this question is settled here in the negative, using a reduction from the halting problem for two-counter turing machines to show that the subtype relation of f≤ is undecidable.  benjamin c. pierce
a decision method for the equivalence of some non-real-time deterministic pushdown automata  a generalization of the alternate stacking procedure of valiant for deciding the equivalence of some deterministic pushdown automata (dpda) is introduced. to analyze the power of the generalized procedure we define a subclass of dpda's, called the proper dpda's. this class properly contains the non- singular dpda's and the real time strict dpda's, and the corresponding class of languages properly contains the real time strict deterministic languages. the equivalence problem for proper automata is reducible to the problem of deciding whether or not an automaton is proper. the main result of the paper is that the generalized procedure yields an equivalence test for proper dpda's, at least one of which is also a finite-turn machine.  esko ukkonen
a note on efficient zero-knowledge proofs and arguments (extended abstract)  in this note, we present new zero-knowledge interactive proofs and arguments for languages in np. to show that x ε l, with an error probability of at most 2-k, our zero-knowledge proof system requires o(|x|c1)+o(lg&amp;l; t;supscrpt>c2 |x|)kc1 and c2 depend only on l. this construction is the first in the ideal bit commitment model that achieves large values of k more efficiently than by running k independent iterations of the base interactive proof system. under suitable complexity assumptions, we exhibit zero knowledge arguments that require o(lgc|x|kl bits of communication, where c depends only on l, and l is the security parameter for the prover. this is the first construction in which the total amount of communication can be less than that needed to transmit the np witness. our protocols are based on efficiently checkable proofs for np[4].  joe kilian
a dynamic load balancer for a parallel branch and bound algorithm  this paper presents a load-balancing scheme for a parallel branch and bound (pbb) algorithm utilizing a dynamic load balancer (dlb). the pbb algorithm is used to solve a resource scheduling problem on the hypercube. the dlb is included in the pbb algorithm and is distributed to each node to balance the workload during run time. the dlb is evaluated by implementing two pbb algorithms, with dlb and without dlb. results show that the pbb with dlb is 3.14 times faster than the algorithm without dlb.  r. p. ma f-s. tsung m-h. ma
a syntactic theory of message passing  recent developments by hewitt and others have stimulated interest in message- passing constructs as an alternative to the more conventional applicative semantics on which most current languages are based. the present work illuminates the distinction between applicative and message-passing semantics by means of the μ-calculus, a syntactic model of message-passing systems similar in mechanism to the λ-calculus. algorithms for the translation of expressions from the λ\- to the μ-calculus are presented, and differences between the two approaches are discussed.  message-passing semantics seem particularly applicable to the study of multiprocessing. the μ-calculus, through the mechanism of conduits, provides a simple model for a limited but interesting class of parallel computations. multiprocessing capabilities of the μ-calculus are illustrated, and multiple- processor implementations are discussed briefly.  stephen a. ward robert h. halstead
an algorithm for finding canonical sets of ground rewrite rules in polynomial time  in this paper, it is shown that there is an algorithm that, given by finite set e of ground equations, produces a reduced canonical rewriting system r equivalent to e in polynomial time. this algorithm based on congruence closure performs simplification steps guided by a total simplification ordering on ground terms, and it runs in time o(n3).  jean gallier paliath narendran david plaisted stan raatz wayne snyder