François Le Gall

171 papers A* 16A 17B 19Misc 4Journal 106Unranked 8
YearRankTypeTitle / Venue / Authors
2026 — conf
A Simpler Exponential-Time Approximation Algorithm for MAX-k-SAT.
SOSA
Harry Buhrman, Sevag Gharibian, Zeph Landau, François Le Gall, Norbert Schuch, Suguru Tamaki
2026 J jnl
Fine-Grained Complexity for Quantum Problems from Size-Preserving Circuit-to-Hamiltonian Constructions.
CoRR
Nai-Hui Chia, Atsuya Hasegawa, François Le Gall, Yu-Ching Shen
2025 J jnl
A Simpler Exponential-Time Approximation Algorithm for MAX-k-SAT.
CoRR
Harry Buhrman, Sevag Gharibian, Zeph Landau, François Le Gall, Norbert Schuch, Suguru Tamaki
2025 J jnl
A slightly improved upper bound for quantum statistical zero-knowledge.
CoRR
François Le Gall, Yupan Liu, Qisheng Wang
2025 J jnl
Barriers for rectangular matrix multiplication.
Comput. Complex.
Matthias Christandl, François Le Gall, Vladimir Lysikov, Jeroen Zuiddam
2025 A conf
Classical Algorithms for Constant Approximation of the Ground State Energy of Local Hamiltonians.
ESA
François Le Gall
2025 J jnl
Correction: Robust dequantization of the quantum singular value transformation and quantum machine learning algorithms.
Comput. Complex.
François Le Gall
2025 J jnl
Dequantization and Hardness of Spectral Sum Estimation.
CoRR
Roman Edenhofer, Atsuya Hasegawa, François Le Gall
2025 A* conf
Distributed Quantum Advantage for Local Problems.
STOC
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
2025 J jnl
Does there exist a quantum fingerprinting protocol without coherent measurements?
CoRR
Atsuya Hasegawa, Srijita Kundu, François Le Gall, Harumichi Nishimura, Qisheng Wang
2025 J jnl
Exponential Quantum Advantage for Message Complexity in Distributed Algorithms.
CoRR
François Le Gall, Maël Luce, Joseph Marchand, Mathieu Roget
2025 A* conf
Group Order is in QCMA.
FOCS
François Le Gall, Harumichi Nishimura, Dhara Thakkar
2025 J jnl
Group Order is in QCMA.
CoRR
François Le Gall, Harumichi Nishimura, Dhara Thakkar
2025 J jnl
Maximum Separation of Quantum Communication Complexity With and Without Shared Entanglement.
CoRR
Atsuya Hasegawa, François Le Gall, Augusto Modanese
2025 A* conf
Online Locality Meets Distributed Quantum Computing.
STOC
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
2025 J jnl
Quantum Merlin-Arthur proof systems for synthesizing quantum states.
Quantum
Hugo Delavenne, François Le Gall, Yupan Liu, Masayuki Miyamoto
2025 J jnl
Robust Dequantization of the Quantum Singular Value Transformation and Quantum Machine Learning Algorithms.
Comput. Complex.
François Le Gall
2025 A conf
Space-Bounded Quantum Interactive Proof Systems.
CCC
François Le Gall, Yupan Liu, Harumichi Nishimura, Qisheng Wang
2024 J jnl
Beating Grover search for low-energy estimation and state preparation.
CoRR
Harry Buhrman, Sevag Gharibian, Zeph Landau, François Le Gall, Norbert Schuch, Suguru Tamaki
2024 J jnl
Classical Algorithms for Constant Approximation of the Ground State Energy of Local Hamiltonians.
CoRR
François Le Gall
2024 J jnl
Classical versus quantum queries in quantum PCPs with classical proofs.
CoRR
Harry Buhrman, François Le Gall, Jordi Weggemans
2024 J jnl
Distributed Quantum Advantage for Local Problems.
CoRR
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
2024 A* conf
Faster Rectangular Matrix Multiplication by Combination Loss Analysis.
SODA
François Le Gall
2024 A* conf
No Distributed Quantum Advantage for Approximate Graph Coloring.
STOC
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
2024 J jnl
Online Locality Meets Distributed Quantum Computing.
CoRR
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
2024 B conf
Quantum Simultaneous Protocols Without Public Coins Using Modified Equality Queries.
OPODIS
François Le Gall, Oran Nadler, Harumichi Nishimura, Rotem Oshman
2024 J jnl
Quantum Simultaneous Protocols without Public Coins using Modified Equality Queries.
CoRR
François Le Gall, Oran Nadler, Harumichi Nishimura, Rotem Oshman
2024 J jnl
Quantum State Synthesis: Relation with Decision Complexity Classes and Impossibility of Synthesis Error Reduction.
CoRR
Hugo Delavenne, François Le Gall
2024 J jnl
Quantum state synthesis: relation with decision complexity classes and impossibility of error reduction.
Quantum Inf. Comput.
Hugo Delavenne, François Le Gall
2024 J jnl
Space-bounded quantum interactive proof systems.
CoRR
François Le Gall, Yupan Liu, Harumichi Nishimura, Qisheng Wang
2024 J jnl
Space-bounded quantum interactive proof systems.
Electron. Colloquium Comput. Complex.
François Le Gall, Yupan Liu, Harumichi Nishimura, Qisheng Wang
2023 J jnl
Dequantizing the Quantum Singular Value Transformation: Hardness and Applications to Quantum Chemistry and the Quantum PCP Conjecture.
SIAM J. Comput.
Sevag Gharibian, François Le Gall
2023 B conf
Distributed Merlin-Arthur Synthesis of Quantum States and Its Applications.
MFCS
François Le Gall, Masayuki Miyamoto, Harumichi Nishimura
2023 A conf
Distributed Quantum Interactive Proofs.
STACS
François Le Gall, Masayuki Miyamoto, Harumichi Nishimura
2023 J jnl
Faster Rectangular Matrix Multiplication by Combination Loss Analysis.
CoRR
François Le Gall
2023 A* conf
Improved Hardness Results for the Guided Local Hamiltonian Problem.
ICALP
Chris Cade, Marten Folkertsma, Sevag Gharibian, Ryu Hayakawa, François Le Gall, Tomoyuki Morimae, Jordi Weggemans
2023 J jnl
No distributed quantum advantage for approximate graph coloring.
CoRR
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
2023 B conf
Quantum Distributed Computing: Potential and Limitations (Invited Talk).
OPODIS
François Le Gall
2023 J jnl
Quantum Meets Fine-Grained Complexity: Sublinear Time Quantum Algorithms for String Problems.
Algorithmica
François Le Gall, Saeed Seddighin
2023 J jnl
Quantum Merlin-Arthur proof systems for synthesizing quantum states.
CoRR
Hugo Delavenne, François Le Gall, Yupan Liu, Masayuki Miyamoto
2023 J jnl
Robust Dequantization of the Quantum Singular value Transformation and Quantum Machine Learning Algorithms.
CoRR
François Le Gall
2023 J jnl
Space-bounded quantum state testing via space-efficient quantum singular value transformation.
CoRR
François Le Gall, Yupan Liu, Qisheng Wang
2023 J jnl
Space-bounded quantum state testing via space-efficient quantum singular value transformation.
Electron. Colloquium Comput. Complex.
François Le Gall, Yupan Liu, Qisheng Wang
2022 — ed.
17th Conference on the Theory of Quantum Computation, Communication and Cryptography, TQC 2022, Urbana Champaign, Illinois, USA, July 11-15, 2022
TQC
François Le Gall, Tomoyuki Morimae
2022 B conf
An Optimal Oracle Separation of Classical and Quantum Hybrid Schemes.
ISAAC
Atsuya Hasegawa, François Le Gall
2022 J jnl
An optimal oracle separation of classical and quantum hybrid schemes.
CoRR
Atsuya Hasegawa, François Le Gall
2022 B conf
Bounds on Oblivious Multiparty Quantum Communication Complexity.
LATIN
François Le Gall, Daiki Suruga
2022 A conf
Brief Announcement: Distributed Quantum Interactive Proofs.
DISC
François Le Gall, Masayuki Miyamoto, Harumichi Nishimura
2022 A* conf
Dequantizing the Quantum singular value transformation: hardness and applications to Quantum chemistry and the Quantum PCP conjecture.
STOC
Sevag Gharibian, François Le Gall
2022 J jnl
Distributed Merlin-Arthur Synthesis of Quantum States and Its Applications.
CoRR
François Le Gall, Masayuki Miyamoto, Harumichi Nishimura
2022 J jnl
Distributed Quantum Interactive Proofs.
CoRR
François Le Gall, Masayuki Miyamoto, Harumichi Nishimura
2022 J jnl
Improved Hardness Results for the Guided Local Hamiltonian Problem.
CoRR
Sevag Gharibian, Ryu Hayakawa, François Le Gall, Tomoyuki Morimae
2022 J jnl
Non-trivial lower bound for 3-coloring the ring in the quantum LOCAL model.
CoRR
François Le Gall, Ansis Rosmanis
2022 J jnl
Quantum Approximate Counting for Markov Chains and Application to Collision Counting.
CoRR
François Le Gall, Iu-Iong Ng
2022 A conf
Quantum Distributed Algorithms for Detection of Cliques.
ITCS
Keren Censor-Hillel, Orr Fischer, François Le Gall, Dean Leitersdorf, Rotem Oshman
2022 J jnl
Quantum Distributed Algorithms for Detection of Cliques.
CoRR
Keren Censor-Hillel, Orr Fischer, François Le Gall, Dean Leitersdorf, Rotem Oshman
2022 A conf
Quantum Meets Fine-Grained Complexity: Sublinear Time Quantum Algorithms for String Problems.
ITCS
François Le Gall, Saeed Seddighin
2021 J jnl
Dequantizing the Quantum Singular Value Transformation: Hardness and Applications to Quantum Chemistry and the Quantum PCP Conjecture.
CoRR
Sevag Gharibian, François Le Gall
2021 A conf
Distributed Quantum Proofs for Replicated Data.
ITCS
Pierre Fraigniaud, François Le Gall, Harumichi Nishimura, Ami Paz
2021 J jnl
Fast Distributed Algorithms for Girth, Cycles and Small Subgraphs.
CoRR
Keren Censor-Hillel, Orr Fischer, Tzlil Gonen, François Le Gall, Dean Leitersdorf, Rotem Oshman
2021 B conf
Lower Bounds for Induced Cycle Detection in Distributed Computing.
ISAAC
François Le Gall, Masayuki Miyamoto
2021 J jnl
Lower Bounds for Induced Cycle Detection in Distributed Computing.
CoRR
François Le Gall, Masayuki Miyamoto
2021 B conf
Quantum Advantage with Shallow Circuits Under Arbitrary Corruption.
ISAAC
Atsuya Hasegawa, François Le Gall
2021 J jnl
Quantum Advantage with Shallow Circuits under Arbitrary Corruption.
CoRR
Atsuya Hasegawa, François Le Gall
2021 — conf
Quantum Logarithmic Space and Post-Selection.
TQC
François Le Gall, Harumichi Nishimura, Abuzer Yakaryilmaz
2021 J jnl
Quantum Logarithmic Space and Post-selection.
CoRR
François Le Gall, Harumichi Nishimura, Abuzer Yakaryilmaz
2021 B conf
Test of Quantumness with Small-Depth Quantum Circuits.
MFCS
Shuichi Hirahara, François Le Gall
2021 J jnl
Test of Quantumness with Small-Depth Quantum Circuits.
CoRR
Shuichi Hirahara, François Le Gall
2021 A* conf
Tight Distributed Listing of Cliques.
SODA
Keren Censor-Hillel, Yi-Jun Chang, François Le Gall, Dean Leitersdorf
2020 J jnl
Barriers for Rectangular Matrix Multiplication.
Electron. Colloquium Comput. Complex.
Matthias Christandl, François Le Gall, Vladimir Lysikov, Jeroen Zuiddam
2020 J jnl
Barriers for rectangular matrix multiplication.
CoRR
Matthias Christandl, François Le Gall, Vladimir Lysikov, Jeroen Zuiddam
2020 A conf
Brief Announcement: Distributed Quantum Proofs for Replicated Data.
DISC
Pierre Fraigniaud, François Le Gall, Harumichi Nishimura, Ami Paz
2020 J jnl
Distributed Quantum Proofs for Replicated Data.
CoRR
Pierre Fraigniaud, François Le Gall, Harumichi Nishimura, Ami Paz
2020 A conf
Fast Distributed Algorithms for Girth, Cycles and Small Subgraphs.
DISC
Keren Censor-Hillel, Orr Fischer, Tzlil Gonen, François Le Gall, Dean Leitersdorf, Rotem Oshman
2020 A* conf
On Distributed Listing of Cliques.
PODC
Keren Censor-Hillel, François Le Gall, Dean Leitersdorf
2020 J jnl
On Distributed Listing of Cliques.
CoRR
Keren Censor-Hillel, François Le Gall, Dean Leitersdorf
2020 J jnl
Quantum Communication Complexity of Distribution Testing.
CoRR
Aleksandrs Belovs, Arturo Castellanos, François Le Gall, Guillaume Malod, Alexander A. Sherstov
2020 A conf
Quantum Distributed Algorithm for Triangle Finding in the CONGEST Model.
STACS
Taisuke Izumi, François Le Gall, Frédéric Magniez
2020 J jnl
Quantum Meets Fine-grained Complexity: Sublinear Time Quantum Algorithms for String Problems.
CoRR
François Le Gall, Saeed Seddighin
2020 Misc conf
Quantum Speedup for the Minimum Steiner Tree Problem.
COCOON
Masayuki Miyamoto, Masakazu Iwamura, Koichi Kise, François Le Gall
2020 B conf
Quantum-Inspired Classical Algorithms for Singular Value Transformation.
MFCS
Dhawal Jethwani, François Le Gall, Sanjay Kumar Singh
2020 J jnl
Tight Distributed Listing of Cliques.
CoRR
Keren Censor-Hillel, Yi-Jun Chang, François Le Gall, Dean Leitersdorf
2019 A conf
Average-Case Quantum Advantage with Shallow Circuits.
CCC
François Le Gall
2019 J jnl
Generalized Quantum Arthur-Merlin Games.
SIAM J. Comput.
Hirotada Kobayashi, François Le Gall, Harumichi Nishimura
2019 A conf
Quantum Advantage for the LOCAL Model in Distributed Computing.
STACS
François Le Gall, Harumichi Nishimura, Ansis Rosmanis
2019 J jnl
Quantum Distributed Algorithm for Triangle Finding in the CONGEST Model.
CoRR
Taisuke Izumi, François Le Gall, Frédéric Magniez
2019 A* conf
Quantum Distributed Algorithm for the All-Pairs Shortest Path Problem in the CONGEST-CLIQUE Model.
PODC
Taisuke Izumi, François Le Gall
2019 J jnl
Quantum Distributed Algorithm for the All-Pairs Shortest Path Problem in the CONGEST-CLIQUE Model.
CoRR
Taisuke Izumi, François Le Gall
2019 J jnl
Quantum-Inspired Classical Algorithms for Singular Value Transformation.
CoRR
Dhawal Jethwani, François Le Gall, Sanjay Kumar Singh
2018 J jnl
Average-Case Quantum Advantage with Shallow Circuits.
CoRR
François Le Gall
2018 B conf
Interactive Proofs with Polynomial-Time Quantum Prover for Computing the Order of Solvable Groups.
MFCS
François Le Gall, Tomoyuki Morimae, Harumichi Nishimura, Yuki Takeuchi
2018 J jnl
Interactive Proofs with Polynomial-Time Quantum Prover for Computing the Order of Solvable Groups.
CoRR
François Le Gall, Tomoyuki Morimae, Harumichi Nishimura, Yuki Takeuchi
2018 J jnl
Quantum Advantage for the LOCAL Model in Distributed Computing.
CoRR
François Le Gall, Harumichi Nishimura, Ansis Rosmanis
2018 A* conf
Sublinear-Time Quantum Computation of the Diameter in CONGEST Networks.
PODC
François Le Gall, Frédéric Magniez
2018 J jnl
Sublinear-Time Quantum Computation of the Diameter in CONGEST Networks.
CoRR
François Le Gall, Frédéric Magniez
2017 J jnl
Improved Rectangular Matrix Multiplication using Powers of the Coppersmith-Winograd Tensor.
CoRR
François Le Gall, Florent Urrutia
2017 — conf
Multiparty Quantum Communication Complexity of Triangle Finding.
TQC
François Le Gall, Shogo Nakajima
2017 — conf
Probabilistic Logarithmic-Space Algorithms for Laplacian Solvers.
APPROX-RANDOM
Dean Doron, François Le Gall, Amnon Ta-Shma
2017 J jnl
Quantum Algorithm for Triangle Finding in Sparse Graphs.
Algorithmica
François Le Gall, Shogo Nakajima
2017 J jnl
Quantum Algorithms for Matrix Products over Semirings.
Chic. J. Theor. Comput. Sci.
François Le Gall, Harumichi Nishimura
2017 Misc conf
Quantum Query Complexity of Unitary Operator Discrimination.
COCOON
Akinori Kawachi, Kenichi Kawano, François Le Gall, Suguru Tamaki
2017 A* conf
Triangle Finding and Listing in CONGEST Networks.
PODC
Taisuke Izumi, François Le Gall
2017 J jnl
Triangle Finding and Listing in CONGEST Networks.
CoRR
Taisuke Izumi, François Le Gall
2016 A conf
Further Algebraic Algorithms in the Congested Clique Model and Applications to Graph-Theoretic Problems.
DISC
François Le Gall
2016 J jnl
Further Algebraic Algorithms in the Congested Clique Model and Applications to Graph-Theoretic Problems.
CoRR
François Le Gall
2016 J jnl
Improving Quantum Query Complexity of Boolean Matrix Multiplication Using Graph Collision.
Algorithmica
Stacey Jeffery, Robin Kothari, François Le Gall, Frédéric Magniez
2016 J jnl
On the Group and Color Isomorphism Problems.
CoRR
François Le Gall, David J. Rosenbaum
2016 B conf
Quantum Communication Complexity of Distributed Set Joins.
MFCS
Stacey Jeffery, François Le Gall
2016 J jnl
Quantum Communication Complexity of Distributed Set Joins.
CoRR
Stacey Jeffery, François Le Gall
2016 J jnl
Quantum algorithms for finding constant-sized sub-hypergraphs.
Theor. Comput. Sci.
François Le Gall, Harumichi Nishimura, Seiichiro Tani
2016 J jnl
Solving Laplacian Systems in Logarithmic Space.
CoRR
François Le Gall
2015 A* conf
Fast Matrix Multiplication: Limitations of the Coppersmith-Winograd Method.
STOC
Andris Ambainis, Yuval Filmus, François Le Gall
2015 A conf
Generalized Quantum Arthur-Merlin Games.
CCC
Hirotada Kobayashi, François Le Gall, Harumichi Nishimura
2015 B conf
Quantum Algorithm for Triangle Finding in Sparse Graphs.
ISAAC
François Le Gall, Shogo Nakajima
2015 J jnl
Quantum Algorithm for Triangle Finding in Sparse Graphs.
CoRR
François Le Gall, Shogo Nakajima
2015 J jnl
Stronger Methods of Making Quantum Interactive Proofs Perfectly Complete.
SIAM J. Comput.
Hirotada Kobayashi, François Le Gall, Harumichi Nishimura
2014 B conf
Algebraic complexity theory and matrix multiplication.
ISSAC
François Le Gall
2014 J jnl
Fast Matrix Multiplication: Limitations of the Laser Method.
CoRR
Andris Ambainis, Yuval Filmus, François Le Gall
2014 J jnl
Fast Matrix Multiplication: Limitations of the Laser Method.
Electron. Colloquium Comput. Complex.
Andris Ambainis, Yuval Filmus, François Le Gall
2014 A* conf
Improved Quantum Algorithm for Triangle Finding via Combinatorial Arguments.
FOCS
François Le Gall
2014 J jnl
Improved Quantum Algorithm for Triangle Finding via Combinatorial Arguments.
CoRR
François Le Gall
2014 J jnl
Powers of Tensors and Fast Matrix Multiplication.
CoRR
François Le Gall
2014 B conf
Powers of tensors and fast matrix multiplication.
ISSAC
François Le Gall
2014 J jnl
Privacy in Quantum Communication Complexity.
CoRR
Iordanis Kerenidis, Mathieu Laurière, François Le Gall, Mathys Rennela
2014 Misc conf
Quantum Algorithms for Finding Constant-Sized Sub-hypergraphs.
COCOON
François Le Gall, Harumichi Nishimura, Seiichiro Tani
2014 — conf
Quantum Algorithms for Matrix Products over Semirings.
SWAT
François Le Gall, Harumichi Nishimura
2014 — conf
Quantum Complexity of Boolean Matrix Multiplication and Related Problems.
Computing with New Resources
François Le Gall
2013 J jnl
Generalized Quantum Arthur-Merlin Games.
CoRR
Hirotada Kobayashi, François Le Gall, Harumichi Nishimura
2013 J jnl
Property testing for cyclic groups and beyond.
J. Comb. Optim.
François Le Gall, Yuichi Yoshida
2013 J jnl
Quantum Algorithms for Finding Constant-sized Sub-hypergraphs over 3-uniform Hypergraphs.
CoRR
François Le Gall, Harumichi Nishimura, Seiichiro Tani
2013 J jnl
Quantum Algorithms for Matrix Products over Semirings.
CoRR
François Le Gall, Harumichi Nishimura
2013 J jnl
Quantum weakly nondeterministic communication complexity.
Theor. Comput. Sci.
François Le Gall
2013 A conf
Stronger methods of making quantum interactive proofs perfectly complete.
ITCS
Hirotada Kobayashi, François Le Gall, Harumichi Nishimura
2012 B conf
A Time-Efficient Output-Sensitive Quantum Algorithm for Boolean Matrix Multiplication.
ISAAC
François Le Gall
2012 J jnl
Faster Algorithms for Rectangular Matrix Multiplication
CoRR
François Le Gall
2012 A* conf
Faster Algorithms for Rectangular Matrix Multiplication.
FOCS
François Le Gall
2012 J jnl
Improved Time-Efficient Output-Sensitive Quantum Algorithms for Boolean Matrix Multiplication
CoRR
François Le Gall
2012 A* conf
Improved output-sensitive quantum algorithms for Boolean matrix multiplication.
SODA
François Le Gall
2012 J jnl
On QMA protocols with two short quantum proofs.
Quantum Inf. Comput.
François Le Gall, Shota Nakagawa, Harumichi Nishimura
2012 J jnl
On the distance between non-isomorphic groups.
Eur. J. Comb.
Gábor Ivanyos, François Le Gall, Yuichi Yoshida
2012 J jnl
Quantum Private Information Retrieval with Sublinear Communication Complexity.
Theory Comput.
François Le Gall
2012 J jnl
Reconstructing Strings from Substrings with Quantum Queries
CoRR
Richard Cleve, Kazuo Iwama, François Le Gall, Harumichi Nishimura, Seiichiro Tani, Junichi Teruyama, Shigeru Yamashita
2012 — conf
Reconstructing Strings from Substrings with Quantum Queries.
SWAT
Richard Cleve, Kazuo Iwama, François Le Gall, Harumichi Nishimura, Seiichiro Tani, Junichi Teruyama, Shigeru Yamashita
2012 J jnl
Stronger Methods of Making Quantum Interactive Proofs Perfectly Complete
CoRR
Hirotada Kobayashi, François Le Gall, Harumichi Nishimura
2011 J jnl
On QMA Protocols with Two Short Quantum Proofs
CoRR
François Le Gall, Shota Nakagawa, Harumichi Nishimura
2011 J jnl
On the distance between non-isomorphic groups
CoRR
Gábor Ivanyos, François Le Gall, Yuichi Yoshida
2011 J jnl
Property Testing for Cyclic Groups and Beyond
CoRR
François Le Gall, Yuichi Yoshida
2011 Misc conf
Property Testing for Cyclic Groups and Beyond.
COCOON
François Le Gall, Yuichi Yoshida
2011 J jnl
Quantum Private Information Retrieval with Sublinear Communication Complexity
CoRR
François Le Gall
2011 J jnl
Quantum Property Testing of Group Solvability.
Algorithmica
Yoshifumi Inui, François Le Gall
2011 J jnl
The One-Way Communication Complexity of Subgroup Membership.
Chic. J. Theor. Comput. Sci.
Scott Aaronson, François Le Gall, Alexander Russell, Seiichiro Tani
2010 A conf
An Efficient Quantum Algorithm for Some Instances of the Group Isomorphism Problem.
STACS
François Le Gall
2010 J jnl
An Efficient Quantum Algorithm for some Instances of the Group Isomorphism Problem
CoRR
François Le Gall
2010 J jnl
Constructing Quantum Network Coding Schemes from Classical Nonlinear Protocols
CoRR
Hirotada Kobayashi, François Le Gall, Harumichi Nishimura, Martin Roetteler
2010 B conf
Perfect quantum network communication protocol based on classical network coding.
ISIT
Hirotada Kobayashi, François Le Gall, Harumichi Nishimura, Martin Rötteler
2010 J jnl
The quantum query complexity of certification.
Quantum Inf. Comput.
Andris Ambainis, Andrew M. Childs, François Le Gall, Seiichiro Tani
2009 A conf
Efficient Isomorphism Testing for a Class of Group Extensions.
STACS
François Le Gall
2009 J jnl
Exponential Separation of Quantum and Classical Online Space Complexity.
Theory Comput. Syst.
François Le Gall
2009 J jnl
General Scheme for Perfect Quantum Network Coding with Free Classical Communication
CoRR
Hirotada Kobayashi, François Le Gall, Harumichi Nishimura, Martin Rötteler
2009 — conf
General Scheme for Perfect Quantum Network Coding with Free Classical Communication.
ICALP (1)
Hirotada Kobayashi, François Le Gall, Harumichi Nishimura, Martin Rötteler
2009 J jnl
Perfect Quantum Network Communication Protocol Based on Classical Network Coding
CoRR
Hirotada Kobayashi, François Le Gall, Harumichi Nishimura, Martin Rötteler
2009 J jnl
The One-Way Communication Complexity of Group Membership
CoRR
Scott Aaronson, François Le Gall, Alexander Russell, Seiichiro Tani
2009 J jnl
The quantum query complexity of certification
CoRR
Andris Ambainis, Andrew M. Childs, François Le Gall, Seiichiro Tani
2008 J jnl
Efficient Isomorphism Testing for a Class of Group Extensions
CoRR
François Le Gall
2008 B conf
Quantum Property Testing of Group Solvability.
LATIN
Yoshifumi Inui, François Le Gall
2007 J jnl
Efficient quantum algorithms for the hidden subgroup problem over semi-direct product groups.
Quantum Inf. Comput.
Yoshifumi Inui, François Le Gall
2006 J jnl
Dihedral Hidden Subgroup Problem: A Survey.
Inf. Media Technol.
Hirotada Kobayashi, François Le Gall
2006 J jnl
Exponential Separation of Quantum and Classical Online Space Complexity
CoRR
François Le Gall
2006 B conf
Exponential separation of quantum and classical online space complexity.
SPAA
François Le Gall
2006 B conf
Quantum Weakly Nondeterministic Communication Complexity.
MFCS
François Le Gall
2005 J jnl
Quantum Weakly Nondeterministic Communication Complexity
CoRR
François Le Gall