Arithmetic circuits: a chasm at depth three

DOI10.1109/FOCS.2013.68MaRDI QIDQ6981717zbMATH OpenFDO

Authors Ankit Gupta, Neeraj Kayal, Ramprasad Saptharishi, Pritish Kamath

Publication date 20 May 2025

Full work available at URL https://doi.org/10.1109/FOCS.2013.68

Mathematics Subject Classification ID

Combinatorics (05-XX) Computer science (68-XX) Information and communication theory, circuits (94-XX)

Cited in

(7)

• Linear independence, alternants and applications
• Low-depth algebraic circuit lower bounds over any field
• Bernstein-Gelfand-Gelfand meets geometric complexity theory: resolving the 2 2 permanents of a 2 n matrix
• A largish sum-of-squares implies circuit hardness and derandomization
• Reconstruction of depth 3 arithmetic circuits with top fan-in 3
• Algebraic metacomplexity and representation theory
• Real -conjecture for sum-of-squares: a unified approach to lower bound and derandomization

This page was built for publication: Arithmetic circuits: a chasm at depth three

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