Lower bounds for arithmetic circuits via the Hankel matrix

DOI10.1007/S00037-021-00214-1OpenAlexW3204259261MaRDI QIDQ2051372

Guillaume Lagarde, Olivier Serre, Pierre Ohlmann, Nathanaël Fijalkow

Publication date: 24 November 2021

Published in: Computational Complexity (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/s00037-021-00214-1

zbMATH Keywords

Hankel matrixlower boundsarithmetic circuit complexityparse trees

Mathematics Subject Classification ID

Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17)

Related Items (1)

Unnamed Item

Uses Software

• OEIS

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• The complexity of computing the permanent
• The rank of a formal tree power series
• The complexity of partial derivatives
• Matrices de Hankel
• Non-commutative arithmetic circuits: depth reduction and size lower bounds
• Hardness vs randomness
• Lower bounds on arithmetic circuits via partial derivatives
• Deterministic identity testing for sum of read-once oblivious arithmetic branching programs
• Deterministic polynomial identity testing in non-commutative models
• Depth-4 lower bounds, determinantal complexity: a unified approach
• Lower bounds and PIT for non-commutative arithmetic circuits with restricted parse trees
• Characterizing Valiant's algebraic complexity classes
• An Exponential Lower Bound for Homogeneous Depth Four Arithmetic Formulas
• On the Power of Homogeneous Depth 4 Arithmetic Circuits
• Some Exact Complexity Results for Straight-Line Computations over Semirings
• Hitting-Sets for ROABP and Sum of Set-Multilinear Circuits
• Lower bounds for depth 4 formulas computing iterated matrix multiplication
• A super-polynomial lower bound for regular arithmetic formulas
• Hitting sets for multilinear read-once algebraic branching programs, in any order
• Separating multilinear branching programs and formulas
• Approaching the Chasm at Depth Four
• Non-commutative circuits and the sum-of-squares problem
• Derandomizing polynomial identity tests means proving circuit lower bounds
• Lower bounds for special cases of syntactic multilinear ABPs

This page was built for publication: Lower bounds for arithmetic circuits via the Hankel matrix