Easily refutable subformulas of large random 3CNF formulas

by Uriel Feige and Eran Ofek

Theory of Computing, Volume 3(2), pp. 25-43, 2007

Bibliography with links to cited articles

[1] N. Alon and J. Spencer: The Probabilistic Method. John Wiley and Sons, 2002.
[2] E. Ben-Sasson and A. Wigderson: Short proofs are narrow- resolution made simple. J. ACM, 48(2):149-169, 2001. [JACM:10.1145/375827.375835].
[3] V. Chvátal and E. Szemerédi: Many hard examples for resolution. J. ACM, 35(4):759-768, 1988. [JACM:10.1145/48014.48016].
[4] A. Coja-Oghlan, A. Goerdt, and A. Lanka: Strong refutation heuristics for random k-SAT. Combinatorics, Probability and Computing, 16(1):5-28, 2007. Conference version appeared in Proc. 8th Internat. Workshop on Randomization and Computation (RANDOM '04), volume 3122 of LNCS, pp. 310-321. Springer, 2004. [doi:10.1017/S096354830600784X, Springer:x1tlgm3cexcj].
[5] A. Coja-Oghlan, A. Goerdt, A. Lanka, and F. Schadlich: Techniques from combinatorial approximation algorithms yield efficient algorithms for random 2k-sat. Theoretical Computer Science, 329:1-45, 2004. [TCS:10.1016/j.tcs.2004.07.017].
[6] U. Feige: Relations between average case complexity and approximation complexity. In Proc. 34th STOC, pp. 534-543. ACM Press, 2002. [STOC:509907.509985].
[7] U. Feige and E. Ofek: Spectral techniques applied to sparse random graphs. Random Structures and Algorithms, 27(2):251-275, 2005. [RSA:10.1002/rsa.20089].
[8] E. Friedgut and J. Bourgain: Sharp thresholds of graph properties, and the k-sat problem. Journal of the American Mathematical Society, 12(4):1017-1054, 1999. [JAMS:jams/1999-12-04/S0894-0347-99-00305-7].
[9] J. Friedman, A. Goerdt, and M. Krivelevich: Recognizing more unsatisfiable random 3-sat instances efficiently. SIAM J. on Computing, 35(2):408-430, 2005. [SICOMP:10.1137/S009753970444096X].
[10] A. Goerdt and M. Krivelevich: Efficient recognition of random unsatisfiable k-SAT instances by spectral methods. In Proc. Ann. Symp. on Theoretical Aspects of Computer Science (STACS '01), volume 2010 of LNCS, pp. 294-304. Springer, 2001. [STACS:27cr0lrbpr7px7y3].
[11] A. Goerdt and A. Lanka: Recognizing more random 3-sat instances efficiently. LICS'03 Workshop on Typical Case Complexity and Phase Transitions, 2003.
[ .html ]
[12] M. Hajiaghayi and B. Sorkin: The satisfiability threshold of random 3-SAT is at least 3.52, 2003. [arXiv:math/0310193].
[ http ]
[13] S. Janson, Y. Stamatiou, and M. Vamvakari: Bounding the unsatisfiability threshold of random 3-sat. Random Structures and Algorithms, 17(2):103-116, 2000. [RSA:10.1002/1098-2418(200009)17:2<103::AID-RSA2>3.0.CO;2-P].
[14] A. Kaporis, L. Kirousis, and E. Lalas: The probabilistic analysis of a greedy satisfiability algorithm. Random Structures and Algorithms, 28(4):444-480, 2006. [RSA:10.1002/rsa.20104].
[15] S. Khot: Ruling out PTAS for graph min-bisection, densest subgraph and bipartite clique. In Proc. 45th FOCS, pp. 136-145. IEEE Computer Society, 2004. [FOCS:10.1109/FOCS.2004.59].
[16] U. Zwick: Outward rotations: a tool for rounding solutions of semidefinite programming relaxations, with applications to MAX CUT and other problems. In Proc. 31st STOC, pp. 679-687. ACM Press, 1999. [STOC:301250.301431].

This file has been generated by bibtex2html 1.81.