Phuong The Nguyen
I am now working in the industry.
Email:
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.
Papers
 The NOF Multiparty Communication Complexity of Composed Functions
Anil Ada, Arkadev Chattopadhyay, Omar Fawzi, Phuong Nguyen
ECCC:TR11155
pp 130
ICALP 2012
Conference version.
To appear in Journal on Computational Complexity.
 Lifting Lower Bounds for Treelike 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 G_{i} with prenex cuts. [pdf file]
Emil Jeřábek and Phuong Nguyen.
Mathematical Logic Quarterly. Volume 57, Issue 5/2011, pp 524532.
 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 419446

Proving Infinitude of Prime Numbers Using Binomial Coefficients.
Computer Science Logic (CSL) 2008 (LNCS 5213) pp 184198.
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 374388.
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 523549.
DOI: 10.1007/s0015300901364.
The original publication is available at www.springerlink.com.

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 245254.
Full version (updated December 2010, pp 129)

Separating DAGLike and TreeLike Proof Systems.
22nd Annual IEEE Symposium on Logic in Computer Science (LICS 2007), pp 235244.
Full version (23 pages):
[pdf file]
[ps file].

Theories for TC^{0} 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): 6880, 2002.
(Preliminary version in International Conference on Research in Smart Cards
(ESmart 2001) pp 111123.)

Pertinencecentric 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 4662.

AgFlow: Agentbased Cross Enterprise Workflow Management System.
Zeng L., Benatallah B., Nguyen P., Ngu A.
27th Int. Conference on Very Large Databases (VLDB 2001) pp 697698.
 M.Sc. Thesis:
VTC^{0}: A SecondOrder Theory for TC^{0}
[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.

TwoSorted Theories for L, SL, NL and P.
[pdf file]
[ps file]
ECCC Report
[TR05017]
April 2004. Revised Jan 2005.
For a more general discussion see "Theories for TC^{0} and other Small Complexity Classes"
with Steve Cook.

Proving that VNC^{1} is Finitely Axiomatizable.
[ps file]
(Unpublished. See Book In Progress.)
Courses taught
