waashk/acm huggingface dataset:
riemann hypothesis and finding roots over finite fields  it is shown that assuming generalized riemann hypothesis, the roots of (x) = o mod p, where p is a prime and f(x) is an integral abilene polynomial can be found in deterministic polynomial time. the method developed for solving this problem is also applied to prime decomposition in abelian number fields, and the following result is obtained: assuming generalized riemann hypotheses, for abelian number fields k of finite extension degree over the rational number field q, the decomposition pattern of a prime p in k, i.e. the ramification index and the residue class degree, can be computed in deterministic polynomial time, providing p does not divide the extension degree of k over q. it is also shown, as a theorem fundamental to our algorithm, that for q, p prime and m the order of p mod q, there is a q-th nonresidue in the finite field &amp;l; t;italic>fpm that can be written as ao \\+ a1w \\+ … \+ am-1wm-1, where |a1| ≤ cq2 log2(pq), c is an absolute effectively computable constant, and 1, w, …, wm-1 form a basis of fpm< ;/supscrpt> over fp. more explicitly, w is a root of the q-th cyclotomic polynomial over fp. this result partially generalizes, to finite field extensions over fp, a classical result in number theory stating that assuming generalized riemann hypothesis, the least q-th nonresidue mod p for p,q prime and q dividing p \\- t is bounded by c log2p, where c is an absolute, effectively computable constant.  m-d a huang
on rational solution of the state equation of a finite automation (abstract only)  in this paper we contribute some interesting results on the state space approach following the work of lee [2], yang and huang [1].  we prove that the necessary and sufficient condition for the state equation of a finite automaton m to have a rational solution is that the lexicographic godel numbers of the strings belonging to each of the end-sets of m form an ultimately periodic set.  a state space approach was proposed by lee[2] as an alternative way to analyze finite automata. the approach is based on the transformation of a set of words into a formal power series over the field of integers modulo 2 and also obtaining a state equation in some linear space associated with the automaton. some useful algorithms associated with the state space approach were discussed by yang and huang[1] along with a condition for the state equation to have a rational solution when the automaton has either 4 or 8 states.  the question of existence of a rational solution of a state equation is certainly an interesting one and it is not difficult to see that the condition given by yang and huang [1] is by no means necessary even for automata with only 4 states.  the main objective of our present work is to give the necessary and sufficient condition for the state equation of an automaton to have a rational solution and thus provide a complete answer to the question left open by yang and huang [1]. we also show that the condition obtained in [1] is a special case of our theorem.  furthermore, we discuss a practical method for determining whether the state equation of an automaton has a rational solution and also how to obtain the rational solution in case it exists.  r. chaudhuri h. höft
on the space complexity of randomized synchronization  the "waite-free hierarchy" provides a classification of multiprocessor synchronization primitives based on the values of n for which there are deterministic wait-free implementations of n-process consensus using instances of these objects and read-write registers. in a randomized wait-free setting, this classification is degenerate, since n-process consensus can be solved using only o(n) read-write registers.  in this paper, we propose a classification of synchronization primitives based on the space complexity of randomized solutions to n-process consensus. a historyless object, such as a read-write register, a swap register, or a test&amp;set; register, is an object whose state depends only on the lost nontrivial operation thate was applied to it. we show that, using historyless objects, (n object instances are necessary to solve n-process consensus. this lower bound holds even if the objects have unbounded size and the termination requirement is nondeterministic solo termination, a property strictly weaker than randomized wait-freedom.  we then use this result to related the randomized space complexity of basic multiprocessor synchronization primitives such as shared counters, fetch&amp;add; registers, and compare&amp;swap; registers. viewed collectively, our results imply that there is a separation based on space complexity for synchronization primitives in randomized computation, and that this separation differs from that implied by the deterministic "wait-free hierarchy."  faith fich maurice herlihy nir shavit
imperfect random sources and discrete controlled processes  we consider a simple model for a class of discrete control processes, motivated in part by recent work about the behavior of imperfect random sources in computer algorithms. the process produces a string of characters from {0, 1} of length n and is a "success" or "failure" depending on whether the string produced belongs to a prespecified set l. in an uninfluenced process each character is chosen by a fair coin toss, and hence the probability of success is |l|/2n. we are interested in the effect on the probability of success in the presence of a player (controller) who can intervene in the process by specifying the value of certain characters in the string. we answer the following questions in both worst and average case: (1) how much can the player increase the probability of success given a fixed number of interventions? (2) in terms of |l| what is the expected number of interventions needed to guarantee success? in particular our results imply that if |l|/2n = 1/w(n) where w(n) tends to infinity with n (so the probability of success with no interventions is o(1)) then with ( nlog&amp;l; t;italic>w(n)) interventions the probability of success is 1-o(1).  our main results and the proof techniques are related to a well-known theorem of kruskal, katona, and harper in extremal set theory.  d. lichtenstein n. linial m. saks
some optimal inapproximability results we prove optimal, up to an arbitrary ε > 0, inapproximability results for max-e _k_-sat for _k_ ≥ 3, maximizing the number of satisfied linear equations in an over-determined system of linear equations modulo a prime _p_ and set splitting. as a consequence of these results we get improved lower bounds for the efficient approximability of many optimization problems studied previously. in particular, for max-e2-sat, max- cut, max-di-cut, and vertex cover. johan håstad
acceptance trees  a simple model, at, for nondeterministic machines is presented which is based on certain types of trees. a set of operations, , is defined over at and it is shown to be completely characterized by a set of inequations over . at is used to define the denotational semantics of a language for defining nondeterministic machines. the significance of the model is demonstrated by showing that this semantics reflects an intuitive operational semantics of machines based on the idea that machines should only be differentiated if there is some experiment that differentiates between them.  m. hennessy
toward a complete transformational toolkit for compilers  pim is an equational logic designed to function as a "transformational toolkit" for compilers and other programming tools that analyze and manipulate imperative languages. it has been applied to such problems as program slicing, symbolic evaluation, conditional constant propagation, and dependence analysis. pim consists of the untyped lambda calculus extended with an algebraic data type that characterizes the behavior of lazy stores and generalized conditionals. a graph form of pim terms is by design closely related to several intermediate representations commonly used in optimizing compilers. in this article, we show that pim's core algebraic component, pimt, possesses a complete equational axiomatization (under the assumption of certain reasonable restrictions on term formation). this has the practical consequence of guaranteeing that every semantics-preserving transformation on a program representable in pimt can be derived by application of pimt rules. we systematically derive the complete pimt logic as the culmination of a sequence of increasingly powerful equational systems starting from a straightforward "interpreter" for closed pimt terms. this work is an intermediate step in a larger program to develop a set of well- founded tools for manipulation of imperative programs by compilers and other systems that perform program analysis.  j. a. bergstra t. b. dinesh j. field j. heering
optimal bounds for decision problems on the crcw pram  we prove optimal (log n/log log n) lower bounds on the time for crcw pram's with polynomially bounded numbers of processors or memory cells to compute parity and a number of related problems. we also exhibit a strict time hierarchy of explicit boolean functions of n bits on such machines which holds up to  (log n/log log n) time. furthermore, we show 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. our bounds do not place restrictions on the uniformity of the algorithms nor on the instruction sets of the machines.  p. beame j. hastad
factorization over finitely generated fields  this paper considers the problem of factoring polynomials over a variety of domains. we first describe the current methods of factoring polynomials over the integers, and extend them to the integers mod p. we then consider the problem of factoring over algebraic domains. having produced several negative results, showing that, if the domain is not properly specified, then the problem is insoluble, we then show that, for a properly specified finitely generated extension of the rationals or the integers mod p, the problem is soluble. we conclude by discussing the problems of factoring over algebraic closures.  james h. davenport barry m. trager
an optimal parallel algorithm for the maximal element problem (abstract)  given a set (p1, p2, …, pn) of n points in a plane, a point pi dominates another point pj iff x (pi) ≥ x(pj) and y (pi) ≥ y(pj) where x (p) and y (p) denote the coordinates of a point p. our problem is to find the points which are dominated by no other point. these points are called maximal elements. in this abstract we suggest an  (log n) parallel algorithm with  (n) processors in the erew parallel model which is weaker than crew. (note that most parallel algorithms in the literature use the power of crew pram model.) the main idea is to reduce the problem to the parallel prefix problem [2]. our algorithm runs as follows: first, from p = {pl, …, pn}, find a subset p' = {p1 …, pm }, where each point pi is dominated by no other point having the same x -coordinate aspi. this can be done in  (log n) time with  (n) processors in the erew model applying the parallel sort algorithm by [1]. next sort p' according to the x -coordinate of each point and store each y -coordinate in an array a in the increasing order of the corresponding x -coordinate. assume that the y -coordinate of pi is stored in a [i ] for i = 1, 2, …, m. then for each a [i ], find an index j such that i ≤ j and a [j] ≥ a [k ] for each i ≤ k ≤ m. if i = j, then pi is one of the maximal elements. this can be done in (log n) time with  (n) processors on the erew parallel model by applying a parallel prefix algorithm |2|.  c. rhee s. k. dhall s. lakshmivarahan
an algebra for data flow anomaly detection  an algebra a is developed that is specialized for the detection of data flow anomalies by interpreting the regular expression for the paths in a program as an a expression. two methods are subsequently presented that use a but do not require the explicit computation of the regular expression for the paths. one method is based on the prime program decomposition. the other is based upon the iterative algorithms of global data flow analysis. in addition the use of the algebra to get better warning messages than just the detection of anomalies is presented.  ira r. forman
definability in dynamic logic  we study the expressive power of various versions of dynamic logic and compare them with each other as well as with standard languages in the logical literature. one version of dynamic logic is equivalent to the infinitary logic lckω1 ;ω, but regular dynamic logic is strictly less expressive. in particular, the ordinals ωω and ω ω.2 are indistinguishable by formulas of regular dynamic logic.  albert r. meyer rohit parikh
a time-randomness tradeoff for oblivious routing  three parameters characterize the performance of a probabilistic algorithm: t, the runtime of the algorithm; q, the probability that the algorithm fails to complete the computation in the first t steps and r, the amount of randomness used by the algorithm, measured by the entropy of its random source.  we present a tight tradeoff between these three parameters for the problem of oblivious packet routing on n-vertex bounded- degree networks. we prove a (1 - q) log n/t \\- log q \\-  (1) lower bound for the entropy of a random source of any oblivious packet routing algorithm that routes an arbitrary permutation in t steps with probability 1 - q. we show that this lower bound is almost optimal by proving the existence, for every e3 log n ≤ t ≤ n1/2, of an oblivious algorithm that terminates in t steps with probability 1 - q and uses (1-q+ (1))logn/t-logq independent random bits.  we complement this result with an explicit construction of a family of oblivious algorithms that use less than a factor of log n more random bits than the optimal algorithm achieving the same run-time.  danny krizanc david peleg eli upfal
theory of neuromata  a finite automaton---the so-called neuromaton, realized by a finite discrete recurrent neural network, working in parallel computation mode, is considered. both the size of neuromata (i.e., the number of neurons) and their descriptional complexity (i.e., the number of bits in the neuromaton representation) are studied. it is proved that a constraint time delay of the neuromaton output does not play a role within a polynomial descriptional complexity. it is shown that any regular language given by a regular expression of length n is recognized by a neuromaton with (n) neurons. further, it is proved that this network size is, in the worst case, optimal. on the other hand, generally there is not an equivalent polynomial length regular expression for a given neuromaton. then, two specialized constructions of neural acceptors of the optimal descriptional complexity (n) for a single n-bit string recognition are described. they both require o(n1/2) neurons and either o(n) connections with constant weights or o(n1/2) edges with weights of the  on hopfield condition stating when a regular language is a hopfield language, is formulated. a construction of a hopfield neuromaton is presented for a regular language satisfying the hopfield condition. the class of hopfield languages is shown to be closed under union, intersection, concatenation and complement, and it is not closed under iteration. finally, the problem whether a regular language given by a neuromaton (or by a hopfield acceptor) is nonempty, is proved to be pspace- complete. as a consequence, the same result for a neuromaton equivalence problem is achieved.  jiri sima jiri wiedermann
typed representation of objects by functions  a systematic representation of objects grouped into types by constructions similar to the composition of sets in mathematics is proposed. the representation is by lambda expressions, which supports the representation of objects from function spaces. the representation is related to a rather conventional language of type descriptions in a way that is believed to be new. ordinary control- expressions (i.e.,case- and let-expressions) are derived from the proposed representation.  j. steensgaard-madsen
minimal degrees for polynomial reducibilities  the existence of minimal degrees is investigated for several polynomial reducibilities. it is shown that no set has minimal degree with respect to polynomial many-one or turing reducibility. this extends a result of ladner in which only recursive sets are considered. a polynomial reducibility ≤< italic>ht< /italic> is defined. this reducibility is a strengthening of polynomial turing reducibility, and its properties relate to the p = ? np question. for this new reducibility, a set of minimal degree is constructed under the assumption that p = np. however, the set constructed is nonrecursive, and it is shown that no recursive set is of minimal ≤ h ;t degree.  steven homer
efficient simulation of finite automata by neural nets  let k(m) denote the smallest number with the property that every m-state finite automaton can be built as a neural net using k(m) or fewer neurons. a counting argument shows that k(m) is at least ((m log m)1/3), and a construction shows that k(m) is at most < italic>o(m3/4&amp;l; t;/supscrpt>). the counting argument and the construction allow neural nets with arbitrarily complex local structure and thus may require neurons that themselves amount to complicated networks. mild, and in practical situations almost necessary, constraints on the local structure of the network give, again by a counting argument and a construction, lower and upper bounds for k(m) that are both linear in m.  noga alon a. k. dewdney teunis j. ott
tradeoffs between communication and space  this paper initiates the study of communication complexity when the processors have limited work space. the following tradeoffs between number c of communications steps and space s are proved:  for multiplying two n × n matrices in the arithmetic model with two-way communication, cs = (n).  for convolution of two degree n polynomials in the arithmetic model with two- way communication, cs = (n2).  & lt;/item>  for multiplying an n × n matrix by an n-vector in the boolean model with one- way communication, cs = (n2).  in contrast, the discrete fourier transform and sorting can be accomplished in (n) communication steps and  (log n) space simultaneously, and the search problems of karchmer and wigderson associated with any language in nck can be solved in  (logk< ;/supscrpt> n) communication steps and  (logk< ;/supscrpt> n) space simultaneously.  t. lam p. tiwari m. tompa
on playing "twenty questions" with a liar  motivated by the problem of searching in the presence of adversarial errors, we consider a version of the game "twenty questions" played on the set {0,…,n-1} where the player giving answers may lie in her answers. the questioner is allowed q questions and the responder may lie in upto [rq] of the answers, for some fixed and previously known fraction r. under three different models of this game and for two different question classes, we give precise conditions (i.e. tight bounds on r and, in most cases, optimal bounds on q under which the questioner has a winning strategy in the game.  aditi dhagat peter gács peter winkler
lower bounds for algebraic computation trees  a topological method is given for obtaining lower bounds for the height of algebraic computation trees, and algebraic decision trees. using this method we are able to generalize, and present in a uniform and easy way, almost all the known nonlinear lower bounds for algebraic computations. applying the method to decision trees we extend all the apparently known lower bounds for linear decision trees to bounded degree algebraic decision trees, thus answering the open questions raised by steele and yao [20]. we also show how this new method can be used to establish lower bounds on the complexity of constructions with ruler and compass in plane euclidean geometry.  michael ben-or
mechanizing unity in isabelle  unity is an abstract formalism for proving properties of concurrent systems, which typically are expressed using guarded assignments [chandy and misra 1988]. unity has been mechanized in higher-order logic using isabelle, a proof assistant. safety and progress primitives, their weak forms (for the substitution axiom), and the program composition operator (union) have been formalized. to give a feel for the concrete syntax, this article presents a few extracts from the isabelle definitions andproofs. it discusses a small example, two-process mutual exclusion. a mechanical theory of unions of programs supports a degree of compositional reasoning. original work on extending program states is presented and then illustrated through a simple example involving an array of processes.  lawrence c. paulson
learnability of description logics  this paper considers the learnability of subsets of first-order logic. piror work has established two boundaries of learnability: haussler [1989] has shown that conjunctions in first-order logic cannot be learned in the valiant model, even if the form of the conjunction is highly restricted; on the other hand, valiant [1984] has shown that propositional conjunctions are learnable. in this paper, we study the learnability of the restricted first-order logics known as description logics. description logics are also subsets of predicate calculus, but are expressed using a different syntax, allowing a different set of syntactic restrictions to be explored. in this paper, we first define a simple description logic, summarize some results on its expressive power, and then analyze its learnability. it is shown that the full logic cannot be tractably learned; however, syntactic restrictions that enable tractable learning exist. the learnability results hold even if the alphabets of primitive classes and roles (over which descriptions are constructed) are infinite; our positive result thus generalizes not only the result of valiant [1984] on learning monomials to learning concepts in our (conjunctive) first order language, but also the result of blum [1990] on learning monomials over infinite attribute spaces.  william w. cohen haym hirsh
quicksort algorithms with an early exit for sorted subfiles  the quicksort algorithm is known to be one of the most efficient internal sorting techniques. quicksort has received considerable attention almost from the moment of its invention. this paper reviews some of the important improvements to quicksort that have appeared in the literature. historically, the improvements to quicksort have been in one of the following areas: (1) algorithms for determining a better pivot value, (2) algorithms that consider the size of the generated subfiles, and (3) various schemes used to partition the file. despite improvements in these areas, the worst case situation of (n2) comparisons for sorted or nearly sorted files still remains. this paper proposes a fourth research area for quicksort improvement designed to remove the worst case behavior due to sorted or nearly sorted files. during the partitioning process (using any scheme) determine if the left and right subfiles are in sorted order. this is a minor but very effective modification to the quicksort algorithm. a new quicksort algorithms, qsorte, is presented that provides an early exit for sorted subfiles. test results on randomly generated lists, nearly sorted lists, sorted and sorted lists in reverse order are given for quicksort, quickersort, bsort, qsorte and several other algorithms. results show qsorte performs just as well as quicksort for random files and in addition has (n) comparisons for sorted or nearly sorted files and (n) comparisons for sorted or nearly sorted files in reverse.  roger l. wainwright