research
∙
07/31/2023
On bipartite coverings of graphs and multigraphs
A bipartite covering of a (multi)graph G is a collection of bipartite gr...
share
research
∙
07/12/2023
Sublinear Time Shortest Path in Expander Graphs
Computing a shortest path between two nodes in an undirected unweighted ...
research
∙
05/24/2023
Strong blocking sets and minimal codes from expander graphs
A strong blocking set in a finite projective space is a set of points th...
research
∙
04/08/2023
A Unified Characterization of Private Learnability via Graph Theory
We provide a unified framework for characterizing pure and approximate d...
research
∙
01/05/2023
Diagonalization Games
We study several variants of a combinatorial game which is based on Cant...
research
∙
12/22/2022
Invertibility of digraphs and tournaments
For an oriented graph D and a set X⊆ V(D), the inversion of X in D is th...
research
∙
10/26/2022
Turán graphs with bounded matching number
We determine the maximum possible number of edges of a graph with n vert...
research
∙
09/23/2022
Logarithmically larger deletion codes of all distances
The deletion distance between two binary words u,v ∈{0,1}^n is the small...
research
∙
03/07/2022
Identifying the Deviator
A group of players are supposed to follow a prescribed profile of strate...
research
∙
01/02/2022
Implicit representation of sparse hereditary families
For a hereditary family of graphs , let _n denote the set of all members...
research
∙
07/27/2021
Partitioning all k-subsets into r-wise intersecting families
Let r ≥ 2, n and k be integers satisfying k ≤r-1/rn. In the original arX...
research
∙
07/18/2021
A Theory of PAC Learnability of Partial Concept Classes
We extend the theory of PAC learning in a way which allows to model a ri...
research
∙
07/13/2021
On the Hat Guessing Number of Graphs
The hat guessing number HG(G) of a graph G on n vertices is defined in t...
research
∙
01/22/2021
Adversarial Laws of Large Numbers and Optimal Regret in Online Classification
Laws of large numbers guarantee that given a large enough sample from so...
research
∙
09/16/2020
Typical and Extremal Aspects of Friends-and-Strangers Graphs
Given graphs X and Y with vertex sets V(X) and V(Y) of the same cardinal...
research
∙
06/30/2020
Efficient Splitting of Measures and Necklaces
We provide approximation algorithms for two problems, known as NECKLACE ...
research
∙
06/18/2020
Palette Sparsification Beyond (Δ+1) Vertex Coloring
A recent palette sparsification theorem of Assadi, Chen, and Khanna [SOD...
research
∙
06/02/2020
Hierarchical Clustering: a 0.585 Revenue Approximation
Hierarchical Clustering trees have been widely accepted as a useful form...
research
∙
03/25/2020
Explicit expanders of every degree and size
An (n,d,λ)-graph is a d regular graph on n vertices in which the absolut...
research
∙
03/16/2020
The ε-t-Net Problem
We study a natural generalization of the classical ϵ-net problem (Haussl...
research
∙
03/10/2020
Closure Properties for Private Classification and Online Prediction
Let H be a class of boolean functions and consider acomposed class H' th...
research
∙
01/31/2020
Boosting Simple Learners
We consider boosting algorithms under the restriction that the weak lear...
research
∙
01/02/2020
Algorithmic Number On the Forehead Protocols Yielding Dense Ruzsa-Szemerédi Graphs and Hypergraphs
We describe algorithmic Number On the Forehead protocols that provide de...
research
∙
11/05/2019
On Generalized Regularity
Szemeredi's regularity lemma is one instance in a family of regularity l...
research
∙
10/25/2019
Limits of Private Learning with Access to Public Data
We consider learning problems where the training set consists of two typ...
research
∙
08/10/2019
High-girth near-Ramanujan graphs with localized eigenvectors
We show that for every prime d and α∈ (0,1/6), there is an infinite sequ...
research
∙
05/17/2019
Deterministic Combinatorial Replacement Paths and Distance Sensitivity Oracles
In this work we derandomize two central results in graph algorithms, rep...
research
∙
12/23/2018
The hat guessing number of graphs
Consider the following hat guessing game: n players are placed on n vert...
research
∙
09/08/2018
Multitasking Capacity: Hardness Results and Improved Constructions
We consider the problem of determining the maximal α∈ (0,1] such that ev...
research
∙
09/06/2018
The Minrank of Random Graphs over Arbitrary Fields
The minrank of a graph G on the set of vertices [n] over a field F is th...
research
∙
06/04/2018
Private PAC learning implies finite Littlestone dimension
We show that every approximately differentially private learning algorit...
research
∙
08/07/2017
Unbalancing Sets and an Almost Quadratic Lower Bound for Syntactically Multilinear Arithmetic Circuits
We prove a lower bound of Ω(n^2/^2 n) on the size of any syntactically m...
research
∙
09/30/2014
Nonstochastic Multi-Armed Bandits with Graph-Structured Feedback
We present and study a partial-information model of online learning, whe...
research
∙
07/17/2013
From Bandits to Experts: A Tale of Domination and Independence
We consider the partial observability model for multi-armed bandits, int...
research
∙
10/25/2009