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

Boolean sumsclique covering numbergraph complexitymonotone circuitsquadratic functions

Mathematics Subject Classification ID

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

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

(9)

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

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)