CPSC-637 Complexity Theory

Paper Presentations

• Albert Nash Boggess (April 18, 2008)
  Slides (ppt)
  "Extracting randomness: how and why, a survey,"
  N. Nisan
  Proc. IEEE Conference on Computational Complexity, pp. 44-58, 1996.
  paper (pdf)

• Jia-Hao Fan (April 18, 2008)
  Slides (ppt)
  "Algorithmics in exponential time,"
  U. Schoning,
  Lecture Notes in Computer Science 3404, (STACS 2005), pp. 36-43, 2005.
  paper (pdf)

• Ashraf Ibrahim (April 18, 2008)
  Slides (ppt)
  "Some connections between nonuniform and uniform complexity classes",
  R. Karp and R. Lipton
  Proc. 12th Annual ACM Symposium on Theory of Computing, pp. 302-309, 1980.
  paper (pdf)

• Yixin Cao (April 21, 2008)
  Slides (ppt)
  "Derandomization in cryptography,"
  B. Barak, S. Ong, and S. Vadhan,
  SIAM Journal on Computing 37, pp. 380-400, 2007.
  paper (pdf)

• Korben Rusek (April 21, 2008)
  Slides (ppt)
  "PP is as hard as the polynomial-time hierarchy,"
  S. Toda
  SIAM Journal on Computing 20, pp. 865-877, 1991.
  paper (pdf)

• Jia Hu (April 23, 2008)
  Slides (ppt)
  "Improved algorithms for path, matching, and packing problems,"
  J. Chen, S. Lu, S.-H. Sze, and F. Zhang,
  Proc. 18th ACM-SIAM Symposium on Discrete Algorithms, pp. 298-307, 2007.
  paper (pdf)

• Yang Liu (April 23, 2008)
  Slides (ppt)
  "Undirected ST-connectivity in log-space,"
  O. Reingold,
  Proc. 37th ACM Symp. on Theory of Computing, (STOC 2005), pp. 376-385, 2005.
  paper (pdf)

• Xiaolong Tang (April 23, 2008)
  Slides (ppt)
  "One bit of advice,"
  H. Buhrman, R. Chang, and L. Fortnow,
  Lecture Notes in Computer Science 2607, (STACS 2003), pp. 547-558, 2003.
  paper (pdf)