Improved Lower Bounds for Tree-Like Resolution over Linear Inequalities

DOI10.1007/978-3-540-72788-0_10zbMath1214.03045OpenAlexW1504627710MaRDI QIDQ3612456

Arist Kojevnikov

Publication date: 10 March 2009

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

Full work available at URL: https://doi.org/10.1007/978-3-540-72788-0_10

zbMATH Keywords

integer programmingcutting planespropositional proof complexity

Mathematics Subject Classification ID

Integer programming (90C10) Polyhedral combinatorics, branch-and-bound, branch-and-cut (90C57) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Complexity of proofs (03F20)

Related Items (5)

Randomized feasible interpolation and monotone circuits with a local oracle ⋮ Unnamed Item ⋮ Depth lower bounds in Stabbing Planes for combinatorial principles ⋮ Resolution over linear equations and multilinear proofs ⋮ Resolution over linear equations modulo two

This page was built for publication: Improved Lower Bounds for Tree-Like Resolution over Linear Inequalities