# 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 S ^{1}_{2}**. (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.
**S _{k, 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 ? ^{b}_{1}-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 R ^{i}_{2}.**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.