Random arithmetic formulas can be reconstructed efficiently
From MaRDI portal
Publication:488050
DOI10.1007/S00037-014-0085-0zbMATH Open1314.68390OpenAlexW2019969751MaRDI QIDQ488050FDOQ488050
Authors: Yong-Cai Geng, Sumit K. Garg 
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
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
Randomized algorithms (68W20) Symbolic computation and algebraic computation (68W30) Complexity classes (hierarchies, relations among complexity classes, etc.) (68Q15) Computational aspects and applications of commutative rings (13P99)
Cites Work
- A Singular Introduction to Commutative Algebra
- Title not available (Why is that?)
- Boolean function complexity. Advances and frontiers.
- Title not available (Why is that?)
- Interpolating polynomials from their values
- Computing with polynomials given by black boxes for their evaluations: greatest common divisors, factorization, separation of numerators and denominators
- Arithmetic circuits: a survey of recent results and open questions
- Tensor rank is NP-complete
- Polynomial-Time Reductions from Multivariate to Bi- and Univariate Integral Polynomial Factorization
- Sharp Effective Nullstellensatz
- Read-once polynomial identity testing
- Affine projections of polynomials (extended abstract)
- Approaching the chasm at depth four
- Apolarity and canonical forms for homogeneous polynomials
- Automorphisms mapping a point into a subvariety
- Title not available (Why is that?)
- Size-Depth Tradeoffs for Algebraic Formulas
- Permanent and determinant
- Minimizing Disjunctive Normal Form Formulas and $AC^0$ Circuits Given a Truth Table
- Randomness efficient identity testing of multivariate polynomials
- Résolution des systèmes d'équations algébriques
- The Complexity of Boolean Formula Minimization
- Learning functions represented as multiplicity automata
- Thirty years of polynomial system solving, and now?
- Effective equidimensional decomposition of affine varieties
- A combinatorial proof of the effective Nullstellensatz
- Circuit minimization problem
- Interpolation of depth-3 arithmetic circuits with two multiplication gates
- A Lower Bound for the Formula Size of Rational Functions
- Title not available (Why is that?)
- Title not available (Why is that?)
- Title not available (Why is that?)
- Interpolating Arithmetic Read-Once Formulas in Parallel
- Ideal membership in polynomial rings over the integers
- The question of finitely many steps in polynomial ideal theory
- Solving systems of algebraic equations
- Random arithmetic formulas can be reconstructed efficiently
- Exact learning of random DNF over the uniform distribution
- Learning arithmetic circuits via partial derivatives.
- Efficient Learning Algorithms Yield Circuit Lower Bounds
- Efficient algorithms for some special cases of the polynomial equivalence problem
- Reconstruction of depth-4 multilinear circuits with top fan-in 2
- Efficient Reconstruction of Random Multilinear Formulas
- New results on noncommutative and commutative polynomial identity testing
Cited In (5)
- Derandomization and absolute reconstruction for sums of powers of linear forms
- Average-case linear matrix factorization and reconstruction of low width algebraic branching programs
- Random arithmetic formulas can be reconstructed efficiently
- Approaching the chasm at depth four
- Sparse multivariate polynomial interpolation on the basis of Schubert polynomials
Uses Software
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)
