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

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 Sunday, 09-Oct-2011 19:23:43 PDT.

Publications

[25-PDF] [25-PS] Conservative Fragments of S12 and R12. 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 S12. (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] 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-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. 46:249-256 (No.2) May 2000.

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

Reviews

[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 S12 in Σb2-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.

Master's Students Papers

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

Talks

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 Sunday, 09-Oct-2011 19:23:43 PDT.

Oct. 9, 2011. On the Finite Axiomatizability of Prenex R12. 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 S12 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 S12 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 S12 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 Θb1 in S12 implies a circuit block-recognition principle which in turn implies the surjective weak pigeonhole principle for Σb1 formulas. We introduce a class of predicates corresponding to poly-log length iterates of polynomial-time computable predicates and show that over R12, the multifunction pigeonhole principle for such predicates is equivalent to an "iterative" circuit block-recognition principle. A consequence of this is that if R23 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 S12 this principle is equivalent to the existence of a string which is hard for any circuit of size nk. This shows that T22, a slightly stronger theory, can prove a predicate exists which is hard for circuits of size nk. Krajicek and Pudlak have shown if the injective weak pigeonhole principle for p-time functions is witnessable from a class C satisfying PTIMEC = 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 R22, a theory between T22 and S12 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 R22 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, Σb1 and Θb2-formulas. We show that the relational surjective pigeonhole principle for Θb2-formulas in S12 implies a circuit block-recognition principle which in turn implies the surjective weak pigeonhole principle for Σb1 formulas. We introduce a class of predicates corresponding to poly-log length iterates of polynomial-time computable predicates and show that over R22, the multifunction pigeonhole principle for such predicates is equivalent to an ``iterative'' circuit block-recognition principle. A consequence of this is that if R23 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 n2 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 Sunday, 09-Oct-2011 19:23:43 PDT.