Random arithmetic formulas can be reconstructed efficiently
type: Item
instance of: scholarly article
title: Random arithmetic formulas can be reconstructed efficiently
zbMATH Open document ID: 1314.68390
author: Yong-Cai Geng
author: Sumit K. Garg
published in: Computational Complexity
publication date: 2015-01-23T00:00:00Z
Mathematics Subject Classification ID: 68W20
Mathematics Subject Classification ID: 13P99
Mathematics Subject Classification ID: 68Q15
Mathematics Subject Classification ID: 68W30
zbMATH DE Number: 6390108
zbMATH Keywords: arithmetic formulas
zbMATH Keywords: average case
zbMATH Keywords: reconstruction
describes a project that uses: SINGULAR
MaRDI profile type: Publication
full work available at URL: s00037-014-0085-0
OpenAlex ID: W2019969751
cites work: Minimizing Disjunctive Normal Form Formulas and $AC^0$ Circuits Given a Truth Table
cites work: Q3975184
cites work: New results on noncommutative and commutative polynomial identity testing
cites work: Ideal membership in polynomial rings over the integers
cites work: Automorphisms mapping a point into a subvariety
cites work: Learning functions represented as multiplicity automata
cites work: Apolarity and canonical forms for homogeneous polynomials
cites work: Interpolating Arithmetic Read-Once Formulas in Parallel
cites work: Size-Depth Tradeoffs for Algebraic Formulas
cites work: The Complexity of Boolean Formula Minimization
cites work: A Lower Bound for the Formula Size of Rational Functions
cites work: Permanent and determinant
cites work: Interpolation of Depth-3 Arithmetic Circuits with Two Multiplication Gates
cites work: Q4247789
cites work: A combinatorial proof of the effective Nullstellensatz
cites work: Efficient Learning Algorithms Yield Circuit Lower Bounds
cites work: A Singular Introduction to Commutative Algebra
cites work: Approaching the Chasm at Depth Four
cites work: Efficient Reconstruction of Random Multilinear Formulas
cites work: Reconstruction of depth-4 multilinear circuits with top fan-in 2
cites work: Q4002797
cites work: Tensor rank is NP-complete
cites work: The question of finitely many steps in polynomial ideal theory
cites work: Effective equidimensional decomposition of affine varieties
cites work: Boolean function complexity. Advances and frontiers.
cites work: Circuit minimization problem
cites work: Polynomial-Time Reductions from Multivariate to Bi- and Univariate Integral Polynomial Factorization
cites work: Computing with polynomials given by black boxes for their evaluations: greatest common divisors, factorization, separation of numerators and denominators
cites work: Q5365127
cites work: Affine projections of polynomials
cites work: Learning Theory and Kernel Machines
cites work: Randomness efficient identity testing of multivariate polynomials
cites work: Sharp Effective Nullstellensatz
cites work: Q3973339
cites work: Résolution des systèmes d'équations algébriques
cites work: Solving systems of algebraic equations
cites work: Thirty years of polynomial system solving, and now?
cites work: Q4839061
cites work: Exact learning of random DNF over the uniform distribution
cites work: Q5302074
cites work: Arithmetic Circuits: A survey of recent results and open questions
cites work: Q4953977
cites work: Interpolating polynomials from their values
DOI: 10.1007/S00037-014-0085-0
Recommended article: Randomized proofs in arithmetic
Recommended article: The revised recursive reduction for efficiently generating random numbers
Recommended article: Efficient rational number reconstruction
Recommended article: Randomized algorithms in number theory
Recommended article: Number-theoretic constructions of efficient pseudo-random functions
Recommended article: A Superfast Randomized Algorithm to Decompose Binary Forms
Recommended article: Q3144177
Recommended article: Complete Derandomization of Identity Testing and Reconstruction of Read-Once Formulas
Recommended article: Q5111163
description: scientific article; zbMATH DE number 6390108