Partial Derivatives in Arithmetic Complexity and Beyond

DOI10.1561/0400000043zbMath1278.68010OpenAlexW4293765205MaRDI QIDQ2872492

Avi Wigderson, Xi Chen, Neeraj Kayal

Publication date: 15 January 2014

Published in: Foundations and Trends® in Theoretical Computer Science (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1561/0400000043

zbMATH Keywords

upper and lower boundsmultivariate polynomialarithmetic complexitypartial derivativescomplexity of polynomials

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Symbolic computation and algebraic computation (68W30) Polynomials in real and complex fields: location of zeros (algebraic theorems) (12D10) Research exposition (monographs, survey articles) pertaining to computer science (68-02) Polynomials, factorization in commutative rings (13P05) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17)

Related Items (19)

Exact learning from an honest teacher that answers membership queries ⋮ An Exponential Lower Bound for Homogeneous Depth Four Arithmetic Formulas ⋮ Barriers for Rank Methods in Arithmetic Complexity ⋮ Fundamental invariants of orbit closures ⋮ Representation of monomials as a sum of powers of linear forms ⋮ Unnamed Item ⋮ Unnamed Item ⋮ A restriction estimate using polynomial partitioning ⋮ Jacobian Hits Circuits: Hitting Sets, Lower Bounds for Depth-$D$ Occur-$k$ Formulas and Depth-3 Transcendence Degree-$k$ Circuits ⋮ Unnamed Item ⋮ Leakage-resilience of the Shamir secret-sharing scheme against physical-bit leakages ⋮ A Selection of Lower Bounds for Arithmetic Circuits ⋮ Flattenings and Koszul Young flattenings arising in complexity theory ⋮ On the Symmetries of and Equivalence Test for Design Polynomials. ⋮ A super-quadratic lower bound for depth four arithmetic circuits ⋮ Tropical Complexity, Sidon Sets, and Dynamic Programming ⋮ A \(\tau \)-conjecture for Newton polygons ⋮ Geometric complexity theory: an introduction for geometers ⋮ Polynomial-time algorithms for quadratic isomorphism of polynomials: the regular case

This page was built for publication: Partial Derivatives in Arithmetic Complexity and Beyond