<!doctype html public "-//w3c//dtd html 4.0 transitional//en">

<html>

<head>

   <meta http-equiv="Content-Type" content="text/html; charset=iso-8859-1">

   <meta name="GENERATOR" content="Mozilla/4.75 [en] (X11; U; SunOS 5.5.1 sun4u) [Netscape]">

   <title>Research</title>

<!-- Changed by: M. Luisa Bonet,  4-Nov-1998 -->

</head>

<body>

<p><b><font color="#008000"><font size=+2>Journal Publications</font></font></b>

Albert Atserias, Maria Luisa Bonet and Juan Luis Esteban.

<i>``<a href="infocomp.ps.gz"> Lower Bounds for the Weak Pigeonhole Principle

Beyond Resolution </a>''</i>. Accepted for publication in

<b>Information and Computation.</b>

Maria Luisa Bonet and Nicola Galesi.

<i>``<a href="archive.ps.gz"> Degree Complexity for a Modified Pigeonhole

Principle</a>''.</i> Accepted for publication in the

<b>Archive for Mathematical Logic.</b>

Maria Luisa Bonet and Nicola Galesi.

``Optimality of Size-Width trade-offs for Resolution''.

Accepted for publication at the <b> Journal of Computational Complexity.</b>

<p>Maria Luisa Bonet, Carlos Domingo, Ricard Gavalda, Alexis Maciel and

Toniann Pitassi.

<i>``Non-automatizability of bounded-depth Frege proofs''.</i>

Under review.

Maria Luisa Bonet, Juan Luis Esteban, Nicola Galesi and Jan Johansen.

<i>``<a href="FOCS98.ps.gz">On

the Relative Complexity of Resolution Refinements and Cutting Planes Proof

Systems</a>''.</i> <b> SIAM Journal of Computing.</b> vol. 30, num.5, pag.

1462-1484.

<p>Maria Luisa Bonet, Toniann Pitassi and Ran Raz. <i>``<a href="FOCS97.ps.gz">

On Interpolation and Automatization for Frege Systems</a>''.

</i> <b> SIAM Journal

of Computing.</b> vol.29, num. 6,2000, pag. 1939-1967.

Maria Luisa Bonet, Cynthia Phillips, Tandy Warnow, and Shibu Yooseph.

<i>``<a href="SIAMtandy.ps.gz">Constructing

Evolutionary Trees in the Presence o f Polymorphic Characters</a>''.</i><b>SIAM

Journal of Computing.</b> vol.29, num.1, 1999, pag. 103-131.

Maria Luisa Bonet, Mike Steel, Tandy Warnow y Shibu Yooseph.

<i>Bether

Methods for Solving Parsimony and Compatibility.</i><b>Journal of Computational

Biology.</b> vol. 5, num 3, 1998, pag. 391-407.

Maria Luisa Bonet, Toniann Pitassi y Ran Raz.

<i>Lower Bounds for Cutting

Planes with Small Coefficients.Journal of Symbolic Logic (JSL),vol.

62, num. 3, Septiembre 1997, pag. 708--728.

<p>Maria Luisa Bonet and Samue R. Buss. <i>``On the serial transitive

closure problem''.</i> <b> SIAM Journal of Computing, 24(1):109-122.</b>

1995.

<p>Maria Luisa Bonet and Samuel R. Buss. <i>``Size-Depth Tradeoffs for

Parity and Parity-free Boolean Formulae''.</i> <b>Information Processing

Letters, 49: 151-155.</b> 1994.

<p>Maria Luisa Bonet and Samuel R. Buss. <i>``The deduction rule and linear

and near-linear proof simulations''.</i> <b>Journal of Symbolic Logic (JSL),

58(2):688-709.</b> 1993.

<p><b><font color="#008000"><font size=+2>Book Chapters and Thesis</font></font></b>

<p>Maria Luisa Bonet and Nicola Galesi. <i>``Linear lower bounds and simulations

in Frege systems with substitutions''.</i> <b>Lecture Notes in Computer

Science, 1414.</b> Pages 115-128. Springer-Verlag, 1998.

Maria Luisa Bonet, Cynthia Phillips, Tandy Warnow, and Shibu Yooseph.

<i>``Inferring Evolutionary Trees from

Polymorphic Characters, and an Analysis of the Indo-European

Family of Languages''.</i> <b>DIMACS Series in Discrete Mathematics

and Theoretical Computer Science, 37: 43-55.</b> 1997.

<p>Maria Luisa Bonet, Samuel R. Buss and Toniann Pitassi. <i>``Hard Examples

for Frege Proof Systems''.</i> <b>Feasible Mathematics II,</b> P. Clote

and F. Remmel (Ed.) Pages 30-56. Editorial Birhäuser, 1995.

<p>Maria Luisa Bonet <i>``Number of Symbols in Frege Proofs with and without

the Deduction Rule''.</i> <b>Arithmetic, Proof Theory and Computational

Complexity, Peter Clote and Jan Krajícek, (ed.). Pages 61-95.

1993.

<p>Maria Luisa Bonet <i>``The Lengths of Propositional Proofs and the Deduction

Rule''. PHD Thesis. 1991. University of California, Berkeley.

<p><b><font color="#008000"><font size=+2>Conference Publications</font></font></b>

Albert Atserias, Maria Luisa Bonet and Juan Luis Esteban.

<i>``<a href="ICALP01.ps.gz"> Lower Bounds for the Weak Pigeonhole

Principle Beyond Resolution</a>''</i>. <b>ICALP 2001.</b>

<p>Maria Luisa Bonet, Nicola Galesi.<i>``<a href="FOCS99.ps.gz">A Study

of Proof Search Algorithms for Resolution and Polynomial Calculus</a>''.

<b>40th

IEEE Symposium on Foundations of Computer Science, FOCS'99.</b>

Maria Luisa Bonet, Juan Luis Esteban, Nicola Galesi and Jan Johansen.

<i>``<a href="FOCS98.ps.gz">Exponential Separations between

Restricted Resolution and Cutting Planes Proof Systems</a>''.

<b>39th IEEE Symposium on Foundations of Computer Science, FOCS'98.</b>

Standord, California USA. 1998.

<p>Maria Luisa Bonet, Carlos Domingo, Ricard Gavaldá, Alexis

Maciel and Toniann Pitassi.

<i>``<a href="complexity98.ps.gz">Non-automatizability

of Bounded-Depth Frege Proofs</a>''</i>. <b>IEEE Conference on Computational

Complexity.</b> 1998.

Maria Bonet, Mike Steel, Tandy Warnow, and Shibu Yooseph.

<i> ``<a href="compbio.ps.gz">Better

Methods for Solving Parsimony and Compatibility</a>''.

<b>Second Annual

International Conference on Computational Molecular Biology. 1998.

Maria Luisa Bonet and Nicola Galesi.

<i>``Linear lower bounds and simulations

in Frege systems with substitutions''</i>. <b>Annual Conference of the European

Association for Computer Science Logic, CSL'97.</b> Nielsen and Thomas

(Ed.)

Maria Luisa Bonet, Toniann Pitassi y Ran Raz.

<i>`` No Feasible Interpolation

for $TC^0$-Frege Proofs''</i>. <b>38th IEEE Symposium on Foundations of Computer

Science, FOCS'97.</b> Pages 254-265. Miami Beach, Florida, USA. 1997.

<p>Maria Luisa Bonet, Cynthia Phillips, Tandy Warnow, and Shibu Yooseph

<i>``Constructing Evolutionary Trees

in the Presence of Polymorphic Characters''</i>.<b>ACM Symposium

on the Theory of Computing, STOC'96. Philadelphia, Pensylvania, USA.

1996.

<p>Maria Luisa Bonet, Toniann Pitassi and Ran Raz.<i> ``Lower Bounds for

Cutting Planes with Small Coefficients''</i>. <b>ACM Symposium on the Theory

of Computing, STOC'95. Las Vegas, Nevada, USA. 1995.

<p>Maria Luisa Bonet and Samuel R. Buss.<i> ``On the deduction rule and

the number of proof lines''</i>. <b>IEEE Symposium on Logic in Computer Science,

LICS'91.</b> Pages 286-297. Amsterdam, Holand. 1991.

</body>

</html>