Some Exact Complexity Results for Straight-Line Computations over Semirings
From MaRDI portal
Publication:3945585
DOI10.1145/322326.322341zbMath0485.68038OpenAlexW2021082954MaRDI QIDQ3945585
Publication date: 1982
Published in: Journal of the ACM (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1145/322326.322341
permanentalgebraic complexityarithmetic complexityiterated matrix multiplicationFarkas lemmaiterated convolutionminimax algebraconvexity theorynumber of multiplicationsrelations among complexity classescomputation of polynomialsstraight- line algorithm
Related Items
Cancellation is exponentially powerful for computing the determinant, Greedy can beat pure dynamic programming, On semiring complexity of Schur polynomials, Some complete and intermediate polynomials in algebraic complexity theory, Lower bounds for monotone counting circuits, Valiant's holant theorem and matchgate tensors, Arithmetic Circuits, Monomial Algebras and Finite Automata, Log-Concavity and Lower Bounds for Arithmetic Circuits, On the Expressive Power of Read-Once Determinants, Integer complexity and well-ordering, Incremental versus non-incremental dynamic programming, On the expressive power of CNF formulas of bounded tree- and clique-width, Multilinear formulas, maximal-partition discrepancy and mixed-sources extractors, Shadows of Newton polytopes, Monotone arithmetic complexity of graph homomorphism polynomials, ReLU neural networks of polynomial size for exact maximum flow computation, Are there elimination algorithms for the permanent?, Complexity of tropical Schur polynomials, Lower bounds for monotone \(q\)-multilinear Boolean circuits, Exponential lower bounds on the complexity of a class of dynamic programs for combinatorial optimization problems, Lower bounds for tropical circuits and dynamic programs, Limitations of incremental dynamic programming, Characterizing Valiant's algebraic complexity classes, Unnamed Item, Monotone separations for constant degree polynomials, Tropicalization, symmetric polynomials, and complexity, Subtraction-free complexity, cluster transformations, and spanning trees, Regular expression length via arithmetic formula complexity, Slightly improved lower bounds for homogeneous formulas of bounded depth and bounded individual degree, Unnamed Item, Unnamed Item, Approximation Limitations of Pure Dynamic Programming, Lower bounds for arithmetic circuits via the Hankel matrix, A Selection of Lower Bounds for Arithmetic Circuits, A super-quadratic lower bound for depth four arithmetic circuits, $$P\mathop{ =}\limits^{?}NP$$, Non-commutative arithmetic circuits: depth reduction and size lower bounds, A lower bound for monotone arithmetic circuits computing \(0-1\) permanent, Tropical Complexity, Sidon Sets, and Dynamic Programming, Lower bounds and PIT for non-commutative arithmetic circuits with restricted parse trees, Lower bounds on the depth of monotone arithmetic computations, Sorting can exponentially speed up pure dynamic programming, Monotone circuit lower bounds from robust sunflowers, Size-depth trade-offs for monotone arithmetic circuits, Lower bounds on monotone arithmetic circuits with restricted depths, Limitations of sums of bounded read formulas and ABPs
