Email: my last name at liafa.univ-paris-diderot.fr

Office: bâtiment Sophie Germain, 4058

Laboratoire d'Informatique Algorithmique: Fondements et Applications (LIAFA)

(Équipe Algorithmique et Complexité)

Université Paris Diderot Paris 7, Case 7014

75205 Paris Cedex 13

France

I am now a postdoc at the Université Paris 7 Diderot.

I completed my Ph. D. in computer science at the University of Toronto, as a member of the theory group, working under the supervision of Stephen Cook and Toni Pitassi. I did my undergraduate work at Harvard in mathematics, focusing on logic.

I am interested in tradeoffs between online privacy and other measures like communication cost, accuracy, and optimality. Can privacy be traded away in return for faster computation time or better answers to computational problems? Do the same protocols protect privacy from eavesdroppers and other participants? Are some applications and functions hopelessly privacy-revealing?

My general theory interests cover a variety of topics, including computability, distributed computing, cryptography, using randomization in algorithms and proof techniques, and proof complexity.

**How to Measure Privacy: a survey.** Working paper.

**Managing Incentives and Privacy in Mechanism Design.**
Working paper with Paolo Penna.

**Relative Discrepancy does not separate Information and Communication Complexity.**
Lila Fontes, Rahul Jain, Iordanis Kerenidis, Sophie Laplante, Mathieu Lauriere, and Jérémie Roland.
ECCC 2015. To appear in ICALP 2015.

**
The Hardness of Being Private
**.
Anil Ada, Arkadev Chattopadhyay, Stephen Cook, Lila Fontes, Michal
Koucký, Toniann Pitassi.
ACM Transactions on Computation Theory, volume 6(1), 2014.

**Trading Privacy for
Communication**. Lila Fontes.
Ph.D. dissertation, successfully defended
February 19, 2014.

**The Hardness of Being
Private**.
Anil Ada, Arkadev Chattopadhyay, Stephen Cook, Lila Fontes, Michal
Koucký, Toniann Pitassi.
CCC 2012
(slides).

**Formal Theories
for Linear Algebra**.
Stephen Cook and Lila Fontes.
Logical Methods in Computer Science Vo. 8 (1:25)2012,pp. 1--31.
An early version
appeared in
Computer Science Logic (CSL)
2010.

**Interpreting LAP into VparityL and V#L.**
Lila Fontes. Working paper.
(draft pdf)
This was subsumed by "Formal Theories for Linear Algebra,"
above.

**Formal Theories for Logspace Counting.**
Lila Fontes. M. Sc. thesis.
(pdf,
arXiv)

I enjoy teaching. I've been a teaching assistant for:

- Algorithm Design and Analysis (CSC 373 summer 2013 and fall 2011),
- Enriched Introduction to the Theory of Computation (CSC 240 winter 2013, 2010, and 2009),
- Introduction to the Theory of Computation (CSC 236 fall 2007 and 2012, winter 2008, & 2012),
- Automata Theory (CSC 448 winter 2011 & 2012),
- Computability and Logic (CSC 438/2404 fall 2011 and 2012),
- Computational Complexity and Computability (CSC 363 fall 2010, 2009 & 2008), and
- Algebra I: Theory of Groups and Vector Spaces (Math 122 fall 2006).

__Service:__
I was on the Department of Computer Science Chair's Search Committee
(spring 2010).
I served as treasurer for the Computer Science Graduate
Student Benevolent Society (CSGSBS) from '09-'11.
I was a CS representative to the Graduate Student Union '08-'09.

__Sports:__
I have in the past enjoyed gymnastics,
crew,
skiing, and
rugby, and
synchronized swimming.
This has resulted in some cool images of my knee
(see my MRI and
X-ray),
and some knee surgeries. I do not recommend knee surgery as an
enjoyable pastime.
I also run and sometimes
shoot arrows, although
not at the same time (yet).

__Communication:__
I have an online presence, as you well know.
I maintain a
personal
blog,
and, with my siblings, an oft-neglected silly
blog.
I sometimes tweet
interesting links, if you're into that kind of thing.

Complexity Zoo

Looking for a LaTeX symbol? Try
Detexify
or
The Comprehensive LaTeX Symbols List
.

Bibtex
help

MathWorld
+
Wikipedia
=
Planet Math

Mendeley

Grace Hopper

Anita Borg Institute

The estimated scale of the universe and everything
(warning: autoplays music)

Neighborhood markets in Paris

Help the British Library
accurately place historical maps
.

A F.A.Q. for your thesis defense.