Sophie Laplante
Sophie Laplante
IRIF, Université Paris Cité
Verified email at
Cited by
Cited by
Lower bounds on information complexity via zero-communication protocols and applications
I Kerenidis, S Laplante, V Lerays, J Roland, D Xiao
SIAM Journal on Computing 44 (5), 1550-1572, 2015
Lower bounds for randomized and quantum query complexity using Kolmogorov arguments
S Laplante, F Magniez
SIAM Journal on Computing 38 (1), 46-62, 2008
Quantum kolmogorov complexity
A Berthiaume, W Van Dam, S Laplante
Journal of Computer and System Sciences 63 (2), 201-221, 2001
The quantum adversary method and classical formula size lower bounds
S Laplante, T Lee, M Szegedy
computational complexity 15 (2), 163-196, 2006
Simulating quantum correlations as a distributed sampling problem
J Degorre, S Laplante, J Roland
Physical Review A 72 (6), 062314, 2005
Resource-bounded Kolmogorov complexity revisited
H Buhrman, L Fortnow, S Laplante
SIAM Journal on Computing 31 (3), 887-905, 2001
Probabilistic abstraction for model checking: An approach based on property testing
S Laplante, R Lassaigne, F Magniez, S Peyronnet, M De Rougemont
ACM Transactions on Computational Logic (TOCL) 8 (4), 20-es, 2007
The communication complexity of non-signaling distributions
J Degorre, M Kaplan, S Laplante, J Roland
International Symposium on Mathematical Foundations of Computer Science, 270-281, 2009
Merkle puzzles in a quantum world
G Brassard, P Høyer, K Kalach, M Kaplan, S Laplante, L Salvail
Annual Cryptology Conference, 391-410, 2011
Classical simulation of traceless binary observables on any bipartite quantum state
J Degorre, S Laplante, J Roland
Physical Review A 75 (1), 012309, 2007
On coherence, random-self-reducibility, and self-correction
J Feigenbaum, L Fortnow, S Laplante, A Naik
Computational Complexity 7 (2), 174-191, 1998
Computationally convincing proofs of knowledge
G Brassard, S Laplante, C Crépeau, C Léger
Annual Symposium on Theoretical Aspects of Computer Science, 251-262, 1991
Cryptographic security of individual instances
L Antunes, S Laplante, A Pinto, L Salvador
International Conference on Information Theoretic Security, 195-210, 2007
Relative discrepancy does not separate information and communication complexity
L Fontes, R Jain, I Kerenidis, S Laplante, M Laurière, J Roland
ACM Transactions on Computation Theory (TOCT) 9 (1), 1-15, 2016
Classical and quantum partition bound and detector inefficiency
S Laplante, V Lerays, J Roland
International Colloquium on Automata, Languages, and Programming, 617-628, 2012
New bounds for the language compression problem
H Buhrman, S Laplante, PB Miltersen
Proceedings 15th Annual IEEE Conference on Computational Complexity, 126-130, 2000
Robust Bell inequalities from communication complexity
S Laplante, M Laurière, A Nolin, J Roland, G Senno
Quantum 2, 72, 2018
Circuit lower bounds a la Kolmogorov
L Fortnow, S Laplante
Information and Computation 123 (1), 121-126, 1995
Stronger separations for random-self-reducibility, rounds, and advice
L Babai, S Laplante
Proceedings. Fourteenth Annual IEEE Conference on Computational Complexity …, 1999
Nearly optimal language compression using extractors
L Fortnow, S Laplante
Annual Symposium on Theoretical Aspects of Computer Science, 84-93, 1998
The system can't perform the operation now. Try again later.
Articles 1–20