
-
Approximability of all Boolean CSPs in the dynamic streaming setting
A Boolean constraint satisfaction problem (CSP), Max-CSP(f), is a maximi...
read it
-
Optimal Streaming Approximations for all Boolean Max-2CSPs
We prove tight upper and lower bounds on approximation ratios of all Boo...
read it
-
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...
read it
-
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...
read it
-
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...
read it
-
3SUM with Preprocessing: Algorithms, Lower Bounds and Cryptographic Applications
Given a set of integers {a_1, ..., a_N}, the 3SUM problem requires findi...
read it
-
On the computational complexity of the probabilistic label tree algorithms
Label tree-based algorithms are widely used to tackle multi-class and mu...
read it
-
The information-theoretic value of unlabeled data in semi-supervised learning
We quantify the separation between the numbers of labeled examples requi...
read it
-
Circuit Depth Reductions
The best known circuit lower bounds against unrestricted circuits remain...
read it
-
Static Data Structure Lower Bounds Imply Rigidity
We show that static data structure lower bounds in the group (linear) mo...
read it
-
Collapsing Superstring Conjecture
In the Shortest Common Superstring (SCS) problem, one is given a collect...
read it
-
Detecting Patterns Can Be Hard: Circuit Lower Bounds for the String Matching Problem
Detecting patterns in strings and images is a fundamental and well studi...
read it