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
∙
07/12/2023
Sublinear Time Shortest Path in Expander Graphs
Computing a shortest path between two nodes in an undirected unweighted ...
research
∙
06/13/2023
Invertible Bloom Lookup Tables with Less Memory and Randomness
In this work we study Invertible Bloom Lookup Tables (IBLTs) with small ...
research
∙
04/18/2023
Super-Logarithmic Lower Bounds for Dynamic Graph Problems
In this work, we prove a Ω̃(^3/2 n ) unconditional lower bound on the ma...
research
∙
02/13/2023
Sparse Dimensionality Reduction Revisited
The sparse Johnson-Lindenstrauss transform is one of the central techniq...
research
∙
01/27/2023
AdaBoost is not an Optimal Weak to Strong Learner
AdaBoost is a classic boosting algorithm for combining multiple inaccura...
research
∙
01/23/2023
The Impossibility of Parallelizing Boosting
The aim of boosting is to convert a sequence of weak learners into a str...
research
∙
01/05/2023
Diagonalization Games
We study several variants of a combinatorial game which is based on Cant...
research
∙
12/05/2022
Bagging is an Optimal PAC Learner
Determining the optimal sample complexity of PAC learning in the realiza...
research
∙
11/15/2022
Improved Coresets for Euclidean k-Means
Given a set of n points in d dimensions, the Euclidean k-means problem (...
research
∙
10/11/2022
Hierarchical Categories in Colored Searching
In colored range counting (CRC), the input is a set of points where each...
research
∙
07/07/2022
Barriers for Faster Dimensionality Reduction
The Johnson-Lindenstrauss transform allows one to embed a dataset of n p...
research
∙
07/07/2022
Fast Discrepancy Minimization with Hereditary Guarantees
Efficiently computing low discrepancy colorings of various set systems, ...
research
∙
06/03/2022
Optimal Weak to Strong Learning
The classic algorithm AdaBoost allows to convert a weak learner, that is...
research
∙
04/04/2022
The Fast Johnson-Lindenstrauss Transform is Even Faster
The seminal Fast Johnson-Lindenstrauss (Fast JL) transform by Ailon and ...
research
∙
03/17/2022
Stronger 3SUM-Indexing Lower Bounds
The 3SUM-Indexing problem was introduced as a data structure version of ...
research
∙
02/25/2022
Towards Optimal Lower Bounds for k-median and k-means Coresets
Given a set of points in a metric space, the (k,z)-clustering problem co...
research
∙
07/14/2021
Optimality of the Johnson-Lindenstrauss Dimensionality Reduction for Practical Measures
It is well known that the Johnson-Lindenstrauss dimensionality reduction...
research
∙
06/15/2021
Compression Implies Generalization
Explaining the surprising generalization performance of deep neural netw...
research
∙
06/11/2021
Property-Preserving Hash Functions from Standard Assumptions
Property-preserving hash functions allow for compressing long inputs x_0...
research
∙
02/03/2021
CountSketches, Feature Hashing and the Median of Three
In this paper, we revisit the classic CountSketch method, which is a spa...
research
∙
11/10/2020
Margins are Insufficient for Explaining Gradient Boosting
Boosting is one of the most successful ideas in machine learning, achiev...
research
∙
08/12/2020
Further Unifying the Landscape of Cell Probe Lower Bounds
In a landmark paper, Pǎtraşcu demonstrated how a single lower bound for ...
research
∙
06/03/2020
Near-Tight Margin-Based Generalization Bounds for Support Vector Machines
Support Vector Machines (SVMs) are among the most fundamental tools for ...
research
∙
09/27/2019
Margin-Based Generalization Lower Bounds for Boosted Classifiers
Boosting is one of the most successful ideas in machine learning. The mo...
research
∙
09/21/2019
Optimal Learning of Joint Alignments with a Faulty Oracle
We consider the following problem, which is useful in applications such ...
research
∙
04/09/2019
Lower Bounds for Oblivious Near-Neighbor Search
We prove an Ω(d n/ ( n)^2) lower bound on the dynamic cell-probe comple...
research
∙
02/28/2019
Lower Bounds for Multiplication via Network Coding
Multiplication is one of the most fundamental computational problems, ye...
research
∙
01/30/2019
Optimal Minimal Margin Maximization with Boosting
Boosting algorithms produce a classifier by iteratively combining base h...
research
∙
12/20/2018
The Query Complexity of a Permutation-Based Variant of Mastermind
We study the query complexity of a permutation-based variant of the gues...
research
∙
11/04/2018
Lower Bounds for External Memory Integer Sorting via Network Coding
Sorting extremely large datasets is a frequently occuring task in practi...
research
∙
10/24/2018
Lower Bounds for Oblivious Data Structures
An oblivious data structure is a data structure where the memory access ...
research
∙
06/20/2018
A Faster External Memory Priority Queue with DecreaseKeys
A priority queue is a fundamental data structure that maintains a dynami...
research
∙
05/22/2018
Fully Understanding the Hashing Trick
Feature hashing, also known as the hashing trick, introduced by Weinber...
research
∙
02/19/2018
Upper and lower bounds for dynamic data structures on strings
We consider a range of simply stated dynamic data structure problems on ...
research
∙
11/13/2017
Tight Cell Probe Bounds for Succinct Boolean Matrix-Vector Multiplication
The conjectured hardness of Boolean matrix-vector multiplication has bee...
research
∙
11/08/2017
Constructive Discrepancy Minimization with Hereditary L2 Guarantees
In discrepancy minimization problems, we are given a family of sets S = ...
research
∙
01/25/2017
