Random arithmetic formulas can be reconstructed efficiently

DOI10.1007/s00037-014-0085-0zbMath1314.68390MaRDI QIDQ488050

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

zbMATH Keywords

reconstruction; average case; arithmetic formulas

Mathematics Subject Classification ID

68W30: Symbolic computation and algebraic computation

13P99: Computational aspects and applications of commutative rings

68Q15: Complexity classes (hierarchies, relations among complexity classes, etc.)

68W20: Randomized algorithms

Uses Software

• SINGULAR