A SAT Attack on the Erdős Discrepancy Conjecture

DOI10.1007/978-3-319-09284-3_17zbMath1343.68217arXiv1402.2184OpenAlexW2964092005MaRDI QIDQ3192068

Boris Konev, Alexej P. Lisitsa

Publication date: 26 September 2014

Published in: Lecture Notes in Computer Science (Search for Journal in Brave)

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

Mathematics Subject Classification ID

Irregularities of distribution, discrepancy (11K38) Arithmetic combinatorics; higher degree uniformity (11B30)

Related Items

Combining SAT solvers with computer algebra systems to verify combinatorial conjectures ⋮ Mechanical Proofs of Properties of the Tribonacci Word ⋮ Proof checking and logic programming ⋮ Expressing Symmetry Breaking in DRAT Proofs ⋮ MathCheck: A Math Assistant via a Combination of Computer Algebra Systems and SAT Solvers ⋮ Optimal bounds for the no-show paradox via SAT solving ⋮ Formalizing Size-Optimal Sorting Networks: Extracting a Certified Proof Checker ⋮ Computer-aided proof of Erdős discrepancy properties ⋮ How to get more out of your oracles ⋮ Tao’s resolution of the Erdős discrepancy problem ⋮ Formally proving size optimality of sorting networks ⋮ Quantifying local randomness in human DNA and RNA sequences using Erdös motifs ⋮ Truth Assignments as Conditional Autarkies ⋮ Discrepancy one among homogeneous arithmetic progressions ⋮ Binary pattern tile set synthesis is NP-hard ⋮ The packing chromatic number of the infinite square lattice is between 13 and 15 ⋮ Optimal symmetry breaking for graph problems ⋮ On propositional coding techniques for the distinguishability of objects in finite sets ⋮ Functional Encryption for Inner Product with Full Function Privacy ⋮ The SAT+CAS method for combinatorial search with applications to best matrices ⋮ Computing Maximum Unavoidable Subgraphs Using SAT Solvers ⋮ Applying computer algebra systems with SAT solvers to the Williamson conjecture ⋮ MathCheck2: A SAT+CAS Verifier for Combinatorial Conjectures ⋮ Incompleteness, Undecidability and Automated Proofs ⋮ On orthogonal symmetric chain decompositions ⋮ On the hereditary discrepancy of homogeneous arithmetic progressions