Sophie Laplante

According to our database, Sophie Laplante authored at least 26 papers between 1991 and 2023.

Collaborative distances:

• Dijkstra number of three.
• Erdős number of two.

2023

The communication complexity of functions with large outputs.

Lila Fontes, Sophie Laplante, Mathieu Laurière, Alexandre Nolin

Electron. Colloquium Comput. Complex., 2023

2022

Certificate games.

Sourav Chakraborty, Anna Gál, Sophie Laplante, Rajat Mittal, Anupa Sunny

Electron. Colloquium Comput. Complex., 2022

2020

Sensitivity lower bounds from linear dependencies.

Sophie Laplante, Reza Naserasr, Anupa Sunny

Electron. Colloquium Comput. Complex., 2020

2019

Key Establishment à la Merkle in a Quantum World.

Gilles Brassard, Peter Høyer, Kassem Kalach, Marc Kaplan, Sophie Laplante, Louis Salvail

J. Cryptol., 2019

2017

Provably Secure Key Establishment Against Quantum Adversaries.

Aleksandrs Belovs, Gilles Brassard, Peter Høyer, Marc Kaplan, Sophie Laplante, Louis Salvail

Proceedings of the 12th Conference on the Theory of Quantum Computation, 2017

2016

Robust Bell Inequalities from Communication Complexity.

Sophie Laplante, Mathieu Laurière, Alexandre Nolin, Jérémie Roland, Gabriel Senno

Proceedings of the 11th Conference on the Theory of Quantum Computation, 2016

2015

Relative Discrepancy does not separate Information and Communication Complexity.

Lila Fontes, Rahul Jain, Iordanis Kerenidis, Sophie Laplante, Mathieu Laurière, Jérémie Roland

Electron. Colloquium Comput. Complex., 2015

2012

Classical and quantum partition bound and detector inefficiency.

Sophie Laplante, Virginie Lerays, Jérémie Roland

Electron. Colloquium Comput. Complex., 2012

Lower bounds on information complexity via zero-communication protocols and applications.

Iordanis Kerenidis, Sophie Laplante, Virginie Lerays, Jérémie Roland, David Xiao

Electron. Colloquium Comput. Complex., 2012

2011

Kolmogorov complexity and combinatorial methods in communication complexity.

Marc Kaplan, Sophie Laplante

Theor. Comput. Sci., 2011

Non-local box complexity and secure function evaluation.

Marc Kaplan, Sophie Laplante, Iordanis Kerenidis, Jérémie Roland

Quantum Inf. Comput., 2011

The communication complexity of non-signaling distributions.

Julien Degorre, Marc Kaplan, Sophie Laplante, Jérémie Roland

Quantum Inf. Comput., 2011

Merkle Puzzles in a Quantum World.

Gilles Brassard, Peter Høyer, Kassem Kalach, Marc Kaplan, Sophie Laplante, Louis Salvail

Proceedings of the Advances in Cryptology - CRYPTO 2011, 2011

2008

Lower Bounds for Randomized and Quantum Query Complexity Using Kolmogorov Arguments.

Sophie Laplante, Frédéric Magniez

SIAM J. Comput., 2008

2007

Probabilistic abstraction for model checking: An approach based on property testing.

Sophie Laplante, Richard Lassaigne, Frédéric Magniez, Sylvain Peyronnet, Michel de Rougemont

ACM Trans. Comput. Log., 2007

Cryptographic Security of Individual Instances.

Luis Antunes, Sophie Laplante, Alexandre Pinto, Liliana C. M. Salvador

Proceedings of the Information Theoretic Security - Second International Conference, 2007

2006

The Quantum Adversary Method and Classical Formula Size Lower Bounds.

Sophie Laplante, Troy Lee, Mario Szegedy

Comput. Complex., 2006

Lower Bounds Using Kolmogorov Complexity.

Sophie Laplante

Proceedings of the Logical Approaches to Computational Barriers, 2006

2001

Resource-Bounded Kolmogorov Complexity Revisited.

Harry Buhrman, Lance Fortnow, Sophie Laplante

SIAM J. Comput., 2001

Quantum Kolmogorov Complexity.

André Berthiaume, Wim van Dam, Sophie Laplante

J. Comput. Syst. Sci., 2001

2000

New Bounds for the Language Compression Problem.

Harry Buhrman, Sophie Laplante, Peter Bro Miltersen

Proceedings of the 15th Annual IEEE Conference on Computational Complexity, 2000

1999

Stronger Separations for Random-Self-Reducibility, Rounds, and Advice.

László Babai, Sophie Laplante

Proceedings of the 14th Annual IEEE Conference on Computational Complexity, 1999

1998

On Coherence, Random-Self-Reducibility, and Self-Correction.

Joan Feigenbaum, Lance Fortnow, Sophie Laplante, Ashish V. Naik

Comput. Complex., 1998

Nearly Optimal Language Compression Using Extractors.

Lance Fortnow, Sophie Laplante

Proceedings of the STACS 98, 1998

1995

Circuit Lower Bounds à la Kolmogorov.

Lance Fortnow, Sophie Laplante

Inf. Comput., 1995

1991

Computationally Convincing Proofs of Knowledge.

Gilles Brassard, Claude Crépeau, Sophie Laplante, Christian Léger

Proceedings of the STACS 91, 1991