-
Approximability of all Boolean CSPs in the dynamic streaming setting
A Boolean constraint satisfaction problem (CSP), Max-CSP(f), is a maximi...
02/24/2021 ∙ by Chi-Ning Chou, et al. ∙
0
∙
share
read it
-
Optimal Streaming Approximations for all Boolean Max-2CSPs
We prove tight upper and lower bounds on approximation ratios of all Boo...
04/24/2020 ∙ by Chi-Ning Chou, et al. ∙
0
∙
share
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...
02/20/2020 ∙ by Alexander Golovnev, et al. ∙
0
∙
share
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...
11/06/2019 ∙ by Divesh Aggarwal, et al. ∙
0
∙
share
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...
08/24/2019 ∙ by Alexander Golovnev, et al. ∙
0
∙
share
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...
07/19/2019 ∙ by Alexander Golovnev, et al. ∙
0
∙
share
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...
06/01/2019 ∙ by Robert Busa-Fekete, et al. ∙
0
∙
share
read it
-
The information-theoretic value of unlabeled data in semi-supervised learning
We quantify the separation between the numbers of labeled examples requi...
01/16/2019 ∙ by Alexander Golovnev, et al. ∙
0
∙
share
read it
-
Circuit Depth Reductions
The best known circuit lower bounds against unrestricted circuits remain...
11/12/2018 ∙ by Alexander Golovnev, et al. ∙
0
∙
share
read it
-
Static Data Structure Lower Bounds Imply Rigidity
We show that static data structure lower bounds in the group (linear) mo...
11/07/2018 ∙ by Zeev Dvir, et al. ∙
0
∙
share
read it
-
Collapsing Superstring Conjecture
In the Shortest Common Superstring (SCS) problem, one is given a collect...
09/23/2018 ∙ by Alexander Golovnev, et al. ∙
0
∙
share
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...
09/07/2017 ∙ by Alexander Golovnev, et al. ∙
0
∙
share
read it
