Randomness efficient identity testing of multivariate polynomials

DOI10.1145/380752.380801MaRDI QIDQ5175971zbMATH OpenOpenAlexFDO

Authors Adam R. Klivans, Daniel A. Spielman

Publication date 27 February 2015

Published in Proceedings of the thirty-third annual ACM symposium on Theory of computing (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1145/380752.380801

Mathematics Subject Classification ID

Polynomials over finite fields (11T06) Algebraic coding theory; cryptography (number-theoretic aspects) (11T71) Analysis of algorithms and problem complexity (68Q25) Randomized algorithms (68W20)

Recommendations

• scientific article; zbMATH DE number 1775429
• scientific article; zbMATH DE number 2079409
• Primality and identity testing via Chinese remaindering
• Deterministically testing sparse polynomial identities of unbounded degree
• Randomness efficient testing of sparse black box identities of unbounded degree over the reals

Cites work

• A constant-factor approximation algorithm for the \(k\)-median problem (extended abstract)

Cited in

(65)

• Deterministic identity testing for sum of read-once oblivious arithmetic branching programs
• Sparse multivariate polynomial interpolation on the basis of Schubert polynomials
• The interpolation problem for \(k\)-sparse polynomials and character sums
• A case of depth-3 identity testing, sparse factorization and duality
• Blackbox identity testing for sum of special ROABPs and its border class
• Improved hitting set for orbit of ROABPs
• On hitting-set generators for polynomials that vanish rarely
• Sparse polynomial interpolation based on diversification
• Faster interpolation algorithms for sparse multivariate polynomials given by straight-line programs
• Tropical combinatorial Nullstellensatz and sparse polynomials
• Computing Walrasian equilibria: fast algorithms and structural properties
• Operator scaling: theory and applications
• Monomials in arithmetic circuits: complete problems in the counting hierarchy
• Noisy interpolation of sparse polynomials in finite fields
• Cryptographic hardness for learning intersections of halfspaces
• Exact learning from an honest teacher that answers membership queries
• Jacobian hits circuits: hitting sets, lower bounds for depth-D occur-k formulas and depth-3 transcendence degree-k circuits
• Characterizing arithmetic read-once formulae
• Optimal testing of multivariate polynomials over small prime fields
• Randomness efficient testing of sparse black box identities of unbounded degree over the reals
• Complexity of short generating functions
• Arithmetic Circuits, Monomial Algebras and Finite Automata
• Primality and identity testing via Chinese remaindering
• Derandomizing the Isolation Lemma and Lower Bounds for Circuit Size
• On enumerating monomials and other combinatorial structures by polynomial interpolation
• scientific article; zbMATH DE number 2079409 (Why is no real title available?)
• scientific article; zbMATH DE number 1775429 (Why is no real title available?)
• Random arithmetic formulas can be reconstructed efficiently
• Read-once polynomial identity testing
• Bipartite perfect matching is in quasi-NC
• On some computations on sparse polynomials
• Towards blackbox identity testing of log-variate circuits
• scientific article; zbMATH DE number 7471587 (Why is no real title available?)
• Quantified Derandomization: How to Find Water in the Ocean
• Derandomizing isolation in space-bounded settings
• Hitting-Sets for ROABP and Sum of Set-Multilinear Circuits
• Depth-4 identity testing and Noether's normalization lemma
• Efficient Black-Box Identity Testing for Free Group Algebras
• On hitting-set generators for polynomials that vanish rarely
• scientific article; zbMATH DE number 7758310 (Why is no real title available?)
• No short polynomials vanish on bounded rank matrices
• Algebraic algorithms for variants of subset sum
• A deterministic parallel reduction from weighted matroid intersection search to decision
• Linear independence, alternants, and applications
• Black box polynomial identity testing of generalized depth-3 arithmetic circuits with bounded top fan-in
• Variety evasive subspace families
• Complexity theory. Abstracts from the workshop held June 2--7, 2024
• Linear independence, alternants and applications
• NP-hardness of testing equivalence to sparse polynomials and to constant-support polynomials
• Tensor reconstruction beyond constant rank
• Reconstruction of depth-4 multilinear circuits
• On matrix multiplication and polynomial identity testing
• Derandomizing multivariate polynomial factoring for low degree factors
• Optimal pseudorandom generators for low-degree polynomials over moderately large fields
• Bit complexity of polynomial GCD on sparse representation
• On solving sparse polynomial factorization related problems
• Derandomization via symmetric polytopes: poly-time factorization of certain sparse polynomials
• Towards identity testing for sums of products of Read-once and multilinear bounded-Read formulae
• Hitting sets for orbits of circuit classes and polynomial families
• Constructing faithful homomorphisms over fields of finite characteristic
• Building above read-once polynomials: identity testing and hardness of representation
• Faster \& deterministic FPT algorithm for worst-case tensor decomposition
• Deterministic polynomial identity tests for multilinear bounded-read formulae
• An explicit separation of relativised random polynomial time and relativised deterministic polynomial time
• Deterministically testing sparse polynomial identities of unbounded degree

This page was built for publication: Randomness efficient identity testing of multivariate polynomials

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5175971)