Some Exact Complexity Results for Straight-Line Computations over Semirings
From MaRDI portal
Publication:3945585
Cited in
(55)- Lower bounds on monotone arithmetic circuits with restricted depths
- Non-commutative arithmetic circuits: depth reduction and size lower bounds
- A lower bound for monotone arithmetic circuits computing \(0-1\) permanent
- Lower bounds on the depth of monotone arithmetic computations
- Greedy can beat pure dynamic programming
- On semiring complexity of Schur polynomials
- Lower bounds for arithmetic circuits via the Hankel matrix
- Limitations of sums of bounded read formulas and ABPs
- Tropicalization, symmetric polynomials, and complexity
- Slightly improved lower bounds for homogeneous formulas of bounded depth and bounded individual degree
- Lower bounds and PIT for non-commutative arithmetic circuits with restricted parse trees
- Valiant's holant theorem and matchgate tensors
- Incremental versus non-incremental dynamic programming
- Exponential lower bounds on the complexity of a class of dynamic programs for combinatorial optimization problems
- Characterizing Valiant's algebraic complexity classes
- A Selection of Lower Bounds for Arithmetic Circuits
- \(\mathrm P \overset {?} {=} \mathrm{NP}\)
- Tropical complexity, Sidon sets, and dynamic programming
- Cancellation is exponentially powerful for computing the determinant
- Log-concavity and lower bounds for arithmetic circuits
- On the Expressive Power of Read-Once Determinants
- Lower bounds for monotone counting circuits
- Arithmetic Circuits, Monomial Algebras and Finite Automata
- Are there elimination algorithms for the permanent?
- Lower bounds for tropical circuits and dynamic programs
- Patching colors with tensors
- A super-quadratic lower bound for depth four arithmetic circuits
- scientific article; zbMATH DE number 7204375 (Why is no real title available?)
- scientific article; zbMATH DE number 7204408 (Why is no real title available?)
- Limitations of incremental dynamic programming
- Approximation limitations of pure dynamic programming
- Regular expression length via arithmetic formula complexity
- Subtraction-free complexity, cluster transformations, and spanning trees
- Monotone circuit lower bounds from robust sunflowers
- Shadows of Newton polytopes
- Monotone arithmetic complexity of graph homomorphism polynomials
- ReLU neural networks of polynomial size for exact maximum flow computation
- Lower bounds for monotone q-multilinear Boolean circuits
- On the expressive power of CNF formulas of bounded tree- and clique-width
- Multilinear formulas, maximal-partition discrepancy and mixed-sources extractors
- Monotone classes beyond VNP
- Notes on Boolean read-k and multilinear circuits
- Symmetric arithmetic circuits
- Symmetric arithmetic circuits
- Superpolynomial lower bounds against low-depth algebraic circuits
- Monotone classes beyond VNP
- ReLU neural networks of polynomial size for exact maximum flow computation
- Lower bounds on dynamic programming for maximum weight independent set
- Monotone bounded-depth complexity of homomorphism polynomials
- Arithmetic circuits and neural networks for regular matroids
- Sorting can exponentially speed up pure dynamic programming
- Size-depth trade-offs for monotone arithmetic circuits
- Integer complexity and well-ordering
- Complexity of tropical Schur polynomials
- Monotone separations for constant degree polynomials
This page was built for publication: Some Exact Complexity Results for Straight-Line Computations over Semirings
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q3945585)
