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

DOI10.1137/S0097539701396959MaRDI QIDQ5700577zbMATH OpenWikidataFDO

Authors Kazuyuki Amano, A. Maruoka

Publication date 28 October 2005

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

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)

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

Cited in

(16)

• The Potential of the Approximation Method
• Reductions for monotone Boolean circuits
• Limiting negations in non-deterministic circuits
• Testing \(k\)-monotonicity
• On the mystery of negations in circuits: structure vs power
• Negation-limited formulas
• Linear-size log-depth negation-limited inverter for \(k\)-tonic binary sequences
• scientific article; zbMATH DE number 1222575 (Why is no real title available?)
• On Negations in Boolean Networks
• On negation complexity of injections, surjections and collision-resistance in cryptography
• Negation-limited complexity of parity and inverters
• Ehrenfeucht-Fraïssé Games on Random Structures
• Lower bounds for Boolean circuits of bounded negation width
• The Average-Case Complexity of Counting Cliques in Erdös--Rényi Hypergraphs
• Depth lower bounds against circuits with sparse orientation
• Depth lower bounds against circuits with sparse orientation

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)