scientific article; zbMATH DE number 7250152

DOI10.4230/LIPICS.CCC.2018.12MaRDI QIDQ5121900zbMATH OpenFDO

Authors Marco L. Carmosino, Russell Impagliazzo, Shachar Lovett, Ivan Mihajlin

Publication date 22 September 2020

zbMATH Keywords

arithmetic circuitscircuit lower boundshardness amplificationnon-commutative computation

Mathematics Subject Classification ID

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

Recommendations

• Non-commutative circuits and the sum-of-squares problem
• Lower bounds for non-commutative skew circuits
• On Lower Bounds for Constant Width Arithmetic Circuits
• Lower bounds for arithmetic circuits via the Hankel matrix
• On lower bounds for multiplicative circuits and linear circuits in noncommutative domains

Cites work

• Arithmetic circuits: a chasm at depth 3
• Arithmetic circuits: a survey of recent results and open questions
• Arithmetic circuits: the chasm at depth four gets wider
• Natural proofs
• Non-commutative circuits and the sum-of-squares problem
• Noncommutative Valiant's classes: structure and complete problems
• On the hardness of the noncommutative determinant
• Powers of tensors and fast matrix multiplication
• Randomized polynomial time identity testing for noncommutative circuits
• Succinct hitting sets and barriers to proving algebraic circuits lower bounds
• The complexity of partial derivatives

Cited in

(5)

• A super-quadratic lower bound for depth four arithmetic circuits
• Non-commutative arithmetic circuits: depth reduction and size lower bounds
• Lower bounds for arithmetic circuits via the Hankel matrix
• Hardness magnification near state-of-the-art lower bounds
• scientific article; zbMATH DE number 7561765 (Why is no real title available?)

This page was built for publication:

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5121900)