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

algebraic complexityarithmetic circuitsexplicit polynomialslower boundspermanent

Mathematics Subject Classification ID

Complexity classes (hierarchies, relations among complexity classes, etc.) (68Q15) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) 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

(34)

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

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)