Search filters

List of works by Noga Alon

A Characterization of the (Natural) Graph Properties Testable with One-Sided Error

scholarly article from 'SIAM Journal on Computing' published in 2008

A Combinatorial Characterization of the Testable Graph Properties: It's All About Regularity

scholarly article from 'SIAM Journal on Computing' published in 2009

A Ramsey-type problem and the Turán numbers*

A Separator Theorem for Nonplanar Graphs

A Simple Proof of the Upper Bound Theorem

scientific article published in 1985

A biological solution to a fundamental distributed computing problem

scientific article published in January 2011

A fast and simple randomized parallel algorithm for the maximal independent set problem

scientific article (publication date: December 1986)

A graph-theoretic approach to multitasking

scientific article published in January 2017

A graph-theoretic game and its application to the k-server problem

scientific article published in February 1995

A lattice point problem and additive number theory

A nowhere-zero point in linear mappings

A separator theorem for nonplanar graphs

scientific article (publication date: 1990)

A simple algorithm for edge-coloring bipartite multigraphs

Acyclic coloring of graphs

Acyclic edge colorings of graphs

Adding Distinct Congruence Classes Modulo a Prime

Additive Patterns in Multiplicative Subgroups

scholarly article from 'Geometric and Functional Analysis' published in 2014

Additive approximation for edge-deletion problems

scholarly article from 'Annals of Mathematics' published in 2009

Adversarial laws of large numbers and optimal regret in online classification

scientific article published on 16 June 2021

Algorithmic construction of sets for k-restrictions

article

An Application of Graph Theory to Additive Number Theory

An Extremal Problem for Sets with Applications to Graph Theory

scientific article published in 1985

Approximate maximum parsimony and ancestral maximum likelihood

scientific article

Approximating the cut-norm via Grothendieck's inequality

Beeping a Maximal Independent Set

Beeping a maximal independent set

article published in 2012

Biomolecular network motif counting and discovery by color coding

scientific article

Bounding the piercing number

scientific article published in 1995

Color Coding

Color-coding

article by Noga Alon et al published 1 July 1995 in Journal of the ACM

Coloring, sparseness and girth

scientific article published in July 2016

Colorings and orientations of graphs

Combinatorial reconstruction problems

article

Counting sum-free sets in abelian groups

scholarly article from 'Israel Journal of Mathematics' published in 2014

Covering graphs by the minimum number of equivalence relations

scientific article published in 1986

Disjoint edges in geometric graphs

ECONOMICAL COVERS WITH GEOMETRIC APPLICATIONS

scientific article published in 2003

EFX: A Simpler Approach and an (Almost) Optimal Guarantee via Rainbow Cycle Number

scientific article published on 07 July 2023

Easily Testable Graph Properties

scholarly article from 'Combinatorics, Probability and Computing' published in 2015

Efficient Testing of Bipartite Graphs for Forbidden Induced Subgraphs

Efficient Testing of Large Graphs

scholarly article from 'Combinatorica' published in 2000

Eigenvalues and expanders

scientific article published in 1986

Eigenvalues, geometric expanders, sorting in rounds, and ramsey theory

Embedding nearly-spanning bounded degree trees

scholarly article from 'Combinatorica' published in 2007

Every Monotone Graph Property Is Testable

scholarly article from 'SIAM Journal on Computing' published in 2008

Explicit Ramsey graphs and orthonormal labelings

scholarly article from 'The Electronic Journal of Combinatorics' published in 1994

Finding a large hidden clique in a random graph

scholarly article by Noga Alon et al published October 1998 in Random Structures and Algorithms

Finding and counting given length cycles

Hardness of fully dense problems

article published in 2007

Increasing the chromatic number of a random graph

scholarly article from 'Journal of Combinatorics' published in 2010

Large matchings in uniform hypergraphs and the conjectures of Erdős and Samuels

scholarly article from 'Journal of Combinatorial Theory, Series A' published in 2012

Linear Arboricity and Linear k-Arboricity of Regular Graphs

Measures of pseudorandomness for finite sequences: typical values

scientific article published in 2007

Multi-node graphs: a framework for multiplexed biological assays

scientific article published on December 2006

Near-optimum Universal Graphs for Graphs with Bounded Degrees

chapter from 'Approximation, Randomization, and Combinatorial Optimization: Algorithms and Techniques' published in 2001

Nonnegative k-sums, fractional covers, and probability of small deviations

scholarly article from 'Journal of Combinatorial Theory, Series B' published in 2012

Norm-Graphs: Variations and Applications

scientific article (publication date: July 1999)

On k-saturated graphs with restrictions on the degrees

scientific article published in September 1996

On partitions of discrete boxes

scientific article published in 2002

Optimal induced universal graphs for bounded-degree graphs

conference paper from 'Proceedings of the Twenty-Eighth Annual ACM-SIAM Symposium on Discrete Algorithms' published in 2017

Ordinal embeddings of minimum relaxation

article published in 2008

Partitioning multi-dimensional sets in a small number of “uniform” parts

Piercing convex sets

scientific article published in August 1992

Piercing d-Intervals

scientific article published in 1998

Point Selections and Weak ε-Nets for Convex Hulls

scientific article published in 1992

Polychromatic Colorings of Plane Graphs

Polychromatic colorings of plane graphs

Polynomial time randomized approximation schemes for Tutte-Gröthendieck invariants: The dense case

scientific article (publication date: July 1995)

Practically stabilizing SWMR atomic memory in message-passing systems

scholarly article by Noga Alon et al published June 2015 in Journal of Computer and System Sciences

Properly colored subgraphs and rainbow subgraphs in edge-colorings with local constraints

scholarly article from 'Random Structures and Algorithms' published in 2003

Quasi-Randomness and Algorithmic Regularity for Graphs with General Degree Distributions

scholarly article from 'SIAM Journal on Computing' published in 2010

Reflection Sequences

article

Resolution enhancement in MRI.

scientific article published on 6 January 2006

Scale-sensitive dimensions, uniform convergence, and learnability

Simple Constructions of Almost k-wise Independent Random Variables

scholarly article by Noga Alon et al published 1992 in Random Structures and Algorithms

Single round simulation on radio networks

scholarly article; 1992 Alon, Bar-Noy, Linial, Peleg

Spanning Directed Trees with Many Leaves

Spanning subgraphs of random graphs

scholarly article from 'Graphs and Combinatorics' published in 1992

Sparse universal graphs for bounded-degree graphs

scholarly article from 'Random Structures and Algorithms' published in 2007

Stable Kneser hypergraphs and ideals in ℕ with the Nikodým property

scientific article published on 19 August 2008

Submultiplicative Glivenko-Cantelli and Uniform Convergence of Revenues

scientific article published in January 2017

Subset sums

scientific article published in 1987

THE NUMBER OF EDGE COLORINGS WITH NO MONOCHROMATIC CLIQUES

scholarly article from 'Journal of the London Mathematical Society' published in 2004

Testing k-wise and almost k-wise independence

scholarly article published 2007

Testing subgraphs in large graphs

scholarly article from 'Random Structures and Algorithms' published in 2002

The Algorithmic Aspects of the Regularity Lemma

scholarly article from 'Journal of Algorithms' published in 1994

The Borsuk-Ulam theorem and bisection of necklaces

The Number Of Orientations Having No Fixed Tournament

scholarly article from 'Combinatorica' published in 2006

The Polynomial Method and Restricted Sums of Congruence Classes

scientific article (publication date: February 1996)

The Probabilistic Method.

book published in 2005

The Space Complexity of Approximating the Frequency Moments

The linear arboricity of graphs

The monotone circuit complexity of boolean functions

scientific article (publication date: March 1987)

The number of small semispaces of a finite set of points in the plane

scientific article (publication date: 1986)

The probabilistic method

book published in 2016

The space complexity of approximating the frequency moments

The strong chromatic number of a graph

scholarly article by Noga Alon published 1992 in Random Structures and Algorithms

Tight bounds for shared memory systems accessed by Byzantine processes

Transversal numbers for hypergraphs arising in geometry

scientific article published in July 2002

Universality and tolerance

conference paper from 'Proceedings 41st Annual Symposium on Foundations of Computer Science' published in 2000

λ1, Isoperimetric inequalities for graphs, and superconcentrators

scientific article published in 1985