Disproving the Single Level Conjecture

DOI10.1137/S0097539705447001MaRDI QIDQ5470747zbMATH OpenOpenAlexWikidataFDO

Authors Stasys 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

quadratic functionsclique covering numbermonotone circuitsBoolean 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)

Recommendations

• Disproving Hooley's conjecture
• Disproof of a conjecture of Jacobsthal
• Proof of the middle levels conjecture
• scientific article; zbMATH DE number 7204439
• Singular failures of GCH and level by level equivalence
• Disproof of the Mertens conjecture.
• Level compatibility in Sharifi’s conjecture
• A Disproof of the Fon-der-Flaass Conjecture
• Disproof of the list Hadwiger conjecture
• Disproof of a conjecture of Neumann-Lara

Cited in

(8)

• Failures of SCH and level by level equivalence
• The monotone circuit complexity of quadratic Boolean functions
• Decomposition of graphs and monotone formula size of homogeneous functions
• Algorithms and Computation
• Cancellation-free circuits in unbounded and bounded depth
• Finding bipartite subgraphs efficiently
• scientific article; zbMATH DE number 4074972 (Why is no real title available?)
• Monotone formula size of homogeneous functions

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

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