COMP251 Data structures and algorithms (McGill University, Fall 2009)

Publications

• Book with Stephen Cook: Logical Foundations of Proof Complexity (submitted)
• The provably total NP search problems of weak second order bounded arithmetic (submitted). [.pdf file]
  Leszek Aleksander Kolodziejczyk, Phuong Nguyen and Neil Thapen.
• PhD Thesis: Bounded Reverse Mathematics [.ps file]. [.pdf file].
  University of Toronto, 2008. Supervisor: Steve Cook.
• Proving Infinitude of Prime Numbers Using Binomial Coefficients.
  Computer Science Logic (CSL) 2008 (LNCS 5213) pp 184--198. Full version (22 pages): [.pdf file]   [.ps file].
• Relativizing Small Complexity Classes and their Theories.
  Klaus Aehlig, Stephen Cook and Phuong Nguyen.
  Computer Science in Logic 2007 (LNCS 4646) pp 374--388. Full version (18 pages): [.pdf file]   [.ps file].
• The Equivalence of Theories that Characterize ALogTime. [.pdf file]   [.ps file].
  Archive for Mathematical Logic: Volume 48, Issue6 (2009), Pages 523-549. DOI: 10.1007/s00153-009-0136-4. The original publication is available at www.springerlink.com.
• The Complexity of Proving the Discrete Jordan Curve Theorem.
  Phuong Nguyen and Stephen Cook.
  22nd Annual IEEE Symposium on Logic in Computer Science (LICS 2007), pp 245--254. Full version (24 pages): [.pdf file]   [.ps file].
• Separating DAG-Like and Tree-Like Proof Systems.
  22nd Annual IEEE Symposium on Logic in Computer Science (LICS 2007), pp 235--244. Full version (23 pages): [.pdf file]   [.ps file].
• Theories for TC⁰ and other Small Complexity Classes [.ps file]
  Phuong Nguyen and Stephen Cook.
  LMCS 2,1 (2006) (Logical Methods in Computer Science) Special issue: Selected papers of LICS 2004.
• Characterizing polynomial time computable functions using theories with weak set existence principles [.ps file].
  Aleksandar Ignjatovic and Phuong Nguyen.
  Computing: The Australasian Theory Symposium (CATS), Electronic Notes in Theoretical Computer Science, Volume 78, 2003.
• Learning in Logic with RichProlog [.pdf file].
  Eric Martin, Phuong Nguyen, Arun Sharma, Frank Stephan.
  The International Conference on Logic Programming (ICLP), 2002 pp 239 - 254.
• CardS4: Modal Theorem Proving on Java Smartcards [.ps file].
  Rajeev Goré and Phuong The Nguyen.
  Journal of Telecommunications and Information Technology (4): 68-80, 2002.
  (Preliminary version in International Conference on Research in Smart Cards (E--Smart 2001) pp 111--123.)
• Pertinence-centric Document Version Management Scheme.
  B. Benatallah, M. Mehdavi, P. Nguyen, L. Port, Q. Sheng, B. McIver
  15th International Conference on Advanced Information Systems Engineering (CAiSE'03) pp 46--62.
• AgFlow: Agent-based Cross Enterprise Workflow Management System.
  Zeng L., Benatallah B., Nguyen P., Ngu A.
  27th Int. Conference on Very Large Databases (VLDB 2001) pp 697--698.
• M.Sc. Thesis: VTC⁰: A Second-Order Theory for TC⁰ [.ps file] [Also available from ECCC archive].
  University of Toronto, 2004.
• Honour Thesis: Inductive Logic Programming with RichProlog [.ps file].
  University of New South Wales, 2001.
• Two-Sorted Theories for L, SL, NL and P. [.pdf file]  [.ps file]    ECCC Report [TR05-017]
  April 2004. Revised Jan 2005.
  For a more general discussion see "Theories for TC⁰ and other Small Complexity Classes" with Steve Cook.
• Proving that VNC¹ is Finitely Axiomatizable. [.ps file] (Unpublished. See Book In Progress.)

• CSC373 Algorithm Design and Analysis (University of Toronto): summer 2007, summer 2006.
• CSE 3101: Design and Analysis of Algorithms (York University) summer 2006