
Adversarial Laws of Large Numbers and Optimal Regret in Online Classification
Laws of large numbers guarantee that given a large enough sample from so...
read it

Typical and Extremal Aspects of FriendsandStrangers Graphs
Given graphs X and Y with vertex sets V(X) and V(Y) of the same cardinal...
read it

Efficient Splitting of Measures and Necklaces
We provide approximation algorithms for two problems, known as NECKLACE ...
read it

Palette Sparsification Beyond (Δ+1) Vertex Coloring
A recent palette sparsification theorem of Assadi, Chen, and Khanna [SOD...
read it

Hierarchical Clustering: a 0.585 Revenue Approximation
Hierarchical Clustering trees have been widely accepted as a useful form...
read it

Explicit expanders of every degree and size
An (n,d,λ)graph is a d regular graph on n vertices in which the absolut...
read it

The εtNet Problem
We study a natural generalization of the classical ϵnet problem (Haussl...
read it

Closure Properties for Private Classification and Online Prediction
Let H be a class of boolean functions and consider acomposed class H' th...
read it

Boosting Simple Learners
We consider boosting algorithms under the restriction that the weak lear...
read it

Algorithmic Number On the Forehead Protocols Yielding Dense RuzsaSzemerédi Graphs and Hypergraphs
We describe algorithmic Number On the Forehead protocols that provide de...
read it

On Generalized Regularity
Szemeredi's regularity lemma is one instance in a family of regularity l...
read it

Limits of Private Learning with Access to Public Data
We consider learning problems where the training set consists of two typ...
read it

Highgirth nearRamanujan graphs with localized eigenvectors
We show that for every prime d and α∈ (0,1/6), there is an infinite sequ...
read it

Deterministic Combinatorial Replacement Paths and Distance Sensitivity Oracles
In this work we derandomize two central results in graph algorithms, rep...
read it

The hat guessing number of graphs
Consider the following hat guessing game: n players are placed on n vert...
read it

Multitasking Capacity: Hardness Results and Improved Constructions
We consider the problem of determining the maximal α∈ (0,1] such that ev...
read it

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...
read it

Private PAC learning implies finite Littlestone dimension
We show that every approximately differentially private learning algorit...
read it

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...
read it

Nonstochastic MultiArmed Bandits with GraphStructured Feedback
We present and study a partialinformation model of online learning, whe...
read it

From Bandits to Experts: A Tale of Domination and Independence
We consider the partial observability model for multiarmed bandits, int...
read it

Sum of Us: Strategyproof Selection from the Selectors
We consider directed graphs over a set of n agents, where an edge (i,j) ...
read it