We present a deterministic $2^{O(t)}q^{\frac{t-2}{t-1}+o(1)}$ algorithm to decide whether a univariate polynomial $f$, with $t$ monomial terms and degree $

For a linear code, deep holes are defined to be vectors that are further away from codewords than all other vectors. The problem of deciding whether a received word is a deep hole for generalized Reed-Solomon (GRS) codes is proved to be co-NP-complete by Guruswami and Vardy. For the extended Reed-Solomon codes RSq(Fq, k), a conjecture was made to classify deep holes by Cheng and Murray. Since then efforts have been made to prove the conjecture, or its various forms. In this paper, we classify deep holes completely for GRS codes RSp(D, k), where p is a prime, |D| > k ≥ (p - 1)/2. Our techniques are built on the idea of deep hole trees, and several results concerning the Erdös-Heilbronn conjecture.

We present a deterministic 2O(t)qt-2/t-1 +o(1) algorithm to decide whether a univariate polynomial f, with exactly t monomial terms and degree

Every finite field has many multiplicative generators. However, finding one in polynomial time is an important open problem. In fact, even finding elements of high order has not been solved satisfactorily. In this paper, we present an algorithm that for any positive integer c and prime power q, finding an element of order in the finite field in deterministic time (qc)O(1). We also show that there are many weak keys for the discrete logarithm problems in those fields with respect to certain bases.

Determining the minimum distance of a linear code is one of the most important problems in algorithmic coding theory. The exact version of the problem was shown to be NP-complete by Vardy. The gap version of the problem was shown to be NP-hard for any constant factor under a randomized reduction in an earlier work. It was shown in the same paper that the minimum distance problem is not approximable in randomized polynomial time to the factor 2log1-ϵnunlessNP⊆RTIME(2polylog(n)). In this paper, we derandomize the reduction and thus prove that there is no deterministic polynomial time algorithm to approximate the minimum distance to any constant factor unlessP=NP. We also prove that the minimum distance is not approximable in deterministic polynomial time to the factor 2log1-ϵnunlessNP⊆DTIME(2polylog(n)). As the main technical contribution, for any constant 2/3s, runs in timepoly(s) and constructs a codeCof lengthpoly(s) with an explicit Hamming ball of radius ρd(C), such that the projection at the firstscoordinates sends the codewords in the ball surjectively onto a linear subspace of dimensions, whered(C) denotes the minimum distance ofC. The codes are obtained by concatenating Reed-Solomon codes with Hadamard codes.

It has been proved that the maximum likelihood decoding problem of Reed-Solomon codes is NP-hard. However, the length of the code in the proof is at most polylogarithmic in the size of the alphabet. For the complexity of maximum likelihood decoding of the primitive Reed-Solomon code, whose length is one less than the size of alphabet, the only known result states that it is at least as hard as the discrete logarithm in some cases where the information rate unfortunately goes to zero. In this paper, it is proved under a well known cryptography hardness assumption that: 1) There does not exist a randomized polynomial time maximum likelihood decoder for the Reed-Solomon code family [q, k(q)]q, where k(x) is any function in Z+→ Z+computable in time xO(1)satisfying √x ≤ k(x) ≤ x - √x. 2) There does not exist a randomized polynomial time bounded-distance decoder for primitive Reed-Solomon codes at distance 2/3 + ϵ of the minimum distance for any constant 0 <; ϵ <; 1/3. In particular, this rules out the possibility of a polynomial time algorithm for maximum likelihood decoding problem of primitive Reed-Solomon codes of any rate under the assumption.

Determining the minimum distance of a linear code is one of the most important problems in algorithmic coding theory. The exact version of the problem was shown to be NP-complete in [14]. In [8], the gap version of the problem was shown to be NP-hard for any constant factor under a randomized reduction. It was shown in the same paper that the minimum distance problem is not approximable in randomized polynomial time to the factor 2log1-e n unless NP ⊆ RTIME(2polylog(n)). In this paper, we derandomize the reduction and thus prove that there is no deterministic polynomial time algorithm to approximate the minimum distance to any constant factor unless P=NP. We also prove that the minimum distance is not approximable in deterministic polynomial time to the factor 2log1-en unless NP ⊆ DTIME(2polylog(n)). As the main technical contribution, for any constant 2/3

The minimum distance is one of the most important combinatorial characterizations of a code. The maximum-likelihood decoding problem is one of the most important algorithmic problems of a code. While these problems are known to be hard for general linear codes, the techniques used to prove their hardness often rely on the construction of artificial codes. In general, much less is known about the hardness of the specific classes of natural linear codes. In this correspondence, we show that both problems are NP-hard for algebraic geometry codes. We achieve this by reducing a well-known NP-complete problem to these problems using a randomized algorithm. The family of codes in the reductions is based on elliptic curves. They have positive rates, but the alphabet sizes are exponential in the block lengths.

The zero testing and sign determination problems of real algebraic numbers of high extension degree are important in computational complexity and numerical analysis. In this paper we concentrate an sparse cyclotomic integers. Given an integer n and a sparse polynomial f(x) = Ckxe(k)+ ck-1xe(k-1)+ ... + c1xe(1)over Z, we present a deterministic polynomial time algorithm to decide whether f(wn) is zero or not, where f(wn) denotes the n-th primitive root of unity e2piradic(-1/n). All previously known algorithms are either randomized, or do not run in polynomial time. As a side result, we prove that if n is free of prime factors less than k + 1, there exist k field automorphisms sigma1, sigma2, ... , sigmakin the Galois group Gal (Q(wn)/Q) such that for any nonzero integers c1, c2... , ckand for any integers 0 les e12ki(ckwnek+ ck-1wne(k-1)+ ... + c1wne(1)) | ges 1/2(k(2)logn+klogk).

For an error‐correcting code and a distance bound, the list decoding problem is to compute all the codewords within a given distance to a received message. The bounded distance decoding problem is to find one codeword if there is at least one codeword within the given distance, or to output the empty set if there is not. Obviously the bounded distance decoding problem is not as hard as the list decoding problem. For a Reed–Solomon code $[n,k]_q$, a simple counting argument shows that for any integer $0 0 $. We show that the discrete logarithm problem over ${\bf F}_{q^{h}}$ can be efficiently reduced by a randomized algorithm to the bounded distance decoding problem of the Reed–Solomon code $[q, g-h]_q$ with radius $q - g$. These results show that the decoding problems for the Reed–Solomon code are at least as hard as the discrete logarithm problem over certain finite fields. For the list decoding problem of Reed–Solomon codes, although the infeasible radius that we obtain is much larger than the radius, which is known to be feasible, it is the first nontrivial bound. Our result on the bounded distance decodability of Reed–Solomon codes is also the first of its kind. The main tools for obtaining these results are an interesting connection between the problem of list decoding of Reed–Solomon code, the problem of a discrete logarithm over finite fields, and a generalization of Katz’s theorem on representations of elements in an extension finite field by products of distinct linear factors.

In this paper, we present an algorithm that, given a fixed prime power q and a positive integer N, finds an integer $n \in [N, 2qN]$ and an element $\alpha \in \mbox{\bf F}_{q^n}$ of order greater than $ 5.8^{n / \log_q n}$, in time polynomial in N. We present another algorithm that finds an integer $n \in [N, N+O(N^{0.77})]$ and an element $\alpha \in \mbox{\bf F}_{q^n}$ of order at least $ 5.8^{\sqrt{n}}$, in time polynomial in N. Our result is inspired by the recent AKS primality testing algorithm [M. Agrawal, N. Kayal, and N. Saxena, Ann. of Math. (2), 160 (2004), pp. 781–793] and the subsequent improvements [P. Berrizbeitia, Math. Comp., 74 (2005), pp. 2043–2059, Q. Cheng, in Proceedings of the 23rd Annual International Cryptology Conference (CRYPTO 2003), D. Boneh, ed., Lecture Notes in Comput. Sci. 2729, Springer-Verlag, Berlin, 2003, pp. 338–348, D. J. Bernstein, Math. Comp., 76 (2007), pp. 389–403].

In this paper, we study the complexity of self-assembly under models that are natural generalizations of the tile self-assembly model. In particular, we extend Rothemund and Winfree's study of the tile complexity of tile self-assembly [Proceedings of the 32nd Annual ACM Symposium on Theory of Computing, Portland, OR, 2000, pp. 459--468]. They provided a lower bound of $\Omega(\frac{\log N}{\log\log N})$ on the tile complexity of assembling an $N\times N$ square for almost all N. Adleman et al. [Proceedings of the 33rd Annual ACM Symposium on Theory of Computing, Heraklion, Greece, 2001, pp. 740--748] gave a construction which achieves this bound. We consider whether the tile complexity for self-assembly can be reduced through several natural generalizations of the model. One of our results is a tile set of size $O(\sqrt{\log N})$ which assembles an $N\times N$ square in a model which allows flexible glue strength between nonequal glues. This result is matched for almost all N by a lower bound dictated by Kolmogorov complexity. For three other generalizations, we show that the $\Omega(\frac{\log N}{\log\log N})$ lower bound applies to $N\times N$ squares. At the same time, we demonstrate that there are some other shapes for which these generalizations allow reduced tile sets. Specifically, for thin rectangles with length N and width k, we provide a tighter lower bound of $\Omega(\frac{N^{1/k}}{k})$ for the standard model, yet we also give a construction which achieves $O(\frac{\log N}{\log\log N})$ complexity in a model in which the temperature of the tile system is adjusted during assembly. We also investigate the problem of verifying whether a given tile system uniquely assembles into a given shape; we show that this problem is NP-hard for three of the generalized models.

In this paper, we study the bounded sum-of-digits discrete logarithm problem in finite fields. Our results are concerned primarily with fields F q n , where n|q - 1. The fields are called Kummer extensions of F q . It is known that we can efficiently construct an element g with order exponential in n. Let $S_q(\bullet)$ be the function from integers to the sum of digits in their q-ary expansions. We first present an algorithm that, given g e (0 $\leq$ e < q n ), finds e in random polynomial time, provided that S q (e) < n. We then show that the problem is solvable in random polynomial time for most of the exponent e with S q (e) < 1.32 n by exploring an interesting connection between the discrete logarithm problem and the problem of list decoding of Reed--Solomon codes and applying the Guruswami--Sudan algorithm. As far as we are aware, our algorithm is the first one which can solve discrete logarithms of $2^{\log^{1-\epsilon}{q^n}}$ many instances in polynomial time for infinite many constant characteristic fields F q n . Furthermore, since every finite field has an extension of reasonable degree, which is a Kummer extension, our result revealsan unexpected property of the discrete logarithm problem, namely, the bounded sum-of-digits discrete logarithm problem in any given finite field becomes polynomial-time solvable in certain low degree extensions. As a side result, we obtain a sharper lower bound on the number of congruent polynomials generated by linear factors than the one based on the Stothers--Mason ABC-theorem. We also prove that, in the field F q q -1, the bounded sum-of-digits discrete logarithm with respect to g can be computed in random time O(f(w)log 4 (q q -1)), where f is a subexponential function and w is the bound on the q-ary sum-of-digits of the exponent; hence the problem is fixed parameter tractable. These results are shown to be generalized to Artin--Schreier extension F p p , where p is a prime.

For an error-correcting code and a distance bound, the list decoding problem is to compute all the codewords within a given distance to a received message. The bounded distance decoding problem is to find one codeword if there is at least one codeword within the given distance, or to output the empty set if there is not. Obviously the bounded distance decoding problem is not as hard as the list decoding problem. For a Reed-Solomon code [n, k]/sup q/, a simple counting argument shows that for any integer 00. We show that the discrete logarithm problem over F/sub qh/ can be efficiently reduced by a randomized algorithm to the bounded distance decoding problem of the Reed-Solomon code [q, g - h]/sub q/ with radius q - g. These results show that the decoding problems for the Reed-Solomon code are at least as hard as the discrete logarithm problem over finite fields. The main tools to obtain these results are an interesting connection between the problem of list-decoding of Reed-Solomon code and the problem of discrete logarithm over finite fields, and a generalization of Katz's theorem on representations of elements in an extension finite field by products of distinct linear factors.

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.