Cryptography and Complexity Reading Seminar

Organizers: Alex Myasnikov and Sasha Ushakov

Mondays, Tuesdays, Thursdays, 11:00am
Subscribe to receive automatic announcements about the seminar

Previous talks:

• June 14-26. A. Ushakov. "Average case completeness" by Yuri Gurevich.
  Download paper.
• May 15-16. A. Myasnikov. "Efficient cryptographic schemed as secure as Subset Sum". by R. Impagliazzo, M. Naor.
  Download paper.
• May 11th. W. Backes."Introduction to lattice basis reduction."
  Suggested reading: Sections 1-4 in C.P.Schnorr, M. Euchner."Lattice Basis Reduction: Improved Practical Algorithms and Solving Subset Sum Problems"
• May 9th. A. Ushakov."Lattice reduction in cryptology." by P. Nguyen, J. Stern.
  Download paper.
• May 8th. A. Ushakov. "Improved low-density subset sum algorithms." by J.Lagarias et. al.
  Download paper.
• May 1st. Alexei Miasnikov. "A personal view of average-case complexity" by Russel Impagliazzo
  Download the paper.

Average Case Complexity:

• Andreas Blass and Yuri Gurevich. Matrix Transformation is Complete for the Average Case.
• Yuri Gurevich. Average case completeness
• Andreas Blass and Yuri Gurevich. Randomizing reductions of search problems.
• Andreas Blass and Yuri Gurevich. On the reduction theory for average case complexity.
• Russel Impagliazzo. A personal view of average-case complexity.

• 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"

• J.Lagarias, A. Odlyzko. Improved low-density subset sum algorithms.
• J.Lagarias, A. Odlyzko. Solving Low-Density Subset Sum Problems.
• R. Impagliazzo, M. Naor. Efficient cryptographic schemed as secure as Subset Sum
• R.Beier, B.Vocking. Random Knapsack in polynomial time
• M. Ajtai. Generating hard instances of Lattice problems
• P. Nguyen, J. Stern. Lattice reduction in cryptology.