|
|
|
 |
|
|
|
Cryptography and Complexity Reading Seminar
|
|
Organizers: Alex Myasnikov and Sasha Ushakov
Mondays, Tuesdays, Thursdays, 11:00am
Subscribe
to receive automatic announcements about the seminar
|
Presentations |
Previous talks:
|
Suggested reading |
Average Case Complexity:
k-SAT
- D. Achlioptas, "Lower bounds for random 3-SAT via differential equations"
- D.Achlioptas, Y. Peres, "The threshol for random k-sat is $2^k \log 2 -O(k)$"
- S. Cook, D. Mitchell, "Finding Hard Instances of the Satisfiability Problem: {A} Survey"
- O. Dubois, Y. Boufkhad. A general upper bound for the satisfiability threshold of random r-SAT formulae.
- O. Dubois, Y. Boufkhadz and J. Mandlery, "Typical random 3-SAT formulae and the satisfiability threshold"
- O. Dubois, V. Puyhaubert, "Phase Transitions and Satisfiability Threshold"
- E. Friedgut, "Sharp Thresholds of Graph properties and the k-SAT Problem"
- M. Hajiaghayi, G. Sorkin, "The satisfiability threshold of random 3-SAT is at least 3.52"
Subset Sum Problem:
|
|
|
|
|
|
Stevens Institute of Technology •
Hoboken, NJ • (201) 216-5000
Sitemap |
|
|
|