Sophie Laplante

Publications

• The communication complexity of functions with large outputs ECCC Technical report TR23-041, 2023. SIROCCO 2023, to appear.

• Sourav Chakraborty, Anna Gal, Sophie Laplante, Rajat Mittal, Anupa Sunny Certificate games ECCC Technical report TR22-143, 2022. ITCS 2023.
• Sophie Laplante, Loris Perez, Sylvie Tissot, Lou Vettier, , QuBOBS, physical devices and a visual representation to explain quantum computing. quant-ph technical report arXiv:2211.16324, 2022.

• Sophie Laplante, Reza Naserasr, Anupa Sunny, Sensitivity lower bounds from linear dependencies ECCC technical report TR20-002, 2020. MFCS 2020: 62:1-62:14.

• Gilles Brassard, Peter Hoyer, Kassem Kalach, Marc Kaplan, Sophie Laplante, Louis Salvail, Key establishment a la Merkle in a Quantum World. Journal of Cryptology, Vol 32, no 3, 2019.

• Sophie Laplante, Mathieu Laurière, Alexandre Nolin, Jérémie Roland, and Gabriel Senno Robust Bell inequalities from communication complexity Quantum 2, 72 (2018).

• Alexandrs Belovs, Gilles Brassard, Peter Høyer, Marc Kaplan, Sophie Laplante, and Louis Salvail, Provably secure key establishment against quantum adversaries. Proceedings of TQC 2017. quant-ph Technical Report number 1704.08182.

• Sophie Laplante, Mathieu Lauriere, Alexandre Nolin, Jérémie Roland, Gabriel Senno, Robust Bell inequalities from communication complexity. Proceedings of TQC 2016, LIPIcs Vol. 61, 5:1-5:24. quant-ph Technical Report number 1606.09514, 2016.
• Lila Fontes, Rahul Jain, Iordanis Kerenidis, Sophie Laplante, Mathieu Lauriere, Jérémie Roland, Relative Discrepancy does not separate Information and Communication Complexity , ECCC TR15-028. ICALP 2015. ACM Transactions on Computation Theory (TOCT) 9 (1), 4, 2016. ACM Best of computing: Notable Books and Articles in Computing of 2016

• Iordanis Kerenidis, Sophie Laplante, Virginie Lerays, Jérémie Roland, David Xiao, Lower bounds on information complexity via zero-communication protocols and applications, SIAM J Comp.Vol 44, Number 5, 2015. FOCS 2012, pp. 500-509. quant-ph Report Number 1204.1505. ECCC Report Number TR12-038.

• Sophie Laplante, Virginie Lerays, Jérémie Roland, Classical and quantum partition bound and detector inefficiency, ICALP 2012, quant-ph Report Number 1203.4155. ECCC Report Number TR12-023.

• Gilles Brassard, Peter Hoyer, Kassem Kalach, Marc Kaplan, Sophie Laplante, Louis Salvail. Merkle Puzzles in a Quantum World, quant-ph Report Number 1108.2316. Proceedings of Crypto 2011, pp. 385-404. Journal of Cryptology, to appear.
• 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.

• Chapter in Le plus grand des hasards : Surprises quantiques, Dars, Papillault, editors. Belin 2010.

• 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.

• 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, Classical simulation of traceless binary observables on any bipartite quantum state. PRA, Vol.75, No.1, 2007. Also Simulation of bipartite qudit correlations quant-ph Technical Report number 0608064.
• 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, 8 (4), 2007. Also in LICS 2002. Also appears as ECCC Report TR01-051.

• 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.
• 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. (Computational Complexity, Special Issue on Complexity 2005, 15 (2) 2006, 163-196.)

• 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

• 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, 1998. (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.

Other publications

• 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