b'Noga Alon'

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

0 Noga Alon, et al. ∙

research

∙ 07/12/2023

Sublinear Time Shortest Path in Expander Graphs

Computing a shortest path between two nodes in an undirected unweighted ...

0 Noga Alon, et al. ∙

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

0 Noga Alon, et al. ∙

research

∙ 04/08/2023

A Unified Characterization of Private Learnability via Graph Theory

We provide a unified framework for characterizing pure and approximate d...

0 Noga Alon, et al. ∙

research

∙ 01/05/2023

Diagonalization Games

We study several variants of a combinatorial game which is based on Cant...

0 Noga Alon, et al. ∙

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

0 Noga Alon, et al. ∙

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

0 Noga Alon, et al. ∙

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

0 Noga Alon, et al. ∙

research

∙ 03/07/2022

Identifying the Deviator

A group of players are supposed to follow a prescribed profile of strate...

0 Noga Alon, et al. ∙

research

∙ 01/02/2022

Implicit representation of sparse hereditary families

For a hereditary family of graphs , let _n denote the set of all members...

0 Noga Alon, et al. ∙

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

0 Noga Alon, et al. ∙

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

17 Noga Alon, et al. ∙

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

0 Noga Alon, et al. ∙

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

6 Noga Alon, et al. ∙

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

0 Noga Alon, et al. ∙

research

∙ 06/30/2020

Efficient Splitting of Measures and Necklaces

We provide approximation algorithms for two problems, known as NECKLACE ...

0 Noga Alon, et al. ∙

research

∙ 06/18/2020

Palette Sparsification Beyond (Δ+1) Vertex Coloring

A recent palette sparsification theorem of Assadi, Chen, and Khanna [SOD...

0 Noga Alon, et al. ∙

research

∙ 06/02/2020

Hierarchical Clustering: a 0.585 Revenue Approximation

Hierarchical Clustering trees have been widely accepted as a useful form...

0 Noga Alon, et al. ∙

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

0 Noga Alon, et al. ∙

research

∙ 03/16/2020

The ε-t-Net Problem

We study a natural generalization of the classical ϵ-net problem (Haussl...

0 Noga Alon, et al. ∙

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

0 Noga Alon, et al. ∙

research

∙ 01/31/2020

Boosting Simple Learners

We consider boosting algorithms under the restriction that the weak lear...

6 Noga Alon, et al. ∙

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

0 Noga Alon, et al. ∙

research

∙ 11/05/2019

On Generalized Regularity

Szemeredi's regularity lemma is one instance in a family of regularity l...

0 Noga Alon, et al. ∙

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

10 Noga Alon, et al. ∙

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

0 Noga Alon, et al. ∙

research

∙ 05/17/2019

Deterministic Combinatorial Replacement Paths and Distance Sensitivity Oracles

In this work we derandomize two central results in graph algorithms, rep...

0 Noga Alon, et al. ∙

research

∙ 12/23/2018

The hat guessing number of graphs

Consider the following hat guessing game: n players are placed on n vert...

0 Noga Alon, et al. ∙

research

∙ 09/08/2018

Multitasking Capacity: Hardness Results and Improved Constructions

We consider the problem of determining the maximal α∈ (0,1] such that ev...

0 Noga Alon, et al. ∙

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

0 Noga Alon, et al. ∙

research

∙ 06/04/2018

Private PAC learning implies finite Littlestone dimension

We show that every approximately differentially private learning algorit...

0 Noga Alon, et al. ∙

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

0 Noga Alon, et al. ∙

research

∙ 09/30/2014

Nonstochastic Multi-Armed Bandits with Graph-Structured Feedback

We present and study a partial-information model of online learning, whe...

0 Noga Alon, et al. ∙

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

0 Noga Alon, et al. ∙

research

∙ 10/25/2009

Sum of Us: Strategyproof Selection from the Selectors

We consider directed graphs over a set of n agents, where an edge (i,j) ...

0 Noga Alon, et al. ∙

Noga Alon

Featured Co-authors