Chris Pollett > Publications, Reviews, Master's Student Papers and Talks

For copyright reasons versions below may be close to but not the
final journal version.

This document was last modified Tuesday, 06-Dec-2016 22:05:32 PST.

[26-PDF]
**On the Finite Axiomatizability of
∀Σ ^{b}_{1}(
prenex R^{1}_{2}).** Preprint.

[25-PDF] [25-PS]
**Conservative Fragments of S ^{1}_{2} and
R^{1}_{2}.** Archive For Mathematical Logic. Vol. 50. Iss. 3. 2011. pp. 367 -- 393.

[24-PDF]
[24-PS]
**Alternating Hierarchies for Time-Space Tradeoffs.** (with Eric
Miles). arXiv:0801.1307v1. 2008.

[23-PDF]
[23-PS]
**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-PDF]
[22-PS]
**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-PDF]
[21-PS]
**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-PDF]
[20-PS]
**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-PDF]
[19-PS]
**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-PDF]
[18-PS]
**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-PDF]
[17-PS]
**A Theory for Logspace and NLIN versus co-NLIN**.
Journal of Symbolic Logic. Vol. 68 No. 4. 2003. pp. 1082-1090.

[16-PDF]
[16-PS]
**Nepomnjascij's Theorem and Independence Proofs in Bounded
Arithmetic.**
ECCC TR02-051.

[15-PDF]
[15-PS]
**
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-PDF]
[14-PS]
**On the Bounded Version of Hilbert's Tenth
Problem.**
Archive for Mathematical Logic. Vol. 42. No. 5. 2003. pp. 469--488.

[13-PDF]
[13-PS]
**
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-PDF]
[12-PS]
**
Minimization and NP multifunctions.** (with N.
Danner) Theoretical Computer
Science. Vol. 318. Iss. 1-2. 2004. pp.
105--119.

[11-PDF]
[11-PS]
**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-PDF]
[10-PS]
**Strengths and Weaknesses of LH Arithmetic.** (with
R. Pruim)
Mathematical Logic Quarterly. **48**
(No.2) Feb 2002.
pp.221--243.

[9-PDF]
[9-PS]
**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-PDF]
[8-PS]
**Multifunction
Algebras and the Provability of PH↓.**
Annals of
Pure and Applied Logic. Vol. 104 July 2000. pp.
279--303.

[7-PDF]
[7-PS]
**
Translating
IΔ _{0} + exp proofs into weaker systems.**
Mathematical
Logic Quarterly.

[6-PDF]
[6-PS]
**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-PDF]
[5-PS]
**
Structure
and Definability in General Bounded Arithmetic Theories.**
Annals of Pure and Applied Logic.
Vol 100. October 1999.
pp.189--245.

[4-PDF] [4-PS]
**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-PDF]
[3-PS] **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-PDF] [2-PS]
**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-PDF] **Arithmetic
Theories
with Prenex Normal Form Induction.**
Ph.D. Thesis. UC San Diego. 1997.

[Rev 13-PDF]
[Rev 13-PS]
**Review of S. Cook and N. Thapen paper: ``The Strength of
Replacement in Weak Arithmetic''**
Mathematical Reviews. MR#2264422.

[Rev 12-PDF]
[Rev 12-PS]
**Review of G. Ferreira and I. Oitavem paper: ``An Interpretation of S ^{1}_{2} in Σ^{b}_{2}-NIA.''**
Mathematical Reviews. MR#2287276.

[Rev 11-PDF]
[Rev 11-PS]
**Review of P. Naumov paper: ``Upper bounds on complexity of Frege proofs with limited use of certain
schemata.''**
Mathematical Reviews. MR#2227496.

[Rev 11-PDF]
[Rev 11-PS]
**Review of M. R. Fellows, S. Szeider and G. Wrightson paper: ``On finding short resolution refutations and
small
unsatisfiable subsets.''**
Mathematical Reviews. MR#2202495.

[Rev 10-PDF]
[Rev 10-PS]
**Review of M. Jarvisalo, T. A. Junttila and I. Niemela paper: ``Unrestricted vs restricted cut in a tableau
method for Boolean circuits.''**
Mathematical Reviews. MR#2185702.

[Rev 9-PDF]
[Rev 9-PS]
**Review of J. Krajicek paper: ``Structured pigeonhole principle,
search problems, and hard tautologies.''**
Mathematical Reviews. MR#2140049.

[Rev 8-PDF]
[Rev 8-PS]
**Review of M. Alekhnovich, E. Ben-Sasson, A. Razborov, and A Wigderson paper: ``Pseudorandom number generators in propositional proof
complexity.''**
Mathematical Reviews. MR#2114305.

[Rev 7-PDF]
[Rev 7-PS]
**Review of M. Moniri paper: ``Polynomial induction and length minimization in intuitionistic bounded arithmetic.''**
Mathematical Reviews. MR#2099386.

[Rev 6-PDF]
[Rev 6-PS]
**Review of J. Krajicek paper: ``Dual weak pigeonhole principle,
pseudo-surjective functions, and provability of circuit lower bounds .''**
Mathematical Reviews. MR#2039361.

[Rev 5-PDF]
[Rev 5-PS]
**Review of A. Beckmann paper: ``Dynamic ordinal analysis.''**
Mathematical Reviews. MR#2018084.

[Rev 4-PDF]
[Rev 4-PS]
**Review of Buresh-Oppenheim, Clegg, Impagliazzo, Pitassi paper: ``Homogenization and the
polynomial calculus.''**
Mathematical Reviews. MR#2022043.

[Rev 3-PDF]
[Rev 3-PS] **Review of P. Pudlak paper: ``Parallel Strategies.''**
Mathematical Reviews. MR#2017351.

[Rev 2-PDF]
[Rev 2-PS]
**Review of M. Moniri paper: ``Comparing constructive arithmetical
theories based on NP-PIND and coNP-PIND.''**
Mathematical Reviews. MR#2030203.

[Rev 1-PDF]
[Rev 1-PS]
**Review of A. Beckmann paper: ``Proving consistency of equational theories
in bounded arithmetic.''**
Bulletin of Symbolic Logic. Vol. 9. No. 1. 2003.
pp.44-45.

These are some papers I am author on that were mainly dealing with research conducted by master's students who I either supervised or was on their commitee.

[MS 5-PDF]
**Neural Network CAPTCHA Crackers.** (with Geetika Garg).
Proceedings of the Future Technology Conference 2016. San Francisco, CA. 2016. pp. 853-861.

[MS 4-PDF]
**An Open Source Advertisement System.** (with Pushkar Umaranikar)
International Journal of Computer, Electrical, Automation, Control and Information Engineering. Vol. 10. No. 6. 2016. pp. 898-907.

[MS
3-PDF]
**A Scalable Media Job Framework for an Open Source Search Engine.** (with Pooja Mishra ) To Appear
International Journal of Computer, Electrical, Automation, Control and Information Engineering. Vol. 10. No. 5. 2016. pp. 790-797.

[MS 2-PDF]
[MS 2-PS]
**Stealthy Ciphertext.** (with Martina Simova and Mark Stamp)
Proceeding of the Conference on Internet Computing.
2005. pp. 380--386.

[MS 1-PDF]
[MS 1-PS]
**On using Mouse Movement as a Biometric.** (with Shivani Hashia and Mark Stamp)
The 3rd International Conference on Computer Science and its Applications. (ICCSA)
. 2005. pp. 143--147.

This is a partial list of talks I have given at various places, together
with overheads if I could find them.

This document was last modified Tuesday, 06-Dec-2016 22:05:32 PST.

**Oct. 9, 2011. ****Neural Net Captcha Cracker**.
Talk given at Future Technology Conference 2016, San Francisco, Dec 6, 2016.

**Oct. 9, 2011. On the Finite Axiomatizability of Prenex R ^{1}_{2}**.
Talk given at BIRS. Banff, Canada.

**April 8. 2008. Weak Definability Notions for Independence
Results in Bounded
Arithmetic**. Talk given at Oberwolfach, Germany.

**Feb. 1. 2008. The Surjective Weak Pigeonhole Principle in
Bounded Arithmetic. Talk given at VIG 2008, UCLA**.

**Apr. 10. 2006. When can S ^{1}_{2} prove the weak pigeonhole principle? Talk
given at Newton Mathematical Institute, Cambridge University.** An embarassing glitch appeared
in a proof in the original talk on the next to last slide. This is corrected in the version I am posting here.

It is well known result of Krajicek and Pudlak that if S^{1}_{2} could prove
the injective weak pigeonhole principle for every polynomial time function
then RSA would not be secure. In this talk, we will consider function
algebras based on a common characterization of the polynomial time functions
where we slightly modify the initial functions and further restrict the amount
of allowable recursion. We will then argue that S^{1}_{2} can prove the
surjective weak pigeonhole principle for functions in this algebra.

**Apr. 4. 2006. Introduction to Quantum Branching Programs. Talk
given at Berkeley Quantum Information and Computation Seminar (Chemistry Department, UC Berkeley). (Joint
work with Farid Ablayev, Aida Gainutdinova, Marek Karpinski, and Cristopher
Moore.)**

Branching programs of bounded width are a nonuniform model of computation which can be viewed as generalizing finite automata. As such they are a relatively simple model of computation and quantum versions of branching programs might serve as a good model on which to develop potentially implementable quantum algorithms. In this talk we will introduce quantum branching programs and discuss upper and lower bounds in terms of deterministic and stochastic models of computation on what kind of algorithms are implementable on quantum branching programs.

**Dec. 1. 2005. Video Game Engines. Talk given to High School Students at National Hispanic University Charter
High School.**

**Apr. 16. 2005. Circuits Principles and Weak Pigeonhole Principles. Talk
given at AMS Sectional Meeting #1007, UC Santa Barbara, Special Session on Complexity of Computation
and Algorithms. (Joint work with Norman
Danner.)** The next four talks listed below are very similar, this talk's set of slides is probably
the best. I am retiring this talk at this point.

This talk considers the relational versions of the surjective and multifunction weak pigeonhole
principles for various classes
of formulas. These principles are interesting because of their close connection to the provability of
circuit lower bounds,
and hence the P versus NP question, in weak systems of arithmetic. We show that the relational
surjective pigeonhole
principle for Θ^{b}_{1} in S^{1}_{2} implies a circuit
block-recognition principle which in turn implies the surjective weak
pigeonhole principle for Σ^{b}_{1} formulas. We introduce a class of predicates
corresponding to poly-log length iterates of
polynomial-time computable predicates and show that over R^{1}_{2}, the multifunction
pigeonhole principle for such predicates
is equivalent to an "iterative" circuit block-recognition principle. A consequence of this is that if
R^{2}_{3} proves this circuit
iteration principle then RSA is vulnerable to quasi-polynomial time attacks.

**Mar. 22. 2005. Equivalents of the Weak Multifunction Pigeonhole Principle. Talk
given at Oberwolfach, Germany. (Joint work with Norman
Danner.)**

This talk discusses joint work of myself with Norman Danner of Wesleyan
University.
I began the talk by presenting a recent result of Jerabek on
the surjective weak pigeonhole principle for p-time functions. Namely,
that over the theory S^{1}_{2} this principle is
equivalent to the
existence of a string which is hard for any circuit of size n^{k}.
This
shows that T^{2}_{2}, a slightly stronger theory, can
prove a predicate
exists which is hard for circuits of size n^{k}. Krajicek and
Pudlak have shown if the injective weak pigeonhole principle
for p-time functions is witnessable from a class C
satisfying PTIME^{C} = C then RSA is insecure against
attacks from C. As the multifunction weak pigeonhole
principle
implies both the injective and surjective principles, it is natural to
wonder if there is any circuit class such that the existence of a hard
string for this class is equivalent to the multifunction weak pigeonhole
principle for the analogous uniform class. We show that for
R^{2}_{2}, a
theory between T^{2}_{2} and S^{1}_{2}
in strength, the multifunction weak
pigeonhole principle for quasi-log iterated p-time relations is
equivalent to circuit lower bounds for quasi-log iterated p-size
circuits. Thus, we show if R^{2}_{2} could prove lower
bounds for this
class of circuits, one can also show RSA is insecure against
quasi-polynomial time attacks.

**Feb. 1. 2005. Circuit principles and weak pigeonhole variants. Talk given for
my CATS 2005 paper, Newcastle, Australia. (Joint work with Norman
Danner.)**

This paper/talk considers the relational versions of the surjective and
multifunction
weak pigeonhole principles for PV, Σ^{b}_{1} and
Θ^{b}_{2}-formulas.
We show that the relational
surjective pigeonhole principle for Θ^{b}_{2}-formulas
in S^{1}_{2}
implies a circuit block-recognition principle which in turn
implies the surjective weak pigeonhole principle for
Σ^{b}_{1}
formulas.
We introduce a class of predicates corresponding to poly-log length
iterates of polynomial-time computable predicates and show that
over R^{2}_{2}, the multifunction pigeonhole principle for
such predicates
is equivalent to an ``iterative'' circuit block-recognition principle.
A consequence of this is that if
R^{2}_{3} proves this circuit iteration principle then RSA
is vulnerable to
quasi-polynomial time attacks.

**Nov. 4. 2004. Circuit Principles, The Weak Pigeonhole
Principle, and RSA. SJSU Computer Science Colloquium. Nov 4. 2004. (Joint work with Norman Danner.)**

The weak pigeonhole principle for a relation says that the relation does not represent a map of n^{2} pigeons into n
holes such
that each pigeon is mapped and each hole only gets one pigeon. This principle for polynomial time relations is closely
connected with the RSA cryptographic scheme. In particular, Krajicek and Pudlak have shown that if given any polynomial time
relation one can find a polynomial time algorithm which finds for this relation either an unmapped pigeon or two pigeons in
the the same hole, then one could break RSA in polynomial time. In this talk we will discuss this result. It is also an open
area of research how much mathematics is needed to prove the weak pigeonhole principle. We will show this problem for
certain weak systems is connected to whether the system can prove lower bounds on the the size of circuits. After discussing
several results of this type from our own research and that of Jerabek, we will finally connect this back to the security of
RSA.

**Aug. 19, 2003. Weak Arithmetics and Unrelativized Independence Results. Invited talk. Logic
Colloquium 2003 (LC 2003). Helsinki, Finland.**

In this talk I will survey some techniques which can be used to show unrelativized independence results for questions like NP vs coNP, the collapse of the polynomial hierarchy, or Hilbert's Tenth Problem in weak systems of arithmetic. I will also present some new results concerning the limits of formalizing padding arguments in commonly studied weak arithmetics.

**Apr. 15, 2003. On the Power of Classical and
Quantum Branching Programs. CS Colloquium. Santa Clara University.**

Branching Programs have proven to be a useful model of computation in a variety of domains such as hardware verification, model checking, and other CAD applications. As branching programs are also a very simple model of computation with several easy ways to restrict their power, it is interesting to generalize the branching program model to the quantum setting. In this talk I will survey some of the known results about classical branching programs, discuss (assuming no background in quantum mechanics) how both classical and quantum branching program models work, and describe some of our results concerning the power of the quantum branching program model.

**Jan. 25, 2003. Bounded Versions of Hilbert's Tenth Problem and NP
= co-NP. Mini-Workshop: Hilbert's Tenth Problem, Mazur's Conjecture
and Divisibility Sequences. Mathematisches Forschungsinstitut Oberwolfach.
Oberwolfach, Germany.**

We discuss the provability of Matijasevich-Robinson-Davis-Putnam (MRDP) result in weak systems of arithmetic. It is a well-known result of Gaifman and Dimitricopoulos IDelta_0+exp proves MRDP. What was shown in their result was that every bounded formula in their language could be rewritten as a formula consisting of an existential block of quantifiers followed by an equation of the form p = q where p and q are polynomials. By Parikh's Theorem, IDelta_0+exp cannot prove the existence of superexponentially fast growing functions. Therefore, one could ask whether if one expanded the language by IDelta_0+exp's access to it, then one could obtain a system unable to prove MRDP in this new language. This is possible because now the bounds on the quantifiers that need to be eliminated are larger than before. In fact, we construct a system that cannot prove MRDP and show as well that it cannot prove NP = co-NP in a certain very uniform way.

**Nov. 27, 2002. Nepomnjascij's Theorem and Independence Proofs in
Bounded Arithmetic. Logic Colloquium. UC Berkeley.**

Many complexity classes in computer science, for example, functions in PTIME, LOGSPACE, NC, AC^0, have characterizations in terms of being the provably "NP-definable" functions of some weak theory of arithmetic. If the complexity class in question is known not to be equal to NP, this can be used to show the weak system of arithmetic cannot prove NP = co-NP. The problem with this kind of result is, of course, you need to be able to show first that the complexity class in question is different from NP. For all but the weakest classes this question has been open for quite some time. In this talk I will survey some of my own work in this area as well as some recent work of Ressayre and Boughattas. Then I will present some new results of mine based on Nepomnjascij's Theorem that get around this barrier in a slightly different setting related to the problem of whether nondeterministic linear time is equal to co-nondeterministic linear time and related to how strong a theory of arithmetic is needed to prove the Matiyasevich-Robinson-Davis-Putnam Theorem.

**Aug. 7, 2002. Quantum and Stochastic Branching Programs of Bounded
Width. 29th International Colloquium on Automata, Languages, and
Programming. (ICALP 2002). Malaga, Spain.**

**Jun. 29, 2002. Using IDelta_0 in independence proofs.
Bounded Arithmetic and Complexity Classes 2002. (BACC 2002). Lisbon,
Portugal. **

**Jun. 7, 2002. On the Bounded Version of Hilbert's Tenth Problem.
21st Days of Weak Arithmetics. (JAF '21) Steklov Institute of Mathematics
St.Petersburg, Russia.**

Hilbert's Tenth problem concerned the decidability of Diophantine
equations over the integers. Its negative solution, Matiyassevich's
theorem, amounted to showing that the class of formulas of the form

(exists y)P(x,y)=Q(x,y)

where P, Q are polynomials with natural number coefficients is equivalent
to the class of recursively enumerable sets. The bounded form of Hilbert's
Tenth problem is whether the NP-predicates are the class D of predicates
given by formulas of the form

( exists y)[(\sum_j yj <= 2^{|\sum_i xi|^k}) /\ P(x,y)=Q(x, y)]

where P, Q are polynomials with natural coefficients. This problem is
related to the average case completeness of certain NP-problems.
In this talk we give lower bounds on the provability of both these
problems in weak fragments of arithmetic. We show the theory I^5E cannot
prove D=NP. Here I^mE has a finite set of axioms and induction on bounded
existential formulas up to m lengths of a number for the language L_2,
which has the symbols <= , 0, S, +, x#y, |x|, 2^{|x||y|}, \lfloor x/2^i
\rfloor, and limited subtraction. We use the non-provability of D=NP to
show that I^5E cannot prove the Matiyassevich's theorem.

**Apr. 8, 2002. Implicit Complexity and Bounded Arithmetic Theories.
Mathematische Logik. Mathematisches Forschungsinstitut Oberwolfach.
Oberwolfach, Germany.**

Bounded arithmetic theories are weak fragments of arithmetic useful in the study of computational complexity classes. In this talk we will discuss known techniques for doing independence proofs in these theories. We will then consider the question of classifying the Sigma^b_1≠definable multifunctions of a particular bounded arithmetic theory, S_2. Such a classification might prove useful in proving new independence results. We will then indicate why an implicit complexity approach to this characterization might be reasonable.

**Jun., 2001. Computational complexity and independence results.
Meeting on Discrete Mathematics and Mathematical Cybernetics
organized by Moscow State University. Dubna,
Russia.**

**Jul. 30, 2000. Strengths and Weaknesses of LH Arithmetic. Contributed
paper and talk. Logic Colloquium
2000 (LC 2000). Paris, France.**

In Pollett~\cite{cpollett00} a bounded arithmetic theory $Z$ was shown not to be able to prove the collapse of the polynomial hierarchy. This theory also had the property that if $Z \subseteq S^i_2$ for any $i\geq 1$ then the polynomial hierarchy collapses. Here $S^i_2$ are the theories of Buss~\cite{bus86a}. Unfortunately, despite this property $Z$ seemed too weak a theory to formalize many of the arguments that have been used in computational complexity. In this talk, we give a new arithmetic characterization of the levels of $\log$-time hierarchy. Using this characterization, we propose a new variant of the theory $TAC^0$ of Clote and Takeuti~\cite{clotak95}. This variant has nice deductive fragments which in some sense correspond to the levels of the log-time hierarchy. We show that this theory (like $Z$) cannot prove the collapse of the polynomial hierarchy. Furthermore, we give some evidence that this theory may be strong enough to prove that the log-time hierarchy is infinite, so unlike $Z$ it can carry out useful complexity arguments.

**Jul., 2000. On the Complexity of Quantum ACC. Computational Complexity
2000. Florence, Italy.** The linked slides have some the content of the original talk; however, some slides are
from a job interview at SJSU and page 13 has been lost.

**Nov. 5, 1999. Strengths and Weaknesses of LH Arithmetic.
Logic Colloquium, UCLA.**

One way to quantify the difficulty of P = NP problem would be to exhibit a logical theory which is capable of formalizing current attempts at answering this question and yet which is not powerful enough to prove or disprove this equality. Razborov has argued that most current circuit lower bound techniques can be formalized in a fragment of arithmetic which roughly has induction on NE-predicates. Nevertheless, exhibiting any fragment of arithmetic which one can demonstrate cannot prove the collapse of the polynomial hierarchy is nontrivial. In this talk we will consider a much weaker theory than Razborov's, but which we argue can still do some interesting mathematics. Namely, it can "reason" about all the functions in the log-time hierarchy, it can prove the log-time hierarchy differs from NP, and, in fact, we give some evidence it might be able to show the log-time hierarchy is infinite. (In the real world this is known to be true.) On the other hand, we show this theory cannot prove the polynomial hierarchy collapses. So, in particular, it cannot prove P = NP, and it follows that any proof that the polynomial hierarchy collapses, if such a proof exists, must be formalized in a stronger fragment than ours.

**Mar. 21, 1999. Using translation to separate bounded arithmetic
theories. ASL Annual Meeting. UC San Diego.**

**Aug. 3-7, 1998. Multifunction Algebras and Provability of the Collapse
of PH. Proof Theory and Complexity 1998. (PTAC 1998). BRICS, Aarhus,
Denmark.**

In this talk I will introduce some multifunctions algebras which
for i > 1 correspond to functions computable in polynomial time with a
limited number of witnessing queries to an oracle at the i - 1 level of
the hierarchy. We then consider two subtheories of the well-studied
bounded arithmetic theory S_2 of Buss. Actually, one of our theories is
contained in the other. Using our algebras (mainly the i = 1 variants on
our algebras) we
establish the following properties for these theories:
(1) Neither theory can prove the polynomial hierarchy collapses.

(2) If either theory is contained in S^i_2

for some i then the polynomial hierarchy
collapses.

(3) If either theory proves the polynomial hierarchy is infinite then for
all i, S^i_2

can separate the ith level of the hierarchy.

(4) There is an interesting initial segment of any model of the weaker
theory that satisfies all of IDelta_0 + exp. (Postscript: statement 4 in
restrospect was not quite correct, although it did lead to me write a
paper about IDelta_0 +exp presented in San Diego.)

**Apr. 17, 1998. Bounded query classes and Bounded Arithmetic.
Adelphia University.**

In trying to solve the P=NP question people have developed lower bounds techniques such as Hastad's Switching Lemma, Razborov-Smolensky, etc. These techniques can often be formalized in very weak theories of arithmetic. One such theory which can prove the Switching Lemma is S_2(\alpha). A natural question is "can one show that the P=NP problem is independent of such theories?" If so, one can rule out certain lower bounds methods as a means of solving this problem. In this talk we will consider some complexity questions related to fragments of S_2(\alpha) and bounded query classes. We will use our results to derive a weak relativized independence result.

**Mar. 5, 1998. Bounded query classes and bounded arithmetic.
Logic, Computability and Complexity 1998. (LCC 1998). Amsterdam,
Netherlands.**

There is a well-known result of Krajicek which connects the bounded query class P^{\Sigma^p_i}(log) with the Delta^b_{i+1}-predicates of S^i_2. In this talk we discuss a generalization of this result which was motivated by trying to show the Delta^b_{i+1}-predicates of R^i_2 are P^{Sigma^p_i}(loglog). We also discuss a general condition result which can be used to show on bounded arithmetic theory is conservative over another. We then use these results together with recent results about bounded query classes to derive tighter collapses of the polynomial hierarchy under the assumption that various bounded arithmetic theories are equal. We finally discuss new relativized seperations of bounded arithmetic theories and a weak relativized independence result.

**Oct.(?), 1997. Structure and Definability in Bounded Arithmetic
Theories. Logic Seminar. Massachusetts Institute of Technology.**

**Jul. 28, 1997. Nonmonotonic Reasoning with Quantified Boolean
Constraints. The Fourth International Conference on Logic Programming and
Nonmonotonic Reasoning (LPNMR '97). Schloss Dagstuhl, Germany.**

We define and investigate the complexity of several nonmonotonic logics with quantified Boolean formulas as constraints. We give quantified constraint versions of the constraint programming formalism of Marek, Nerode, and Remmel [15] and of the natural extension of their theory to default logic. We also introduce a new formalism which adds constraints to circumscription. We show that standard complexity results for each of these formalisms generalize in the quantified constraint case. Gogic, Kautz, Papadimitriou, and Selman [8] have introduced a new method for measuring the strengths of reasoning formalisms based on succinctness of model representation. We show a natural hierarchy based on this measure exists between our versions of logic programming, circumscription, and default logic. Finally, we discuss some results about the relative succinctness of our reasoning formalisms versus any formalism for which model checking can be done somewhere in the polynomial time hierarchy.

**May 27, 1997. My thesis defense
talk. UC San Diego.**

This document last modified Tuesday, 06-Dec-2016 22:05:32 PST.