Randomness efficient identity testing of multivariate polynomials

DOI10.1145/380752.380801zbMath1323.68563OpenAlexW1967348711MaRDI QIDQ5175971

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

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

Related Items (max. 100)

Sparse polynomial interpolation based on diversification ⋮ Exact learning from an honest teacher that answers membership queries ⋮ Quantified Derandomization: How to Find Water in the Ocean ⋮ Arithmetic Circuits, Monomial Algebras and Finite Automata ⋮ On enumerating monomials and other combinatorial structures by polynomial interpolation ⋮ Deterministic identity testing for sum of read-once oblivious arithmetic branching programs ⋮ Sparse multivariate polynomial interpolation on the basis of Schubert polynomials ⋮ Faster interpolation algorithms for sparse multivariate polynomials given by straight-line programs ⋮ 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 ⋮ Tropical combinatorial Nullstellensatz and sparse polynomials ⋮ Unnamed Item ⋮ Unnamed Item ⋮ Deterministic polynomial identity tests for multilinear bounded-read formulae ⋮ A case of depth-3 identity testing, sparse factorization and duality ⋮ Unnamed Item ⋮ Unnamed Item ⋮ Black box polynomial identity testing of generalized depth-3 arithmetic circuits with bounded top fan-in ⋮ Unnamed Item ⋮ Derandomizing the Isolation Lemma and Lower Bounds for Circuit Size ⋮ Random arithmetic formulas can be reconstructed efficiently ⋮ Efficient Black-Box Identity Testing for Free Group Algebras ⋮ Read-once polynomial identity testing ⋮ Depth-4 Identity Testing and Noether’s Normalization Lemma ⋮ Deterministically testing sparse polynomial identities of unbounded degree ⋮ Noisy interpolation of sparse polynomials in finite fields ⋮ Building above read-once polynomials: identity testing and hardness of representation ⋮ Computing Walrasian equilibria: fast algorithms and structural properties ⋮ Blackbox identity testing for sum of special ROABPs and its border class ⋮ Cryptographic hardness for learning intersections of halfspaces ⋮ Jacobian Hits Circuits: Hitting Sets, Lower Bounds for Depth-$D$ Occur-$k$ Formulas and Depth-3 Transcendence Degree-$k$ Circuits ⋮ Operator scaling: theory and applications ⋮ Characterizing Arithmetic Read-Once Formulae ⋮ Derandomizing Isolation in Space-Bounded Settings ⋮ Bipartite Perfect Matching is in Quasi-NC ⋮ COMPLEXITY OF SHORT GENERATING FUNCTIONS ⋮ Improved hitting set for orbit of ROABPs ⋮ Hitting-Sets for ROABP and Sum of Set-Multilinear Circuits ⋮ On hitting-set generators for polynomials that vanish rarely ⋮ Monomials in arithmetic circuits: complete problems in the counting hierarchy

Cites Work

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

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