Random arithmetic formulas can be reconstructed efficiently
From MaRDI portal
Publication:488050
DOI10.1007/s00037-014-0085-0zbMath1314.68390OpenAlexW2019969751MaRDI QIDQ488050
Publication date: 23 January 2015
Published in: Computational Complexity (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1007/s00037-014-0085-0
Symbolic computation and algebraic computation (68W30) Computational aspects and applications of commutative rings (13P99) Complexity classes (hierarchies, relations among complexity classes, etc.) (68Q15) Randomized algorithms (68W20)
Related Items
Derandomization and absolute reconstruction for sums of powers of linear forms, Sparse multivariate polynomial interpolation on the basis of Schubert polynomials, Random arithmetic formulas can be reconstructed efficiently, Average-case linear matrix factorization and reconstruction of low width algebraic branching programs, Approaching the Chasm at Depth Four
Uses Software
Cites Work
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Random arithmetic formulas can be reconstructed efficiently
- New results on noncommutative and commutative polynomial identity testing
- Boolean function complexity. Advances and frontiers.
- Interpolating polynomials from their values
- Computing with polynomials given by black boxes for their evaluations: greatest common divisors, factorization, separation of numerators and denominators
- Thirty years of polynomial system solving, and now?
- Permanent and determinant
- Résolution des systèmes d'équations algébriques
- Apolarity and canonical forms for homogeneous polynomials
- Effective equidimensional decomposition of affine varieties
- A combinatorial proof of the effective Nullstellensatz
- Arithmetic Circuits: A survey of recent results and open questions
- Automorphisms mapping a point into a subvariety
- Circuit minimization problem
- Tensor rank is NP-complete
- The Complexity of Boolean Formula Minimization
- A Singular Introduction to Commutative Algebra
- Minimizing Disjunctive Normal Form Formulas and $AC^0$ Circuits Given a Truth Table
- Interpolation of Depth-3 Arithmetic Circuits with Two Multiplication Gates
- A Lower Bound for the Formula Size of Rational Functions
- Polynomial-Time Reductions from Multivariate to Bi- and Univariate Integral Polynomial Factorization
- Interpolating Arithmetic Read-Once Formulas in Parallel
- Learning functions represented as multiplicity automata
- Ideal membership in polynomial rings over the integers
- Sharp Effective Nullstellensatz
- The question of finitely many steps in polynomial ideal theory
- Solving systems of algebraic equations
- Size-Depth Tradeoffs for Algebraic Formulas
- Exact learning of random DNF over the uniform distribution
- Randomness efficient identity testing of multivariate polynomials
- Learning Theory and Kernel Machines
- Efficient Learning Algorithms Yield Circuit Lower Bounds
- Reconstruction of depth-4 multilinear circuits with top fan-in 2
- Affine projections of polynomials
- Efficient Reconstruction of Random Multilinear Formulas
- Approaching the Chasm at Depth Four
