Showing cs.CCShow all
3 papers · 1 filter
cs.CC2020
Strongly refuting all semi-random Boolean CSPs
Jackson Abascal, Venkatesan Guruswami, Pravesh K. Kothari
We give an efficient algorithm to strongly refute \emph{semi-random} instances of all Boolean constraint satisfaction problems. The number of constraints required by our algorithm…
cs.CC2017
Critique of Barbosa's "P != NP Proof"
Jackson Abascal, Shir Maimon
We review André Luiz Barbosa's paper "P != NP Proof," in which the classes P and NP are generalized and claimed to be proven separate. We highlight inherent ambiguities in Barbosa'…
cs.CC2017
A Refutation of Guinea's "Understanding SAT is in P"
Jackson Abascal, Shir Maimon
In this work, we summarize and critique the paper "Understanding SAT is in P" by Alejandro Sánchez Guinea [arXiv:1504.00337]. The paper claims to present a polynomial-time solution…