We design two deterministic polynomial time algorithms for variants of a problem introduced by Edmonds in 1967: determine the rank of a matrix M whose entries are homogeneous linear polynomials over the integers. Given a linear subspace B of the nxn matrices over some field F, we consider the following problems: symbolic matrix rank (SMR) is the problem to determine the maximum rank among matrices in B, while symbolic determinant identity testing (SDIT) is the question to decide whether there exists a nonsingular matrix in B. The constructive versions of these problems are asking to find a matrix of maximum rank, respectively a nonsingular matrix, if there exists one. Our first algorithm solves the constructive SMR when B is spanned by unknown rank one matrices, answering an open question of Gurvits. Our second algorithm solves the constructive SDIT when B is spanned by triangularizable matrices, but the triangularization is not given explicitly. Both algorithms work over finite fields of size at least n+1 and over the rational numbers, and the first algorithm actually solves (the non-constructive) SMR independent of the field size. Our main tool to obtain these results is to generalize Wong sequences, a classical method to deal with pairs of matrices, to the case of pairs of matrix spaces.

In this paper we describe a new efficient (in fact optimal) data structure for the top-K color problem. Each element of an array A is assigned a color c with priority p(c). For a query range [a, b] and a value K, we have to report K colors with the highest priorities among all colors that occur in A[a‥b], sorted in reverse order by their priorities. We show that such queries can be answered in O(K) time using an O(N log σ) bits data structure, where N is the number of elements in the array and σ is the number of colors. Thus our data structure is asymptotically optimal with respect to the worst-case query time and space. As an immediate application of our results, we obtain optimal time solutions for several document retrieval problems. The method of the paper could be also of independent interest.

We present new deterministic algorithms for several cases of the maximum rank matrix completion problem (for short matrix completion), i.e., the problem of assigning values to the variables in a given symbolic matrix to maximize the resulting matrix rank. Matrix completion is one of the fundamental problems in computational complexity. It has numerous important algorithmic applications, among others, in computing dynamic transitive closures or multicast network codings [N. J. A. Harvey, D. R. Karger, and K. Murota, Proceedings of the Sixteenth Annual ACM-SIAM Symposium on Discrete Algorithms, 2005, pp. 489–498; N. J. A. Harvey, D. R. Karger, and S. Yekhanin, Proceedings of the Seventeenth Annual ACM-SIAM Symposium on Discrete Algorithms, 2006, pp. 1103–1111]. We design efficient deterministic algorithms for common generalizations of the results of Lovász and Geelen on this problem by allowing linear polynomials in the entries of the input matrix such that the submatrices corresponding to each variable have rank one. Our methods are algebraic and quite different from those of Lovász and Geelen. We look at the problem of matrix completion in the more general setting of linear spaces of linear transformations and find a maximum rank element there using a greedy method. Matrix algebras and modules play a crucial role in the algorithm. We show (hardness) results for special instances of matrix completion naturally related to matrix algebras; i.e., in contrast to computing isomorphisms of modules (for which there is a known deterministic polynomial time algorithm), finding a surjective or an injective homomorphism between two given modules is as hard as the general matrix completion problem. The same hardness holds for finding a maximum dimension cyclic submodule (i.e., generated by a single element). For the “dual” task, i.e., finding the minimal number of generators of a given module, we present a deterministic polynomial time algorithm. The proof methods developed in this paper apply to fairly general modules and could also be of independent interest.

In this paper we study the adaptive prefix coding problem in cases where the size of the input alphabet is large. We present an online prefix coding algorithm that uses O(sigma1/lambda+epsiv) bits of space for any constants epsiv > 0, > 1, and encodes the string of symbols in O(loglog sigma) time per symbol in the worst case, where sigma is the size of the alphabet. The upper bound on the encoding length is lambdanH(s) + (lambda/ ln 2 + 2 + epsiv)n + O(sigma1/lambdalog2sigma) bits.

In this work we relate the deterministic complexity of factoring polynomials (over finite fields) to certain combinatorial objects we call m-schemes. We extend the known conditional deterministic subexponential time polynomial factoring algorithm for finite fields to get an underlying m-scheme. We demonstrate how the properties of m-schemes relate to improvements in the deterministic complexity of factoring polynomials over finite fields assuming the generalized Riemann Hypothesis (GRH). In particular, we give the first deterministic polynomial time algorithm (assuming GRH) to find a nontrivial factor of a polynomial of prime degree n where (n-1) is a smooth number.

We design a linear time approximation scheme for the Gale-Berlekamp Switching Game and generalize it to a wider class of dense fragile minimization problems including the Nearest Codeword Problem (NCP) and Unique Games Problem. Further applications include, among other things, finding a constrained form of matrix rigidity and maximum likelihood decoding of an error correcting code. As another application of our method we give the first linear time approximation schemes for correlation clustering with a fixed number of clusters and its hierarchical generalization. Our results depend on a new technique for dealing with small objective function values of optimization problems and could be of independent interest.

In this paper we present a new algorithm for adaptive prefix coding. Our algorithm encodes a text S of m symbols in O(m) time, i.e., in O(1) time per symbol. The length of the encoded string is bounded above by (H + 1)m + O(nlog2m) bits where n is the alphabet size and H is the entropy. This is the first algorithm that works in O(m) time and achieves an almost optimal bound on the encoding length in the worst case. Besides that our algorithm does not depend on the explicit tree traversal

Summary form only given. We present a parallel algorithm for the construction of minimum redundancy length-restricted codes that is based on the package-merge algorithm of Larmore and Hirschberg (1990). Our algorithm constructs a length-restricted code in O(L) time with n processors on a CREW PRAM. Thus our algorithm has the same time-processor product as the sequential algorithm of (1990). We also consider the problem of constructing the almost-optimal length-restricted codes.

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.

The max-bisection and min-bisection problems are to find a partition of the vertices of a graph into two equal size subsets that, respectively, maximizes or minimizes the number of edges with endpoints in both subsets. We design the first polynomial time approximation scheme for the max-bisection problem on arbitrary planar graphs solving a long-standing open problem. The method of solution involves designing exact polynomial time algorithms for computing optimal partitions of bounded treewidth graphs, in particular max- and min-bisection, which could be of independent interest. Using a similar method we design also the first polynomial timeapproximation scheme for max-bisection on unit disk graphs (which could also be easily extended to other geometrically defined graphs).

Let k be a fixed integer. We consider the problem of partitioning an input set of points endowed with a distance function into k clusters. We give polynomial time approximation schemes for the following three clustering problems: Metric k-Clustering, l 22k-Clustering, and l22k-Median. In the k-Clustering problem, the objective is to minimize the sum of all intra-cluster distances. In the k-Median problem, the goal is to minimize the sum of distances from points in a cluster to the (best choice of) cluster center. In metric instances, the input distance function is a metric. In l 22 instances, the points are in R d and the distance between two points x,y is measured by x−y22 (notice that (R d, ⋅ 22 is not a metric space). For the first two problems, our results are the first polynomial time approximation schemes. For the third problem, the running time of our algorithms is a vast improvement over previous work.

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.

AbatractWe prove the first exponential lower bound on the size of any depth 3 arithmetic circuit with unbounded fanin computing an explicit function (the determinant) over an arbitrary finite field.This answers an open problem of [N91] and [NW951 for the cs~e of finite fields.We intepret here arithmetic circuits in the algebra of polynomials over the given field.The proof method involves a new argument on the rank of linear functions, and a group symmetry on polynomials vanishing at certain nonsingular matrices, and could be of independent interest.

We prove that a single threshold gate with arbitrary weights can be simulated by an explicit polynomial-size, depth-2 majority circuit. In general we show that a polynomial-size, depth-d threshold circuit can be simulated uniformly by a polynomial-size majority circuit of depth d + 1. Goldmann, Håstad, and Razborov showed in [Comput. Complexity, 2 (1992), pp. 277--300] that a nonuniform simulation exists. Our construction answers two open questions posed by them: we give an explicit construction, whereas they use a randomized existence argument, and we show that such a simulation is possible even if the depth d grows with the number of variables n (their simulation gives polynomial-size circuits only when d is constant).

We design an algorithm for computing the generalized (algebraic circuits with root extracting; cf.\ Pippenger [J. Comput. System Sci., 22 (1981), pp. 454--470], Ja'Ja' [Proc. 22nd IEEE FOCS, 1981, pp. 95--100], Grigoriev, Singer, and Yao [ SIAM J. Comput., 24 (1995), pp. 242--246]) additive complexity of any rational function. It is the first computability result of this sort on the additive complexity of algebraic circuits.

We present polynomial time algorithms for some fundamental tasks from representation theory of finite dimensional algebras.These involve testing (and constructing) isomorphisms of modules aa well as expressing of modules as direct sums of indecomposable modules.Over number fields the latter task seems to be difficult, therefore we restrict our attention to decomposition over finite fields and over the algebraic or real closure of number fields.The module isomorphism problem can be reformulated as follows.Let Al, . . . .Am and A{,. . . .AL be two families of n x n-matrices with entries from the field K.The task is to find a nonsingular n x n-matrix X with entries from K such that XAi X-] = A: for all 1 < i ~m (if such a matrix exists).In the case when K is the field of the real algebraic numbers, we propose a method for the variant where the matrix X is required to be orthogonal, q Research partially supported by the Volkswagen-Stiftung, Program on Computational Complexity.t

We prove Ω(n²) complexity lower bound for the general model of randomized computation trees solving the Knapsack Problem, and more generally Restricted Integer Programming. This is the first nontrivial lower bound proven for this model of computation. The method of the proof depends crucially on the new technique for proving lower bounds on the border complexity of a polynomial which could be of independent interest.

Article Free Access Share on A lower bound for randomized algebraic decision trees Authors: Dima Grigoriev Dept. of Computer Science and Mathematics, Penn State University, University Park Dept. of Computer Science and Mathematics, Penn State University, University ParkView Profile , Marek Karpinski Dept. of Computer Science, University of Bonn, 53117, Bonn Dept. of Computer Science, University of Bonn, 53117, BonnView Profile , Friedhelm Meyer auf der Heide Heinz Nixdorf Institute and Computer Science Department, University of Paderborn, 33098 Paderborn Heinz Nixdorf Institute and Computer Science Department, University of Paderborn, 33098 PaderbornView Profile , Roman Smolensky Dept. of Computer Science, University of Bonn, 53117, Bonn Dept. of Computer Science, University of Bonn, 53117, BonnView Profile Authors Info & Claims STOC '96: Proceedings of the twenty-eighth annual ACM symposium on Theory of ComputingJuly 1996 Pages 612–619https://doi.org/10.1145/237814.238011Published:01 July 1996Publication History 12citation385DownloadsMetricsTotal Citations12Total Downloads385Last 12 Months13Last 6 weeks3 Get Citation AlertsNew Citation Alert added!This alert has been successfully added and will be sent to:You will be notified whenever a record that you have chosen has been cited.To manage your alert preferences, click on the button below.Manage my AlertsNew Citation Alert!Please log in to your account Save to BinderSave to BinderCreate a New BinderNameCancelCreateExport CitationPublisher SiteeReaderPDF

We prove for the first time an existence of the short (polynomial size) proofs for nondivisibility of two sparse polynomials (putting thus this problem is the class NP) under the Extended Riemann Hypothesis. The divisibility problem is closely relate

We introduce a new method of proving lower bounds on the depth of algebraic decision trees of degree d and apply it to prove a lower bound /spl Omega/(log N) for testing membership to an n-dimensional convex polyhedron having N faces of all dimensions, provided that N>(nd)/sup /spl Omega//(n). This weakens considerably the restriction on N previously imposed by the authors and opens a possibility to apply the bound to some naturally appearing polyhedra.

Article Polynomial time approximation schemes for dense instances of NP-hard problems Share on Authors: Sanjeev Arora Princeton University Princeton UniversityView Profile , David Karger MIT Laboratory for Computer Science, AT&T Bell Laboratories MIT Laboratory for Computer Science, AT&T Bell LaboratoriesView Profile , Marek Karpinski University of Bonn University of BonnView Profile Authors Info & Claims STOC '95: Proceedings of the twenty-seventh annual ACM symposium on Theory of computingMay 1995 Pages 284–293https://doi.org/10.1145/225058.225140Online:29 May 1995Publication History 120citation1,159DownloadsMetricsTotal Citations120Total Downloads1,159Last 12 Months4Last 6 weeks1 Get Citation AlertsNew Citation Alert added!This alert has been successfully added and will be sent to:You will be notified whenever a record that you have chosen has been cited.To manage your alert preferences, click on the button below.Manage my AlertsNew Citation Alert!Please log in to your account Save to BinderSave to BinderCreate a New BinderNameCancelCreateExport CitationPublisher SiteGet Access

In this paper we consider real counterparts of classical probabilistic complexity classes in the framework of real Turing machines as introduced by Blum, Shub, and Smale [2].We give an extension of the well-known "BPP ~P/poly" result from discrete complexity theory to a very general setting in the real number model.This result holds for real inputs, real outputs, and random elements drawn from an arbitrary probability distribution over lR~.Then we turn to the study of Boolean parts, that is, classes of languages of zero-one vectors accepted by real machines.In particular we show that the classes BPP, PP, PH, and PSPACE are not enlarged by allowing the use of real constants and arithmetic at unit cost provided we restrict branching to equality tests.

We introduce a new method for proving explicit upper bounds on the VC Dimension of general functional basis networks, and prove as an application, for the first time, the VC Dimension of analog neural networks with the sigmoid activation function o(y) = 1/1 + e-y to be bounded by a quadratic polynomial in the number of programmable parameters.O

Article Free Access Share on Co-learning of total recursive functions Authors: Rūsiņš Freivalds Department of Computer Science, University of Latvia, Raina bulvaris 29, LV-1459, Riga Latvia Department of Computer Science, University of Latvia, Raina bulvaris 29, LV-1459, Riga LatviaView Profile , Marek Karpinski Department of Computer Science, University of Bonn, Römerstrasse 164, D-5300, Bonn 1 Germany Department of Computer Science, University of Bonn, Römerstrasse 164, D-5300, Bonn 1 GermanyView Profile , Carl H. Smith Department of Computer Science, University of Maryland, College Park, MD Department of Computer Science, University of Maryland, College Park, MDView Profile Authors Info & Claims COLT '94: Proceedings of the seventh annual conference on Computational learning theoryJuly 1994 Pages 190–197https://doi.org/10.1145/180139.181098Published:16 July 1994Publication History 8citation28DownloadsMetricsTotal Citations8Total Downloads28Last 12 Months12Last 6 weeks1 Get Citation AlertsNew Citation Alert added!This alert has been successfully added and will be sent to:You will be notified whenever a record that you have chosen has been cited.To manage your alert preferences, click on the button below.Manage my AlertsNew Citation Alert!Please log in to your account Save to BinderSave to BinderCreate a New BinderNameCancelCreateExport CitationPublisher SiteeReaderPDF

We describe a new method of proving lower bounds on the depth of algebraic decision trees and apply it to prove a lower bound \\Omega\\Gammand/ N) for testing membership to a convex polyhedron having N facets of all dimensions, provided that N is large enough. This bound apparently does not follow from the methods developed by M. Ben-Or, A. Bjorner, L. Lovasz, and A. Yao ([B 83], [BLY 92]) because the topological invariants used in these methods become trivial for a convex polyhedra. Departments of Computer Science and Mathematics, Penn State University, University Park, PA 16802, Email: [email protected]. Supported in part by the Volkswagen-- Stiftung. y Department of Computer Science, University of Bonn, 53117 Bonn, and the International Computer Science Institute, Berkeley, California. Research supported in part by DFG Grant KA 673/4--1, by the ESPRIT BR Grants 7097 and ECUS030, and by the Volkswagen-Stiftung. Email: [email protected] z Departments of Computer Science and Mathemat...

The authors analyze the computational complexity of sparse rational interpolation, and give the first deterministic algorithm for this problem with singly exponential bounds on the number of arithmetic operations.

. Some deterministic and probabilistic methods are presented for counting and estimating the number of points on curves over finite fields, and on their projections. The classical question of estimating the size of the image of a univariate polynomial is a special case. For curves given by sparse polynomials, the counting problem is #P-complete via probabilistic parsimonious Turing reductions. 1. Introduction One of the most celebrated results in algebraic geometry is Weil's theorem on the number of points on algebraic curves over a finite field. In this paper, we address some computational problems related to this question. Our main results are: ffi A "computational Weil estimate" for projections of curves and images of polynomials, in Section 3. ffi #P-completeness of the exact counting problem for sparse curves, in Section 4. We consider a finite field F q with q elements, an algebraic closure K of F q , a polynomial f 2 F q [x; y] of degree n , the plane curve C = ff = 0g = f(a;...

We prove that a single threshold gate with arbitrary weights can be simulated by an explicit polynomial-size, depth-2 majority circuit. In general we show that a polynomial-size, depth-d threshold circuit can be simulated uniformly by a polynomial-size majority circuit of depth d + 1. Goldmann, H astad, and Razborov showed in (Comput. Complexity, 2 (1992), pp. 277{300) that a nonuniform simulation exists. Our construction answers two open questions posed by them: we give an explicit construction, whereas they use a randomized existence argument, and we show that such a simulation is possible even if the depth d grows with the number of variables n (their simulation gives polynomial-size circuits only when d is constant).

A read-once formula is a Boolean formula in which each variable occurs, at most, once. Such formulas are also called μ-formulas or Boolean trees. This paper treats the problem of exactly identifying an unknown read-once formula using specific kinds of queries. The main results are a polynomial-time algorithm for exact identification of monotone read-once formulas using only membership queries, and a polynomial-time algorithm for exact identification of general read-once formulas using equivalence and membership queries (a protocol based on the notion of a minimally adequate teacher [1]). The results of the authors improve on Valiant's previous results for read-once formulas [26]. It is also shown, that no polynomial-time algorithm using only membership queries or only equivalence queries can exactly identify all read-once formulas.

The authors prove upper and lower bounds on the VC dimension of sparse univariate polynomials over reals and apply these results to prove uniform learnability of sparse polynomials and rational functions. As an application the solution to the open problem of Vapnik [in Estimation of Dependences Based on Empirical Data, Springer-Verlag, Berlin, 1982] on computational approximation of the regression in a class of polynomials used in the theory of empirical data dependences is given.

Article Free Access Share on Existence of short proofs for nondivisibility of sparse polynomials under the extended Riemann hypothesis Authors: Dima Yu. Grigoriev View Profile , Marek Karpinski View Profile , Andrew M. Odlyzko View Profile Authors Info & Claims ISSAC '92: Papers from the international symposium on Symbolic and algebraic computationAugust 1992 Pages 117–122https://doi.org/10.1145/143242.143287Online:01 August 1992Publication History 5citation182DownloadsMetricsTotal Citations5Total Downloads182Last 12 Months2Last 6 weeks0 Get Citation AlertsNew Citation Alert added!This alert has been successfully added and will be sent to:You will be notified whenever a record that you have chosen has been cited.To manage your alert preferences, click on the button below.Manage my AlertsNew Citation Alert!Please log in to your account Save to BinderSave to BinderCreate a New BinderNameCancelCreateExport CitationPublisher SiteeReaderPDF

The authors design the first polynomial time (for an arbitrary and fixed field GF(q)) ( in , delta )-approximation algorithm for the number of zeros of arbitrary polynomial f(x/sub 1/. . . x/sub n/) over GF(q). It gives the first efficient method for estimating the number of zeros and nonzeros of multivariate polynomials over small finite fields other than GF(2) (like GF(3)), the case important for various circuit approximation techniques. The algorithm is based on the estimation of the number of zeros of an arbitrary polynomial f(x/sub 1/. . .,x/sub n/) over GF(q) in the function of the number m of its terms. The bounding ratio is proved to be m/sup (q-1)/log/sup q/.>

We present two algorithms for interpolating sparse rational functions.The first is the interpolation algorithm in a sense of sparse partial fraction representation of rational functions.The second is the algorithm for computing the entier and the remainder of a rational function.The first algorithm works without apriori known bound on the degree of a rational function, the second one is in the parallel class NC provided that the degree is known.The presented algorithms complement the sparse interpolation results of [GKS 90].

The authors present the first algorithm for the (black box) interpolation of t-sparse, n-variate, rational functions without knowing bounds on exponents of their sparse representation, with the number of queries independent of exponents. In fact, the algorithm uses O(nt/sup t/) queries to the black box, and it can be implemented for a fixed t in a polynomially bounded storage (or polynomial parallel time).>

The authors consider the problem of reconstructing (i.e., interpolating) a t-sparse multivariate polynomial given a black box which will produce the value of the polynomial for any value of the arguments. It is shown that, if the polynomial has coefficients in a finite field $GF[q]$ and the black box can evaluate the polynomial in the field $GF[q^{\ulcorner 2\log_{q}(nt)+3 \urcorner}]$, where n is the number of variables, then there is an algorithm to interpolate the polynomial in $O(\log^3 (nt))$ boolean parallel time and $O(n^2 t^6 \log^2 nt)$ processors. This algorithm yields the first efficient deterministic polynomial time algorithm (and moreover boolean $NC$-algorithm) for interpolating t-sparse polynomials over finite fields and should be contrasted with the fact that efficient interpolation using a black box that only evaluates the polynomial at points in $GF[q]$ is not possible (cf. [M. Clausen, A. Dress, J. Grabmeier, and M. Karpinski, Theoret. Comput. Sci., 1990, to appear]). This algorithm, together with the efficient deterministic interpolation algorithms for fields of characteristic 0 (cf. [D. Yu. Grigoriev and M. Karpinski, in Proceedings of the 28th IEEE Symposium on the Foundations of Computer Science, 1987, pp. 166–172], [M. Ben-Or and P. Tiwari, in Proceedings of the 20th ACM Symposium on the Theory of Computing, 1988, pp. 301–309]), yields for the first time the general deterministic sparse conversion algorithm working over arbitrary fields. (The reason for this is that every field of positive characteristic contains a primitive subfield of this characteristic, and so this method can be applied to the slight extension of this subfield.) The method of solution involves the polynomial enumeration techniques of [D. Yu. Grigoriev and M. Karpinski, op. cit.] combined with introducing a new general method of solving the problem of determining if a t-sparse polynomial is identical to zero by evaluating it in a slight extension of the coefficient field (i.e., an extension whose degree over this field is logarithmic in nt).

The first efficient parallel algorithm for computing minimal elimination ordering (MEO) of an arbitrary graph is designed. The algorithm works in O(log/sup 3/n) parallel time and O(nm) processors on a concurrent-read-concurrent-write parallel random-access machine (CRCW PRAM) for an n-vertex, m-edge graph and is optimal up to polylogarithmic factor with respect to the best sequential algorithm of D. Rose et. al. (SIAM J. Comput., vol.5, p.266-83, 1976). As an application, the first efficient parallel solution to the problem of minimal fill-in for arbitrary graphs is given. The method of solution involves the development of new techniques for solving the connected minimal set system problem and combining them with some new divide-and-conquer methods.>

G.A. Dirac's classical theorem (1952) asserts that if every vertex of a graph G on n vertices has degree at least n/2, the G has a Hamiltonian cycle. A fast parallel algorithm on a concurrent-read-exclusive-write parallel random-access machine (CREW PRAM) is given to find a Hamiltonian cycle in such graphs. The algorithm uses a linear number of processors and is optimal up to a polylogarithmic factor. It works in O(log/sup 4/n) parallel time and uses linear number of processors on a CREW PRAM. It is also proved that a perfect matching in dense graphs can be found in NC/sup 2/. The cost of improved time is a quadratic number of processors. It is also proved that finding an NC algorithm for perfect matching in slightly less dense graphs is as hard as the same problem for all graphs, and the problem of finding a Hamiltonian cycle becomes NP-complete.>

It is shown that the problem of deciding and constructing a perfect matching in bipartite graphs G with the polynomial permanents of their n × n adjacency matrices A (perm(A) = nO(1)) are in the deterministic classes NC2 and NC3, respectively. We further design an NC3 algorithm for the problem of constructing all perfect matchings (enumeration problem) in a graph G with a permanent bounded by O(nk). The basic step was the development of a new symmetric functions method for the decision algorithm and the new parallel technique for the matching enumerator problem. The enumerator algorithm works in O(log3 n) parallel time and O(n3k+5.5 · log n) processors. In the case of arbitrary bipartite graphs it yields an 'optimal' (up to the log n- factor) parallel time algorithm for enumerating all the perfect matchings in a graph. It entails also among other things an efficient NC3-algorithm for computing small (polynomially bounded) arithmetic permanents, and a sublinear parallel time algorithm for enumerating all the perfect matchings in graphs with permanents up to 2nε.