We consider a simple model of a growing cluster of points in R d , d ≥ 2 . Beginning with a point X 1 located at the origin, we generate a random sequence of points X 1 , X 2 , … , X i , … , . To generate X i , i ≥ 2 we choose a uniform integer j in [ i − 1 ] = 1 , 2 , … , i − 1 and then let X i = X j + D i where D i = ( δ 1 , … , δ d ) . Here the δ j are independent copies of the Normal distribution N ( 0 , σ i ) , where σ i = i − α for some α > 0 . We prove that for any α > 0 the resulting point set is bounded a.s., and moreover, that the points generated look like samples from a β -dimensional subset of R d from the standpoint of the minimum lengths of combinatorial structures on the point-sets, where β = min ( d , 1 / α ) .

A central problem related to transformers can be stated as follows: given two $n \times d$ matrices $Q$ and $K$, and a non-negative function $f$, define the matrix $A$ as follows: (1) apply the function $f$ to each entry of the $n \times n$ matrix $Q K^T$, and then (2) normalize each of the row sums of $A$ to be equal to $1$. The matrix $A$ can be computed in $O(n^2 d)$ time assuming $f$ can be applied to a number in constant time, but the quadratic dependence on $n$ is prohibitive in applications where it corresponds to long context lengths. For a large class of functions $f$, we show how to find all the "large attention scores", i.e., entries of $A$ which are at least a positive value $\varepsilon$, in time with linear dependence on $n$ (i.e., $n \cdot \textrm{poly}(d/\varepsilon)$) for a positive parameter $\varepsilon > 0$. Our class of functions include all functions $f$ of the form $f(x) = |x|^p$, as explored recently in transformer models. Using recently developed tools from randomized numerical linear algebra, we prove that for any $K$, there is a "universal set" $U \subset [n]$ of size independent of $n$, such that for any $Q$ and any row $i$, the large attention scores $A_{i,j}$ in row $i$ of $A$ all have $j \in U$. We also find $U$ in $n \cdot \textrm{poly}(d/\varepsilon)$ time. Notably, we (1) make no assumptions on the data, (2) our workspace does not grow with $n$, and (3) our algorithms can be computed in streaming and parallel settings. We empirically show the benefits of our scheme for vision transformers, showing how to train new models that use our universal set while training as well, showing that our model is able to consistently select "important keys'" during training. We also provide theoretical motivation by formulating a planted model in which our efficient algorithms provably identify relevant keys for each query.

The Separating Hyperplane theorem is a fundamental result in Convex Geometry with myriad applications. The theorem asserts that for a point a not in a closed convex set K, there is a hyperplane with K on one side and a strictly on the other side. Our first result, Random Separating Hyperplane Theorem (RSH), is a strengthening of this for polytopes. RSH asserts that if the distance between a and a polytope K with k vertices and unit diameter in ℜ^d is at least δ, where δ is a fixed constant in (0,1), then a randomly chosen hyperplane separates a and K with probability at least 1/poly(k) and margin at least Ω (δ/√d). RSH has algorithmic applications in learning polytopes. We consider a fundamental problem, denoted the "Hausdorff problem", of learning a unit diameter polytope K within Hausdorff distance δ, given an optimization oracle for K. Using RSH, we show that with polynomially many random queries to the optimization oracle, K can be approximated within error O(δ). To our knowledge, this is the first provable algorithm for the Hausdorff Problem in this setting. Building on this result, we show that if the vertices of K are well-separated, then an optimization oracle can be used to generate a list of points, each within distance O(δ) of K, with the property that the list contains a point close to each vertex of K. Further, we show how to prune this list to generate a (unique) approximation to each vertex of the polytope. We prove that in many latent variable settings, e.g., topic modeling, LDA, optimization oracles do exist provided we project to a suitable SVD subspace. Thus, our work yields the first efficient algorithm for finding approximations to the vertices of the latent polytope under the well-separatedness assumption. This assumption states that each vertex of K is far from the convex hull of the remaining vertices of K, and is much weaker than other assumptions behind algorithms in the literature which find vertices of the latent polytope.

We study the bit complexity of two related fundamental computational problems in linear algebra and control theory. Our results are: (1) An Õ(n^{ω+3}a+n⁴a²+n^ωlog(1/ε)) time algorithm for finding an ε-approximation to the Jordan Normal form of an integer matrix with a-bit entries, where ω is the exponent of matrix multiplication. (2) An Õ(n⁶d⁶a+n⁴d⁴a²+n³d³log(1/ε)) time algorithm for ε-approximately computing the spectral factorization P(x) = Q^*(x)Q(x) of a given monic n× n rational matrix polynomial of degree 2d with rational a-bit coefficients having a-bit common denominators, which satisfies P(x)⪰0 for all real x. The first algorithm is used as a subroutine in the second one. Despite its being of central importance, polynomial complexity bounds were not previously known for spectral factorization, and for Jordan form the best previous best running time was an unspecified polynomial in n of degree at least twelve [Cai, 1994]. Our algorithms are simple and judiciously combine techniques from numerical and symbolic computation, yielding significant advantages over either approach by itself.

Many algorithms for clustering high dimensional data assume that k, the number of clusters, is given. However, there has been little work on provably inferring k from the data. This paper gives polynomial time algorithms for finding k from the data assuming it satisfies certain natural deterministic conditions. Informally, we assume that there is a Ground Truth (GT) clustering of the data with the following properties: (i) Each cluster has a certain minimum size, (ii) the inter-mean separation of any two distinct clusters in the GT is large enough (although still weaker than what is typically assumed in the literature), and (iii) we define a novel “no large sub-cluster” (NLSC) property that characterizes the notion of a cluster by stipulating that there be no subsets of low “directional variance”. NLSC is indeed satisfied by large class of distributions including log-concave densities. The first major contribution is an algorithm for finding k where m, the minimum GT cluster size, is assumed to be known. This algorithm uses a novel rounding procedure which finds subsets of size m with low Directional Variance by rounding a SDP relaxation using Cheeger's inequality and it is shown that k is precisely the number of such sets whose means are well-separated. The harder problem of finding k when m not given is addressed by running the previous algorithm for each value of m to find candidate values of k and the corresponding k-clustering. The second major contribution of this paper is a test which certifies the correct candidate thereby yielding a polynomial time algorithm which finds k.

The recently introduced Latent $k-$ Polytope($\LkP$) encompasses several stochastic Mixed Membership models including Topic Models. The problem of finding $k$, the number of extreme points of $\LkP$, is a fundamental challenge and includes several important open problems such as determination of number of components in Ad-mixtures. This paper addresses this challenge by introducing Interpolative Convex Rank(\INR) of a matrix defined as the minimum number of its columns whose convex hull is within Hausdorff distance $\varepsilon$ of the convex hull of all columns. The first important contribution of this paper is to show that under \emph{standard assumptions} $k$ equals the \INR of a \emph{subset smoothed data matrix} defined from Data generated from an $\LkP$. The second important contribution of the paper is a polynomial time algorithm for finding $k$ under standard assumptions. An immediate corollary is the first polynomial time algorithm for finding the \emph{inner dimension} in Non-negative matrix factorisation(NMF) with assumptions which are qualitatively different than existing ones such as \emph{Separability}. %An immediate corollary is the first polynomial time algorithm for finding the \emph{inner dimension} in Non-negative matrix factorisation(NMF) with assumptions considerably weaker than \emph{Separability}.

Deriving Optimal bounds on Sample Complexity of Latent Variable models is an active area of research. Recently such bounds were obtained for Mixture of Gaussians \cite{HSNCAY18}, no such results are known for Ad-mixtures, a generalization of Mixture distributions. In this paper we show that $O^*(dk/m)$ samples are sufficient to learn each of $k-$ topic vectors of LDA, a popular Ad-mixture model, with vocabulary size $d$ and $m\in \Omega(1)$ words per document, to any constant error in $L_1$ norm. The result is a corollary of the major contribution of this paper: the first sample complexity upper bound for the problem (introduced in \cite{BK20}) of learning the vertices of a Latent $k-$ Polytope in $\RR^d$, given perturbed points from it. The bound, $O^*(dk/\beta)$, is optimal and linear in number of parameters. It applies to many stochastic models including a broad class Ad-mixtures. To demonstrate the generality of the approach we specialize the setting to Mixed Membership Stochastic Block Models(MMSB) and show for the first time that if an MMSB has $k$ blocks, the sample complexity is $O^*(k^2)$ under usual assumptions.

In this paper we show that the learning problem for a large class of Latent variable models, such as Mixed Membership Stochastic Block Models, Topic Models, and Adversarial Clustering can be posed geometrically as follows: find a latent k— vertex simplex, K in Rd, given n data points, each obtained by perturbing a latent point in K. This problem does not seem to have been addressed. Our main contribution is an efficient algorithm for the geometric problem under deterministic assumptions which naturally hold for the models considered here. We observe that for a suitable r ≤ n, K is close to a data-determined polytope K’ (the subset smoothed, polytope) which is the convex hull of the points, each obtained by averaging an r subset of data points. Our algorithm is simply stated: it optimizes k carefully chosen linear functions over K’ to find the k vertices of the latent simplex. The proof of correctness is more involved, drawing on existing and new tools from Numerical Analysis. Our overall runtime of O* (k nnz) is as good as the best times of existing algorithms (modulo O* (1) factor) for the special cases and is better for sparse data which is the norm in Topic Modelling and Mixed Membership models. Some consequences of our algorithm are: Mixed Membership Models and Topic Models: We give the first quasi-input-sparsity time algorithm for parameter estimation for k ϵ O* (1) Adversarial Clustering: In k–means, an adversary is allowed to move many data points from each cluster towards the convex hull of other cluster centers. Our algorithm still estimates cluster centers well.

We introduce the following \em hidden hubs model $H(n,k,\sigma_0, \sigma_1)$: the input is an $n \times n$ random matrix $A$ with a subset $S$ of $k$ special rows (hubs); entries in rows outside $S$ are generated from the Gaussian distribution $p_0 = N(0,\sigma_0^2)$, while for each row in $S$, an unknown subset of $k$ of its entries are generated from $p_1 = N(0,\sigma_1^2)$, $\sigma_1>\sigma_0$, and the rest of the entries from $p_0$. The special rows with higher variance entries can be viewed as hidden higher-degree hubs. The problem we address is to identify the hubs efficiently. The planted Gaussian Submatrix Model is the special case where the higher variance entries must all lie in a $k \times k$ submatrix. If $k≥c\sqrt{n}\ln n$, just the row sums are sufficient to find $S$ in the general model. For the Gaussian submatrix problem (and the related planted clique problem), this can be improved by a $\sqrt\ln n$ factor to $k \ge c\sqrt{n}$ by spectral or combinatorial methods. We give a polynomial-time algorithm to identify all the hidden hubs with high probability for $k \ge n^0.5-δ$ for some $δ>0$, when $\sigma_1^2>2\sigma_0^2$. The algorithm extends to the setting where planted entries might have different variances, each at least $\sigma_1^2$. We also show a nearly matching lower bound: for $\sigma_1^2 \le 2\sigma_0^2$, there is no polynomial-time Statistical Query algorithm for distinguishing between a matrix whose entries are all from $N(0,\sigma_0^2)$ and a matrix with $k=n^0.5-δ$ hidden hubs for any $δ>0$. The lower bound as well as the algorithm are related to whether the chi-squared distance of the two distributions diverges. At the critical value $\sigma_1^2=2\sigma_0^2$, we show that the hidden hubs problem can be solved for $k≥c\sqrt n(\ln n)^1/4$, improving on the naive row sum-based method.

The Noisy Non-negative Matrix factorization (NMF) is: given a data matrix A (d x n), find non-negative matrices B;C (d x k, k x n respy.) so that A = BC +N, where N is a noise matrix. Existing polynomial time algorithms with proven error guarantees require EACH column N_⋅j to have l1 norm much smaller than ||(BC)_⋅j ||_1, which could be very restrictive. In important applications of NMF such as Topic Modeling as well as theoretical noise models (e.g. Gaussian with high sigma), almost EVERY column of N_.j violates this condition. We introduce the heavy noise model which only requires the average noise over large subsets of columns to be small. We initiate a study of Noisy NMF under the heavy noise model. We show that our noise model subsumes noise models of theoretical and practical interest (for e.g. Gaussian noise of maximum possible sigma). We then devise an algorithm TSVDNMF which under certain assumptions on B,C, solves the problem under heavy noise. Our error guarantees match those of previous algorithms. Our running time of O(k.(d+n)^2) is substantially better than the O(d.n^3) for the previous best. Our assumption on B is weaker than the “Separability” assumption made by all previous results. We provide empirical justification for our assumptions on C. We also provide the first proof of identifiability (uniqueness of B) for noisy NMF which is not based on separability and does not use hard to check geometric conditions. Our algorithm outperforms earlier polynomial time algorithms both in time and error, particularly in the presence of high noise.

In the nonnegative matrix factorization (NMF) problem we are given an $n \times m$ nonnegative matrix $M$ and an integer $r > 0$. Our goal is to express $M$ as $A W$, where $A$ and $W$ are nonnegative matrices of size $n \times r$ and $r \times m$, respectively. In some applications, it makes sense to ask instead for the product $AW$ to approximate $M$, i.e. (approximately) minimize $\left\lVert{M - AW}_F\right\rVert$, where $\left\lVert\right\rVert_F$, denotes the Frobenius norm; we refer to this as approximate NMF. This problem has a rich history spanning quantum mechanics, probability theory, data analysis, polyhedral combinatorics, communication complexity, demography, chemometrics, etc. In the past decade NMF has become enormously popular in machine learning, where $A$ and $W$ are computed using a variety of local search heuristics. Vavasis recently proved that this problem is NP-complete. (Without the restriction that $A$ and $W$ be nonnegative, both the exact and approximate problems can be solved optimally via the singular value decomposition.) We initiate a study of when this problem is solvable in polynomial time. Our results are the following: 1. We give a polynomial-time algorithm for exact and approximate NMF for every constant $r$. Indeed NMF is most interesting in applications precisely when $r$ is small. 2. We complement this with a hardness result, that if exact $NMF$ can be solved in time $(nm)^{o(r)}$, 3-SAT has a subexponential-time algorithm. This rules out substantial improvements to the above algorithm. 3. We give an algorithm that runs in time polynomial in $n$, $m$, and $r$ under the separablity condition identified by Donoho and Stodden in 2003. The algorithm may be practical since it is simple and noise tolerant (under benign assumptions). Separability is believed to hold in many practical settings. To the best of our knowledge, this last result is the first example of a polynomial-time algorithm that provably works under a non-trivial condition on the input and we believe that this will be an interesting and important direction for future work.

The classic Arrow-Debreu market model captures both production and consumption, two equally important blocks of an economy, however most of the work in theoretical computer science has so far concentrated on markets without production, i.e., the exchange economy. In this paper we show two new results on markets with production. Our first result gives a polynomial time algorithm for Arrow-Debreu markets under piecewise linear concave (PLC) utilities and polyhedral production sets provided the number of goods is constant. This is the first polynomial time result for the most general case of Arrow-Debreu markets.

We consider algorithmic problems in the setting in which the input data has been partitioned arbitrarily on many servers. The goal is to compute a function of all the data, and the bottleneck is the communication used by the algorithm. We present algorithms for two illustrative problems on massive data sets: (1) computing a low-rank approximation of a matrix A=A^1 + A^2 + \ldots + A^s, with matrix A^t stored on server t and (2) computing a function of a vector a_1 + a_2 + \ldots + a_s, where server t has the vector a_t; this includes the well-studied special case of computing frequency moments and separable functions, as well as higher-order correlations such as the number of subgraphs of a specified type occurring in a graph. For both problems we give algorithms with nearly optimal communication, and in particular the only dependence on n, the size of the data, is in the number of bits needed to represent indices and words (O(\log n)).

We study spectral algorithms for the high-dimensional Nearest Neighbor Search problem (NNS). In particular, we consider a semi-random setting where a dataset is chosen arbitrarily from an unknown subspace of low dimension, and then perturbed by full-dimensional Gaussian noise. We design spectral NNS algorithms whose query time depends polynomially on the dimension and logarithmically on the size of the point set. These spectral algorithms use a repeated computation of the top PCA vector/subspace, and are effective even when the random-noise magnitude is much larger than the interpoint distances. Our motivation is that in practice, a number of spectral NNS algorithms outperform the random-projection methods that seem otherwise theoretically optimal on worst-case datasets. In this paper we aim to provide theoretical justification for this disparity. The full version of this extended abstract is available on arXiv.

The Nonnegative Matrix Factorization (NMF) problem has a rich history spanning quantum mechanics, probability theory, data analysis, polyhedral combinatorics, communication complexity, demography, chemometrics, etc. In the past decade NMF has become enormously popular in machine learning, where the factorization is computed using a variety of local search heuristics. Vavasis recently proved that this problem is NP-complete. We initiate a study of when this problem is solvable in polynomial time. Consider a nonnegative m x n matrix $M$ and a target inner-dimension r. Our results are the following: - We give a polynomial-time algorithm for exact and approximate NMF for every constant r. Indeed NMF is most interesting in applications precisely when r is small. We complement this with a hardness result, that if exact NMF can be solved in time (nm)o(r), 3-SAT has a sub-exponential time algorithm. Hence, substantial improvements to the above algorithm are unlikely. - We give an algorithm that runs in time polynomial in n, m and r under the separablity condition identified by Donoho and Stodden in 2003. The algorithm may be practical since it is simple and noise tolerant (under benign assumptions). Separability is believed to hold in many practical settings.

There has been much progress on efficient algorithms for clustering data points generated by a mixture of k probability distributions under the assumption that the means of the distributions are well-separated, i.e., the distance between the means of any two distributions is at least Ω(k) standard deviations. These results generally make heavy use of the generative model and particular properties of the distributions. In this paper, we show that a simple clustering algorithm works without assuming any generative (probabilistic) model. Our only assumption is what we call a "proximity condition'': the projection of any data point onto the line joining its cluster center to any other cluster center is Ω(k) standard deviations closer to its own center than the other center. Here the notion of standard deviations is based on the spectral norm of the matrix whose rows represent the difference between a point and the mean of the cluster to which it belongs. We show that in the generative models studied, our proximity condition is satisfied and so we are able to derive most known results for generative models as corollaries of our main result. We also prove some new results for generative models - e.g., we can cluster all but a small fraction of points only assuming a bound on the variance. Our algorithm relies on the well known k-means algorithm, and along the way, we prove a result of independent interest - that the k-means algorithm converges to the "true centers'' even in the presence of spurious points provided the initial (estimated) centers are close enough to the corresponding actual centers and all but a small fraction of the points satisfy the proximity condition. Finally, we present a new technique for boosting the ratio of inter-center separation to standard deviation. This allows us to prove results for learning certain mixture of distributions under weaker separation conditions.

While Spectral Methods have long been used for Principal Component Analysis, this survey focusses on work over the last 15 years with three salient features: (i) Spectral methods are useful not only for numerical problems, but also discrete optimization problems (Constraint Optimization Problems - CSP's) like the max. cut problem and similar mathematical considerations underlie both areas. (ii) Spectral methods can be extended to tensors. The theory and algorithms for tensors are not as simple/clean as for matrices, but the survey describes methods for low-rank approximation which extend to tensors. These tensor approximations help us solve Max-$r$-CSP's for $r>2$ as well as numerical tensor problems. (iii) Sampling on the fly plays a prominent role in these methods. A primary result is that for any matrix, a random submatrix of rows/columns picked with probabilities proportional to the squared lengths (of rows/columns), yields estimates of the singular values as well as an approximation to the whole matrix.

We present two probability inequalities. The simpler first inequality weakens both hypotheses in Hoffding-Azumaine quality. Using it, we generalize concentration results previously known for the uniform density for the TSP, MWST and Random Projections to long-tailed inhomogeneous distributions. The second more complicated inequality further weakens the moment requirements and using it, we prove the best possible concentration for the long-studied bin packing problem as well as some others.

This volume contains the proceedings of the 29th international conference on the Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2009), organized under the auspices of the Indian Association for Research in Computing Science (IARCS) at the Indian Institute of Technology, Kanpur, India.

Let K be a polytope in Rn defined by m linear inequalities. We give a new Markov Chain algorithm to draw a nearly uniform sample from K. The underlying Markov Chain is the first to have a mixing time that is strongly polynomial when started from a "central" point x0. If s is the supremum over all chords pq passing through x0 of (|p-x0|)/(|q-x0|) and ε is an upper bound on the desired total variation distance from the uniform, it is sufficient to take O(m n( n log (s m) + log 1/ε)) steps of the random walk. We use this result to design an affine interior point algorithm that does a single random walk to solve linear programs approximately. More precisely, suppose Q = {z | Bz ≤ 1} contains a point z such that cT z ≥ d and r := supz ∈ Q |Bz| + 1, where B is an m x n matrix. Then, after τ = O(mn (n ln(mr/ε) + ln 1/δ)) steps, the random walk is at a point xτ for which cT xτ ≥ d(1-ε) with probability greater than 1-δ. The fact that this algorithm has a run-time that is provably polynomial is notable since the analogous deterministic affine algorithm analyzed by Dikin has no known polynomial guarantees.

We present multiple pass streaming algorithms for a basic statistical clustering problem for massive data sets. If our algorithm is allotted $2\ell$ passes, it will produce an approximation with error at most $\epsilon$ using $\tilde{O}(k^3/\epsilon^{2/\ell})$ bits of memory, the most critical resource for streaming computation. We demonstrate that this tradeoff between passes and memory allotted is intrinsic to the problem and model of computation by proving lower bounds on the memory requirements of any $\ell$ pass randomized algorithm that are nearly matched by our upper bounds. In this problem, we are given a set of n points drawn randomly according to a mixture of k uniform distributions and wish to approximate the density function of the mixture. The points are placed in a data stream (possibly in adversarial order), which may only be read in sequential passes by the algorithm. The algorithm is quite general and can be adapted to solve the problems of learning a mixture of linear distributions in $\mathbb{R}$ and a mixture of uniform distributions in $\mathbb{R}^2$.

We consider markets in the classical Arrow-Debreu model. There are n agents and m goods. Each buyer has a concave utility function (of the bundle of goods he/she buys) and an initial bundle. At an ldquoequilibriumrdquo set of prices for goods, if each individual buyer separately ex-changes the initial bundle for an optimal bundle at the set prices, the market clears, i.e., all goods are exactly consumed. Classical theorems guarantee the existence of equilibria, but computing them has been the subject of much recent research. In the related area of Multi-Agent Games,much attention has been paid to the complexity as well as algorithms. While most general problems are hard, polynomial time algorithms have been developed for restricted classes of games, when one assumes the number of strategies is constant.For the Market Equilibrium problem, several important special cases of utility functions have been tackled. Here we begin a program for this problem similar to that for multi-agent games, where general utilities are considered. We begin by showing that if the utilities are separable piece-wise linear concave (PLC) functions, and the number of goods(or alternatively the number of buyers) is constant, then we can compute an exact equilibrium in polynomial time.Our technique for the constant number of goods is to de-compose the space of price vectors into cells using certain hyperplanes, so that in each cell, each buyerpsilas threshold marginal utility is known. Still, one needs to solve a linear optimization problem in each cell. We then show the main result - that for general (non-separable) PLC utilities, an exact equilibrium can be found in polynomial time provided the number of goods is constant. The starting point of the algorithm is a ldquocell-decompositionrdquo of the space of price vectors using polynomial surfaces (instead of hyperplanes).We use results from computational algebraic geometry to bound the number of such cells. For solving the problem inside each cell, we introduce and use a novel LP-duality based method. We note that if the number of buyers and agents both can vary, the problem is PPAD hard even for the very special case of PLC utilities - namely Leontief utilities.

We study the problem of finding a large planted clique in the random graph $G_{n,1/2}$. We reduce the problem to that of maximising a three dimensional tensor over the unit ball in $n$ dimensions. This latter problem has not been well studied and so we hope that this reduction will eventually lead to an improved solution to the planted clique problem.

We present an algorithm for learning a mixture of distributions based on spectral projection. We prove a general property of spectral projection for arbitrary mixtures and show that the resulting algorithm is efficient when the components of the mixture are logconcave distributions in $\Re^n$ whose means are separated. The separation required grows with k, the number of components, and $\log n$. This is the first result demonstrating the benefit of spectral projection for general Gaussians and widens the scope of this method. It improves substantially on previous results, which focus either on the special case of spherical Gaussians or require a separation that has a considerably larger dependence on n.

Motivated by applications in which the data may be formulated as a matrix, we consider algorithms for several common linear algebra problems. These algorithms make more efficient use of computational resources, such as the computation time, random access memory (RAM), and the number of passes over the data, than do previously known algorithms for these problems. In this paper, we devise two algorithms for the matrix multiplication problem. Suppose A and B (which are $m\times n$ and $n\times p$, respectively) are the two input matrices. In our main algorithm, we perform c independent trials, where in each trial we randomly sample an element of $\{ 1,2,\ldots, n\}$ with an appropriate probability distribution ${\cal P}$ on $\{ 1,2,\ldots, n\}$. We form an $m\times c$ matrix C consisting of the sampled columns of A, each scaled appropriately, and we form a $c\times n$ matrix R using the corresponding rows of B, again scaled appropriately. The choice of ${\cal P}$ and the column and row scaling are crucial features of the algorithm. When these are chosen judiciously, we show that $CR$ is a good approximation to $AB$. More precisely, we show that $$ \left\|AB-CR\right\|_F = O(\left\|A\right\|_F \left\|B\right\|_F /\sqrt c) , $$ where $\|\cdot\|_F$ denotes the Frobenius norm, i.e., $\|A\|^2_F=\sum_{i,j}A_{ij}^2$. This algorithm can be implemented without storing the matrices A and B in RAM, provided it can make two passes over the matrices stored in external memory and use $O(c(m+n+p))$ additional RAM to construct C and R. We then present a second matrix multiplication algorithm which is similar in spirit to our main algorithm. In addition, we present a model (the pass-efficient model) in which the efficiency of these and other approximate matrix algorithms may be studied and which we argue is well suited to many applications involving massive data sets. In this model, the scarce computational resources are the number of passes over the data and the additional space and time required by the algorithm. The input matrices may be presented in any order of the entries (and not just row or column order), as is the case in many applications where, e.g., the data has been written in by multiple agents. In addition, the input matrices may be presented in a sparse representation, where only the nonzero entries are written.

In many applications, the data consist of (or may be naturally formulated as) an $m \times n$ matrix A. It is often of interest to find a low-rank approximation to A, i.e., an approximation D to the matrix A of rank not greater than a specified rank k, where k is much smaller than m and n. Methods such as the singular value decomposition (SVD) may be used to find an approximation to A which is the best in a well-defined sense. These methods require memory and time which are superlinear in m and n; for many applications in which the data sets are very large this is prohibitive. Two simple and intuitive algorithms are presented which, when given an $m \times n$ matrix A, compute a description of a low-rank approximation $D^{*}$ to A, and which are qualitatively faster than the SVD. Both algorithms have provable bounds for the error matrix $A-D^{*}$. For any matrix X, let $\|{X}\|_F$ and $\|{X}\|_2$ denote its Frobenius norm and its spectral norm, respectively. In the first algorithm, c columns of A are randomly chosen. If the $m \times c$ matrix C consists of those c columns of A (after appropriate rescaling), then it is shown that from $C^TC$ approximations to the top singular values and corresponding singular vectors may be computed. From the computed singular vectors a description $D^{*}$ of the matrix A may be computed such that $\mathrm{rank}(D^{*}) \le k$ and such that $$ \left\|A-D^{*}\right\|_{\xi}^{2} \le \min_{D:\mathrm{rank}(D)\le k} \left\|A-D\right\|_{\xi}^{2} + poly(k,1/c) \left\|{A}\right\|^2_F $$ holds with high probability for both $\xi = 2,F$. This algorithm may be implemented without storing the matrix A in random access memory (RAM), provided it can make two passes over the matrix stored in external memory and use $O(cm+c^2)$ additional RAM. The second algorithm is similar except that it further approximates the matrix C by randomly sampling r rows of C to form a $r \times c$ matrix W. Thus, it has additional error, but it can be implemented in three passes over the matrix using only constant additional RAM. To achieve an additional error (beyond the best rank k approximation) that is at most $\epsilon\|{A}\|^2_F$, both algorithms take time which is polynomial in k, $1/\epsilon$, and $\log(1/\delta)$, where $\delta>0$ is a failure probability; the first takes time linear in $\mbox{max}(m,n)$ and the second takes time independent of m and n. Our bounds improve previously published results with respect to the rank parameter k for both the Frobenius and spectral norms. In addition, the proofs for the error bounds use a novel method that makes important use of matrix perturbation theory. The probability distribution over columns of A and the rescaling are crucial features of the algorithms which must be chosen judiciously.

In many applications, the data consist of (or may be naturally formulated as) an $m \times n$ matrix A which may be stored on disk but which is too large to be read into random access memory (RAM) or to practically perform superlinear polynomial time computations on it. Two algorithms are presented which, when given an $m \times n$ matrix A, compute approximations to A which are the product of three smaller matrices, C, U, and R, each of which may be computed rapidly. Let $A' = CUR$ be the computed approximate decomposition; both algorithms have provable bounds for the error matrix $A-A'$. In the first algorithm, c columns of A and r rows of A are randomly chosen. If the $m \times c$ matrix C consists of those c columns of A (after appropriate rescaling) and the $r \times n$ matrix R consists of those r rows of A (also after appropriate rescaling), then the $c \times r$ matrix U may be calculated from C and R. For any matrix X, let $\|X\|_F$ and $\|X\|_2$ denote its Frobenius norm and its spectral norm, respectively. It is proven that $$ \left\|A-A'\right\|_\xi \le \min_{D:\mathrm{rank}(D)\le k} \left\|A-D\right\|_\xi + poly(k,1/c) \left\|A\right\|_F $$ holds in expectation and with high probability for both $\xi = 2,F$ and for all $k=1,\ldots,\mbox{rank}(A)$; thus by appropriate choice of k $$ \left\|A-A'\right\|_2 \le \epsilon \left\|A\right\|_F $$ also holds in expectation and with high probability. This algorithm may be implemented without storing the matrix A in RAM, provided it can make two passes over the matrix stored in external memory and use $O(m+n)$ additional RAM (assuming that c and r are constants, independent of the size of the input). The second algorithm is similar except that it approximates the matrix C by randomly sampling a constant number of rows of C. Thus, it has additional error but it can be implemented in three passes over the matrix using only constant additional RAM. To achieve an additional error (beyond the best rank-k approximation) that is at most $\epsilon \|A\|_F$, both algorithms take time which is a low-degree polynomial in k, $1/\epsilon$, and $1/\delta$, where $\delta>0$ is a failure probability; the first takes time linear in $\mbox{max}(m,n)$ and the second takes time independent of m and n. The proofs for the error bounds make important use of matrix perturbation theory and previous work on approximating matrix multiplication and computing low-rank approximations to a matrix. The probability distribution over columns and rows and the rescaling are crucial features of the algorithms and must be chosen judiciously.

We present a divide-and-merge methodology for clustering a set of objects that combines a top-down “divide” phase with a bottom-up “merge” phase. In contrast, previous algorithms use either top-down or bottom-up methods to construct a hierarchical clustering or produce a flat clustering using local search (e.g., k -means). For the divide phase, which produces a tree whose leaves are the elements of the set, we suggest an efficient spectral algorithm. When the data is in the form of a sparse document-term matrix, we show how to modify the algorithm so that it maintains sparsity and runs in linear space. The merge phase quickly finds the optimal partition that respects the tree for many natural objective functions, for example, k -means, min-diameter, min-sum, correlation clustering, etc. We present a thorough experimental evaluation of the methodology. We describe the implementation of a meta-search engine that uses this methodology to cluster results from web searches. We also give comparative empirical results on several real datasets.

We present a divide-and-merge methodology for clustering a set of objects that combines a top-down "divide" phase with a bottom-up "merge" phase. In contrast, previous algorithms either use top-down or bottom-up methods to construct a hierarchical clustering or produce a flat clustering using local search (e.g., k-means). Our divide phase produces a tree whose leaves are the elements of the set. For this phase, we use an efficient spectral algorithm. The merge phase quickly finds an optimal tree-respecting partition for many natural objective functions, e.g., k-means, min-diameter, min-sum, correlation clustering, etc., We present a meta-search engine that uses this methodology to cluster results from web searches. We also give empirical results on text-based data where the algorithm performs better than or competitively with existing clustering algorithms.

The only general class of MAX-rCSP problems for which Polynomial Time Approximation Schemes (PTAS) are known are the dense problems. In this paper, we give PTAS's for a much larger class of weighted MAX-rCSP problems which includes as special cases the dense problems and, for r = 2, all metric instances (where the weights satisfy the triangle inequality) and quasimetric instances; for r > 2, our class includes a generalization of metrics. Our algorithms are based on low-rank approximations with two novel features: (1) a method of approximating a tensor by the sum of a small number of "rank-1" tensors, akin to the traditional Singular Value Decomposition (this might be of independent interest) and (2) a simple way of scaling the weights. Besides MAX-rCSP problems, we also give PTAS's for problems with a constant number of global constraints such as maximum weighted graph bisection and some generalizations.

We consider the problem of approximating a given m × n matrix A by another matrix of specified rank k , which is smaller than m and n . The Singular Value Decomposition (SVD) can be used to find the "best" such approximation. However, it takes time polynomial in m, n which is prohibitive for some modern applications. In this article, we develop an algorithm that is qualitatively faster, provided we may sample the entries of the matrix in accordance with a natural probability distribution. In many applications, such sampling can be done efficiently. Our main result is a randomized algorithm to find the description of a matrix D * of rank at most k so that holds with probability at least 1 − δ (where |·| F is the Frobenius norm). The algorithm takes time polynomial in k ,1/ϵ, log(1/δ) only and is independent of m and n . In particular, this implies that in constant time, it can be determined if a given matrix of arbitrary size has a good low-rank approximation.

We motivate and develop a natural bicriteria measure for assessing the quality of a clustering that avoids the drawbacks of existing measures. A simple recursive heuristic is shown to have poly-logarithmic worst-case guarantees under the new measure. The main result of the article is the analysis of a popular spectral algorithm. One variant of spectral clustering turns out to have effective worst-case guarantees; another finds a "good" clustering, if one exists.

We present a new efficient sampling method for approximating r-dimensional Maximum Constraint Satisfaction Problems, MAX-rCSP, on n variables up to an additive error εnr. We prove a newgeneral paradigm in that it suffices, for a given set of constraints, to pick a small uniformly random subset of its variables, and the optimum value of the subsystem induced on these variables gives (after a direct normalization and with high probability) an approximation to the optimum of the whole system up to an additive error of εnr. Our method gives for the first time a polynomial in ε—1 bound on the sample size necessary to carry out the above approximation. Moreover, this bound is independent in the exponent on the dimension r. The above method gives a completely uniform sampling technique for all the MAX-rCSP problems, and improves the best known sample bounds for the low dimensional problems, like MAX-CUT. The method of solution depends on a new result on t he cut norm of random subarrays, and a new sampling technique for high dimensional linear programs. This method could be also of independent interest.

Given an m x n matrix A and an n x p matrix B, we present 2 simple and intuitive algorithms to compute an approximation P to the pr oductA·B, with provable bounds for the norm of the err or matrix "P- A·B. Both algorithms run in O(mp+mn+np) time. In both algorithms, we randomly pick s = O(1) columns of A to form an m x s matrix S and the corresponding rows of B to form an s x p matrix R. After scaling the columns of S and the rows of R, we multiply them together to obtain our approximation P. The choice of the probability distribution we use for picking the columns of A and the scaling are the crucial features which enable us to give fairly elementary proofs of the error bounds. Our first algorithm can be implemented without storing the matrices A and B in Random Access Memory, provided we can make two passes through the matrices (stored in external memory). The second algorithm has a smaller bound on the 2-norm of the error matrix, but requires storage of A and B in RAM. We also present a fast algorithm that "describes" P as a sum of rank one matrices if B = AT.

Mixtures of gaussian (or normal) distributions arise in a variety of application areas. Many techniques have been proposed for the task of finding the component gaussians given samples from the mixture, such as the EM algorithm, a local-search heuristic from Dempster, Laird and Rubin~(1977). However, such heuristics are known to require time exponential in the dimension (i.e., number of variables) in the worst case, even when the number of components is $2$.

We propose a new measure for assessing the quality of a clustering. A simple heuristic is shown to give worst-case guarantees under the new measure. Then we present two results regarding the quality of the clustering found by a popular spectral algorithm. One proffers worst case guarantees whilst the other shows that if there exists a "good" clustering then the spectral algorithm will find one close to it.

The notion of conductance introduced by Jerrum and Sinclair [JS] has been widely used to prove rapid mixing of Markov chains.Here we introduce a variant of this -instead of measuring the conductance of the worst subset of states, we show that it is enough to bound a certain weighted a~wage conductance (where the average is taken over subsets of states with different sizes.)In the case of convex bodies, we show that this average conductance is better than the known bounds for the worst cage; this helps us save a factor of O(n) which is incurred in all proofs as a 'penalty" for a "bad start" (i.e., because the starting distribution may be arbitrary).We show that in a convex body in !R", with diameter D, random walk with steps in a ball with radius 6 mixes in O'(nD2/$) time (if idle steps at the boundary are not counted).This gives an O'(n3) sampling algorithm after appropriate preprocessing, improving the previous bound of O'(n').

We describe a deterministic polynomial-time algorithm which, for a convex body K in Euclidean n-space, finds upper and lower bounds on K's diameter which differ by a factor of O(/spl radic/n/logn). We show that this is, within a constant factor, the best approximation to the diameter that a polynomial-time algorithm can produce even if randomization is allowed. We also show that the above results hold for other quantities similar to the diameter-namely; inradius, circumradius, width, and maximization of the norm over K. In addition to these results for Euclidean spaces, we give tight results for the error of deterministic polynomial-time approximations of radii and norm-maxima for convex bodies in finite-dimensional l/sub p/ spaces.

In several applications, the data consists of an m/spl times/n matrix A and it is of interest to find an approximation D of a specified rank k to A where, k is much smaller than m and n. Traditional methods like the Singular Value Decomposition (SVD) help us find the "best" such approximation. However, these methods take time polynomial in m, n which is often too prohibitive. In this paper, we develop an algorithm which is qualitatively faster provided we may sample the entries of the matrix according to a natural probability distribution. Indeed, in the applications such sampling is possible. Our main result is that we can find the description of a matrix D* of rank at most k so that /spl par/A-D*/spl par//sub F//spl les/min/D,rank(D)/spl les/k/spl par/A-D/spl par//sub F/+/spl epsiv//spl par/A/spl par//sub F/ holds with probability at least 1-/spl delta/. (For any matrix M, /spl par/M/spl par//sub F//sup 2/ denotes the sum of the squares of all the entries of M.) The algorithm takes time polynomial in k, 1//spl epsiv/, log(1//spl delta/) only, independent of m, n.

In this paper we analyse two very simple techniques to minimize a linear function over a convex set. The first is a deterministic algorithm based on gradient descent. The second is a randomized algorithm which makes a small local random change at every step. The second method can be used when the convex set is presented by just a membership oracle whereas the first requires something similar to a separation oracle. We define a simple notation of smoothness of convex sets and show that both algorithms provide a near optimal solution for smooth convex sets in polynomial time. We describe several application examples from linear and stochastic programming where the relevant sets are indeed smooth and thus our algorithms apply. The main point of the paper is that such simple algorithms yield good running time bounds for natural problems.

When is the volume of a convex polytope in R' close to the number of lattice points in the polytope?We show that if the polytope contains a ball of radius n-, where m is the number of facets, then the volume approximates the number of lattice points to within a constant factor.This general condition is then specialized to derive polynomial time sampling and counting algorithms for various combL natorird problems whose solutions can be viewed as lattice points of convex polytopea.We also show, via tight examples, that our condition is essentially the beat possible.

The authors consider the problem of learning a linear threshold function (a halfspace in n dimensions, also called a "perceptron"). Methods for solving this problem generally fall into two categories. In the absence of noise, this problem can be formulated as a linear program and solved in polynomial time with the ellipsoid algorithm (or interior point methods). On the other hand, simple greedy algorithms such as the perceptron algorithm seem to work well in practice and can be made noise tolerant; but, their running time depends on a separation parameter (which quantifies the amount of "wiggle room" available) and can be exponential in the description length of the input. They show how simple greedy methods can be used to find weak hypotheses (hypotheses that classify noticeably more than half of the examples) in polynomial time, without dependence on any separation parameter. This results in a polynomial-time algorithm for learning linear threshold functions in the PAC model in the presence of random classification noise. The algorithm is based on a new method for removing outliers in data. Specifically, for any set S of points in R/sup n/, each given to b bits of precision, they show that one can remove only a small fraction of S so that in the remaining set T, for every vector v, max/sub x/spl epsiv/T/(v/spl middot/x)/sup 2//spl les/poly(n,b)|T|/sup -1//spl Sigma//sub x/spl epsiv/T/(v/spl middot/x)/sup 2/. After removing these outliers, they are able to show that a modified version of the perceptron learning algorithm works in polynomial time, even in the presence of random classification noise.

We present a polynomial time algorithm to learn (in Valiant's PAC model) an arbitrarily oriented cube in n-space, given uniformly distributed sample points from it. In fact, we solve the more general problem of learning, in polynomial time, a linear (affine) transformation of a product distribution.

There are two main contributions of the present paper. In the first, we use the constructive version of the Regularity Lemma to give directly simple polynomial time approximation schemes for several graph "subdivision" problems in dense graphs including the Max Cut problem, the Graph Bisection problem, the Min l-way cut problem and Graph Separator problem. Arora, Karger and Karpinski (1992) gave the first PTASs for these problems whose running time is O(n/sup o(1/e2)/). Our PTASs have running time where the exponent of n is a constant independent of e. The central point here is that the Regularity Lemma provides an explanation of why these Max-SNP hard problems turn out to be easy in dense graphs. We also give a simple PTAS for dense versions of a special case of the Quadratic Assignment Problem (QAP).

This paper deals with the normal density of n dependent random variables. This is a function of the form: ce(-x/sup T/Ax) where A is an n/spl times/n positive definite matrix, a: is the n-vector of the random variables and c is a suitable constant. The first problem we consider is the (approximate) evaluation of the integral of this function over the positive orthant /spl int/(x/sub 1/=0)/sup /spl infin///spl int/(x/sub 2/=0)/sup /spl infin///spl middot//spl middot//spl middot//spl int/(x/sub n/=0)/sup /spl infin//ce(-x/sup T/Ax). This problem has a long history and a substantial literature. Related to it is the problem of drawing a sample from the positive orthant with probability density (approximately) equal to ce(-x/sup T/Ax). We solve both these problems here in polynomial time using rapidly mixing Markov Chains. For proving rapid convergence of the chains to their stationary distribution, we use a geometric property called the isoperimetric inequality. Such an inequality has been the subject of recent papers for general log-concave functions. We use these techniques, but the main thrust of the paper is to exploit the special property of the normal density to prove a stronger inequality than for general log-concave functions. We actually consider first the problem of drawing a sample according to the normal density with A equal to the identity matrix from a convex set K in R/sup n/ which contains the unit ball. This problem is motivated by the problem of computing the volume of a convex set in a way we explain later. Also, the methods used in the solution of this and the orthant problem are similar.

This paper outlines the use of rapidly mixing Markov Chains in randomized polynomial time algorithms to solve approximately certain counting problems. They fall into two classes: combinatorial problems like counting the number of perfect matchings in certain graphs and geometric ones like computing the volumes of convex sets.>

We present a polynomial-time algorithm to learn an intersection of a constant number of halfspaces in n dimensions, over the uniform distribution on an n-dimensional ball. The algorithm we present in fact can learn an intersection of an arbitrary (polynomial) number of halfspaces over this distribution, if the subspace spanned by the normal vectors to the bounding hyperplanes has constant dimension. This generalizes previous results for this distribution, in particular a result of E.B. Baum (1990) who showed how to learn an intersection of 2 halfspaces defined by hyperplanes that pass through the origin (his results in fact held for a variety of symmetric distributions). Our algorithm uses estimates of second moments to find vectors in a low-dimensional "relevant subspace". We believe that the algorithmic techniques studied here may be useful in other geometric learning applications.>

An important class of functions that arise in statistics and other areas are the log-concave functions.Here we provide the first polynomial time algorithm to generate samples from a given log-concave distribution.The algorithm is fairly simple and natural; it is the proof of its fast convergence that is new.To this end, we prove a general isoperimetric inequality for convex sets and use this together with recent developments in the theory of rapidly mixing Markov chains.We use our sampling algorithm to develop an algorithm for integrating log-concave functions.As one application, we are able to develop an algorithm for approximating the volume of convex bodies given by an oracle; we do so by enclosing the given body in a cube, defining a log-concave function that is 1 on the body and exponentially falls off outside, and integrating this function.This a.llo ws us to avoid one of the complications in prior algorithms for computing volumes -dealing with sharp corners -and results in an algorithm which is faster than previous algorithms.

A randomized polynomial-time algorithm for approximating the volume of a convex body K in n -dimensional Euclidean space is presented. The proof of correctness of the algorithm relies on recent theory of rapidly mixing Markov chains and isoperimetric inequalities to show that a certain random walk can be used to sample nearly uniformly from within K .

We present a randomised polynomial time algorithm for approximating the volume of a convex body K in n-dimensional Euclidean space. The proof of correctness of the algorithm relies on recent theory of rapidly mixing Markov chains and isoperimetric inequalities to show that a certain random walk can be used to sample nearly uniformly from within K.

We show that the following statements are equivalent: Statement 1. 3-pushdown graphs have sublinear separators. Statement 1∗. k-page graphs have sublinear separators. Statement 2. A one-tape nondeterministic Turing machine can simulate a two-tape machine in subquadratic time. None of the statements is known to be true or false at present. However, our proof of equivalence is quantitative-it relates exactly the separator size of the two kinds of graphs to the running time of the simulation in Statement 2. Using this equivalence we derive several graph-theoretic corollaries. There are known examples where upper bounds on graph properties imply upper bounds on computation time or space. There are other examples where lower bounds on graph properties are used to derive lower bounds on computation time in restricted settings. However, our results may constitute the first example where a graph problem is shown to be equivalent to a problem in computational complexity. In a companion paper we construct graphs and prove a lower bound or their separators. Using the equivalence we prove an almost linear lower bound for the size of separators for 3-pushdown graphs and an almost quadratic lower bound for simulating two-tape nondeterministic Turing machines by one-tape machines. Specifically, for an integers s let ls(n), the s-iterated logarithm function, be defined inductively: l°(n)=n, ls+1(n)=log2(ls(n)) for s⩾0. Then: For every fixed s and all n, there is an n-vertex 3-pushdown graph whose smallest separator contains at least ω(n/ls(n)) vertices. There is a language L recognizable in real time by a two-tape nondeterministic Turing machine, but every on-line one-tape nondeterministic Turing machine that recognizes L requires ω(n2/ls(n)) time for any positive integer.

Given n natural numbers $a_1 , \cdots ,a_n $ and a target integer b, the SubsetSum problem is to determine whether some subset of the $a_i $; sums to b. That is, to recognize members of the following set: \[ {\text{SubsetSum}} = \left\{ \left\langle {a_1 , \cdots ,a_n ;b} \right\rangle |a_i \in {\bf N} b \in {\bf Z},{\text{ and }}\exists x \in \{ 0,1\} ^n {\text{ such that }} a \cdot x = b \right\} . \] For a given vector $a = (a_1 , \cdots ,a_n )$ and integer b, if a subset of the $a_i $ sums to b, then listing which subset provides a short proof that $\langle {a;b} \rangle \in {\text{SubsetSum}}$. However, in general there are no short (polynomial-length) proofs of nonmembership unless NP equals coNP. The main result in this paper provides a proof system that contains polynomial-length nonmembership proofs for a vast majority of the problem instances that do not belong to SubsetSum.

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.

The paper presents a sublinear time parallel algorithm for computing the greatest common divisor of two integers. Its running time on two n bit integers is $O({{n\log \log n} / {\log n}})$ using the weak concurrent read concurrent write model.

We show that the following statements are equivalent :Statement 1: 3-pushdown graphs have sublinear separators.

The accessibility problem for linear sequential machines [12] is the problem of deciding whether there is an input x such that on x the machine starting in a given state q 1 goes to a given state q 2 . Harrison shows that this problem is reducible to the following simply stated linear algebra problem, which we call the "orbit problem": Given ( n, A, x, y ), where n is a natural number and A, x, and y are n x n , n x 1, and n x 1 matrices of rationals, respectively, decide whether there is a natural number I such that A i x = y . He conjectured that the orbit problem is decidable. No progress was made on the conjecture for ten years until Shank [22] showed that if n is fixed at 2, then the problem is decidable. This paper shows that the orbit problem for general n is decidable and indeed decidable in polynomial time. The orbit problem arises in several contexts; two of these, linear recurrences and the discrete logarithm problem for polynomials, are discussed, and we apply our algorithm for the orbit problem in these contexts.

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 advent of practical parallel processors has caused a reexamination of many existing algorithms with the hope of discovering a parallel implementation. One of the oldest and best known algorithms is Euclid's algorithm for computing the greatest common divisor (GCD). In this paper we present a parallel algorithm to compute the GCD of two integers. The two salient features of the algorithm are: the observation based on the pigeon hole principle that we can easily find an integer combination of the two integers A and B which has fewer bits than n and the idea of working in phases so as to perform arithmetics on n-bit integers only once every phase, the more frequent operations being performed on O(log/sup 2/n)-bit integers. It appears that yet another approach is needed if the GCD is to be computed in poly-log parallel time.

It is shown that the binary expansions of algebraic numbers do not form secure pseudorandom sequences, given sufficiently many initial bits of an algebraic number, its minimal polynomial can be reconstructed, and therefore the further bits of the algebraic number can be computed. This also enables the authors to devise a simple algorithm to factorise polynomials with rational coefficients. All algorithms work in polynomial time

The integer programming problem is: Given m×n and m×l matrices A and b respectively of integers, find whether, there exists an all integer n×l vector x satisfying the m inequalities A×≤b. In settling an important open problem, Lenstra (1981) showed in an elegant way that when n, the number of dimensions is fixed, there is a polynomial-time algorithm to solve this problem. His algorithm achieves a running-time of 0(cn3•p(length of data)) where p is some polynomial and c a constant independent of n. Since such an algorithm has several important applications - cryptography (Shamir (1982)), diophantine approximations (Lagarias (1982)), coding theory (Conway and Sloane (1982), etc. it is important to improve the running time. We present an algorithm here that has a running time of 0(n9nL log L) where L is the length of the input. Whereas Lenstra's algorithm in the worst case reduces an n-dimensional problem to cn2−(n−) dimensional problems, our algorithm effectively reduces an n-dimensional problem to at most polynomially many (n−1) dimensional problems, thus achieving our time bound. The algorithm we propose, first finds a “more orthogonal” basis for a lattice (see the next section for the definition of a lattice) than those of Lenstra (1981) and Lenstra, Lenstra and Lovasz (1982), but in time 0(ndn poly (length of input)). It then uses an enumeration technique to solve integer programming and related problems.

While nondeterminism is widely beleived to be more powerful than determinism in various contexts (the most famous being the conjecture that NP strictly contains P), no proof of the added power of nondeterminism is available for any significant issue. The weaker conjecture (than NP strictly contains P) that there is a language accepted by a nondeterministic linear time bounded multitape Turing Machine that cannot be accepted by a deterministic linear time bounded multi-tape TM still seems quite hard (Paul 1982). The aim of this paper is to show how the existance of the polynomial-time hierarchy of Meyer and Stockmeyer(1972) and the related concept of alternation (Chandra, Kozen and Stockmeyer(1981)) can be exploited to prove the power of nondeterminism over determinism in some contexts. It is hoped that this approach may be useful in proving stronger results.

It ts shown that a set of linear Dtophantme equations m nonnegative variables with nonnegative coefficients can be reduced to a single equation with the same solution set in polynomial time.A weaker verston of the above statement ~s shown to be true when the coefficients are allowed to be negative Besides being polynomial-trine bounded, the present aggregation scheme differs from existing ones in that the final equation is m variables that are not exphcltly bounded Three applications of this aggregation technique are presented: (i) ~t Is proved that a certain type of knapsack problem cannot have a polynomialtune approxtmatlon algorithm unless NP = P; 00 an analog of Farkas' lemma for integer programming is proved; and 0ii) ~t is shown that a decision problem revolving integer variables is NP-complete.

It would be of interest to separate nondeterminism from determinism i.e., to show that for all "nice" functions t(n), NTIME (t(n)), (the class of languages accepted by multitape nondeterministic Turing machines in time O(t(n))) strictly contains DTIME (t(n)) (the class of languages accepted by multitape deterministic Turing machines in time O(t(n)). We establish a weaker form of the statement. We show that there is a universal constant k such that for all "nice" functions t(n), the class of languages that can be accepted simultaneously in deterministic time O(t(n)) and space o((t(n))1/k) is strictly contained in NTIME (t(n)). (We will use the notation SPACE, TIME (s(n),t(n)) to denote the class of languages accepted by a deterministic TM in time O(t(n)) and simultaneously space O(s(n)).) This result is proved using a time-alternation trade-off and several other applications of this trade-off are presented. For example, we show that for each language L in SPACE, TIME (nl-ε, ni) (where o≪ε≪l, ε, i constants) there exists a j such that L is accepted by a O(n) time bounded alternating Turing machine with j alternations. The trade-off also leads to the separation ∪SεSt SPACE, TIME (s,t)⊂+Σ2 TIME(t) where t(n) is any "nice" function and St is a class of "nice" functions in o(t). Here St includes most natural functions for natural t. For example, nj/log*n is in Snj.

As remarked in Cook (1980), we do not know any nonlinear lower bound on the circuit size of a language in P or even in NP. The best known lower bound seems to be due to Paul (1975). Instead of trying to prove lower bounds on the circuit-size of a "natural" language, this note raises the question of whether some language in a class is of provably high circuit complexity. We show that for each nonnegative integer k, there is a language Lk in Σ2P ∩ π2P (of the Meyer and Stockmeyer (1972) hierarchy) Which does not have O(nk)-size circuits. The method is indirect and does not produce the language Lk. Other results of a similar nature are presented and several questions raised.

The “accessibility problem” for linear sequential machines (Harrison [7]) is the problem of deciding whether there is an input x that sends such a machine from a given state q1 to a given state q2. Harrison [7] showed that this problem is reducible to the “orbit problem:” Given AεQn×n does there exist iεN such that Aix =y.* We will call this the “orbit problem” because the question can be rephrased as: Does y belong to the orbit of x under A where the “orbit of x under A” is the set {Aix: i = 0,1,2,...}. (A0 is the identity matrix I.) In Harrison's original problem the elements of A,x, and y were members of an arbitrary “computable” field. In view of the lack of structure of such fields, we study only the rationals. Shank [13] proves that the orbit problem is decidable for the rational case when n=2. The current paper establishes that for the general rational case, the problem is decidable - and in fact polynomial-time decidable.

A polynomial time algorithm is presented for solving the following two-variable integer programming problem maximize ClXl + c2x2 subject to a, lxl + a,2x2 =< b,, I = 1, 2, , n, and x~, x2 => O, integers, where a,j, cj, and b, are assumed to be nonnegattve integers This generahzes a result of Htrschberg and Wong, who developed a polynomial algorithm for the same problem with only one constraint (l e, where n = 1) However, the techniques used here are quite different

Recently, Frumkin [9] pointed out that none of the well-known algorithms that transform an integer matrix into Smith [16] or Hermite [12] normal form is known to be polynomially bounded in its running time. In fact, Blankinship [3] noticed—as an empirical fact—that intermediate numbers may become quite large during standard calculations of these canonical forms. Here we present new algorithms in which both the number of algebraic operations and the number of (binary) digits of all intermediate numbers are bounded by polynomials in the length of the input data (assumed to be encoded in binary). These algorithms also find the multiplier-matrices K, $U'$ and $K'$ such that $AK$ and $U'AK'$ are the Hermite and Smith normal forms of the given matrix A. This provides the first proof that multipliers with small enough entries exist.