# Lógica, Provas e Algoritmos

## Alessandra Carbone

### Current Position

Associate Professor, Department of Mathematics and
Computer Science, University of Paris 12
### Education

**1985** University of Milan (Italy), M.A. in Computer Science.
**1988** University of Siena (Italy), Specialization School in
Mathematical Logic.

Thesis advisors: Franco Montagna and Dick de Jongh
**1992** The City College of New York, M.A. in Pure Mathematics
**1993** The Graduate School of the City University of New York,
PhD in Mathematics.

Thesis advisor: Rohit Parikh
### Interests

Proof complexity, structures of proofs, combinatorics, combinatorial
group theory, automata theory.
### Visiting positions (selected)

**Jun-Jul 1989 and Jun-Jul 1990**
Department of Mathematics of the University of Amsterdam
(The Netherlands)
**Sept 1993 - Aug 1995**
Department of Mathematics, University of Paris 7.
Holding a postdoctoral fellowship from the EC.
**Dec 1993 and April 1994 **
Department of Mathematics of the Technische Universität Wien
(Austria).
**Sept 1995- Aug 1996**
Department of Discrete Mathematics and Algebra of the
Technische Universität Wien (Austria). Holding a Lise-Meitner
Fellowship for Science of the Austrian Science Foundation.
**Jan-Feb 1996**
Institut des Hautes Études Scientifiques, Bures-sur-Yvette (France).
**April 1996**
DIMACS, Piscataway (USA).
**December 1996**
Tata Institute of Fundamental Research, Bombay (India) and
Institute of Mathematical Sciences, Madras (India).
April 1997
Courant Institute of Mathematical Sciences, New York (USA)
### Invited addresses (selection)

*Proof Theory, Complexity, Metamathematics*,
5-8 April, 1994. Technische Universität Wien (Vienna, Austria).
*Proof Theory and Proof Search* Workshop,
11-12 November, 1994. University of Paris 7 (Paris, France).
*Workshop on Feasible Arithmetics and Length of Proofs*,
21-23 April, 1996. DIMACS (Center for Discrete Mathematics and
Theoretical Computer Science), Rutgers University (NJ, USA).
Section in Honor of Prof. Parikh - *16 FST-TCS Conference*,
18-20 December, 1996. Hyderabad (India).
*Geometry and Complexity*,
5-9 May, 1997. The Fields Institute, Toronto (Canada).
### Service (selection)

Co-organizer, with Misha Gromov (IHES) of the meeting
*Patterns formation in geometry, biology and computer graphics*,
I.H.E.S. (Bures sur Yvette, Francia), December 1997.
Member of the Program Committee for the *A.S.L. Meeting* (joint to
the annual meeting of the AMS), Baltimore, USA, January 1998.
Member of Program Committee of *CSL'98*, annual conference
of the European Association of Computer Science Logic (EACSL). Brno,
Check Republic, August 31-September 4, 1998.
### List of Publications (selected)

#### Dissertations

Ph.D. Dissertation, *On logical flow graphs*,
The City University of New York, NY, USA, 1993.
Thesis of Specialization in Mathematical Logic, *The length of proofs*,
University of Siena, 1988.
#### Research articles (selection)

``Rosser Orderings in Bimodal Logics''
with Franco Montagna, *Zeitschrift für Mathematische Logik und
Grundlagen der Mathematik* 35:343-358, 1989.
``Much Shorter Proofs: a Bimodal Investigations''
with Franco Montagna, *Zeitschrift für Mathematische Logik und
Grundlagen der Mathematik*. 36, 1990.
``Provable Fixed Points in $I\Delta _0 +\Omega _1$''
*Notre Dame Journal of Formal Logic*. 32:562-572,1991.
``Interpolants, Cut Elimination and Flow Graphs for the Propositional
Calculus'',
*Annals of Pure and Applied Logic* 83:249-299, 1997.
``The Craig Interpolation Theorem for Schematic Systems''.
In *Collegium Logicum - Annals of the Kurt Gödel Society*,
Springer-Verlag, vol. 2, 1996, 87-100.
``Making proofs without Modus Ponens: an introduction to the combinatorics
and complexity of cut elimination'',
with Stephen Semmes. In *Bullettin of the American Mathematical
Society* 34:131--159, 1997.
``Turning cycles into spirals''.
To appear in *Annals of Pure and Applied Logic*, 1997.
``Looking from the inside and from the outside'',
with Stephen Semmes, IHES preprint M/96/44, Bures-sur-Yvette (France),
1996. Submitted.
``Some Combinatorics behind Proofs''. Submitted, 1996.
``No Speed-Up for the Non-Standard Theory of Feasible Numbers''.
Submitted, 1997.
#### Books

*Geometry and Symmetry of Implicit Representations*.
Graphs, Formal proofs, Algorithmic Recursion and Complexity.
with Stephen Semmes. In preparation, 1997.