waashk/acm huggingface dataset:
testing polynomials which are easy to compute (extended abstract)  we exploit the fact that the set of all polynomials pε@@@@[x1,..,xn] of degree ≤d which can be evaluated with ≤v nonscalar steps can be embedded into a zariski-closed affine set w(d,n,v),dim w(d,n,v)≤(v+1 +n)2 and deg w(d,n,v)≤(2vd)(v+1+n)2. as a consequence we prove that for u: 2v(d+1)2 and s: 6(v+1+n)2 there exist &amp;abarbelow;~~1,..,&amp;abarbelow;sε [u]n {1,2,..,u}n such that for all polynomials pεw(d,n,v):p(&amp;abarbelow;1) p(&amp;abarbelow;2) ... p(&amp;abarbelow;s) o implies p o. this means that &amp;abarbelow;1,...,&amp;abarbelow;< supscrpt>s is a correct test sequence for a zero test on all polynomials in w(d,n,v). moreover, "almost every" sequence &amp;abarbelow;1,..,&amp;abarbelow;s ε[u]n is such a correct test sequence for w(d,n,v). the existence of correct test sequences &amp;abarbelow; 1,..,&amp;abarbelow;sε [u]n is established by a counting argument without constructing a correct test sequence. we even show that it is beyond the known methods to establish (i.e. to construct and to prove correctness) of such a short correct test sequence for w(d,n,v). we prove that given such a short, correct test sequence for w(d,n,v) we can efficiently construct a multivariate polynomial pε@@@@[x,..,xn] with deg(p) d and small integer coefficients such that p@@@@ w(d,n,v). for v>n log d lower bounds of this type are beyond our present methods in algebraic complexity theory.  j. heintz c. p. schnorr
the tight deterministic time hierarchy  let k be a constant -&-ge; 2, and let us consider only deterministic k-tape turing machines.  we assume t2(n) -&-gt; n and t2 is computable in time t2. then there is a language which is accepted in time t2, but not accepted in any time t1 with t1(n) -&-equil; o(t2(n)).  furthermore, we obtain a strong hierarchy (isomorphic to the rationals q) for languages accepted in fixed space and variable time.  martin furer
turtle graphics: hidden features in apl2 twenty-five years ago martin gardner wrote an article in "mathematical games" of the scientific american with the title _fantastic patterns traced by programmed "worms"_ [gar 1]. later on these worms were called "turtles". these turtle graphics are well known from the logo-system [ab/dis].these graphics are also vector graphics not made by setting absolute coordinates but by setting relative increments of distances and angles. with tiny apl2 idioms i have developed many 2d-graphics. it has happened in a short time in a normal manner and as a dialogue form. my top is "_one-liner as eye liner_" hendrik rama
problems, puzzles, challenges this new section is for the submission of problems, puzzles and challenges for our computer algebra systems to solve, and for publishing the computer solutions to the above. we start the problem section by presenting some problems that appear at first glance to be purely numerical, that is they look like they should be solvable by using a purely numerical package. however, you may find that this just leads to an error message when you try to solve them using a purely numerical package. can our computer algebra systems come to the rescue and solve the following problems? g. j. fee m. b. managan
an operator calculus  this paper extends a line of apl development presented in a sequence of papers [1-7] over the past six years. the main topics addressed are the interactions of operators such as rank, composition, derivative, and inverse (i.e., the beginnings of a calculus of operators), a simplification in the complement of attributes tentatively presented in [6], and a treatment of the shapes of individual results (as defined in [7]) in the case of empty frames.  brief treatments are also given to a number of smaller matters: a transliteration or token substitution facility, the treatment of niladic functions, a custom (variant) operator, the obsolescence of certain system variables, and some changes in the function definition operator and in the treatment of supernumerary axes.  kenneth e. iverson roland pesch j. henri schueler
two infinite sets of primes with fast primality tests  infinite sets p and q of primes are described, p q. for any natural number n it can be decided if n ∈ p in (deterministic) time ((log n)9). this answers affirmatively the question of whether there exists an infinite set of primes whose membership can be tested in polynomial time, and is the main result of the paper. also, for every n ∈ q, we show how to produce at random, in expected time ((log n)3), a certificate of length (log n) which can be verified in (deterministic) time ((log n)3); this is less than the time needed for two exponentiations and is much faster than existing methods. finally it is important that p is relatively dense (at least cn& lt;/italic>2/3/log n elements less than n). elements of q in a given range may be generated quickly, but it would be costly for an adversary to search q in this range; this could be useful in cryptography.  jános pintz william steiger endre szemeredi
an algorithm for parallel computation of partial sums  an algorithm for parallel computation of several partial sums is proposed. the partial sums are partitioned into sets of r sums each. all sets are computed in parallel. in each set the redundancy shown to be inherent to the problem is utilized to reduce the required computation. in addition to a memory- accumulator architecture proposed earlier to implement this algorithm, a permuter-adder tree implementation is considered. both approaches admit of implementation in vlsi, ccd or software form. the addition operation could be replaced by any commutative and associative binary operation, with implications for a wide class of applications.  adly t. fam
trading group theory for randomness  in a previous paper [bs] we proved, using the elements of the theory of nilpotent groups, that some of the fundamental computational problems in matriz groups belong to np. these problems were also shown to belong to conp, assuming an unproven hypothesis concerning finite simple groups.  the aim of this paper is to replace most of the (proven and unproven) group theory of [bs] by elementary combinatorial arguments. the result we prove is that relative to a random oracle b, the mentioned matrix group problems belong to (np conp)_b.  the problems we consider are membership in and order of a matrix group given by a list of generators. these problems can be viewed as multidimensional versions of a close relative of the discrete logarithm problem. hence np conp might be the lowest natural complexity class they may fit in.  we remark that the results remain valid for black box groups where group operations are performed by an oracle.  the tools we introduce seem interesting in their own right. we define a new hierarchy of complexity classes am(k) "just above np", introducing arthur vs. merlin games, the bounded-away version of papdimitriou's games against nature. we prove that in spite of their analogy with the polynomial time hierarchy, the finite levels of this hierarchy collapse to am=am(2). using a combinatorial lemma on finite groups [be], we construct a game by which the nondeterministic player (merlin) is able to convince the random player (arthur) about the relation [g]=n provided arthur trusts conclusions based on statistical evidence (such as a slowly- strassen type "proof" of primality).  one can prove that am consists precisely of those languages which belong to npb for almost every oracle b.  our hierarchy has an interesting, still unclarified relation to another hierarchy, obtained by removing the central ingredient from the user vs. expert games of goldwasser, micali and rackoff.  l babai
the activity of a variable and its relation to decision trees  the construction of sequential testing procedures from functions of discrete arguments is a common problem in switching theory, software engineering, pattern recognition, and management. the concept of the activity of an argument is introduced, and a theorem is proved which relates it to the expected testing cost of the most general type of decision trees. this result is then extended to trees constructed from relations on finite sets and to decision procedures with cycles. these results are used, in turn, as the basis for a fast heuristic selection rule for constructing testing procedures. finally, some bounds on the performance of the selection rule are developed.  b. e. moret m. thomason and r. c. gonzalez
enumerating order types for small sets with applications  order types are a means to characterize the combinatorial properties of a finite point configuration. in particular, the crossing properties of all straight-line segments spanned by an planar $n$-point set are reflected by its order type. we establish a complete and reliable data base for all possible order types of size $n=10$ or less. the data base includes a realizing point set for each order type in small integer grid representation. to our knowledge, no such project has been carried out before.  we substantiate the usefulness of our data base by applying it to several problems in computational and combinatorial geometry. problems concerning triangulations, simple polygonalizations, complete geometric graphs, and $k$-sets are addressed. this list of possible applications is not meant to be exhaustive. we believe our data base to be of value to many researchers who wish to examine their conjectures on small point configurations.  oswin aichholzer franz aurenhammer hannes krasser
pac-learnability of determinate logic programs  the field of inductive logic programming (ilp) is concerned with inducing logic programs from examples in the presence of background knowledge. this paper defines the ilp problem, and describes the various syntactic restrictions that are commonly used for learning first-order representations. we then derive some positive results concerning the learnability of these restricted classes of logic programs, by reduction to a standard propositional learning problem. more specifically, k-clause predicate definitions consisting of determinate, function-free, non-recursve horn clauses with variables of bounded depth are polynomially learnable under simple distributions. similarly, recursive k-clause definitions are polynomially learnable under simple distributions if we allow existential and membership queries about the target concept.  saso dzeroski stephen muggleton stuart russell
bandwidth-based lower bounds on slowdown for efficient emulations of fixed- connection networks  this paper presents a new method for obtaining lower bounds on the slowdown of efficient emulations between network machines based on their communication bandwidth. the proofs measure the communication complexity of a message pattern by viewing its graph as a network machine and measuring the communication bandwidth β. this approach yields an intuitive lower bound on the time to route a communication pattern represented by multigraph c on a host machine h (with uniform load) as t ≥ (β(c)/β(h)), and thus a lower bound on the slowdown of emulating guest machine g on host h as the ratio of their communication bandwidths.  clyde p. kruskal kevin j. rappoport
efficient construction of lr(k) states and tables  a new method for building lr(k) states and parsing tables is presented. the method aims at giving a feasible construction of a collection of lr(k) parsing tables, especially when k > 1\\. for nontrivial grammars. to this purpose, the algorithm first attempts to build a set of normal states for the given grammar, each one associated to a single parsing action in {accept, reduce, shift}. when such an action cannot be uniquely determined, that is, when up to k input symbols have to be examined (inadequacy), further states, belonging to a new type, called look-ahead states, are computed. the action associated with inadequate states is a new parsing action, look. states are built without actual computation of the firstk and effk functions; that is, nonterminals are kept in the context string of items composing each state, and their expansion to terminals is deferred until indispensable to solve inadequacy. the aforementioned method is illustrated; then the canonical collection of states and the canonical tables are compared with those obtained from the proposed method. a sufficient condition is stated, by which the size of parsing tables, obtained by applying this new method, is smaller than that of canonical tables. experimental results show that such a condition is verified by the grammars of several programming languagues and that significant speed is gained by avoiding the computation of the firstk function.  m. anicona g. dodero v. gianuzzi m. morgavi
optimal bounds for decision problems on the crcw pram  optimal (log n/log log n) lower bounds on the time for crcw prams with polynomially bounded numbers of processors or memory cells to compute parity and a number of related problems are proven. a strict time hierarchy of explicit boolean functions of n bits on such machines that holds up to (log n/log log n) time is also exhibited. that is, for every time bound t within this range a function is exhibited that can be easily computed using polynomial resources in time t but requires more than polynomial resources to be computed in time t \\- 1. finally, it is shown that almost all boolean functions of n bits require log n \\- log log n \\+ (1) time when the number of processors is at most polynomial in n. the bounds do not place restrictions on the uniformity of the algorithms nor on the instruction sets of the machines.  paul beame johan hastad
sparse dynamic programming i: linear cost functions  dynamic programming solutions to a number of different recurrence equations for sequence comparison and for rna secondary structure prediction 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 for these problems are given, when the weight functions used in the recurrences are taken to be linear. the time complexity of the 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
the strong exponential hierarchy collapses  the polynomial hierarchy, composed of the levels p, np, pnp, npnp, etc., plays a central role in classifying the complexity of feasible computations. it is not known whether the polynomial hierarchy collapses.  we resolve the question of collapse for an exponential-time analogue of the polynomial-time hierarchy. composed of the levels e (i.e., c dtime[2cn]), ne, pne, npne, etc., the strong exponential hierarchy collapses to its Δ2 level. e pne = npne npnpne *** our proof stresses the use of partial census information and the exploitation of nondeterminism.  extending our techniques, we also derive new quantitative relativization results. we show that if the (weak) exponential hierarchy's Δj+1 and j+1 levels, respectively e p ;j and ne pj, do separate, this is due to the large number of queries ne makes to its j database.1  our technique provide a successful method of proving the collapse of certain complexity classes.  l. a. hemachandra
stabbing and ray shooting in 3 dimensional space  in this paper we consider the following problems: given a set t of triangles in 3-space, with |t| = n,  answer the query "given a line l, does l stab the set of triangles?" (query problem).  find whether a stabbing line exists for the set of triangles (existence problem).  given a ray  , which is the first triangle in t hit by  ?  the following results are shown.  there is an (n3) lower bound on the descriptive complexity of the set of all stabbers for a set of triangles.  the existence problem for triangles on a set of planes with g different plane inclinations can be solved in  (2n2 log n) time (theorem 2).  the query problem is solvable in quasiquadratic  (n2+ε) preprocessing and storage and logarithmic  (log n) query time (theorem 4).  if we are given m rays we can answer ray shooting queries in  (m5 /6-δ n5/6+5δ log2 n \\+ m log2 n \\+ n log n log m) randomized expected time and  (m \\+ n) space (theorem 5).  in time  ((n+m)5/3+4δ) it is possible to decide whether two non convex polyhedra of complexity m and n intersect (corollary 1).  given m rays and n axis- oriented boxes we can answer ray shooting queries in randomized expected time  (m3 /4-δ n3/4+3δ log4 n \\+ m log4 n \\+ n log n log m) and  (m \\+ n) space (theorem 6).  marco pellegrini
an interval logic for higher-level temporal reasoning  during the last several years, we have explored temporal logic as a framework for specifying and reasoning about concurrent programs, distributed systems, and communications protocols. previous papers[schwartz/melliar-smith81, 82, vogt82a,b] report on our efforts using temporal reasoning primitives to express very high-level abstract requirements that a program or system is to satisfy. based on our experiences with those primitives, we have developed an interval logic more suitable for expressing higher-level temporal properties.  richard l. schwartz p. m. melliar-smith friedrich h. vogt
polynomial time inference of a subclass of context-free transformations  this paper deals with a class of prolog programs, called context-free term transformations (ctf). we present a polynomial time algorithm to identify a subclass of cft, whose program consists of at most two clauses, from positive data; the algorithm uses 2-mmg (2-minimal multiple generalization) algorithm, which is natural extension of plotkin's least generalization algorithm, to reconstruct the pair of heads of the unknown program. using this algorithm, we show the consistent and conservative polynomial time identifiability of the class of tree languages defined by cftfbuniq together with tree languages defined by pairs of two tree patterns, both of which are proper subclasses of cft, in the limit from positive data.  hiroki arimura hiroki ishizaka takeshi shinohara
sharing the load of logic-program evaluation  we propose a method of parallelizing bottom-up-evaluation of logic programs. the method does not introduce interprocess communication, or synchronization overhead. we demonstrate that it can be applied when evaluating several classes of logic programs, e.g., the class of linear single rule programs. this extends the work reported in [ws] by significantly expanding the classes of logic programs that can be evaluated in parallel. we also prove that there are classes of programs to which the parallelization method cannot be applied.  o. wolfson
some structural properties of polynomial reducibilities and sets in np  in this abstract and discussion of forthcoming papers, we will be concerned with variations on a common theme: without assuming a solution to p vs np, what can one say of a general nature that relates structural properties of general classes of sets in np to reducibilities among these sets? by "structural" we mean, in ways that will become clearer as we proceed, properties which arise from general definitions rather than properties which may arise from a perhaps more "natural" computational point of view. although quite a bit is known about such questions relative to oracles or relative to the assumption that p @@@@ np, in so far as possible we wish to obtain absolute results; that is results which are about sets in np (not relativized) and which can be obtained without assuming a solution to p vs np. in a final section summarizing our results we will make some general comments about the historical antecedents and possible future significance of this approach.  paul young
church-rosser thue systems and formal languages  since about 1971, much research has been done on thue systems that have properties that ensure viable and efficient computation. the strongest of these is the church-rosser property, which states that two equivalent strings can each be brought to a unique canonical form by a sequence of length- reducing rules. in this paper three ways in which formal languages can be defined by thue systems with this property are studied, and some general results about the three families of languages so determined are studied.  robert mcnaughton paliath narendran friedrich otto
a strassen-newton algorithm for high-speed parallelizable matrix inversion  this paper describes techniques to compute matrix inverses by means of algorithms that are highly suited to massively parallel computation. in contrast, conventional techniques such as pivoted gaussian elimination and lu decomposition are efficient only on vector computers or fairly low-level parallel systems.  these techniques are based on an algorithm suggested by strassen in 1969. variations of this scheme employ matrix newton iterations and other methods to improve the numerical stability while at the same time preserving a very high level of parallelism. one-processor cray-2 implementations of these schemes range from one that is up to 55% faster than a conventional library routine to one that, while slower than a library routine, achieves excellent numerical stability.  the problem of computing the solution to a single set of linear equations is discussed, and it is shown that shown that this problem can also be solved efficiently using these techniques.  d. h. bailey h. r. p. gerguson
generosity helps, or an 11 - competitive algorithm for three servers  we propose a new algorithm called equipoise for the k-server problem, and we prove that it is 2-competitive for two servers and 11-competitive for three servers. for k=3, this is a tremendous improvement over previously known constants. the algorithm uses several techniques for designing on-line algorithms - convex hulls, work functions and forgiveness.  the results presented in this paper were earlier announced at the dimacs workshop on on-line algorithms [8].  marek chrobak lawrence l. larmore
simple and efficient bounded concurrent timestamping and the traceable use abstraction  in a timestamping system, processors repeatedly choose timestamps so that the order of the timestamps obtained reflects the real-time order in which they were requested. concurrent timestamping systems permit requests by multiple processors to be issued concurrently; in bounded timestamping systems the sizes of the timestamps and the size and number of shared variables are bounded. an algorithm is wait-free if there exists an a priori bound on the number of steps a processor must take in order to make progress, independent of the action or inaction of other processors. letting n denote the number of procesors, we construct a simple wait-free bounded concurrent timestamping system requiring o(n) steps (accesses to shared memory) for a processor to read the current timestamps and determine the order among them, and o(n) steps to generate a timestamp, independent of the actions of the other processors. in addition, we introduce and implement the traceable use abstraction, a new primitive providing "inventory control" over values introduced by processors in the course of an algorithm execution. this abstraction has proved to be of great value in converting unbounded algorithms to bounded ones {attiya and rachman 1998; dwork et al. 1992; 1993].  cynthia dwork orli waarts
on dynamic voronoi diagrams and the minimum hausdorff distance for point sets under euclidean motion in the plane  we show that the dynamic voronoi diagram of k sets of points in the plane, where each set consists of m points moving rigidly, has complexity o(n2k2< ;/supscrpt>λs_(k)) for some fixed s, where λ s(n) is the maximum length of a (n, s) davenport-schinzel sequence. this improves the result of aonuma et al., who show an upper bound of o(n3k4 log* k) for the complexity of such voronoi diagrams. we then apply this result to the problem of finding the minimum hausdorff distance between two point sets in the plane under euclidean motion. we show that this distance can be computed in time o((m \\+ n)6 log (mn)), where the two sets contain m and n points respectively.  daniel p. huttenlocher klara kedem jon m. kleinberg