In this article we state and prove a corrected version of Theorem 3.5 in [SIAM J. Comput., 18 (1989), pp. 859--881].

Sigma-delta modulation, a widely used method of analog-to-digital (A/D) signal conversion, is known to be robust to hardware imperfections, i.e., bit streams generated by slightly imprecise hardware components can be decoded comparably well. We formulate a model for robustness and give a rigorous analysis for single-loop sigma-delta modulation applied to constant signals (DC inputs) for N time cycles, with an arbitrary (small enough) initial condition u/sub o/, and a quantizer that may contain an offset error. The mean-square error (MSE) of any decoding scheme for this quantizer (with u/sub o/ and the offset error known) is bounded below by 1/96N/sup -3/. We also determine the asymptotically best possible MSE as N/spl rarr//spl infin/ for perfect decoding when u/sub o/=0 and u/sub o/= 1/2 . The robustness result is the upper bound that a triangular linear filter decoder (with both u/sub o/ and the offset error unknown) achieves an MSE of 40/3N/sup -3/. These results establish the known result that the O(1/N/sup 3/) decay of the MSE with N is optimal in the single-loop case, under weaker assumptions than previous analyses, and show that a suitable linear decoder is robust against offset error. These results are obtained using methods from number theory and Fourier analysis.

We describe methods to label the M 1 × M 2 grid with the integers 1 to M 1 M 2 so that any K consecutively labeled cells are relatively far apart in the grid in the Manhattan metric. Constructions of such labelings are given which are nearly optimal in a range of conditions. Such labelings can be used in addressing schemes for storing data on two-dimensional arrays that include randomly located "blobs" of defective cells. The data can be precoded using block error-correcting codes before storage, and the usefulness of well-spaced points is to decrease the probability of "burst" errors which cannot be corrected. Possible applications include the storage of speech or music on low-quality memory chips and in "holographic memories" to store bit-mapped data. More generally, we present a general family of mappings of the integers 1 to M 1 M 2 . . . M d onto the d-dimensional grid of size M 1 × M 2 × . . . × M d , called mixed radix vector mappings. These mappings give labelings whenever they are one to one. We give a sufficient condition for these mappings to be one to one, which is easy to verify in many cases.

We consider the problem of deciding whether a polygonal knot in 3-dimensional Euclidean space is unknotted, ie., capable of being continuously deformed without self-intersection so that it lies in a plane. We show that this problem, UNKNOTTING PROBLEM is in NP. We also consider the problem, SPLITTING PROBLEM of determining whether two or more such polygons can be split, or continuously deformed without self-intersection so that they occupy both sides of a plane without intersecting it. We show that it also is in NP. Finally, we show that the problem of determining the genus of a polygonal knot (a generalization of the problem of determining whether it is unknotted) is in PSPACE. We also give exponential worst-case running time bounds for deterministic algorithms to solve each of these problems. These algorithms are based on the use of normal surfaces and decision procedures due to W. Haken, with recent extensions by W. Jaco and J. L. Tollefson.

Communications problems that involve frequency interference, such as the channel assignment problem in the design of cellular telephone networks, can be cast as graph coloring problems in which the frequencies (colors) assigned to an edge's vertices interfere if they are too similar. The paper considers situations modeled by vertex-coloring d-regular graphs with n vertices using a color set 1, 2,..., n, where colors i and j are said to interfere if their circular distance $\min \{ | i-j | , n- | i-j | \}$ does not exceed a given threshold value $\alpha$. Given a d-regular graph G and threshold $\alpha$, an interference-minimizing coloring is a coloring of vertices that minimizes the number of edges that interfere. Let $I_\alpha (G)$ denote the minimum number of interfering edges in such a coloring of G. For most triples $(n, \alpha ,d),$ we determine the minimum value of $I_\alpha (G)$ over all d-regular graphs and find graphs that attain it. In determining when this minimum value is 0, we prove that for $r \geq 3$ there exists a d-regular graph G on n vertices that is r-colorable whenever $d \leq (1- \frac{1}{r}) n-1$ and nd is even. We also study the maximum value of $I_\alpha (G)$ over all d-regular graphs and find graphs that attain this maximum in many cases.

We consider the problem of deciding whether a polygonal knot in 3-dimensional Euclidean space is unknotted (that is, whether it is capable of being continuously deformed without self-intersection so that it lies in a plane). We show that this problem, UNKNOTTING PROBLEM, is in NP. We also consider the problem, SPLITTING PROBLEM, of determining whether two or more such polygons can be split (that is, whether they are capable of being continuously deformed without self-intersection so that they occupy both sides of a plane without intersecting it), and show that it also is in NP. Finally, we show that the problem of determining the genus of a polygonal knot (a generalization of the problem of determining whether it is unknotted) is in PSPACE.

This paper gives a probabilistic performance analysis of simple algorithms for packing lists $L_n $, of n squares into a strip or a set of bins. It is assumed that the square sizes are drawn independently from the uniform distribution on,$[0,1]$. The strip-packing problem is to pack the squares into a strip of width 1 so as to minimize the height of the packing. Let ${\operatorname{OPT}}(L_n)$ denote the height of an optimal strip packing for list $L_n $. A simple $O(n\log n)$ approximation algorithm, called Algorithm A, is described and it is proven that the height $A(L_n )$ of a packing of list $L_n $ satisfies $A(L_n ) - {\operatorname{OPT}}(L_n ) \leqq \tfrac{1}{4}$ with probability $1 - O(e^{ - c_0 n} )$ for a positive constant $c_0 $. It is also shown that $E[{\operatorname{OPT}}(L_n )] = 3n/8 + \Theta (n^{{1 / 3}} )$. The bin-packing problem is to pack the squares into square bins of size 1 so as to minimize the number of bins. Let ${\operatorname{OPT}}_B (L_n )$ denote the number of bins in an optimal packing of list $L_n $. The authors present another $O(n\log n)$ approximation algorithm and show that the number of bins it needs to pack a list $L_n $ is precisely ${\operatorname{OPT}}_B (L_n )$ with probability $1 - O(e^{ - c_1 n} )$ for a positive constant $c_1 $. Finally, it is shown that $E[{\operatorname{OPT}}_B (L_n )] = {n / 2} + \Theta (1)$. These bounds for packing squares into strips and bins are much tighter than GTthose that have been obtained for packing rectangles.

This paper considers variants and generalizations of the following computational problem. Given a real input ${\bf x} \in \mathbb{R}^n $, find a small integer relation ${\bf m}$ for x that is a nonzero vector $m \in \mathbb{Z}^n $ orthogonal to ${\bf x}$, or prove that no integer relation ${\bf m}$ exists with $\|{\bf m}\| \leqq 2^\lambda $. An algorithm is presented that solves this problem in $O(n^3 (k + n))$ arithmetic operations over real numbers. The algorithm is a variation of the multidimensional Euclidean algorithm proposed by Ferguson and Forcade [Bull. Amer. Math. Soc., 1(1979), pp. 912–914] and Bergman [Notes on Ferguson and Forcade’s Generalized Euclidean Algorithm, University of California, Berkeley, CA, 1980]. A connection between such multidimensional Euclidean algorithms and the Lattice Basis Reduction Algorithm of Lenstra, Lenstra Jr., and Lovász [Math. Ann., 21 (1982), pp. 515–534] is shown. Polynomial time solutions are also established for finding linearly independent sets of small integer relations and for finding small simultaneous integer relations for several real vectors, using real input vectors and counting arithmetic operations over real numbers at unit cost. For integer input vectors ${\bf x}$ a different algorithm is given for finding integer relations (that always exist) that uses at most $O(n^3 \log \|x\|)$ arithmetic operations on $O(n + \log \|{\bf x}\|)$ bit integers.

Misère End Play is a two-person constant sum game with perfect information. The game uses a deck of cards that consists of a single totally ordered suit of $2n$ cards. To begin play, the deck is divided into two hands of n cards each, held by players Left and Right, with one player designated as having the lead. The player on lead plays one of his cards, and the other player, after seeing it, plays one of his cards. The player with the higher card wins a “trick” and obtains the lead. The cards in the trick are removed and play continues until all cards are played. In Misère End Play each player's goal is to take as few tricks as possible. Misère End Play is shown to have a simple optimal strategy.

We propose a general polynomial time algorithm to find small integer solutions to systems of linear congruences. We use this algorithm to obtain two polynomial time algorithms for reconstructing the values of variables $x_1 , \cdots ,x_k $ when we are given some linear congruences relating them together with some bits obtained by truncating the binary expansions of the variables. The first algorithm reconstructs the variables when either the high order bits or the low order bits of the $x_i $ are known. It is essentially optimal in its use of information in the sense that it will solve most problems almost as soon as the variables become uniquely determined by their constraints. The second algorithm reconstructs the variables when an arbitrary window of consecutive bits of the variables is known. This algorithm will solve most problems when twice as much information as that necessary to uniquely determine the variables is available. Two cryptanalytic applications of the algorithms are given: predicting linear congruential generators whose outputs are truncated and breaking the simplest version of Blum’s protocol for exchanging secrets.

Let a sequence of k-dimensional vectors ${\bf x}_0 ,{\bf x}_1 , \cdots $ (over a ring A) be determined by a polynomial recurrence of form ${\bf x}_n = T({\bf x}_{n - 1} )$, where $T:A^k \to A^k $ itself is known to be a polynomial map in k variables of degree at most d but is otherwise unknown. We show that there is a finite N such that the entire sequence $\{ {\bf x}_n :n \geqq 0\} $ can be deduced from the first $N + 1$ terms ${\bf x}_0 ,{\bf x}_1 , \cdots ,{\bf x}_N $ alone. The number $N = \phi (d,k,A)$ depends on d and k and the ring A but not on T. Let $\phi ^ * (d,k)$ denote the maximum of $\phi (d,k,A)$ over all commutative rings with unit. Then we show that $\phi ^ * (d,k) < \infty $. In particular, $\phi ^ * (d,1) = d + 1$ and $\phi ^ * (1,k) = k + 1$. In the general case $\phi ^ * (d,k) \geqq \left( {\begin{array}{*{20}c} {k + d} \\ k \\ \end{array} } \right)$ and equality does not always hold because $\phi ^ * (2,2) \geqq 7$. In addition, we show that for each k that $\max \{ \phi (d,k,{\bf F}):{\bf F}{\text{ a field}}\} $ is bounded by a polynomial in d. These results are applied to the problem of correctly extrapolating the values $\{ {{\bf x}_i :i \geqq 0} \}$ of an unknown polynomial recurrence $(\bmod M)$ in k variables of degree at most d, where d and k are known and M is not known. A polynomial-time algorithm is given which computes a value $\hat {\bf x}_{n + 1} $ given the values $\{ {{\bf x}_i :0 \leqq i \leqq n} \}$ of such a recurrence as input, and it is shown that $\hat {\bf x}_{n + 1} \ne {\bf x}_{n + 1} $ for at most \[ 1 + \phi ^ * (d,k) + \log \left( {M^{dN} N^{\tfrac{1}{2}N} } \right) \] values of n, where $N = 1 + k\left( {\begin{array}{*{20}c} {k + d} \\ k \\ \end{array} } \right)$.

The subset sum problem is to decide whether or not the 0-l integer programming problem Σ n i=l a i x i = M , ∀I , x I = 0 or 1, has a solution, where the a i and M are given positive integers. This problem is NP-complete, and the difficulty of solving it is the basis of public-key cryptosystems of knapsack type. An algorithm is proposed that searches for a solution when given an instance of the subset sum problem. This algorithm always halts in polynomial time but does not always find a solution when one exists. It converts the problem to one of finding a particular short vector v in a lattice, and then uses a lattice basis reduction algorithm due to A. K. Lenstra, H. W. Lenstra, Jr., and L. Lovasz to attempt to find v. The performance of the proposed algorithm is analyzed. Let the density d of a subset sum problem be defined by d = n /log 2 (max i a i ). Then for “almost all” problems of density d < 0.645, the vector v we searched for is the shortest nonzero vector in the lattice. For “almost all” problems of density d < 1/ n , it is proved that the lattice basis reduction algorithm locates v. Extensive computational tests of the algorithm suggest that it works for densities d < d c ( n ), where d c ( n ) is a cutoff value that is substantially larger than 1/ n . This method gives a polynomial time attack on knapsack public-key cryptosystems that can be expected to break them if they transmit information at rates below d c ( n ), as n → ∞.

Simultaneous Diophantine approximation in d dimensions deals with the approximation of a vector ${\bf \alpha } = (\alpha _1 , \cdots ,\alpha _d )$ of d real numbers by vectors of rational numbers all having the same denominator. This paper considers the computational complexity of algorithms to find good simultaneous approximations to a given vector $ {\bf \alpha} $ of d rational numbers. We measure the goodness of an approximation using the sup norm. We show that a result of H. W. Lenstra, Jr. produces polynomial-time algorithms to find sup norm best approximations to a given vector ${\bf \alpha} $ when the dimension d is fixed. We show that a recent algorithm of A. K. Lenstra, H. W. Lenstra, Jr. and L. Lovasz to find short vectors in an integral lattice can be used to find a good approximation to a given vector ${\bf \alpha} $ in d dimensions with a denominator $Q^ * $ satisfying $1 \leqq Q^ * \leqq 2^{d/2} N$ which is within a factor $\sqrt {5d} 2^{(d + 1)/2} $ of the best approximation with denominator Q with $1 \leqq Q \leqq N$. This algorithm runs in time polynomial in the input size, independent of the dimension d. We also prove complementary results showing that certain natural simultaneous Diophantine approximation problems are NP-hard. We show that the problem of deciding whether a given vector ${\bf \alpha} $ of rational numbers has a simultaneous approximation of specified accuracy with respect to the sup norm with denominator Q in a given interval $1 \leqq Q \leqq N$ is NP-complete. (Here the dimension d is allowed to vary.) We prove two other complexity results, which suggest that the problem of locating best (sup norm) simultaneous approximations is harder than this NP-complete problem.

One of the most popular and fast methods of generating "random" sequence are linear congruential generators. This paper discusses the predictability of the sequence given only a constant proportion /spl alpha/ of the leading bits of the first few numbers generated. We show that the rest of the sequence is predictable in polynomial time, almost always, provided /spl alpha/ > 2/5.

The subset sum problem is to decide whether or not the 0-1 integer programming problem Σi=1n aixi = M; all xi = 0 or 1; has a solution, where the ai and M are given positive integers. This problem is NP-complete, and the difficulty of solving it is the basis of public key cryptosystems of knapsack type. We propose an algorithm which when given an instance of the subset sum problem searches for a solution. This algorithm always halts in polynomial time, but does not always find a solution when one exists. It converts the problem to one of finding a particular short vector v in a lattice, and then uses a lattice basis reduction algorithm due to A. K. Lenstra, H. W. Lenstra, Jr., and L. Lovász to attempt to find v. We analyze the performance of the proposed algorithm. Let the density d of a subset sum problem be defined by d=n/log2(maxi ai). Then for "almost all" problems of density d ≪ .645 the vector v we are searching for is the shortest nonzero vector in the lattice. We prove that for "almost all" problems of density d ≪ 1/n the lattice basis reduction algorithm locates v. Extensive computational tests of the algorithm suggest that it works for densities d ≪ dc (n), where dc (n) is a cutoff value that is substantially larger than 1/n. This method gives a polynomial time attack on knapsack public key cryptosystems that can be expected to break them if they transmit information at rates below dc (n), as n → ∞.

Simultaneous Diophantine approximation in d dimensions deals with the approximation of a vector α = (α1, ..., αd) of d real numbers by vectors of rational numbers all having the same denominator. This paper considers the computational complexity of algorithms to find good simultaneous approximations to a given vector α of d rational numbers. We measure the goodness of an approximation using the sup norm. We show that a result of H. W. Lenstra, Jr. produces polynomial-time algorithms to find sup norm best approximations to a given vector α when the dimension d is fixed. We show that a recent algorithm of A. K. Lenstra, H. W. Lenstra, Jr., and L. Lovasz to find short vectors in an integral lattice can be used to find a good approximation to a given vector α in d dimensions with a denominator Q satisfying 1 ≤ Q ≤ 2d/2 N which is within a factor √5d 2d+1/2 of the best approximation with denominator Q* with 1 ≤ Q* ≤ N. This algorithm runs in time polynomial in the input size, independent of the dimension d. We prove results complementing these, showing certain natural simultaneous Diophantine approximation problems are NP-hard. We show that the problem of deciding whether a given vector α of rational numbers has a simultaneous approximation of specified accuracy with respect to the sup norm with denominator Q in a given interval 1 ≤ Q ≤ N is NP-complete. (Here the dimension d is allowed to vary.) We prove two other complexity results, which suggest that the problem of locating best (sup norm) simultaneous approximations is harder than this NP-complete problem.

One of the problems which confront designers, implementers, and users of database management systems is the very large amounts of space often required to store a database in a computer system. In general, that space is used for two purposes: to represent certain atomio units of data and to represent certain relationships among those atomic units. This paper investigates the second aspect of the problem, the storage requirements of relationship representations. The class of navigational representations is defined, and several relationship representation techniques commonly used in database management systems are shown to be navigational. Two additional techniques for constructing relationship representations are presented. The first produces more compact representations than the standard techniques by taking advantage of a property of relationships called companionship. The second technique, called the powerset representation, always achieves a worst-case lower bound on the size of navigational relationship representations.

Binary quadratic Diophantine equations are of interest from the viewpoint of computational complexity theory. This class of equations includes as special cases many of the known examples of natural problems apparently occupying intermediate stages in the P − NP hierarchy, i.e., problems not known to be solvable in polynomial time nor to be NP-complete, for example the problem of factoring integers. Let L(F) denote the length of the binary encoding of the binary quadratic Diophantine equation F given by ax 2 +bx1x2+cx 2 +dx1+ex2+f = 0. Suppose F is such an equation having a nonnegative integer solution. This paper shows that there is a proof (i.e., “certificate”) that F has such a solution which can be checked in O(L(F) 5 logL(F)log logL(F)) bit operations. A corollary of this result is that the set � = {F : F has a nonnegative integer solution} is in