Selected Publications (see DBLP for my other papers)

  1. S. A. Cook and Y. Filmus, D. T. M. Le: The Complexity of the Comparator Circuit Value Problem, submitted in 2012. [arXiv:1208.2721]
    [This paper solved several open problems raised in the CLS'11 paper below.]

  2. S. A. Cook, D. T. M. Le, and Y. Ye: A Formal Theory for the Complexity Class Associated with the Stable Marriage Problem, 2011. [arXiv:1106.4142]
    • Short version appeared in Proceedings of CSL'11: [DROPS].
    • Also presented in the LCC'11 (Logic and Computational Complexity) workshop. Presentation slides: [PDF].
    • Slides for Prague's Logic and Complexity Seminar: [PDF].

  3. D. T. M. Le and S. A. Cook: Formalizing Randomized Matching Algorithms. (invited for the special issue of LICS'11) . Journal of Logical Methods in Computer Science 8 (3:5), 2012. [arXiv:1103.5215]
    • Short version appeared in Proceedings of LICS'11. Presentation slides: [PDF].

  4. D. T. M. Le: On Three Alternative Characterizations of Combined Traces. (invited for the special issue of Petri Nets '10). Fundamentae Informatica 113(3-4): 265-293, 2011. [arXiv:1011.1030]

  5. R. Janicki, D. T. M. Le: Modelling Concurrency with Comtraces and Generalized Comtraces. Journal of Information and Computation 209, pages 1355–1389, 2011. [arXiv:0907.1722]


  • Bounded Arithmetic and Formalizing Probabilistic Proofs, Ph.D. Thesis, University of Toronto, 2014. [PDF]
  • Studies in Comtrace Monoids, M.Sc. Thesis, McMaster University, 2008. [PDF]

Notes and Expositions

  • Lecture notes for Avi Wigderson's talks on "Randomness, Pseudorandomness and Derandomization" from the Fields Distinguished Lecture Series, Sept 2010.
    1. Randomness - A computational complexity view. [PDF]
    2. Cryptography and Pseudorandomness. [PDF]
    3. Expander graphs - a ubiquitous pseudorandom structure. [PDF]

  • I also wrote a news article on Avi's talks for the Fields Institute's Winter 2011 newsletter.

I was just guessin',
At numbers and figures,
Pullin' the puzzles apart.

Questions of science,
Science and progress,
Do not speak as loud as my heart.

from "The Scientist" by Coldplay