Phuong The Nguyen

I am now working in the industry.


Institutions I've been to:
School of Computer Science and Engineering at University of New South Wales
Department of Computer Science, University of Toronto
Mathematical Institute, Academy of Sciences of the Czech Repulic
Department of Computer Science, McGill University
Department of Informatique and Operation Research, University of Montreal

Click here for list of courses that I've taught

Book with Steve Cook: "Logical Foundations of Proof Complexity" (ASL Perspectives in Logic Series) from Cambridge University Press, 2010.
Some corrections
An almost complete draft (as of September 2, 2008)

PhD Thesis: Bounded Reverse Mathematics [ps file]   [pdf file].
University of Toronto, 2008. Supervisor: Steve Cook.


  • The NOF Multiparty Communication Complexity of Composed Functions
    Anil Ada, Arkadev Chattopadhyay, Omar Fawzi, Phuong Nguyen
    ECCC:TR11-155 pp 1-30
    ICALP 2012 Conference version.
    To appear in Journal on Computational Complexity.
  • Lifting Lower Bounds for Tree-like Proofs. [pdf file]
    Alexis Maciel, Phuong Nguyen, Toniann Pitassi
    To appear in Journal on Computational Complexity.
  • Feasible interpolation for lifted sequents. [pdf file]
    Logic and Computational Complexity workshop, 2011.
  • Simulation of Gi with prenex cuts. [pdf file]
    Emil Jeřábek and Phuong Nguyen.
    Mathematical Logic Quarterly. Volume 57, Issue 5/2011, pp 524--532.
  • Computationally Limited Randomness. [pdf file]
    Matei David, Phuong Nguyen, Periklis A. Papakonstantinou, and Anastasios Sidiropoulos.
    Innovations in Computer Science 2011.
  • The provably total NP search problems of weak second order bounded arithmetic. [pdf file]
    Leszek Aleksander Kolodziejczyk, Phuong Nguyen and Neil Thapen.
    Annals of Pure and Applied Logic, Volume 162, Issue 6, 2011, Pages 419-446
  • 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
  • The Complexity of Proving the Discrete Jordan Curve Theorem.
    Phuong Nguyen and Stephen Cook.
    ACM Transactions on Computational Logic, Volume 13, Number 1.
    22nd Annual IEEE Symposium on Logic in Computer Science (LICS 2007), pp 245--254.
    Full version (updated December 2010, pp 1-29)
  • 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 TC0 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: VTC0: A Second-Order Theory for TC0 [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 TC0 and other Small Complexity Classes" with Steve Cook.
  • Proving that VNC1 is Finitely Axiomatizable. [ps file] (Unpublished. See Book In Progress.)
Courses taught

Last modified by Phuong Nguyen, November 26, 2013