research
∙
08/30/2023
Optimal Non-Adaptive Cell Probe Dictionaries and Hashing
We present a simple and provably optimal non-adaptive cell probe data st...
share
research
∙
11/21/2022
Algorithmic Applications of Hypergraph and Partition Containers
We present a general method to convert algorithms into faster algorithms...
research
∙
11/15/2022
The wrong direction of Jensen's inequality is algorithmically right
Let 𝒜 be an algorithm with expected running time e^X, conditioned on the...
research
∙
04/22/2022
Hardness of Approximation in P via Short Cycle Removal: Cycle Detection, Distance Oracles, and Beyond
We present a new technique for efficiently removing almost all short cyc...
research
∙
04/14/2022
Planting Undetectable Backdoors in Machine Learning Models
Given the computational cost and technical expertise required to train m...
research
∙
10/07/2021
Faster algorithm for Unique (k,2)-CSP
In a (k,2)-Constraint Satisfaction Problem we are given a set of arbitra...
research
∙
07/05/2021
Randomized Dimensionality Reduction for Facility Location and Single-Linkage Clustering
Random dimensionality reduction is a versatile tool for speeding up algo...
research
∙
07/21/2020
Breaking the 2^n barrier for 5-coloring and 6-coloring
The coloring problem (i.e., computing the chromatic number of a graph) c...
research
∙
09/24/2019
Random k-out subgraph leaves only O(n/k) inter-component edges
Each vertex of an arbitrary simple graph on n vertices chooses k random ...
research
∙
02/20/2018