Informal Workshop on Logic and Complexity

Torino, 28^th and 29^th June 2004

The idea is to bring together researchers involved in the italian national project “Protocollo”, one of whose research mainstreams is about implicit characterizations of computational classes, mainly based on structural proof-theroy.

The programme divides essentially in three parts:

• Monday 28^th , in the morning: the most stable material and ideas, will be presented. The speakers will have slots of 1 hour;

• Monday 28^th , in the afternoon: less formalized subjects and problems will be presented. The speakers will have slots of about 1 hour whose sharing of time, between presentation and discussion, is up to the speakers;

• Tuesday29^th , in the morning: open discussion, may be in separate groups, each working on one the subjects, illustrated in the morning, or something related.
  

Scheduling, Abstracts of stable material, Abstracts of works in progress, and a Participants follow.

Scheduling

Abstracts of stable material

• Ugo Dal Lago. "On Light Logics, Uniform Encoding and Polynomial Time". Abstract: "We investigate on the extensional expressive power of Light Affine Logic, analysing the class of uniformly representable functions for various fragments of the logic. We give evidence on the incompleteness (for polynomial time) of the propositional fragment. Following previous work, we show that second order leads to polytime unsoundness. We then introduce simple constraints on second order quantification and least fixpoints, proving the obtained fragment to be polytime sound and complete."
• Damiano Mazza. "Unifying Light Logics". Abstract: "We present a sequent calculus/proof-net system for linear logic in which all extant ``light'' systems (systems having a time bound on cut-elimination, i.e., ELL, LLL, and SLL) appear as fragments. One of the interesting aspects of this calculus is that it is based upon a decomposition of the exponential connectives which seems to be related to the one arising from game semantics/ludics, according to which the exponential modalities should be seen as the sum of a purely structural part and a "polarity shift" ".

Abstracts of works in progress

• Marco Pedicini. "Polynomial Computations with Reals and Programming". No abstract.
• Ugo Dal Lago. "Relating structural proof-theory and non-size encreasing polynomial computations". No abstract.
• Luca Roversi. "Fix-point operators and LAL". No abstract.
• Ugo Dal Lago. "Approximation theorem and Computational Complexity". No abstract.

Participants

• Mario Coppo
• Paolo Coppola
• Ugo De'Liguoro
• Mariangiola Dezani
• Giuseppe Falzetta
• Ugo Dal Lago
• Andrea Masini
• Simone Martini
• Damiano Mazza
• Luca Paolini
• Marco Pedicini
• Simona Ronchi Della Rocca
• Luca Roversi