Negation can be exponentially powerful

DOI10.1016/0304-3975(80)90060-2zbMath0442.68030OpenAlexW1966757974MaRDI QIDQ1143790

Leslie G. Valiant

Publication date: 1980

Published in: Theoretical Computer Science (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/0304-3975(80)90060-2

zbMATH Keywords

negationsalgebraic algorithmscancellation of termscomputing multivariate polynomialscounting perfect matchings in planar graphs

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Graph theory (including graph drawing) in computer science (68R10)

Related Items (27)

Cancellation is exponentially powerful for computing the determinant ⋮ Greedy can beat pure dynamic programming ⋮ On semiring complexity of Schur polynomials ⋮ Lower bounds for monotone counting circuits ⋮ Valiant's holant theorem and matchgate tensors ⋮ Lower bounds on arithmetic circuits via partial derivatives ⋮ On the relative power of reduction notions in arithmetic circuit complexity ⋮ Log-Concavity and Lower Bounds for Arithmetic Circuits ⋮ Integer complexity and well-ordering ⋮ Multilinear formulas, maximal-partition discrepancy and mixed-sources extractors ⋮ Shadows of Newton polytopes ⋮ On the complexity of computing bilinear forms with \(\{0,1\}\) constants ⋮ Complexity of tropical Schur polynomials ⋮ Unnamed Item ⋮ On \(\epsilon\)-sensitive monotone computations ⋮ Lower bounds for tropical circuits and dynamic programs ⋮ Small normalized circuits for semi-disjoint bilinear forms require logarithmic and-depth ⋮ Monotone separations for constant degree polynomials ⋮ Building above read-once polynomials: identity testing and hardness of representation ⋮ Subtraction-free complexity, cluster transformations, and spanning trees ⋮ Unnamed Item ⋮ A super-quadratic lower bound for depth four arithmetic circuits ⋮ Non-cancellative Boolean circuits: A generalization of monotone boolean circuits ⋮ Tropical Complexity, Sidon Sets, and Dynamic Programming ⋮ Lower bounds in algebraic computational complexity ⋮ A direct version of Shamir and Snir's lower bounds on monotone circuit depth ⋮ Lower bounds on monotone arithmetic circuits with restricted depths

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Complexity of monotone networks for Boolean matrix product
• Monotone switching circuits and Boolean matrix product
• A lower bound on the number of additions in monotone computations
• Matrix tree theorems
• Gaussian elimination is not optimal
• Combinatorial methods
• The statistics of dimers on a lattice
• Statistical Mechanics of Dimers on a Plane Lattice
• The Power of Negative Thinking in Multiplying Boolean Matrices
• Shifting Graphs and Their Applications
• Switching functions whose monotone complexity
• On the parallel evaluation of multivariate polynomials

This page was built for publication: Negation can be exponentially powerful