LeGall Francois

最終更新日時:2016/07/29 10:27:37

印刷する

氏名(漢字/フリガナ/アルファベット表記)
LeGall Francois/ルガル フランソワ/Francois Legall
所属部署・職名(部局/所属/講座等/職名)
情報学研究科/通信情報システム専攻コンピュータ工学講座/特定准教授
学部兼担
部局 所属 講座等 職名
国際高等教育院 国際高等教育院
電子メールアドレス
メールアドレス
legall @ i.kyoto-u.ac.jp
所属学会(国内)
学会名(日本語) 学会名(英語)
情報処理学会 Information Processing Society of Japan
電子情報通信学会 The Institute of Electronics, Information and Communication Engineers
所属学会(海外)
学会名(英語) 国名
EATCS
ACM SIGACT
取得学位
学位名(日本語) 学位名(英語) 大学(日本語) 大学(英語) 取得区分
修士(科学) 東京大学
博士(情報理工学) 東京大学
出身大学院・研究科等
大学名(日本語) 大学名(英語) 研究科名(日本語) 研究科名(英語) 専攻名(日本語) 専攻名(英語) 修了区分
東京大学 大学院新領域創成科学研究科修士課程複雑理工学専攻 修了
東京大学 大学院情報理工学系研究科博士後期課程コンピュータ科学専攻 修了
職歴
期間 組織名(日本語) 組織名(英語) 職名(日本語) 職名(英語)
2006/04/16〜2009/11/30 科学技術振興機構 ERATO-SORST 量子情報システムアーキテクチャ ERATO-SORST Quantum Computation and Information Project, JST 研究員 Researcher
2009/12/01〜2012/04/01 東京大学情報理工学系研究科 Graduate School of Information Science and Technology, The University of Tokyo 特任講師 Lecturer
2012/04/01〜2016/03/31 東京大学情報理工学系研究科 Graduate School of Information Science and Technology, The University of Tokyo 特任准教授 Associate Professor
個人ホームページ
URL
http://www.francoislegall.com/
研究テーマ
(日本語)
アルゴリズム、計算量理論、量子計算
(英語)
Algorithms, Computational Complexity, Quantum computing
論文 > 論文
(文系研究者の一般的な論文集への寄稿や単行本の分担執筆などは「著書等」を参照してください)
著者名 タイトル 書誌情報等 年月 査読の有無 言語
Iordanis Kerenidis,Mathieu Laurière,Francois Le Gall,Mathys Rennela Information cost of quantum communication protocols. Quantum Information & Computation,16,3&4,181-196 2016
François Le Gall,Harumichi Nishimura,Seiichiro Tani Quantum algorithms for finding constant-sized sub-hypergraphs. Theor. Comput. Sci.,609,569-582 2016
Hirotada Kobayashi,François Le Gall,Harumichi Nishimura Stronger Methods of Making Quantum Interactive Proofs Perfectly Complete. SIAM J. Comput.,44,2,243-289 2015
Hirotada Kobayashi,François Le Gall,Harumichi Nishimura Generalized Quantum Arthur-Merlin Games. 30th Conference on Computational Complexity, CCC 2015, June 17-19, 2015, Portland, Oregon, USA,488-511 2015
François Le Gall,Shogo Nakajima Quantum Algorithm for Triangle Finding in Sparse Graphs. Algorithms and Computation - 26th International Symposium, ISAAC 2015, Nagoya, Japan, December 9-11, 2015, Proceedings,590-600 2015
Andris Ambainis,Yuval Filmus,François Le Gall Fast Matrix Multiplication: Limitations of the Coppersmith-Winograd Method. Proceedings of the Forty-Seventh Annual ACM on Symposium on Theory of Computing, STOC 2015, Portland, OR, USA, June 14-17, 2015,585-593 2015
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,176-191 2014
François Le Gall,Harumichi Nishimura,Seiichiro Tani Quantum Algorithms for Finding Constant-Sized Sub-hypergraphs. Computing and Combinatorics - 20th International Conference, COCOON 2014, Atlanta, GA, USA, August 4-6, 2014. Proceedings,429-440 2014
François Le Gall Improved Quantum Algorithm for Triangle Finding via Combinatorial Arguments. 55th IEEE Annual Symposium on Foundations of Computer Science, FOCS 2014, Philadelphia, PA, USA, October 18-21, 2014,216-225 2014
François Le Gall Algebraic complexity theory and matrix multiplication. International Symposium on Symbolic and Algebraic Computation, ISSAC '14, Kobe, Japan, July 23-25, 2014,23 2014
François Le Gall Powers of tensors and fast matrix multiplication. International Symposium on Symbolic and Algebraic Computation, ISSAC '14, Kobe, Japan, July 23-25, 2014,296-303 2014
François Le Gall,Harumichi Nishimura Quantum Algorithms for Matrix Products over Semirings. Algorithm Theory - SWAT 2014 - 14th Scandinavian Symposium and Workshops, Copenhagen, Denmark, July 2-4, 2014. Proceedings,331-343 2014
François Le Gall,Yuichi Yoshida Property testing for cyclic groups and beyond. J. Comb. Optim.,26,4,636-654 2013
François Le Gall Quantum weakly nondeterministic communication complexity. Theor. Comput. Sci.,486,43-49 2013
Hirotada Kobayashi,François Le Gall,Harumichi Nishimura Stronger methods of making quantum interactive proofs perfectly complete. Innovations in Theoretical Computer Science, ITCS '13, Berkeley, CA, USA, January 9-12, 2013,329-352 2013
Gábor Ivanyos,François Le Gall,Yuichi Yoshida On the distance between non-isomorphic groups. Eur. J. Comb.,33,4,474-476 2012
François Le Gall,Shota Nakagawa,Harumichi Nishimura On QMA protocols with two short quantum proofs. Quantum Information & Computation,12,7-8,589-600 2012
François Le Gall Quantum Private Information Retrieval with Sublinear Communication Complexity. Theory of Computing,8,1,369-374 2012
François Le Gall Faster Algorithms for Rectangular Matrix Multiplication. 53rd Annual IEEE Symposium on Foundations of Computer Science, FOCS 2012, New Brunswick, NJ, USA, October 20-23, 2012,514-523 2012
François Le Gall A Time-Efficient Output-Sensitive Quantum Algorithm for Boolean Matrix Multiplication. Algorithms and Computation - 23rd International Symposium, ISAAC 2012, Taipei, Taiwan, December 19-21, 2012. Proceedings,639-648 2012
François Le Gall Improved output-sensitive quantum algorithms for Boolean matrix multiplication. Proceedings of the Twenty-Third Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2012, Kyoto, Japan, January 17-19, 2012,1464-1476 2012
Richard Cleve,Kazuo Iwama,François Le Gall,Harumichi Nishimura,Seiichiro Tani,Junichi Teruyama,Shigeru Yamashita Reconstructing Strings from Substrings with Quantum Queries. Algorithm Theory - SWAT 2012 - 13th Scandinavian Symposium and Workshops, Helsinki, Finland, July 4-6, 2012. Proceedings,388-397 2012
Yoshifumi Inui,François Le Gall Quantum Property Testing of Group Solvability. Algorithmica,59,1,35-47 2011
Scott Aaronson,François Le Gall,Alexander Russell,Seiichiro Tani The One-Way Communication Complexity of Subgroup Membership. Chicago J. Theor. Comput. Sci.,2011 2011
François Le Gall,Yuichi Yoshida Property Testing for Cyclic Groups and Beyond. Computing and Combinatorics - 17th Annual International Conference, COCOON 2011, Dallas, TX, USA, August 14-16, 2011. Proceedings,432-443 2011
Hirotada Kobayashi,Francois Le Gall,Harumichi Nishimura,Martin Rötteler Constructing quantum network coding schemes from classical nonlinear protocols. 2011 IEEE International Symposium on Information Theory Proceedings, ISIT 2011, St. Petersburg, Russia, July 31 - August 5, 2011,109-113 2011
Andris Ambainis,Andrew M. Childs,François Le Gall,Seiichiro Tani The quantum query complexity of certification. Quantum Information & Computation,10,3&4,181-189 2010
Hirotada Kobayashi,François Le Gall,Harumichi Nishimura,Martin Rötteler Perfect quantum network communication protocol based on classical network coding. IEEE International Symposium on Information Theory, ISIT 2010, June 13-18, 2010, Austin, Texas, USA, Proceedings,2686-2690 2010
François Le Gall An Efficient Quantum Algorithm for Some Instances of the Group Isomorphism Problem. 27th International Symposium on Theoretical Aspects of Computer Science, STACS 2010, March 4-6, 2010, Nancy, France,549-560 2010
François Le Gall Exponential Separation of Quantum and Classical Online Space Complexity. Theory Comput. Syst.,45,2,188-202 2009
Hirotada Kobayashi,François Le Gall,Harumichi Nishimura,Martin Rötteler General Scheme for Perfect Quantum Network Coding with Free Classical Communication. Automata, Languages and Programming, 36th International Colloquium, ICALP 2009, Rhodes, Greece, July 5-12, 2009, Proceedings, Part I,622-633 2009
François Le Gall Efficient Isomorphism Testing for a Class of Group Extensions. 26th International Symposium on Theoretical Aspects of Computer Science, STACS 2009, February 26-28, 2009, Freiburg, Germany, Proceedings,625-636 2009
Yoshifumi Inui,François Le Gall Quantum Property Testing of Group Solvability. LATIN 2008: Theoretical Informatics, 8th Latin American Symposium, Búzios, Brazil, April 7-11, 2008, Proceedings,772-783 2008
Yoshifumi Inui,François Le Gall Efficient quantum algorithms for the hidden subgroup problem over semi-direct product groups. Quantum Information & Computation,7,5,559-570 2007
François Le Gall Quantum Weakly Nondeterministic Communication Complexity. Mathematical Foundations of Computer Science 2006, 31st International Symposium, MFCS 2006, Stará Lesná, Slovakia, August 28-September 1, 2006, Proceedings,658-669 2006
François Le Gall Exponential separation of quantum and classical online space complexity. SPAA 2006: Proceedings of the 18th Annual ACM Symposium on Parallelism in Algorithms and Architectures, Cambridge, Massachusetts, USA, July 30 - August 2, 2006,67-73 2006

  • <<
  • >>
  • 表示
学術賞等
賞の名称(日本語) 賞の名称(英語) 授与組織名(日本語) 授与組織名(英語) 年月
ISSAC 2014 Distinguished Paper Award ISSAC 2014 Distinguished Paper Award ACM SIGACT ACM SIGACT 2014/07/24
外部資金:競争的資金・科学研究費補助金
種別 代表/分担 テーマ(日本語) テーマ(英語) 期間
若手研究A 代表 Algebraic Complexity Theory: New Approaches and Algorithmic Applications Algebraic Complexity Theory: New Approaches and Algorithmic Applications 2016/04/01〜2020/03/31
担当科目
講義名(日本語) 講義名(英語) 開講期 学部/研究科 期間
Fundamentals of Discrete Optimization-E2 Fundamentals of Discrete Optimization-E2 後期 全学共通科目 2016/04〜2017/03
Introduction to Algorithms-E2 Introduction to Algorithms-E2 前期 全学共通科目 2016/04〜2017/03
Introduction to Algorithms-E2 Introduction to Algorithms-E2 後期 全学共通科目 2016/04〜2017/03
Intro to Coding Theory & Cryptography-E2 Introduction to Coding Theory and Cryptography-E2 前期 全学共通科目 2016/04〜2017/03