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

Lua error in Module:PublicationMSCList at line 37: attempt to index local 'msc_result' (a nil value).

Related Items (12)

Limiting negations in non-deterministic circuits ⋮ On Negation Complexity of Injections, Surjections and Collision-Resistance in Cryptography ⋮ Lower bounds for Boolean circuits of bounded negation width ⋮ The Average-Case Complexity of Counting Cliques in Erdös--Rényi Hypergraphs ⋮ Reductions for monotone Boolean circuits ⋮ 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 ⋮ Negation-limited complexity of parity and inverters ⋮ Ehrenfeucht-Fraïssé Games on Random Structures ⋮ On Negations in Boolean Networks ⋮ Unnamed Item

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