Toniann Pitassi's Home Page
Pitassi received bachelors and masters degrees from
Pennsylvania State University
and then received a PhD from the University of Toronto in
1992. After that, Toni spent 2 years as a postdoc at UCSD,
and then 2 years as an assistant professor (in mathematics with
a joint appt in computer science) at the University of Pittsburgh.
Since September, 1996, she has been at the Department of Computer
Science at the University of Arizona, now as an associate professor.
Contact Information:
Phone: (+1) 520-621-4526
Fax: (+1) 520-621-4246
E-Mail: toni@cs.arizona.edu
Research Interests
- Complexity theory
- Logic, bounded arithmetic
- propositional theorem proving (both lower bounds as well as
automated theorem proving
- concrete complexity theory, algorithms
Papers (in random order)
- Homogenization and the polynomial calculus ,
Buresh-Oppenheim, J., Clegg, M., Impagliazzo, R., and Pitassi, T.
Submitted for publication, 1999.
- A new proof of the weak
pigeonhole principle , Maciel, A., Pitassi, T., and Woods, A.
Submitted for publication, 1999.
- Linear gaps between degrees for the
polynomial calculus modulo distinct primes ,
Buss, S., Grigoreiv, D., Impagliazzo, R., and Pitassi, T.
Proceedings from ACM Symposium on the Theory of
Computing, 1999.
- Stochastic Satisfiability ,
Littman, M., Majercik, S., and Pitassi, T.
To appear in Journal of Artificial Intelligence , 1999.
- On the complexity of unsatisfiability
proofs for random kCNF formulas , Beame, P., Karp, R.,
Pitassi, T., and Saks, M.
Submitted for publication, 1999.
- No automatization or interpolation for
bounded-depth Frege systems , Bonet, M., Domingo, C., Gavalda, R.,
Maciel, A., and Pitassi, T.
Proceedings from IEEE Conference on Complexity Theory, 1999.
- Propositional proof complexity and
unsolvability of polynomial equations ,
Pitassi, T.
Proceedings of ICM 1998, Berlin, 1998.
- Propositional proof complexity:
Past, Present and Future, Beame, P., and Pitassi, T.
The Computatonal Complexity Column, in the Bulletin of
the EATCS.
Also appeared as TR98-067 in ECCC.
- Decidability and recursive
functions ,
Brecht, T., Mcilraith, S., and Pitassi, T.
To appear in Encyclopedia of Electrical Engineering .
-
Resolution and the weak pigeonhole principle ,
Buss, S., and Pitassi, T.
Springer-Verlag Lecture Notes in Computer Science .
(Publications of selected papers presented at
Proceedings from Computer Science Logic '97.
- Algebraic propositional proof systems ,
Pitassi, T.
DIMACS Series in Discrete Mathematics and Theoretical Computer
Science ,
Volume 31, Descriptive Complexity and Finite Models,
Editors Immerman, and Kolaitis, pp. 214-244.
- Are there hard examples for
Frege systems?, Bonet, M., Buss, S., and Pitassi, T. (1994).
Feasible Mathematics, Volume II, Birkhauser,
pp. 30-56.
- Minimal propositional proof length is NP-hard
to linearly approximate, Aleknovich, A., Buss, S.,
Moran, S., and Pitassi, T.
To appear in Journal of Symbolic Logic.
- No interpolation or automatization
for Frege systems, Bonet, M., Pitassi, T., and Raz, R.
SIAM Journal of Computing.
- The relative complexity of NP
Search Problems, Paul Beame, Steve Cook, Jeff Edmonds,
Russell Impagliazzo, and Toniann Pitassi
Proceedings from 27th ACM Symposium on Theory of Computing,
1995, pp. 303-314.
- Lower bounds for Cutting
Planes proofs with Small Coefficients, Maria Bonet, Ran Raz
and Toniann Pitassi.
Proceedings from 26th ACM Symposium on Theory of Computing,
1995, pp. 575-584. (The full version of this paper will appear
in the Journal of Symbolic Logic.)
- Good degree bounds
on Nullstellensatz refutations of the induction principle,
Sam Buss and Toniann Pitassi.
Proceedings from Symposium on Computational
Complexity , 1996.
- The complexity of the Hajos Calculus,
Toniann Pitassi and Alasdair Urquhart.
Proceedings from 33rd IEEE Symposium on Foundations of Computer
Science, pp. 187-196. (The full version of this paper
appeared in SIAM Journal on Discrete Mathematics, Vol 8, Issue 3,
August 1995.)
- Lower bounds for Hilbert's
Nullstellensatz and propositional proofs,
with Paul Beame, Russell Impagliazzo, Jan Krajicek and Pavel Pudlak.
Proceedings from 35th IEEE Symposium on Foundations of
Computer Science, 1994, pp. 794-806.
(Full version to appear in Proceedings of the London Mathematical
Society.)
- Simplified and improved
Resolution lower bounds, Paul Beame and Toniann Pitassi
Proceedings from Symposium on Foundations of Computer Science.
- An exponential separation between
the parity principle and the pigeonhole principle.
Beame, P., and Pitassi, T. (1996).
Annals of Pure and Applied Logic,
Vol. 80, pp. 197-225.
- Exponential lower bounds
for the tree-like Hajos Calculus. Iwama, K., and Pitassi, T.
Information Processing Letters, Vol. 54, pp. 289-294.
- Improved depth lower bounds for
small distance connectivity, with Paul Beame and Russell
Impagliazzo.
Proceedings from 36th IEEE Symposium on Foundations of
Computer Science 1995, pp. 692-703.
- Upper and lower bounds for tree-like
cutting planes proofs., Impagliazzo, R., Pitassi, T.,
and Urquhart, A.
Proceedings from Logic in Computer Science.
Pictures
