Disproving the Single Level Conjecture

DOI10.1137/S0097539705447001zbMath1113.94013OpenAlexW2090188355WikidataQ123279273 ScholiaQ123279273MaRDI QIDQ5470747

Stasys P. Jukna

Publication date: 1 June 2006

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

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

zbMATH Keywords

monotone circuitsquadratic functionsclique covering numberBoolean sumsgraph complexity

Mathematics Subject Classification ID

Graph theory (including graph drawing) in computer science (68R10) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17)

Related Items (2)

Finding bipartite subgraphs efficiently ⋮ Cancellation-free circuits in unbounded and bounded depth

This page was built for publication: Disproving the Single Level Conjecture