research
∙
04/27/2023
Logarithmic-Regret Quantum Learning Algorithms for Zero-Sum Games
We propose the first online quantum algorithm for zero-sum games with Õ(...
share
research
∙
11/10/2022
Parameterized Complexity of Weighted Local Hamiltonian Problems and the Quantum Exponential Time Hypothesis
We study a parameterized version of the local Hamiltonian problem, calle...
research
∙
03/15/2022
Quantum Parameterized Complexity
Parameterized complexity theory was developed in the 1990s to enrich the...
research
∙
11/15/2021
Quantum soundness of testing tensor codes
A locally testable code is an error-correcting code that admits very eff...
research
∙
10/05/2020
Symbolic Verification of Quantum Circuits
This short note proposes a symbolic approach for representing and reason...
research
∙
09/27/2020
Quantum soundness of the classical low individual degree test
Low degree tests play an important role in classical complexity theory, ...
research
∙
01/13/2020
MIP*=RE
We show that the class MIP* of languages that can be decided by a classi...
research
∙
11/27/2019
Approximating Permanent of Random Matrices with Vanishing Mean: Made Better and Simpler
The algorithm and complexity of approximating the permanent of a matrix ...
research
∙
06/11/2019
General Linear Group Action on Tensors: A Candidate for Post-Quantum Cryptography
Starting from the one-way group action framework of Brassard and Yung (C...
research
∙
05/30/2018
Quantum proof systems for iterated exponential time, and beyond
We show that any language in nondeterministic time ((...(n))), where the...
research
∙
11/01/2017