A lower bound on the number of additions in monotone computations
From MaRDI portal
Publication:1232179
DOI10.1016/0304-3975(76)90083-9zbMath0342.68024OpenAlexW2020346765MaRDI QIDQ1232179
Publication date: 1976
Published in: Theoretical Computer Science (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1016/0304-3975(76)90083-9
Related Items
Affine projections of symmetric polynomials., Cancellation is exponentially powerful for computing the determinant, On semiring complexity of Schur polynomials, Lower bounds for monotone counting circuits, The complexity of computing the permanent, Minkowski Complexity of Sets: An Easy Lower Bound, Integer complexity and well-ordering, Multilinear formulas, maximal-partition discrepancy and mixed-sources extractors, Monotone arithmetic complexity of graph homomorphism polynomials, Negation can be exponentially powerful, Lower bounds for monotone \(q\)-multilinear Boolean circuits, A note on 'Is shortest path problem not harder than matrix multiplication?', Towards an Almost Quadratic Lower Bound on the Monotone Circuit Complexity of the Boolean Convolution, Bounds for Semi-disjoint Bilinear Forms in a Unit-Cost Computational Model, Lower bounds for tropical circuits and dynamic programs, Lower bounds for resolution and cutting plane proofs and monotone computations, Small normalized circuits for semi-disjoint bilinear forms require logarithmic and-depth, A lower bound on the number of additions in monotone computations, A note on Schnorr's separatedness, Subtraction-free complexity, cluster transformations, and spanning trees, Lower bounds on the worst-case complexity of some oracle algorithms, A lower bound of \({1\over 2}n^2\) on linear search programs for the knapsack problem, A counterexample to a conjecture of Schnorr referring to monotone networks, Unnamed Item, Tropical Complexity, Sidon Sets, and Dynamic Programming, Lower bounds in algebraic computational complexity
Cites Work
