The Discrepancy of Unsatisfiable Matrices and a Lower Bound for the Komlós Conjecture Constant

DOI10.1137/22m149819xarXiv2111.02974OpenAlexW3208572847WikidataQ123308202 ScholiaQ123308202MaRDI QIDQ6158363

Dmitriy Kunisky

Publication date: 31 May 2023

Published in: SIAM Journal on Discrete Mathematics (Search for Journal in Brave)

Full work available at URL: https://arxiv.org/abs/2111.02974

zbMATH Keywords

discrepancy theorysatisfiabilityKomlós conjectureresolution proof system

Mathematics Subject Classification ID

Trees (05C05) Combinatorics in computer science (68R05) Irregularities of distribution, discrepancy (11K38)

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Disproof of the neighborhood conjecture with implications to SAT
• Computing unsatisfiable \(k\)-SAT instances with few occurrences per variable
• Packing lines in a hypercube
• Minimal non-two-colorable hypergraphs and minimal unsatisfiable formulas
• On a conjecture of Kömlos about signed sums of vectors inside the sphere
• An efficient algorithm for the minimal unsatisfiability problem for a subclass of CNF
• DNF tautologies with a limited number of occurrences of every variable
• Positional games
• A note on norms of signed sums of vectors
• The Local Lemma Is Asymptotically Tight for SAT
• A Note on Unsatisfiable k-CNF Formulas with Few Occurrences per Variable
• One More Occurrence of Variables Makes Satisfiability Jump from Trivial to NP-Complete
• An Algorithm for Komlós Conjecture Matching Banaszczyk's Bound
• The Gram-Schmidt walk: a cure for the Banaszczyk blues
• Discrepancy minimization via a self-balancing walk

This page was built for publication: The Discrepancy of Unsatisfiable Matrices and a Lower Bound for the Komlós Conjecture Constant