Random arithmetic formulas can be reconstructed efficiently
From MaRDI portal
Recommendations
- Randomized proofs in arithmetic
- The revised recursive reduction for efficiently generating random numbers
- Efficient rational number reconstruction
- Randomized algorithms in number theory
- Number-theoretic constructions of efficient pseudo-random functions
- A superfast randomized algorithm to decompose binary forms
- Randomness and arithmetic
- Complete derandomization of identity testing and reconstruction of read-once formulas
- scientific article; zbMATH DE number 7204283
Cites work
- scientific article; zbMATH DE number 16653 (Why is no real title available?)
- scientific article; zbMATH DE number 17840 (Why is no real title available?)
- scientific article; zbMATH DE number 52497 (Why is no real title available?)
- scientific article; zbMATH DE number 1302473 (Why is no real title available?)
- scientific article; zbMATH DE number 774007 (Why is no real title available?)
- scientific article; zbMATH DE number 1446863 (Why is no real title available?)
- A Lower Bound for the Formula Size of Rational Functions
- A Singular Introduction to Commutative Algebra
- A combinatorial proof of the effective Nullstellensatz
- Affine projections of polynomials (extended abstract)
- Apolarity and canonical forms for homogeneous polynomials
- Approaching the chasm at depth four
- Arithmetic circuits: a survey of recent results and open questions
- Automorphisms mapping a point into a subvariety
- Boolean function complexity. Advances and frontiers.
- Circuit minimization problem
- Computing with polynomials given by black boxes for their evaluations: greatest common divisors, factorization, separation of numerators and denominators
- Effective equidimensional decomposition of affine varieties
- Efficient Learning Algorithms Yield Circuit Lower Bounds
- Efficient Reconstruction of Random Multilinear Formulas
- Efficient algorithms for some special cases of the polynomial equivalence problem
- Exact learning of random DNF over the uniform distribution
- Ideal membership in polynomial rings over the integers
- Interpolating Arithmetic Read-Once Formulas in Parallel
- Interpolating polynomials from their values
- Interpolation of depth-3 arithmetic circuits with two multiplication gates
- Learning arithmetic circuits via partial derivatives.
- Learning functions represented as multiplicity automata
- Minimizing Disjunctive Normal Form Formulas and $AC^0$ Circuits Given a Truth Table
- New results on noncommutative and commutative polynomial identity testing
- Permanent and determinant
- Polynomial-Time Reductions from Multivariate to Bi- and Univariate Integral Polynomial Factorization
- Random arithmetic formulas can be reconstructed efficiently
- Randomness efficient identity testing of multivariate polynomials
- Read-once polynomial identity testing
- Reconstruction of depth-4 multilinear circuits with top fan-in 2
- Résolution des systèmes d'équations algébriques
- Sharp Effective Nullstellensatz
- Size-Depth Tradeoffs for Algebraic Formulas
- Solving systems of algebraic equations
- Tensor rank is NP-complete
- The Complexity of Boolean Formula Minimization
- The question of finitely many steps in polynomial ideal theory
- Thirty years of polynomial system solving, and now?
Cited in
(5)- Average-case linear matrix factorization and reconstruction of low width algebraic branching programs
- Sparse multivariate polynomial interpolation on the basis of Schubert polynomials
- Derandomization and absolute reconstruction for sums of powers of linear forms
- Random arithmetic formulas can be reconstructed efficiently
- Approaching the chasm at depth four
This page was built for publication: Random arithmetic formulas can be reconstructed efficiently
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q488050)
