FG
François Le Gall
quant-phcs.CCcs.DScs.DCmath.GRcs.SCcs.DMcs.ITmath.ITcs.DB
On Valency
published · living versionsW_73tn2awr·v1 · currentpublished
Breaking the quantum barriers for Graph Collision
with Arjan Cornelissen, Amin Shiraz Gilani, Shiva Kintali, Subhasree Patro +1
1 version
Preprints & journals
78 papers in the corpus · 2004–2026An Entropy-Governed Speedup for Quantum Algorithms on Local Hamiltonians2605.18241v1 · Ranitha Mataraarachchi, Francois Le Gall, Suguru Tamaki2026 · 0 citationsarXiv
Fine-Grained Complexity for Quantum Problems from Size-Preserving Circuit-to-Hamiltonian Constructions2602.14379v2 · Nai-Hui Chia, Atsuya Hasegawa, Francois Le Gall et al.2026 · 0 citations41st Computational Complexity Conference (CCC 2026)
A slightly improved upper bound for quantum statistical zero-knowledge2512.11597v2 · Francois Le Gall, Yupan Liu, Qisheng Wang2025 · 0 citationsProceedings of the 51st International Symposium on Mathematical Foundations of Computer Science (MFCS 2026), pp. 12:1-12:20, 2026
A Simpler Exponential-Time Approximation Algorithm for MAX-k-SAT2510.18164v1 · Harry Buhrman, Sevag Gharibian, Zeph Landau et al.2025 · 0 citations2026 SIAM Symposium on Simplicity in Algorithms (SOSA), pg. 247-253
Exponential Quantum Advantage for Message Complexity in Distributed Algorithms2510.01657v1 · Francois Le Gall, Mael Luce, Joseph Marchand et al.2025 · 0 citationsarXiv
Beating the Natural Grover Bound for Low-Energy Estimation and State Preparation.40758028 · Buhrman, Harry, Gharibian, Sevag, Landau, Zeph et al.2025 · 3 citationsPhysical review letters. 2025;135(3):030601
Maximum Separation of Quantum Communication Complexity With and Without Shared Entanglement2505.16457v3 · Atsuya Hasegawa, Francois Le Gall, Augusto Modanese2025 · 0 citationsarXiv
Group Order is in QCMA2504.05547v2 · Francois Le Gall, Harumichi Nishimura, Dhara Thakkar2025 · 0 citationsarXiv
Does there exist a quantum fingerprinting protocol without coherent measurements?2502.13427v1 · Atsuya Hasegawa, Srijita Kundu, Francois Le Gall et al.2025 · 0 citationsarXiv
Quantum Simultaneous Protocols without Public Coins using Modified Equality Queries2412.08091v1 · Francois Le Gall, Oran Nadler, Harumichi Nishimura et al.2024 · 0 citationsarXiv
Distributed Quantum Advantage for Local Problems2411.03240v1 · Alkida Balliu, Sebastian Brandt, Xavier Coiteux-Roy et al.2024 · 3 citationsarXiv
Classical versus quantum queries in quantum PCPs with classical proofs2411.00946v1 · Harry Buhrman, Francois Le Gall, Jordi Weggemans2024 · 0 citationsarXiv
Classical Algorithms for Constant Approximation of the Ground State Energy of Local Hamiltonians2410.21833v3 · Francois Le Gall2024 · 1 citationarXiv
Quantum State Synthesis: Relation with Decision Complexity Classes and Impossibility of Synthesis Error Reduction2407.02907v2 · Hugo Delavenne, Francois Le Gall2024 · 0 citationsarXiv
Online Locality Meets Distributed Quantum Computing2403.01903v4 · Amirreza Akbari, Xavier Coiteux-Roy, Francesco d'Amore et al.2024 · 6 citationsarXiv
Space-bounded quantum state testing via space-efficient quantum singular value transformation2308.05079v3 · Francois Le Gall, Yupan Liu, Qisheng Wang2023 · 3 citationsarXiv
No distributed quantum advantage for approximate graph coloring2307.09444v3 · Xavier Coiteux-Roy, Francesco d'Amore, Rishikesh Gajjala et al.2023 · 8 citationsarXiv
Faster Rectangular Matrix Multiplication by Combination Loss Analysis2307.06535v2 · Francois Le Gall2023 · 9 citationsarXiv
Robust Dequantization of the Quantum Singular value Transformation and Quantum Machine Learning Algorithms2304.04932v2 · Francois Le Gall2023 · 6 citationsarXiv
Prior Entanglement Exponentially Improves One-Server Quantum Private Information Retrieval for Quantum Messages2304.05125v1 · Seunghoan Song, Francois Le Gall, Masahito Hayashi2023 · 2 citationsEPJ Quantum Technology, 11, 55 (2024)
Quantum Merlin-Arthur proof systems for synthesizing quantum states2303.01877v4 · Hugo Delavenne, Francois Le Gall, Yupan Liu et al.2023 · 1 citationQuantum 9, 1688 (2025)
Non-trivial lower bound for 3-coloring the ring in the quantum LOCAL model2212.02768v1 · Francois Le Gall, Ansis Rosmanis2022 · 1 citationarXiv
Bounds on oblivious multiparty quantum communication complexity2210.15402v1 · Francois Le Gall, Daiki Suruga2022 · 4 citationsProceedings of the 15th Latin American Theoretical Informatics Symposium (LATIN 2022), pp. 641-657, 2022
Distributed Merlin-Arthur Synthesis of Quantum States and Its Applications2210.01389v2 · Francois Le Gall, Masayuki Miyamoto, Harumichi Nishimura2022 · 4 citationsProceedings of the 48th International Symposium on Mathematical Foundations of Computer Science (MFCS 2023), pp. 63:1-63:15, 2023
Distributed Quantum Interactive Proofs2210.01390v1 · Francois Le Gall, Masayuki Miyamoto, Harumichi Nishimura2022 · 2 citationsProceedings of the 40th International Symposium on Theoretical Aspects of Computer Science (STACS 2023), pp.42:1--42:21, 2023
Improved Hardness Results for the Guided Local Hamiltonian Problem2207.10250v3 · Chris Cade, Marten Folkertsma, Sevag Gharibian et al.2022 · 2 citationsProceedings of the 50th EATCS International Colloquium on Automata, Languages and Programming (ICALP 2023), pp. 32:1-32.19, 2023
An optimal oracle separation of classical and quantum hybrid schemes2205.04633v2 · Atsuya Hasegawa, Francois Le Gall2022 · 4 citationsProceedings of the 33rd International Symposium on Algorithms and Computation (ISAAC 2022), pp. 6:1-6:14, 2022
Quantum Approximate Counting for Markov Chains and Application to Collision Counting2204.02552v2 · Francois Le Gall, Iu-Iong Ng2022 · 0 citationsQuantum Information and Computation, Vol.22 No.15&16, pp. 1261-1279, 2022
Quantum Distributed Algorithms for Detection of Cliques2201.03000v1 · Keren Censor-Hillel, Orr Fischer, Francois Le Gall et al.2022 · 15 citationsarXiv
Dequantizing the Quantum Singular Value Transformation: Hardness and Applications to Quantum Chemistry and the Quantum PCP Conjecture2111.09079v5 · Sevag Gharibian, Francois Le Gall2021 · 12 citationsSIAM Journal on Computing, Vol. 52(4), pp. 1009-1038, 2023
Lower Bounds for Induced Cycle Detection in Distributed Computing2110.00741v1 · Francois Le Gall, Masayuki Miyamoto2021 · 2 citationsarXiv
Test of Quantumness with Small-Depth Quantum Circuits2105.05500v2 · Shuichi Hirahara, Francois Le Gall2021 · 6 citationsProceedings of the 46th International Symposium on Mathematical Foundations of Computer Science (MFCS 2021), pp. 59:1-59:15, 2021
Quantum Logarithmic Space and Post-selection2105.02681v1 · Francois Le Gall, Harumichi Nishimura, Abuzer Yakary\ilmaz2021 · 1 citationProceedings of the 16th Conference on the Theory of Quantum Computation, Communication and Cryptography (TQC 2021), 10:1--10:17, 2021
Quantum Advantage with Shallow Circuits Under Arbitrary Corruption2105.00603v3 · Atsuya Hasegawa, Francois Le Gall2021 · 1 citationProceedings of the 32nd International Symposium on Algorithms and Computation (ISAAC 2021), pp. 74:1-74:16, 2021
Fast Distributed Algorithms for Girth, Cycles and Small Subgraphs2101.07590v1 · Keren Censor-Hillel, Orr Fischer, Tzlil Gonen et al.2021 · 8 citationsarXiv
Tight Distributed Listing of Cliques2011.07405v1 · Keren Censor-Hillel, Yi-Jun Chang, Francois Le Gall et al.2020 · 16 citationsProceedings of the 32nd ACM-SIAM Symposium on Discrete Algorithms (SODA 2021), 2878-2891, 2021
Quantum Meets Fine-grained Complexity: Sublinear Time Quantum Algorithms for String Problems2010.12122v2 · Francois Le Gall, Saeed Seddighin2020 · 27 citationsAlgorithmica, Vol. 85(5), pp. 1251-1286, 2023
On Distributed Listing of Cliques2007.05316v1 · Keren Censor-Hillel, Francois Le Gall, Dean Leitersdorf2020 · 22 citationsProceedings of the 39th ACM Symposium on Principles of Distributed Computing (PODC 2020), pp. 474-482, 2020
Quantum Communication Complexity of Distribution Testing2006.14870v1 · Aleksandrs Belovs, Arturo Castellanos, Francois Le Gall et al.2020 · 1 citationQuantum Information and Computation, Vol.21 No.15&16, pp.1261-1273, 2021
Barriers for rectangular matrix multiplication2003.03019v2 · Matthias Christandl, Francois Le Gall, Vladimir Lysikov et al.2020 · 7 citationscomput. complex. 34, 4 (2025)
Distributed Quantum Proofs for Replicated Data2002.10018v2 · Pierre Fraigniaud, Francois Le Gall, Harumichi Nishimura et al.2020 · 2 citationsProceedings of the 12th Innovations in Theoretical Computer Science Conference (ITCS2021), pp. 28:1-28:20, 2021
Quantum-Inspired Classical Algorithms for Singular Value Transformation1910.05699v3 · Dhawal Jethwani, Francois Le Gall, Sanjay K. Singh2019 · 14 citationsProceedings of the 45th International Symposium on Mathematical Foundations of Computer Science (MFCS 2020), 53:1-53:14, 2020
Quantum Distributed Algorithm for Triangle Finding in the CONGEST Model1908.11488v2 · Taisuke Izumi, Francois Le Gall, Fr'ed'eric Magniez2019 · 18 citationsProceedings of the 37th International Symposium on Theoretical Aspects of Computer Science (STACS 2020), 23:1-23:13, 2020
Quantum Speedup for the Minimum Steiner Tree Problem1904.03581v3 · Masayuki Miyamoto, Masakazu Iwamura, Koichi Kise et al.2019 · 7 citationsarXiv
Average-Case Quantum Advantage with Shallow Circuits1810.12792v4 · Francois Le Gall2018 · 17 citationsProceedings of the 34th Computational Complexity Conference (CCC 2019), 21:1-21:20, 2019
Quantum Advantage for the LOCAL Model in Distributed Computing1810.10838v1 · Francois Le Gall, Harumichi Nishimura, Ansis Rosmanis2018 · 15 citationsProceedings of the 36th International Symposium on Theoretical Aspects of Computer Science (STACS 2019), 49:1-49:14, 2019
Interactive Proofs with Polynomial-Time Quantum Prover for Computing the Order of Solvable Groups1805.03385v1 · Francois Le Gall, Tomoyuki Morimae, Harumichi Nishimura et al.2018 · 1 citationProceedings of the 43rd International Symposium on Mathematical Foundations of Computer Science (MFCS 2018), 26:1-26:13, 2018
Sublinear-Time Quantum Computation of the Diameter in CONGEST Networks1804.02917v3 · Francois Le Gall, Fr'ed'eric Magniez2018 · 36 citationsProceedings of the 37th ACM Symposium on Principles of Distributed Computing (PODC 2018), pp. 337-346, 2018
Improved Rectangular Matrix Multiplication using Powers of the Coppersmith-Winograd Tensor1708.05622v2 · Francois Le Gall, Florent Urrutia2017 · 21 citationsProceedings of the 29th ACM-SIAM Symposium on Discrete Algorithms (SODA 2018), pp. 1029-1046, 2018
Triangle Finding and Listing in CONGEST Networks1705.09061v1 · Taisuke Izumi, Francois Le Gall2017 · 33 citationsProceedings of the 36th ACM Symposium on Principles of Distributed Computing (PODC 2017), pp. 381-389, 2017
Career total: 113 works. 78 are in this corpus.Showing the 50 most recent.
Profile built from the corpus for this byline.
Author records are still filling in while the Hub is in alpha. If this is your page, you'll be able to claim it soon. Spot a mistake? Tell us.