Erika De Benedetti

PhD

DipInfo@UniTo

Tel~ +39 011670 6815
Email~ @di.unito.it

Who am I?

Last update: February 12, 2015

I earned both my bachelor and master degree in Computer Science at the University of Torino with passing marks 110 / 110 magna cum laude.
My master thesis, with title "Polynomial lambda-calculus via intersection types", has been recommended for publication.

I was awarded the Optime Award by the Industrial Union of Torino for best results achieved in master thesis in 2010/2011.
In 2012 I was awarded the Silver Medal by the University of Torino for best master thesis in computer science 2010/2011.

I earned my italian and french PhD on February 10, 2015 in Torino, at the end of a three-years joint PhD programme (cotutelle) between the Dipartimento di Informatica (UniTo) and the LIP (ENS de Lyon), under the joint supervision of Simonetta Ronchi Della Rocca and Patrick Baillot. My PhD thesis is titled Linear logic, type assignment systems and implicit computational complexity. [.pdf]

Since January 2015 I obtained a research grant at the Dipartimento di Informatica in Torino.

I am a member of the Formal Methods in Computing group in Torino and former member of the PLUME (Preuves et Langages) group in Lyon.

I was a member of the organizing committee of CSL 2013, the annual meeting of the European Association for Computer Science Logic, held in Torino from the 1st to the 6th of September 2013.
In 2013 I also created and maintained the website of DICE 2013.

My working place is located at Dipartimento di Informatica, Corso Svizzera 185 - Torino: Office 6, 1st floor.

A little tag-cloud of my research topics:

functional languages implicit computational complexity intersection types lambda-calculus linear logic polynomial characterization semantics of programming languages type systems

 

Conference and seminar presentations

Last update: February 12, 2015

A type assignment for lambda-calculus complete both for FPTIME and strong normalization.

  • DICE 2012 (Tallinn) - March 31, 2012 [.pdf]
  • LIP (ENS de Lyon) - June 11, 2012
  • ICTCS 2012 (Varese) - September 20, 2012 [.pdf]

Bounding normalization times through intersection types

  • ITRS 2012 (Dubrovnik) - June 29, 2012 [.pdf]

ELL revisited for polynomial time and an exponential time hierarchy

  • Lambda-group meeting (Torino) - October 26, 2012 [.pdf]

Characterizing polynomial and exponential complexity classes in elementary lambda-calculus

  • GdT meeting (ENS de Lyon) - June 24, 2013 (part 1)
  • GdT meeting (ENS de Lyon) - March 31, 2014 (part 2)
  • DICE 2014 (Grenoble) - April 5, 2014 [.pdf]
  • TCS 2014 (Roma) - September 2, 2014 [.pdf]

Linear logic, type assignment systems and implicit computational complexity (PhD defense)

  • Dipartimento di Informatica (Torino) - February 10, 2015 [.pdf]

Publications, thesis and works in progress

Last update: February 4, 2015

See also the common publications page.

[DB14] Erika De Benedetti. Linear logic, type assignment systems and implicit computational complexity. PhD thesis, Universita' degli Studi di Torino - ENS de Lyon, 2014. [.pdf]

In this thesis we study the linear logic approach to implicit computational complexity, with the aim of giving a characterization of one or more complexity classes through type assignment systems for (variant of) lambda-calculus.

[BDBRDR14] Patrick Baillot, Erika De Benedetti and Simona Ronchi Della Rocca. Characterizing polynomial and exponential complexity classes in elementary lambda-calculus. IFIP TCS 2014: 151-163. [.pdf]

In the present work we define an elementary lambda-calculus which is typable in elementary logic. We prove then that the hierarchy of complexity classes k-EXPTIME is characterized by a hierarchy of types. Moreover we extend this result from the classes of problems to the corresponding classes of functions.

[DBRDR14] Erika De Benedetti and Simona Ronchi Della Rocca. A type assignment for lambda-calculus complete both for FPTIME and strong normalization. To appear in Information and Computation, 2014. [.pdf]

A type assignment for lambda calculus is presented, which is sound and complete for polynomial time computations and strong normalization.

[DBRDR13] Erika De Benedetti and Simona Ronchi Della Rocca. Bounding normalization time through intersection types. CoRR, abs/1307.8205, 2013. [.pdf]

Non-idempotent intersection types are used in order to give a bound of the length of the normalization beta-reduction sequence of a lambda term: namely, the bound is expressed as a function of the size of the term.

[DB11] Erika De Benedetti. Polynomial lambda-calculus via intersection types. Master's thesis, Universita' degli Studi di Torino, 2011. [.pdf]

In my master thesis I extend the Soft Type Assignment system of Gaboardi-Ronchi using intersection types and I prove that typed lambda-terms in this system characterize PTIME functions.

Teaching

Last update: November 27, 2013

A.a. 2013-2014

Il calendario delle sessioni di tutorato collettivo è reperibile sulla piattaforma i-learn (autenticazione necessaria). È possibile richiedere appuntamento ai tutor tramite l'indirizzo tutorprog{[at]}educ.di.unito.it.

Random things that I love

Pelosoni affettuosi. Progressive/psychedelic rock. Casina e decorazioni varie.
FIMO, disegni e videogiochi. Altro pelosone affettuoso ma letale. Torino.
L'amore mio. Il mare. Pizza buona.