A Superpolynomial Lower Bound for a Circuit Computing the Clique Function with at most (1/6)log log n Negation Gates

DOI10.1137/S0097539701396959zbMATH Open1081.94042WikidataQ56210387 ScholiaQ56210387MaRDI QIDQ5700577FDOQ5700577

A. Maruoka, Kazuyuki Amano

Publication date: 28 October 2005

Published in: SIAM Journal on Computing (Search for Journal in Brave)

Recommendations

• scientific article; zbMATH DE number 1222575
• Algorithms and Computation
• On the complexity of negation-limited Boolean networks (preliminary version)
• The Potential of the Approximation Method
• The monotone circuit complexity of Boolean functions

zbMATH Keywords

lower boundapproximation methodcircuit complexitymonotone circuitnegation-limited circuitclique function

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17)

Cited In (14)

• The Potential of the Approximation Method
• Reductions for monotone Boolean circuits
• Limiting negations in non-deterministic circuits
• On the mystery of negations in circuits: structure vs power
• Title not available (Why is that?)
• Negation-limited formulas
• Linear-size log-depth negation-limited inverter for \(k\)-tonic binary sequences
• On Negations in Boolean Networks
• Negation-limited complexity of parity and inverters
• Ehrenfeucht-Fraïssé Games on Random Structures
• Lower bounds for Boolean circuits of bounded negation width
• On Negation Complexity of Injections, Surjections and Collision-Resistance in Cryptography
• The Average-Case Complexity of Counting Cliques in Erdös--Rényi Hypergraphs
• Title not available (Why is that?)

This page was built for publication: A Superpolynomial Lower Bound for a Circuit Computing the Clique Function with at most (1/6)log log n Negation Gates

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5700577)