Lower bounds for arithmetic circuits via the Hankel matrix
From MaRDI portal
Publication:2051372
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
Related Items (1)
Uses Software
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
