Publications & Presentations

Pollett, Christopher J

Publications & Presentations

24. Alternating Hierarchies for Time-Space Tradeoffs. (with Eric Miles). arXiv:0801.1307v1. 2008.

23. The Weak Pigeonhole Principle for Function Classes in S12. (with Norman Danner). Mathematical Logic Quarterly. Volume 52, Issue 6 (December 2006). pp. 575--584.

22. Circuit Principles and Weak Pigeonhole Variants. (with Norman Danner). This paper improves the result of the conference paper below. Theoretical Computer Science. Volume 383. 2007. pp. 115-131.

21. Circuit Principles and Weak Pigeonhole Variants. (with Norman Danner). Conferences in Research and Practice in Information Technology -- Computing: The Australasian Theory Symposium (CATS 2005). Eds. M. Atkinson and F. Dehne. Volume 41. Australian Computer Science Communications. Volume 27. Number 4. pp. 31--40.

20. On the Computational Power of Probabilistic and Quantum Branching Programs. (with Farid Ablayev, Aida Gainutdinova, Marek Karpinski, and Cristopher Moore). Information and Computation. Dec. 2005. Vol. 203. Iss 2. pp. 145--162.

19. Languages to diagonalize against advice classes. Computational Complexity. Vol. 14 Iss 4. pp. 342--361. 2005. An earlier version with many typos appeared as ECCC TR04-014.

18. Sk, exp does not prove NP=coNP uniformly. Zapiski Nauchnykh Seminarov. Dom 1. Vol. 304. 2003. pp. 99--120. (Without the uniformity condition the result only implies a restricted form of IOpen +exp cannot prove NP = coNP.) Translated from English to English but with some typos eliminated in Journal of Mathematical Sciences. Vol. 130. No. 2. Oct. 2005. pp.4607--4619.

17. A Theory for Logspace and NLIN versus co-NLIN. Journal of Symbolic Logic. Vol. 68 No. 4. 2003. pp. 1082-1090.

16. Nepomnjascij's Theorem and Independence Proofs in Bounded Arithmetic. ECCC TR02-051.

15. Quantum and Stochastic Branching Programs of Bounded Width. (with Farid Ablayev and Cris Moore) 29th International Colloquium on Automata, Languages, and Programming (ICALP). 2002. p.343--354. Earlier versions can be found at ECCC TR02-013 and LANL quant-ph/020113. The upper bound result in the ICALP paper needed a syntactic restriction. This has been revised in the ECCC and LANL version and in the version on-line here.

14. On the Bounded Version of Hilbert's Tenth Problem.Archive for Mathematical Logic. Vol. 42. No. 5. 2003. pp. 469--488.

13. Counting, Fanout, and the Complexity of Quantum ACC. (with Fred Green, Steve Homer, and Cris Moore) Quantum Information and Computation. Vol. 2. No. 1. 2002. pp.35--65.

12. Minimization and NP multifunctions. (with N. Danner) Theoretical Computer Science. Vol. 318. Iss. 1-2. 2004. pp. 105--119.

11. Ordinal Notations and Well-Orderings in Bounded Arithmetic. (with A. Beckmann and S.R. Buss) Annals of Pure and Applied Logic.120 (Issue 1-3) Apr. 2003. pp. 197-223.

10. Strengths and Weaknesses of LH Arithmetic. (with R. Pruim) Mathematical Logic Quarterly.48 (No.2) Feb 2002. pp.221--243.

9. On the Complexity of Quantum ACC. (with Fred Green and Steve Homer) Proceedings of the Fifteenth Annual IEEE Conference on Computational Complexity. July 4-7, 2000. pp250--262. Is also Boston University Technical Report BUCS-TR-2000-003 and LANL quant-ph/0002057.

8. Multifunction Algebras and the Provability of PH?. Annals of Pure and Applied Logic. Vol. 104 July 2000. pp. 279--303.

7. Translating I?0 + exp proofs into weaker systems.Mathematical Logic Quarterly.46:249-256 (No.2) May 2000.

6. On the ?b1-bit comprehension rule. (with Jan Johannsen) Proceedings of Logic Colloquium 1998. edited by S.R. Buss, P. Hajek, P. Pudlak pp.262--270, A.K.Peters and ASL, 2000.

5. Structure and Definability in General Bounded Arithmetic Theories.Annals of Pure and Applied Logic. Vol 100. October 1999. pp.189--245.

4. On Proofs about Threshold Circuits and Counting Hierarchies (with Jan Johannsen). Proceedings of Thirteenth IEEE Symposium on Logic in Computer Science. pp.444--452. IEEE press. 1998.

3. Nonmonotonic reasoning with quantified boolean constraints. (with J. Remmel) Logic Programming and Nonmonotonic Reasoning. 1997. Jurgen Dix, Ulrich Furbach and Anil Nerode (Eds). pp.18--39. LNAI, 1265. Springer. 1997.

2. A propositional proof system for Ri2.Proof Complexity and Feasible Arithmetics. Paul W. Beame and Samuel R. Buss eds. pp.253--278. 1997. DIMACS: Series in Discrete Mathematics and Theoretical Computer Science. Vol 39. AMS. 1997.

1. Arithmetic Theories with Prenex Normal Form Induction. Ph.D. Thesis. UC San Diego. 1997.