research
∙
02/20/2023
A Qubit, a Coin, and an Advice String Walk Into a Relational Problem
Relational problems (those with many possible valid outputs) are differe...
share
research
∙
02/06/2023
Noisy decoding by shallow circuits with parities: classical and quantum
We consider the problem of decoding corrupted error correcting codes wit...
research
∙
07/22/2022
Matching Triangles and Triangle Collection: Hardness based on a Weak Quantum Conjecture
Classically, for many computational problems one can conclude time lower...
research
∙
03/10/2022
Memory Compression with Quantum Random-Access Gates
In the classical RAM, we have the following useful property. If we have ...
research
∙
06/03/2021
Limits of quantum speed-ups for computational geometry and other problems: Fine-grained complexity via quantum walks
Many computational problems are subject to a quantum speed-up: one might...
research
∙
11/13/2019
The Quantum Strong Exponential-Time Hypothesis
The strong exponential-time hypothesis (SETH) is a commonly used conject...
research
∙
12/21/2018