Random Cnf's are Hard for the Polynomial Calculus. Ben-Sasson, E. & Impagliazzo, R. Computational Complexity, 19(4):501-519, 2010.
bibtex   
@article{BI10,
  author    = {Eli Ben-Sasson and Russell Impagliazzo},
  title     = {Random Cnf's are Hard for the Polynomial Calculus},
  journal   = {Computational Complexity},
  volume    = {19},
  number    = {4},
  year      = {2010},
  pages     = {501-519},
}

Downloads: 0