François Le Gall

ORCID

Publication Activity (10 Years)

Years Active: 2005-2024
Publications (10 Years): 89

Top Venues

Publications

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
No Distributed Quantum Advantage for Approximate Graph Coloring. STOC (2024)
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
Online Locality Meets Distributed Quantum Computing. CoRR (2024)
François Le Gall
Faster Rectangular Matrix Multiplication by Combination Loss Analysis. SODA (2024)
Harry Buhrman, Sevag Gharibian, Zeph Landau, François Le Gall, Norbert Schuch, Suguru Tamaki
Beating Grover search for low-energy estimation and state preparation. CoRR (2024)
Hugo Delavenne, François Le Gall
Quantum State Synthesis: Relation with Decision Complexity Classes and Impossibility of Synthesis Error Reduction. CoRR (2024)
François Le Gall
Faster Rectangular Matrix Multiplication by Combination Loss Analysis. CoRR (2023)
François Le Gall, Yupan Liu, Qisheng Wang
Space-bounded quantum state testing via space-efficient quantum singular value transformation. CoRR (2023)
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
No distributed quantum advantage for approximate graph coloring. CoRR (2023)
François Le Gall, Yupan Liu, Qisheng Wang
Space-bounded quantum state testing via space-efficient quantum singular value transformation. Electron. Colloquium Comput. Complex. (2023)
François Le Gall
Quantum Distributed Computing: Potential and Limitations (Invited Talk). OPODIS (2023)
François Le Gall, Masayuki Miyamoto, Harumichi Nishimura
Distributed Merlin-Arthur Synthesis of Quantum States and Its Applications. MFCS (2023)
François Le Gall, Saeed Seddighin
Quantum Meets Fine-Grained Complexity: Sublinear Time Quantum Algorithms for String Problems. Algorithmica 85 (5) (2023)
Hugo Delavenne, François Le Gall, Yupan Liu, Masayuki Miyamoto
Quantum Merlin-Arthur proof systems for synthesizing quantum states. CoRR (2023)
François Le Gall
Robust Dequantization of the Quantum Singular value Transformation and Quantum Machine Learning Algorithms. CoRR (2023)
Sevag Gharibian, François Le Gall
Dequantizing the Quantum Singular Value Transformation: Hardness and Applications to Quantum Chemistry and the Quantum PCP Conjecture. SIAM J. Comput. 52 (4) (2023)
François Le Gall, Masayuki Miyamoto, Harumichi Nishimura
Distributed Quantum Interactive Proofs. STACS (2023)
Chris Cade, Marten Folkertsma, Sevag Gharibian, Ryu Hayakawa, François Le Gall, Tomoyuki Morimae, Jordi Weggemans
Improved Hardness Results for the Guided Local Hamiltonian Problem. ICALP (2023)
Sevag Gharibian, François Le Gall
Dequantizing the Quantum singular value transformation: hardness and applications to Quantum chemistry and the Quantum PCP conjecture. STOC (2022)
François Le Gall, Iu-Iong Ng
Quantum Approximate Counting for Markov Chains and Application to Collision Counting. CoRR (2022)
Keren Censor-Hillel, Orr Fischer, François Le Gall, Dean Leitersdorf, Rotem Oshman
Quantum Distributed Algorithms for Detection of Cliques. CoRR (2022)
François Le Gall, Masayuki Miyamoto, Harumichi Nishimura
Brief Announcement: Distributed Quantum Interactive Proofs. DISC (2022)
François Le Gall, Daiki Suruga
Bounds on Oblivious Multiparty Quantum Communication Complexity. LATIN (2022)
Atsuya Hasegawa, François Le Gall
An optimal oracle separation of classical and quantum hybrid schemes. CoRR (2022)
François Le Gall, Masayuki Miyamoto, Harumichi Nishimura
Distributed Quantum Interactive Proofs. CoRR (2022)
Atsuya Hasegawa, François Le Gall
An Optimal Oracle Separation of Classical and Quantum Hybrid Schemes. ISAAC (2022)
François Le Gall, Saeed Seddighin
Quantum Meets Fine-Grained Complexity: Sublinear Time Quantum Algorithms for String Problems. ITCS (2022)
François Le Gall, Masayuki Miyamoto, Harumichi Nishimura
Distributed Merlin-Arthur Synthesis of Quantum States and Its Applications. CoRR (2022)
François Le Gall, Ansis Rosmanis
Non-trivial lower bound for 3-coloring the ring in the quantum LOCAL model. CoRR (2022)
Sevag Gharibian, Ryu Hayakawa, François Le Gall, Tomoyuki Morimae
Improved Hardness Results for the Guided Local Hamiltonian Problem. CoRR (2022)
Keren Censor-Hillel, Orr Fischer, François Le Gall, Dean Leitersdorf, Rotem Oshman
Quantum Distributed Algorithms for Detection of Cliques. ITCS (2022)
François Le Gall, Masayuki Miyamoto
Lower Bounds for Induced Cycle Detection in Distributed Computing. CoRR (2021)
François Le Gall, Masayuki Miyamoto
Lower Bounds for Induced Cycle Detection in Distributed Computing. ISAAC (2021)
Pierre Fraigniaud, François Le Gall, Harumichi Nishimura, Ami Paz
Distributed Quantum Proofs for Replicated Data. ITCS (2021)
Keren Censor-Hillel, Orr Fischer, Tzlil Gonen, François Le Gall, Dean Leitersdorf, Rotem Oshman
Fast Distributed Algorithms for Girth, Cycles and Small Subgraphs. CoRR (2021)
Atsuya Hasegawa, François Le Gall
Quantum Advantage with Shallow Circuits under Arbitrary Corruption. CoRR (2021)
Shuichi Hirahara, François Le Gall
Test of Quantumness with Small-Depth Quantum Circuits. MFCS (2021)
Shuichi Hirahara, François Le Gall
Test of Quantumness with Small-Depth Quantum Circuits. CoRR (2021)
François Le Gall, Harumichi Nishimura, Abuzer Yakaryilmaz
Quantum Logarithmic Space and Post-selection. CoRR (2021)
Atsuya Hasegawa, François Le Gall
Quantum Advantage with Shallow Circuits Under Arbitrary Corruption. ISAAC (2021)
Sevag Gharibian, François Le Gall
Dequantizing the Quantum Singular Value Transformation: Hardness and Applications to Quantum Chemistry and the Quantum PCP Conjecture. CoRR (2021)
François Le Gall, Harumichi Nishimura, Abuzer Yakaryilmaz
Quantum Logarithmic Space and Post-Selection. TQC (2021)
Keren Censor-Hillel, Yi-Jun Chang, François Le Gall, Dean Leitersdorf
Tight Distributed Listing of Cliques. SODA (2021)
Aleksandrs Belovs, Arturo Castellanos, François Le Gall, Guillaume Malod, Alexander A. Sherstov
Quantum Communication Complexity of Distribution Testing. CoRR (2020)
Keren Censor-Hillel, Orr Fischer, Tzlil Gonen, François Le Gall, Dean Leitersdorf, Rotem Oshman
Fast Distributed Algorithms for Girth, Cycles and Small Subgraphs. DISC (2020)
Matthias Christandl, François Le Gall, Vladimir Lysikov, Jeroen Zuiddam
Barriers for Rectangular Matrix Multiplication. Electron. Colloquium Comput. Complex. 27 (2020)
Dhawal Jethwani, François Le Gall, Sanjay K. Singh
Quantum-Inspired Classical Algorithms for Singular Value Transformation. MFCS (2020)
Masayuki Miyamoto, Masakazu Iwamura, Koichi Kise, François Le Gall
Quantum Speedup for the Minimum Steiner Tree Problem. COCOON (2020)
Pierre Fraigniaud, François Le Gall, Harumichi Nishimura, Ami Paz
Distributed Quantum Proofs for Replicated Data. CoRR (2020)
Keren Censor-Hillel, François Le Gall, Dean Leitersdorf
On Distributed Listing of Cliques. PODC (2020)
Keren Censor-Hillel, Yi-Jun Chang, François Le Gall, Dean Leitersdorf
Tight Distributed Listing of Cliques. CoRR (2020)
Keren Censor-Hillel, François Le Gall, Dean Leitersdorf
On Distributed Listing of Cliques. CoRR (2020)
Pierre Fraigniaud, François Le Gall, Harumichi Nishimura, Ami Paz
Brief Announcement: Distributed Quantum Proofs for Replicated Data. DISC (2020)
Matthias Christandl, François Le Gall, Vladimir Lysikov, Jeroen Zuiddam
Barriers for rectangular matrix multiplication. CoRR (2020)
Taisuke Izumi, François Le Gall, Frédéric Magniez
Quantum Distributed Algorithm for Triangle Finding in the CONGEST Model. STACS (2020)
François Le Gall, Saeed Seddighin
Quantum Meets Fine-grained Complexity: Sublinear Time Quantum Algorithms for String Problems. CoRR (2020)
François Le Gall, Harumichi Nishimura, Ansis Rosmanis
Quantum Advantage for the LOCAL Model in Distributed Computing. STACS (2019)
Taisuke Izumi, François Le Gall, Frédéric Magniez
Quantum Distributed Algorithm for Triangle Finding in the CONGEST Model. CoRR (2019)
Dhawal Jethwani, François Le Gall, Sanjay K. Singh
Quantum-Inspired Classical Algorithms for Singular Value Transformation. CoRR (2019)
Hirotada Kobayashi, François Le Gall, Harumichi Nishimura
Generalized Quantum Arthur-Merlin Games. SIAM J. Comput. 48 (3) (2019)
Taisuke Izumi, François Le Gall
Quantum Distributed Algorithm for the All-Pairs Shortest Path Problem in the CONGEST-CLIQUE Model. PODC (2019)
François Le Gall
Average-Case Quantum Advantage with Shallow Circuits. Computational Complexity Conference (2019)
Taisuke Izumi, François Le Gall
Quantum Distributed Algorithm for the All-Pairs Shortest Path Problem in the CONGEST-CLIQUE Model. CoRR (2019)
François Le Gall, Harumichi Nishimura, Ansis Rosmanis
Quantum Advantage for the LOCAL Model in Distributed Computing. CoRR (2018)
François Le Gall, Frédéric Magniez
Sublinear-Time Quantum Computation of the Diameter in CONGEST Networks. CoRR (2018)
François Le Gall, Frédéric Magniez
Sublinear-Time Quantum Computation of the Diameter in CONGEST Networks. PODC (2018)
François Le Gall
Average-Case Quantum Advantage with Shallow Circuits. CoRR (2018)
François Le Gall, Tomoyuki Morimae, Harumichi Nishimura, Yuki Takeuchi
Interactive Proofs with Polynomial-Time Quantum Prover for Computing the Order of Solvable Groups. CoRR (2018)
François Le Gall, Tomoyuki Morimae, Harumichi Nishimura, Yuki Takeuchi
Interactive Proofs with Polynomial-Time Quantum Prover for Computing the Order of Solvable Groups. MFCS (2018)
François Le Gall, Harumichi Nishimura
Quantum Algorithms for Matrix Products over Semirings. Chic. J. Theor. Comput. Sci. 2017 (2017)
Taisuke Izumi, François Le Gall
Triangle Finding and Listing in CONGEST Networks. CoRR (2017)
François Le Gall, Shogo Nakajima
Quantum Algorithm for Triangle Finding in Sparse Graphs. Algorithmica 79 (3) (2017)
Akinori Kawachi, Kenichi Kawano, François Le Gall, Suguru Tamaki
Quantum Query Complexity of Unitary Operator Discrimination. COCOON (2017)
François Le Gall, Florent Urrutia
Improved Rectangular Matrix Multiplication using Powers of the Coppersmith-Winograd Tensor. CoRR (2017)
Taisuke Izumi, François Le Gall
Triangle Finding and Listing in CONGEST Networks. PODC (2017)
Dean Doron, François Le Gall, Amnon Ta-Shma
Probabilistic Logarithmic-Space Algorithms for Laplacian Solvers. APPROX-RANDOM (2017)
François Le Gall, Shogo Nakajima
Multiparty Quantum Communication Complexity of Triangle Finding. TQC (2017)
Stacey Jeffery, Robin Kothari, François Le Gall, Frédéric Magniez
Improving Quantum Query Complexity of Boolean Matrix Multiplication Using Graph Collision. Algorithmica 76 (1) (2016)
François Le Gall
Further Algebraic Algorithms in the Congested Clique Model and Applications to Graph-Theoretic Problems. DISC (2016)
Stacey Jeffery, François Le Gall
Quantum Communication Complexity of Distributed Set Joins. MFCS (2016)
Stacey Jeffery, François Le Gall
Quantum Communication Complexity of Distributed Set Joins. CoRR (2016)
François Le Gall, Harumichi Nishimura, Seiichiro Tani
Quantum algorithms for finding constant-sized sub-hypergraphs. Theor. Comput. Sci. 609 (2016)
François Le Gall, David J. Rosenbaum
On the Group and Color Isomorphism Problems. CoRR (2016)
François Le Gall
Further Algebraic Algorithms in the Congested Clique Model and Applications to Graph-Theoretic Problems. CoRR (2016)
François Le Gall
Solving Laplacian Systems in Logarithmic Space. CoRR (2016)
Hirotada Kobayashi, François Le Gall, Harumichi Nishimura
Generalized Quantum Arthur-Merlin Games. Computational Complexity Conference (2015)
Andris Ambainis, Yuval Filmus, François Le Gall
Fast Matrix Multiplication: Limitations of the Coppersmith-Winograd Method. STOC (2015)
François Le Gall, Shogo Nakajima
Quantum Algorithm for Triangle Finding in Sparse Graphs. ISAAC (2015)
François Le Gall, Shogo Nakajima
Quantum Algorithm for Triangle Finding in Sparse Graphs. CoRR (2015)
Hirotada Kobayashi, François Le Gall, Harumichi Nishimura
Stronger Methods of Making Quantum Interactive Proofs Perfectly Complete. SIAM J. Comput. 44 (2) (2015)
Andris Ambainis, Yuval Filmus, François Le Gall
Fast Matrix Multiplication: Limitations of the Laser Method. Electron. Colloquium Comput. Complex. 21 (2014)
François Le Gall
Quantum Complexity of Boolean Matrix Multiplication and Related Problems. Computing with New Resources (2014)
François Le Gall
Algebraic complexity theory and matrix multiplication. ISSAC (2014)
François Le Gall
Powers of Tensors and Fast Matrix Multiplication. CoRR (2014)
François Le Gall
Powers of tensors and fast matrix multiplication. ISSAC (2014)
Andris Ambainis, Yuval Filmus, François Le Gall
Fast Matrix Multiplication: Limitations of the Laser Method. CoRR (2014)
François Le Gall
Improved Quantum Algorithm for Triangle Finding via Combinatorial Arguments. CoRR (2014)
François Le Gall, Harumichi Nishimura
Quantum Algorithms for Matrix Products over Semirings. SWAT (2014)
François Le Gall
Improved Quantum Algorithm for Triangle Finding via Combinatorial Arguments. FOCS (2014)
François Le Gall, Harumichi Nishimura, Seiichiro Tani
Quantum Algorithms for Finding Constant-Sized Sub-hypergraphs. COCOON (2014)
Iordanis Kerenidis, Mathieu Laurière, François Le Gall, Mathys Rennela
Privacy in Quantum Communication Complexity. CoRR (2014)

François Le Gall.css-eqlu8i{font-size:small;padding-left:4px;}

Publication Activity (10 Years)

Top Topics

Top Venues

François Le Gall