François Le Gall

New affiliation (from December 2009):

Previous affiliation (until November 2009):

Research interests: theoretical computer science, quantum computation

• Computational complexity
• Discrete algorithms (especially for group-theoretic problems)
• Quantum computing (quantum algorithms and quantum communication complexity)

Publications

Research Results

François Le Gall.
An Efficient Quantum Algorithm for some Instances of the Group Isomorphism Problem.
To appear in the Proceedings of the 27th International Symposium on Theoretical Aspects of Computer Science (STACS 2010).
Available at arXiv:1001.0608 .

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.
Also available at 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.
Also available at arXiv:0908.1457 .

Scott Aaronson, François Le Gall, Alexander Russell and Seiichiro Tani.
The One-Way Communication Complexity of Group Membership.
Submitted.
Available at arXiv:0902.3175 .

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.
Also available at arXiv:0812.2298 .

Hirotada Kobayashi, François Le Gall, Harumichi Nishimura and Martin Roetteler.
Perfect Quantum Network Communication Protocol Based on Classical Network Coding.
Submitted.
Available at arXiv:0902.1299 .

Yoshifumi Inui and François Le Gall.
Quantum Property Testing of Group Solvability.
Algorithmica, published online on July 11, 2009.
A preliminary version appeared in the Proceedings of the 8th Latin American Theoretical Informatics Conference (LATIN08), pp. 772-783, 2008.
Also available at arXiv:0712.3829 .

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.
Also available at quant-ph/0412033 .

François Le Gall.
Quantum Weakly Nondeterministic Communication Complexity.
Theoretical Computer Science, to appear, 2010.
A preliminary version appeared in the Proceedings of the 31st International Symposium of Mathematical Foundations of Computer Science (MFCS 2006), pp. 658-669, 2006.
Also available at quant-ph/0511025.

François Le Gall.
Exponential Separation of Quantum and Classical Online Space Complexity.
Theory of Computing Systems, Vol. 45 No. 2, pp. 188-202, 2009.
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 available at quant-ph/0606066 .

Surveys

François Le Gall and Seiichiro Tani.
Quantum Distributed Computing (in Japanese).
IEICE Transactions A, Vol.J90-A No.5, pp. 393-402, 2007.

Hirotada Kobayashi and François Le Gall.
Dihedral Hidden Subgroup Problem: A Survey.
IPSJ Journal, 46(10), pp. 2409-2417, 2005.

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

Theses