scientific article

DOI10.4086/toc.2006.v002a006zbMath1213.68301OpenAlexW2110206454MaRDI QIDQ3002768

Ran Raz

Publication date: 24 May 2011

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

Full work available at URL: https://doi.org/10.4086/toc.2006.v002a006

Title: zbMATH Open Web Interface contents unavailable due to conflicting licenses.

zbMATH Keywords

lower boundsalgebraic complexityarithmetic circuitsmultilinear polynomialsseparation of complexity classeslog-depth

Mathematics Subject Classification ID

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

Related Items (30)

Subexponential size hitting sets for bounded depth multilinear formulas ⋮ Quadratic lower bounds for algebraic branching programs and formulas ⋮ Resource trade-offs in syntactically multilinear arithmetic circuits ⋮ Characterizing Propositional Proofs as Noncommutative Formulas ⋮ Small-depth Multilinear Formula Lower Bounds for Iterated Matrix Multiplication, with Applications. ⋮ The Shifted Partial Derivative Complexity of Elementary Symmetric Polynomials ⋮ Lower Bounds for Depth-4 Formulas Computing Iterated Matrix Multiplication ⋮ Multilinear formulas, maximal-partition discrepancy and mixed-sources extractors ⋮ \textsf{VNP} = \textsf{VP} in the multilinear world ⋮ An Exponential Lower Bound for Homogeneous Depth Four Arithmetic Formulas ⋮ Unbalancing sets and an almost quadratic lower bound for syntactically multilinear arithmetic circuits ⋮ Algebraic proofs over noncommutative formulas ⋮ Unnamed Item ⋮ A Quadratic Size-Hierarchy Theorem for Small-Depth Multilinear Formulas ⋮ Read-once polynomial identity testing ⋮ Small-Depth Multilinear Formula Lower Bounds for Iterated Matrix Multiplication with Applications ⋮ Resolution over linear equations and multilinear proofs ⋮ Lower Bounds for Syntactically Multilinear Algebraic Branching Programs ⋮ Lower bounds for special cases of syntactic multilinear ABPs ⋮ Slightly improved lower bounds for homogeneous formulas of bounded depth and bounded individual degree ⋮ Unnamed Item ⋮ Unnamed Item ⋮ Algebraic Complexity Classes ⋮ A Selection of Lower Bounds for Arithmetic Circuits ⋮ A quadratic lower bound for algebraic branching programs ⋮ A super-quadratic lower bound for depth four arithmetic circuits ⋮ On Proving Parameterized Size Lower Bounds for Multilinear Algebraic Models ⋮ Unnamed Item ⋮ Unifying known lower bounds via geometric complexity theory ⋮ Limitations of sums of bounded read formulas and ABPs

This page was built for publication: