We consider computational problems concerning algebras over finite fields. In particular, we propose an algorithm for finding a small generating set for the multiplicative group of GF(p)[x]/F, where p is a prime number and F in GF(p)[x] is an arbitrary polynomial. Based on this result, a new set of expander graphs can be explicitly constructed. In addition, we present algorithms for basis construction and decomposition of a given element with respect to the basis.

It is well known that every rational integer has a finite or periodic p-adic expansion. In this paper a more general notion of Þ-adic expansion is introduced for algebraic integers, where given a number field K and a principal prime ideal Þ in K, a different choice of generator for Þ is allowed in each stage of the expansion. With the notion of Þ-adic expansion, we prove that there is always a finite or periodic Þ-adic expansion for every algebraic integer. Moreover, we prove a bound on the periodicity of the Þ-adic expansion that depends only on the number field K and the prime ideal Þ. The proof yields an algorithm for constructing such a Þ-adic expansion for elements in the ring O of algebraic integers of K, through finding an approximation to the closest vector on the lattice spanned by the unit group of O.

Self-assembly is the ubiquitous process by which simple objects autonomously assemble into intricate complexes. It has been suggested that intricate self-assembly processes will ultimately be used in circuit fabrication, nano-robotics, DNA computation, and amorphous computing. In this paper, we study two combinatorial optimization problems related to efficient self-assembly of shapes in the Tile Assembly Model of self-assembly proposed by Rothemund and Winfree [18]. The first is the Minimum Tile Set Problem, where the goal is to find the smallest tile system that uniquely produces a given shape. The second is the Tile Concentrations Problem, where the goal is to decide on the relative concentrations of different types of tiles so that a tile system assembles as quickly as possible. The first problem is akin to finding optimum program size, and the second to finding optimum running time for a "program" to assemble the shape.Self-assembly is the ubiquitous process by which simple objects autonomously assemble into intricate complexes. It has been suggested that intricate self-assembly processes will ultimately be used in circuit fabrication, nano-robotics, DNA computation, and amorphous computing. In this paper, we study two combinatorial optimization problems related to efficient self-assembly of shapes in the Tile Assembly Model of self-assembly proposed by Rothemund and Winfree [18]. The first is the Minimum Tile Set Problem, where the goal is to find the smallest tile system that uniquely produces a given shape. The second is the Tile Concentrations Problem, where the goal is to decide on the relative concentrations of different types of tiles so that a tile system assembles as quickly as possible. The first problem is akin to finding optimum program size, and the second to finding optimum running time for a "program" to assemble the shape.We prove that the first problem is NP-complete in general, and polynomial time solvable on trees and squares. In order to prove that the problem is in NP, we present a polynomial time algorithm to verify whether a given tile system uniquely produces a given shape. This algorithm is analogous to a program verifier for traditional computational systems, and may well be of independent interest. For the second problem, we present a polynomial time $O(\log n)$-approximation algorithm that works for a large class of tile systems that we call partial order systems.

Recently Rothemund and Winfree [6] have considered the program size complexity of constructing squares by self-assembly. Here, we consider the time complexity of such constructions using a natural generalization of the Tile Assembly Model defined in [6]. In the generalized model, the Rothemund-Winfree construction of n \times n squares requires time Θ(n log n) and program size Θ(log n). We present a new construction for assembling n \times n squares which uses optimal time Θ(n) and program size Θ(\frac{log n}{log log n}). This program size is also optimal since it matches the bound dictated by Kolmogorov complexity. Our improved time is achieved by demonstrating a set of tiles for parallel self-assembly of binary counters. Our improved program size is achieved by demonstrating that self-assembling systems can compute changes in the base representation of numbers. Self-assembly is emerging as a useful paradigm for computation. In addition the development of a computational theory of self-assembly promises to provide a new conduit by which results and methods of theoretical computer science might be applied to problems of interest in biology and the physical sciences.

Article A black box approach to the algebraic set decomposition problem Share on Authors: Ming-Deh A. Huang Department of Computer Science, University of Southern California, Los Angeles, CA Department of Computer Science, University of Southern California, Los Angeles, CAView Profile , Ashwin J. Rao Department of Computer Science, University of Southern California, Los Angeles, CA Department of Computer Science, University of Southern California, Los Angeles, CAView Profile Authors Info & Claims STOC '98: Proceedings of the thirtieth annual ACM symposium on Theory of computingMay 1998 Pages 497–506https://doi.org/10.1145/276698.276863Published:23 May 1998 0citation514DownloadsMetricsTotal Citations0Total Downloads514Last 12 Months4Last 6 weeks0 Get Citation AlertsNew Citation Alert added!This alert has been successfully added and will be sent to:You will be notified whenever a record that you have chosen has been cited.To manage your alert preferences, click on the button below.Manage my AlertsNew Citation Alert!Please log in to your account Save to BinderSave to BinderCreate a New BinderNameCancelCreateExport CitationPublisher SiteGet Access

In this paper some theoretical and (potentially) practical aspects of quantum computing are considered. Using the tools of transcendental number theory it is demonstrated that quantum Turing machines (QTM) with rational amplitudes are sufficient to define the class of bounded error quantum polynomial time (BQP) introduced by Bernstein and Vazirani [Proc. 25th ACM Symposium on Theory of Computation, 1993, pp. 11--20, SIAM J. Comput., 26 (1997), pp. 1277--1339]. On the other hand, if quantum Turing machines are allowed unrestricted amplitudes (i.e., arbitrary complex amplitudes), then the corresponding BQP class has uncountable cardinality and contains sets of all Turing degrees. In contrast, allowing unrestricted amplitudes does not increase the power of computation for error-free quantum polynomial time (EQP). Moreover, with unrestricted amplitudes, BQP is not equal to EQP. The relationship between quantum complexity classes and classical complexity classes is also investigated. It is shown that when quantum Turing machines are restricted to have transition amplitudes which are algebraic numbers, BQP, EQP, and nondeterministic quantum polynomial time (NQP) are all contained in PP, hence in ${\rm P}^{#{\rm P}}$ and PSPACE. A potentially practical issue of designing "machine independent" quantum programs is also addressed. A single ("almost universal") quantum algorithm based on Shor's method for factoring integers is developed which would run correctly on almost all quantum computers, even if the underlying unitary transformations are unknown to the programmer and the device builder.

We consider the following polynomial congruences problem: given a prime p, and a set of polynomials f/sub 1/,...,f/sub m//spl isin/F/sub p/[x/sub 1/,...,x/sub n/] of total degree at most d, solve the system f/sub 1/=...=f/sub m/=0 for solution(s) in F/sub p//sup n/. We give a randomized algorithm for the decision version of this problem. When the system has F/sub p/-rational solutions our algorithm finds one of them as well as an approximation of the total number of such solutions. For a fixed number of variables, the algorithm runs in random polynomial time with parallel complexity poly-logarithmic in d, m and p, using a polynomial number of processors. As an essential step of the algorithm, we also formulate an algebraic homotopy method for extracting components of all dimensions of an algebraic set. The method is efficiently parallelizable.

We consider the problem of counting the number of points on a plane curve, given by a homogeneous polynomial F/spl isin/F/sub p/[x, y, z], which is rational over the ground field F/sub p/. More precisely, we show that if we are given a projective plane curve C of degree n, and if C has only ordinary multiple points, then one can compute the number of F/sub p/-rational points on C in randomized time (log p)/sup /spl Delta// where /spl Delta/=(degF)/sup O(1/). The complexity of this construction improves previously known bounds for this problem by at least an order of magnitude.>

Several computational problems concerning the construction of rational functions and intersecting curves over a given curve are studied. The first problem is to construct a rational function with prescribed zeros and poles over a given curve. More precisely, let C be a smooth projective curve and assume as given an affine plane model F(x,y)=0 for C, a finite set of points P/sub i/=(X/sub i/, Y/sub i/) with F (X/sub i/, Y/sub i/)=0 and natural numbers n/sub i/, and a finite set of points Q/sub i/=(X/sub j/, Y/sub j/) with F(X/sub j/, Y/sub j/)=0 and natural numbers m/sub j/. The problem is to decide whether there is a rational function which has zeros at each point P/sub i/ of order n/sub i/, poles at each Q/sub j/ of order m/sub j/, and no zeros or poles anywhere else on C. One would also like to construct such a rational function if one exists. An efficient algorithm for solving this problem when the given plane curve has only ordinary multiple points is given.>

The notion of pure nested radicals and its field-theoretic counterpart, pure root extensions, are defined and used for investigating exact radical solutions.>

This paper explores the idea of using simple secure and verifiable distributed protocols as building blocks for ccnstructing more complicated protocols.A notion of reduction among multi-party problems is introduced and formally defined.The very simple and natural distributed sum problem is shown to be universal under the notion of reduction.An optimally secure, verifiable, and robust protocol for the distributed sum problem and the closely related election problem is presented.The distributed sum protocol together with the proof of reduction from the multi-party problems yields an efficient systematic method for the automatic generation of secure and verifiable protocols for all multi-party problems.

This paper is the first in a sequence of papers which will prove the existence of a random polynomial time algorithm for the set of primes. The techniques used are from arithmetic algebraic geometry and to a lesser extent algebraic and analytic number theory. The result complements the well known result of Strassen and Soloway that there exists a random polynomial time algorithm for the set of composites.

We present a systematic approach for solving graph problems under the network models. We illustrate this approach on the mesh-of-trees networks. It is known that under the CREW PRAM model, when a undirected graph of n nodes is given by an n by n adjacency matrix, the problems of finding minimum spanning forest, connected components, and biconnected components can all be solved with optimal speedup when the number of processors p ≤ n2/log2n. We show that for these problems, the same optimal speedup can be achieved even under the much more restrictive mesh-of-trees network. We also show that for the problem of finding directed spanning forest of arbitrary digraphs and the problem of testing strong connectivity of 1-reachable digraphs, near-optimal speedup can be achieved.

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 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 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.

Based on Kummer Theorem, we study the deterministic complexity of two factorization problems: polynomial factorization over finite fields and prime factorization in algebraic number fields. We show that factoring polynomials of degree n in Fp[x], with p prime, is polynimially equivalent to factoring p in algebraic number field of extension degree n over Q, where p is “regular” with respect to the generating polynomials of the number fields. Part of the proof also yields an efficient polynomial time algorithm for computing the factorization pattern. Number theoretical methods are then developed to solve two important kinds of polynomials:φn(x) mod p where φn is the n-th cyclotomic polynomial, and xn. - α mod p where α ε N. We show that when Extended Riemann Hypothesis is assumed, all the roots of both kinds of polynomials in Fp can be found efficiently in time polynomial in n and logp. As α consequence, when p χ 1(n), factorization of p in the n-th cyclotomic field can be computed in polynomial time. The result on finding all roots of xn χ α(p) extends α result of Adleman, Menders, and Miller, which states that the least root of xn χ α(p) can be found in polynomial time, when Extended Riemann Hypothesis is assumed.