research
∙
12/06/2022
Quantum Worst-Case to Average-Case Reductions for All Linear Problems
We study the problem of designing worst-case to average-case reductions ...
share
research
∙
02/18/2022
Worst-Case to Average-Case Reductions via Additive Combinatorics
We present a new framework for designing worst-case to average-case redu...
research
∙
08/12/2021
Derandomization of Cell Sampling
Since 1989, the best known lower bound on static data structures was Sie...
research
∙
09/15/2020
Relaxed Locally Correctable Codes with Improved Parameters
Locally decodable codes (LDCs) are error-correcting codes C : Σ^k →Σ^n t...
research
∙
09/10/2020
Toward Probabilistic Checking against Non-Signaling Strategies with Constant Locality
Non-signaling strategies are a generalization of quantum strategies that...
research
∙
05/27/2019
On Mappings on the Hypercube with Small Average Stretch
Let A ⊆{0,1}^n be a set of size 2^n-1, and let ϕ{0,1}^n-1→ A be a biject...
research
∙
09/08/2018
Multitasking Capacity: Hardness Results and Improved Constructions
We consider the problem of determining the maximal α∈ (0,1] such that ev...
research
∙
01/10/2018
An Entropy Lower Bound for Non-Malleable Extractors
A (k,ε)-non-malleable extractor is a function nmExt : {0,1}^n ×{0,1}^d ...
research
∙
09/07/2017
