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.