Elusive functions and lower bounds for arithmetic circuits

DOI10.4086/TOC.2010.V006A007MaRDI QIDQ3002820zbMATH OpenOpenAlexFDO

Authors Ran Raz

Publication date 24 May 2011

Published in Theory of Computing (Search for Journal in Brave)

Copyright license Creative Commons Attribution 4.0 International

Full work available at URL https://doi.org/10.4086/toc.2010.v006a007

zbMATH Keywords

lower boundsarithmetic circuitspermanentalgebraic complexityexplicit polynomials

Mathematics Subject Classification ID

Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Complexity classes (hierarchies, relations among complexity classes, etc.) (68Q15) Analytic circuit theory (94C05)

Recommendations

• Lower bounds for the circuit size of partially homogeneous polynomials
• Arithmetic circuits: a chasm at depth 3
• scientific article; zbMATH DE number 1775446
• Depth-3 arithmetic circuits over fields of characteristic zero
• The computational power of depth five arithmetic circuits

Cited in

(31)

• Permanent does not have succinct polynomial size arithmetic circuits of constant depth
• Multi-k-ic depth three circuit lower bound
• scientific article; zbMATH DE number 7250153 (Why is no real title available?)
• Lower bounds for matrix factorization
• A super-quadratic lower bound for depth four arithmetic circuits
• Lower bounds for matrix factorization
• Real \(\tau \)-conjecture for sum-of-squares: a unified approach to lower bound and derandomization
• On the closures of monotone algebraic classes and variants of the determinant
• Unbalancing sets and an almost quadratic lower bound for syntactically multilinear arithmetic circuits
• On the power of homogeneous depth 4 arithmetic circuits
• scientific article; zbMATH DE number 7250151 (Why is no real title available?)
• Lower bounds for the circuit size of partially homogeneous polynomials
• Lower bounds for planar arithmetic circuits
• A polynomial degree bound on equations for non-rigid matrices and small linear circuits
• On defining integers and proving arithmetic circuit lower bounds
• Unifying known lower bounds via geometric complexity theory
• Determinants vs. algebraic branching programs
• Functional lower bounds for arithmetic circuits and connections to boolean circuit complexity
• Low-depth algebraic circuit lower bounds over any field
• Determinants vs. algebraic branching programs
• Algebraic geometry and representation theory in the study of matrix multiplication complexity and other problems in theoretical computer science
• On fixed-polynomial size circuit lower bounds for uniform polynomials in the sense of Valiant
• Algebraic complexity classes
• Lower bounds for planar arithmetic circuits
• scientific article; zbMATH DE number 7009617 (Why is no real title available?)
• Succinct functional commitment for a large class of arithmetic circuits
• Superpolynomial lower bounds against low-depth algebraic circuits
• Improved lower bound, and proof barrier, for constant depth algebraic circuits
• Weighted sum-of-squares lower bounds for univariate polynomials imply \(\mathsf{VP} \neq \mathsf{VNP}\)
• Uniform derandomization from pathetic lower bounds
• scientific article; zbMATH DE number 1148334 (Why is no real title available?)

This page was built for publication: Elusive functions and lower bounds for arithmetic circuits

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