Peerreviewed Papers

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), to appear, 2022.
[arXiv:2205.04633]

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), to appear, 2022.

François Le Gall, Masayuki Miyamoto and Harumichi Nishimura.
Brief Announcement: Distributed Quantum Interactive Proofs.
Proceedings of the 36th International Symposium on Distributed Computing (DISC 2022), to appear, 2022.

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. 1932, 2022.
DOI: 10.1145/3519935.3519991
Also accepted as a contributed talk at QIP 2022.
[arXiv:2111.09079]

Keren CensorHillel, 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:135:25, 2022.
DOI: 10.4230/LIPIcs.ITCS.2022.35
Also accepted as a contributed talk at QIP 2022.
[proceedings]

François Le Gall and Saeed Seddighin.
Quantum Meets Finegrained Complexity: Sublinear Time Quantum Algorithms for String Problems.
Proceedings of the 13th Innovations in Theoretical Computer Science conference (ITCS 2022), pp. 97:197: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.12611273, 2021.
DOI: 10.26421/QIC21.15161
[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:158: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:174:16, 2021.
DOI: 10.4230/LIPIcs.ISAAC.2021.74
[arXiv:2105.00603]

Shuichi Hirahara and François Le Gall.
Test of Quantumness with SmallDepth Quantum Circuits.
Proceedings of the 46th International Symposium on Mathematical Foundations of Computer Science (MFCS 2021), pp. 59:159:15, 2021.
DOI: 10.4230/LIPIcs.MFCS.2021.59
Also accepted as a contributed talk at QIP 2022.
[arXiv:2105.05500]

François Le Gall, Harumichi Nishimura and Abuzer Yakaryılmaz.
Quantum Logarithmic Space and Postselection.
Proceedings of the 16th Conference on the Theory of Quantum Computation, Communication and Cryptography (TQC 2021), 10:110:17, 2021.
DOI: 10.4230/LIPIcs.TQC.2021.10
[arXiv:2105.02681]

Keren CensorHillel, YiJun Chang, François Le Gall and Dean Leitersdorf.
Tight Distributed Listing of Cliques.
Proceedings of the 32nd ACMSIAM Symposium on Discrete Algorithms (SODA 2021), 28782891, 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:128: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 kClique Instances on a Quantum Computer.
IEEE Transactions on Quantum Engineering, Vol. 1, 3102911, 2020.
DOI: 10.1109/TQE.2020.3045692
[arXiv:2008.12525]

Keren CensorHillel, 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:133:17, 2020.
DOI: 10.4230/LIPIcs.DISC.2020.33
[Proceedings]

Dhawal Jethwani, François Le Gall and Sanjay K. Singh.
QuantumInspired Classical Algorithms for Singular Value Transformation.
Proceedings of the 45th International Symposium on Mathematical Foundations of Computer Science (MFCS 2020), 53:153: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. 234245, 2020.
DOI: 10.1007/9783030581503\_19
[arXiv:1904.03581]

Keren CensorHillel, 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. 474482, 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:123:13, 2020.
DOI: 10.4230/LIPIcs.STACS.2020.23
Also accepted as a contributed talk at TQC'20.
[arXiv:1908.11488]

Taisuke Izumi and François Le Gall.
Quantum Distributed Algorithm for the AllPairs Shortest Path Problem
in the CONGESTCLIQUE Model.
Proceedings of the 38th ACM Symposium on Principles of Distributed Computing (PODC 2019), pp. 8493, 2019.
DOI: 10.1145/3293611.3331628
[arXiv:1906.02456]

François Le Gall.
AverageCase Quantum Advantage with Shallow Circuits.
Proceedings of the 34th Computational Complexity Conference (CCC 2019), 21:121:20, 2019.
DOI: 10.4230/LIPIcs.CCC.2019.21
[arXiv:1810.12792]

Hirotada Kobayashi, François Le Gall and Harumichi Nishimura.
Generalized Quantum ArthurMerlin Games.
SIAM Journal on Computing, Vol. 48 No. 3, pp. 865902, 2019.
DOI: 10.1137/17M1160173
A preliminary version appeared in the
Proceedings of the 30th Computational Complexity Conference (CCC 2015), pp. 488511, 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:149:14, 2019.
DOI: 10.4230/LIPIcs.STACS.2019.49
Also accepted as a contributed talk at TQC'19.
[arXiv:1810.10838]

François Le Gall, Tomoyuki Morimae, Harumichi Nishimura and Yuki Takeuchi.
Interactive Proofs with PolynomialTime Quantum Prover for Computing the Order of Solvable Groups.
Proceedings of the 43rd International Symposium on Mathematical Foundations of Computer Science (MFCS 2018), 26:126:13, 2018.
DOI: 10.4230/LIPIcs.MFCS.2018.26
[arXiv:1805.03385]

François Le Gall and Frédéric Magniez.
SublinearTime Quantum Computation of the Diameter in CONGEST Networks.
Proceedings of the 37th ACM Symposium on Principles of Distributed Computing (PODC 2018), pp. 337346, 2018.
DOI: 10.1145/3212734.3212744
Also accepted 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 CoppersmithWinograd Tensor.
Proceedings of the 29th ACMSIAM Symposium on Discrete Algorithms (SODA 2018), pp. 10291046, 2018.
DOI: 10.1137/1.9781611975031.67
[arXiv:1708.05622]

Dean Doron, François Le Gall and Amnon TaShma.
Probabilistic LogarithmicSpace Algorithms for Laplacian Solvers.
Proceedings of the 21st International Workshop on Randomization and Computation (RANDOM 2017), pp. 41:141:20, 2017.
DOI: 10.4230/LIPIcs.APPROXRANDOM.2017.41
[ECCC TR17036]

Akinori Kawachi, Kenichi Kawano, François Le Gall and Suguru Tamaki.
Quantum Query Complexity of Unitary Operator Discrimination.
IEICE Transactions 102D(3): 483491 (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. 309320, 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. 381389, 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:16:11, 2018.
DOI: 10.4230/LIPIcs.TQC.2017.6
[Proceedings]

Tomoyuki Morimae, Harumichi Nishimura and François Le Gall.
Modified Group NonMembership is in AWPP.
Quantum Information and Computation, Vol. 17 No. 3&4, pp. 242250, 2017.
DOI: 10.26421/QIC17.343
[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. 331343, 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. 941959, 2017.
DOI: 10.1007/s004530160267z
A preliminary version appeared in the Proceedings of the 26th International Symposium on Algorithms and Computation (ISAAC 2015), pp. 590600, 2015.
[arXiv:1507.06878]

François Le Gall.
Further Algebraic Algorithms in the Congested Clique Model and Applications to GraphTheoretic Problems.
Proceedings of the 30th International Symposium on Distributed Computing (DISC 2016), pp. 5770, 2016.
DOI: 10.1007/9783662534267\_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 accepted 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. 181196, 2016.
DOI: 10.26421/QIC16.341
[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. 116, 2016.
DOI: 10.1007/s004530159985x
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 CoppersmithWinograd Method.
Proceedings of the 47th ACM Symposium on Theory of Computing (STOC 2015), pp. 585593, 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. 243289, 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. 329352, 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. 216225, 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. 296303, 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 Constantsized Subhypergraphs.
Theoretical Computer Science, Vol. 609 No. 3 (Special issue on COCOON 2014), pp. 569582, 2016.
DOI: 10.1007/9783319087832\_37
A preliminary version appeared in the
Proceedings of the 20th Annual International Computing and Combinatorics Conference (COCOON 2014), pp. 429440, 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. 636654, 2013.
DOI: 10.1007/s1087801194458
A preliminary version appeared in the Proceedings of the 17th Annual International Computing and Combinatorics Conference (COCOON 2011), pp. 432443, 2011.
[arXiv:1105.1842]

François Le Gall.
Quantum Weakly Nondeterministic Communication Complexity.
Theoretical Computer Science, Vol. 486, pp. 4349, 2013. (Special issue devoted to the theory of quantum communication complexity and nonlocality)
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. 658669, 2006.
[quantph/0511025]

François Le Gall.
A TimeEfficient OutputSensitive Quantum Algorithms for Boolean
Matrix Multiplication.
Proceedings of the 23rd International Symposium on Algorithms and Computation (ISAAC 2012), LNCS 7676, pp. 639648, 2012.
DOI: 10.1007/9783642352614\_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. 514523, 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. 369374, 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. 388397, 2012.
DOI: 10.1007/9783642311550\_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. 589600, 2012.
DOI: 10.26421/QIC12.784
[arXiv:1108.4306]

Gábor Ivanyos, François Le Gall and Yuichi Yoshida.
On the distance between nonisomorphic groups.
European Journal of Combinatorics, Vol. 33 No. 4, pp. 474476, 2012.
DOI: 10.1016/j.ejc.2011.10.009
[arXiv:1107.0133]

François Le Gall.
Improved OutputSensitive Quantum Algorithms for Boolean Matrix Multiplication.
Proceedings of the 23rd Annual ACMSIAM Symposium on Discrete Algorithms (SODA 2012), pp. 14641476, 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 OneWay 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. 109113, 2011.
DOI: 10.1109/ISIT.2011.6033701
Also presented at QIP 2011 as a contributed talk.
[arXiv:1012.4583]

MinHsiu Hsieh and François Le Gall.
NPhardness 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. 3547, 2011.
DOI: 10.1007/s0045300993388
A preliminary version appeared in the Proceedings of the 8th Latin American Theoretical Informatics Conference (LATIN 2008), pp. 772783, 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. 549560, 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. 181189, 2010.
DOI: 10.26421/QIC10.341
[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. 622633, 2009.
DOI: 10.1007/9783642029271\_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. 625636, 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 Semidirect Product Groups.
Quantum Information and Computation, Vol.7 No.5&6, pp. 559570, 2007.
DOI: 10.26421/QIC7.569
[quantph/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. 188202, 2009.
DOI: 10.1007/s0022400790973
A preliminary version appeared in the Proceedings of the 18th Annual ACM Symposium on Parallelism in Algorithms and Architectures (SPAA 2006),
pp. 6773, 2006.
Also presented at QIP 2007 as a long talk.
[quantph/0606066]
Surveys and Book Chapters

François Le Gall.
Quantum Complexity of Boolean Matrix Multiplication and Related Problems.
Computing with New Resources: Essays Dedicated to Jozef Gruska on the Occasion of His 80th Birthday, LNCS 8808, pp. 176191, 2014.
DOI: 10.1007/9783319133508\_13

François Le Gall.
Algebraic Complexity Theory and Matrix Multiplication. (Tutorial at ISSAC'14)
Proceedings of the 39th International Symposium on Symbolic and Algebraic Computation (ISSAC 2014), p. 23, 2014.
DOI: 10.1145/2608628.2627493
Handout of the tutorial

François Le Gall and Seiichiro Tani.
Quantum Distributed Computing. (In Japanese)
IEICE Transactions A, Vol. J90A, No. 5, pp. 393402, 2007.

Hirotada Kobayashi and François Le Gall.
Dihedral Hidden Subgroup Problem: A Survey.
IPSJ Journal, 46(10), pp. 24092417, 2005.
DOI: 10.2197/ipsjdc.1.470

Hirotada Kobayashi and François Le Gall.
The Present Status of the Hidden Subgroup Problem Research. (In Japanese)
Mathematical Sciences, 42(6), pp. 1319, 2004.
Theses

Master Thesis: "A Study of the Learning of Formal Languages by Analog Neural Networks", February 2003
The University of Tokyo
Supervisor: Prof. Kazuyuki Aihara

PhD Thesis: "ResourceBounded Quantum Computation", January 2006
The University of Tokyo
Supervisor: Prof. Hiroshi Imai