Jacobian Hits Circuits: Hitting Sets, Lower Bounds for Depth-$D$ Occur-$k$ Formulas and Depth-3 Transcendence Degree-$k$ Circuits
From MaRDI portal
Publication:2817792
DOI10.1137/130910725zbMath1350.68292MaRDI QIDQ2817792
Ramprasad Saptharishi, Nitin Saxena, Chandan Saha, Manindra Agrawal
Publication date: 2 September 2016
Published in: SIAM Journal on Computing (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1137/130910725
Jacobian; lower bound; depth; circuits; algebraic independence; identity testing; Vandermonde; immanant; black box
68Q25: Analysis of algorithms and problem complexity
68W30: Symbolic computation and algebraic computation
Related Items
Unnamed Item, A super-quadratic lower bound for depth four arithmetic circuits, Algebraic independence over positive characteristic: new criterion and applications to locally low-algebraic-rank circuits, Subspace Arrangements, Graph Rigidity and Derandomization Through Submodular Optimization
Cites Work
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Arithmetic circuits: the chasm at depth four gets wider
- Black box polynomial identity testing of generalized depth-3 arithmetic circuits with bounded top fan-in
- Matching is as easy as matrix inversion
- On zero-testing and interpolation of \(k\)-sparse multivariate polynomials over finite fields
- A probabilistic remark on algebraic program testing
- Exponential lower bounds for depth three Boolean circuits
- PRIMES is in P
- Algebraic independence and blackbox identity testing
- Deterministic extractors for affine sources over large fields
- Polynomial identity testing for depth 3 circuits
- Arithmetic Circuits: A Chasm at Depth 3
- Partial Derivatives in Arithmetic Complexity and Beyond
- Deterministic identity testing of depth-4 multilinear circuits with bounded top fan-in
- An Almost Optimal Rank Bound for Depth-3 Identities
- Algebraic Independence and Blackbox Identity Testing
- On P vs. NP and geometric complexity theory
- Fast Parallel Computation of Polynomials Using Few Processors
- Arithmetic Circuits: A survey of recent results and open questions
- Proof verification and the hardness of approximation problems
- Locally decodable codes with 2 queries and polynomial identity testing for depth 3 circuits
- On the Relation between Polynomial Identity Testing and Finding Variable Disjoint Factors
- Improved Polynomial Identity Testing for Read-Once Formulas
- A Lower Bound for the Formula Size of Rational Functions
- A complexity theory based on Boolean algebra
- Fast Probabilistic Algorithms for Verification of Polynomial Identities
- Algebraic methods for interactive proof systems
- Blackbox Polynomial Identity Testing for Depth 3 Circuits
- Randomness efficient identity testing of multivariate polynomials
- Deterministic Polynomial Time Algorithms for Matrix Completion Problems
- Jacobian hits circuits
- Black-box identity testing of depth-4 multilinear circuits
- Blackbox identity testing for bounded top fanin depth-3 circuits
- Algebraic independence in positive characteristic: A $p$-adic calculus
- Quasi-polynomial hitting-set for set-depth-Δ formulas
- FSTTCS 2005: Foundations of Software Technology and Theoretical Computer Science
- Derandomizing polynomial identity tests means proving circuit lower bounds
- Pseudo-random generators for all hardnesses
- Depth-3 arithmetic circuits over fields of characteristic zero
