@Book{AlonSp02,
  author =       "N. Alon and J. Spencer",
  title =        "The Probabilistic Method",
  publisher =    "John Wiley and Sons",
  year =         "2002",
  note =         "",
}

@Article{FriedgutBo99,
  author = "E. Friedgut and J. Bourgain",
  title =  "Sharp Thresholds of Graph Properties, and the k-Sat Problem",
  journal = "Journal of the American Mathematical Society",
  volume =       "12",
  number =       "4",
  pages =        "1017--1054",
  year =         "1999",
  eprint = "JAMS:jams/1999-12-04/S0894-0347-99-00305-7"
}

@InProceedings{GoerdtKr01,
  author =       "A. Goerdt and M. Krivelevich",
  title = "Efficient Recognition of Random Unsatisfiable $k$-{SAT} Instances by Spectral Methods",
  booktitle =    "Proc. Ann. Symp. on Theoretical Aspects of Computer Science (STACS '01)",
  pages = "294--304",
  publisher = "Springer",
  series = "LNCS",
  volume = "2010",
  year = "2001",
  eprint="stacs:27cr0lrbpr7px7y3"
}

@article{FriedmanGoKr05,
    author = "J. Friedman and A. Goerdt and M. Krivelevich",
    title = "Recognizing More Unsatisfiable Random 3-SAT Instances Efficiently",
    journal = "SIAM J. on Computing",
    volume = "35",
    number = "2",
    pages = "408--430",
    year = "2005",
    eprint="sicomp:10.1137/S009753970444096X"
}

@InProceedings{Feige02,
    author = "U. Feige",
    title = "Relations between Average Case Complexity and Approximation Complexity",
    pages = "534--543",
    booktitle = "Proc. 34th STOC",
    publisher = "ACM Press",
    year = "2002",
    eprint="stoc:509907.509985"
}

@article{FeigeOf05,
  author = "U. Feige and E. Ofek",
  title =  "Spectral Techniques Applied to Sparse Random Graphs",
  journal= "Random Structures and Algorithms",
  volume = "27",
  number = "2",
  pages  = "251--275",
  year   = "2005",
  eprint="rsa:10.1002/rsa.20089"
}

@inproceedings{Zwick99,
    author = "U. Zwick",
    title = "Outward rotations: a tool for rounding solutions of semidefinite programming relaxations, with applications to {MAX {CUT}} and other problems",
    pages = "679--687",
    booktitle = "Proc. 31st STOC",
    publisher = "ACM Press",
    year = "1999",
    eprint="stoc:301250.301431"
}

@article{CojaGoLaSc03,
  AUTHOR =       "A. Coja-Oghlan and A. Goerdt and A. Lanka and F. Schadlich",
  TITLE =        "Techniques from combinatorial approximation algorithms yield efficient algorithms for random $2k$-SAT",
  JOURNAL =      "Theoretical Computer Science",
  VOLUME =       "329",
  PAGES =        "1--45",
  YEAR =         "2004",
  eprint="tcs:10.1016/j.tcs.2004.07.017"
}

@Misc{GoerdtLa03,
  title =  "Recognizing more random 3-SAT instances efficiently",
  author = "A. Goerdt and A. Lanka",
  howpublished = "LICS'03 Workshop on Typical Case Complexity and Phase Transitions",
  year = "2003",
  url = "http://www.scs.carleton.ca/~kranakis/LICS-03.html",
}

@article{ChvatalSz88,
  author = "V. Chv\'{a}tal and E. Szemer\'{e}di",
  title = "Many hard examples for resolution",
  journal = "J. ACM",
  volume = "35",
  number = "4",
  pages = "759--768",
  year = "1988",
  eprint="jacm:10.1145/48014.48016"
}

@InProceedings{CojaGoLa04,
  author =  "A. Coja-Oghlan and A. Goerdt and A. Lanka",
  title =   "Strong Refutation Heuristics for Random $k$-{SAT}",
  booktitle =   "Proc. 8th Internat. Workshop on Randomization and Computation (RANDOM '04)",
  publisher =   "Springer",
  series = "LNCS",
  volume = "3122",
  pages = "310--321",
  year =    "2004",
  eprint="springer:x1tlgm3cexcj"
}

@article{CojaGoLa07,
  author =  "A. Coja-Oghlan and A. Goerdt and A. Lanka",
  title =   "Strong Refutation Heuristics for Random $k$-{SAT}",
  journal = "Combinatorics, Probability and Computing",
  volume = "16",
  number = "1",
  pages = "5--28",
  year =    "2007",
  note = "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",
  eprint="springer:x1tlgm3cexcj"
}

@article{JansonStVa00,
    author = "S. Janson and Y. Stamatiou and M. Vamvakari",
    title = "Bounding the unsatisfiability threshold of random 3-SAT",
    journal = "Random Structures and Algorithms",
    volume = "17",
    number = "2",
    pages = "103--116",
    year = "2000",
    eprint="rsa:10.1002/1098-2418(200009)17:2<103::AID-RSA2>3.0.CO;2-P"
}

@article{Ben-SassonWi01,
 author = {E. Ben-Sasson and A. Wigderson},
 title = {Short proofs are narrow--- resolution made simple},
 journal = {J. ACM},
 volume = {48},
 number = {2},
 year = {2001},
 issn = {0004-5411},
 pages = {149--169},
 eprint="jacm:10.1145/375827.375835"
}

@Misc{HajiaghayiSo03,
  title =   "The Satisfiability Threshold of Random 3-{SAT} Is at Least 3.52",
  author =  "M. Hajiaghayi and B. Sorkin",
  year =    "2003",
  oai =     "oai:arXiv.org:math/0310193",
  subject = "Combinatorics; Probability; Discrete Mathematics",
  eprint = "arxiv:math/0310193",
  URL =     "http://arxiv.org/abs/math/0310193",
}

@article{KaporisKiLa03,
  author    = "A. Kaporis and L. Kirousis and E. Lalas",
  title     = "The probabilistic analysis of a greedy satisfiability algorithm",
  journal   = "Random Structures and Algorithms",
  volume    = "28",
  number    = "4",
  year      = "2006",
  pages     = "444--480",
  eprint="rsa:10.1002/rsa.20104"
}

@InProceedings{Khot04a,
  author =  "S. Khot",
  title =   "Ruling Out {PTAS} for Graph Min-Bisection, Densest Subgraph and Bipartite Clique",
  booktitle =   "Proc. 45th FOCS",
  pages = "136--145",
  publisher = "IEEE Computer Society",
  year =    "2004",
  eprint="focs:10.1109/FOCS.2004.59"
}