Fast Probabilistic Algorithms for Verification of Polynomial Identities
From MaRDI portal
Publication:3899517
DOI10.1145/322217.322225zbMath0452.68050WikidataQ29304498 ScholiaQ29304498MaRDI QIDQ3899517
Publication date: 1980
Published in: Journal of the ACM (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1145/322217.322225
68Q25: Analysis of algorithms and problem complexity
11C08: Polynomials in number theory
12E05: Polynomials in general fields (irreducibility, etc.)
65F99: Numerical linear algebra
26B99: Functions of several variables
68W99: Algorithms in computer science
Related Items
Bell's Primeness Criterion for W(2n + 1), Polynomial equation solving by lifting procedures for ramified fibers, Deformation techniques to solve generalised Pham systems, A fast Las Vegas algorithm for computing the Smith normal form of a polynomial matrix, Counting curves and their projections, Sparse interpolation of symmetric polynomials, Decomposition of algebras over finite fields and number fields, On the decidability of sparse univariate polynomial interpolation, Non-deterministic exponential time has two-prover interactive protocols, Selected topics on assignment problems, Probabilistic checking of associativity in algebras, Functional decomposition of polynomials: the tame case, The complexity of equivalence for commutative rings, On the Piano Movers problem. II: General techniques for computing topological properties of real algebraic manifolds, Probabilistic Turing machines and recursively enumerable Dedekind cuts, Parallel algorithms for matrix normal forms, Interpolating polynomials from their values, An explicit separation of relativised random polynomial time and relativised deterministic polynomial time, Subtree isomorphism is in random NC, Nonlinear bipartite matching, Degeneration of structured integer matrices modulo an integer, Solving structured linear systems with large displacement rank, Additive preconditioning, eigenspaces, and the inverse iteration, Factoring sparse multivariate polynomials, Irreducibility of multivariate polynomials, Matching is as easy as matrix inversion, Complexity of parallel matrix computations, Constructing a perfect matching is in random NC, Automatic parameterization of rational curves and surfaces. III: Algebraic plane curves, Rubber bands, convex embeddings and graph connectivity, On zero-testing and interpolation of \(k\)-sparse multivariate polynomials over finite fields, Polymatroids: Construction and random algorithms, The image of weighted combinatorial problems, An introduction to randomized algorithms, Generalized sum graphs, Random pseudo-polynomial algorithms for some combinatorial programming problems, Improved processor bounds for combinatorial problems in RNC, On interpolating arithmetic read-once formulas with exponentiation, Elimination of parameters in the polynomial hierarchy, Depth-efficient simulation of Boolean semi-unbounded circuits by arithmetic ones, Finding the radical of matrix algebras using Fitting decompositions, The computational complexity of some problems of linear algebra, Decomposition of algebras over \(F_ q(X_ 1,\dots,X_ m)\), Directed \(s\)-\(t\) numberings, rubber bands, and testing digraph \(k\)-vertex connecitivity, Probabilistically checkable proofs and their consequences for approximation algorithms, On the degree of Boolean functions as real polynomials, Efficient matrix preconditioners for black box linear algebra, On the hardness of computing the permanent of random matrices, Testing the shift-equivalence of polynomials using quantum machines, Parallel computation of polynomial GCD and some related parallel computations over abstract fields, Straight-line programs in geometric elimination theory, Testing shift-equivalence of polynomials by deterministic, probabilistic and quantum machines., On testing for zero polynomials by a set of points with bounded precision., Cardinality constrained minimum cut problems: complexity and algorithms., Efficient decomposition of separable algebras., Randomized algorithms over finite fields for the exact parity base problem., Effective equidimensional decomposition of affine varieties, An efficient solution for Cauchy-like systems of linear equations, On the equations relating a three-dimensional object and its two-dimensional images, A new approach to fast polynomial interpolation and multipoint evaluation, Orthogonal representations and connectivity of graphs, Randomised algorithms, The time-precision tradeoff problem on on-line probabilistic Turing machines, Functional programming concepts and straight-line programs in computer algebra, Lower bounds for dynamic algebraic problems, On the complexity of pattern matching for highly compressed two-dimensional texts., Early termination in sparse interpolation algorithms, Algorithms for computing sparsest shifts of polynomials in power, Chebyshev, and Pochhammer bases, Fast computation of discrete invariants associated to a differential rational mapping, Complexity results for triangular sets, Computing Cartan subalgebras of Lie algebras, Computational indistinguishability: A sample hierarchy, New techniques for the computation of linear recurrence coefficients, Superfast algorithms for Cauchy-like matrix computations and extensions, Maximum matchings in planar graphs via Gaussian elimination, Lifting and recombination techniques for absolute factorization, Decoding interleaved Reed-Solomon codes over noisy channels, Schur aggregation for linear systems and determinants, Cryptanalyzing the polynomial-reconstruction based public-key system under optimal parameter choice, Fast computation of special resultants, From an approximate to an exact absolute polynomial factorization, Improved dense multivariate polynomial factorization algorithms, The complexity of two problems on arithmetic circuits, Processor efficient parallel matching, Change of order for regular chains in positive dimension, Efficient parallel factorization and solution of structured and unstructured linear systems, On the complexity of the resolvent representation of some prime differential ideals, Rigid realizations of graphs on small grids, Maximal bilinear complexity and codes, Computing generators of the ideal of a smooth affine algebraic variety, Fast computation of a rational point of a variety over a finite field, ON THE RANK FUNCTION OF THE 3-DIMENSIONAL RIGIDITY MATROID, On Dinur’s proof of the PCP theorem, Additive Preconditioning for Matrix Computations, Attribute-Based Broadcast Encryption Scheme Made Efficient, Approximate String Matching with Address Bit Errors, Derandomizing the Isolation Lemma and Lower Bounds for Circuit Size, Classifying the computational complexity of problems, Fast Parallel Computation of Hermite and Smith Forms of Polynomial Matrices, Singular spaces of matrices and their application in combinatorics, Factoring multivariate polynomials via partial differential equations, Using types as search keys in function libraries, Robustness and Randomness, The Monomial Ideal Membership Problem and Polynomial Identity Testing, A CCA Secure Hybrid Damgård’s ElGamal Encryption, A Gröbner free alternative for polynomial system solving, Kronecker's and Newton's approaches to solving: a first comparison, Computational arithmetic geometry. I: Sentences nearly in the polynomial hierarchy, Parallel output-sensitive algorithms for combinatorial and linear algebra problems, Back-and-forth systems for generic curves and a decision algorithm for the limit theory
