François Le Gall

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

2023

Dequantizing the Quantum Singular Value Transformation: Hardness and Applications to Quantum Chemistry and the Quantum PCP Conjecture.

[BibT_eX]

[DOI]

Sevag Gharibian

SIAM J. Comput., August, 2023

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

[BibT_eX]

[DOI]

Saeed Seddighin

Algorithmica, May, 2023

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

[BibT_eX]

[DOI]

Yupan Liu

Qisheng Wang

Electron. Colloquium Comput. Complex., 2023

No distributed quantum advantage for approximate graph coloring.

[BibT_eX]

[DOI]

CoRR, 2023

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

[BibT_eX]

[DOI]

CoRR, 2023

Quantum Merlin-Arthur proof systems for synthesizing quantum states.

[BibT_eX]

[DOI]

CoRR, 2023

Distributed Quantum Interactive Proofs.

[BibT_eX]

[DOI]

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

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

[BibT_eX]

[DOI]

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

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

[BibT_eX]

[DOI]

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

Improved Hardness Results for the Guided Local Hamiltonian Problem.

[BibT_eX]

[DOI]

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

2022

Quantum approximate counting for Markov chains and collision counting.

[BibT_eX]

[DOI]

Iu-Iong Ng

Quantum Inf. Comput., 2022

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

[BibT_eX]

[DOI]

Ansis Rosmanis

CoRR, 2022

Improved Hardness Results for the Guided Local Hamiltonian Problem.

[BibT_eX]

[DOI]

CoRR, 2022

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

[BibT_eX]

[DOI]

Iu-Iong Ng

CoRR, 2022

Brief Announcement: Distributed Quantum Interactive Proofs.

[BibT_eX]

[DOI]

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

Bounds on Oblivious Multiparty Quantum Communication Complexity.

[BibT_eX]

[DOI]

Daiki Suruga

Proceedings of the LATIN 2022: Theoretical Informatics, 2022

An Optimal Oracle Separation of Classical and Quantum Hybrid Schemes.

[BibT_eX]

[DOI]

Atsuya Hasegawa

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

Quantum Distributed Algorithms for Detection of Cliques.

[BibT_eX]

[DOI]

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

2021

Quantum communication complexity of distribution testing.

[BibT_eX]

[DOI]

Alexander A. Sherstov

Quantum Inf. Comput., 2021

Quantum Logarithmic Space and Post-Selection.

[BibT_eX]

[DOI]

Abuzer Yakaryilmaz

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

Tight Distributed Listing of Cliques.

[BibT_eX]

[DOI]

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

Test of Quantumness with Small-Depth Quantum Circuits.

[BibT_eX]

[DOI]

Shuichi Hirahara

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

Quantum Advantage with Shallow Circuits Under Arbitrary Corruption.

[BibT_eX]

[DOI]

Atsuya Hasegawa

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

Lower Bounds for Induced Cycle Detection in Distributed Computing.

[BibT_eX]

[DOI]

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

Distributed Quantum Proofs for Replicated Data.

[BibT_eX]

[DOI]

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

2020

Barriers for Rectangular Matrix Multiplication.

[BibT_eX]

[DOI]

Electron. Colloquium Comput. Complex., 2020

Brief Announcement: Distributed Quantum Proofs for Replicated Data.

[BibT_eX]

[DOI]

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

Fast Distributed Algorithms for Girth, Cycles and Small Subgraphs.

[BibT_eX]

[DOI]

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

Quantum Distributed Algorithm for Triangle Finding in the CONGEST Model.

[BibT_eX]

[DOI]

Taisuke Izumi

Frédéric Magniez

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

On Distributed Listing of Cliques.

[BibT_eX]

[DOI]

Keren Censor-Hillel

Dean Leitersdorf

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

Quantum-Inspired Classical Algorithms for Singular Value Transformation.

[BibT_eX]

[DOI]

Dhawal Jethwani

Sanjay Kumar Singh

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

Quantum Speedup for the Minimum Steiner Tree Problem.

[BibT_eX]

[DOI]

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

2019

Generalized Quantum Arthur-Merlin Games.

[BibT_eX]

[DOI]

Hirotada Kobayashi

SIAM J. Comput., 2019

Quantum Query Complexity of Unitary Operator Discrimination.

[BibT_eX]

[DOI]

IEICE Trans. Inf. Syst., 2019

Quantum Advantage for the LOCAL Model in Distributed Computing.

[BibT_eX]

[DOI]

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.

[BibT_eX]

[DOI]

Taisuke Izumi

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

Average-Case Quantum Advantage with Shallow Circuits.

[BibT_eX]

[DOI]

Proceedings of the 34th Computational Complexity Conference, 2019

2018

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

[BibT_eX]

[DOI]

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.

[BibT_eX]

[DOI]

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.

[BibT_eX]

[DOI]

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.

[BibT_eX]

[DOI]

Tomoyuki Morimae

Quantum Inf. Comput., 2017

Probabilistic logarithmic-space algorithms for Laplacian solvers.

[BibT_eX]

[DOI]

Dean Doron

Amnon Ta-Shma

Electron. Colloquium Comput. Complex., 2017

Quantum Algorithms for Matrix Products over Semirings.

[BibT_eX]

[DOI]

Chic. J. Theor. Comput. Sci., 2017

Quantum Algorithm for Triangle Finding in Sparse Graphs.

[BibT_eX]

[DOI]

Shogo Nakajima

Algorithmica, 2017

Multiparty Quantum Communication Complexity of Triangle Finding.

[BibT_eX]

[DOI]

Shogo Nakajima

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

Triangle Finding and Listing in CONGEST Networks.

[BibT_eX]

[DOI]

Taisuke Izumi

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

2016

Quantum algorithms for finding constant-sized sub-hypergraphs.

[BibT_eX]

[DOI]

Seiichiro Tani

Theor. Comput. Sci., 2016

Information cost of quantum communication protocols.

[BibT_eX]

[DOI]

Quantum Inf. Comput., 2016

Modified group non-membership is in AWPP.

[BibT_eX]

[DOI]

Tomoyuki Morimae

CoRR, 2016

On the Group and Color Isomorphism Problems.

[BibT_eX]

[DOI]

David J. Rosenbaum

CoRR, 2016

Solving Laplacian Systems in Logarithmic Space.

[BibT_eX]

[DOI]

CoRR, 2016

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

[BibT_eX]

[DOI]

Algorithmica, 2016

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

[BibT_eX]

[DOI]

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

Quantum Communication Complexity of Distributed Set Joins.

[BibT_eX]

[DOI]

Stacey Jeffery

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

2015

Stronger Methods of Making Quantum Interactive Proofs Perfectly Complete.

[BibT_eX]

[DOI]

Hirotada Kobayashi

SIAM J. Comput., 2015

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

[BibT_eX]

[DOI]

Andris Ambainis

Yuval Filmus

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

2014

Fast Matrix Multiplication: Limitations of the Laser Method.

[BibT_eX]

[DOI]

Andris Ambainis

Yuval Filmus

Electron. Colloquium Comput. Complex., 2014

Privacy in Quantum Communication Complexity.

[BibT_eX]

[DOI]

CoRR, 2014

Powers of tensors and fast matrix multiplication.

[BibT_eX]

[DOI]

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

Algebraic complexity theory and matrix multiplication.

[BibT_eX]

[DOI]

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

Improved Quantum Algorithm for Triangle Finding via Combinatorial Arguments.

[BibT_eX]

[DOI]

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

Quantum Complexity of Boolean Matrix Multiplication and Related Problems.

[BibT_eX]

[DOI]

Proceedings of the Computing with New Resources, 2014

2013

Quantum weakly nondeterministic communication complexity.

[BibT_eX]

[DOI]

Theor. Comput. Sci., 2013

Property testing for cyclic groups and beyond.

[BibT_eX]

[DOI]

Yuichi Yoshida

J. Comb. Optim., 2013

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

[BibT_eX]

[DOI]

Seiichiro Tani

CoRR, 2013

2012

Quantum Private Information Retrieval with Sublinear Communication Complexity.

[BibT_eX]

[DOI]

Theory Comput., 2012

On QMA protocols with two short quantum proofs.

[BibT_eX]

[DOI]

Shota Nakagawa

Quantum Inf. Comput., 2012

On the distance between non-isomorphic groups.

[BibT_eX]

[DOI]

Gábor Ivanyos

Yuichi Yoshida

Eur. J. Comb., 2012

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

[BibT_eX]

[DOI]

CoRR, 2012

Reconstructing Strings from Substrings with Quantum Queries.

[BibT_eX]

[DOI]

Proceedings of the Algorithm Theory - SWAT 2012, 2012

Improved output-sensitive quantum algorithms for Boolean matrix multiplication.

[BibT_eX]

[DOI]

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

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

[BibT_eX]

[DOI]

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

Faster Algorithms for Rectangular Matrix Multiplication.

[BibT_eX]

[DOI]

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

2011

The One-Way Communication Complexity of Subgroup Membership.

[BibT_eX]

[DOI]

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

Quantum Property Testing of Group Solvability.

[BibT_eX]

[DOI]

Yoshifumi Inui

Algorithmica, 2011

Constructing quantum network coding schemes from classical nonlinear protocols.

[BibT_eX]

[DOI]

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

2010

The quantum query complexity of certification.

[BibT_eX]

[DOI]

Quantum Inf. Comput., 2010

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

[BibT_eX]

[DOI]

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

Perfect quantum network communication protocol based on classical network coding.

[BibT_eX]

[DOI]

Proceedings of the IEEE International Symposium on Information Theory, 2010

2009

Exponential Separation of Quantum and Classical Online Space Complexity.

[BibT_eX]

[DOI]

Theory Comput. Syst., 2009

The One-Way Communication Complexity of Group Membership

[BibT_eX]

[DOI]

CoRR, 2009

Efficient Isomorphism Testing for a Class of Group Extensions.

[BibT_eX]

[DOI]

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

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

[BibT_eX]

[DOI]

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

2007

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

[BibT_eX]

[DOI]

Yoshifumi Inui