François Le Gall

According to our database, François Le Gall authored at least 102 papers between 2006 and 2025.

Collaborative distances:

• Dijkstra number of four.
• Erdős number of three.

2025

A Simpler Exponential-Time Approximation Algorithm for MAX-k-SAT.

Harry Buhrman, Sevag Gharibian, Zeph Landau, François Le Gall, Norbert Schuch, Suguru Tamaki

CoRR, October, 2025

Exponential Quantum Advantage for Message Complexity in Distributed Algorithms.

François Le Gall, Maël Luce, Joseph Marchand, Mathieu Roget

CoRR, October, 2025

Dequantization and Hardness of Spectral Sum Estimation.

Roman Edenhofer, Atsuya Hasegawa, François Le Gall

CoRR, September, 2025

Correction: Robust dequantization of the quantum singular value transformation and quantum machine learning algorithms.

François Le Gall

Comput. Complex., June, 2025

Barriers for rectangular matrix multiplication.

Matthias Christandl, François Le Gall, Vladimir Lysikov, Jeroen Zuiddam

Comput. Complex., June, 2025

Maximum Separation of Quantum Communication Complexity With and Without Shared Entanglement.

Atsuya Hasegawa, François Le Gall, Augusto Modanese

CoRR, May, 2025

Group Order is in QCMA.

François Le Gall, Harumichi Nishimura, Dhara Thakkar

CoRR, April, 2025

Does there exist a quantum fingerprinting protocol without coherent measurements?

Atsuya Hasegawa, Srijita Kundu, François Le Gall, Harumichi Nishimura, Qisheng Wang

CoRR, February, 2025

Quantum Merlin-Arthur proof systems for synthesizing quantum states.

Hugo Delavenne, François Le Gall, Yupan Liu, Masayuki Miyamoto

Quantum, 2025

Robust Dequantization of the Quantum Singular Value Transformation and Quantum Machine Learning Algorithms.

François Le Gall

Comput. Complex., 2025

Distributed Quantum Advantage for Local Problems.

Alkida Balliu, Sebastian Brandt, Xavier Coiteux-Roy, Francesco d'Amore, Massimo Equi, François Le Gall, Henrik Lievonen, Augusto Modanese, Dennis Olivetti, Marc-Olivier Renou, Jukka Suomela, Lucas Tendick, Isadora Veeren

Proceedings of the 57th Annual ACM Symposium on Theory of Computing, 2025

Online Locality Meets Distributed Quantum Computing.

Amirreza Akbari, Xavier Coiteux-Roy, Francesco d'Amore, François Le Gall, Henrik Lievonen, Darya Melnyk, Augusto Modanese, Shreyas Pai, Marc-Olivier Renou, Václav Rozhon, Jukka Suomela

Proceedings of the 57th Annual ACM Symposium on Theory of Computing, 2025

Classical Algorithms for Constant Approximation of the Ground State Energy of Local Hamiltonians.

François Le Gall

Proceedings of the 33rd Annual European Symposium on Algorithms, 2025

Space-Bounded Quantum Interactive Proof Systems.

François Le Gall, Yupan Liu, Harumichi Nishimura, Qisheng Wang

Proceedings of the 40th Computational Complexity Conference, 2025

2024

Quantum state synthesis: relation with decision complexity classes and impossibility of error reduction.

Hugo Delavenne, François Le Gall

Quantum Inf. Comput., September, 2024

Classical versus quantum queries in quantum PCPs with classical proofs.

Harry Buhrman, François Le Gall, Jordi Weggemans

CoRR, 2024

Beating Grover search for low-energy estimation and state preparation.

Harry Buhrman, Sevag Gharibian, Zeph Landau, François Le Gall, Norbert Schuch, Suguru Tamaki

CoRR, 2024

Quantum State Synthesis: Relation with Decision Complexity Classes and Impossibility of Synthesis Error Reduction.

Hugo Delavenne, François Le Gall

CoRR, 2024

No Distributed Quantum Advantage for Approximate Graph Coloring.

Xavier Coiteux-Roy, Francesco d'Amore, Rishikesh Gajjala, Fabian Kuhn, François Le Gall, Henrik Lievonen, Augusto Modanese, Marc-Olivier Renou, Gustav Schmid, Jukka Suomela

Proceedings of the 56th Annual ACM Symposium on Theory of Computing, 2024

Faster Rectangular Matrix Multiplication by Combination Loss Analysis.

François Le Gall

Proceedings of the 2024 ACM-SIAM Symposium on Discrete Algorithms, 2024

Quantum Simultaneous Protocols Without Public Coins Using Modified Equality Queries.

François Le Gall, Oran Nadler, Harumichi Nishimura, Rotem Oshman

Proceedings of the 28th International Conference on Principles of Distributed Systems, 2024

2023

Space-bounded quantum state testing via space-efficient quantum singular value transformation.

François Le Gall, Yupan Liu, Qisheng Wang

Electron. Colloquium Comput. Complex., 2023

Distributed Quantum Interactive Proofs.

François Le Gall, Masayuki Miyamoto, Harumichi Nishimura

Proceedings of the 40th International Symposium on Theoretical Aspects of Computer Science, 2023

Quantum Distributed Computing: Potential and Limitations (Invited Talk).

François Le Gall

Proceedings of the 27th International Conference on Principles of Distributed Systems, 2023

Distributed Merlin-Arthur Synthesis of Quantum States and Its Applications.

François Le Gall, Masayuki Miyamoto, Harumichi Nishimura

Proceedings of the 48th International Symposium on Mathematical Foundations of Computer Science, 2023

Improved Hardness Results for the Guided Local Hamiltonian Problem.

Chris Cade, Marten Folkertsma, Sevag Gharibian, Ryu Hayakawa, François Le Gall, Tomoyuki Morimae, Jordi Weggemans

Proceedings of the 50th International Colloquium on Automata, Languages, and Programming, 2023

2022

Quantum approximate counting for Markov chains and collision counting.

Francois Le Gall, Iu-Iong Ng

Quantum Inf. Comput., 2022

Non-trivial lower bound for 3-coloring the ring in the quantum LOCAL model.

François Le Gall, Ansis Rosmanis

CoRR, 2022

Improved Hardness Results for the Guided Local Hamiltonian Problem.

Sevag Gharibian, Ryu Hayakawa, François Le Gall, Tomoyuki Morimae

CoRR, 2022

Quantum Approximate Counting for Markov Chains and Application to Collision Counting.

François Le Gall, Iu-Iong Ng

CoRR, 2022

Brief Announcement: Distributed Quantum Interactive Proofs.

François Le Gall, Masayuki Miyamoto, Harumichi Nishimura

Proceedings of the 36th International Symposium on Distributed Computing, 2022

Dequantizing the Quantum singular value transformation: hardness and applications to Quantum chemistry and the Quantum PCP conjecture.

Sevag Gharibian, François Le Gall

Proceedings of the STOC '22: 54th Annual ACM SIGACT Symposium on Theory of Computing, Rome, Italy, June 20, 2022

Bounds on Oblivious Multiparty Quantum Communication Complexity.

François Le Gall, Daiki Suruga

Proceedings of the LATIN 2022: Theoretical Informatics, 2022

An Optimal Oracle Separation of Classical and Quantum Hybrid Schemes.

Atsuya Hasegawa, François Le Gall

Proceedings of the 33rd International Symposium on Algorithms and Computation, 2022

Quantum Meets Fine-Grained Complexity: Sublinear Time Quantum Algorithms for String Problems.

François Le Gall, Saeed Seddighin

Proceedings of the 13th Innovations in Theoretical Computer Science Conference, 2022

Quantum Distributed Algorithms for Detection of Cliques.

Keren Censor-Hillel, Orr Fischer, François Le Gall, Dean Leitersdorf, Rotem Oshman

Proceedings of the 13th Innovations in Theoretical Computer Science Conference, 2022

2021

Quantum communication complexity of distribution testing.

Aleksandrs Belovs, Arturo Castellanos, Francois Le Gall, Guillaume Malod, Alexander A. Sherstov

Quantum Inf. Comput., 2021

Quantum Logarithmic Space and Post-Selection.

François Le Gall, Harumichi Nishimura, Abuzer Yakaryilmaz

Proceedings of the 16th Conference on the Theory of Quantum Computation, 2021

Tight Distributed Listing of Cliques.

Keren Censor-Hillel, Yi-Jun Chang, François Le Gall, Dean Leitersdorf

Proceedings of the 2021 ACM-SIAM Symposium on Discrete Algorithms, 2021

Test of Quantumness with Small-Depth Quantum Circuits.

Shuichi Hirahara, François Le Gall

Proceedings of the 46th International Symposium on Mathematical Foundations of Computer Science, 2021

Quantum Advantage with Shallow Circuits Under Arbitrary Corruption.

Atsuya Hasegawa, François Le Gall

Proceedings of the 32nd International Symposium on Algorithms and Computation, 2021

Lower Bounds for Induced Cycle Detection in Distributed Computing.

François Le Gall, Masayuki Miyamoto

Proceedings of the 32nd International Symposium on Algorithms and Computation, 2021

Distributed Quantum Proofs for Replicated Data.

Pierre Fraigniaud, François Le Gall, Harumichi Nishimura, Ami Paz

Proceedings of the 12th Innovations in Theoretical Computer Science Conference, 2021

2020

Brief Announcement: Distributed Quantum Proofs for Replicated Data.

Pierre Fraigniaud, François Le Gall, Harumichi Nishimura, Ami Paz

Proceedings of the 34th International Symposium on Distributed Computing, 2020

Fast Distributed Algorithms for Girth, Cycles and Small Subgraphs.

Keren Censor-Hillel, Orr Fischer, Tzlil Gonen, François Le Gall, Dean Leitersdorf, Rotem Oshman

Proceedings of the 34th International Symposium on Distributed Computing, 2020

Quantum Distributed Algorithm for Triangle Finding in the CONGEST Model.

Taisuke Izumi, François Le Gall, Frédéric Magniez

Proceedings of the 37th International Symposium on Theoretical Aspects of Computer Science, 2020

On Distributed Listing of Cliques.

Keren Censor-Hillel, François Le Gall, Dean Leitersdorf

Proceedings of the PODC '20: ACM Symposium on Principles of Distributed Computing, 2020

Quantum-Inspired Classical Algorithms for Singular Value Transformation.

Dhawal Jethwani, François Le Gall, Sanjay Kumar Singh

Proceedings of the 45th International Symposium on Mathematical Foundations of Computer Science, 2020

Quantum Speedup for the Minimum Steiner Tree Problem.

Masayuki Miyamoto, Masakazu Iwamura, Koichi Kise, François Le Gall

Proceedings of the Computing and Combinatorics - 26th International Conference, 2020

2019

Quantum Advantage for the LOCAL Model in Distributed Computing.

François Le Gall, Harumichi Nishimura, Ansis Rosmanis

Proceedings of the 36th International Symposium on Theoretical Aspects of Computer Science, 2019

Quantum Distributed Algorithm for the All-Pairs Shortest Path Problem in the CONGEST-CLIQUE Model.

Taisuke Izumi, François Le Gall

Proceedings of the 2019 ACM Symposium on Principles of Distributed Computing, 2019

Average-Case Quantum Advantage with Shallow Circuits.

François Le Gall

Proceedings of the 34th Computational Complexity Conference, 2019

2018

Improved Rectangular Matrix Multiplication using Powers of the Coppersmith-Winograd Tensor.

Francois Le Gall, Florent Urrutia

Proceedings of the Twenty-Ninth Annual ACM-SIAM Symposium on Discrete Algorithms, 2018

Sublinear-Time Quantum Computation of the Diameter in CONGEST Networks.

François Le Gall, Frédéric Magniez

Proceedings of the 2018 ACM Symposium on Principles of Distributed Computing, 2018

Interactive Proofs with Polynomial-Time Quantum Prover for Computing the Order of Solvable Groups.

François Le Gall, Tomoyuki Morimae, Harumichi Nishimura, Yuki Takeuchi

Proceedings of the 43rd International Symposium on Mathematical Foundations of Computer Science, 2018

2017

Modified Group Non-Membership is in Promise-AWPP relative to group oracles.

Tomoyuki Morimae, Harumichi Nishimura, Francois Le Gall

Quantum Inf. Comput., 2017

Multiparty Quantum Communication Complexity of Triangle Finding.

François Le Gall, Shogo Nakajima

Proceedings of the 12th Conference on the Theory of Quantum Computation, 2017

Triangle Finding and Listing in CONGEST Networks.

Taisuke Izumi, François Le Gall

Proceedings of the ACM Symposium on Principles of Distributed Computing, 2017

Quantum Query Complexity of Unitary Operator Discrimination.

Akinori Kawachi, Kenichi Kawano, François Le Gall, Suguru Tamaki

Proceedings of the Computing and Combinatorics - 23rd International Conference, 2017

Probabilistic Logarithmic-Space Algorithms for Laplacian Solvers.

Dean Doron, François Le Gall, Amnon Ta-Shma

Proceedings of the Approximation, 2017

2016

Information cost of quantum communication protocols.

Iordanis Kerenidis, Mathieu Laurière, Francois Le Gall, Mathys Rennela

Quantum Inf. Comput., 2016

Modified group non-membership is in AWPP.

Tomoyuki Morimae, Harumichi Nishimura, Francois Le Gall

CoRR, 2016

On the Group and Color Isomorphism Problems.

François Le Gall, David J. Rosenbaum

CoRR, 2016

Solving Laplacian Systems in Logarithmic Space.

François Le Gall

CoRR, 2016

Improving Quantum Query Complexity of Boolean Matrix Multiplication Using Graph Collision.

Stacey Jeffery, Robin Kothari, François Le Gall, Frédéric Magniez

Algorithmica, 2016

Further Algebraic Algorithms in the Congested Clique Model and Applications to Graph-Theoretic Problems.

François Le Gall

Proceedings of the Distributed Computing - 30th International Symposium, 2016

Quantum Communication Complexity of Distributed Set Joins.

Stacey Jeffery, François Le Gall

Proceedings of the 41st International Symposium on Mathematical Foundations of Computer Science, 2016

2015

Fast Matrix Multiplication: Limitations of the Coppersmith-Winograd Method.

Andris Ambainis, Yuval Filmus, François Le Gall

Proceedings of the Forty-Seventh Annual ACM on Symposium on Theory of Computing, 2015

Quantum Algorithm for Triangle Finding in Sparse Graphs.

François Le Gall, Shogo Nakajima

Proceedings of the Algorithms and Computation - 26th International Symposium, 2015

Generalized Quantum Arthur-Merlin Games.

Hirotada Kobayashi, François Le Gall, Harumichi Nishimura

Proceedings of the 30th Conference on Computational Complexity, 2015

2014

Fast Matrix Multiplication: Limitations of the Laser Method.

Andris Ambainis, Yuval Filmus, François Le Gall

Electron. Colloquium Comput. Complex., 2014

Privacy in Quantum Communication Complexity.

Iordanis Kerenidis, Mathieu Laurière, François Le Gall, Mathys Rennela

CoRR, 2014

Quantum Algorithms for Matrix Products over Semirings.

François Le Gall, Harumichi Nishimura

Proceedings of the Algorithm Theory - SWAT 2014, 2014

Powers of tensors and fast matrix multiplication.

François Le Gall

Proceedings of the International Symposium on Symbolic and Algebraic Computation, 2014

Algebraic complexity theory and matrix multiplication.

François Le Gall

Proceedings of the International Symposium on Symbolic and Algebraic Computation, 2014

Improved Quantum Algorithm for Triangle Finding via Combinatorial Arguments.

François Le Gall

Proceedings of the 55th IEEE Annual Symposium on Foundations of Computer Science, 2014

Quantum Algorithms for Finding Constant-Sized Sub-hypergraphs.

François Le Gall, Harumichi Nishimura, Seiichiro Tani

Proceedings of the Computing and Combinatorics - 20th International Conference, 2014

Quantum Complexity of Boolean Matrix Multiplication and Related Problems.

François Le Gall

Proceedings of the Computing with New Resources, 2014

2013

Quantum Algorithms for Finding Constant-sized Sub-hypergraphs over 3-uniform Hypergraphs.

François Le Gall, Harumichi Nishimura, Seiichiro Tani

CoRR, 2013

Stronger methods of making quantum interactive proofs perfectly complete.

Hirotada Kobayashi, François Le Gall, Harumichi Nishimura

Proceedings of the Innovations in Theoretical Computer Science, 2013

2012

Quantum Private Information Retrieval with Sublinear Communication Complexity.

François Le Gall

Theory Comput., 2012

On QMA protocols with two short quantum proofs.

François Le Gall, Shota Nakagawa, Harumichi Nishimura

Quantum Inf. Comput., 2012

On the distance between non-isomorphic groups.

Gábor Ivanyos, François Le Gall, Yuichi Yoshida

Eur. J. Comb., 2012

Improved Time-Efficient Output-Sensitive Quantum Algorithms for Boolean Matrix Multiplication

François Le Gall

CoRR, 2012

Reconstructing Strings from Substrings with Quantum Queries.

Richard Cleve, Kazuo Iwama, François Le Gall, Harumichi Nishimura, Seiichiro Tani, Junichi Teruyama, Shigeru Yamashita

Proceedings of the Algorithm Theory - SWAT 2012, 2012

Improved output-sensitive quantum algorithms for Boolean matrix multiplication.

François Le Gall

Proceedings of the Twenty-Third Annual ACM-SIAM Symposium on Discrete Algorithms, 2012

A Time-Efficient Output-Sensitive Quantum Algorithm for Boolean Matrix Multiplication.

François Le Gall

Proceedings of the Algorithms and Computation - 23rd International Symposium, 2012

Faster Algorithms for Rectangular Matrix Multiplication.

François Le Gall

Proceedings of the 53rd Annual IEEE Symposium on Foundations of Computer Science, 2012

2011

The One-Way Communication Complexity of Subgroup Membership.

Scott Aaronson, François Le Gall, Alexander Russell, Seiichiro Tani

Chic. J. Theor. Comput. Sci., 2011

Constructing quantum network coding schemes from classical nonlinear protocols.

Hirotada Kobayashi, Francois Le Gall, Harumichi Nishimura, Martin Rötteler

Proceedings of the 2011 IEEE International Symposium on Information Theory Proceedings, 2011

Property Testing for Cyclic Groups and Beyond.

François Le Gall, Yuichi Yoshida

Proceedings of the Computing and Combinatorics - 17th Annual International Conference, 2011

2010

The quantum query complexity of certification.

Andris Ambainis, Andrew M. Childs, François Le Gall, Seiichiro Tani

Quantum Inf. Comput., 2010

An Efficient Quantum Algorithm for Some Instances of the Group Isomorphism Problem.

François Le Gall

Proceedings of the 27th International Symposium on Theoretical Aspects of Computer Science, 2010

Perfect quantum network communication protocol based on classical network coding.

Hirotada Kobayashi, François Le Gall, Harumichi Nishimura, Martin Rötteler

Proceedings of the IEEE International Symposium on Information Theory, 2010

2009

The One-Way Communication Complexity of Group Membership

Scott Aaronson, François Le Gall, Alexander Russell, Seiichiro Tani

CoRR, 2009

Efficient Isomorphism Testing for a Class of Group Extensions.

François Le Gall

Proceedings of the 26th International Symposium on Theoretical Aspects of Computer Science, 2009

General Scheme for Perfect Quantum Network Coding with Free Classical Communication.

Hirotada Kobayashi, François Le Gall, Harumichi Nishimura, Martin Rötteler

Proceedings of the Automata, Languages and Programming, 36th International Colloquium, 2009

2008

Quantum Property Testing of Group Solvability.

Yoshifumi Inui, François Le Gall

Proceedings of the LATIN 2008: Theoretical Informatics, 2008

2007

Efficient quantum algorithms for the hidden subgroup problem over semi-direct product groups.

Yoshifumi Inui, François Le Gall

Quantum Inf. Comput., 2007

2006

Dihedral Hidden Subgroup Problem: A Survey.

Hirotada Kobayashi, François Le Gall

Inf. Media Technol., 2006

Exponential separation of quantum and classical online space complexity.

François Le Gall

Proceedings of the SPAA 2006: Proceedings of the 18th Annual ACM Symposium on Parallelism in Algorithms and Architectures, Cambridge, Massachusetts, USA, July 30, 2006

Quantum Weakly Nondeterministic Communication Complexity.

François Le Gall

Proceedings of the Mathematical Foundations of Computer Science 2006, 2006