Zobrazeno 1 - 10
of 32
pro vyhledávání: '"Sophie Laplante"'
Publikováno v:
Quantum, Vol 2, p 72 (2018)
The question of how large Bell inequality violations can be, for quantum distributions, has been the object of much work in the past several years. We say that a Bell inequality is normalized if its absolute value does not exceed 1 for any classical
Externí odkaz:
https://doaj.org/article/78cf393ccb74424099326730b8724033
Publikováno v:
Structural Information and Communication Complexity ISBN: 9783031327322
Externí odkaz:
https://explore.openaire.eu/search/publication?articleId=doi_________::c3b45822b7fa117e50de6e7b3eea5624
https://doi.org/10.1007/978-3-031-32733-9_19
https://doi.org/10.1007/978-3-031-32733-9_19
Publikováno v:
Journal of Cryptology. 32:601-634
In 1974, Ralph Merkle proposed the first unclassified protocol for secure communications over insecure channels. When legitimate communicating parties are willing to spend an amount of computational effort proportional to some parameter N, an eavesdr
Externí odkaz:
https://explore.openaire.eu/search/publication?articleId=doi_________::70e965b50c393a711e4df4e2a4f672be
https://doi.org/10.1007/s00145-019-09317-z
https://doi.org/10.1007/s00145-019-09317-z
Autor:
Mathieu Laurière, Jérémie Roland, Sophie Laplante, Iordanis Kerenidis, Rahul Jain, Lila Fontes
Publikováno v:
ACM Transactions on Computational Theory, 9 (1
Automata, Languages, and Programming ISBN: 9783662476710
ICALP (1)
42nd International Colloquium on Automata, Languages and Programming (ICALP'15)
Automata, Languages, and Programming ISBN: 9783662476710
ICALP (1)
42nd International Colloquium on Automata, Languages and Programming (ICALP'15)
Does the information complexity of a function equal its communication complexity? We examine whether any currently known techniques might be used to show a separation between the two notions. Ganor et al. [2014] recently provided such a separation in
Externí odkaz:
https://explore.openaire.eu/search/publication?articleId=doi_dedup___::41b49a2462fd86c3e97d74a680a497a6
https://doi.org/10.1145/2967605
https://doi.org/10.1145/2967605
Publikováno v:
Quantum, 2
11th Conference on the Theory of Quantum Computation, Communication and Cryptography (TQC 2016)
Quantum, Vol 2, p 72 (2018)
11th Conference on the Theory of Quantum Computation, Communication and Cryptography (TQC 2016)
Quantum, Vol 2, p 72 (2018)
The question of how large Bell inequality violations can be, for quantum distributions, has been the object of much work in the past several years. We say that a Bell inequality is normalized if its absolute value does not exceed 1 for any classical
Externí odkaz:
https://explore.openaire.eu/search/publication?articleId=doi_dedup___::df6e7203e5828644290dc30992f5546b
http://hdl.handle.net/2013/ULB-DIPOT:oai:dipot.ulb.ac.be:2013/271620
http://hdl.handle.net/2013/ULB-DIPOT:oai:dipot.ulb.ac.be:2013/271620
Autor:
Sophie Laplante, Marc Kaplan
Publikováno v:
Theoretical Computer Science. 412:2524-2535
We introduce a method based on Kolmogorov complexity to prove lower bounds on communication complexity. The intuition behind our technique is close to information theoretic methods.We use Kolmogorov complexity for three different things: first, to gi
Externí odkaz:
https://explore.openaire.eu/search/publication?articleId=doi_dedup___::4d69a1fc3e53b67bc498302f64b6b339
https://doi.org/10.1016/j.tcs.2010.10.044
https://doi.org/10.1016/j.tcs.2010.10.044
Publikováno v:
SIAM Journal on Computing. 31:887-905
We take a fresh look at CD complexity, where CDt(x) is the size of the smallest program that distinguishes x from all other strings in time t(|x|). We also look at CND complexity, a new nondeterministic variant of CD complexity, and time-bounded Kolm
Externí odkaz:
https://explore.openaire.eu/search/publication?articleId=doi_________::5e5d4727199b4972ba5bb33893e5e052
https://doi.org/10.1137/s009753979834388x
https://doi.org/10.1137/s009753979834388x
Publikováno v:
IEEE Conference on Computational Complexity
We study three types of self‐reducibility that are motivated by the theory of program verification. A set A is random‐self‐reducible if one can determine whether an input x is in A by making random queries to an A‐oracle. The distribution of
Externí odkaz:
https://explore.openaire.eu/search/publication?articleId=doi_dedup___::d239a983d13c9b9cfaf5f792ee6d0d84
https://doi.org/10.1007/s000370050009
https://doi.org/10.1007/s000370050009
Autor:
Sophie Laplante, Lance Fortnow
Publikováno v:
Information and Computation. 123:121-126
In a recent paper, Razborov ( in "Feasible Mathematics II" (P. Clote and J. Remmel, Eds.), gave a new combinatorial proof of Hastad′s switching lemma ( in "Randomness and Computation" (S. Micali, Ed.), pp. 143-170, 1989) eliminating the probabilist
Externí odkaz:
https://explore.openaire.eu/search/publication?articleId=doi_dedup___::c35908c12e7051488a1d84c8d758d7ee
https://doi.org/10.1006/inco.1995.1161
https://doi.org/10.1006/inco.1995.1161
Publikováno v:
39th International Colloquium on Automata, Languages and Programming (ICALP'12). Springer
Automata, Languages, and Programming ISBN: 9783642315930
Automata, Languages, and Programming ISBN: 9783642315930
In communication complexity, two players each have an input and they wish to compute some function of the joint inputs. This has been the object of much study and a wide variety of lower bound methods have been introduced to address the problem of sh
Externí odkaz:
https://explore.openaire.eu/search/publication?articleId=doi_dedup___::59fcfc2dcc28fe8eb995737964485bb9
http://arxiv.org/abs/1203.4155
http://arxiv.org/abs/1203.4155