research
∙
03/09/2023
Range Avoidance for Constant-Depth Circuits: Hardness and Algorithms
Range Avoidance (AVOID) is a total search problem where, given a Boolean...
share
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 ...
research
∙
11/21/2022
Lattice Problems Beyond Polynomial Time
We study the complexity of lattice problems in a world where algorithms,...
research
∙
05/16/2022
Polynomial formulations as a barrier for reduction-based hardness proofs
The Strong Exponential Time Hypothesis (SETH) asserts that for every ε>0...
research
∙
05/04/2022
Sketching Approximability of (Weak) Monarchy Predicates
We analyze the sketching approximability of constraint satisfaction prob...
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
∙
06/24/2021
Linear Space Streaming Lower Bounds for Approximating CSPs
We consider the approximability of constraint satisfaction problems in t...
research
∙
05/03/2021
Approximability of all finite CSPs in the dynamic streaming setting
A constraint satisfaction problem (CSP), Max-CSP( F), is specified by a ...
research
∙
02/24/2021
Approximability of all Boolean CSPs in the dynamic streaming setting
A Boolean constraint satisfaction problem (CSP), Max-CSP(f), is a maximi...
research
∙
04/24/2020
Optimal Streaming Approximations for all Boolean Max-2CSPs
We prove tight upper and lower bounds on approximation ratios of all Boo...
research
∙
02/20/2020
The (Generalized) Orthogonality Dimension of (Generalized) Kneser Graphs: Bounds and Applications
The orthogonality dimension of a graph G=(V,E) over a field 𝔽 is the sma...
research
∙
11/06/2019
Fine-grained hardness of CVP(P)— Everything that we can prove (and nothing else)
We show that the Closest Vector Problem in the ℓ_p norm (CVP_p) cannot b...
research
∙
08/24/2019
An Attack on the the Encryption Scheme of the Moscow Internet Voting System
The next Moscow City Duma elections will be held on September 8th with a...
research
∙
07/19/2019
3SUM with Preprocessing: Algorithms, Lower Bounds and Cryptographic Applications
Given a set of integers {a_1, ..., a_N}, the 3SUM problem requires findi...
research
∙
06/01/2019
On the computational complexity of the probabilistic label tree algorithms
Label tree-based algorithms are widely used to tackle multi-class and mu...
research
∙
01/16/2019
The information-theoretic value of unlabeled data in semi-supervised learning
We quantify the separation between the numbers of labeled examples requi...
research
∙
11/12/2018
Circuit Depth Reductions
The best known circuit lower bounds against unrestricted circuits remain...
research
∙
11/07/2018
Static Data Structure Lower Bounds Imply Rigidity
We show that static data structure lower bounds in the group (linear) mo...
research
∙
09/23/2018
Collapsing Superstring Conjecture
In the Shortest Common Superstring (SCS) problem, one is given a collect...
research
∙
09/07/2017