Phuong The Nguyen
I am now working in the industry.
Links: UNSW, Toronto,
University of Montreal.
Webpage of courses taught
Book with Steve Cook:
"Logical Foundations of Proof Complexity"
(ASL Perspectives in Logic Series)
from Cambridge University Press, 2010.
An almost complete
(as of September 2, 2008)
PhD Thesis: Bounded Reverse Mathematics
University of Toronto, 2008. Supervisor: Steve Cook.
- The NOF Multiparty Communication Complexity of Composed Functions
Anil Ada, Arkadev Chattopadhyay, Omar Fawzi, Phuong Nguyen
Conference version to appear in ICALP 2012.
- Lifting Lower Bounds for Tree-like Proofs. [pdf file]
Alexis Maciel, Phuong Nguyen, Toniann Pitassi
Submitted February 2011.
- 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.
- Proving soundness for the quantified propositional calculus Gi*.
pp 1-43, revised November 2011.
- 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]
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]
The Equivalence of Theories that Characterize ALogTime.
Archive for Mathematical Logic: Volume 48, Issue6 (2009), Pages 523-549.
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 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):
Theories for TC0 and other Small Complexity Classes
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
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
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
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
[Also available from ECCC archive].
University of Toronto, 2004.
- Honour Thesis:
Inductive Logic Programming with RichProlog
University of New South Wales, 2001.
Two-Sorted Theories for L, SL, NL and P.
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.
(Unpublished. See Book In Progress.)