Research Summary
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, communication complexity, distributed
computing, cryptography, using randomization in algorithms and
proof techniques, and proof complexity.
My Erdős
number is 4.
Publications
Forthcoming
- L. Fontes, S. Laplante, M. Laurière, and A. Nolin. Lower
bounds for public-coin information complexity.
In preparation.
- L. Fontes, S. Laplante, M. Laurière, and A. Nolin.
The communication complexity of functions with large
outputs.
Submitted.
Journal Publications
- A. Ada, A. Chattopadhyay, S. Cook, L. Fontes, M. Koucký,
T. Pitassi. The Hardness of Being Private. ACM
Transactions on Computation Theory Vol. 6(1), 2014.
- S. Cook and L. Fontes. Formal Theories for Linear
Algebra. Logical Methods in Computer Science, Vol. 8 (1:25),
2012, pp.1-31.
Conference Publications
- L. Fontes, R. Jain, I. Kerenidis, S. Laplante,
M. Laurière. Relative discrepancy does not separate
information and communication complexity. International
Colloquium on Automata, Languages, and Programming, Vol. 1,
2015, pp. 506-516.
- A. Ada, A. Chattopadhyay, S. Cook, L. Fontes, M. Koucký,
T. Pitassi. The Hardness of Being
Private. 27th IEEE Conference on Computational
Complexity, 2012.
- S. Cook and L. Fontes. Formal Theories for Linear
Algebra. Computer Science and Logic, 2010.
Manuscripts
- Trading Privacy for Communication. Ph. D. thesis in
Computer Science, University of Toronto, 2014. Supervised by
Toniann Pitassi and Stephen Cook.
- Formal Theories for Logspace Counting. M. Sc. thesis
in Computer Science, University of Toronto, 2009. Supervised by
Stephen Cook.
- Independence Results for Peano Arithmetic.
Undergraduate thesis, honors mathematics at Harvard,
2007. Supervised by Peter Koellner.