Lower bounds on monotone complexity of the logical permanent
From MaRDI portal
Publication:1071001
DOI10.1007/BF01157687zbMath0584.94026OpenAlexW2045260280WikidataQ56701133 ScholiaQ56701133MaRDI QIDQ1071001
Publication date: 1985
Published in: Mathematical Notes (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1007/bf01157687
Related Items
More on the complexity of slice functions ⋮ The complexity of central slice functions ⋮ Some complete and intermediate polynomials in algebraic complexity theory ⋮ \(\text{PI}_ k\) mass production and an optimal circuit for the Nečiporuk slice ⋮ Entropy of contact circuits and lower bounds on their complexity ⋮ A method for obtaining efficient lower bounds for monotone complexity ⋮ On monotone simulations on nonmonotone networks ⋮ Lower bounds for Boolean circuits of bounded negation width ⋮ Average circuit depth and average communication complexity ⋮ On digraph coloring problems and treewidth duality ⋮ Lower bounds for monotone \(q\)-multilinear Boolean circuits ⋮ On derandomization and average-case complexity of monotone functions ⋮ Circuit complexity of linear functions: gate elimination and feeble security ⋮ Acyclicity programming for sigma-protocols ⋮ Lower bounds for depth-restricted branching programs ⋮ On algorithm complexity ⋮ Separating the eraser Turing machine classes \(L_ e\), \(NL_ e\), \(co- NL_ e\) and \(P_ e\) ⋮ Lower bounds for tropical circuits and dynamic programs ⋮ Expressing combinatorial optimization problems by linear programs ⋮ A note on the power of majority gates and modular gates ⋮ A simple lower bound for monotone clique using a communication game ⋮ Matching theory -- a sampler: From Dénes König to the present ⋮ One-way permutations, computational asymmetry and distortion. ⋮ Separating complexity classes related to \(\Omega\)-decision trees ⋮ Natural proofs ⋮ Approximation Limitations of Pure Dynamic Programming ⋮ The gap between monotone and non-monotone circuit complexity is exponential ⋮ Coxeter groups and nonuniform complexity ⋮ Adventures in monotone complexity and TFNP ⋮ A super-quadratic lower bound for depth four arithmetic circuits ⋮ Lower Bounds for DeMorgan Circuits of Bounded Negation Width ⋮ A lower bound for monotone arithmetic circuits computing \(0-1\) permanent ⋮ On Negations in Boolean Networks ⋮ OMITTING TYPES, BOUNDED WIDTH AND THE ABILITY TO COUNT ⋮ On the minimum number of negations leading to super-polynomial savings ⋮ Non-cancellative Boolean circuits: A generalization of monotone boolean circuits ⋮ Positive versions of polynomial time ⋮ Notes on Hazard-Free Circuits ⋮ Proof complexity of monotone branching programs ⋮ On the computational complexity of qualitative coalitional games
Cites Work
- Switching functions whose monotone complexity is nearly quadratic
- A new lower bound on the monotone network complexity of Boolean sums
- Boolean functions whose monotone complexity is of size \(n^ 2\) / log n
- The Power of Negative Thinking in Multiplying Boolean Matrices
- An $n^{5/2} $ Algorithm for Maximum Matchings in Bipartite Graphs
