Tight Upper Bound on Splitting by Linear Combinations for Pigeonhole Principle

DOI10.1007/978-3-319-40970-2_6zbMath1475.68138OpenAlexW2484670842MaRDI QIDQ2818003

Vsevolod Oparin

Publication date: 5 September 2016

Published in: Theory and Applications of Satisfiability Testing – SAT 2016 (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/978-3-319-40970-2_6

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Complexity of proofs (03F20) Computational aspects of satisfiability (68R07)

Related Items (1)

Resolution over linear equations modulo two

Cites Work

• A satisfiability algorithm and average-case hardness for formulas over the full binary basis
• Exponential lower bounds for the running time of DPLL algorithms on satisfiable formulas
• Lower Bounds for Splittings by Linear Combinations
• An Elementary Proof of a 3n − o(n) Lower Bound on the Circuit Complexity of Affine Dispersers
• Hard examples for resolution
• A Computing Procedure for Quantification Theory
• A machine program for theorem-proving

This page was built for publication: Tight Upper Bound on Splitting by Linear Combinations for Pigeonhole Principle