Disproving the Single Level Conjecture

DOI10.1137/S0097539705447001zbMATH Open1113.94013OpenAlexW2090188355WikidataQ123279273 ScholiaQ123279273MaRDI QIDQ5470747FDOQ5470747

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

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

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)

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
• Title not available (Why is that?)
• 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)