waashk/acm huggingface dataset:
are search and decision programs computationally equivalent?  from the point of view of sequential polynomial time computation, the answer to the question in the title is 'yes'. the process of self- reducibility is a linear time turing (oracle) reduction from a given combinatorial search problem to an appropriately defined decision problem.  however, from the point of view of fast parallel computation, the answer is not so clear. many of the sequential algorithms that were 'marked off' as being "inherently sequential" embed within them the self-reducibility process. can this inherently sequential process be parallelized?  to study this problem, we define an abstract setting (namely that of an independence system) in which one, universal search problem captures all combinatorial search problems. we consider several natural decision and function oracles to which this search problem may be reduced.  on the positive side, we give efficient probabilistic parallel reductions to these oracles. these reductions constitute a scheme for parallelizing search problems in case the oracles for these problems are themselves efficiently computable in parallel. we give examples of problems that did not yield to parallelism before, but can be parallelized using this scheme.  on the negative side, we prove lower bounds on any determininistic parallel reductions to the same oracles. if p processors are used, the sequential (linear) running time cannot be enhanced by more than a factor of (log p) and hence for any polynomial number of processors the problem remains inherently sequential. this proves that randomization can be exponentially more powerful than determinism in our model, and suggests that nc random nc.  finally, we state some intriguing conjectures and suggest new directions of research in complexity theory that arise from this work.  r m karp e upfal a wigderson
quadratic lower bounds for deterministic and nondeterministic one-tape turing machines  we introduce new techniques for proving quadratic lower bounds for deterministic and nondeterministic l-tape turing machines (all considered turing machines have an additional oneway input tape). in particular we produce quadratic lower bounds for the simulation of 2-tape tm's by l-tape tm's and thus answer a rather old question (problem no.1 and no.7 in the list of duris, galil, paul, reischuk [3]). further we demonstrate a substantial superiority of nondeterminism over determinism and of co- nondeterminism over nondeterminism for l-tape tm's.  wolfgang maass
generalized conjunctive types  the definitions of conjunctive types and their subtype relation, as introduced by coppo-dezani, are extended to consider the conjunction as a partial mapping from pairs of types to types, and the subtype relation as a relation between finite sets of types and types. these extensions basically mean that only conjunctions of compatible types are allowed and that the subtype relation is more like, so to speak, the implication in propositional logic. we show that the basic properties of the typing system with conjunctive types are still true. the terms that have a type are exactly the terms that are convertible to a head normal form and it is possible to characterize the terms with normal form by means of the types that are derivable for them in the system. furthermore, the type assignment defines the interpretation of terms in a very general class of models of the λ-calculus: the models that are based on an information system, as defined by scott.  g. monteleone
partial polymorphic type inference and higher-order unification  we show that the problem of partial type inference in the nth-order polymorphic λ-calculus is equivalent to nth-order unification. on the one hand, this means that partial type inference in polymorphic λ-calculi of order 2 or higher is undecidable. on the other hand, higher-order unification is often tractable in practice, and our translation entails a very useful algorithm for partial type inference in the ω-order polymorphic λ-calculus. we present an implementation in λprolog in full.  frank pfenning
learning k-term dnf formulas with an incomplete membership oracle  we consider the problem of learning k-term dnf formulas using equivalence queries and incomplete membership queries as defined by angluin and slonim. we demonstrate that this model can be applied to non-monotone classes. namely, we describe a polynomial-time algorithm that constructs a k-term dnf formula representationally equivalent to the target using incomplete membership queries and equivalence queries from the class of dnf formulas.  sally a. goldman h. david mathias
on simultaneous inner and outer approximation of shapes  for compact euclidean bodies p, q, we define λ(p, q) to be smallest ratio r/s where r > 0, s > 0 satisfy sq′ p rq″. here sq denotes a scaling of q by factor s, and q′, q″ are some translates of q. this function λ gives us a new distance function between bodies which, unlike previously studied measures, is invariant under affine transformations. if homothetic bodies are identified, the logarithm of this function is a metric. (two bodies are homothetic if one can be obtained from the other by scaling and translation).  for integer  ≥ 3, define λ( ) to be the minimum value such that for each convex polygon p there exists a convex  -gon q with λ(p, q) ≤ λ( ). among other results, we prove that 2.118… ≤ λ(3) ≤ 2.25 and λ( ) = 1 + ( -2). we give an  (n22 n) time algorithm which for any input convex n-gon p, finds a triangle t that minimizes λ(t, p) among triangles. but in linear time, we can find a triangle t with λ(t, p) ≤ 2.25.  our study is motivated by the attempt to reduce the complexity of the polygon containment problem, and also the motion planning problem.  in each case, we describe algorithms which will run faster when certain implicit slackness parameters of the input are bounded away from 1. these algorithms illustrate a new algorithmic paradigm in computational geometry for coping with complexity.  rudolf fleischer kurt mehlhorn gunter rote emo welzl chee yap
the minimum consistent dfa problem cannot be approximated within any polynomial  the minimum consistent dfa problem is that of finding a dfa with as few states as possible that is consistent with a given sample (a finite collection of words, each labeled as to whether the dfa found should accept or reject). assuming that p  np, it is shown that for any constant k, no polynomial-time algorithm can be guaranteed to find a consistent dfa with fewer than optk states, where opt is the number of states in the minimum state dfa consistent with the sample. this result holds even if the alphabet is of constant size two, and if the algorithm is allowed to produce an nfa, a regular expression, or a regular grammar that is consistent with the sample. a similar nonapproximability result is presented for the problem of finding small consistent linear grammars. for the case of finding minimum consistent dfas when the alphabet is not of constant size but instead is allowed to vary with the problem specification, the slightly stronger lower bound on approximability of opt(1-ε)log logopt is shown for any ε > 0.  leonard pitt manfred k. warmuth
logics capturing local properties  well-known theorems of hanf and gaifman establishing locality of first-order definable properties have been used in many applications. these theorems were recently generalized to other logics, which led to new applications in descriptive complexity and database theory. however, a logical characterization of local properties that correspond to hanf's and gaifman's theorems is still lacking. such a characterization only exists for structures of bounded valence. in this paper, we give logical characterizations of local properties behind hanf's and gaifman's theorems. we first deal with an infinitary logic with counting terms and quantifiers that is known to capture hanf-locality on structures of bounded valence. we show that testing isomorphism of neighborhoods can be added to it without violating hanf- locality, while increasing its expressive power. we then show that adding local second-order quantification to it caputures precisely all hanf-local properties. to capture gaifman-locality, one must also add a (potentially infinite) case statement. we further show that the hierarchy based on the number of variants in the case statement is strict.  leonid libkin
recent progress in understanding minimax search  lookahead search has been known for a long time to be effective in tackling problems which can be cast in minimax form (mainly game playing, but others include maintaining unstable balance against gravity, and business decisions). recent results have shown that the benefit of lookahead depends on the structure inherent in the problem, and even that there exist some minimax problems for which lookahead search is dis-advantageous. this paper reviews those results and then discusses algorithms which can be interpreted as recognising the structure of local areas of the search in order to control search expansion. such algorithms can be orders of magnitude more cost- effective than search using alpha-beta alone.  d. f. beal
optimal separations between concurrent-write parallel machines  we obtain tight bounds on the relative powers of the priority and common models of parallel random-access machines (prams). specifically we prove that:  the element distinctness function of n integers, though solvable in constant time on a priority pram with n processors, requires (a(n,p)) time to solve on a common pram with p ≥ n processors, where a ;(n,p) = n log n/p log (n/p log n \\+ 1).  one step of a priority pram with n processors can be simulated on a common pram with p processors in  (a(n,p)) steps.  as an example, the results show that the time separation between priority and common prams each with n processors is (log n/log log n).  r. b. boppana
concepts and experiments in computational reflection  this paper brings some perspective to various concepts in computational reflection. a definition of computational reflection is presented, the importance of computational reflection is discussed and the architecture of languages that support reflection is studied. further, this paper presents a survey of some experiments in reflection which have been performed. examples of existing procedural, logic-based and rule-based languages with an architecture for reflection are briefly presented. the main part of the paper describes an original experiment to introduce a reflective architecture in an object- oriented language. it stresses the contributions of this language to the field of object-oriented programming and illustrates the new programming style made possible. the examples show that a lot of programming problems that were previously handled on an ad hoc basis, can in a reflective architecture be solved more elegantly.  pattie maes
nondeterministic polynomial-time computations and models of arithmetic:  a semantic, or model theoretic, approach is proposed to study the problems p =? np and np =? co-np. this approach seems to avoid the difficulties that recursion-theoretic approaches appear to face in view of the result of baker et al. on relativizations of the p =? np question; moreover, semantical methods are often simpler and more powerful than syntactical ones. the connection between the existence of certain partial extensions of nonstandard models of arithmetic and the question np =? co-np is discussed. several problems are stated about nonstandard models, and a possible link between the davis-matijasevi@@@@-putnam-robinson theorem on diophantine sets and the np =? co-np question is mentioned.  attila máte
a parallel block algorithm for exact triangularization of rectangular matrices  a new block algorithm for triangularization of regular or singular matrices with dimension _m_ × _n_ is proposed. taking benefit of fast block multiplication algorithms, it achieves the best known sequential complexity _ _(_m& lt;/i>_w_-1_n_) for any sizes and any rank. moreover, the block strategy enables to improve locality with respect to previous algorithms as exhibited by practical performances.  jean-guillaume dumas jean-louis roch
one, two, three . . . infinity: lower bounds for parallel computation  in this paper we compare the power of the two most commonly used concurrent- write models of parallel computation, the common pram and the priority pram. these models differ in the way they resolve write conflicts. if several processors want to write into the same shared memory cell at the same time, in the common model they have to write the same value. in the priority model, they may attempt to write different values; the processor with smallest index succeeds.  we consider pram's with n processors, each having arbitrary computational power. we provide the first separation results between these two models in two extreme cases: when the size m of the shared memory is small (m ≤ nε, ε < 1), and when it is infinite.  in the case of small memory, the priority model can be faster than the common model by a factor of (log n), and this lower bound holds even if the common model is probabilistic. in the case of infinite memory, the gap between the models can be a factor of (log log log n).  we develop new proof techniques to obtain these results. the technique used for the second lower bound is strong enough to establish the first tight time bounds for the priority model, which is the strongest parallel computation model. we show that finding the maximum of n numbers requires (log log n) steps, generalizing a result of valiant for parallel computation trees.  f e fich f meyer auf der heide p ragde a wigderson
a sharp threshold in proof complexity  we give the first example of a sharp threshold in proof complexity. more precisely, we show that for any sufficiently small ε>0 and Δ>2.28, random formulas consisting of (1-ε)n 2-clauses and &amp;dgr; n 3-clauses, which are known to be unsatisfiable almost certainly, almost certainly require resolution and davis- putnam proofs of unsatisfiability of exponential size, whereas it is easily seen that random formulas with (1+ε)n 2-clauses (and Δ n 3 clauses) have linear size proofs of unsatisfiability almost certainly.  a consequence of our result also yields the first proof that typical random 3-cnf formulas at ratios below the generally accepted range of the satisfiability threshold (and thus expected to be satisfiable almost certainly) cause natural davis-putnam algorithms to take exponential time to find satisfying assignments.  dimitris achlioptas paul beame michael molloy
quantum lower bounds by polynomials we examine the number of queries to input variables that a quantum algorithm requires to compute boolean functions on {0,1}_n_ in the _black- box_ model. we show that the exponential quantum speed-up obtained for _partial_ functions (i.e., problems involving a promise on the input) by deutsch and jozsa, simon, and shor cannot be obtained for any _total_ function: if a quantum algorithm computes some total boolean function _f_ with small error probability using _t_ black-box queries, then there is a classical deterministic algorithm that computes _f_ exactly with _o_(_ts6_) queries. we also give asymptotically tight characterizations of _t_ for all symmetric _f_ in the exact, zero-error, and bounded- error settings. finally, we give new precise bounds for and, or, and parity. our results are a quantum extension of the so-called polynomial method, which has been successfully applied in classical complexity theory, and also a quantum extension of results by nisan about a polynomial relationship between randomized and deterministic decision tree complexity. robert beals harry buhrman richard cleve michele mosca ronald de wolf
a general sequential time-space tradeoff for finding unique elements  an optimal (n2) lower bound is shown for the time-space product of any r-way branching program that determines those values which occur exactly once in a list of n integers in the range [1, r] where r ≥ n. this (n2) tradeoff also applies to the sorting problem and thus improves the previous time-space tradeoffs for sorting. because the r-way branching program is a such a powerful model these time-space product tradeoffs also apply to all models of sequential computation that have a fair measure of space such as off-line multi-tape turing machines and off-line log- cost rams.  p. beame
fully abstract compositional semantics for logic programs  we propose a framework for discussing fully abstract compositional semantics, which exposes the interrelations between the choices of observables, compositions, and meanings. every choice of observables and compositions determines a unique fully abstract equivalence. a semantics is fully abstract if it induces this equivalence.  we study the semantics of logic programs within this framework. we find the classical herbrand-base semantics of logic programs inadequate, since it identifies programs that should be distinguished and vice versa. we therefore propose alternative semantics, and consider the cases of no compositions, composition by program union, and composition of logic modules (programs with designated exported and imported predicates). although equivalent programs can be in different vocabularies, we prove that our fully abstract semantics are always in a subvocabulary of that of the program. this subvocabulary, called the essential vocabulary, is common to all equivalent programs. the essential vocabulary is also the smallest subvocabulary in which an equivalent program can be written.  h. gaifman e. shapiro
mso definable string transductions and two-way finite-state transducers  we extend a classic result of buchi, elgot, and trakhtenbrot: mso definable string transductions i.e., string-to-string functions that are definable by an interpretation using monadic second-order (mso) logic, are exactly those realized by deterministic two-way finite-state transducers, i.e., finite-state automata with a two-way input tape and a one- way output tape. consequently, the equivalence of two mso definable string transductions is decidable. in the nondeterministic case however, mso definable string tranductions, i.e., binary relations on strings that are mso definable by an interpretation with parameters, are incomparable to those realized by nondeterministic two-way finite-state transducers. this is a motivation to look for another machine model, and we show that both classes of mso definable string transductions are characterized in terms of hennie machines, i.e., two-way finite-state transducers that are allowed to rewrite their input tape, but may visit each position of their input only a bounded number of times.  joost engelfriet hendrik jan hoogeboom
parallel algorithms for evaluating sequences of set-manipulation operations  given an off-line sequence s of n set-manipulation operations, we investigate the parallel complexity of evaluating s (i.e., finding the response to every operation in s and returning the resulting set). we show that the problem of evaluating s is in nc for various combinations of common set-manipulation operations. once we establish membership in nc (or, if membership in nc is obvious), we develop techniques for improving the time and/or processor complexity.  mikhail j. atallah michael t. goodrich s. rao kosaraju
an improved algorithm for the resolution of singularities  this paper contains several improvements of villamayor's algorithm for the problem of resolution of the singularities of a hypersurface. the first improves the management of the charts which represent the blown up variety. the second improves the way how new resolution problems are created in the recursion, based on hironaka's theory of idealistic exponents. the remaining two improve the way how discrete information is used, based on the adaption of encinas and villamayor of abhyankar's theory of good points.  gábor bodnár josef schicho
call by name, assignment, and the lambda calculus  we define an extension of the call-by-name lambda calculus with additional constructs and reduction rules that represent mutable variables and assignments. the extended calculus has neither a concept of an explicit store nor a concept of evaluation order; nevertheless, we show that programs in the calculus can be implemented using a single-threaded store. we also show that the new calculus has the church-rosser property and that it is a conservative extension of classical lambda calculus with respect to operational equivalence; that is, all algebraic laws of the functional subset are preserved.  martin odersky dan rabin paul hudak
castles in the air revisited  we show that the total number of faces bounding any single cell in an arrangement of n (d\\--1)-simplices in ird is o(nd\\--1 log n), thus almost settling a conjecture of pach and sharir. we present several applications of this result, mainly to translational motion planning in polyhedral environments. we then extend our analysis technique to derive other results on complexity in simplex arrangements. for example, we show that the number of vertices in such an arrangement, which are incident to the same cell on more than one "side," is o (nd-1 log n). we also show that the number of repetitons of a "k-flap," formed by intersecting d\\--k simplices, along the boundary of the same cell, summed over all cells and all k-flaps, is o(nd-1~~ log n). we use this quantity, which we call the excess of the arrangement, to derive bounds on the complexity of m distinct cells of such an arrangement.  boris aronov micha sharir
recognizing substrings of lr(k) languages in linear time  lr parsing techniques have long been studied as efficient and powerful methods for processing context free languages. a linear time algorithm for recognizing languages representable by lr(k) grammars has long been known. recognizing substrings of a context-free language is at least as hard as recognizing full strings of the language, as the latter problem easily reduces to the former. in this paper we present a linear time algorithm for recognizing substrings of lr(k) languages, thus showing that the substring recognition problem for these languages is no harder than the full string recognition problem. an interesting data structure, the forest structured stack, allows the algorithm to track all possible parses of a substring without loosing the efficiency of the original lr parser. we present the algorithm, prove its correctness, analyze its complexity, and mention several applications that have been constructed.  joseph bates alon lavie
counting triangle crossings and halving planes  every collection of t ≥ 2n2 triangles witha total of n vertices in r3 has w4n6< /de> crossing pairs. this implies that one of their edgesmeetswt3n6 of the triangles. from this it followsthat n points in  r3 have only o(n8/3) halvingplanes.  tamal k. dey herbert edelsbrunner
dataflow for logic program as substitution manipulator  this paper shows a method of constructing a dataflow, which denotes the deductions of a logic program, by means of a sequence domain based on equivalence classes of substitutions. the dataflow involves fair merge functions to represent unions of atom subsets over a sequence domain, as well as functions as manipulations of unifiers for the deductions of clauses. a continuous functional is associated with the dataflow on condition that the dataflow completely and soundly denotes the atom generation in terms of equivalent substitutions sets. its least fixpoint is interpreted as denoting the whole atom generation based on manipulations of equivalent substitutions sets.  s. yamasaki