research
∙
01/09/2022
Locality-Preserving Hashing for Shifts with Connections to Cryptography
Can we sense our location in an unfamiliar environment by taking a subli...
share
research
∙
10/31/2021
Fine-Grained Cryptanalysis: Tight Conditional Bounds for Dense k-SUM and k-XOR
An average-case variant of the k-SUM conjecture asserts that finding k n...
research
∙
08/09/2020
Consistent High Dimensional Rounding with Side Information
In standard rounding, we want to map each value X in a large continuous ...
research
∙
11/09/2019
Quantum speedups need structure
We prove the following conjecture, raised by Aaronson and Ambainis in 20...
research
∙
01/25/2019
A structure theorem for almost low-degree functions on the slice
The Fourier-Walsh expansion of a Boolean function f {0,1}^n →{0,1} is it...
research
∙
10/20/2017
Biased halfspaces, noise sensitivity, and relative Chernoff inequalities (extended version)
In analysis of Boolean functions, a halfspace is a function f:{-1,1}^n →...
research
∙
05/25/2011