This is the authors' abstract. We don't add key points for this paper.
We obtain computer assisted proofs of several spherical volume inequalities that appear in the analysis of semidefinite programming based approximation algorithms for Boolean constraint satisfaction problems. These inequalities imply, in particular, that the performance ratio achieved by the MAX 3-SAT approximation algorithm of Karloff and Zwick is indeed 7/8, as conjectured by them, and that the performance ratio of the MAX 3-CSP algorithm of the author is indeed ½. Other results are also implied. The computer assisted proofs are obtained using a system called REALSEARCH written by the author. This system uses interval arithmetic to produce rigorous proofs that certain collections of constraints in real variables have no real solution.
Answers are grounded in this paper and cite their sources.
No takes yet. Share an insight, caveat, or question.
Uri Zwick (2002) studied this question.
Synapse has enriched 8 closely related papers on similar clinical questions. Consider them for comparative context: