Sophie Laplante

Publications

• Gilles Brassard, Peter Hoyer, Kassem Kalach, Marc Kaplan, Sophie Laplante, Louis Salvail. Merkle Puzzles in a Quantum World, Proceedings of Crypto 2011, pp. 385-404. Quant-ph Report Number 1108.2316.
• Chapter in Le plus grand des hasards : Surprises quantiques, Dars, Papillault, editors. Belin 2010.
• Marc Kaplan, Iordanis Kerenidis, Sophie Laplante, Jeremie Roland, Non-local box complexity and secure function evaluation quant-ph Technical Report number 0903.2179. Proceedings of IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science, FSTTCS 2009, pages 239-250, 2009. Quantum Information and Computation, 11(1&2):40-69, 2011.
• Marc Kaplan, Sophie Laplante, Kolmogorov complexity and combinatorial methods in communication complexity, ECCC Report number TR-08-109. Proceedings of the Conference on Theory and Applications of Models of Computation 2009, pp. 261-270. Special Issue on TAMC, Theor. Comput. Sci. 412(23): 2524-2535 (2011)
• Julien Degorre, Marc Kaplan, Sophie Laplante, Jérémie Roland, The communication complexity of non-signaling distributions quant-ph Technical Report number 0804.4859. Proceedings 34th International Symposium of the Mathematical Foundations of Computer Science MFCS 2009, pp. 270-281. Quantum Information and Computation, 11(8): 0649-0676, 2011.
• Luis Antunes, Sophie Laplante, Alexandre Pinto, Liliana Salvador, Cryptographic security of individual instances, Proceedings of International Conference on Information Theoretic Security 2007, pp. 195-210.
• Julien Degorre, Sophie Laplante, Jérémie Roland, Simulation of bipartite qudit correlations quant-ph Technical Report number 0608064. PRA, Vol.75, No.1, 2007.
• Julia Kempe, Sophie Laplante, Frédéric Magniez, Comment calculer quantique, dossier spécial de La Recherche, numéro 398, juin 2006.
• Sophie Laplante, Lower bounds using Kolmogorov complexity, proceedings of CiE2006, invited in special session on Challenges in Complexity.
• Julien Degorre, Sophie Laplante, Jérémie Roland, Simulating quantum correlations as a distributed sampling problem, quant-ph Technical Report number 0507120. Phys. Rev. A 72, 062314 (2005).
• RESQ 05 tutorial on adversary method slides
• Sophie Laplante, Troy Lee, and Mario Szegedy, The quantum adversary method and formula size lower bounds, quant-ph Technical Report number 0501057. Conference version, Proceedings of Complexity 2005, 76-90. (Computational Complexity, Special Issue on Complexity 2005, 15 (2) 2006, 163-196.)
• Sophie Laplante, Frederic Magniez, Lower bounds for randomized and quantum query complexity using Kolmogorov arguments. SIAM Journal on Computing, 38 (1) 2008, 46-62. Complexity 2004, 294-304. (slides) and quant-ph, Technical Report number 0311189.
• Sophie Laplante, Richard Lassaigne, Frederic Magniez, Sylvain Peyronnet, Michel de Rougemont. Probabilistic abstraction for model checking: An approach based on property testing, ACM Transactions on Computational Logic, to appear. Also in LICS 2002. Also appears as ECCC Report TR01-051.
• Harry Buhrman, Lance Fortnow, Sophie Laplante. Resource-bounded Kolmogorov complexity revisited, SIAM Journal on Computing, 2001. Includes results from the paper: Nearly Optimal Language Compression using Extractors, STACS 98.
• André Berthiaume, Wim van Dam, Sophie Laplante, Quantum Kolmogorov Complexity, Complexity 2000, 240-249. JCSS, Special Issue on Complexity 2000, Volume 63, No. 2, September 2001, 201-221.
• Harry Buhrman, Sophie Laplante, Peter Bro Miltersen, New Bounds for the Language Compression Problem, Complexity 2000, 126-130.
• Laszlo Babai, Sophie Laplante, Stronger separations for random-self-reducibility, rounds, and advice, Complexity 99, 98-104.
• Sophie Laplante, John Rogers, Indistinguishability.
• Joan Feigenbaum, Lance Fortnow, Sophie Laplante, Ashish Naik, On Coherence, Random-self-reducibility and Self-correction, Computational Complexity, Volume 7 number 2. (Journal version of the Complexity 97 paper.)
• Lance Fortnow, Sophie Laplante, Circuit Lower Bounds à la Kolmogorov, Information and Computation, Volume 123, Number 1, 1995.
• Gilles Brassard, Claude Crépeau, Sophie Laplante, Christian Léger, Computationally Convincing Proofs of Knowledge Proceedings of STACS 1991.

• Habilitation thesis, Université Paris-Sud Applications de la complexité de Kolmogorov a la complexité classique et quantique, slides
• Ph.D. Thesis, University of Chicago, Kolmogorov Techniques in Computational Complexity Theory
• Masters thesis, Université de Montréal, Le principe des boites noires en cryptologie: application et limites

Before printing think about the Environment. Avant d'imprimer, pensez à l'environnement