Links


Photo by Collège de France

External sources

Recent

Books
2021
[2021]Algorithmes quantiques : quand la physique quantique défie la thèse de Church-Turing (), Collège de France / Fayard, , 80 pages. [url]
Journal articles
2020
[2020]Extended Learning Graphs for Triangle Finding (, and ), In Algorithmica, volume 82, . [pdf] [doi]
Conference papers
2021
[2021]Quantum Time-Space Tradeoff for Finding Multiple Collision Pairs ( and ), In Proceedings of 16th Conference on the Theory of Quantum Computation, Communication and Cryptography, , TQC Outstanding Paper Prize. [pdf] [doi]
2020
[2020]Quantum Distributed Complexity of Set Disjointness on a Line ( and ), In Proceedings of 47th International Colloquium on Automata, Languages and Programming, , 82:1–82:18. [pdf] [doi]
[2020]Quantum Distributed Algorithm for Triangle Finding in the CONGEST Model (, and ), In Proceedings of 37th International Symposium on Theoretical Aspects of Computer Science, , Also presented at TQC'20. [pdf] [doi]

All

Books
2021
[2021]Algorithmes quantiques : quand la physique quantique défie la thèse de Church-Turing (), Collège de France / Fayard, , 80 pages. [url]
Journal articles
2023
[2023]Quantum Time-Space Tradeoff for Finding Multiple Collision Pairs ( and ), In ACM Transactions on Computation Theory, volume 15, . [pdf] [doi]
2022
[2022]Quantum Distributed Complexity of Set Disjointness on a Line ( and ), In ACM Transactions on Computation Theory, volume 14, . [pdf] [doi]
2020
[2020]Extended Learning Graphs for Triangle Finding (, and ), In Algorithmica, volume 82, . [pdf] [doi]
2018
[2018]Streaming Communication Protocols (, and ), In ACM Transactions on Computation Theory, volume 10, . [pdf] [doi]
2017
[2017]Improved quantum query algorithms for triangle finding and associativity testing (, and ), In Algorithmica, volume 77, . [pdf] [doi]
[2017]Optimal parallel quantum query algorithms (, and ), In Algorithmica, volume 79, . [pdf] [doi]
2016
[2016]Improved bounds for the randomized decision tree complexity of recursive majority (, , , , and ), In Random Structures & Algorithms, volume 48, . [pdf] [doi]
[2016]Quantum walks can find a marked element on any graph (, , and ), In Algorithmica, volume 74, . [pdf] [doi]
[2016]Improving Quantum Query Complexity of Boolean Matrix Multiplication Using Graph Collision (, , and ), In Algorithmica, volume 76, . [pdf] [doi]
2014
[2014]Recognizing well-parenthesized expressions in the streaming model (, and ), In SIAM Journal on Computing, volume 43, . [pdf]
[2014]Hidden translation and orbit coset in quantum computing (, , , and ), In SIAM Journal on Computing, volume 43, . [pdf]
2013
[2013]Validating XML documents in the streaming model with external memory ( and ), In ACM Transactions on Database Systems, volume 38, , Special issue of ICDT'12. [pdf]
2012
[2012]On the hitting times of quantum versus random walks (, , and ), In Algorithmica, volume 63, . [pdf]
[2012]A learning graph based quantum query algorithm for finding constant-size subgraphs (, and ), In Chicago Journal of Theoretical Computer Science, . [pdf]
2011
[2011]Search via quantum walk (, , and ), In SIAM Journal on Computing, volume 40, . [pdf]
2010
[2010]Strong no-go theorem for gaussian quantum bit commitment (, , and ), In Physical Review A, volume 81, . [pdf]
[2010]Approximate satisfiability and equivalence (, and ), In SIAM Journal on Computing, volume 39, . [pdf]
2009
[2009]Quantum testers for hidden group properties (, , and ), In Fundamenta Matematicae, volume 91, , Special issue on Machines on Computations and Universality. [pdf]
2008
[2008]Lower bounds for randomized and quantum query complexity using Kolmogorov arguments ( and ), In SIAM Journal on Computing, volume 38, . [pdf]
2007
[2007]Quantum algorithms for the triangle problem (, and ), In SIAM Journal on Computing, volume 37, . [pdf]
[2007]Property testing of regular tree languages ( and ), In Algorithmica, volume 49, . [pdf]
[2007]Quantum complexity of testing group commutativity ( and ), In Algorithmica, volume 48, . [pdf]
[2007]Probabilistic abstraction for model checking: An approach based on property testing (, , , and ), In ACM Transactions on Computational Logic, volume 8, . [pdf]
[2007]Self-testing of universal and fault-tolerant sets of quantum gates (, , and ), In SIAM Journal on Computing, volume 37, . [pdf]
2005
[2005]Multi-linearity self-testing with relative error (), In Theory of Computing Systems, volume 38, . [pdf]
[2005]Quantum algorithms for element distinctness (, , , , , and ), In SIAM Journal on Computing, volume 34, . [pdf]
2003
[2003]Approximate testing with error relative to input size (, and ), In Journal of Computer and System Sciences, volume 66, . [pdf]
[2003]Efficient quantum algorithms for some instances of the non-Abelian hidden subgroup problem (, and ), In International Journal of Foundations of Computer Science, volume 14, . [pdf]
Conference papers
2021
[2021]Quantum Time-Space Tradeoff for Finding Multiple Collision Pairs ( and ), In Proceedings of 16th Conference on the Theory of Quantum Computation, Communication and Cryptography, , TQC Outstanding Paper Prize. [pdf] [doi]
2020
[2020]Quantum Distributed Complexity of Set Disjointness on a Line ( and ), In Proceedings of 47th International Colloquium on Automata, Languages and Programming, , 82:1–82:18. [pdf] [doi]
[2020]Quantum Distributed Algorithm for Triangle Finding in the CONGEST Model (, and ), In Proceedings of 37th International Symposium on Theoretical Aspects of Computer Science, , Also presented at TQC'20. [pdf] [doi]
2019
[2019]Quantum Chebyshev's Inequality and Applications ( and ), In Proceedings of 46th International Colloquium on Automata, Languages and Programming, . [pdf] [doi]
2018
[2018]Sublinear-Time Quantum Computation of the Diameter in CONGEST Networks ( and ), In Proceedings of 37th ACM Symposium on Principles of Distributed Computing, , Also presented at QIP'19 as a contributed talk. [pdf] [doi]
[2018]Improved bounds for testing Dyck languages (, and ), In Proceedings of 29th ACM-SIAM Symposium on Discrete Algorithms, . [pdf] [doi]
2017
[2017]Extended Learning Graphs for Triangle Finding (, and ), In Proceedings of 34th International Symposium on Theoretical Aspects of Computer Science, . [pdf] [doi]
[2017]Streaming Communication Protocols (, and ), In Proceedings of 44th International Colloquium on Automata, Languages, and Programming, . [pdf] [doi]
2016
[2016]Stable Matching with Evolving Preferences (, and ), In Proceedings of 20th International Workshop on Randomization and Computation, . [pdf] [doi]
[2016]Streaming Property Testing of Visibly Pushdown Languages (, , and ), In Proceedings of 24rd European Symposium on Algorithms, . [pdf] [doi]
2014
[2014]Optimal parallel quantum query algorithms (, and ), In Proceedings of 22nd European Symposium on Algorithms, . [pdf]
[2014]Unidirectional Input/Output Streaming Complexity of Reversal and Sorting (, and ), In Proceedings of 18th International Workshop on Randomization and Computation, . [pdf]
2013
[2013]Improved quantum query algorithms for triangle finding and associativity testing (, and ), In Proceedings of 24th ACM-SIAM Symposium on Discrete Algorithms, , Also presented at QIP'13 as a contributed talk. [pdf]
[2013]Nested quantum walks with quantum data structures (, and ), In Proceedings of 24th ACM-SIAM Symposium on Discrete Algorithms, , Also presented at QIP'14 as a contributed talk. [pdf]
[2013]Streaming complexity of checking priority queues ( and ), In Proceedings of 30th Symposium on Theoretical Aspects of Computer Science, . [pdf]
[2013]Time-Efficient Quantum Walks for 3-Distinctness (, , , and ), In Proceedings of 40th International Colloquium on Automata, Languages and Programming, , Also presented at QIP'14 as a contributed talk. [pdf]
2012
[2012]Maximum matching in semi-streaming with few passes (, and ), In Proceedings of 15th International Workshop on Approximation Algorithms for Combinatorial Optimization Problems, , Full version. [pdf]
[2012]Validating XML documents in the streaming model with external memory ( and ), In Proceedings of 15th International Conference on Database Theory, , Best Newcomer Paper. [pdf]
[2012]Improving quantum query complexity of boolean matrix multiplication using graph collision (, and ), In Proceedings of 39th International Colloquium on Automata, Languages and Programming, . [pdf]
2011
[2011]The complexity of approximate Nash equilibrium in congestion games with negative delays (, , and ), In Proceedings of 7th Workshop on Internet & Network Economics, . [pdf]
[2011]Improved bounds for the randomized decision tree complexity of recursive majority (, , and ), In Proceedings of 38th International Colloquium on Automata, Languages and Programming, . [pdf]
2010
[2010]Recognizing well-parenthesized expressions in the streaming model (, and ), In Proceedings of 42nd ACM Symposium on Theory of Computing, . [pdf]
[2010]Finding is as easy as detecting for quantum walks (, , and ), In Proceedings of 37th International Colloquium on Automata, Languages and Programming, , Also presented at QIP'11 as a featured talk. [pdf]
2009
[2009]On the hitting times of quantum versus random walks (, , and ), In Proceedings of 20th ACM-SIAM Symposium on Discrete Algorithms, . [pdf]
2007
[2007]Search via quantum walk (, , and ), In Proceedings of 39th ACM Symposium on Theory of Computing, , Also presented at QIP'07 as a contributed talk. [pdf]
2006
[2006]Self-testing of quantum circuits (, , and ), In Proceedings of 33rd International Colloquium on Automata, Languages and Programming, , Also presented at QIP'06 as a contributed talk. [pdf]
[2006]Approximate satisfiability and equivalence (, and ), In Proceedings of 21st IEEE Symposium on Logic in Computer Science, . [pdf]
2005
[2005]Quantum algorithms for the triangle problem (, and ), In Proceedings of 16th ACM-SIAM Symposium on Discrete Algorithms, , Also presented at QIP'04 as an invited talk. [pdf]
[2005]Quantum complexity of testing group commutativity ( and ), In Proceedings of 32nd International Colloquium on Automata, Languages and Programming, . [pdf]
2004
[2004]Property testing of regular tree languages ( and ), In Proceedings of 31st International Colloquium on Automata, Languages and Programming, . [pdf]
[2004]Lower bounds for randomized and quantum query complexity using Kolmogorov arguments ( and ), In Proceedings of 19th IEEE Conference on Computational Complexity, . [pdf]
2003
[2003]Quantum testers for hidden group properties (, , and ), In Proceedings of the 28th International Symposium on Mathematical Foundations of Computer Science, . [pdf]
[2003]Hidden translation and orbit coset in quantum computing (, , , and ), In Proceedings of 35th ACM Symposium on Theory of Computing, , Also presented at QIP'03 as an invited talk. [pdf]
2002
[2002]Probabilistic abstraction for model checking: An approach based on property testing (, , , and ), In Proceedings of 17th IEEE Symposium on Logic in Computer Science, . [pdf]
2001
[2001]Efficient quantum algorithms for some instances of the non-Abelian hidden subgroup problem (, and ), In Proceedings of 13th ACM Symposium on Parallelism in Algorithms and Architectures, . [pdf]
[2001]Quantum algorithms for element distinctness (, , , , , and ), In Proceedings of 15th IEEE Conference on Computational Complexity, . [pdf]
2000
[2000]Multi-linearity self-testing with relative error (), In Proceedings of 17th Symposium on Theoretical Aspects of Computer Science, . [pdf]
[2000]Self-testing of universal and fault-tolerant sets of quantum gates (, , and ), In Proceedings of 32nd ACM Symposium on Theory of Computing, . [pdf]
1999
[1999]Approximate testing with relative error (, and ), In Proceedings of 31st ACM Symposium on Theory of Computing, . [pdf]
Other publications
2024
[2024]Even-Cycle Detection in the Randomized and Quantum CONGEST Model (, , and ), Technical report arXiv:2402.12018, arXiv.org, . [pdf]
2015
[2015]La physique quantique réinvente les algorithmes ( and ), Chapter in La Recherche, volume 501, .
2014
[2014]Complexité de communication (, and ), Chapter in Informatique Mathématique - Une photographie en 2014, Presses Universitaires de Perpignan, . [pdf]
2013
[2013]Some approximations in Model Checking and Testing (, , and ), Technical report arXiv:1304.5199, arXiv.org, , Survey. [pdf]
2009
[2009]Special issue in Quantum Computation, Algorithmica 55(3) ( and ), Springer, .
2007
[2007]Vérification approchée - Calcul quantique (), Habilitation, Université Paris-Sud, France, , Record number 1018. [pdf]
2006
[2006]Comment calculer quantique (, and ), Chapter in La Recherche, volume 398, . [pdf]
2000
[2000]Auto-test pour les calculs approché et quantique (), PhD thesis, Université Paris-Sud, France, , Record number 6076. [pdf]
[2000]Exact and approximate testing/correcting of algebraic functions: A survey (, and ), Chapter in Proceedings of 1st Summer School on Theoretical Aspects of Computer Science, , Also ECCC Report TR01-014. [pdf]