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)

Full work available at URL https://doi.org/10.1137/S0097539701396959

zbMATH Keywords

approximation methodcircuit complexityclique functionlower boundmonotone circuitnegation-limited circuit

Mathematics Subject Classification ID

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

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

(17)

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

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)