Peer-reviewed Papers

• Xavier Coiteux-Roy, Francesco d'Amore, Rishikesh Gajjala, Fabian Kuhn, François Le Gall, Henrik Lievonen, Augusto Modanese, Marc-Olivier Renou, Gustav Schmid and Jukka Suomela.
  No distributed quantum advantage for approximate graph coloring.
  Proceedings of the 56th ACM Symposium on Theory of Computing (STOC 2024), to appear, 2024.
  [arXiv:2307.09444]
  
  
• François Le Gall.
  Faster Rectangular Matrix Multiplication by Combination Loss Analysis.
  Proceedings of the 2024 ACM-SIAM Symposium on Discrete Algorithms (SODA 2024), pp. 3765-3791, 2024.
  DOI: 10.1137/1.9781611977912.133
  [arXiv:2307.06535]
  
  
• François Le Gall, Masayuki Miyamoto and Harumichi Nishimura.
  Distributed Merlin-Arthur Synthesis of Quantum States and Its Applications.
  Proceedings of the 48th International Symposium on Mathematical Foundations of Computer Science (MFCS 2023), pp. 63:1-63:15, 2023.
  DOI: 10.4230/LIPIcs.MFCS.2023.63
  Also presented as a contributed talk at TQC 2023.
  [arXiv:2210.01389]
  
  
• Chris Cade, Marten Folkertsma, Sevag Gharibian, Ryu Hayakawa, François Le Gall, Tomoyuki Morimae and Jordi Weggemans.
  Improved Hardness Results for the Guided Local Hamiltonian Problem.
  Proceedings of the 50th EATCS International Colloquium on Automata, Languages and Programming (ICALP 2023), pp. 32:1-32.19, 2023.
  DOI: 10.4230/LIPIcs.ICALP.2023.32
  Also presented as a contributed talk at QIP 2023.
  This is a merge of [arXiv:2207.10250] and [arXiv:2207.10097].
  
  
• François Le Gall, Masayuki Miyamoto and Harumichi Nishimura.
  Distributed Quantum Interactive Proofs.
  Proceedings of the 40th International Symposium on Theoretical Aspects of Computer Science (STACS 2023), pp.42:1--42:21, 2023.
  DOI: 10.4230/LIPIcs.STACS.2023.42
  A preliminary (short) version appeared as a brief announcement in Proceedings of the 36th International Symposium on Distributed Computing (DISC 2022), pp. 48:1-48:3, 2022.
  DOI: 10.4230/LIPIcs.DISC.2022.48
  [arXiv:2210.01390]
  
  
• Atsuya Hasegawa and François Le Gall.
  An optimal oracle separation of classical and quantum hybrid schemes.
  Proceedings of the 33rd International Symposium on Algorithms and Computation (ISAAC 2022), pp. 6:1-6:14, 2022.
  DOI: 10.4230/LIPIcs.ISAAC.2022.6
  [arXiv:2205.04633]
  
  
• François Le Gall and Iu-iong Ng.
  Quantum Approximate Counting for Markov Chains and Application to Collision Counting.
  Quantum Information and Computation, Vol.22 No.15&16, pp. 1261-1279, 2022.
  DOI: 10.26421/QIC22.15-16-1
  Also presented as a contributed talk at AQIS 2021.
  [arXiv:2204.02552]
  
  
• François Le Gall and Daiki Suruga.
  Bounds on oblivious multiparty quantum communication complexity.
  Proceedings of the 15th Latin American Theoretical Informatics Symposium (LATIN 2022), pp. 641-657, 2022.
  DOI: 10.1007/978-3-031-20624-5_39
  [arXiv:2210.15402]
  
  
• Sevag Gharibian and François Le Gall.
  Dequantizing the Quantum Singular Value Transformation: Hardness and Applications to Quantum Chemistry and the Quantum PCP Conjecture.
  Proceedings of the 54th ACM Symposium on Theory of Computing (STOC 2022), pp. 19-32, 2022.
  DOI: 10.1145/3519935.3519991
  Also presented as a contributed talk at QIP 2022.
  [arXiv:2111.09079]
  
  
• Keren Censor-Hillel, Orr Fischer, François Le Gall, Dean Leitersdorf and Rotem Oshman.
  Quantum Distributed Algorithms for Detection of Cliques.
  Proceedings of the 13th Innovations in Theoretical Computer Science conference (ITCS 2022), pp. 35:1-35:25, 2022.
  DOI: 10.4230/LIPIcs.ITCS.2022.35
  Also presented as a contributed talk at QIP 2022.
  [proceedings]
  
  
• François Le Gall and Saeed Seddighin.
  Quantum Meets Fine-grained Complexity: Sublinear Time Quantum Algorithms for String Problems.
  Algorithmica, Vol. 85(5), pp. 1251-1286, 2023.
  DOI: 10.1007/s00453-022-01066-z
  A preliminary version appears in the Proceedings of the 13th Innovations in Theoretical Computer Science conference (ITCS 2022), pp. 97:1-97:23, 2022.
  DOI: 10.4230/LIPIcs.ITCS.2022.97
  [arXiv:2010.12122]
  
  
• Aleksandrs Belovs, Arturo Castellanos, François Le Gall, Guillaume Malod and Alexander A. Sherstov.
  Quantum Communication Complexity of Distribution Testing.
  Quantum Information and Computation, Vol.21 No.15&16, pp.1261-1273, 2021.
  DOI: 10.26421/QIC21.15-16-1
  [arXiv:2006.14870]
  
  
• François Le Gall and Masayuki Miyamoto.
  Lower Bounds for Induced Cycle Detection in Distributed Computing.
  Proceedings of the 32nd International Symposium on Algorithms and Computation (ISAAC 2021), pp. 58:1-58:19, 2021.
  DOI: 10.4230/LIPIcs.ISAAC.2021.58
  [arXiv:2110.00741]
  
  
• Atsuya Hasegawa and François Le Gall.
  Quantum Advantage with Shallow Circuits under Arbitrary Corruption.
  Proceedings of the 32nd International Symposium on Algorithms and Computation (ISAAC 2021), pp. 74:1-74:16, 2021.
  DOI: 10.4230/LIPIcs.ISAAC.2021.74
  [arXiv:2105.00603]
  
  
• Shuichi Hirahara and François Le Gall.
  Test of Quantumness with Small-Depth Quantum Circuits.
  Proceedings of the 46th International Symposium on Mathematical Foundations of Computer Science (MFCS 2021), pp. 59:1-59:15, 2021.
  DOI: 10.4230/LIPIcs.MFCS.2021.59
  Also presented as a contributed talk at QIP 2022.
  [arXiv:2105.05500]
  
  
• François Le Gall, Harumichi Nishimura and Abuzer Yakaryılmaz.
  Quantum Logarithmic Space and Post-selection.
  Proceedings of the 16th Conference on the Theory of Quantum Computation, Communication and Cryptography (TQC 2021), 10:1--10:17, 2021.
  DOI: 10.4230/LIPIcs.TQC.2021.10
  [arXiv:2105.02681]
  
  
• Keren Censor-Hillel, Yi-Jun Chang, François Le Gall and Dean Leitersdorf.
  Tight Distributed Listing of Cliques.
  Proceedings of the 32nd ACM-SIAM Symposium on Discrete Algorithms (SODA 2021), 2878-2891, 2021.
  DOI: 10.1137/1.9781611976465.171
  [arXiv:2011.07405]
  
  
• Pierre Fraigniaud, François Le Gall, Harumichi Nishimura and Ami Paz.
  Distributed Quantum Proofs for Replicated Data.
  Proceedings of the 12th Innovations in Theoretical Computer Science conference (ITCS 2021), 28:1-28:20, 2021.
  DOI: 10.4230/LIPIcs.ITCS.2021.28
  Also presented as a brief announcement at the 34th International Symposium on Distributed Computing (DISC 2020).
  Also presented as a contributed talk at QIP 2021.
  [arXiv:2002.10018]
  
  
• Sara Ayman Metwalli, François Le Gall and Rodney Van Meter.
  Finding Small and Large k-Clique Instances on a Quantum Computer.
  IEEE Transactions on Quantum Engineering, Vol. 1, 3102911, 2020.
  DOI: 10.1109/TQE.2020.3045692
  [arXiv:2008.12525]
  
  
• Keren Censor-Hillel, Orr Fischer, Tzlil Gonen, François Le Gall, Dean Leitersdorf and Rotem Oshman.
  Fast Distributed Algorithms for Girth, Cycles and Small Subgraphs.
  Proceedings of the 34th International Symposium on Distributed Computing (DISC 2020), 33:1-33:17, 2020.
  DOI: 10.4230/LIPIcs.DISC.2020.33
  [Proceedings]
  
  
• Dhawal Jethwani, François Le Gall and Sanjay K. Singh.
  Quantum-Inspired Classical Algorithms for Singular Value Transformation.
  Proceedings of the 45th International Symposium on Mathematical Foundations of Computer Science (MFCS 2020), 53:1-53:14, 2020.
  DOI: 10.4230/LIPIcs.MFCS.2020.53
  [arXiv:1910.05699]
  
  
• Masayuki Miyamoto, Masakazu Iwamura, Koichi Kise and François Le Gall.
  Quantum Speedup for the Minimum Steiner Tree Problem.
  Proceedings of the 26th International Computing and Combinatorics Conference (COCOON 2020), pp. 234-245, 2020.
  DOI: 10.1007/978-3-030-58150-3\_19
  [arXiv:1904.03581]
  
  
• Keren Censor-Hillel, François Le Gall and Dean Leitersdorf.
  On Distributed Listing of Cliques.
  Proceedings of the 39th ACM Symposium on Principles of Distributed Computing (PODC 2020), pp. 474-482, 2020.
  DOI: 10.1145/3382734.3405742
  [arXiv:2007.05316]
  
  
• Taisuke Izumi, François Le Gall and Frédéric Magniez.
  Quantum Distributed Algorithm for Triangle Finding in the CONGEST Model.
  Proceedings of the 37th International Symposium on Theoretical Aspects of Computer Science (STACS 2020), 23:1-23:13, 2020.
  DOI: 10.4230/LIPIcs.STACS.2020.23
  Also presented as a contributed talk at TQC'20.
  [arXiv:1908.11488]
  
  
• Taisuke Izumi and François Le Gall.
  Quantum Distributed Algorithm for the All-Pairs Shortest Path Problem in the CONGEST-CLIQUE Model.
  Proceedings of the 38th ACM Symposium on Principles of Distributed Computing (PODC 2019), pp. 84-93, 2019.
  DOI: 10.1145/3293611.3331628
  [arXiv:1906.02456]
  
  
• François Le Gall.
  Average-Case Quantum Advantage with Shallow Circuits.
  Proceedings of the 34th Computational Complexity Conference (CCC 2019), 21:1-21:20, 2019.
  DOI: 10.4230/LIPIcs.CCC.2019.21
  [arXiv:1810.12792]
  
  
• Hirotada Kobayashi, François Le Gall and Harumichi Nishimura.
  Generalized Quantum Arthur-Merlin Games.
  SIAM Journal on Computing, Vol. 48 No. 3, pp. 865-902, 2019.
  DOI: 10.1137/17M1160173
  A preliminary version appeared in the Proceedings of the 30th Computational Complexity Conference (CCC 2015), pp. 488-511, 2015.
  [arXiv:1312.4673]
  
  
• François Le Gall, Ansis Rosmanis and Harumichi Nishimura.
  Quantum Advantage for the LOCAL Model in Distributed Computing.
  Proceedings of the 36th International Symposium on Theoretical Aspects of Computer Science (STACS 2019), 49:1-49:14, 2019.
  DOI: 10.4230/LIPIcs.STACS.2019.49
  Also presented as a contributed talk at TQC'19.
  [arXiv:1810.10838]
  
  
• François Le Gall, Tomoyuki Morimae, Harumichi Nishimura and Yuki Takeuchi.
  Interactive Proofs with Polynomial-Time Quantum Prover for Computing the Order of Solvable Groups.
  Proceedings of the 43rd International Symposium on Mathematical Foundations of Computer Science (MFCS 2018), 26:1-26:13, 2018.
  DOI: 10.4230/LIPIcs.MFCS.2018.26
  [arXiv:1805.03385]
  
  
• François Le Gall and Frédéric Magniez.
  Sublinear-Time Quantum Computation of the Diameter in CONGEST Networks.
  Proceedings of the 37th ACM Symposium on Principles of Distributed Computing (PODC 2018), pp. 337-346, 2018.
  DOI: 10.1145/3212734.3212744
  Also presented as a contributed talk at QIP'19.
  [arXiv:1804.02917]
  
  
• François Le Gall and Florent Urrutia.
  Improved Rectangular Matrix Multiplication using Powers of the Coppersmith-Winograd Tensor.
  Proceedings of the 29th ACM-SIAM Symposium on Discrete Algorithms (SODA 2018), pp. 1029-1046, 2018.
  DOI: 10.1137/1.9781611975031.67
  [arXiv:1708.05622]
  
  
• Dean Doron, François Le Gall and Amnon Ta-Shma.
  Probabilistic Logarithmic-Space Algorithms for Laplacian Solvers.
  Proceedings of the 21st International Workshop on Randomization and Computation (RANDOM 2017), pp. 41:1-41:20, 2017.
  DOI: 10.4230/LIPIcs.APPROX-RANDOM.2017.41
  [ECCC TR17-036]
  
  
• Akinori Kawachi, Kenichi Kawano, François Le Gall and Suguru Tamaki.
  Quantum Query Complexity of Unitary Operator Discrimination.
  IEICE Transactions 102-D(3): 483-491 (2019).
  DOI: 10.1587/transinf.2018FCP0012
  A preliminary version appeared in the Proceedings of the 23rd Annual International Computing and Combinatorics Conference (COCOON 2017), pp. 309-320, 2017.
  
  
• Taisuke Izumi and François Le Gall.
  Triangle Finding and Listing in CONGEST Networks.
  Proceedings of the 36th ACM Symposium on Principles of Distributed Computing (PODC 2017), pp. 381-389, 2017.
  DOI: 10.1145/3087801.3087811
  [arXiv:1705.09061]
  
  
• François Le Gall and Shogo Nakajima.
  Multiparty Quantum Communication Complexity of Triangle Finding.
  Proceedings of the Conference on the Theory of Quantum Computation, Communication and Cryptography (TQC 2017), pp. 6:1-6:11, 2018.
  DOI: 10.4230/LIPIcs.TQC.2017.6
  [Proceedings]
  
  
• Tomoyuki Morimae, Harumichi Nishimura and François Le Gall.
  Modified Group Non-Membership is in AWPP.
  Quantum Information and Computation, Vol. 17 No. 3&4, pp. 242-250, 2017.
  DOI: 10.26421/QIC17.3-4-3
  [arXiv:1602.06073]
  
  
• François Le Gall and Harumichi Nishimura.
  Quantum Algorithms for Matrix Products over Semirings.
  Chicago Journal of Theoretical Computer Science, Vol. 2017, Article 1, 2017.
  DOI: 10.4086/cjtcs.2017.001
  A preliminary version appeared in the Proceedings of the 14th Scandinavian Symposium and Workshops on Algorithm Theory (SWAT 2014), pp. 331-343, 2014.
  [arXiv:1310.3898]
  
  
• François Le Gall and Shogo Nakajima.
  Quantum Algorithm for Triangle Finding in Sparse Graphs.
  Algorithmica (Special issue on ISAAC 2015), Vol. 79 No. 3, pp. 941-959, 2017.
  DOI: 10.1007/s00453-016-0267-z
  A preliminary version appeared in the Proceedings of the 26th International Symposium on Algorithms and Computation (ISAAC 2015), pp. 590-600, 2015.
  [arXiv:1507.06878]
  
  
• François Le Gall.
  Further Algebraic Algorithms in the Congested Clique Model and Applications to Graph-Theoretic Problems.
  Proceedings of the 30th International Symposium on Distributed Computing (DISC 2016), pp. 57-70, 2016.
  DOI: 10.1007/978-3-662-53426-7\_5
  [arXiv:1608.02674]
  
  
• Stacey Jeffery and François Le Gall.
  Quantum Communication Complexity of Distributed Set Joins.
  Proceedings of the 41st International Symposium on Mathematical Foundations of Computer Science (MFCS 2016), Article No. 54, 2016.
  DOI: 10.4230/LIPIcs.MFCS.2016.54
  Also presented as a contributed talk at TQC'16.
  [arXiv:1608.06617]
  
  
• Iordanis Kerenidis, Mathieu Laurière, François Le Gall and Mathys Rennela.
  Information cost of Quantum Communication Complexity.
  Quantum Information and Computation, Vol. 16 No. 3&4, pp. 181-196, 2016.
  DOI: 10.26421/QIC16.3-4-1
  [arXiv:1409.8488]
  
  
• Stacey Jeffery, Robin Kothari, François Le Gall and Frédéric Magniez.
  Improving Quantum Query Complexity of Boolean Matrix Multiplication Using Graph Collision.
  Algorithmica, Vol. 76 No. 1, pp. 1-16, 2016.
  DOI: 10.1007/s00453-015-9985-x
  Note: the results in this paper supersede those of [Le Gall, ISAAC'12] and [Le Gall, SODA'12] listed below.
  
  
• Andris Ambainis, Yuval Filmus and François Le Gall.
  Fast Matrix Multiplication: Limitations of the Coppersmith-Winograd Method.
  Proceedings of the 47th ACM Symposium on Theory of Computing (STOC 2015), pp. 585-593, 2015.
  DOI: 10.1145/2746539.2746554
  [arXiv:1411.5414]
  
  
• Hirotada Kobayashi, François Le Gall and Harumichi Nishimura.
  Stronger Methods of Making Quantum Interactive Proofs Perfectly Complete.
  SIAM Journal on Computing, Vol. 44(2), pp. 243-289, 2015.
  DOI: 10.1137/140971944
  A preliminary version appeared in the Proceedings of the 4th ACM Innovations in Theoretical Computer Science conference (ITCS 2013), pp. 329-352, 2013.
  Also presented at QIP 2013 as a contributed talk.
  [arXiv:1210.1290]
  
  
• François Le Gall.
  Improved Quantum Algorithm for Triangle Finding via Combinatorial Arguments.
  Proceedings of the 55th Annual IEEE Symposium on Foundations of Computer Science (FOCS 2014), pp. 216-225, 2014.
  DOI: 10.1109/FOCS.2014.31
  Also presented at QIP 2015 as a contributed talk.
  [arXiv:1407.0085]
  
  
• François Le Gall.
  Powers of Tensors and Fast Matrix Multiplication.
  Proceedings of the 39th International Symposium on Symbolic and Algebraic Computation (ISSAC 2014), pp. 296-303, 2014.
  (Received the distinguished paper award)
  DOI: 10.1145/2608628.2627493
  [arXiv:1401.7714]
  
  
• François Le Gall, Harumichi Nishimura and Seiichiro Tani.
  Quantum Algorithms for Finding Constant-sized Sub-hypergraphs.
  Theoretical Computer Science, Vol. 609 No. 3 (Special issue on COCOON 2014), pp. 569-582, 2016.
  DOI: 10.1007/978-3-319-08783-2\_37
  A preliminary version appeared in the Proceedings of the 20th Annual International Computing and Combinatorics Conference (COCOON 2014), pp. 429-440, 2014.
  [arXiv:1310.4127]
  
  
• François Le Gall and Yuichi Yoshida.
  Property Testing for Cyclic Groups and Beyond.
  Journal of Combinatorial Optimization, Vol. 26 No. 4 (Special issue on COCOON 2011), pp. 636-654, 2013.
  DOI: 10.1007/s10878-011-9445-8
  A preliminary version appeared in the Proceedings of the 17th Annual International Computing and Combinatorics Conference (COCOON 2011), pp. 432-443, 2011.
  [arXiv:1105.1842]
  
  
• François Le Gall.
  Quantum Weakly Nondeterministic Communication Complexity.
  Theoretical Computer Science, Vol. 486, pp. 43-49, 2013. (Special issue devoted to the theory of quantum communication complexity and non-locality)
  DOI: 10.1016/j.tcs.2012.12.015
  A preliminary version appeared in the Proceedings of the 31st International Symposium of Mathematical Foundations of Computer Science (MFCS 2006), pp. 658-669, 2006.
  [quant-ph/0511025]
  
  
• François Le Gall.
  A Time-Efficient Output-Sensitive Quantum Algorithms for Boolean Matrix Multiplication.
  Proceedings of the 23rd International Symposium on Algorithms and Computation (ISAAC 2012), LNCS 7676, pp. 639-648, 2012.
  DOI: 10.1007/978-3-642-35261-4\_66
  [arXiv:1201.6174]
  
  
• Takahiko Satoh, François Le Gall and Hiroshi Imai.
  Quantum network coding for quantum repeaters.
  Physical Review A, Vol. 83, 032331, 2012.
  DOI: 10.1103/PhysRevA.86.032331
  [arXiv:1205.3745]
  
  
• François Le Gall.
  Faster Algorithms for Rectangular Matrix Multiplication.
  Proceedings of the 53rd Annual IEEE Symposium on Foundations of Computer Science (FOCS 2012), pp. 514-523, 2012.
  DOI: 10.1109/FOCS.2012.80
  [arXiv:1204.1111]
  
  
• François Le Gall.
  Quantum Private Information Retrieval with Sublinear Communication Complexity.
  Theory of Computing, Vol. 8, pp. 369-374, 2012.
  DOI: 10.4086/toc.2012.v008a016
  [arXiv:1107.5881]
  
  
• Richard Cleve, Kazuo Iwama, François Le Gall, Harumichi Nishimura, Seiichiro Tani, Junichi Teruyama and Shigeru Yamashita.
  Reconstructing Strings from Substrings with Quantum Queries.
  Proceedings of the 13th Scandinavian Symposium and Workshops on Algorithm Theory (SWAT 2012), pp. 388-397, 2012.
  DOI: 10.1007/978-3-642-31155-0\_34
  [arXiv:1204.4691]
  
  
• François Le Gall, Shota Nakagawa and Harumichi Nishimura.
  On QMA Protocols with Two Short Quantum Proofs.
  Quantum Information and Computation, Vol.12 No.7&8, pp. 589-600, 2012.
  DOI: 10.26421/QIC12.7-8-4
  [arXiv:1108.4306]
  
  
• Gábor Ivanyos, François Le Gall and Yuichi Yoshida.
  On the distance between non-isomorphic groups.
  European Journal of Combinatorics, Vol. 33 No. 4, pp. 474-476, 2012.
  DOI: 10.1016/j.ejc.2011.10.009
  [arXiv:1107.0133]
  
  
• François Le Gall.
  Improved Output-Sensitive Quantum Algorithms for Boolean Matrix Multiplication.
  Proceedings of the 23rd Annual ACM-SIAM Symposium on Discrete Algorithms (SODA 2012), pp. 1464-1476, 2012.
  DOI: 10.1137/1.9781611973099.116
  Also presented at QIP 2012 as a contributed talk.
  [Proceedings]
  
  
• Scott Aaronson, François Le Gall, Alexander Russell and Seiichiro Tani.
  The One-Way Communication Complexity of Subgroup Membership.
  Chicago Journal of Theoretical Computer Science, Vol. 2011, Article 6, 2011.
  DOI: 10.4086/cjtcs.2011.006
  [arXiv:0902.3175]
  
  
• Junya Fukawa, Hiroshi Imai and François Le Gall.
  Quantum Coloring Games via Symmetric SAT Games.
  Presented as a long talk at the 11th Asian Quantum Information Science Conference (AQIS 2011).
  
  
• Hirotada Kobayashi, François Le Gall, Harumichi Nishimura and Martin Roetteler.
  Constructing Quantum Network Coding Schemes from Classical Nonlinear Protocols.
  Proceedings of the 2011 IEEE International Symposium on Information Theory (ISIT 2011), pp. 109-113, 2011.
  DOI: 10.1109/ISIT.2011.6033701
  Also presented at QIP 2011 as a contributed talk.
  [arXiv:1012.4583]
  
  
• Min-Hsiu Hsieh and François Le Gall.
  NP-hardness of Decoding Quantum Error Correction Codes.
  Physical Review A, Vol. 83, 052331, 2011.
  DOI: 10.1103/PhysRevA.83.052331
  [arXiv:1009.1319]
  
  
• Yoshifumi Inui and François Le Gall.
  Quantum Property Testing of Group Solvability.
  Algorithmica, Vol. 59, No. 1 (Special issue on LATIN 2008), pp. 35-47, 2011.
  DOI: 10.1007/s00453-009-9338-8
  A preliminary version appeared in the Proceedings of the 8th Latin American Theoretical Informatics Conference (LATIN 2008), pp. 772-783, 2008.
  [arXiv:0712.3829]
  
  
• Hirotada Kobayashi, François Le Gall, Harumichi Nishimura and Martin Roetteler.
  Perfect Quantum Network Communication Protocol Based on Classical Network Coding.
  Proceedings of the 2010 IEEE International Symposium on Information Theory (ISIT 2010), pp. 2686 - 2690, 2010.
  DOI: 10.1109/ISIT.2010.5513644
  [arXiv:0902.1299]
  
  
• François Le Gall.
  An Efficient Quantum Algorithm for some Instances of the Group Isomorphism Problem.
  Proceedings of the 27th International Symposium on Theoretical Aspects of Computer Science (STACS 2010), pp. 549-560, 2010.
  DOI: 10.4230/LIPIcs.STACS.2010.2484
  [arXiv:1001.0608] (full version)
  
  
• Andris Ambainis, Andrew M. Childs, François Le Gall and Seiichiro Tani.
  The quantum query complexity of certification.
  Quantum Information and Computation, Vol.10 No.3&4, pp. 181-189, 2010.
  DOI: 10.26421/QIC10.3-4-1
  [arXiv:0903.1291]
  
  
• Hirotada Kobayashi, François Le Gall, Harumichi Nishimura and Martin Roetteler.
  General Scheme for Perfect Quantum Network Coding with Free Classical Communication.
  Proceedings of the 36th International Colloquium on Automata, Languages and Programming (ICALP 2009), pp. 622-633, 2009.
  DOI: 10.1007/978-3-642-02927-1\_52
  [arXiv:0908.1457]
  
  
• François Le Gall.
  Efficient Isomorphism Testing for a Class of Group Extensions.
  Proceedings of the 26th International Symposium on Theoretical Aspects of Computer Science (STACS 2009), pp. 625-636, 2009.
  DOI: 10.4230/LIPIcs.STACS.2009.1830
  [arXiv:0812.2298] (full version)
  
  
• Yoshifumi Inui and François Le Gall.
  Efficient Quantum Algorithms for the Hidden Subgroup Problem over a Class of Semi-direct Product Groups.
  Quantum Information and Computation, Vol.7 No.5&6, pp. 559-570, 2007.
  DOI: 10.26421/QIC7.5-6-9
  [quant-ph/0412033]
  
  
• François Le Gall.
  Exponential Separation of Quantum and Classical Online Space Complexity.
  Theory of Computing Systems, Vol. 45 No. 2 (Special issue on SPAA 2006), pp. 188-202, 2009.
  DOI: 10.1007/s00224-007-9097-3
  A preliminary version appeared in the Proceedings of the 18th Annual ACM Symposium on Parallelism in Algorithms and Architectures (SPAA 2006), pp. 67-73, 2006.
  Also presented at QIP 2007 as a long talk.
  [quant-ph/0606066]