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.