scientific article; zbMATH DE number 7250152

DOI10.4230/LIPICS.CCC.2018.12zbMATH Open1441.68039MaRDI QIDQ5121900FDOQ5121900

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

Publication date: 22 September 2020

Title of this publication is not available (Why is that?)

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

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)

Cites Work

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

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
• Title not available (Why is that?)

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)