Fast Probabilistic Algorithms for Verification of Polynomial Identities
From MaRDI portal
Publication:3899517
DOI10.1145/322217.322225zbMath0452.68050OpenAlexW2080132708WikidataQ29304498 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
Analysis of algorithms and problem complexity (68Q25) Polynomials in number theory (11C08) Polynomials in general fields (irreducibility, etc.) (12E05) Numerical linear algebra (65F99) Functions of several variables (26B99) Algorithms in computer science (68W99)
Related Items
Spotting Trees with Few Leaves, Discovering the Roots: Uniform Closure Results for Algebraic Classes Under Factoring, Robustness and Randomness, Unnamed Item, Generalization of the subset sum problem and cubic forms, The 𝑝-adic Kakeya conjecture, A New Black Box Factorization Algorithm - the Non-monic Case, Connections between graphs and matrix spaces, On approximate data reduction for the Rural Postman Problem: Theory and experiments, On the security of functional encryption in the generic group model, Practical sublinear proofs for R1CS from lattices, On the security of DLCSP over \(\mathrm{GL}_n (\mathbb{F}_q [S_r)\)], A combinatorial algorithm for computing the entire sequence of the maximum degree of minors of a generic partitioned polynomial matrix with \(2 \times 2\) submatrices, MyOPE: malicious security for oblivious polynomial evaluation, Worst-case subexponential attacks on PRGs of constant degree or constant locality, Dominator coloring and CD coloring in almost cluster graphs, Symmetries in directed Gaussian graphical models, Integral reduction with Kira 2.0 and finite field methods, On time-lock cryptographic assumptions in abelian hidden-order groups, Interpolation of dense and sparse rational functions and other improvements in \texttt{FireFly}, Compact Ring Signature in the Standard Model for Blockchain, The price of verifiability: lower bounds for verifiable random functions, Beyond Uber: instantiating generic groups via PGGs, Absolute reconstruction for sums of powers of linear forms: degree 3 and beyond, Unnamed Item, Hardness of graph-structured algebraic and symbolic problems, Bounds on the higher degree Erdős-Ginzburg-Ziv constants over \({\mathbb{F}}_q^n\), Algebraic reductions of knowledge, Diverse collections in matroids and graphs, Computing isomorphisms between lattices, Unnamed Item, The Monomial Ideal Membership Problem and Polynomial Identity Testing, Many Visits TSP Revisited, Efficient Black-Box Identity Testing for Free Group Algebras, ON BINARY SOLUTIONS TO SYSTEMS OF EQUATIONS, On multivariate polynomials with many roots over a finite grid, Improved Explicit Hitting-Sets for ROABPs, Algebraic independence in positive characteristic: A $p$-adic calculus, Equivalences and Black-Box Separations of Matrix Diffie-Hellman Problems, Detecting and Counting Small Pattern Graphs, Depth-4 Identity Testing and Noether’s Normalization Lemma, Coin Flipping Cannot Shorten Arithmetic Computations, 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, The \(k\)-distinct language: parameterized automata constructions, Effective bounds on the dimensions of Jacobians covering abelian varieties, DMU-ABSE: Dynamic Multi-user Attribute-Based Searchable Encryption with File Deletion and User Revocation, Bounding the Number of Common Zeros of Multivariate Polynomials and Their Consecutive Derivatives, Unnamed Item, Fast Detection of Degenerate Predicates in Free Space Construction, Table based detection of degenerate predicates in free space construction, A CCA Secure Hybrid Damgård’s ElGamal Encryption, On Parity Check (0,1)-Matrix over $\mathbb{Z}_p$, Short Proofs for the Determinant Identities, Hitting-Sets for ROABP and Sum of Set-Multilinear Circuits, Parameterized Pre-Coloring Extension and List Coloring Problems, Algorithms for Weighted Matching Generalizations I: Bipartite Graphs, b-matching, and Unweighted f-factors, Unnamed Item, Probabilistic Saturations and Alt’s Problem, Membership in Moment Polytopes is in NP and coNP, Lattice-Based SNARGs and Their Application to More Efficient Obfuscation, On the complexity of pattern matching for highly compressed two-dimensional texts., The Elekes-Szabó theorem in four dimensions, 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, On division polynomial PIT and supersingularity, Maximum matchings in planar graphs via Gaussian elimination, Lifting and recombination techniques for absolute factorization, Algebraic independence over positive characteristic: new criterion and applications to locally low-algebraic-rank circuits, Decoding interleaved Reed-Solomon codes over noisy channels, On the analysis of cryptographic assumptions in the generic ring model, Schur aggregation for linear systems and determinants, Ideals of spaces of degenerate matrices, Quantum compression relative to a set of measurements, An improved finiteness test and a systematic procedure to compute the strong \(\mathscr{H}_2\) norm of differential algebraic systems with multiple delays, Homomorphic signatures with sublinear public keys via asymmetric programmable hash functions, Computing Cartan subalgebras of Lie algebras, Extractors for varieties, Graph reconstruction in the congested clique, Deterministic identity testing for sum of read-once oblivious arithmetic branching programs, Weighted Reed-Muller codes revisited, Sparse resultants and straight-line programs, Resultant elimination via implicit equation interpolation, Randomized preprocessing versus pivoting, Tropical combinatorial Nullstellensatz and sparse polynomials, Towards a tight hardness-randomness connection between permanent and arithmetic circuit identity testing, On the genericity of maximum rank distance and Gabidulin codes, On groups with unbounded Cayley graphs, A case of depth-3 identity testing, sparse factorization and duality, Strong security of linear ramp secret sharing schemes with general access structures, Revisiting the parameterized complexity of maximum-duo preservation string mapping, Joint equidistribution of CM points, Nonclassical Berry-Esseen inequalities and accuracy of the bootstrap, Computational indistinguishability: A sample hierarchy, Cardinality constrained minimum cut problems: complexity and algorithms., Maximum weight spectrum codes, Efficient decomposition of separable algebras., New techniques for the computation of linear recurrence coefficients, Superfast algorithms for Cauchy-like matrix computations and extensions, Homotopy techniques for solving sparse column support determinantal polynomial systems, Metric estimates and membership complexity for Archimedean amoebae and tropical hypersurfaces, Practical homomorphic message authenticators for arithmetic circuits, Computing girth and cogirth in perturbed graphic matroids, A fast parallel sparse polynomial GCD algorithm, Verification protocols with sub-linear communication for polynomial matrix operations, Elimination for generic sparse polynomial systems, Algorithms for topology-free and alignment network queries, Anonymous HIBE with short ciphertexts: full security in prime order groups, Normal projection: deterministic and probabilistic algorithms, An efficient solution for Cauchy-like systems of linear equations, A deterministic algorithm for testing the equivalence of read-once branching programs with small discrepancy, Sparse affine-invariant linear codes are locally testable, Efficient algorithms for sparse cyclotomic integer zero testing, On the equations relating a three-dimensional object and its two-dimensional images, A note on parameterized polynomial identity testing using hitting set generators, Linear matroid intersection is in quasi-NC, Heuristic algorithms for recognition of some cubic hypersurfaces, Average-case linear matrix factorization and reconstruction of low width algebraic branching programs, The complexity of sparse Hensel lifting and sparse polynomial factorization, Obfuscating circuits via composite-order graded encoding, On subversion-resistant SNARKs, A probabilistic algorithm for verifying polynomial middle product in linear time, Blackbox identity testing for sum of special ROABPs and its border class, A new approach to fast polynomial interpolation and multipoint evaluation, Partition-balanced families of codes and asymptotic enumeration in coding theory, Many-visits TSP revisited, A promenade through correct test sequences. I: Degree of constructible sets, Bézout's inequality and density, Fast verification of masking schemes in characteristic two, Random construction of partial MDS codes, A combinatorial algorithm for computing the degree of the determinant of a generic partitioned polynomial matrix with \(2\times 2\) submatrices, Orthogonal representations and connectivity of graphs, Improved distance queries and cycle counting by Frobenius normal form, Univariate ideal membership parameterized by rank, degree, and number of generators, Simple multi-party set reconciliation, An algebraic Monte-Carlo algorithm for the partition adjacency matrix realization problem, Randomised algorithms, Randomized algorithms over finite fields for the exact parity base problem., The time-precision tradeoff problem on on-line probabilistic Turing machines, Improved hitting set for orbit of ROABPs, A combinatorial algorithm for computing the rank of a generic partitioned matrix with \(2 \times 2\) submatrices, Necessary field size and probability for MDP and complete MDP convolutional codes, Functional programming concepts and straight-line programs in computer algebra, Accelerated tower arithmetic, Don't tamper with dual system encryption. Beyond polynomial related-key security of IBE, Parameterized complexity of list coloring and max coloring, Degeneracy loci and polynomial equation solving, Lower bounds for dynamic algebraic problems, Polynomial modular product verification and its implications, Computing valuations of the Dieudonné determinants, Boolean ideals and their varieties, Effective equidimensional decomposition of affine varieties, Random multipliers numerically stabilize Gaussian and block Gaussian elimination: proofs and an extension to low-rank approximation, Relating \(p\)-adic eigenvalues and the local Smith normal form, Equivalence of polynomial identity testing and polynomial factorization, Monomials in arithmetic circuits: complete problems in the counting hierarchy, A fast parallel algorithm for minimum-cost small integral flows, An efficient certificate-based signature scheme in the standard model, Real \(\tau \)-conjecture for sum-of-squares: a unified approach to lower bound and derandomization, A direct algorithm to compute the topological Euler characteristic and Chern-Schwartz-MacPherson class of projective complete intersection varieties, Factoring sparse multivariate polynomials, More efficient shuffle argument from unique factorization, The key-dependent message security of key-alternating Feistel ciphers, Irreducibility of multivariate polynomials, Zero testing of algebraic functions, Black-box polynomial resultants, Fast exact algorithms using Hadamard product of polynomials, Structure-preserving signatures and commitments to group elements, Directed \(s\)-\(t\) numberings, rubber bands, and testing digraph \(k\)-vertex connecitivity, Subexponential size hitting sets for bounded depth multilinear formulas, Probabilistically checkable proofs and their consequences for approximation algorithms, On the degree of Boolean functions as real polynomials, Matching is as easy as matrix inversion, Efficient matrix preconditioners for black box linear algebra, On approximation by \(^{\oplus}\)-OBDDs, Finding linear dependencies in integration-by-parts equations: a Monte Carlo approach, Additive preconditioning for matrix computations, Rural postman parameterized by the number of components of required edges, Fast dynamic transitive closure with lookahead, Complexity of parallel matrix computations, On the hardness of computing the permanent of random matrices, Testing the shift-equivalence of polynomials using quantum machines, Constructing a perfect matching is in random NC, Parameterized algorithms for the module motif problem, Automatic parameterization of rational curves and surfaces. III: Algebraic plane curves, Parallel computation of polynomial GCD and some related parallel computations over abstract fields, Cryptanalysis of HFE, multi-HFE and variants for odd and even characteristic, Polynomial equation solving by lifting procedures for ramified fibers, Deformation techniques to solve generalised Pham systems, Rubber bands, convex embeddings and graph connectivity, Straight-line programs in geometric elimination theory, On enumerating monomials and other combinatorial structures by polynomial interpolation, Testing shift-equivalence of polynomials by deterministic, probabilistic and quantum machines., Multiple recurrence and convergence results associated to \(\mathbb F_P^\omega\)-actions, Matrix computations and polynomial root-finding with preprocessing, Faster \(p\)-adic feasibility for certain multivariate sparse polynomials, On testing for zero polynomials by a set of points with bounded precision., Deterministic polynomial identity tests for multilinear bounded-read formulae, Sparse interpolation of multivariate rational functions, On triple intersections of three families of unit circles, Interpolating polynomials from their values, The generalized Erdős-Falconer distance problems in vector spaces over finite fields, An explicit separation of relativised random polynomial time and relativised deterministic polynomial time, Solving linear systems of equations with randomization, augmentation and aggregation, Detecting lacunary perfect powers and computing their roots, Subtree isomorphism is in random NC, Pattern matching with address errors: rearrangement distances, Nonlinear bipartite matching, Black box polynomial identity testing of generalized depth-3 arithmetic circuits with bounded top fan-in, Almost tight upper bound for finding Fourier coefficients of bounded pseudo-Boolean functions, On zero-testing and interpolation of \(k\)-sparse multivariate polynomials over finite fields, Polymatroids: Construction and random algorithms, The image of weighted combinatorial problems, A non-linear lower bound for planar epsilon-nets, An introduction to randomized algorithms, Parameterized algorithms for list \(K\)-cycle, Common composites of triangular polynomial systems and hash functions, Read-once polynomial identity testing, Generalized sum graphs, Degeneration of structured integer matrices modulo an integer, A fast Las Vegas algorithm for computing the Smith normal form of a polynomial matrix, Counting curves and their projections, Odd properly colored cycles in edge-colored graphs, Sparse interpolation of symmetric polynomials, On the Alon-Füredi bound, Random pseudo-polynomial algorithms for some combinatorial programming problems, Solving structured linear systems with large displacement rank, 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, Categories generated by a trivalent vertex, Additive preconditioning, eigenspaces, and the inverse iteration, The ideal membership problem and polynomial identity testing, Selected topics on assignment problems, Randomized preprocessing of homogeneous linear systems of equations, New progress in real and complex polynomial root-finding, Deterministically testing sparse polynomial identities of unbounded degree, Interrogating witnesses for geometric constraint solving, The inverse moment problem for convex polytopes, Probabilistic algorithms for computing resolvent representations of regular differential ideals, A geometric index reduction method for implicit systems of differential algebraic equations, Building above read-once polynomials: identity testing and hardness of representation, Improved processor bounds for combinatorial problems in RNC, Multipartite secret sharing by bivariate interpolation, Probabilistic checking of associativity in algebras, On interpolating arithmetic read-once formulas with exponentiation, 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, A parameterized view on matroid optimization problems, Maximum weight bipartite matching in matrix multiplication time, Elimination of parameters in the polynomial hierarchy, Depth-efficient simulation of Boolean semi-unbounded circuits by arithmetic ones, Approximate string matching with address bit errors, Finding the radical of matrix algebras using Fitting decompositions, The computational complexity of some problems of linear algebra, Probabilistic Turing machines and recursively enumerable Dedekind cuts, Parallel algorithms for matrix normal forms, Decomposition of algebras over \(F_ q(X_ 1,\dots,X_ m)\), Constrained multilinear detection and generalized graph motifs, A Combinatorial Algorithm for Computing the Rank of a Generic Partitioned Matrix with 2 $$\times $$ 2 Submatrices, Factoring multivariate polynomials via partial differential equations, New Ideas to Build Noise-Free Homomorphic Cryptosystems, Spotting Trees with Few Leaves, A Practical Leakage-Resilient Signature Scheme in the Generic Group Model, Faster sparse multivariate polynomial interpolation of straight-line programs, Exact learning from an honest teacher that answers membership queries, Parametric nonlinear discrete optimization over well-described sets and matroid intersections, Maximal bilinear complexity and codes, Cryptanalyzing the polynomial-reconstruction based public-key system under optimal parameter choice, Categories of dimension zero, Computing generators of the ideal of a smooth affine algebraic variety, Generic complexity of the membership problem for semigroups of integer matrices, Derandomization from Algebraic Hardness, Narrow sieves for parameterized paths and packings, On the directions determined by Cartesian products and the clique number of generalized Paley graphs, Singular spaces of matrices and their application in combinatorics, On probabilistic algorithm for solving almost all instances of the set partition problem, Efficient revocable identity-based encryption with short public parameters, On the complexity exponent of polynomial system solving, Simultaneous robust subspace recovery and semi-stability of quiver representations, Characterizing Propositional Proofs as Noncommutative Formulas, Uniform derandomization from pathetic lower bounds, Chevalley-Warning at the boundary, Tripartite-to-bipartite entanglement transformation by stochastic local operations and classical communication and the structure of matrix spaces, Improved Parameterized Algorithms for Network Query Problems, Improved parameterized algorithms for network query problems, On the complexity landscape of connected \(f\)-factor problems, An optimized inner product argument with more application scenarios, Minimisation of Multiplicity Tree Automata, Irreducibility of random polynomials of bounded degree, Unnamed Item, Unnamed Item, How to Obtain Fully Structure-Preserving (Automorphic) Signatures from Structure-Preserving Ones, A Shuffle Argument Secure in the Generic Model, Factoring multivariate polynomials represented by black boxes: a Maple + C implementation, Additive Preconditioning for Matrix Computations, On sets of linear forms of maximal complexity, Automated analysis of cryptographic assumptions in generic group models, Attribute-Based Broadcast Encryption Scheme Made Efficient, Approximate String Matching with Address Bit Errors, Unnamed Item, Efficient multivariate low-degree tests via interactive oracle proofs of proximity for polynomial codes, Classifying the computational complexity of problems, Unnamed Item, On additive-nilpotency of Jacobian matrices of polynomial maps, Reconstructing rational functions with \texttt{FireFly}, Weak identifiability for differential algebraic systems, Unnamed Item, Fast Parallel Computation of Hermite and Smith Forms of Polynomial Matrices, Derandomizing the Isolation Lemma and Lower Bounds for Circuit Size, Barriers for Rank Methods in Arithmetic Complexity, Fast computation of special resultants, From an approximate to an exact absolute polynomial factorization, Improved dense multivariate polynomial factorization algorithms, Witnessing matrix identities and proof complexity, On Zeros of a Polynomial in a Finite Grid, Bell's Primeness Criterion for W(2n + 1), A Signature Scheme with Efficient Proof of Validity, Recent Results on Polynomial Identity Testing, The complexity of two problems on arithmetic circuits, Unnamed Item, Permanent Does Not Have Succinct Polynomial Size Arithmetic Circuits of Constant Depth, Invitation to Algorithmic Uses of Inclusion–Exclusion, Algebraic Independence and Blackbox Identity Testing, 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, Some results on counting roots of polynomials and the Sylvester resultant, The computational complexity of some problems of linear algebra, Using types as search keys in function libraries, Unnamed Item, Unnamed Item, Unnamed Item, Generalized commutators and a problem related to the Amitsur–Levitzki theorem, On the size of Kakeya sets in finite fields, Unnamed Item, A Symbolic Approach to Compute a Null-Space Basis in the Projection Method, Estimating the norms of random circulant and Toeplitz matrices and their inverses, The Complexity of Acyclic Subhypergraph Problems, Three-Player Entangled XOR Games are NP-Hard to Approximate, Sublinear Root Detection and New Hardness Results for Sparse Polynomials over Finite Fields, Jacobian Hits Circuits: Hitting Sets, Lower Bounds for Depth-$D$ Occur-$k$ Formulas and Depth-3 Transcendence Degree-$k$ Circuits, Geometric complexity theory V: Efficient algorithms for Noether normalization, Characterizing Arithmetic Read-Once Formulae, Much Ado about Zero, Using Sparse Interpolation in Hensel Lifting, Enhancing the Extended Hensel Construction by Using Gröbner Bases, Block-Wise P-Signatures and Non-interactive Anonymous Credentials with Efficient Attributes, Unnamed Item, Rank-Metric Codes Over Arbitrary Galois Extensions and Rank Analogues of Reed--Muller Codes, From Independent Sets and Vertex Colorings to Isotropic Spaces and Isotropic Decompositions: Another Bridge between Graphs and Alternating Matrix Spaces, Bipartite Perfect Matching is in Quasi-NC, Fast computation of a rational point of a variety over a finite field, MIXING FOR PROGRESSIONS IN NONABELIAN GROUPS, ON THE RANK FUNCTION OF THE 3-DIMENSIONAL RIGIDITY MATROID, Rigid realizations of graphs on small grids, Sparse MDS Matrices over Small Fields: A Proof of the GM-MDS Conjecture, On Dinur’s proof of the PCP theorem
