Jacobian Hits Circuits: Hitting Sets, Lower Bounds for Depth-$D$ Occur-$k$ Formulas and Depth-3 Transcendence Degree-$k$ Circuits (Q2817792): Difference between revisions

Latest revision as of 11:59, 12 July 2024

scientific article

Language	Label	Description	Also known as
English	Jacobian Hits Circuits: Hitting Sets, Lower Bounds for Depth-$D$ Occur-$k$ Formulas and Depth-3 Transcendence Degree-$k$ Circuits	scientific article

Statements

instance of

scholarly article

0 references

title

Jacobian Hits Circuits: Hitting Sets, Lower Bounds for Depth-$D$ Occur-$k$ Formulas and Depth-3 Transcendence Degree-$k$ Circuits (English)

0 references

author

Chandan Saha

0 references

Ramprasad Saptharishi

0 references

Nitin Saxena

0 references

Manindra Agrawal

0 references

published in

SIAM Journal on Computing

0 references

publication date

2 September 2016

0 references

zbMATH Keywords

algebraic independence

0 references

black box

0 references

circuits

0 references

depth

0 references

identity testing

0 references

immanant

0 references

Jacobian

0 references

lower bound

0 references

Vandermonde

0 references

MaRDI profile type

MaRDI publication profile

0 references

full work available at URL

https://doi.org/10.1137/130910725

0 references

cites work

FSTTCS 2005: Foundations of Software Technology and Theoretical Computer Science

0 references

PRIMES is in P

0 references

Proof verification and the hardness of approximation problems

0 references

Quasi-polynomial hitting-set for set-depth-Δ formulas

0 references

Jacobian hits circuits

0 references

Q2913799

0 references

Algebraic Independence and Blackbox Identity Testing

0 references

Algebraic independence and blackbox identity testing

0 references

On zero-testing and interpolation of $k$-sparse multivariate polynomials over finite fields

0 references

Partial Derivatives in Arithmetic Complexity and Beyond

0 references

A probabilistic remark on algebraic program testing

0 references

Locally decodable codes with 2 queries and polynomial identity testing for depth 3 circuits

0 references

Arithmetic Circuits: A Chasm at Depth 3

0 references

Q2911618

0 references

Deterministic extractors for affine sources over large fields

0 references

Q3942397

0 references

Deterministic Polynomial Time Algorithms for Matrix Completion Problems

0 references

Q4526985

0 references

A Lower Bound for the Formula Size of Rational Functions

0 references

Derandomizing polynomial identity tests means proving circuit lower bounds

0 references

Deterministic identity testing of depth-4 multilinear circuits with bounded top fan-in

0 references

Arithmetic circuits: the chasm at depth four gets wider

0 references

Randomness efficient identity testing of multivariate polynomials

0 references

Q3002772

0 references

Polynomial identity testing for depth 3 circuits

0 references

Black box polynomial identity testing of generalized depth-3 arithmetic circuits with bounded top fan-in

0 references

Blackbox Polynomial Identity Testing for Depth 3 Circuits

0 references

Algebraic methods for interactive proof systems

0 references

Q3891767

0 references

Algebraic independence in positive characteristic: A $p$-adic calculus

0 references

On P vs. NP and geometric complexity theory

0 references

Matching is as easy as matrix inversion

0 references

Q3135082

0 references

Exponential lower bounds for depth three Boolean circuits

0 references

Q3549708

0 references

Fast Probabilistic Algorithms for Verification of Polynomial Identities

0 references

An Almost Optimal Rank Bound for Depth-3 Identities

0 references

Blackbox identity testing for bounded top fanin depth-3 circuits

0 references

A complexity theory based on Boolean algebra

0 references

Q5302074

0 references

Improved Polynomial Identity Testing for Read-Once Formulas

0 references

On the Relation between Polynomial Identity Testing and Finding Variable Disjoint Factors

0 references

Black-box identity testing of depth-4 multilinear circuits

0 references

Depth-3 arithmetic circuits over fields of characteristic zero

0 references

Arithmetic Circuits: A survey of recent results and open questions

0 references

Pseudo-random generators for all hardnesses

0 references

Fast Parallel Computation of Polynomials Using Few Processors

0 references

Q3851616

0 references

Identifiers

zbMATH Open document ID

1350.68292

0 references

DOI

10.1137/130910725

0 references

Mathematics Subject Classification ID

0 references

0 references

0 references

0 references

0 references

0 references

Sitelinks

Mathematics(1 entry)

mardi Publication:2817792

@@ Property / author @@
-Manindra Agrawal
@@ Property / author: Manindra Agrawal / rank @@
-Normal rank
@@ Property / author @@
+Manindra Agrawal
@@ Property / author: Manindra Agrawal / rank @@
+Normal rank
@@ Property / MaRDI profile type @@
+MaRDI publication profile
@@ Property / MaRDI profile type: MaRDI publication profile / rank @@
+Normal rank
@@ Property / full work available at URL @@
+https://doi.org/10.1137/130910725
@@ Property / full work available at URL: https://doi.org/10.1137/130910725 / rank @@
+Normal rank
@@ Property / OpenAlex ID @@
+W2508387244
@@ Property / OpenAlex ID: W2508387244 / rank @@
+Normal rank
@@ Property / cites work @@
+FSTTCS 2005: Foundations of Software Technology and Theoretical Computer Science
+Normal rank
@@ Property / cites work @@
+PRIMES is in P
@@ Property / cites work: PRIMES is in P / rank @@
+Normal rank
@@ Property / cites work @@
+Proof verification and the hardness of approximation problems
+Normal rank
@@ Property / cites work @@
+Quasi-polynomial hitting-set for set-depth-Δ formulas
+Normal rank
@@ Property / cites work @@
+Jacobian hits circuits
@@ Property / cites work: Jacobian hits circuits / rank @@
+Normal rank
@@ Property / cites work @@
+Q2913799
@@ Property / cites work: Q2913799 / rank @@
+Normal rank
@@ Property / cites work @@
+Algebraic Independence and Blackbox Identity Testing
+Normal rank
@@ Property / cites work @@
+Algebraic independence and blackbox identity testing
+Normal rank
@@ Property / cites work @@
+On zero-testing and interpolation of \(k\)-sparse multivariate polynomials over finite fields
+Normal rank
@@ Property / cites work @@
+Partial Derivatives in Arithmetic Complexity and Beyond
+Normal rank
@@ Property / cites work @@
+A probabilistic remark on algebraic program testing
+Normal rank
@@ Property / cites work @@
+Locally decodable codes with 2 queries and polynomial identity testing for depth 3 circuits
+Normal rank
@@ Property / cites work @@
+Arithmetic Circuits: A Chasm at Depth 3
@@ Property / cites work: Arithmetic Circuits: A Chasm at Depth 3 / rank @@
+Normal rank
@@ Property / cites work @@
+Q2911618
@@ Property / cites work: Q2911618 / rank @@
+Normal rank
@@ Property / cites work @@
+Deterministic extractors for affine sources over large fields
+Normal rank
@@ Property / cites work @@
+Q3942397
@@ Property / cites work: Q3942397 / rank @@
+Normal rank
@@ Property / cites work @@
+Deterministic Polynomial Time Algorithms for Matrix Completion Problems
+Normal rank
@@ Property / cites work @@
+Q4526985
@@ Property / cites work: Q4526985 / rank @@
+Normal rank
@@ Property / cites work @@
+A Lower Bound for the Formula Size of Rational Functions
+Normal rank
@@ Property / cites work @@
+Derandomizing polynomial identity tests means proving circuit lower bounds
+Normal rank
@@ Property / cites work @@
+Deterministic identity testing of depth-4 multilinear circuits with bounded top fan-in
+Normal rank
@@ Property / cites work @@
+Arithmetic circuits: the chasm at depth four gets wider
+Normal rank
@@ Property / cites work @@
+Randomness efficient identity testing of multivariate polynomials
+Normal rank
@@ Property / cites work @@
+Q3002772
@@ Property / cites work: Q3002772 / rank @@
+Normal rank
@@ Property / cites work @@
+Polynomial identity testing for depth 3 circuits
@@ Property / cites work: Polynomial identity testing for depth 3 circuits / rank @@
+Normal rank
@@ Property / cites work @@
+Black box polynomial identity testing of generalized depth-3 arithmetic circuits with bounded top fan-in
+Normal rank
@@ Property / cites work @@
+Blackbox Polynomial Identity Testing for Depth 3 Circuits
+Normal rank
@@ Property / cites work @@
+Algebraic methods for interactive proof systems
@@ Property / cites work: Algebraic methods for interactive proof systems / rank @@
+Normal rank
@@ Property / cites work @@
+Q3891767
@@ Property / cites work: Q3891767 / rank @@
+Normal rank
@@ Property / cites work @@
+Algebraic independence in positive characteristic: A $p$-adic calculus
+Normal rank
@@ Property / cites work @@
+On P vs. NP and geometric complexity theory
@@ Property / cites work: On P vs. NP and geometric complexity theory / rank @@
+Normal rank
@@ Property / cites work @@
+Matching is as easy as matrix inversion
@@ Property / cites work: Matching is as easy as matrix inversion / rank @@
+Normal rank
@@ Property / cites work @@
+Q3135082
@@ Property / cites work: Q3135082 / rank @@
+Normal rank
@@ Property / cites work @@
+Exponential lower bounds for depth three Boolean circuits
+Normal rank
@@ Property / cites work @@
+Q3549708
@@ Property / cites work: Q3549708 / rank @@
+Normal rank
@@ Property / cites work @@
+Fast Probabilistic Algorithms for Verification of Polynomial Identities
+Normal rank
@@ Property / cites work @@
+An Almost Optimal Rank Bound for Depth-3 Identities
+Normal rank
@@ Property / cites work @@
+Blackbox identity testing for bounded top fanin depth-3 circuits
+Normal rank
@@ Property / cites work @@
+A complexity theory based on Boolean algebra
@@ Property / cites work: A complexity theory based on Boolean algebra / rank @@
+Normal rank
@@ Property / cites work @@
+Q5302074
@@ Property / cites work: Q5302074 / rank @@
+Normal rank
@@ Property / cites work @@
+Improved Polynomial Identity Testing for Read-Once Formulas
+Normal rank
@@ Property / cites work @@
+On the Relation between Polynomial Identity Testing and Finding Variable Disjoint Factors
+Normal rank
@@ Property / cites work @@
+Black-box identity testing of depth-4 multilinear circuits
+Normal rank
@@ Property / cites work @@
+Depth-3 arithmetic circuits over fields of characteristic zero
+Normal rank
@@ Property / cites work @@
+Arithmetic Circuits: A survey of recent results and open questions
+Normal rank
@@ Property / cites work @@
+Pseudo-random generators for all hardnesses
@@ Property / cites work: Pseudo-random generators for all hardnesses / rank @@
+Normal rank
@@ Property / cites work @@
+Fast Parallel Computation of Polynomials Using Few Processors
+Normal rank
@@ Property / cites work @@
+Q3851616
@@ Property / cites work: Q3851616 / rank @@
+Normal rank