126 citations · 834 across the 125 of their papers we have counts for
159 papers
The power of many colours
Noga Alon, Matija Bucić, Micha Christoph +1
A classical problem, due to Gerencsér and Gyárfás from 1967, asks how large a monochromatic connected component can we guarantee in any -edge colouring of ? We consider how…
On bipartite coverings of graphs and multigraphs
Noga Alon
A bipartite covering of a (multi)graph is a collection of bipartite graphs, so that each edge of belongs to at least one of them. The capacity of the covering is the sum of…
Sublinear Time Shortest Path in Expander Graphs
Noga Alon, Allan Grønlund, Søren Fuglede Jørgensen +1
Computing a shortest path between two nodes in an undirected unweighted graph is among the most basic algorithmic tasks. Breadth first search solves this problem in linear time, wh…
Strong blocking sets and minimal codes from expander graphs
Noga Alon, Anurag Bishnoi, Shagnik Das +1
A strong blocking set in a finite projective space is a set of points that intersects each hyperplane in a spanning set. We provide a new graph theoretic construction of such sets:…
A Unified Characterization of Private Learnability via Graph Theory
Noga Alon, Shay Moran, Hilla Schefler +1
We provide a unified framework for characterizing pure and approximate differentially private (DP) learnability. The framework uses the language of graph theory: for a concept clas…
The limit points of the top and bottom eigenvalues of regular graphs
Noga Alon, Fan Wei
We prove that for each the set of all limit points of the second largest eigenvalue of growing sequences of -regular graphs is . A similar argument s…