Jacobian hits circuits: hitting sets, lower bounds for depth-D occur-k formulas and depth-3 transcendence degree-k circuits

DOI10.1137/130910725zbMATH Open1350.68292OpenAlexW2508387244MaRDI QIDQ2817792FDOQ2817792

Authors: Chandan Saha, Ramprasad Saptharishi, Nitin Saxena, 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

Recommendations

• Jacobian hits circuits: hitting-sets, lower bounds for depth-\(D\) occur-\(k\) formulas \& depth-\(3\) transcendence degree-\(k\) circuits
• Arithmetic circuits with locally low algebraic rank
• Arithmetic circuits with locally low algebraic rank
• Black box polynomial identity testing of generalized depth-3 arithmetic circuits with bounded top fan-in
• Algebraic independence and blackbox identity testing

zbMATH Keywords

lower bounddepthalgebraic independenceJacobiancircuitsidentity testingVandermondeimmanantblack box

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Symbolic computation and algebraic computation (68W30)

Cites Work

• Title not available (Why is that?)
• A probabilistic remark on algebraic program testing
• Proof verification and the hardness of approximation problems
• Title not available (Why is that?)
• Fast Probabilistic Algorithms for Verification of Polynomial Identities
• PRIMES is in P
• Title not available (Why is that?)
• On zero-testing and interpolation of \(k\)-sparse multivariate polynomials over finite fields
• Fast Parallel Computation of Polynomials Using Few Processors
• Arithmetic circuits: the chasm at depth four gets wider
• Algebraic independence in positive characteristic: a \(p\)-adic calculus
• Matching is as easy as matrix inversion
• Exponential lower bounds for depth three Boolean circuits
• On the relation between polynomial identity testing and finding variable disjoint factors
• Polynomial identity testing for depth 3 circuits
• Arithmetic circuits: a chasm at depth 3
• Arithmetic circuits: a survey of recent results and open questions
• Improved Polynomial Identity Testing for Read-Once Formulas
• Title not available (Why is that?)
• Blackbox Polynomial Identity Testing for Depth 3 Circuits
• Read-once polynomial identity testing
• Jacobian hits circuits: hitting-sets, lower bounds for depth-\(D\) occur-\(k\) formulas \& depth-\(3\) transcendence degree-\(k\) circuits
• Black-box identity testing of depth-4 multilinear circuits
• Blackbox identity testing for bounded top fanin depth-3 circuits
• Quasi-polynomial hitting-set for set-depth-\({\Delta}\) formulas
• FSTTCS 2005: Foundations of Software Technology and Theoretical Computer Science
• Derandomizing polynomial identity tests means proving circuit lower bounds
• Depth-3 arithmetic circuits over fields of characteristic zero
• Black box polynomial identity testing of generalized depth-3 arithmetic circuits with bounded top fan-in
• Deterministic extractors for affine sources over large fields
• Algebraic methods for interactive proof systems
• Deterministic identity testing of depth-\(4\) multilinear circuits with bounded top fan-in
• An almost optimal rank bound for depth-3 identities
• Randomness efficient identity testing of multivariate polynomials
• On circuit lower bounds from derandomization
• Pseudo-random generators for all hardnesses
• Title not available (Why is that?)
• On P vs. NP and geometric complexity theory: dedicated to Sri Ramakrishna
• Title not available (Why is that?)
• The limited power of powering: polynomial identity testing and a depth-four lower bound for the permanent
• A Lower Bound for the Formula Size of Rational Functions
• Partial derivatives in arithmetic complexity and beyond
• A complexity theory based on Boolean algebra
• Deterministic polynomial time algorithms for matrix completion problems
• Title not available (Why is that?)
• Locally decodable codes with 2 queries and polynomial identity testing for depth 3 circuits
• Algebraic independence and blackbox identity testing
• Algebraic independence and blackbox identity testing

Cited In (7)

• A super-quadratic lower bound for depth four arithmetic circuits
• Variety evasive subspace families
• Algebraic independence over positive characteristic: new criterion and applications to locally low-algebraic-rank circuits
• Subspace arrangements, graph rigidity and derandomization through submodular optimization
• Jacobian hits circuits: hitting-sets, lower bounds for depth-\(D\) occur-\(k\) formulas \& depth-\(3\) transcendence degree-\(k\) circuits
• Linear independence, alternants, and applications
• Title not available (Why is that?)

This page was built for publication: Jacobian hits circuits: hitting sets, lower bounds for depth-\(D\) occur-\(k\) formulas and depth-3 transcendence degree-\(k\) circuits

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2817792)