Multi-linear formulas for permanent and determinant are of super-polynomial size

DOI10.1145/1502793.1502797zbMath1325.68112OpenAlexW2023541349MaRDI QIDQ5899508

Ran Raz

Publication date: 11 November 2015

Published in: Journal of the ACM (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1145/1502793.1502797

zbMATH Keywords

lower boundscircuit complexityalgebraic complexityarithmetic formulas

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Determinants, permanents, traces, other special matrix functions (15A15) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17)

Related Items (35)

Subexponential size hitting sets for bounded depth multilinear formulas ⋮ On the hardness of the determinant: sum of regular set-multilinear circuits ⋮ Resource trade-offs in syntactically multilinear arithmetic circuits ⋮ Unnamed Item ⋮ Characterizing Propositional Proofs as Noncommutative Formulas ⋮ The Shifted Partial Derivative Complexity of Elementary Symmetric Polynomials ⋮ Lower Bounds for Depth-4 Formulas Computing Iterated Matrix Multiplication ⋮ Sums of read-once formulas: how many summands are necessary? ⋮ Multi-\(k\)-ic depth three circuit lower bound ⋮ An Exponential Lower Bound for Homogeneous Depth Four Arithmetic Formulas ⋮ Unbalancing sets and an almost quadratic lower bound for syntactically multilinear arithmetic circuits ⋮ Lower bounds for the determinantal complexity of explicit low degree polynomials ⋮ Algebraic proofs over noncommutative formulas ⋮ Unnamed Item ⋮ Barriers for Rank Methods in Arithmetic Complexity ⋮ Read-once polynomial identity testing ⋮ Sums of Read-Once Formulas: How Many Summands Suffice? ⋮ On the complexity of the permanent in various computational models ⋮ A note on parameterized polynomial identity testing using hitting set generators ⋮ Unnamed Item ⋮ Average-case linear matrix factorization and reconstruction of low width algebraic branching programs ⋮ Lower bounds for special cases of syntactic multilinear ABPs ⋮ Unnamed Item ⋮ On the Size of Homogeneous and of Depth-Four Formulas with Low Individual Degree ⋮ Unnamed Item ⋮ A Selection of Lower Bounds for Arithmetic Circuits ⋮ Towards Optimal Depth Reductions for Syntactically Multilinear Circuits ⋮ On the Symmetries of and Equivalence Test for Design Polynomials. ⋮ A super-quadratic lower bound for depth four arithmetic circuits ⋮ On Proving Parameterized Size Lower Bounds for Multilinear Algebraic Models ⋮ Unnamed Item ⋮ Lower bounds and PIT for non-commutative arithmetic circuits with restricted parse trees ⋮ Approaching the Chasm at Depth Four ⋮ Unifying known lower bounds via geometric complexity theory ⋮ Limitations of sums of bounded read formulas and ABPs

This page was built for publication: Multi-linear formulas for permanent and determinant are of super-polynomial size