scientific article; zbMATH DE number 7471587
DOI10.4086/toc.2021.v017a010OpenAlexW3210738158MaRDI QIDQ5028363
Avi Wigderson, Amir Shpilka, Iddo Tzameret, Michael A. Forbes
Publication date: 9 February 2022
Published in: Theory of Computing (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.4086/toc.2021.v017a010
Title: zbMATH Open Web Interface contents unavailable due to conflicting licenses.
lower boundspolynomial calculusalgebraic proof systemsproof complexityIPSalgebraic circuit complexityhardness versus randomnessABPsfunctional lower bounds
Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Complexity classes (hierarchies, relations among complexity classes, etc.) (68Q15) Complexity of proofs (03F20)
Related Items (1)
Cites Work
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Subexponential size hitting sets for bounded depth multilinear formulas
- Factors of low individual degree polynomials
- Lower bounds and separations for constant depth multilinear circuits
- Building above read-once polynomials: identity testing and hardness of representation
- Resolution over linear equations and multilinear proofs
- The strength of multilinear proofs
- Factoring sparse multivariate polynomials
- A probabilistic remark on algebraic program testing
- Lower bounds for the polynomial calculus
- Lower bounds on arithmetic circuits via partial derivatives
- Proof complexity in algebraic systems and bounded depth Frege systems with modular counting
- Algebraic proof systems over formulas.
- Deterministic identity testing for sum of read-once oblivious arithmetic branching programs
- Deterministic polynomial identity testing in non-commutative models
- Affine projections of symmetric polynomials.
- The proof complexity of linear algebra
- On the intractability of Hilbert's Nullstellensatz and an algebraic version of ``\(NP\neq P\)?
- Lower bounds for the polynomial calculus and the Gröbner basis algorithm
- Balancing syntactically multilinear arithmetic circuits
- Perspectives in computational complexity. The Somenath Biswas anniversary volume. Selected papers based on the presentations at the workshop, Kanpur, India, Summer 2012
- Arithmetic Circuits: A Chasm at Depth 3
- Arithmetic Circuits: A survey of recent results and open questions
- Diagonal Circuit Identity Testing and Lower Bounds
- Hardness-Randomness Tradeoffs for Bounded Depth Arithmetic Circuits
- Progress on Polynomial Identity Testing - II
- Fast Probabilistic Algorithms for Verification of Polynomial Identities
- The relative efficiency of propositional proof systems
- Sums of Like Powers of Multivariate Linear Forms
- Lower bounds for resolution and cutting plane proofs and monotone computations
- Characterizing Propositional Proofs as Noncommutative Formulas
- Circuit Complexity, Proof Complexity, and Polynomial Identity Testing
- Lower Bounds on Hilbert's Nullstellensatz and Propositional Proofs
- Identity Testing and Lower Bounds for Read- k Oblivious Algebraic Branching Programs
- Randomness efficient identity testing of multivariate polynomials
- Short Proofs for the Determinant Identities
- Hitting-Sets for ROABP and Sum of Set-Multilinear Circuits
- Hitting sets for multilinear read-once algebraic branching programs, in any order
- Deterministically Factoring Sparse Polynomials into Multilinear Factors and Sums of Univariate Polynomials
- Proof Complexity Lower Bounds from Algebraic Circuit Complexity
- On identity testing of tensors, low-rank recovery and compressed sensing
- Approaching the Chasm at Depth Four
- FSTTCS 2005: Foundations of Software Technology and Theoretical Computer Science
- Multi-linear formulas for permanent and determinant are of super-polynomial size
- Derandomizing polynomial identity tests means proving circuit lower bounds
- Pseudorandom generators without the XOR lemma
- Linear gaps between degrees for the polynomial calculus modulo distinct primes
- Depth-3 arithmetic circuits over fields of characteristic zero
This page was built for publication:
