scientific article; zbMATH DE number 7250153

DOI10.4230/LIPIcs.CCC.2018.13zbMath1441.68040MaRDI QIDQ5121901

Mrinal Kumar, Chi-Ning Chou, Noam Solomon

Publication date: 22 September 2020

Title: zbMATH Open Web Interface contents unavailable due to conflicting licenses.

zbMATH Keywords

algebraic complexitypolynomial identity testingpolynomial factorization circuit lower bounds

Mathematics Subject Classification ID

Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Randomized algorithms (68W20) Networks and circuits as models of computation; circuit complexity (68Q06)

Related Items (5)

Sylvester-Gallai type theorems for quadratic polynomials ⋮ Unnamed Item ⋮ Unnamed Item ⋮ A generalized sylvester-gallai type theorem for quadratic polynomials ⋮ Improved hitting set for orbit of ROABPs

Uses Software

• GitHub
• lowerbounds-survey

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Factors of low individual degree polynomials
• Arithmetic circuits: the chasm at depth four gets wider
• Lower bounds and separations for constant depth multilinear circuits
• The complexity of partial derivatives
• Hardness vs randomness
• Lower bounds on arithmetic circuits via partial derivatives
• The complexity of factors of multivariate polynomials
• Improved bounds for reduction to depth 4 and depth 3
• Arithmetic Circuits: A survey of recent results and open questions
• A Lower Bound for the Size of Syntactically Multilinear Arithmetic Circuits
• Hardness-Randomness Tradeoffs for Bounded Depth Arithmetic Circuits
• A Lower Bound for the Formula Size of Rational Functions
• Lower bounds for depth 4 formulas computing iterated matrix multiplication
• A super-polynomial lower bound for regular arithmetic formulas
• Tensor-Rank and Lower Bounds for Arithmetic Formulas
• Approaching the Chasm at Depth Four
• Derandomizing polynomial identity tests means proving circuit lower bounds

This page was built for publication: