PUBLICATIONS

Marķa Luisa Bonet Carbonell

Journals

Books and book chapters

Conferences

Journals

  1. Marķa Luisa Bonet and Samuel R. Buss (1993).
    ``The Deduction Rule and Linear and Near-linear Proof Simulations''
    Revista: Journal of Symbolic Logic, 58 (2):688-709.
    Download: PostScript or PDF

  2. Marķa Luisa Bonet and Samuel R. Buss (1994).
    ``Size-Depth Tradeoffs for Boolean Formulae''
    Information Processing Letters, 49 (3):151-155.
    Download: PostScript or PDF

  3. Marķa Luisa Bonet and Samuel R. Buss (1995).
    ``The Serial Transitive Closure Problem for Trees''
    SIAM Journal of Computing, 24 (1):109-122.
    Download: PostScript or PDF

  4. Marķa Luisa Bonet, Toniann Pitassi and Ran Raz (1997).
    ``Lower Bounds for Cutting Planes Proofs with Small Coefficients''
    Journal of Symbolic Logic, 62 (3):708-728.
    Download: PostScript or PDF

  5. Marķa Luisa Bonet, Mike Steel, Tandy Warnow and Shibu Yooseph (1998).
    ``Bether Methods for Solving Parsimony and Compatibility''
    Journal of Computational Biology, 5 (3):391-408.
    Download: PostScript or PDF

  6. Marķa Bonet, Cynthia Phillips, Tandy Warnow, and Shibu Yooseph (1999).
    ``Constructing Evolutionary Trees in the Presence of Polymorphic Characters''
    SIAM Journal of Computing, 29 (1):103-131.
    Download: PostScript or PDF

  7. Marķa Luisa Bonet, Toniann Pitassi, and Ran Raz (2000).
    ``On Interpolation and Automatization for Frege Proof Systems''
    SIAM Journal of Computing, 29 (6):1939-1967.
    Download: PostScript or PDF

  8. Marķa Luisa Bonet, Juan Luis Esteban, Nicola Galesi and Jan Johansen (2000).
    ``On the Relative Complexity of Resolution Refinements and Cutting Planes Proof Systems''
    SIAM Journal of Computing, 30 (5):1462-1484.
    Download: PostScript or PDF

  9. Marķa Luisa Bonet and Nicola Galesi (2001).
    ``Optimality of Size-width Tradeoffs for Resolution''
    Computational Complexity, 10 (4):261-276.
    Download: PostScript or PDF

  10. Albert Atserias, Marķa Luisa Bonet and Juan Luis Esteban (2002).
    ``Lower Bounds for the Weak Pigeonhole Principle and Random Formulas Beyond Resolution''
    Information and Computation, 176 (2):136-152.
    Download: PostScript or PDF

  11. Marķa Luisa Bonet and Nicola Galesi (2003)
    ``Degree Complexity for a Modified Pigeonhole Principle''
    Archive for Mathematical Logic, 42 (5):403-414.
    Download: PostScript or PDF

  12. Albert Atserias and Marķa Luisa Bonet (2004).
    ``On the Automatizability of Resolution and Related Propositional Proof Systems''
    Information and Computation, 189(2):182-201.
    Download: PostScript or PDF

  13. Marķa Luisa Bonet, Carlos Domingo, Ricard Gavaldą, Alexis Maciel and Toniann Pitassi (2004).
    ``Non-automatizability of Bounded-depth Frege Proofs''
    Computational Complexity, 13:47-68..
    Download: PostScript or PDF

  14. Marķa Luisa Bonet, Katherine StJohn, Ruchi Mahindru and Nina Amenta.
    ``Approximating Subtree Distances Between Phylogenies''.
    Journal of Computational Biology, 13(8).
    Download: PostScript or PDF

Books and book chapters

  1. Marķa Luisa Bonet (1991).
    ``The Lengths of Propositional Proofs and the Deduction Rule''.
    PhD Thesis, University of California, Berkeley.

  2. Marķa Luisa Bonet (1993).
    ``Number of Symbols in Frege Proofs with and without the Deduction Rule''.
    Peter Clote and Jan Krajķcek ``Arithmetic, Proof Theory and Computational Complexity''.
    Oxford University Press. Pages 61-95.
    Download: PostScript or PDF

  3. Marķa Luisa Bonet, Samuel R. Buss and Toniann Pitassi (1995).
    ``Hard Examples for Frege Proof Systems''.
    P. Clote and F. Remmel ``Feasible Mathematics II''.
    Birhäuser. Pages 30-56.
    Download: PostScript or PDF

  4. Marķa Luisa Bonet, Cynthia Phillips, Tandy Warnow, and Shibu Yooseph (1997).
    ``Inferring Evolutionary Trees from Polymorphic Characters, and an Analysis of the Indo-European Family of Languages''.
    B. Mirkin, F. R. McMorris, F. Roberts and A. Rzhetsky ``Mathematical Hierarchies and Biology''.
    American Mathematical Society, DIMACS Series in Discrete Mathematics and Theoretical Computer Science 37. Pages 43-55.

  5. Marķa Luisa Bonet and Nicola Galesi (1998).
    ``Linear Lower Bounds and Simulations in Frege Systems with Substitutions''.
    Nielsen and Thomas ``Computer Science Logic, 11th International Workshop, CSL '97, Selected Papers''.
    Lecture Notes in Computer Science, 1414, Springer-Verlag. Pages 115-128.
    Download: PostScript or PDF

Conferences

  1. Marķa Luisa Bonet and Samuel R. Buss.
    ``On the Deduction Rule and the Number of Proof Lines''.
    IEEE Symposium on Logic in Computer Science, LICS'91.
    Proceedings of the Sixth Annual IEEE Symposium on Logic in Computer Science, IEEE Computer Society Press, 1991, pages 286-297.
    Amsterdam, Holand. July 15-18,1991.
    Download: PostScript or PDF

  2. Marķa Luisa Bonet, Toniann Pitassi and Ran Raz.
    ``Lower Bounds for Cutting Planes with Small Coefficients''.
    ACM Symposium on the Theory of Computing, STOC'95.
    Proceedings of the 27th ACM Symposium on the Theory of Computing, ACM Press, 1995, pages 575-584.
    Las Vegas, Nevada, USA. May 29 - June 1, 1995.
    Download: PDF

  3. Marķa Luisa Bonet, Cynthia Phillips, Tandy Warnow, and Shibu Yooseph.
    ``Constructing Evolutionary Trees in the Presence of Polymorphic Characters''.
    ACM Symposium on the Theory of Computing, STOC'96.
    Proceedings of the 28th ACM Symposium on the Theory of Computing, ACM Press, 1996, pages 220-229.
    Philadelphia, Pennsylvania, USA. May 20-24, 1996.
    Download: PDF

  4. Marķa Luisa Bonet, Nicola Galesi.
    ``Linear Lower Bounds and Simulations in Frege Systems with Substitutions''.
    EACSL Annual Conference of the European Association for Computer Science Logic, CSL'97.
    Proceedings of the 11th Annual Conference of the European Association for Computer Science Logic, EACSL Press, 1997. pages 109-119.
    Aarhus, Denmark. August 23-29, 1997.
    Download: PostScript or PDF

  5. Marķa Luisa Bonet, Toniann Pitassi and Ran Raz.
    ``No Feasible Interpolation for $TC^0$-Frege Proofs''.
    IEEE Symposium on Foundations of Computer Science, FOCS'97.
    Proceedings of the 38th Annual IEEE Symposium on Foundations of Computer Science, IEEE Computer Society Press, 1997, pages 254-263.
    Miami Beach, Florida, USA. October 20-22, 1997.
    Download: PostScript or PDF

  6. Marķa Bonet, Mike Steel, Tandy Warnow and Shibu Yooseph.
    ``Bether Methods for Solving Parsimony and Compatibility''.
    ACM Conference on Computational Molecular Biology, RECOMB'98.
    Proceedings of the Second Annual International Conference on Research in Computational Molecular Biology, ACM Press, 1998, pages 40-49.
    New York, USA. March 22-25, 1998.
    Download: PostScript or PDF

  7. Marķa Luisa Bonet, Juan Luis Esteban, Nicola Galesi and Jan Johansen.
    ``Exponential Separations between Restricted Resolution and Cutting Planes Proof Systems''.
    IEEE Symposium on Foundations of Computer Science, FOCS'98.
    Proceedings of the 39th Annual IEEE Symposium on Foundations of Computer Science, IEEE Computer Society Press, 1998, pages 638-647.
    Palo Alto, California, USA. Nobember 8-11, 1998.
    Download: PostScript or PDF

  8. Marķa Luisa Bonet, Carlos Domingo, Ricard Gavaldą, Alexis Maciel and Toniann Pitassi.
    ``Non-automatizability of Bounded-depth Frege Proofs''.
    IEEE Conference on Computational Complexity, CCC'99.
    Proceedings of the 14th Annual IEEE Conference on Computational Complexity, IEEE Computer Society Press, 1999, pages 15-23.
    Atlanta, Georgia, USA. May 4-6, 1999.
    Download: PostScript or PDF

  9. Marķa Luisa Bonet and Nicola Galesi.
    ``A Study of Proof Search Algorithms for Resolution and Polynomial Calculus''.
    IEEE Symposium on Foundations of Computer Science, FOCS'99.
    Proceedings of the 40th Annual IEEE Symposium on Foundations of Computer Science, IEEE Computer Society Press, 1999, pages 422-432
    Nueva York, USA. October 17-19, 1999.
    Download: PostScript or PDF

  10. Albert Atserias, Marķa Luisa Bonet and Juan Luis Esteban.
    ``Lower Bounds for the Weak Pigeonhole Principle Beyond Resolution''.
    28th International Colloquium on Automata, Languages and Programming, ICALP'01.
    Proceedings of the 28th International Colloquium on Automata, Languages and Programming, 2001, pages 1005-1016. Lecture Notes in Computer Science 2076, Springer.
    Creta, Grece. July 8-12, 2001.
    Download: PostScript

  11. Albert Atserias and Marķa Luisa Bonet.
    ``On the Automatizability of Resolution and Related Propositional Proof Systems''.
    Annual Conference of the European Association for Computer Science Logic, CSL'02.
    Proceedings of the 16th Annual Conference of the European Association for Computer Science Logic, CSL'02. Lecture Notes in Computer Science 2471, Springer.
    Edinburgh, Scotland. September 22-25, 2002.
    Download: PostScript or PDF

  12. Marķa Luisa Bonet, Jordi Levy and Felip Manya.
    ``A Complete Calculus for Max-SAT ''.
    Proceedings of the 9th International Conference on Theory and Applications on Satisfiability Testing, SAT 2006
    Seattle, USA. August 12-15, 2006.
    Download: PostScript or PDF

  13. Carlos Ansotegui, Marķa Luisa Bonet, Jordy Levy and Felip Manya.
    ``Resolution for Weighted CSP ''.
    Proceedings of the 20th International Joint Conference on Artificial Intelligence, IJCAI'07.
    Hyderabad, India. January 6-12, 2007.
    Download: PostScript or PDF