% csauthors.net - beta - BibTeX bibliography of Noga Alon
@article{journals/dm/Alon83,
title = {On the density of sets of vectors.},
year = {1983},
journal = {Discret. Math.},
author = {{Noga Alon}}
}
@article{journals/jgt/Alon83,
title = {On a conjecture of erdöus, simonovits, and sós concerning anti-Ramsey theorems.},
year = {1983},
journal = {J. Graph Theory},
author = {{Noga Alon}}
}
@inproceedings{conf/focs/AlonM84,
title = {Eigenvalues, Expanders and Superconcentrators (Extended Abstract)},
year = {1984},
booktitle = {FOCS},
author = {{Noga Alon} and {V. D. Milman}},
publisher = {IEEE Computer Society},
booktitle = {25th Annual Symposium on Foundations of Computer Science, West Palm Beach, Florida, USA, 24-26 October 1984}
}
@article{journals/dm/Alon84,
title = {A note on subdigraphs of digraphs with large outdegrees.},
year = {1984},
journal = {Discret. Math.},
author = {{Noga Alon}}
}
@article{journals/jct/AlonFK84,
title = {Regular subgraphs of almost regular graphs.},
year = {1984},
journal = {J. Comb. Theory, Ser. B},
author = {{Noga Alon} and {Shmuel Friedland} and {Gil Kalai}}
}
@article{journals/jct/AlonFK84a,
title = {Every 4-regular graph plus an edge contains a 3-regular subgraph.},
year = {1984},
journal = {J. Comb. Theory, Ser. B},
author = {{Noga Alon} and {Shmuel Friedland} and {Gil Kalai}}
}
@inproceedings{conf/focs/AlonFR85,
title = {Geometrical Realization of Set Systems and Probabilistic Communication Complexity},
year = {1985},
booktitle = {FOCS},
author = {{Noga Alon} and {Peter Frankl} and {Vojtech Rödl}},
publisher = {IEEE Computer Society},
booktitle = {26th Annual Symposium on Foundations of Computer Science, Portland, Oregon, USA, 21-23 October 1985}
}
@inproceedings{conf/stoc/Alon85,
title = {Expanders, Sorting in Rounds and Superconcentrators of Limited Depth},
year = {1985},
booktitle = {STOC},
author = {{Noga Alon}},
publisher = {ACM},
booktitle = {Proceedings of the 17th Annual ACM Symposium on Theory of Computing, May 6-8, 1985, Providence, Rhode Island, USA}
}
@article{journals/ejc/AlonE85,
title = {An Application of Graph Theory to Additive Number Theory.},
year = {1985},
journal = {Eur. J. Comb.},
author = {{Noga Alon} and {Paul Erdös}}
}
@article{journals/ejc/AlonFK85,
title = {Separating Pairs of Points by Standard Boxes.},
year = {1985},
journal = {Eur. J. Comb.},
author = {{Noga Alon} and {Zoltán Füredi} and {Meir Katchalski}}
}
@article{journals/ejc/AlonK85,
title = {A Simple Proof of the Upper Bound Theorem.},
year = {1985},
journal = {Eur. J. Comb.},
author = {{Noga Alon} and {Gil Kalai}}
}
@article{journals/gc/Alon85,
title = {Asynchronous threshold networks.},
year = {1985},
journal = {Graphs Comb.},
author = {{Noga Alon}}
}
@article{journals/gc/Alon85a,
title = {Hypergraphs with high chromatic number.},
year = {1985},
journal = {Graphs Comb.},
author = {{Noga Alon}}
}
@article{journals/gc/AlonF85,
title = {The maximum number of disjoint pairs in a family of subsets.},
year = {1985},
journal = {Graphs Comb.},
author = {{Noga Alon} and {Peter Frankl}}
}
@article{journals/jct/Alon85,
title = {An Extremal Problem for Sets with Applications to Graph Theory.},
year = {1985},
journal = {J. Comb. Theory, Ser. A},
author = {{Noga Alon}}
}
@article{journals/jct/AlonE85,
title = {Even edge colorings of a graph.},
year = {1985},
journal = {J. Comb. Theory, Ser. B},
author = {{Noga Alon} and {Yoshimi Egawa}}
}
@article{journals/jct/AlonM85,
title = {lambda1, Isoperimetric inequalities for graphs, and superconcentrators.},
year = {1985},
journal = {J. Comb. Theory, Ser. B},
author = {{Noga Alon} and {V. D. Milman}}
}
@inproceedings{conf/focs/AlonAV86,
title = {Tight Complexity Bounds for Parallel Comparison Sorting},
year = {1986},
booktitle = {FOCS},
author = {{Noga Alon} and {Yossi Azar} and {Uzi Vishkin}},
publisher = {IEEE Computer Society},
booktitle = {27th Annual Symposium on Foundations of Computer Science, Toronto, Canada, 27-29 October 1986}
}
@inproceedings{conf/focs/AlonM86,
title = {Meanders, Ramsey Theory and Lower Bounds for Branching Programs},
year = {1986},
booktitle = {FOCS},
author = {{Noga Alon} and {Wolfgang Maass 001}},
publisher = {IEEE Computer Society},
booktitle = {27th Annual Symposium on Foundations of Computer Science, Toronto, Canada, 27-29 October 1986}
}
@article{journals/combinatorica/Alon86,
title = {Eigenvalues and expanders.},
year = {1986},
journal = {Comb.},
author = {{Noga Alon}}
}
@article{journals/combinatorica/Alon86a,
title = {Covering graphs by the minimum number of equivalence relations.},
year = {1986},
journal = {Comb.},
author = {{Noga Alon}}
}
@article{journals/combinatorica/Alon86b,
title = {Eigenvalues, geometric expanders, sorting in rounds, and Ramsey theory.},
year = {1986},
journal = {Comb.},
author = {{Noga Alon}}
}
@article{journals/dcg/AlonK86,
title = {Covering a Square by Small Perimeter Rectangles.},
year = {1986},
journal = {Discret. Comput. Geom.},
author = {{Noga Alon} and {Daniel J. Kleitman}}
}
@article{journals/dm/Alon86,
title = {Explicit construction of exponential sized families of k-independent sets.},
year = {1986},
journal = {Discret. Math.},
author = {{Noga Alon}}
}
@article{journals/dm/AlonP86,
title = {On the intersection of edges of a geometric graph by straight lines.},
year = {1986},
journal = {Discret. Math.},
author = {{Noga Alon} and {Micha A. Perles}}
}
@article{journals/ejc/AlonC86,
title = {Extremal Problems Concerning Transformations of the Set of Edges of the Complete Graph.},
year = {1986},
journal = {Eur. J. Comb.},
author = {{Noga Alon} and {Yair Caro}}
}
@article{journals/gc/Alon86,
title = {Decomposition of the completer-graph into completer-partiter-graphs.},
year = {1986},
journal = {Graphs Comb.},
author = {{Noga Alon}}
}
@article{journals/jal/AlonBI86,
title = {A Fast and Simple Randomized Parallel Algorithm for the Maximal Independent Set Problem.},
year = {1986},
journal = {J. Algorithms},
author = {{Noga Alon} and {László Babai} and {Alon Itai}}
}
@article{journals/jct/AlonB86,
title = {Regular hypergraphs, Gordon's lemma, Steinitz' lemma and invariant theory.},
year = {1986},
journal = {J. Comb. Theory, Ser. A},
author = {{Noga Alon} and {Kenneth A. Berman}}
}
@article{journals/jct/AlonG86,
title = {The number of small semispaces of a finite set of points in the plane.},
year = {1986},
journal = {J. Comb. Theory, Ser. A},
author = {{Noga Alon} and {Ervin Györi}}
}
@article{journals/jgt/Alon86,
title = {The longest cycle of a graph with a large minimal degree.},
year = {1986},
journal = {J. Graph Theory},
author = {{Noga Alon}}
}
@inproceedings{conf/compgeom/AlonHW87,
title = {Partitioning and Geometric Embedding of Range Spaces of Finite Vapnik-Chervonenkis Dimension.},
year = {1987},
booktitle = {SCG},
author = {{Noga Alon} and {David Haussler} and {Emo Welzl}},
publisher = {ACM},
booktitle = {Proceedings of the Third Annual Symposium on Computational Geometry, Waterloo, Ontario, Canada, June 8-10, 1987}
}
@inproceedings{conf/icdcs/AlonBM87,
title = {On Disseminating Information Reliably without Broadcasting.},
year = {1987},
booktitle = {ICDCS},
author = {{Noga Alon} and {Amnon Barak} and {Udi Manber}},
publisher = {IEEE Computer Society},
booktitle = {Proceedings of the 7th International Conference on Distributed Computing Systems, Berlin, Germany, September 1987}
}
@article{journals/combinatorica/AlonB87,
title = {The monotone circuit complexity of Boolean functions.},
year = {1987},
journal = {Comb.},
author = {{Noga Alon} and {Ravi B. Boppana}}
}
@article{journals/combinatorica/AlonKPSS87,
title = {The smallets n-uniform hypergraph with positive discrepancy.},
year = {1987},
journal = {Comb.},
author = {{Noga Alon} and {Daniel J. Kleitman} and {Carl Pomerance} and {Michael E. Saks} and {Paul D. Seymour}}
}
@article{journals/gc/AlonF87,
title = {On the kernel of intersecting families.},
year = {1987},
journal = {Graphs Comb.},
author = {{Noga Alon} and {Zoltán Füredi}}
}
@article{journals/gc/AlonKS87,
title = {Large induced degenerate subgraphs.},
year = {1987},
journal = {Graphs Comb.},
author = {{Noga Alon} and {Jeff Kahn 001} and {Paul D. Seymour}}
}
@article{journals/jal/AlonGM87,
title = {Better Expanders and Superconcentrators.},
year = {1987},
journal = {J. Algorithms},
author = {{Noga Alon} and {Zvi Galil} and {V. D. Milman}}
}
@article{journals/jgt/AlonKTSS87,
title = {Subgraphs of large connectivity and chromatic number in graphs of large chromatic number.},
year = {1987},
journal = {J. Graph Theory},
author = {{Noga Alon} and {Daniel J. Kleitman} and {Carsten Thomassen} and {Michael E. Saks} and {Paul D. Seymour}}
}
@article{journals/combinatorica/AlonF88,
title = {On sums of subsets of a set of integers.},
year = {1988},
journal = {Comb.},
author = {{Noga Alon} and {Gregory Freiman}}
}
@article{journals/dm/Alon88,
title = {Sums of subsequences modulo prime powers.},
year = {1988},
journal = {Discret. Math.},
author = {{Noga Alon}}
}
@article{journals/dm/AlonC88,
title = {Explicit construction of linear sized tolerant networks.},
year = {1988},
journal = {Discret. Math.},
author = {{Noga Alon} and {Fan R. K. Chung}}
}
@article{journals/gc/AlonB88,
title = {Every 8-uniform 8-regular hypergraph is 2-colorable.},
year = {1988},
journal = {Graphs Comb.},
author = {{Noga Alon} and {Z. Bregman}}
}
@article{journals/jcss/AlonM88,
title = {Meanders and Their Applications in Lower Bounds Arguments.},
year = {1988},
journal = {J. Comput. Syst. Sci.},
author = {{Noga Alon} and {Wolfgang Maass 001}}
}
@article{journals/jct/Nilli88,
title = {The average size of an independent set in graphs with a given chromatic number.},
year = {1988},
journal = {J. Comb. Theory, Ser. B},
author = {{Alon Nilli}}
}
@article{journals/siamcomp/AlonA88,
title = {The Average Complexity of Deterministic and Randomized Parallel Comparison-Sorting Algorithms.},
year = {1988},
journal = {SIAM J. Comput.},
author = {{Noga Alon} and {Yossi Azar}}
}
@article{journals/siamdm/AlonA88,
title = {Sorting, Approximate Sorting, and Searching in Rounds.},
year = {1988},
journal = {SIAM J. Discret. Math.},
author = {{Noga Alon} and {Yossi Azar}}
}
@article{journals/tit/AlonBCO88,
title = {Balancing sets of vectors.},
year = {1988},
journal = {IEEE Trans. Inf. Theory},
author = {{Noga Alon} and {Ernest E. Bergmann} and {Don Coppersmith} and {Andrew M. Odlyzko}}
}
@inproceedings{conf/stoc/AlonBLP89,
title = {On the Complexity of Radio Communication (Extended Abstract)},
year = {1989},
booktitle = {STOC},
author = {{Noga Alon} and {Amotz Bar-Noy} and {Nathan Linial} and {David Peleg}},
publisher = {ACM},
booktitle = {Proceedings of the 21st Annual ACM Symposium on Theory of Computing, May 14-17, 1989, Seattle, Washington, USA}
}
@article{journals/acr/AlonR89,
title = {Biased Coins and Randomized Algorithms.},
year = {1989},
journal = {Adv. Comput. Res.},
author = {{Noga Alon} and {Michael O. Rabin}}
}
@article{journals/combinatorica/AlonT89,
title = {A nowhere-zero point in liner mappings.},
year = {1989},
journal = {Comb.},
author = {{Noga Alon} and {Michael Tarsi}}
}
@article{journals/dcg/AlonE89,
title = {Disjoint Edges in Geometric Graphs.},
year = {1989},
journal = {Discret. Comput. Geom.},
author = {{Noga Alon} and {Paul Erdös}}
}
@article{journals/dcg/AlonKP89,
title = {Cutting Disjoint Disks by Straight Lines.},
year = {1989},
journal = {Discret. Comput. Geom.},
author = {{Noga Alon} and {Meir Katchalski} and {William R. Pulleyblank}}
}
@article{journals/dcg/AlonKP89a,
title = {The Maximum Size of a Convex Polygon in a Restricted Set in the Plane.},
year = {1989},
journal = {Discret. Comput. Geom.},
author = {{Noga Alon} and {Meir Katchalski} and {William R. Pulleyblank}}
}
@article{journals/dm/AlgorA89,
title = {The star arboricity of graphs.},
year = {1989},
journal = {Discret. Math.},
author = {{I. Algor} and {Noga Alon}}
}
@article{journals/dm/AlonB89,
title = {Graphs with a small number of distinct induced subgraphs.},
year = {1989},
journal = {Discret. Math.},
author = {{Noga Alon} and {Béla Bollobás}}
}
@article{journals/gc/AlonCT89,
title = {Sub-Ramsey numbers for arithmetic progressions.},
year = {1989},
journal = {Graphs Comb.},
author = {{Noga Alon} and {Yair Caro} and {Zsolt Tuza}}
}
@article{journals/gc/AlonF89,
title = {Legitimate colorings of projective planes.},
year = {1989},
journal = {Graphs Comb.},
author = {{Noga Alon} and {Zoltán Füredi}}
}
@article{journals/jct/AlonCKR89,
title = {Combinatorial reconstruction problems.},
year = {1989},
journal = {J. Comb. Theory, Ser. B},
author = {{Noga Alon} and {Yair Caro} and {Ilia Krasikov} and {Yehuda Roditty}}
}
@article{journals/jct/AlonL89,
title = {Cycles of length 0 modulo k in directed graphs.},
year = {1989},
journal = {J. Comb. Theory, Ser. B},
author = {{Noga Alon} and {Nathan Linial}}
}
@article{journals/jct/AlonS89,
title = {Ascending waves.},
year = {1989},
journal = {J. Comb. Theory, Ser. A},
author = {{Noga Alon} and {Joel H. Spencer}}
}
@article{journals/jgt/AlonS89,
title = {A counterexample to the rank-coloring conjecture.},
year = {1989},
journal = {J. Graph Theory},
author = {{Noga Alon} and {Paul D. Seymour}}
}
@article{journals/siamcomp/AlonA89,
title = {Finding an Approximate Maximum.},
year = {1989},
journal = {SIAM J. Comput.},
author = {{Noga Alon} and {Yossi Azar}}
}
@article{journals/tcs/AlonZ89,
title = {On Neciporuk's Theorem for Branching Programs.},
year = {1989},
journal = {Theor. Comput. Sci.},
author = {{Noga Alon} and {Uri Zwick}}
}
@inproceedings{conf/focs/AlonGHP90,
title = {Simple Constructions of Almost k-Wise Independent Random Variables},
year = {1990},
booktitle = {FOCS},
author = {{Noga Alon} and {Oded Goldreich 001} and {Johan Håstad} and {René Peralta 001}},
publisher = {IEEE Computer Society},
booktitle = {31st Annual Symposium on Foundations of Computer Science, St. Louis, Missouri, USA, October 22-24, 1990, Volume II}
}
@inproceedings{conf/focs/AlonN90,
title = {Coin-Flipping Games Immune against Linear-Sized Coalitions (Extended Abstract)},
year = {1990},
booktitle = {FOCS},
author = {{Noga Alon} and {Moni Naor}},
publisher = {IEEE Computer Society},
booktitle = {31st Annual Symposium on Foundations of Computer Science, St. Louis, Missouri, USA, October 22-24, 1990, Volume I}
}
@inproceedings{conf/stoc/AlonST90,
title = {A Separator Theorem for Graphs with an Excluded Minor and its Applications},
year = {1990},
booktitle = {STOC},
author = {{Noga Alon} and {Paul D. Seymour} and {Robin Thomas 001}},
publisher = {ACM},
booktitle = {Proceedings of the 22nd Annual ACM Symposium on Theory of Computing, May 13-17, 1990, Baltimore, Maryland, USA}
}
@article{journals/combinatorica/Alon90,
title = {The maximum number of Hamiltonian paths in tournaments.},
year = {1990},
journal = {Comb.},
author = {{Noga Alon}}
}
@article{journals/dam/AlonAR90,
title = {Universal sequences for complete graphs.},
year = {1990},
journal = {Discret. Appl. Math.},
author = {{Noga Alon} and {Yossi Azar} and {Yiftach Ravid}}
}
@article{journals/ejc/Alon90,
title = {The CW-Inequalities for Vectors in l1.},
year = {1990},
journal = {Eur. J. Comb.},
author = {{Noga Alon}}
}
@article{journals/ejc/AlonKS90,
title = {Not All Graphs are Segment T-graphs.},
year = {1990},
journal = {Eur. J. Comb.},
author = {{Noga Alon} and {Meir Katchalski} and {Edward R. Scheinerman}}
}
@article{journals/gc/Alon90,
title = {Transversal numbers of uniform hypergraphs.},
year = {1990},
journal = {Graphs Comb.},
author = {{Noga Alon}}
}
@article{journals/ipl/Alon90,
title = {Generating Pseudo-Random Permutations and Maximum Flow Algorithms.},
year = {1990},
journal = {Inf. Process. Lett.},
author = {{Noga Alon}}
}
@article{journals/jgt/Alon90,
title = {Ramsey graphs cannot be defined by real polynomials.},
year = {1990},
journal = {J. Graph Theory},
author = {{Noga Alon}}
}
@article{journals/rsa/Alon90,
title = {The Number of Spanning Trees in Regular Graphs.},
year = {1990},
journal = {Random Struct. Algorithms},
author = {{Noga Alon}}
}
@article{journals/siamcomp/AlonKW90,
title = {Linear Circuits over GF(2).},
year = {1990},
journal = {SIAM J. Comput.},
author = {{Noga Alon} and {Mauricio Karchmer} and {Avi Wigderson}}
}
@inproceedings{conf/dimacs/AlonKPW91,
title = {A Graph-Theoretic Game and its Application to the k-Server Problem (Extended Abstract).},
year = {1991},
booktitle = {On-Line Algorithms},
author = {{Noga Alon} and {Richard M. Karp} and {David Peleg} and {Douglas B. West}},
publisher = {DIMACS/AMS},
booktitle = {On-Line Algorithms, Proceedings of a DIMACS Workshop, New Brunswick, New Jersey, USA, February 11-13, 1991}
}
@article{journals/combinatorica/AlonA91,
title = {Parallel comparison algorithms for approximation problems.},
year = {1991},
journal = {Comb.},
author = {{Noga Alon} and {Yossi Azar}}
}
@article{journals/dm/Nilli91,
title = {On the second eigenvalue of a graph.},
year = {1991},
journal = {Discret. Math.},
author = {{Alon Nilli}}
}
@article{journals/gc/AlonH91,
title = {Ramsey graphs contain many distinct induced subgraphs.},
year = {1991},
journal = {Graphs Comb.},
author = {{Noga Alon} and {András Hajnal}}
}
@article{journals/gc/AlonKLMRS91,
title = {Set systems with no union of cardinality 0 modulom.},
year = {1991},
journal = {Graphs Comb.},
author = {{Noga Alon} and {Daniel J. Kleitman} and {Richard J. Lipton} and {Roy Meshulam} and {Michael O. Rabin} and {Joel H. Spencer}}
}
@article{journals/jacm/AlonDO91,
title = {Efficient Simulation of Finite Automata by Neural Nets.},
year = {1991},
journal = {J. ACM},
author = {{Noga Alon} and {A. K. Dewdney} and {Teunis J. Ott}}
}
@article{journals/jcss/AlonBLP91,
title = {A Lower Bound for Radio Broadcast.},
year = {1991},
journal = {J. Comput. Syst. Sci.},
author = {{Noga Alon} and {Amotz Bar-Noy} and {Nathan Linial} and {David Peleg}}
}
@article{journals/jct/AlonBS91,
title = {Multilinear polynomials and Frankl-Ray-Chaudhuri-Wilson type intersection theorems.},
year = {1991},
journal = {J. Comb. Theory, Ser. A},
author = {{Noga Alon} and {László Babai} and {Hiroshi Suzuki}}
}
@article{journals/jct/AlonBS91a,
title = {Multicolored forests in bipartite decompositions of graphs.},
year = {1991},
journal = {J. Comb. Theory, Ser. B},
author = {{Noga Alon} and {Richard A. Brualdi} and {Bryan L. Shader}}
}
@article{journals/jct/AlonLM91,
title = {Additive bases of vector spaces over prime fields.},
year = {1991},
journal = {J. Comb. Theory, Ser. A},
author = {{Noga Alon} and {Nathan Linial} and {Roy Meshulam}}
}
@article{journals/rsa/Alon91,
title = {A Parallel Algorithmic Version of the Local Lemma.},
year = {1991},
journal = {Random Struct. Algorithms},
author = {{Noga Alon}}
}
@article{journals/rsa/AlonMR91,
title = {Acyclic Coloring of Graphs.},
year = {1991},
journal = {Random Struct. Algorithms},
author = {{Noga Alon} and {Colin McDiarmid} and {Bruce A. Reed}}
}
@book{books/wi/AlonS92,
title = {The Probabilistic Method},
year = {1992},
isbn = {0-471-53588-5},
publisher = {John Wiley},
author = {{Noga Alon} and {Joel Spencer}}
}
@inproceedings{conf/compgeom/AlonA92,
title = {On-Line Steiner Trees in the Euclidean Plane.},
year = {1992},
booktitle = {SCG},
author = {{Noga Alon} and {Yossi Azar}},
publisher = {ACM},
booktitle = {Proceedings of the Eighth Annual Symposium on Computational Geometry, Berlin, Germany, June 10-12, 1992}
}
@inproceedings{conf/compgeom/AlonK92,
title = {Piercing Convex Sets.},
year = {1992},
booktitle = {SCG},
author = {{Noga Alon} and {Daniel J. Kleitman}},
publisher = {ACM},
booktitle = {Proceedings of the Eighth Annual Symposium on Computational Geometry, Berlin, Germany, June 10-12, 1992}
}
@inproceedings{conf/dimacs/AlonR92,
title = {Random Cayley Graphs and Expanders (Abstract).},
year = {1992},
booktitle = {Expanding Graphs},
author = {{Noga Alon} and {Yuval Roichman}},
publisher = {DIMACS/AMS},
booktitle = {Expanding Graphs, Proceedings of a DIMACS Workshop, Princeton, New Jersey, USA, May 11-14, 1992}
}
@inproceedings{conf/focs/AjtaiABCHNS92,
title = {Fault Tolerant Graphs, Perfect Hash Functions and Disjoint Paths},
year = {1992},
booktitle = {FOCS},
author = {{Miklós Ajtai} and {Noga Alon} and {Jehoshua Bruck} and {Robert Cypher} and {Ching-Tien Ho} and {Moni Naor} and {Endre Szemerédi}},
publisher = {IEEE Computer Society},
booktitle = {33rd Annual Symposium on Foundations of Computer Science, Pittsburgh, Pennsylvania, USA, 24-27 October 1992}
}
@inproceedings{conf/focs/AlonDLRY92,
title = {The Algorithmic Aspects of the Regularity Lemma (Extended Abstract)},
year = {1992},
booktitle = {FOCS},
author = {{Noga Alon} and {Richard A. Duke} and {Hanno Lefmann} and {Vojtech Rödl} and {Raphael Yuster}},
publisher = {IEEE Computer Society},
booktitle = {33rd Annual Symposium on Foundations of Computer Science, Pittsburgh, Pennsylvania, USA, 24-27 October 1992}
}
@inproceedings{conf/focs/AlonGMN92,
title = {Witnesses for Boolean Matrix Multiplication and for Shortest Paths},
year = {1992},
booktitle = {FOCS},
author = {{Noga Alon} and {Zvi Galil} and {Oded Margalit} and {Moni Naor}},
publisher = {IEEE Computer Society},
booktitle = {33rd Annual Symposium on Foundations of Computer Science, Pittsburgh, Pennsylvania, USA, 24-27 October 1992}
}
@inproceedings{conf/focs/AlonKRS92,
title = {Lower Bounds on the Competitive Ratio for Mobile User Tracking and Distributed Job Scheduling (Extended Abstract)},
year = {1992},
booktitle = {FOCS},
author = {{Noga Alon} and {Gil Kalai} and {Moty Ricklin} and {Larry J. Stockmeyer}},
publisher = {IEEE Computer Society},
booktitle = {33rd Annual Symposium on Foundations of Computer Science, Pittsburgh, Pennsylvania, USA, 24-27 October 1992}
}
@inproceedings{conf/soda/AlonA92,
title = {Comparison-Sorting and Selecting in Totally Monotone Matrices.},
year = {1992},
booktitle = {SODA},
author = {{Noga Alon} and {Yossi Azar}},
publisher = {ACM/SIAM},
booktitle = {Proceedings of the Third Annual ACM/SIGACT-SIAM Symposium on Discrete Algorithms, 27-29 January 1992, Orlando, Florida, USA.}
}
@article{journals/combinatorica/AlonMR92,
title = {Star arboricity.},
year = {1992},
journal = {Comb.},
author = {{Noga Alon} and {Colin McDiarmid} and {Bruce A. Reed}}
}
@article{journals/combinatorica/AlonT92,
title = {Colorings and orientations of graphs.},
year = {1992},
journal = {Comb.},
author = {{Noga Alon} and {Michael Tarsi}}
}
@article{journals/cpc/Alon92,
title = {Choice Numbers of Graphs: a Probabilistic Approach.},
year = {1992},
journal = {Comb. Probab. Comput.},
author = {{Noga Alon}}
}
@article{journals/cpc/AlonBFK92,
title = {Point Selections and Weak e-Nets for Convex Hulls.},
year = {1992},
journal = {Comb. Probab. Comput.},
author = {{Noga Alon} and {Imre Bárány} and {Zoltán Füredi} and {Daniel J. Kleitman}}
}
@article{journals/dam/Alon92,
title = {Transmitting in the n-Dimensional Cube.},
year = {1992},
journal = {Discret. Appl. Math.},
author = {{Noga Alon}}
}
@article{journals/dm/AlonK92,
title = {Partitioning a rectangle into small perimeter rectangles.},
year = {1992},
journal = {Discret. Math.},
author = {{Noga Alon} and {Daniel J. Kleitman}}
}
@article{journals/gc/AlonF92,
title = {Spanning subgraphs of random graphs.},
year = {1992},
journal = {Graphs Comb.},
author = {{Noga Alon} and {Zoltán Füredi}}
}
@article{journals/gc/AlonS92,
title = {Generalized sum graphs.},
year = {1992},
journal = {Graphs Comb.},
author = {{Noga Alon} and {Edward R. Scheinerman}}
}
@article{journals/gc/AlonY92,
title = {AlmostH-factors in dense graphs.},
year = {1992},
journal = {Graphs Comb.},
author = {{Noga Alon} and {Raphael Yuster}}
}
@article{journals/jal/AlonBLP92,
title = {Single Round Simulation on Radio Networks.},
year = {1992},
journal = {J. Algorithms},
author = {{Noga Alon} and {Amotz Bar-Noy} and {Nathan Linial} and {David Peleg}}
}
@article{journals/rsa/Alan92,
title = {The String Chromatic Number of a Graph.},
year = {1992},
journal = {Random Struct. Algorithms},
author = {{Noga Alon}}
}
@article{journals/rsa/AlonGHP92,
title = {Simple Construction of Almost k-wise Independent Random Variables.},
year = {1992},
journal = {Random Struct. Algorithms},
author = {{Noga Alon} and {Oded Goldreich 001} and {Johan Håstad} and {René Peralta 001}}
}
@article{journals/tit/AlonBNNR92,
title = {Construction of asymptotically good low-rate error-correcting codes through pseudo-random graphs.},
year = {1992},
journal = {IEEE Trans. Inf. Theory},
author = {{Noga Alon} and {Jehoshua Bruck} and {Joseph Naor} and {Moni Naor} and {Ron M. Roth}}
}
@inproceedings{conf/fiwac/AlonS93,
title = {Disjoint Systems (Extended Abstract).},
year = {1993},
booktitle = {Algebraic Coding},
author = {{Noga Alon} and {Benny Sudakov}},
publisher = {Springer},
booktitle = {Algebraic Coding, First French-Israeli Workshop, Paris, France, July 19-21, 1993, Proceedings}
}
@article{journals/cpc/AlonY93,
title = {Threshold Functions for H-factors.},
year = {1993},
journal = {Comb. Probab. Comput.},
author = {{Noga Alon} and {Raphael Yuster}}
}
@article{journals/dcg/AlonA93,
title = {On-Line Steine Trees in the Euclidean Plane.},
year = {1993},
journal = {Discret. Comput. Geom.},
author = {{Noga Alon} and {Yossi Azar}}
}
@article{journals/dm/AlonCK93,
title = {Bisection of trees and sequences.},
year = {1993},
journal = {Discret. Math.},
author = {{Noga Alon} and {Yair Caro} and {Ilia Krasikov}}
}
@article{journals/ejc/AlonF93,
title = {Covering the Cube by Affine Hyperplanes.},
year = {1993},
journal = {Eur. J. Comb.},
author = {{Noga Alon} and {Zoltán Füredi}}
}
@article{journals/jgt/AlonC93,
title = {On three zero-sum Ramsey-type problems.},
year = {1993},
journal = {J. Graph Theory},
author = {{Noga Alon} and {Yair Caro}}
}
@article{journals/rsa/AlonGHP93,
title = {Addendum to "Simple Construction of Almost k-wise Independent Random Variables".},
year = {1993},
journal = {Random Struct. Algorithms},
author = {{Noga Alon} and {Oded Goldreich 001} and {Johan Håstad} and {René Peralta 001}}
}
@article{journals/siamcomp/AlonN93,
title = {Coin-Flipping Games Immune Against Linear-Sized Coalitions.},
year = {1993},
journal = {SIAM J. Comput.},
author = {{Noga Alon} and {Moni Naor}}
}
@inproceedings{conf/esa/AlonYZ94,
title = {Finding and Counting Given Length Cycles (Extended Abstract).},
year = {1994},
booktitle = {ESA},
author = {{Noga Alon} and {Raphael Yuster} and {Uri Zwick}},
publisher = {Springer},
booktitle = {Algorithms - ESA '94, Second Annual European Symposium, Utrecht, The Netherlands, September 26-28, 1994, Proceedings}
}
@inproceedings{conf/focs/AlonFW94,
title = {Polynomial time randomised approxmiation schemes for the Tutte polynomial of dense graphs},
year = {1994},
booktitle = {FOCS},
author = {{Noga Alon} and {Alan M. Frieze} and {Dominic Welsh}},
publisher = {IEEE Computer Society},
booktitle = {35th Annual Symposium on Foundations of Computer Science, Santa Fe, New Mexico, USA, 20-22 November 1994}
}
@inproceedings{conf/soda/AlonBFKNO94,
title = {Matching Nuts and Bolts.},
year = {1994},
booktitle = {SODA},
author = {{Noga Alon} and {Manuel Blum 001} and {Amos Fiat} and {Sampath Kannan} and {Moni Naor} and {Rafail Ostrovsky}},
publisher = {ACM/SIAM},
booktitle = {Proceedings of the Fifth Annual ACM-SIAM Symposium on Discrete Algorithms. 23-25 January 1994, Arlington, Virginia, USA.}
}
@inproceedings{conf/stoc/AlonK94,
title = {A spectral technique for coloring random 3-colorable graphs (preliminary version).},
year = {1994},
booktitle = {STOC},
author = {{Noga Alon} and {Nabil Kahalé}},
publisher = {ACM},
booktitle = {Proceedings of the Twenty-Sixth Annual ACM Symposium on Theory of Computing, 23-25 May 1994, Montréal, Québec, Canada}
}
@inproceedings{conf/stoc/AlonYZ94,
title = {Color-coding: a new method for finding simple paths, cycles and other small subgraphs within large graphs.},
year = {1994},
booktitle = {STOC},
author = {{Noga Alon} and {Raphael Yuster} and {Uri Zwick}},
publisher = {ACM},
booktitle = {Proceedings of the Twenty-Sixth Annual ACM Symposium on Theory of Computing, 23-25 May 1994, Montréal, Québec, Canada}
}
@article{journals/combinatorics/Alon94,
title = {Explicit Ramsey graphs and orthonormal labelings.},
year = {1994},
journal = {Electron. J. Comb.},
author = {{Noga Alon}}
}
@article{journals/cpc/Nilli94,
title = {Perfect Hashing and Probability.},
year = {1994},
journal = {Comb. Probab. Comput.},
author = {{Alon Nilli}}
}
@article{journals/dcg/AgarwalAAS94,
title = {Can Visibility Graphs Be Represented Compactly?.},
year = {1994},
journal = {Discret. Comput. Geom.},
author = {{Pankaj K. Agarwal} and {Noga Alon} and {Boris Aronov} and {Subhash Suri}}
}
@article{journals/dm/Alon94,
title = {Probabilistic methods in coloring and decomposition problems.},
year = {1994},
journal = {Discret. Math.},
author = {{Noga Alon}}
}
@article{journals/eccc/ECCC-TR94-005,
title = {Polynomial Time Randomised Approximation Schemes for Tutte-Gröthendieck Invariants: The Dense Case},
year = {1994},
journal = {Electron. Colloquium Comput. Complex.},
author = {{Noga Alon} and {Alan M. Frieze} and {Dominic Welsh}}
}
@article{journals/gc/Alon94,
title = {Packing of partial designs.},
year = {1994},
journal = {Graphs Comb.},
author = {{Noga Alon}}
}
@article{journals/jacm/AlonM94,
title = {Parallel Linear Programming in Fixed Dimension Almost Surely in Constant Time.},
year = {1994},
journal = {J. ACM},
author = {{Noga Alon} and {Nimrod Megiddo}}
}
@article{journals/jal/AlonDLRY94,
title = {The Algorithmic Aspects of the Regularity Lemma.},
year = {1994},
journal = {J. Algorithms},
author = {{Noga Alon} and {Richard A. Duke} and {Hanno Lefmann} and {Vojtech Rödl} and {Raphael Yuster}}
}
@article{journals/jcss/AlonP94,
title = {Superconcentrators of Depths 2 and 3; Odd Levels Help (Rarely).},
year = {1994},
journal = {J. Comput. Syst. Sci.},
author = {{Noga Alon} and {Pavel Pudlák}}
}
@article{journals/jgt/Alon94,
title = {Subdivided graphs have linear ramsey numbers.},
year = {1994},
journal = {J. Graph Theory},
author = {{Noga Alon}}
}
@article{journals/rsa/AlonR94,
title = {Random Cayley Graphs and Expanders.},
year = {1994},
journal = {Random Struct. Algorithms},
author = {{Noga Alon} and {Yuval Roichman}}
}
@article{journals/siamdm/AlonB94,
title = {Explicit Constructions of Depth-2 Majority Circuits for Comparison and Addition.},
year = {1994},
journal = {SIAM J. Discret. Math.},
author = {{Noga Alon} and {Jehoshua Bruck}}
}
@article{journals/siamdm/AlonCG94,
title = {Routing Permutations on Graphs Via Matchings.},
year = {1994},
journal = {SIAM J. Discret. Math.},
author = {{Noga Alon} and {Fan R. K. Chung} and {Ronald L. Graham}}
}
@article{journals/siamdm/AlonST94,
title = {Planar Separators.},
year = {1994},
journal = {SIAM J. Discret. Math.},
author = {{Noga Alon} and {Paul D. Seymour} and {Robin Thomas 001}}
}
@article{journals/tcs/AlonKRS94,
title = {Lower Bounds on the Competitive Ratio for Mobile User Tracking and Distributed Job Scheduling.},
year = {1994},
journal = {Theor. Comput. Sci.},
author = {{Noga Alon} and {Gil Kalai} and {Moty Ricklin} and {Larry J. Stockmeyer}}
}
@article{journals/tit/AlonO94,
title = {A lower bound on the expected length of one-to-one codes.},
year = {1994},
journal = {IEEE Trans. Inf. Theory},
author = {{Noga Alon} and {Alon Orlitsky}}
}
@inproceedings{conf/esa/AlonGY95,
title = {Efficient Dynamic-Resharing "Verifiable Secret Sharing" Against Mobile Adversary.},
year = {1995},
booktitle = {ESA},
author = {{Noga Alon} and {Zvi Galil} and {Moti Yung}},
publisher = {Springer},
booktitle = {Algorithms - ESA '95, Third Annual European Symposium, Corfu, Greece, September 25-27, 1995, Proceedings}
}
@inproceedings{conf/focs/AlonEL95,
title = {Linear Time Erasure Codes with Nearly Optimal Recovery (Extended Abstract).},
year = {1995},
booktitle = {FOCS},
author = {{Noga Alon} and {Jeff Edmonds} and {Michael Luby}},
publisher = {IEEE Computer Society},
booktitle = {36th Annual Symposium on Foundations of Computer Science, Milwaukee, Wisconsin, USA, 23-25 October 1995}
}
@article{journals/cc/AlonFWZ95,
title = {Derandomized Graph Products.},
year = {1995},
journal = {Comput. Complex.},
author = {{Noga Alon} and {Uriel Feige} and {Avi Wigderson} and {David Zuckerman}}
}
@article{journals/combinatorica/AlonD95,
title = {A Lattice Point Problem and Additive Number Theory.},
year = {1995},
journal = {Comb.},
author = {{Noga Alon} and {Moshe Dubiner}}
}
@article{journals/dam/AlonST95,
title = {Covering with Latin Transversals.},
year = {1995},
journal = {Discret. Appl. Math.},
author = {{Noga Alon} and {Joel Spencer} and {Prasad Tetali}}
}
@article{journals/dcg/AlonK95,
title = {Bounding the Piercing Number.},
year = {1995},
journal = {Discret. Comput. Geom.},
author = {{Noga Alon} and {Gil Kalai}}
}
@article{journals/fuin/AlonRS95,
title = {Long Non-Crossing Configurations in the Plane.},
year = {1995},
journal = {Fundam. Informaticae},
author = {{Noga Alon} and {Sridhar Rajagopalan} and {Subhash Suri}}
}
@article{journals/ipl/AlonM95,
title = {epsilon-Discrepancy Sets and Their Application for Interpolation of Sparse Polynomials.},
year = {1995},
journal = {Inf. Process. Lett.},
author = {{Noga Alon} and {Yishay Mansour}}
}
@article{journals/jacm/AlonYZ95,
title = {Color-Coding.},
year = {1995},
journal = {J. ACM},
author = {{Noga Alon} and {Raphael Yuster} and {Uri Zwick}}
}
@article{journals/jct/AlonY95,
title = {The 123 Theorem and Its Extensions.},
year = {1995},
journal = {J. Comb. Theory, Ser. A},
author = {{Noga Alon} and {Raphael Yuster}}
}
@article{journals/rsa/AlonFW95,
title = {Polynomial Time Randomized Approximation Schemes for Tutte-Gröthendieck Invariants: The Dense Case.},
year = {1995},
journal = {Random Struct. Algorithms},
author = {{Noga Alon} and {Alan M. Frieze} and {Dominic Welsh}}
}
@article{journals/rsa/AlonS95,
title = {Disjoint Systems.},
year = {1995},
journal = {Random Struct. Algorithms},
author = {{Noga Alon} and {Benny Sudakov}}
}
@article{journals/rsa/AlonT95,
title = {The Acyclic Orientation Game on Random Graphs.},
year = {1995},
journal = {Random Struct. Algorithms},
author = {{Noga Alon} and {Zsolt Tuza}}
}
@article{journals/siamcomp/AlonKPW95,
title = {A Graph-Theoretic Game and Its Application to the k-Server Problem.},
year = {1995},
journal = {SIAM J. Comput.},
author = {{Noga Alon} and {Richard M. Karp} and {David Peleg} and {Douglas B. West}}
}
@article{journals/tit/AlonO95,
title = {Repeated communication and Ramsey graphs.},
year = {1995},
journal = {IEEE Trans. Inf. Theory},
author = {{Noga Alon} and {Alon Orlitsky}}
}
@inproceedings{conf/esa/AlonCSVW96,
title = {On-line and Off-line Approximation Algorithms for Vector Covering Problems.},
year = {1996},
booktitle = {ESA},
author = {{Noga Alon} and {János Csirik} and {Sergey V. Sevastianov} and {Arjen P. A. Vestjens} and {Gerhard J. Woeginger}},
publisher = {Springer},
booktitle = {Algorithms - ESA '96, Fourth Annual European Symposium, Barcelona, Spain, September 25-27, 1996, Proceedings}
}
@inproceedings{conf/focs/AlonKV96,
title = {The Geometry of Coin-Weighing Problems.},
year = {1996},
booktitle = {FOCS},
author = {{Noga Alon} and {Dmitry N. Kozlov} and {Van H. Vu}},
publisher = {IEEE Computer Society},
booktitle = {37th Annual Symposium on Foundations of Computer Science, FOCS '96, Burlington, Vermont, USA, 14-16 October, 1996}
}
@inproceedings{conf/icalp/AlonS96,
title = {Improved Parallel Approximation of a Class of Integer Programming Programming Problems.},
year = {1996},
booktitle = {ICALP},
author = {{Noga Alon} and {Aravind Srinivasan}},
publisher = {Springer},
booktitle = {Automata, Languages and Programming, 23rd International Colloquium, ICALP96, Paderborn, Germany, 8-12 July 1996, Proceedings}
}
@inproceedings{conf/swat/Alon96,
title = {Derandomization Via Small Sample Spaces (Abstract).},
year = {1996},
booktitle = {SWAT},
author = {{Noga Alon}},
publisher = {Springer},
booktitle = {Algorithm Theory - SWAT '96, 5th Scandinavian Workshop on Algorithm Theory, Reykjavík, Iceland, July 3-5, 1996, Proceedings}
}
@article{journals/algorithmica/AlonN96,
title = {Derandomization, Witnesses for Boolean Matrix Multiplication and Construction of Perfect Hash Functions.},
year = {1996},
journal = {Algorithmica},
author = {{Noga Alon} and {Moni Naor}}
}
@article{journals/combinatorica/Alon96,
title = {Bipartite Subgraphs.},
year = {1996},
journal = {Comb.},
author = {{Noga Alon}}
}
@article{journals/dm/AlonF96,
title = {2-factors in dense graphs.},
year = {1996},
journal = {Discret. Math.},
author = {{Noga Alon} and {Eldar Fischer}}
}
@article{journals/ipl/AlonBF96,
title = {Matching Nuts and Bolts Faster.},
year = {1996},
journal = {Inf. Process. Lett.},
author = {{Noga Alon} and {Phillip G. Bradford} and {Rudolf Fleischer}}
}
@article{journals/jct/Alon96,
title = {Disjoint Directed Cycles.},
year = {1996},
journal = {J. Comb. Theory, Ser. B},
author = {{Noga Alon}}
}
@article{journals/jct/AlonY96,
title = {H-Factors in Dense Graphs.},
year = {1996},
journal = {J. Comb. Theory, Ser. B},
author = {{Noga Alon} and {Raphael Yuster}}
}
@article{journals/jgt/AlonEHK96,
title = {On k-saturated graphs with restrictions on the degrees.},
year = {1996},
journal = {J. Graph Theory},
author = {{Noga Alon} and {Paul Erdös} and {Ron Holzman} and {Michael Krivelevich}}
}
@article{journals/jgt/AlonFH96,
title = {Vertex transversals that dominate.},
year = {1996},
journal = {J. Graph Theory},
author = {{Noga Alon} and {Michael R. Fellows} and {Donovan R. Hare}}
}
@article{journals/jgt/AlonMM96,
title = {Edge-disjoint cycles in regular directed graphs.},
year = {1996},
journal = {J. Graph Theory},
author = {{Noga Alon} and {Colin McDiarmid} and {Michael Molloy 001}}
}
@article{journals/njc/AlonKMH96,
title = {Approximate Hypergraph Coloring.},
year = {1996},
journal = {Nord. J. Comput.},
author = {{Noga Alon} and {Pierre Kelsen} and {Sanjeev Mahajan} and {Ramesh Hariharan}}
}
@article{journals/rsa/Alon96,
title = {Independence numbers of locally sparse graphs and a Ramsey type problem.},
year = {1996},
journal = {Random Struct. Algorithms},
author = {{Noga Alon}}
}
@article{journals/tit/AlonL96,
title = {A linear time erasure-resilient code with nearly optimal recovery.},
year = {1996},
journal = {IEEE Trans. Inf. Theory},
author = {{Noga Alon} and {Michael Luby}}
}
@article{journals/tit/AlonO96,
title = {Source coding and graph entropies.},
year = {1996},
journal = {IEEE Trans. Inf. Theory},
author = {{Noga Alon} and {Alon Orlitsky}}
}
@inproceedings{conf/soda/AlonAWY97,
title = {Approximation Schemes for Scheduling.},
year = {1997},
booktitle = {SODA},
author = {{Noga Alon} and {Yossi Azar} and {Gerhard J. Woeginger} and {Tal Yadid}},
publisher = {ACM/SIAM},
booktitle = {Proceedings of the Eighth Annual ACM-SIAM Symposium on Discrete Algorithms, 5-7 January 1997, New Orleans, Louisiana, USA.}
}
@inproceedings{conf/stoc/AlonDMPT97,
title = {Is Linear Hashing Good?},
year = {1997},
booktitle = {STOC},
author = {{Noga Alon} and {Martin Dietzfelbinger} and {Peter Bro Miltersen} and {Erez Petrank} and {Gábor Tardos}},
publisher = {ACM},
booktitle = {Proceedings of the Twenty-Ninth Annual ACM Symposium on the Theory of Computing, El Paso, Texas, USA, May 4-6, 1997}
}
@article{journals/algorithmica/AlonS97,
title = {Improved Parallel Approximation of a Class of Integer Programming Problems.},
year = {1997},
journal = {Algorithmica},
author = {{Noga Alon} and {Aravind Srinivasan}}
}
@article{journals/algorithmica/AlonYZ97,
title = {Finding and Counting Given Length Cycles.},
year = {1997},
journal = {Algorithmica},
author = {{Noga Alon} and {Raphael Yuster} and {Uri Zwick}}
}
@article{journals/combinatorica/AlonK97,
title = {The Concentration of the Chromatic Number of Random Graphs.},
year = {1997},
journal = {Comb.},
author = {{Noga Alon} and {Michael Krivelevich}}
}
@article{journals/combinatorics/AlonK97,
title = {A purely combinatorial proof of the Hadwiger Debrunner (p, q) Conjecture.},
year = {1997},
journal = {Electron. J. Comb.},
author = {{Noga Alon} and {Daniel J. Kleitman}}
}
@article{journals/combinatorics/AlonR97,
title = {Short Certificates for Tournaments.},
year = {1997},
journal = {Electron. J. Comb.},
author = {{Noga Alon} and {Miklós Ruszinkó}}
}
@article{journals/cpc/AhlswedeAERS97,
title = {Intersecting Systems.},
year = {1997},
journal = {Comb. Probab. Comput.},
author = {{Rudolf Ahlswede} and {Noga Alon} and {Péter L. Erdös} and {Miklós Ruszinkó} and {László A. Székely}}
}
@article{journals/cpc/Alon97,
title = {On the Edge-Expansion of Graphs.},
year = {1997},
journal = {Comb. Probab. Comput.},
author = {{Noga Alon}}
}
@article{journals/dm/Alon97,
title = {Packings with large minimum kissing numbers.},
year = {1997},
journal = {Discret. Math.},
author = {{Noga Alon}}
}
@article{journals/dm/AlonTV97,
title = {Choosability and fractional chromatic numbers.},
year = {1997},
journal = {Discret. Math.},
author = {{Noga Alon} and {Zsolt Tuza} and {Margit Voigt}}
}
@article{journals/gc/AlonK97,
title = {Constructive Bounds for a Ramsey-Type Problem.},
year = {1997},
journal = {Graphs Comb.},
author = {{Noga Alon} and {Michael Krivelevich}}
}
@article{journals/jacm/AlonBCH97,
title = {Scale-sensitive dimensions, uniform convergence, and learnability.},
year = {1997},
journal = {J. ACM},
author = {{Noga Alon} and {Shai Ben-David} and {Nicolò Cesa-Bianchi} and {David Haussler}}
}
@article{journals/jal/AlonK97,
title = {Coins with Arbitrary Weights.},
year = {1997},
journal = {J. Algorithms},
author = {{Noga Alon} and {Dmitry N. Kozlov}}
}
@article{journals/jcss/AlonGM97,
title = {On the Exponent of the All Pairs Shortest Path Problem.},
year = {1997},
journal = {J. Comput. Syst. Sci.},
author = {{Noga Alon} and {Zvi Galil} and {Oded Margalit}}
}
@article{journals/jct/AlonCY97,
title = {Covering the Edges of a Graph by a Prescribed Tree with Minimum Overlap.},
year = {1997},
journal = {J. Comb. Theory, Ser. B},
author = {{Noga Alon} and {Yair Caro} and {Raphael Yuster}}
}
@article{journals/jct/AlonK97,
title = {On the Degree, Size, and Chromatic Index of a Uniform Hypergraph.},
year = {1997},
journal = {J. Comb. Theory, Ser. A},
author = {{Noga Alon} and {Jeong Han Kim}}
}
@article{journals/jct/AlonT97,
title = {A Note on Graph Colorings and Graph Polynomials.},
year = {1997},
journal = {J. Comb. Theory, Ser. B},
author = {{Noga Alon} and {Michael Tarsi}}
}
@article{journals/jct/AlonV97,
title = {Anti-Hadamard Matrices, Coin Weighing, Threshold Gates, and Indecomposable Hypergraphs.},
year = {1997},
journal = {J. Comb. Theory, Ser. A},
author = {{Noga Alon} and {Van H. Vu}}
}
@article{journals/rsa/AlonG97,
title = {Properly colored Hamilton cycles in edge-colored complete graphs.},
year = {1997},
journal = {Random Struct. Algorithms},
author = {{Noga Alon} and {Gregory Z. Gutin}}
}
@article{journals/siamcomp/AlonK97,
title = {A Spectral Technique for Coloring Random 3-Colorable Graphs.},
year = {1997},
journal = {SIAM J. Comput.},
author = {{Noga Alon} and {Nabil Kahalé}}
}
@inproceedings{conf/latin/Alon98,
title = {Spectral Techniques in Graph Algorithms.},
year = {1998},
booktitle = {LATIN},
author = {{Noga Alon}},
publisher = {Springer},
booktitle = {LATIN '98: Theoretical Informatics, Third Latin American Symposium, Campinas, Brazil, April, 20-24, 1998, Proceedings}
}
@article{journals/algorithmica/AlonACESVW98,
title = {On-Line and Off-Line Approximation Algorithms for Vector Covering Problems.},
year = {1998},
journal = {Algorithmica},
author = {{Noga Alon} and {Yossi Azar} and {János Csirik} and {Leah Epstein} and {Sergey V. Sevastianov} and {Arjen P. A. Vestjens} and {Gerhard J. Woeginger}}
}
@article{journals/combinatorica/Alon98,
title = {The Shannon Capacity of a Union.},
year = {1998},
journal = {Comb.},
author = {{Noga Alon}}
}
@article{journals/combinatorics/AlonRR98,
title = {Perfect Matchings in ε-regular Graphs.},
year = {1998},
journal = {Electron. J. Comb.},
author = {{Noga Alon} and {Vojtech Rödl} and {Andrzej Rucinski 001}}
}
@article{journals/dam/AlonZ98,
title = {T-choosability in Graphs.},
year = {1998},
journal = {Discret. Appl. Math.},
author = {{Noga Alon} and {Ayal Zaks}}
}
@article{journals/dcg/Alon98,
title = {Piercing d -Intervals.},
year = {1998},
journal = {Discret. Comput. Geom.},
author = {{Noga Alon}}
}
@article{journals/dm/AlonH98,
title = {Bipartite subgraphs of integer weighted graphs.},
year = {1998},
journal = {Discret. Math.},
author = {{Noga Alon} and {Eran Halperin}}
}
@article{journals/ejc/Alon98,
title = {On the Capacity of Digraphs.},
year = {1998},
journal = {Eur. J. Comb.},
author = {{Noga Alon}}
}
@article{journals/jct/AlonZ98,
title = {Progressions in Sequences of Nearly Consecutive Integers.},
year = {1998},
journal = {J. Comb. Theory, Ser. A},
author = {{Noga Alon} and {Ayal Zaks}}
}
@article{journals/mp/AlonK98,
title = {Approximating the independence number via the theta-function.},
year = {1998},
journal = {Math. Program.},
author = {{Noga Alon} and {Nabil Kahalé}}
}
@article{journals/rsa/AlonKS98,
title = {Finding a large hidden clique in a random graph.},
year = {1998},
journal = {Random Struct. Algorithms},
author = {{Noga Alon} and {Michael Krivelevich} and {Benny Sudakov}}
}
@inproceedings{conf/random/AlonAA99,
title = {Independent Sets in Hypergraphs with Applications to Routing via Fixed Paths.},
year = {1999},
booktitle = {RANDOM-APPROX},
author = {{Noga Alon} and {Uri Arad} and {Yossi Azar}},
publisher = {Springer},
booktitle = {Randomization, Approximation, and Combinatorial Algorithms and Techniques, Third International Workshop on Randomization and Approximation Techniques in Computer Science, and Second International Workshop on Approximation Algorithms for Combinatorial Optimization Problems RANDOM-APPROX'99, Berkeley, CA, USA, August 8-11, 1999, Proceedings}
}
@article{journals/arscom/AlonF99,
title = {Refining the Graph Density Condition for the Existence of Almost K-factors.},
year = {1999},
journal = {Ars Comb.},
author = {{Noga Alon} and {Eldar Fischer}}
}
@article{journals/combinatorica/AlonKS99,
title = {List Coloring of Random and Pseudo-Random Graphs.},
year = {1999},
journal = {Comb.},
author = {{Noga Alon} and {Michael Krivelevich} and {Benny Sudakov}}
}
@article{journals/dam/AlonO99,
title = {Separable Partitions.},
year = {1999},
journal = {Discret. Appl. Math.},
author = {{Noga Alon} and {Shmuel Onn}}
}
@article{journals/ejc/AlonHK99,
title = {Regular Honest Graphs, Isoperimetric Numbers, and Bisection of Weighted Graphs.},
year = {1999},
journal = {Eur. J. Comb.},
author = {{Noga Alon} and {Peter Hamburger} and {Alexandr V. Kostochka}}
}
@article{journals/gc/AlonS99,
title = {Large Sets of Nearly Orthogonal Vectors.},
year = {1999},
journal = {Graphs Comb.},
author = {{Noga Alon} and {Mario Szegedy}}
}
@article{journals/jacm/AlonDMPT99,
title = {Linear Hash Functions.},
year = {1999},
journal = {J. ACM},
author = {{Noga Alon} and {Martin Dietzfelbinger} and {Peter Bro Miltersen} and {Erez Petrank} and {Gábor Tardos}}
}
@article{journals/jal/AlonS99,
title = {On Two Segmentation Problems.},
year = {1999},
journal = {J. Algorithms},
author = {{Noga Alon} and {Benny Sudakov}}
}
@article{journals/jcss/AlonMS99,
title = {The Space Complexity of Approximating the Frequency Moments.},
year = {1999},
journal = {J. Comput. Syst. Sci.},
author = {{Noga Alon} and {Yossi Matias} and {Mario Szegedy}}
}
@article{journals/jct/AlonKS99,
title = {Coloring Graphs with Sparse Neighborhoods.},
year = {1999},
journal = {J. Comb. Theory, Ser. B},
author = {{Noga Alon} and {Michael Krivelevich} and {Benny Sudakov}}
}
@article{journals/jct/AlonR99,
title = {Non-averaging Subsets and Non-vanishing Transversals.},
year = {1999},
journal = {J. Comb. Theory, Ser. A},
author = {{Noga Alon} and {Imre Z. Ruzsa}}
}
@article{journals/jct/AlonRS99,
title = {Norm-Graphs: Variations and Applications.},
year = {1999},
journal = {J. Comb. Theory, Ser. B},
author = {{Noga Alon} and {Lajos Rónyai} and {Tibor Szabó}}
}
@article{journals/jgt/Nilli99,
title = {Short odd cycles in 4-chromatic graphs.},
year = {1999},
journal = {J. Graph Theory},
author = {{Alon Nilli}}
}
@book{books/wi/AlonS00,
title = {The Probabilistic Method, Second Edition},
year = {2000},
isbn = {978-0-47172215-1},
publisher = {John Wiley},
author = {{Noga Alon} and {Joel H. Spencer}}
}
@inproceedings{conf/focs/AlonCKRRS00,
title = {Universality and Tolerance.},
year = {2000},
booktitle = {FOCS},
author = {{Noga Alon} and {Michael R. Capalbo} and {Yoshiharu Kohayakawa} and {Vojtech Rödl} and {Andrzej Rucinski 001} and {Endre Szemerédi}},
publisher = {IEEE Computer Society},
booktitle = {41st Annual Symposium on Foundations of Computer Science, FOCS 2000, 12-14 November 2000, Redondo Beach, California, USA}
}
@article{journals/combinatorica/AlonFKS00,
title = {Efficient Testing of Large Graphs.},
year = {2000},
journal = {Comb.},
author = {{Noga Alon} and {Eldar Fischer} and {Michael Krivelevich} and {Mario Szegedy}}
}
@article{journals/cpc/AlonBS00,
title = {Packing Ferrers Shapes.},
year = {2000},
journal = {Comb. Probab. Comput.},
author = {{Noga Alon} and {Miklós Bóna} and {Joel Spencer}}
}
@article{journals/cpc/AlonFK00,
title = {Locally Thin Set Families.},
year = {2000},
journal = {Comb. Probab. Comput.},
author = {{Noga Alon} and {Emanuela Fachini} and {János Körner}}
}
@article{journals/cpc/AlonKM00,
title = {String Quartets In Binary.},
year = {2000},
journal = {Comb. Probab. Comput.},
author = {{Noga Alon} and {János Körner} and {Angelo Monti}}
}
@article{journals/cpc/AlonS00,
title = {Bipartite Subgraphs And The Smallest Eigenvalue.},
year = {2000},
journal = {Comb. Probab. Comput.},
author = {{Noga Alon} and {Benny Sudakov}}
}
@article{journals/dm/Nilli00,
title = {Triangle-free graphs with large chromatic numbers.},
year = {2000},
journal = {Discret. Math.},
author = {{Alon Nilli}}
}
@article{journals/ejc/Yuster00,
title = {EveryH-decomposition ofKnhas a Nearly Resolvable Alternative.},
year = {2000},
journal = {Eur. J. Comb.},
author = {{Noga Alon} and {Raphael Yuster}}
}
@article{journals/jct/AlonBK00,
title = {On a Problem in Shuffling.},
year = {2000},
journal = {J. Comb. Theory, Ser. A},
author = {{Noga Alon} and {Kenneth A. Berman} and {Daniel J. Kleitman}}
}
@article{journals/jct/AlonF00,
title = {On the Number of Permutations Avoiding a Given Pattern.},
year = {2000},
journal = {J. Comb. Theory, Ser. A},
author = {{Noga Alon} and {Ehud Friedgut}}
}
@article{journals/jgt/AlonGR00,
title = {Decreasing the diameter of bounded degree graphs.},
year = {2000},
journal = {J. Graph Theory},
author = {{Noga Alon} and {András Gyárfás} and {Miklós Ruszinkó}}
}
@article{journals/jgt/AlonKS00,
title = {Long cycles in critical graphs.},
year = {2000},
journal = {J. Graph Theory},
author = {{Noga Alon} and {Michael Krivelevich} and {Paul D. Seymour}}
}
@article{journals/rsa/Alon00,
title = {Degrees and choice numbers.},
year = {2000},
journal = {Random Struct. Algorithms},
author = {{Noga Alon}}
}
@article{journals/siamcomp/AlonKNS00,
title = {Regular Languages are Testable with a Constant Number of Queries.},
year = {2000},
journal = {SIAM J. Comput.},
author = {{Noga Alon} and {Michael Krivelevich} and {Ilan Newman} and {Mario Szegedy}}
}
@inproceedings{conf/coco/AlonB01,
title = {Lower Bounds for Approximations by Low Degree Polynomials Over Zm.},
year = {2001},
booktitle = {CCC},
author = {{Noga Alon} and {Richard Beigel}},
publisher = {IEEE Computer Society},
booktitle = {Proceedings of the 16th Annual IEEE Conference on Computational Complexity, Chicago, Illinois, USA, June 18-21, 2001}
}
@inproceedings{conf/focs/AlonLW01,
title = {Semi-Direct Product in Groups and Zig-Zag Product in Graphs: Connections and Applications.},
year = {2001},
booktitle = {FOCS},
author = {{Noga Alon} and {Alexander Lubotzky} and {Avi Wigderson}},
publisher = {IEEE Computer Society},
booktitle = {42nd Annual Symposium on Foundations of Computer Science, FOCS 2001, 14-17 October 2001, Las Vegas, Nevada, USA}
}
@inproceedings{conf/random/AlonCKRRS01,
title = {Near-optimum Universal Graphs for Graphs with Bounded Degrees.},
year = {2001},
booktitle = {RANDOM-APPROX},
author = {{Noga Alon} and {Michael R. Capalbo} and {Yoshiharu Kohayakawa} and {Vojtech Rödl} and {Andrzej Rucinski 001} and {Endre Szemerédi}},
publisher = {Springer},
booktitle = {Approximation, Randomization and Combinatorial Optimization: Algorithms and Techniques, 4th International Workshop on Approximation Algorithms for Combinatorial Optimization Problems, APPROX 2001 and 5th International Workshop on Randomization and Approximation Techniques in Computer Science, RANDOM 2001 Berkeley, CA, USA, August 18-20, 2001, Proceedings}
}
@inproceedings{conf/recomb/BeigelAKAF01,
title = {An optimal procedure for gap closing in whole genome shotgun sequencing.},
year = {2001},
booktitle = {RECOMB},
author = {{Richard Beigel} and {Noga Alon} and {Simon Kasif} and {Mehmet Serkan Apaydin} and {Lance Fortnow}},
publisher = {ACM},
booktitle = {Proceedings of the Fifth Annual International Conference on Computational Biology, RECOMB 2001, Montréal, Québec, Canada, April 22-25, 2001}
}
@article{journals/combinatorica/AlonPS01,
title = {Ramsey-type Theorems with Forbidden Subgraphs.},
year = {2001},
journal = {Comb.},
author = {{Noga Alon} and {János Pach} and {József Solymosi}}
}
@article{journals/dam/FachiniN01,
title = {Recursive bounds for perfect hashing.},
year = {2001},
journal = {Discret. Appl. Math.},
author = {{Emanuela Fachini} and {Alon Nilli}}
}
@article{journals/dcg/AlonLPS01,
title = {On the Complexity of Arrangements of Circles in the Plane.},
year = {2001},
journal = {Discret. Comput. Geom.},
author = {{Noga Alon} and {Hagit Last} and {Rom Pinchasi} and {Micha Sharir}}
}
@article{journals/eccc/ECCC-TR01-100,
title = {Random Sampling and Approximation of MAX-CSP Problems},
year = {2001},
journal = {Electron. Colloquium Comput. Complex.},
author = {{Noga Alon} and {Wenceslas Fernandez de la Vega} and {Ravi Kannan} and {Marek Karpinski}}
}
@article{journals/gc/AlonTW01,
title = {Linear Arboricity and Linear k-Arboricity of Regular Graphs.},
year = {2001},
journal = {Graphs Comb.},
author = {{Noga Alon} and {Vanessa Teague} and {Nicholas C. Wormald}}
}
@article{journals/jct/AlonFS01,
title = {Parent-Identifying Codes.},
year = {2001},
journal = {J. Comb. Theory, Ser. A},
author = {{Noga Alon} and {Eldar Fischer} and {Mario Szegedy}}
}
@article{journals/jct/AlonL01,
title = {Unextendible Product Bases.},
year = {2001},
journal = {J. Comb. Theory, Ser. A},
author = {{Noga Alon} and {László Lovász 001}}
}
@article{journals/jgt/AlonMT01,
title = {Large induced forests in sparse graphs.},
year = {2001},
journal = {J. Graph Theory},
author = {{Noga Alon} and {Dhruv Mubayi} and {Robin Thomas 001}}
}
@article{journals/jgt/AlonSZ01,
title = {Acyclic edge colorings of graphs.},
year = {2001},
journal = {J. Graph Theory},
author = {{Noga Alon} and {Benny Sudakov} and {Ayal Zaks}}
}
@article{journals/rsa/AdlerAR01,
title = {On the maximum number of Hamiltonian paths in tournaments.},
year = {2001},
journal = {Random Struct. Algorithms},
author = {{Ilan Adler} and {Noga Alon} and {Sheldon M. Ross}}
}
@article{journals/siamdm/AlonCLT01,
title = {Equireplicate Balanced Binary Codes for Oligo Arrays.},
year = {2001},
journal = {SIAM J. Discret. Math.},
author = {{Noga Alon} and {Charles J. Colbourn} and {Alan C. H. Ling} and {Martin Tompa}}
}
@article{journals/siamdm/AlonSZ01,
title = {Constructing Worst Case Instances for Semidefinite Programming Based Approximation Algorithms.},
year = {2001},
journal = {SIAM J. Discret. Math.},
author = {{Noga Alon} and {Benny Sudakov} and {Uri Zwick}}
}
@inproceedings{conf/focs/AlonC02,
title = {Explicit Unique-Neighbor Expanders.},
year = {2002},
booktitle = {FOCS},
author = {{Noga Alon} and {Michael R. Capalbo}},
publisher = {IEEE Computer Society},
booktitle = {43rd Symposium on Foundations of Computer Science (FOCS 2002), 16-19 November 2002, Vancouver, BC, Canada, Proceedings}
}
@article{journals/aam/Alon02,
title = {Voting paradoxes and digraphs realizations.},
year = {2002},
journal = {Adv. Appl. Math.},
author = {{Noga Alon}}
}
@article{journals/aam/AlonK0M02,
title = {Transversal numbers for hypergraphs arising in geometry.},
year = {2002},
journal = {Adv. Appl. Math.},
author = {{Noga Alon} and {Gil Kalai} and {Jirí Matousek 001} and {Roy Meshulam}}
}
@article{journals/algorithmica/AlonZ02,
title = {Algorithmic Aspects of Acyclic Edge Colorings.},
year = {2002},
journal = {Algorithmica},
author = {{Noga Alon} and {Ayal Zaks}}
}
@article{journals/cpc/AlonM02,
title = {The Chromatic Number Of Graph Powers.},
year = {2002},
journal = {Comb. Probab. Comput.},
author = {{Noga Alon} and {Bojan Mohar}}
}
@article{journals/dm/Alon02,
title = {Covering a hypergraph of subgraphs.},
year = {2002},
journal = {Discret. Math.},
author = {{Noga Alon}}
}
@article{journals/dm/AlonBBS02,
title = {Game domination number.},
year = {2002},
journal = {Discret. Math.},
author = {{Noga Alon} and {József Balogh} and {Béla Bollobás} and {Tamás Szabó}}
}
@article{journals/dm/AlonBHK02,
title = {On partitions of discrete boxes.},
year = {2002},
journal = {Discret. Math.},
author = {{Noga Alon} and {Tom Bohman} and {Ron Holzman} and {Daniel J. Kleitman}}
}
@article{journals/gc/AlonHL02,
title = {The Moore Bound for Irregular Graphs.},
year = {2002},
journal = {Graphs Comb.},
author = {{Noga Alon} and {Shlomo Hoory} and {Nathan Linial}}
}
@article{journals/iandc/AlonKKMS02,
title = {Scalable Secure Storage When Half the System Is Faulty.},
year = {2002},
journal = {Inf. Comput.},
author = {{Noga Alon} and {Haim Kaplan} and {Michael Krivelevich} and {Dahlia Malkhi} and {Julien P. Stern}}
}
@article{journals/jcss/AlonGMS02,
title = {Tracking Join and Self-Join Sizes in Limited Storage.},
year = {2002},
journal = {J. Comput. Syst. Sci.},
author = {{Noga Alon} and {Phillip B. Gibbons} and {Yossi Matias} and {Mario Szegedy}}
}
@article{journals/jgt/AlonEGM02,
title = {A Ramsey-type problem and the Turán numbers.},
year = {2002},
journal = {J. Graph Theory},
author = {{Noga Alon} and {Paul Erdös} and {David S. Gunderson} and {Michael Molloy 001}}
}
@article{journals/rsa/Alon02,
title = {Testing subgraphs in large graphs.},
year = {2002},
journal = {Random Struct. Algorithms},
author = {{Noga Alon}}
}
@article{journals/rsa/AlonDLS02,
title = {On the discrepancy of combinatorial rectangles.},
year = {2002},
journal = {Random Struct. Algorithms},
author = {{Noga Alon} and {Benjamin Doerr} and {Tomasz Luczak 001} and {Tomasz Schoen}}
}
@article{journals/rsa/AlonGHR02,
title = {Nonrepetitive colorings of graphs.},
year = {2002},
journal = {Random Struct. Algorithms},
author = {{Noga Alon} and {Jaroslaw Grytczuk} and {Mariusz Haluszczak} and {Oliver Riordan}}
}
@article{journals/siamdm/AlonK02,
title = {Testing k-colorability.},
year = {2002},
journal = {SIAM J. Discret. Math.},
author = {{Noga Alon} and {Michael Krivelevich}}
}
@inproceedings{conf/random/AlonKKLR03,
title = {Testing Low-Degree Polynomials over GF(2(.},
year = {2003},
booktitle = {RANDOM-APPROX},
author = {{Noga Alon} and {Tali Kaufman} and {Michael Krivelevich} and {Simon Litsyn} and {Dana Ron}},
publisher = {Springer},
booktitle = {Approximation, Randomization, and Combinatorial Optimization: Algorithms and Techniques, 6th International Workshop on Approximation Algorithms for Combinatorial Optimization Problems, APPROX 2003 and 7th International Workshop on Randomization and Approximation Techniques in Computer Science, RANDOM 2003, Princeton, NJ, USA, August 24-26, 2003, Proceedings}
}
@article{journals/cpc/AlonKS03,
title = {Tura'n Numbers of Bipartite Graphs and Related Ramsey-Type Questions.},
year = {2003},
journal = {Comb. Probab. Comput.},
author = {{Noga Alon} and {Michael Krivelevich} and {Benny Sudakov}}
}
@article{journals/dm/Alon03,
title = {Problems and results in extremal combinatorics--I.},
year = {2003},
journal = {Discret. Math.},
author = {{Noga Alon}}
}
@article{journals/dm/AlonFLSS03,
title = {Factor d-domatic colorings of graphs.},
year = {2003},
journal = {Discret. Math.},
author = {{Noga Alon} and {Guillaume Fertin} and {Arthur L. Liestman} and {Thomas C. Shermer} and {Ladislav Stacho}}
}
@article{journals/gc/AlonLY03,
title = {A Coding Theory Bound and Zero-Sum Square Matrices.},
year = {2003},
journal = {Graphs Comb.},
author = {{Noga Alon} and {Simon Litsyn} and {Raphael Yuster}}
}
@article{journals/im/AlonC03,
title = {Smaller Explicit Superconcentrators.},
year = {2003},
journal = {Internet Math.},
author = {{Noga Alon} and {Michael R. Capalbo}}
}
@article{journals/ipl/Alon03,
title = {A simple algorithm for edge-coloring bipartite multigraphs.},
year = {2003},
journal = {Inf. Process. Lett.},
author = {{Noga Alon}}
}
@article{journals/ipl/AlonGM03,
title = {Almost k-wise independence versus k-wise independence.},
year = {2003},
journal = {Inf. Process. Lett.},
author = {{Noga Alon} and {Oded Goldreich 001} and {Yishay Mansour}}
}
@article{journals/jal/AlonS03,
title = {Testing satisfiability.},
year = {2003},
journal = {J. Algorithms},
author = {{Noga Alon} and {Asaf Shapira}}
}
@article{journals/jcss/AlonMNSV03,
title = {XML with data values: typechecking revisited.},
year = {2003},
journal = {J. Comput. Syst. Sci.},
author = {{Noga Alon} and {Tova Milo} and {Frank Neven} and {Dan Suciu} and {Victor Vianu}}
}
@article{journals/jcss/AlonVKK03,
title = {Random sampling and approximation of MAX-CSPs.},
year = {2003},
journal = {J. Comput. Syst. Sci.},
author = {{Noga Alon} and {Wenceslas Fernandez de la Vega} and {Ravi Kannan} and {Marek Karpinski}}
}
@article{journals/jct/AlonBKS03,
title = {Maximum cuts and judicious partitions in graphs without short cycles.},
year = {2003},
journal = {J. Comb. Theory, Ser. B},
author = {{Noga Alon} and {Béla Bollobás} and {Michael Krivelevich} and {Benny Sudakov}}
}
@article{journals/jct/AlonCKL03,
title = {Generalized hashing and parent-identifying codes.},
year = {2003},
journal = {J. Comb. Theory, Ser. A},
author = {{Noga Alon} and {Gérard D. Cohen} and {Michael Krivelevich} and {Simon Litsyn}}
}
@article{journals/jct/AlonDV03,
title = {Partitioning into graphs with only small components.},
year = {2003},
journal = {J. Comb. Theory, Ser. B},
author = {{Noga Alon} and {Guoli Ding} and {Bogdan Oporowski} and {Dirk Vertigan}}
}
@article{journals/jgt/AlonKS03,
title = {Induced subgraphs of prescribed size.},
year = {2003},
journal = {J. Graph Theory},
author = {{Noga Alon} and {Michael Krivelevich} and {Benny Sudakov}}
}
@article{journals/rsa/AlonJMP03,
title = {Properly colored subgraphs and rainbow subgraphs in edge-colorings with local constraints.},
year = {2003},
journal = {Random Struct. Algorithms},
author = {{Noga Alon} and {Tao Jiang 003} and {Zevi Miller} and {Dan Pritikin}}
}
@article{journals/siamdm/AlonDPR03,
title = {Testing of Clustering.},
year = {2003},
journal = {SIAM J. Discret. Math.},
author = {{Noga Alon} and {Seannie Dar} and {Michal Parnas} and {Dana Ron}}
}
@article{journals/tocl/AlonMNSV03,
title = {Typechecking XML views of relational databases.},
year = {2003},
journal = {ACM Trans. Comput. Log.},
author = {{Noga Alon} and {Tova Milo} and {Frank Neven} and {Dan Suciu} and {Victor Vianu}}
}
@inproceedings{conf/approx/AlonA04,
title = {Edge Coloring with Delays.},
year = {2004},
booktitle = {APPROX-RANDOM},
author = {{Noga Alon} and {Vera Asodi}},
publisher = {Springer},
booktitle = {Approximation, Randomization, and Combinatorial Optimization, Algorithms and Techniques, 7th International Workshop on Approximation Algorithms for Combinatorial Optimization Problems, APPROX 2004, and 8th International Workshop on Randomization and Computation, RANDOM 2004, Cambridge, MA, USA, August 22-24, 2004, Proceedings}
}
@inproceedings{conf/nips/SrebroAJ04,
title = {Generalization Error Bounds for Collaborative Prediction with Low-Rank Matrices.},
year = {2004},
booktitle = {NIPS},
author = {{Nathan Srebro} and {Noga Alon} and {Tommi S. Jaakkola}},
booktitle = {Advances in Neural Information Processing Systems 17 [Neural Information Processing Systems, NIPS 2004, December 13-18, 2004, Vancouver, British Columbia, Canada]}
}
@article{journals/combinatorics/Nilli04,
title = {Tight Estimates for Eigenvalues of Regular Graphs.},
year = {2004},
journal = {Electron. J. Comb.},
author = {{Alon Nilli}}
}
@article{journals/cpc/AlonS04,
title = {New Bounds on Parent-Identifying Codes: The Case of Multiple Parents.},
year = {2004},
journal = {Comb. Probab. Comput.},
author = {{Noga Alon} and {Uri Stav}}
}
@article{journals/jal/AlonGK04,
title = {Algorithms with large domination ratio.},
year = {2004},
journal = {J. Algorithms},
author = {{Noga Alon} and {Gregory Z. Gutin} and {Michael Krivelevich}}
}
@article{journals/jcss/AlonS04,
title = {Testing subgraphs in directed graphs.},
year = {2004},
journal = {J. Comput. Syst. Sci.},
author = {{Noga Alon} and {Asaf Shapira}}
}
@article{journals/jgt/AlonKLRY04,
title = {Dense graphs are antimagic.},
year = {2004},
journal = {J. Graph Theory},
author = {{Noga Alon} and {Gil Kaplan} and {Arieh Lev} and {Yehuda Roditty} and {Raphael Yuster}}
}
@article{journals/siamcomp/AlonBKRS04,
title = {Learning a Hidden Matching.},
year = {2004},
journal = {SIAM J. Comput.},
author = {{Noga Alon} and {Richard Beigel} and {Simon Kasif} and {Steven Rudich} and {Benny Sudakov}}
}
@inproceedings{conf/focs/AlonSS05,
title = {Additive Approximation for Edge-Deletion Problems.},
year = {2005},
booktitle = {FOCS},
author = {{Noga Alon} and {Asaf Shapira} and {Benny Sudakov}},
publisher = {IEEE Computer Society},
booktitle = {46th Annual IEEE Symposium on Foundations of Computer Science (FOCS 2005), 23-25 October 2005, Pittsburgh, PA, USA, Proceedings}
}
@inproceedings{conf/pods/AlonDLT05,
title = {Estimating arbitrary subset sums with few probes.},
year = {2005},
booktitle = {PODS},
author = {{Noga Alon} and {Nick G. Duffield} and {Carsten Lund} and {Mikkel Thorup}},
publisher = {ACM},
booktitle = {Proceedings of the Twenty-fourth ACM SIGACT-SIGMOD-SIGART Symposium on Principles of Database Systems, June 13-15, 2005, Baltimore, Maryland, USA}
}
@inproceedings{conf/stoc/AlonMMN05,
title = {Quadratic forms on graphs.},
year = {2005},
booktitle = {STOC},
author = {{Noga Alon} and {Konstantin Makarychev} and {Yury Makarychev} and {Assaf Naor}},
publisher = {ACM},
booktitle = {Proceedings of the 37th Annual ACM Symposium on Theory of Computing, Baltimore, MD, USA, May 22-24, 2005}
}
@article{journals/combinatorica/AlonR05,
title = {Sharp Bounds For Some Multicolor Ramsey Numbers.},
year = {2005},
journal = {Comb.},
author = {{Noga Alon} and {Vojtech Rödl}}
}
@article{journals/combinatorics/AlonKSS05,
title = {Discrepancy Games.},
year = {2005},
journal = {Electron. J. Comb.},
author = {{Noga Alon} and {Michael Krivelevich} and {Joel Spencer} and {Tibor Szabó}}
}
@article{journals/dc/AlonMRTW05,
title = {Tight bounds for shared memory systems accessed by Byzantine processes.},
year = {2005},
journal = {Distributed Comput.},
author = {{Noga Alon} and {Michael Merritt} and {Omer Reingold} and {Gadi Taubenfeld} and {Rebecca N. Wright}}
}
@article{journals/eccc/ECCC-TR05-085,
title = {Homomorphisms in Graph Property Testing - A Survey},
year = {2005},
journal = {Electron. Colloquium Comput. Complex.},
author = {{Asaf Shapira} and {Noga Alon}}
}
@article{journals/endm/AlonG05,
title = {Nonrepetitive colorings of graphs.},
year = {2005},
journal = {Electron. Notes Discret. Math.},
author = {{Noga Alon} and {Jaroslaw Grytczuk}}
}
@article{journals/gc/AlonY05,
title = {On a Hypergraph Matching Problem.},
year = {2005},
journal = {Graphs Comb.},
author = {{Noga Alon} and {Raphael Yuster}}
}
@article{journals/jct/AlonPPRS05,
title = {Crossing patterns of semi-algebraic sets.},
year = {2005},
journal = {J. Comb. Theory, Ser. A},
author = {{Noga Alon} and {János Pach} and {Rom Pinchasi} and {Rados Radoicic} and {Micha Sharir}}
}
@article{journals/siamdm/AlonA05,
title = {Learning a Hidden Subgraph.},
year = {2005},
journal = {SIAM J. Discret. Math.},
author = {{Noga Alon} and {Vera Asodi}}
}
@article{journals/tit/AlonKKLR05,
title = {Testing Reed-Muller codes.},
year = {2005},
journal = {IEEE Trans. Inf. Theory},
author = {{Noga Alon} and {Tali Kaufman} and {Michael Krivelevich} and {Simon Litsyn} and {Dana Ron}}
}
@article{journals/toc/AlonS05,
title = {Linear Equations, Arithmetic Progressions and Hypergraph Property Testing.},
year = {2005},
journal = {Theory Comput.},
author = {{Noga Alon} and {Asaf Shapira}}
}
@inproceedings{conf/icalp/AlonSS06,
title = {Additive Approximation for Edge-Deletion Problems (Abstract).},
year = {2006},
booktitle = {ICALP (1)},
author = {{Noga Alon} and {Asaf Shapira} and {Benny Sudakov}},
publisher = {Springer},
booktitle = {Automata, Languages and Programming, 33rd International Colloquium, ICALP 2006, Venice, Italy, July 10-14, 2006, Proceedings, Part I}
}
@article{journals/combinatorica/AlonS06,
title = {On An Extremal Hypergraph Problem Of Brown, Erdös And Sós.},
year = {2006},
journal = {Comb.},
author = {{Noga Alon} and {Asaf Shapira}}
}
@article{journals/combinatorica/AlonY06,
title = {The Number Of Orientations Having No Fixed Tournament.},
year = {2006},
journal = {Comb.},
author = {{Noga Alon} and {Raphael Yuster}}
}
@article{journals/combinatorics/AlonS06,
title = {H-Free Graphs of Large Minimum Degree.},
year = {2006},
journal = {Electron. J. Comb.},
author = {{Noga Alon} and {Benny Sudakov}}
}
@article{journals/cpc/Alon06,
title = {Feasible Schedules for Rotating Transmissions.},
year = {2006},
journal = {Comb. Probab. Comput.},
author = {{Noga Alon}}
}
@article{journals/cpc/Alon06a,
title = {Splitting digraphs.},
year = {2006},
journal = {Comb. Probab. Comput.},
author = {{Noga Alon}}
}
@article{journals/cpc/AlonKMMR06,
title = {Measures of Pseudorandomness for Finite Sequences: Minimal Values.},
year = {2006},
journal = {Comb. Probab. Comput.},
author = {{Noga Alon} and {Yoshiharu Kohayakawa} and {Christian Mauduit} and {Carlos Gustavo T. de A. Moreira} and {Vojtech Rödl}}
}
@article{journals/cpc/AlonS06,
title = {A Characterization of Easily Testable Induced Subgraphs.},
year = {2006},
journal = {Comb. Probab. Comput.},
author = {{Noga Alon} and {Asaf Shapira}}
}
@article{journals/ejc/AlonA06,
title = {Tracing a single user.},
year = {2006},
journal = {Eur. J. Comb.},
author = {{Noga Alon} and {Vera Asodi}}
}
@article{journals/jcb/AlonACKR06,
title = {Multi-Node Graphs: A Framework for Multiplexed Biological Assays.},
year = {2006},
journal = {J. Comput. Biol.},
author = {{Noga Alon} and {Vera Asodi} and {Charles Cantor} and {Simon Kasif} and {John Rachlin}}
}
@article{journals/jct/AlonBKKW06,
title = {Dominating sets in k-majority tournaments.},
year = {2006},
journal = {J. Comb. Theory, Ser. B},
author = {{Noga Alon} and {Graham R. Brightwell} and {Hal A. Kierstead} and {Alexandr V. Kostochka} and {Peter Winkler 001}}
}
@article{journals/jgt/AlonRSV06,
title = {A Ramsey-type result for the hypercube.},
year = {2006},
journal = {J. Graph Theory},
author = {{Noga Alon} and {Rados Radoicic} and {Benny Sudakov} and {Jan Vondrák}}
}
@article{journals/rsa/AlonB06,
title = {Regular graphs whose subgraphs tend to be acyclic.},
year = {2006},
journal = {Random Struct. Algorithms},
author = {{Noga Alon} and {Eitan Bachmat}}
}
@article{journals/siamcomp/AlonN06,
title = {Approximating the Cut-Norm via Grothendieck's Inequality.},
year = {2006},
journal = {SIAM J. Comput.},
author = {{Noga Alon} and {Assaf Naor}}
}
@article{journals/siamdm/Alon06,
title = {Ranking Tournaments.},
year = {2006},
journal = {SIAM J. Discret. Math.},
author = {{Noga Alon}}
}
@article{journals/talg/AlonAABN06,
title = {A general approach to online network optimization problems.},
year = {2006},
journal = {ACM Trans. Algorithms},
author = {{Noga Alon} and {Baruch Awerbuch} and {Yossi Azar} and {Niv Buchbinder} and {Joseph Naor}}
}
@article{journals/talg/AlonMS06,
title = {Algorithmic construction of sets for k-restrictions.},
year = {2006},
journal = {ACM Trans. Algorithms},
author = {{Noga Alon} and {Dana Moshkovitz} and {Shmuel Safra}}
}
@article{journals/tit/AlonL06,
title = {The Shannon capacity of a graph and the independence numbers of its powers.},
year = {2006},
journal = {IEEE Trans. Inf. Theory},
author = {{Noga Alon} and {Eyal Lubetzky}}
}
@inproceedings{conf/esa/AlonY07,
title = {Fast Algorithms for Maximum Subset Matching and All-Pairs Shortest Paths in Graphs with a (Not So) Small Vertex Cover.},
year = {2007},
booktitle = {ESA},
author = {{Noga Alon} and {Raphael Yuster}},
publisher = {Springer},
booktitle = {Algorithms - ESA 2007, 15th Annual European Symposium, Eilat, Israel, October 8-10, 2007, Proceedings}
}
@inproceedings{conf/focs/AlonC07,
title = {Finding Disjoint Paths in Expanders Deterministically and Online.},
year = {2007},
booktitle = {FOCS},
author = {{Noga Alon} and {Michael R. Capalbo}},
publisher = {IEEE Computer Society},
booktitle = {48th Annual IEEE Symposium on Foundations of Computer Science (FOCS 2007), October 20-23, 2007, Providence, RI, USA, Proceedings}
}
@inproceedings{conf/fsttcs/AlonFGKS07,
title = {Better Algorithms and Bounds for Directed Maximum Leaf Problems.},
year = {2007},
booktitle = {FSTTCS},
author = {{Noga Alon} and {Fedor V. Fomin} and {Gregory Z. Gutin} and {Michael Krivelevich} and {Saket Saurabh 001}},
publisher = {Springer},
booktitle = {FSTTCS 2007: Foundations of Software Technology and Theoretical Computer Science, 27th International Conference, New Delhi, India, December 12-14, 2007, Proceedings}
}
@inproceedings{conf/icalp/AlonFGKS07,
title = {Parameterized Algorithms for Directed Maximum Leaf Problems.},
year = {2007},
booktitle = {ICALP},
author = {{Noga Alon} and {Fedor V. Fomin} and {Gregory Z. Gutin} and {Michael Krivelevich} and {Saket Saurabh 001}},
publisher = {Springer},
booktitle = {Automata, Languages and Programming, 34th International Colloquium, ICALP 2007, Wroclaw, Poland, July 9-13, 2007, Proceedings}
}
@inproceedings{conf/stoc/AgarwalAC07,
title = {Improved approximation for directed cut problems.},
year = {2007},
booktitle = {STOC},
author = {{Amit Agarwal} and {Noga Alon} and {Moses Charikar}},
publisher = {ACM},
booktitle = {Proceedings of the 39th Annual ACM Symposium on Theory of Computing, San Diego, California, USA, June 11-13, 2007}
}
@inproceedings{conf/stoc/AlonAKMRX07,
title = {Testing k-wise and almost k-wise independence.},
year = {2007},
booktitle = {STOC},
author = {{Noga Alon} and {Alexandr Andoni} and {Tali Kaufman} and {Kevin Matulef} and {Ronitt Rubinfeld} and {Ning Xie 002}},
publisher = {ACM},
booktitle = {Proceedings of the 39th Annual ACM Symposium on Theory of Computing, San Diego, California, USA, June 11-13, 2007}
}
@article{journals/combinatorica/AlonKS07,
title = {Embedding nearly-spanning bounded degree trees.},
year = {2007},
journal = {Comb.},
author = {{Noga Alon} and {Michael Krivelevich} and {Benny Sudakov}}
}
@article{journals/combinatorica/AlonL07,
title = {Codes And Xor Graph Products.},
year = {2007},
journal = {Comb.},
author = {{Noga Alon} and {Eyal Lubetzky}}
}
@article{journals/combinatorica/AlonL07a,
title = {Privileged users in zero-error transmission over a noisy channel.},
year = {2007},
journal = {Comb.},
author = {{Noga Alon} and {Eyal Lubetzky}}
}
@article{journals/cpc/AlonA07,
title = {Edge Colouring with Delays.},
year = {2007},
journal = {Comb. Probab. Comput.},
author = {{Noga Alon} and {Vera Asodi}}
}
@article{journals/ejc/AlonNSTV07,
title = {Partitioning multi-dimensional sets in a small number of "uniform" parts.},
year = {2007},
journal = {Eur. J. Comb.},
author = {{Noga Alon} and {Ilan Newman} and {Alexander Shen} and {Gábor Tardos} and {Nikolai K. Vereshchagin}}
}
@article{journals/iandc/AilonA07,
title = {Hardness of fully dense problems.},
year = {2007},
journal = {Inf. Comput.},
author = {{Nir Ailon} and {Noga Alon}}
}
@article{journals/iandc/AlonKKMS07,
title = {Addendum to "Scalable secure storage when half the system is faulty" [Inform. Comput 174 (2)(2002) 203-213].},
year = {2007},
journal = {Inf. Comput.},
author = {{Noga Alon} and {Haim Kaplan} and {Michael Krivelevich} and {Dahlia Malkhi} and {Julien P. Stern}}
}
@article{journals/jgt/AlonBGLS07,
title = {Maximum directed cuts in acyclic digraphs.},
year = {2007},
journal = {J. Graph Theory},
author = {{Noga Alon} and {Béla Bollobás} and {András Gyárfás} and {Jenö Lehel} and {Alex D. Scott}}
}
@article{journals/jgt/AlonL07,
title = {Independent sets in tensor graph powers.},
year = {2007},
journal = {J. Graph Theory},
author = {{Noga Alon} and {Eyal Lubetzky}}
}
@article{journals/jgt/AlonS07,
title = {On graphs with subgraphs having large independence numbers.},
year = {2007},
journal = {J. Graph Theory},
author = {{Noga Alon} and {Benny Sudakov}}
}
@article{journals/rsa/AlonC07,
title = {Sparse universal graphs for bounded-degree graphs.},
year = {2007},
journal = {Random Struct. Algorithms},
author = {{Noga Alon} and {Michael R. Capalbo}}
}
@article{journals/rsa/AlonIN07,
title = {On (epsilon, k)-min-wise independent permutations.},
year = {2007},
journal = {Random Struct. Algorithms},
author = {{Noga Alon} and {Toshiya Itoh} and {Tatsuya Nagatani}}
}
@article{journals/siamcomp/AlonFN07,
title = {Efficient Testing of Bipartite Graphs for Forbidden Induced Subgraphs.},
year = {2007},
journal = {SIAM J. Comput.},
author = {{Noga Alon} and {Eldar Fischer} and {Ilan Newman}}
}
@article{journals/siamdm/AlonKS07,
title = {Tur[a-acute]n's Theorem in the Hypercube.},
year = {2007},
journal = {SIAM J. Discret. Math.},
author = {{Noga Alon} and {Anja Krech} and {Tibor Szabó}}
}
@article{journals/siamdm/AlonL07,
title = {Graph Powers, Delsarte, Hoffman, Ramsey, and Shannon.},
year = {2007},
journal = {SIAM J. Discret. Math.},
author = {{Noga Alon} and {Eyal Lubetzky}}
}
@article{journals/talg/AlonGKS07,
title = {Guessing secrets efficiently via list decoding.},
year = {2007},
journal = {ACM Trans. Algorithms},
author = {{Noga Alon} and {Venkatesan Guruswami} and {Tali Kaufman} and {Madhu Sudan 001}}
}
@article{journals/tcs/AlonLW07,
title = {Approximating the maximum clique minor and some subgraph homeomorphism problems.},
year = {2007},
journal = {Theor. Comput. Sci.},
author = {{Noga Alon} and {Andrzej Lingas} and {Martin Wahlen}}
}
@article{journals/tit/AlonA07,
title = {Tracing Many Users With Almost No Rate Penalty.},
year = {2007},
journal = {IEEE Trans. Inf. Theory},
author = {{Noga Alon} and {Vera Asodi}}
}
@book{books/daglib/0021015,
title = {The Probabilistic Method, Third Edition.},
year = {2008},
isbn = {978-0-470-17020-5},
publisher = {Wiley},
series = {Wiley-Interscience series in discrete mathematics and optimization},
author = {{Noga Alon} and {Joel H. Spencer}}
}
@inproceedings{conf/approx/AlonBK08,
title = {Small Sample Spaces Cannot Fool Low Degree Polynomials.},
year = {2008},
booktitle = {APPROX-RANDOM},
author = {{Noga Alon} and {Ido Ben-Eliezer} and {Michael Krivelevich}},
publisher = {Springer},
booktitle = {Approximation, Randomization and Combinatorial Optimization. Algorithms and Techniques, 11th International Workshop, APPROX 2008, and 12th International Workshop, RANDOM 2008, Boston, MA, USA, August 25-27, 2008. Proceedings}
}
@inproceedings{conf/compgeom/AlonHNS08,
title = {The complexity of the outer face in arrangements of random segments.},
year = {2008},
booktitle = {SCG},
author = {{Noga Alon} and {Dan Halperin} and {Oren Nechushtan} and {Micha Sharir}},
publisher = {ACM},
booktitle = {Proceedings of the 24th ACM Symposium on Computational Geometry, College Park, MD, USA, June 9-11, 2008}
}
@inproceedings{conf/focs/AlonLSWH08,
title = {Broadcasting with Side Information.},
year = {2008},
booktitle = {FOCS},
author = {{Noga Alon} and {Eyal Lubetzky} and {Uri Stav} and {Amit Weinstein} and {Avinatan Hassidim}},
publisher = {IEEE Computer Society},
booktitle = {49th Annual IEEE Symposium on Foundations of Computer Science, FOCS 2008, October 25-28, 2008, Philadelphia, PA, USA}
}
@inproceedings{conf/focs/AlonN08,
title = {k-Wise Independent Random Graphs.},
year = {2008},
booktitle = {FOCS},
author = {{Noga Alon} and {Asaf Nussboim}},
publisher = {IEEE Computer Society},
booktitle = {49th Annual IEEE Symposium on Foundations of Computer Science, FOCS 2008, October 25-28, 2008, Philadelphia, PA, USA}
}
@inproceedings{conf/ismb/AlonDHHS08,
title = {Biomolecular network motif counting and discovery by color coding.},
year = {2008},
booktitle = {ISMB},
author = {{Noga Alon} and {Phuong Dao} and {Iman Hajirasouliha} and {Fereydoun Hormozdiari} and {Süleyman Cenk Sahinalp}},
booktitle = {Proceedings 16th International Conference on Intelligent Systems for Molecular Biology (ISMB), Toronto, Canada, July 19-23, 2008}
}
@inproceedings{conf/soda/AlonC08,
title = {Optimal universal graphs with deterministic embedding.},
year = {2008},
booktitle = {SODA},
author = {{Noga Alon} and {Michael R. Capalbo}},
publisher = {SIAM},
booktitle = {Proceedings of the Nineteenth Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2008, San Francisco, California, USA, January 20-22, 2008}
}
@article{journals/combinatorica/AlonS08,
title = {A separation theorem in property testing.},
year = {2008},
journal = {Comb.},
author = {{Noga Alon} and {Asaf Shapira}}
}
@article{journals/combinatorics/AlonF08,
title = {The Maximum Number of Perfect Matchings in Graphs with a Given Degree Sequence.},
year = {2008},
journal = {Electron. J. Comb.},
author = {{Noga Alon} and {Shmuel Friedland}}
}
@article{journals/cpc/AlonSS08,
title = {An Elementary Construction of Constant-Degree Expanders.},
year = {2008},
journal = {Comb. Probab. Comput.},
author = {{Noga Alon} and {Oded Schwartz} and {Asaf Shapira}}
}
@article{journals/disopt/AlonB08,
title = {The Grothendieck constant of random and pseudo-random graphs.},
year = {2008},
journal = {Discret. Optim.},
author = {{Noga Alon} and {Eli Berger}}
}
@article{journals/dm/Alon08,
title = {Problems and results in extremal combinatorics - II.},
year = {2008},
journal = {Discret. Math.},
author = {{Noga Alon}}
}
@article{journals/dm/AlonG08,
title = {Breaking the rhythm on graphs.},
year = {2008},
journal = {Discret. Math.},
author = {{Noga Alon} and {Jaroslaw Grytczuk}}
}
@article{journals/dm/AlonPP08,
title = {An isoperimetric inequality in the universal cover of the punctured plane.},
year = {2008},
journal = {Discret. Math.},
author = {{Noga Alon} and {Adi Pinchasi} and {Rom Pinchasi}}
}
@article{journals/eccc/AlonG08,
title = {Kernels for the Dominating Set Problem on Graphs with an Excluded Minor.},
year = {2008},
journal = {Electron. Colloquium Comput. Complex.},
author = {{Noga Alon} and {Shai Gutner}}
}
@article{journals/eccc/AlonPY08,
title = {Deterministic Approximation Algorithms for the Nearest Codeword Problem.},
year = {2008},
journal = {Electron. Colloquium Comput. Complex.},
author = {{Noga Alon} and {Rina Panigrahy} and {Sergey Yekhanin}}
}
@article{journals/ijcga/AlonS08,
title = {Conflict-Free colorings of Shallow Discs.},
year = {2008},
journal = {Int. J. Comput. Geom. Appl.},
author = {{Noga Alon} and {Shakhar Smorodinsky}}
}
@article{journals/jacm/AlonKNSS08,
title = {Weak ε-nets and interval chains.},
year = {2008},
journal = {J. ACM},
author = {{Noga Alon} and {Haim Kaplan} and {Gabriel Nivasch} and {Micha Sharir} and {Shakhar Smorodinsky}}
}
@article{journals/jct/AlonS08,
title = {The maximum edit distance from hereditary graph properties.},
year = {2008},
journal = {J. Comb. Theory, Ser. B},
author = {{Noga Alon} and {Uri Stav}}
}
@article{journals/rsa/AlonS08,
title = {What is the furthest graph from a hereditary property?},
year = {2008},
journal = {Random Struct. Algorithms},
author = {{Noga Alon} and {Uri Stav}}
}
@article{journals/siamcomp/AlonS08,
title = {A Characterization of the (Natural) Graph Properties Testable with One-Sided Error.},
year = {2008},
journal = {SIAM J. Comput.},
author = {{Noga Alon} and {Asaf Shapira}}
}
@article{journals/siamcomp/AlonS08a,
title = {Every Monotone Graph Property Is Testable.},
year = {2008},
journal = {SIAM J. Comput.},
author = {{Noga Alon} and {Asaf Shapira}}
}
@article{journals/siamdm/AlonKKR08,
title = {Testing Triangle-Freeness in General Graphs.},
year = {2008},
journal = {SIAM J. Discret. Math.},
author = {{Noga Alon} and {Tali Kaufman} and {Michael Krivelevich} and {Dana Ron}}
}
@article{journals/siamdm/AlonKS08,
title = {Large Nearly Regular Induced Subgraphs.},
year = {2008},
journal = {SIAM J. Discret. Math.},
author = {{Noga Alon} and {Michael Krivelevich} and {Benny Sudakov}}
}
@article{journals/siamdm/AlonPW08,
title = {Cleaning Regular Graphs with Brushes.},
year = {2008},
journal = {SIAM J. Discret. Math.},
author = {{Noga Alon} and {Pawel Pralat} and {Nicholas C. Wormald}}
}
@article{journals/talg/AlonBDFHS08,
title = {Ordinal embeddings of minimum relaxation: General properties, trees, and ultrametrics.},
year = {2008},
journal = {ACM Trans. Algorithms},
author = {{Noga Alon} and {Mihai Badoiu} and {Erik D. Demaine} and {Martin Farach-Colton} and {Mohammad Taghi Hajiaghayi} and {Anastasios Sidiropoulos}}
}
@incollection{reference/algo/AlonYZ08,
title = {Color Coding.},
year = {2008},
booktitle = {Encyclopedia of Algorithms},
author = {{Noga Alon} and {Raphael Yuster} and {Uri Zwick}},
publisher = {Springer},
booktitle = {Encyclopedia of Algorithms - 2008 Edition}
}
@inproceedings{conf/focs/AlonLG09,
title = {Choice-Memory Tradeoff in Allocations.},
year = {2009},
booktitle = {FOCS},
author = {{Noga Alon} and {Eyal Lubetzky} and {Ori Gurel-Gurevich}},
publisher = {IEEE Computer Society},
booktitle = {50th Annual IEEE Symposium on Foundations of Computer Science, FOCS 2009, October 25-27, 2009, Atlanta, Georgia, USA}
}
@inproceedings{conf/icalp/AlonLS09,
title = {Fast FAST.},
year = {2009},
booktitle = {ICALP (1)},
author = {{Noga Alon} and {Daniel Lokshtanov} and {Saket Saurabh 001}},
publisher = {Springer},
booktitle = {Automata, Languages and Programming, 36th International Colloquium, ICALP 2009, Rhodes, Greece, July 5-12, 2009, Proceedings, Part I}
}
@inproceedings{conf/soda/AlonF09,
title = {On the power of two, three and four probes.},
year = {2009},
booktitle = {SODA},
author = {{Noga Alon} and {Uriel Feige}},
publisher = {SIAM},
booktitle = {Proceedings of the Twentieth Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2009, New York, NY, USA, January 4-6, 2009}
}
@article{journals/algorithmica/AlonG09,
title = {Linear Time Algorithms for Finding a Dominating Set of Fixed Size in Degenerated Graphs.},
year = {2009},
journal = {Algorithmica},
author = {{Noga Alon} and {Shai Gutner}}
}
@article{journals/combinatorica/AlonL09,
title = {Uniformly cross intersecting families.},
year = {2009},
journal = {Comb.},
author = {{Noga Alon} and {Eyal Lubetzky}}
}
@article{journals/corr/abs-0907-2049,
title = {Strategyproof Approximation Mechanisms for Location on Networks},
year = {2009},
journal = {CoRR},
author = {{Noga Alon} and {Michal Feldman} and {Ariel D. Procaccia} and {Moshe Tennenholtz}}
}
@article{journals/cpc/Alon09,
title = {Perturbed Identity Matrices Have High Rank: Proof and Applications.},
year = {2009},
journal = {Comb. Probab. Comput.},
author = {{Noga Alon}}
}
@article{journals/cpc/Alon09a,
title = {Economical Elimination of Cycles in the Torus.},
year = {2009},
journal = {Comb. Probab. Comput.},
author = {{Noga Alon}}
}
@article{journals/cpc/AlonB09,
title = {Introduction.},
year = {2009},
journal = {Comb. Probab. Comput.},
author = {{Noga Alon} and {Béla Bollobás}}
}
@article{journals/cpc/AlonBKS09,
title = {Sizes of Induced Subgraphs of Ramsey Graphs.},
year = {2009},
journal = {Comb. Probab. Comput.},
author = {{Noga Alon} and {József Balogh} and {Alexandr V. Kostochka} and {Wojciech Samotij}}
}
@article{journals/dcg/AlonBBBCSSZ09,
title = {Polychromatic Colorings of Plane Graphs.},
year = {2009},
journal = {Discret. Comput. Geom.},
author = {{Noga Alon} and {Robert Berke} and {Kevin Buchin} and {Maike Buchin} and {Péter Csorba} and {Saswata Shannigrahi} and {Bettina Speckmann} and {Philipp Zumstein}}
}
@article{journals/eccc/AlonG09,
title = {Balanced Hashing, Color Coding and Approximate Counting.},
year = {2009},
journal = {Electron. Colloquium Comput. Complex.},
author = {{Noga Alon} and {Shai Gutner}}
}
@article{journals/endm/HefetzAK09,
title = {Playing to retain the advantage.},
year = {2009},
journal = {Electron. Notes Discret. Math.},
author = {{Dan Hefetz} and {Noga Alon} and {Michael Krivelevich}}
}
@article{journals/jgt/AlonS09,
title = {Stability-type results for hereditary properties.},
year = {2009},
journal = {J. Graph Theory},
author = {{Noga Alon} and {Uri Stav}}
}
@article{journals/mst/AlonAAP09,
title = {Tell Me Who I Am: An Interactive Recommendation System.},
year = {2009},
journal = {Theory Comput. Syst.},
author = {{Noga Alon} and {Baruch Awerbuch} and {Yossi Azar} and {Boaz Patt-Shamir}}
}
@article{journals/rsa/AlonK09,
title = {Induced subgraphs with distinct sizes.},
year = {2009},
journal = {Random Struct. Algorithms},
author = {{Noga Alon} and {Alexandr V. Kostochka}}
}
@article{journals/siamcomp/AlonAABN09,
title = {The Online Set Cover Problem.},
year = {2009},
journal = {SIAM J. Comput.},
author = {{Noga Alon} and {Baruch Awerbuch} and {Yossi Azar} and {Niv Buchbinder} and {Joseph Naor}}
}
@article{journals/siamcomp/AlonFNS09,
title = {A Combinatorial Characterization of the Testable Graph Properties: It's All About Regularity.},
year = {2009},
journal = {SIAM J. Comput.},
author = {{Noga Alon} and {Eldar Fischer} and {Ilan Newman} and {Asaf Shapira}}
}
@article{journals/siamdm/AlonFGKS09,
title = {Spanning Directed Trees with Many Leaves.},
year = {2009},
journal = {SIAM J. Discret. Math.},
author = {{Noga Alon} and {Fedor V. Fomin} and {Gregory Z. Gutin} and {Michael Krivelevich} and {Saket Saurabh 001}}
}
@article{journals/siamdm/AlonSS09,
title = {Can a Graph Have Distinct Regular Partitions?},
year = {2009},
journal = {SIAM J. Discret. Math.},
author = {{Noga Alon} and {Asaf Shapira} and {Uri Stav}}
}
@article{journals/talg/AlonAG09,
title = {Admission control to minimize rejections and online set cover with repetitions.},
year = {2009},
journal = {ACM Trans. Algorithms},
author = {{Noga Alon} and {Yossi Azar} and {Shai Gutner}}
}
@article{journals/tcs/AlonS09,
title = {Hardness of edge-modification problems.},
year = {2009},
journal = {Theor. Comput. Sci.},
author = {{Noga Alon} and {Uri Stav}}
}
@article{journals/tit/AlonH09,
title = {Optimal Monotone Encodings.},
year = {2009},
journal = {IEEE Trans. Inf. Theory},
author = {{Noga Alon} and {Rani Hod}}
}
@inproceedings{conf/approx/AlonB10,
title = {Testing Boolean Function Isomorphism.},
year = {2010},
booktitle = {APPROX-RANDOM},
author = {{Noga Alon} and {Eric Blais}},
publisher = {Springer},
booktitle = {Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques, 13th International Workshop, APPROX 2010, and 14th International Workshop, RANDOM 2010, Barcelona, Spain, September 1-3, 2010. Proceedings}
}
@inproceedings{conf/colt/Alon10,
title = {Voting Paradoxes.},
year = {2010},
booktitle = {COLT},
author = {{Noga Alon}},
publisher = {Omnipress},
booktitle = {COLT 2010 - The 23rd Conference on Learning Theory, Haifa, Israel, June 27-29, 2010}
}
@inproceedings{conf/focs/AlonY10,
title = {Solving Linear Systems through Nested Dissection.},
year = {2010},
booktitle = {FOCS},
author = {{Noga Alon} and {Raphael Yuster}},
publisher = {IEEE Computer Society},
booktitle = {51th Annual IEEE Symposium on Foundations of Computer Science, FOCS 2010, October 23-26, 2010, Las Vegas, Nevada, USA}
}
@incollection{conf/propertytesting/Alon10,
title = {On Constant Time Approximation of Parameters of Bounded Degree Graphs.},
year = {2010},
booktitle = {Property Testing},
author = {{Noga Alon}},
publisher = {Springer},
booktitle = {Property Testing - Current Research and Surveys}
}
@inproceedings{conf/soda/AlonGKSY10,
title = {Solving MAX-r-SAT Above a Tight Lower Bound.},
year = {2010},
booktitle = {SODA},
author = {{Noga Alon} and {Gregory Z. Gutin} and {Eun Jung Kim 002} and {Stefan Szeider} and {Anders Yeo}},
publisher = {SIAM},
booktitle = {Proceedings of the Twenty-First Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2010, Austin, Texas, USA, January 17-19, 2010}
}
@inproceedings{conf/wdag/AlonADDGT10,
title = {Brief Announcement: Sharing Memory in a Self-stabilizing Manner.},
year = {2010},
booktitle = {DISC},
author = {{Noga Alon} and {Hagit Attiya} and {Shlomi Dolev} and {Swan Dubois} and {Maria Gradinariu} and {Sébastien Tixeuil}},
publisher = {Springer},
booktitle = {Distributed Computing, 24th International Symposium, DISC 2010, Cambridge, MA, USA, September 13-15, 2010. Proceedings}
}
@article{journals/combinatorics/AlonCCG10,
title = {Another Abstraction of the Erdös-Szekeres Happy End Theorem.},
year = {2010},
journal = {Electron. J. Comb.},
author = {{Noga Alon} and {Ehsan Chiniforooshan} and {Vasek Chvátal} and {François Genest}}
}
@article{journals/corr/abs-1007-1802,
title = {Practically Stabilizing Atomic Memory},
year = {2010},
journal = {CoRR},
author = {{Noga Alon} and {Hagit Attiya} and {Shlomi Dolev} and {Swan Dubois} and {Maria Gradinariu} and {Sébastien Tixeuil}}
}
@article{journals/dm/AlonFPT10,
title = {Walking in circles.},
year = {2010},
journal = {Discret. Math.},
author = {{Noga Alon} and {Michal Feldman} and {Ariel D. Procaccia} and {Moshe Tennenholtz}}
}
@article{journals/ipl/AlonFPT10,
title = {A note on competitive diffusion through social networks.},
year = {2010},
journal = {Inf. Process. Lett.},
author = {{Noga Alon} and {Michal Feldman} and {Ariel D. Procaccia} and {Moshe Tennenholtz}}
}
@article{journals/jgt/AlonBK10,
title = {A note on regular Ramsey graphs.},
year = {2010},
journal = {J. Graph Theory},
author = {{Noga Alon} and {Sonny Ben-Shimon} and {Michael Krivelevich}}
}
@article{journals/mor/AlonFPT10,
title = {Strategyproof Approximation of the Minimax on Networks.},
year = {2010},
journal = {Math. Oper. Res.},
author = {{Noga Alon} and {Michal Feldman} and {Ariel D. Procaccia} and {Moshe Tennenholtz}}
}
@article{journals/scw/AlonE10,
title = {The inverse Banzhaf problem.},
year = {2010},
journal = {Soc. Choice Welf.},
author = {{Noga Alon} and {Paul H. Edelman}}
}
@article{journals/siamcomp/AlonCHKRS10,
title = {Quasi-Randomness and Algorithmic Regularity for Graphs with General Degree Distributions.},
year = {2010},
journal = {SIAM J. Comput.},
author = {{Noga Alon} and {Amin Coja-Oghlan} and {Hiêp Hàn} and {Mihyun Kang} and {Vojtech Rödl} and {Mathias Schacht}}
}
@article{journals/siamdm/AlonF10,
title = {The Brunn--Minkowski Inequality and Nontrivial Cycles in the Discrete Torus.},
year = {2010},
journal = {SIAM J. Discret. Math.},
author = {{Noga Alon} and {Ohad N. Feldheim}}
}
@article{journals/talg/AlonG10,
title = {Balanced families of perfect hash functions and their applications.},
year = {2010},
journal = {ACM Trans. Algorithms},
author = {{Noga Alon} and {Shai Gutner}}
}
@article{journals/tcbb/AlonCPR10,
title = {Approximate Maximum Parsimony and Ancestral Maximum Likelihood.},
year = {2010},
journal = {IEEE ACM Trans. Comput. Biol. Bioinform.},
author = {{Noga Alon} and {Benny Chor} and {Fabio Pardi} and {Anat Rapoport}}
}
@article{journals/tit/AlonLS10,
title = {Typical peak sidelobe level of binary sequences.},
year = {2010},
journal = {IEEE Trans. Inf. Theory},
author = {{Noga Alon} and {Simon Litsyn} and {Alexander Shpunt}}
}
@inproceedings{conf/cccg/Alon11,
title = {List coloring and Euclidean Ramsey Theory.},
year = {2011},
booktitle = {CCCG},
author = {{Noga Alon}},
booktitle = {Proceedings of the 23rd Annual Canadian Conference on Computational Geometry, Toronto, Ontario, Canada, August 10-12, 2011}
}
@inproceedings{conf/innovations/AlonEFT11,
title = {Economical Graph Discovery.},
year = {2011},
booktitle = {ICS},
author = {{Noga Alon} and {Yuval Emek} and {Michal Feldman} and {Moshe Tennenholtz}},
publisher = {Tsinghua University Press},
booktitle = {Innovations in Computer Science - ICS 2011, Tsinghua University, Beijing, China, January 7-9, 2011. Proceedings}
}
@inproceedings{conf/sss/AlonADDPT11,
title = {Pragmatic Self-stabilization of Atomic Memory in Message-Passing Systems.},
year = {2011},
booktitle = {SSS},
author = {{Noga Alon} and {Hagit Attiya} and {Shlomi Dolev} and {Swan Dubois} and {Maria Potop-Butucaru} and {Sébastien Tixeuil}},
publisher = {Springer},
booktitle = {Stabilization, Safety, and Security of Distributed Systems - 13th International Symposium, SSS 2011, Grenoble, France, October 10-12, 2011. Proceedings}
}
@inproceedings{conf/tark/AlonFPT11,
title = {Sum of us: strategyproof selection from the selectors.},
year = {2011},
booktitle = {TARK},
author = {{Noga Alon} and {Felix A. Fischer} and {Ariel D. Procaccia} and {Moshe Tennenholtz}},
publisher = {ACM},
booktitle = {Proceedings of the 13th Conference on Theoretical Aspects of Rationality and Knowledge (TARK-2011), Groningen, The Netherlands, July 12-14, 2011}
}
@article{journals/algorithmica/AlonGKSY11,
title = {Solving MAX-r-SAT Above a Tight Lower Bound.},
year = {2011},
journal = {Algorithmica},
author = {{Noga Alon} and {Gregory Z. Gutin} and {Eun Jung Kim 002} and {Stefan Szeider} and {Anders Yeo}}
}
@article{journals/combinatorics/AlonHK11,
title = {The Number of f-Matchings in Almost Every Tree is a Zero Residue.},
year = {2011},
journal = {Electron. J. Comb.},
author = {{Noga Alon} and {Simi Haber} and {Michael Krivelevich}}
}
@article{journals/combinatorics/AlonM11,
title = {On a Generalization of Meyniel's Conjecture on the Cops and Robbers Game.},
year = {2011},
journal = {Electron. J. Comb.},
author = {{Noga Alon} and {Abbas Mehrabian}}
}
@article{journals/corr/abs-1106-2126,
title = {MIS on the fly},
year = {2011},
journal = {CoRR},
author = {{Yehuda Afek} and {Noga Alon} and {Ziv Bar-Joseph}}
}
@article{journals/corr/abs-1109-3639,
title = {Local Correction of Boolean Functions},
year = {2011},
journal = {CoRR},
author = {{Noga Alon} and {Amit Weinstein}}
}
@article{journals/corr/abs-1110-2828,
title = {Testing perfection is hard},
year = {2011},
journal = {CoRR},
author = {{Noga Alon} and {Jacob Fox}}
}
@article{journals/cpc/AlonAKKLT11,
title = {Many Random Walks Are Faster Than One.},
year = {2011},
journal = {Comb. Probab. Comput.},
author = {{Noga Alon} and {Chen Avin} and {Michal Koucký 001} and {Gady Kozma} and {Zvi Lotker} and {Mark R. Tuttle}}
}
@article{journals/cpc/AlonP11,
title = {Modular Orientations of Random and Quasi-Random Regular Graphs.},
year = {2011},
journal = {Comb. Probab. Comput.},
author = {{Noga Alon} and {Pawel Pralat}}
}
@article{journals/jct/AlonBBM11,
title = {The structure of almost all graphs in a hereditary property.},
year = {2011},
journal = {J. Comb. Theory, Ser. B},
author = {{Noga Alon} and {József Balogh} and {Béla Bollobás} and {Robert Morris 001}}
}
@article{journals/jgt/AlonHKPY11,
title = {On graphs and algebraic graphs that do not contain cycles of length 4.},
year = {2011},
journal = {J. Graph Theory},
author = {{Noga Alon} and {H. Tracy Hall} and {Christian Knauer} and {Rom Pinchasi} and {Raphael Yuster}}
}
@article{journals/rsa/AlonK11,
title = {Hypergraph list coloring and Euclidean Ramsey theory.},
year = {2011},
journal = {Random Struct. Algorithms},
author = {{Noga Alon} and {Alexandr V. Kostochka}}
}
@article{journals/siamdm/AlonM11,
title = {Sparse Balanced Partitions and the Complexity of Subgraph Problems.},
year = {2011},
journal = {SIAM J. Discret. Math.},
author = {{Noga Alon} and {Dániel Marx}}
}
@inproceedings{conf/sigecom/AlonBKLT12,
title = {Sequential voting with externalities: herding in social networks.},
year = {2012},
booktitle = {EC},
author = {{Noga Alon} and {Moshe Babaioff} and {Ron Karidi} and {Ron Lavi} and {Moshe Tennenholtz}},
publisher = {ACM},
booktitle = {Proceedings of the 13th ACM Conference on Electronic Commerce, EC 2012, Valencia, Spain, June 4-8, 2012}
}
@inproceedings{conf/soda/AlonRVX12,
title = {Space-efficient local computation algorithms.},
year = {2012},
booktitle = {SODA},
author = {{Noga Alon} and {Ronitt Rubinfeld} and {Shai Vardi} and {Ning Xie 002}},
publisher = {SIAM},
booktitle = {Proceedings of the Twenty-Third Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2012, Kyoto, Japan, January 17-19, 2012}
}
@inproceedings{conf/stoc/AlonMS12,
title = {Nearly complete graphs decomposable into large induced matchings and their applications.},
year = {2012},
booktitle = {STOC},
author = {{Noga Alon} and {Ankur Moitra} and {Benny Sudakov}},
publisher = {ACM},
booktitle = {Proceedings of the 44th Symposium on Theory of Computing Conference, STOC 2012, New York, NY, USA, May 19 - 22, 2012}
}
@inproceedings{conf/www/AlonGT12,
title = {Optimizing budget allocation among channels and influencers.},
year = {2012},
booktitle = {WWW},
author = {{Noga Alon} and {Iftah Gamzu} and {Moshe Tennenholtz}},
publisher = {ACM},
booktitle = {Proceedings of the 21st World Wide Web Conference 2012, WWW 2012, Lyon, France, April 16-20, 2012}
}
@article{journals/dcc/AlonMMV12,
title = {The de Bruijn-Erdős theorem for hypergraphs.},
year = {2012},
journal = {Des. Codes Cryptogr.},
author = {{Noga Alon} and {Keith E. Mellinger} and {Dhruv Mubayi} and {Jacques Verstraëte}}
}
@article{journals/dcg/Alon12,
title = {A Non-linear Lower Bound for Planar Epsilon-nets.},
year = {2012},
journal = {Discret. Comput. Geom.},
author = {{Noga Alon}}
}
@article{journals/dm/AlonK12,
title = {Dense uniform hypergraphs have high list chromatic number.},
year = {2012},
journal = {Discret. Math.},
author = {{Noga Alon} and {Alexandr V. Kostochka}}
}
@article{journals/eccc/AlonC12,
title = {On Rigid Matrices and Subspace Polynomials.},
year = {2012},
journal = {Electron. Colloquium Comput. Complex.},
author = {{Noga Alon} and {Gil Cohen}}
}
@article{journals/eccc/AlonV12,
title = {The Approximate Rank of a Matrix and its Algorithmic Applications.},
year = {2012},
journal = {Electron. Colloquium Comput. Complex.},
author = {{Noga Alon} and {Santosh S. Vempala}}
}
@article{journals/ipl/AlonW12,
title = {Local correction of juntas.},
year = {2012},
journal = {Inf. Process. Lett.},
author = {{Noga Alon} and {Amit Weinstein}}
}
@article{journals/jct/AlonFHRRS12,
title = {Large matchings in uniform hypergraphs and the conjectures of Erdős and Samuels.},
year = {2012},
journal = {J. Comb. Theory, Ser. A},
author = {{Noga Alon} and {Peter Frankl} and {Hao Huang 005} and {Vojtech Rödl} and {Andrzej Rucinski 001} and {Benny Sudakov}}
}
@article{journals/jct/AlonHS12,
title = {Nonnegative k-sums, fractional covers, and probability of small deviations.},
year = {2012},
journal = {J. Comb. Theory, Ser. B},
author = {{Noga Alon} and {Hao Huang 005} and {Benny Sudakov}}
}
@article{journals/tcs/AlonEFT12,
title = {Bayesian ignorance.},
year = {2012},
journal = {Theor. Comput. Sci.},
author = {{Noga Alon} and {Yuval Emek} and {Michal Feldman} and {Moshe Tennenholtz}}
}
@incollection{books/daglib/p/Alon13,
title = {Neighborly Families of Boxes and Bipartite Coverings.},
year = {2013},
booktitle = {The Mathematics of Paul Erdős II},
author = {{Noga Alon}},
publisher = {Springer},
booktitle = {The Mathematics of Paul Erdős II}
}
@inproceedings{conf/aaai/AlonFMT13,
title = {Bundling Attacks in Judgment Aggregation.},
year = {2013},
booktitle = {AAAI},
author = {{Noga Alon} and {Dvir Falik} and {Reshef Meir} and {Moshe Tennenholtz}},
publisher = {AAAI Press},
booktitle = {Proceedings of the Twenty-Seventh AAAI Conference on Artificial Intelligence, July 14-18, 2013, Bellevue, Washington, USA.}
}
@inproceedings{conf/aaai/AlonMT13,
title = {The Value of Ignorance about the Number of Players.},
year = {2013},
booktitle = {AAAI (Late-Breaking Developments)},
author = {{Noga Alon} and {Reshef Meir} and {Moshe Tennenholtz}},
publisher = {AAAI},
booktitle = {Late-Breaking Developments in the Field of Artificial Intelligence, Bellevue, Washington, USA, July 14-18, 2013}
}
@inproceedings{conf/nips/AlonCGM13,
title = {From Bandits to Experts: A Tale of Domination and Independence.},
year = {2013},
booktitle = {NIPS},
author = {{Noga Alon} and {Nicolò Cesa-Bianchi} and {Claudio Gentile} and {Yishay Mansour}},
booktitle = {Advances in Neural Information Processing Systems 26: 27th Annual Conference on Neural Information Processing Systems 2013. Proceedings of a meeting held December 5-8, 2013, Lake Tahoe, Nevada, United States.}
}
@inproceedings{conf/sigecom/AlonMT13,
title = {Differential pricing with inequity aversion in social networks.},
year = {2013},
booktitle = {EC},
author = {{Noga Alon} and {Yishay Mansour} and {Moshe Tennenholtz}},
publisher = {ACM},
booktitle = {Proceedings of the fourteenth ACM Conference on Electronic Commerce, EC 2013, Philadelphia, PA, USA, June 16-20, 2013}
}
@inproceedings{conf/stoc/AlonLSV13,
title = {The approximate rank of a matrix and its algorithmic applications: approximate rank.},
year = {2013},
booktitle = {STOC},
author = {{Noga Alon} and {Troy Lee} and {Adi Shraibman} and {Santosh S. Vempala}},
publisher = {ACM},
booktitle = {Symposium on Theory of Computing Conference, STOC'13, Palo Alto, CA, USA, June 1-4, 2013}
}
@inproceedings{conf/wine/AlonFGT13,
title = {The Asymmetric Matrix Partition Problem.},
year = {2013},
booktitle = {WINE},
author = {{Noga Alon} and {Michal Feldman} and {Iftah Gamzu} and {Moshe Tennenholtz}},
publisher = {Springer},
booktitle = {Web and Internet Economics - 9th International Conference, WINE 2013, Cambridge, MA, USA, December 11-14, 2013, Proceedings}
}
@article{journals/cc/AlonSU13,
title = {On sunflowers and matrix multiplication.},
year = {2013},
journal = {Comput. Complex.},
author = {{Noga Alon} and {Amir Shpilka} and {Christopher Umans}}
}
@article{journals/dc/AfekABCHK13,
title = {Beeping a maximal independent set.},
year = {2013},
journal = {Distributed Comput.},
author = {{Yehuda Afek} and {Noga Alon} and {Ziv Bar-Joseph} and {Alejandro Cornejo} and {Bernhard Haeupler} and {Fabian Kuhn}}
}
@article{journals/ejc/Alon13,
title = {The chromatic number of random Cayley graphs.},
year = {2013},
journal = {Eur. J. Comb.},
author = {{Noga Alon}}
}
@article{journals/int/Alon13,
title = {Restricted Integer Partition Functions.},
year = {2013},
journal = {Integers},
author = {{Noga Alon}}
}
@article{journals/jacm/AlonY13,
title = {Matrix sparsification and nested dissection over arbitrary fields.},
year = {2013},
journal = {J. ACM},
author = {{Noga Alon} and {Raphael Yuster}}
}
@article{journals/jct/AlonY13,
title = {The Turán number of sparse spanning graphs.},
year = {2013},
journal = {J. Comb. Theory, Ser. B},
author = {{Noga Alon} and {Raphael Yuster}}
}
@article{journals/jgt/Alon13,
title = {A Note on Degenerate and Spectrally Degenerate Graphs.},
year = {2013},
journal = {J. Graph Theory},
author = {{Noga Alon}}
}
@article{journals/siamcomp/AlonBCGM13,
title = {Nearly Tight Bounds for Testing Function Isomorphism.},
year = {2013},
journal = {SIAM J. Comput.},
author = {{Noga Alon} and {Eric Blais} and {Sourav Chakraborty 001} and {David García-Soriano} and {Arie Matsliah}}
}
@article{journals/siamdm/Alon13,
title = {Minimizing the Number of Carries in Addition.},
year = {2013},
journal = {SIAM J. Discret. Math.},
author = {{Noga Alon}}
}
@article{journals/siamdm/AlonDHL13,
title = {Basic Network Creation Games.},
year = {2013},
journal = {SIAM J. Discret. Math.},
author = {{Noga Alon} and {Erik D. Demaine} and {Mohammad Taghi Hajiaghayi} and {Tom Leighton}}
}
@article{journals/siamdm/AlonEFT13,
title = {Adversarial Leakage in Games.},
year = {2013},
journal = {SIAM J. Discret. Math.},
author = {{Noga Alon} and {Yuval Emek} and {Michal Feldman} and {Moshe Tennenholtz}}
}
@article{journals/toc/AlonL13,
title = {Almost k-Wise vs. k-Wise Independent Permutations, and Uniformity for General Group Actions.},
year = {2013},
journal = {Theory Comput.},
author = {{Noga Alon} and {Shachar Lovett}}
}
@inproceedings{conf/approx/AlonLS14,
title = {The Cover Number of a Matrix and its Algorithmic Applications.},
year = {2014},
booktitle = {APPROX-RANDOM},
author = {{Noga Alon} and {Troy Lee} and {Adi Shraibman}},
publisher = {Schloss Dagstuhl - Leibniz-Zentrum für Informatik},
booktitle = {Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques, APPROX/RANDOM 2014, September 4-6, 2014, Barcelona, Spain}
}
@inproceedings{conf/isit/AbbeAB14,
title = {Linear Boolean classification, coding and "the critical problem".},
year = {2014},
booktitle = {ISIT},
author = {{Emmanuel Abbe} and {Noga Alon} and {Afonso S. Bandeira}},
publisher = {IEEE},
booktitle = {2014 IEEE International Symposium on Information Theory, Honolulu, HI, USA, June 29 - July 4, 2014}
}
@inproceedings{conf/soda/AlonGHK14,
title = {Broadcast Throughput in Radio Networks: Routing vs. Network Coding.},
year = {2014},
booktitle = {SODA},
author = {{Noga Alon} and {Mohsen Ghaffari 001} and {Bernhard Haeupler} and {Majid Khabbazian}},
publisher = {SIAM},
booktitle = {Proceedings of the Twenty-Fifth Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2014, Portland, Oregon, USA, January 5-7, 2014}
}
@article{journals/dam/AlonP14,
title = {Chasing robbers on random geometric graphs - An alternative approach.},
year = {2014},
journal = {Discret. Appl. Math.},
author = {{Noga Alon} and {Pawel Pralat}}
}
@article{journals/eccc/AlonMY14,
title = {Sign rank, VC dimension and spectral gaps.},
year = {2014},
journal = {Electron. Colloquium Comput. Complex.},
author = {{Noga Alon} and {Shay Moran} and {Amir Yehudayoff}}
}
@article{journals/jct/AlonK14,
title = {Two notions of unit distance graphs.},
year = {2014},
journal = {J. Comb. Theory, Ser. A},
author = {{Noga Alon} and {Andrey Kupavskii}}
}
@article{journals/siamdm/AlonAH14,
title = {Maximizing the Number of Nonnegative Subsets.},
year = {2014},
journal = {SIAM J. Discret. Math.},
author = {{Noga Alon} and {Harout K. Aydinian} and {Hao Huang 005}}
}
@article{journals/siamdm/AlonDHKL14,
title = {Correction: Basic Network Creation Games.},
year = {2014},
journal = {SIAM J. Discret. Math.},
author = {{Noga Alon} and {Erik D. Demaine} and {MohammadTaghi Hajiaghayi} and {Panagiotis Kanellopoulos} and {Tom Leighton}}
}
@article{journals/siamdm/AlonSY14,
title = {On the Compatibility of Quartet Trees.},
year = {2014},
journal = {SIAM J. Discret. Math.},
author = {{Noga Alon} and {Sagi Snir} and {Raphael Yuster}}
}
@inproceedings{conf/colt/AlonCDK15,
title = {Online Learning with Feedback Graphs: Beyond Bandits.},
year = {2015},
booktitle = {COLT},
author = {{Noga Alon} and {Nicolò Cesa-Bianchi} and {Ofer Dekel} and {Tomer Koren}},
publisher = {JMLR.org},
booktitle = {Proceedings of The 28th Conference on Learning Theory, COLT 2015, Paris, France, July 3-6, 2015}
}
@inproceedings{conf/ijcai/AlonFLT15,
title = {How Robust Is the Wisdom of the Crowds?},
year = {2015},
booktitle = {IJCAI},
author = {{Noga Alon} and {Michal Feldman} and {Omer Lev} and {Moshe Tennenholtz}},
publisher = {AAAI Press},
booktitle = {Proceedings of the Twenty-Fourth International Joint Conference on Artificial Intelligence, IJCAI 2015, Buenos Aires, Argentina, July 25-31, 2015}
}
@article{journals/algorithmica/AlonW15,
title = {Local Correction with Constant Error Rate.},
year = {2015},
journal = {Algorithmica},
author = {{Noga Alon} and {Amit Weinstein}}
}
@article{journals/cc/AlonC15,
title = {On Rigid Matrices and U-Polynomials.},
year = {2015},
journal = {Comput. Complex.},
author = {{Noga Alon} and {Gil Cohen}}
}
@article{journals/coling/BerantADG15,
title = {Efficient Global Learning of Entailment Graphs.},
year = {2015},
journal = {Comput. Linguistics},
author = {{Jonathan Berant} and {Noga Alon} and {Ido Dagan} and {Jacob Goldberger}}
}
@article{journals/comgeo/AlonF15,
title = {Drawing outerplanar graphs using three edge lengths.},
year = {2015},
journal = {Comput. Geom.},
author = {{Noga Alon} and {Ohad N. Feldheim}}
}
@article{journals/corr/AlonMP15,
title = {Corruption Detection on Networks.},
year = {2015},
journal = {CoRR},
author = {{Noga Alon} and {Elchanan Mossel} and {Robin Pemantle}}
}
@article{journals/cpc/AlonF15,
title = {Easily Testable Graph Properties.},
year = {2015},
journal = {Comb. Probab. Comput.},
author = {{Noga Alon} and {Jacob Fox}}
}
@article{journals/eccc/AlonNRW15,
title = {Welfare Maximization with Limited Interaction.},
year = {2015},
journal = {Electron. Colloquium Comput. Complex.},
author = {{Noga Alon} and {Noam Nisan} and {Ran Raz} and {Omri Weinstein}}
}
@article{journals/endm/AlonS15,
title = {Many T copies in H-free graphs.},
year = {2015},
journal = {Electron. Notes Discret. Math.},
author = {{Noga Alon} and {Clara Shikhelman}}
}
@article{journals/gc/Alon15,
title = {Size and Degree Anti-Ramsey Numbers.},
year = {2015},
journal = {Graphs Comb.},
author = {{Noga Alon}}
}
@article{journals/jcss/AlonADDPT15,
title = {Practically stabilizing SWMR atomic memory in message-passing systems.},
year = {2015},
journal = {J. Comput. Syst. Sci.},
author = {{Noga Alon} and {Hagit Attiya} and {Shlomi Dolev} and {Swan Dubois} and {Maria Potop-Butucaru} and {Sébastien Tixeuil}}
}
@article{journals/jct/Alon15,
title = {Bipartite decomposition of random graphs.},
year = {2015},
journal = {J. Comb. Theory, Ser. B},
author = {{Noga Alon}}
}
@article{journals/jct/AlonDGS15,
title = {Comparable pairs in families of sets.},
year = {2015},
journal = {J. Comb. Theory, Ser. B},
author = {{Noga Alon} and {Shagnik Das} and {Roman Glebov} and {Benny Sudakov}}
}
@article{journals/jgt/AlonM15,
title = {Chasing a Fast Robber on Planar Graphs and Random Graphs.},
year = {2015},
journal = {J. Graph Theory},
author = {{Noga Alon} and {Abbas Mehrabian}}
}
@article{journals/siamdm/AlonBCMR15,
title = {Separation Dimension of Bounded Degree Graphs.},
year = {2015},
journal = {SIAM J. Discret. Math.},
author = {{Noga Alon} and {Manu Basavaraju} and {L. Sunil Chandran} and {Rogers Mathew} and {Deepak Rajendraprasad}}
}
@article{journals/teco/AlonBCKNW15,
title = {How to Put Through Your Agenda in Collective Binary Decisions.},
year = {2015},
journal = {ACM Trans. Economics and Comput.},
author = {{Noga Alon} and {Robert Bredereck} and {Jiehua Chen 001} and {Stefan Kratsch} and {Rolf Niedermeier} and {Gerhard J. Woeginger}}
}
@inproceedings{conf/colt/AlonMY16,
title = {Sign rank versus VC dimension.},
year = {2016},
booktitle = {COLT},
author = {{Noga Alon} and {Shay Moran} and {Amir Yehudayoff}},
publisher = {JMLR.org},
booktitle = {Proceedings of the 29th Conference on Learning Theory, COLT 2016, New York, USA, June 23-26, 2016}
}
@inproceedings{conf/isit/AlonBFJ16,
title = {On the duplication distance of binary strings.},
year = {2016},
booktitle = {ISIT},
author = {{Noga Alon} and {Jehoshua Bruck} and {Farzad Farnoud} and {Siddharth Jain}},
publisher = {IEEE},
booktitle = {IEEE International Symposium on Information Theory, ISIT 2016, Barcelona, Spain, July 10-15, 2016}
}
@article{journals/corr/AlonB16,
title = {Removal Lemmas for Matrices.},
year = {2016},
journal = {CoRR},
author = {{Noga Alon} and {Omri Ben-Eliezer}}
}
@article{journals/cpc/AlonHW16,
title = {On Active and Passive Testing.},
year = {2016},
journal = {Comb. Probab. Comput.},
author = {{Noga Alon} and {Rani Hod} and {Amit Weinstein}}
}
@article{journals/dm/AlonB16,
title = {Local and global colorability of graphs.},
year = {2016},
journal = {Discret. Math.},
author = {{Noga Alon} and {Omri Ben-Eliezer}}
}
@article{journals/eccc/AlonES16,
title = {Testing Equality in Communication Graphs.},
year = {2016},
journal = {Electron. Colloquium Comput. Complex.},
author = {{Noga Alon} and {Klim Efremenko} and {Benny Sudakov}}
}
@article{journals/jct/Alon16,
title = {High girth augmented trees are huge.},
year = {2016},
journal = {J. Comb. Theory, Ser. A},
author = {{Noga Alon}}
}
@article{journals/jgt/AharoniAB16,
title = {Eigenvalues of K1, k-Free Graphs and the Connectivity of Their Independence Complexes.},
year = {2016},
journal = {J. Graph Theory},
author = {{Ron Aharoni} and {Noga Alon} and {Eli Berger}}
}
@article{journals/siamdm/AlonNS16,
title = {On the Maximum Quartet Distance between Phylogenetic Trees.},
year = {2016},
journal = {SIAM J. Discret. Math.},
author = {{Noga Alon} and {Humberto Naves} and {Benny Sudakov}}
}
@article{journals/tit/AbbeABS16,
title = {Linear Boolean Classification, Coding and the Critical Problem.},
year = {2016},
journal = {IEEE Trans. Inf. Theory},
author = {{Emmanuel Abbe} and {Noga Alon} and {Afonso S. Bandeira} and {Colin Sandon}}
}
@incollection{reference/algo/AlonYZ16,
title = {Color Coding.},
year = {2016},
booktitle = {Encyclopedia of Algorithms},
author = {{Noga Alon} and {Raphael Yuster} and {Uri Zwick}}
}
@inproceedings{conf/focs/AlonK17,
title = {Optimal Compression of Approximate Inner Products and Dimension Reduction.},
year = {2017},
booktitle = {FOCS},
author = {{Noga Alon} and {Bo'az Klartag}},
publisher = {IEEE Computer Society},
booktitle = {58th IEEE Annual Symposium on Foundations of Computer Science, FOCS 2017, Berkeley, CA, USA, October 15-17, 2017}
}
@inproceedings{conf/nips/Alon0SWMCGDO17,
title = {A graph-theoretic approach to multitasking.},
year = {2017},
booktitle = {NIPS},
author = {{Noga Alon} and {Daniel Reichman 001} and {Igor Shinkar} and {Tal Wagner} and {Sebastian Musslick} and {Jonathan D. Cohen 003} and {Tom Griffiths 001} and {Biswadip Dey} and {Kayhan Özcimder}},
booktitle = {Advances in Neural Information Processing Systems 30: Annual Conference on Neural Information Processing Systems 2017, December 4-9, 2017, Long Beach, CA, USA}
}
@inproceedings{conf/nips/AlonBGMMY17,
title = {Submultiplicative Glivenko-Cantelli and Uniform Convergence of Revenues.},
year = {2017},
booktitle = {NIPS},
author = {{Noga Alon} and {Moshe Babaioff} and {Yannai A. Gonczarowski} and {Yishay Mansour} and {Shay Moran} and {Amir Yehudayoff}},
booktitle = {Advances in Neural Information Processing Systems 30: Annual Conference on Neural Information Processing Systems 2017, December 4-9, 2017, Long Beach, CA, USA}
}
@inproceedings{conf/soda/AlonN17,
title = {Optimal induced universal graphs for bounded-degree graphs.},
year = {2017},
booktitle = {SODA},
author = {{Noga Alon} and {Rajko Nenadov}},
publisher = {SIAM},
booktitle = {Proceedings of the Twenty-Eighth Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2017, Barcelona, Spain, Hotel Porta Fira, January 16-19}
}
@article{journals/algorithmica/AlonFT17,
title = {Revenue and Reserve Prices in a Probabilistic Single Item Auction.},
year = {2017},
journal = {Algorithmica},
author = {{Noga Alon} and {Moran Feldman} and {Moshe Tennenholtz}}
}
@article{journals/eccc/AlonBF17,
title = {Testing hereditary properties of ordered graphs and matrices.},
year = {2017},
journal = {Electron. Colloquium Comput. Complex.},
author = {{Noga Alon} and {Omri Ben-Eliezer} and {Eldar Fischer}}
}
@article{journals/jgt/AlonBH17,
title = {More on the Bipartite Decomposition of Random Graphs.},
year = {2017},
journal = {J. Graph Theory},
author = {{Noga Alon} and {Tom Bohman} and {Hao Huang 005}}
}
@article{journals/siamcomp/AlonCGMMS17,
title = {Nonstochastic Multi-Armed Bandits with Graph-Structured Feedback.},
year = {2017},
journal = {SIAM J. Comput.},
author = {{Noga Alon} and {Nicolò Cesa-Bianchi} and {Claudio Gentile} and {Shie Mannor} and {Yishay Mansour} and {Ohad Shamir}}
}
@article{journals/siamdm/AlonR17,
title = {Broadcast Transmission to Prioritizing Receivers.},
year = {2017},
journal = {SIAM J. Discret. Math.},
author = {{Noga Alon} and {Guy Rutenberg}}
}
@article{journals/tit/AlonBHJ17,
title = {Duplication Distance to the Root for Binary Sequences.},
year = {2017},
journal = {IEEE Trans. Inf. Theory},
author = {{Noga Alon} and {Jehoshua Bruck} and {Farzad Farnoud Hassanzadeh} and {Siddharth Jain}}
}
@article{journals/corr/abs-1809-01873,
title = {The Minrank of Random Graphs over Arbitrary Fields.},
year = {2018},
journal = {CoRR},
author = {{Noga Alon} and {Igor Balla} and {Lior Gishboliner} and {Adva Mond} and {Frank Mousset}}
}
@article{journals/cpc/Alon18,
title = {Uniformly Discrete Forests with Poor Visibility.},
year = {2018},
journal = {Comb. Probab. Comput.},
author = {{Noga Alon}}
}
@article{journals/ejc/AharoniAAHHJKN18,
title = {Ramsey-nice families of graphs.},
year = {2018},
journal = {Eur. J. Comb.},
author = {{Ron Aharoni} and {Noga Alon} and {Michal Amir} and {Penny Haxell} and {Dan Hefetz} and {Zilin Jiang} and {Gal Kronenberg} and {Alon Naor}}
}
@article{journals/jgt/AlonK18,
title = {Clique coloring of dense random graphs.},
year = {2018},
journal = {J. Graph Theory},
author = {{Noga Alon} and {Michael Krivelevich}}
}
@article{journals/teco/BronfmanAHR18,
title = {Redesigning the Israeli Medical Internship Match.},
year = {2018},
journal = {ACM Trans. Economics and Comput.},
author = {{Slava Bronfman} and {Noga Alon} and {Avinatan Hassidim} and {Assaf Romm}}
}
@inproceedings{conf/icalp/AlonCC19,
title = {Deterministic Combinatorial Replacement Paths and Distance Sensitivity Oracles.},
year = {2019},
booktitle = {ICALP},
author = {{Noga Alon} and {Shiri Chechik} and {Sarel Cohen}},
publisher = {Schloss Dagstuhl - Leibniz-Zentrum für Informatik},
booktitle = {46th International Colloquium on Automata, Languages, and Programming, ICALP 2019, July 9-12, 2019, Patras, Greece.}
}
@inproceedings{conf/nips/BassilyMA19,
title = {Limits of Private Learning with Access to Public Data.},
year = {2019},
booktitle = {NeurIPS},
author = {{Raef Bassily} and {Shay Moran} and {Noga Alon}},
booktitle = {Advances in Neural Information Processing Systems 32: Annual Conference on Neural Information Processing Systems 2019, NeurIPS 2019, December 8-14, 2019, Vancouver, BC, Canada.}
}
@inproceedings{conf/stoc/AlonLMM19,
title = {Private PAC learning implies finite Littlestone dimension.},
year = {2019},
booktitle = {STOC},
author = {{Noga Alon} and {Roi Livni} and {Maryanthe Malliaris} and {Shay Moran}},
publisher = {ACM},
booktitle = {Proceedings of the 51st Annual ACM SIGACT Symposium on Theory of Computing, STOC 2019, Phoenix, AZ, USA, June 23-26, 2019.}
}
@article{journals/corr/abs-1908-03694,
title = {High-girth near-Ramanujan graphs with localized eigenvectors.},
year = {2019},
journal = {CoRR},
author = {{Noga Alon} and {Shirshendu Ganguly} and {Nikhil Srivastava}}
}
@article{journals/corr/abs-1911-02000,
title = {On Generalized Regularity.},
year = {2019},
journal = {CoRR},
author = {{Noga Alon} and {Guy Moshkovitz}}
}
@article{journals/dc/AlonBEGH19,
title = {Reliable communication over highly connected noisy networks.},
year = {2019},
journal = {Distributed Comput.},
author = {{Noga Alon} and {Mark Braverman} and {Klim Efremenko} and {Ran Gelles} and {Bernhard Haeupler}}
}
@article{journals/dm/AlonS19,
title = {H-free subgraphs of dense graphs maximizing the number of cliques and their blow-ups.},
year = {2019},
journal = {Discret. Math.},
author = {{Noga Alon} and {Clara Shikhelman}}
}
@article{journals/jlms/AlonMS19,
title = {Traces of hypergraphs.},
year = {2019},
journal = {J. Lond. Math. Soc.},
author = {{Noga Alon} and {Guy Moshkovitz} and {Noam Solomon}}
}
@article{journals/siamdm/AlonS19,
title = {Induced Universal Hypergraphs.},
year = {2019},
journal = {SIAM J. Discret. Math.},
author = {{Noga Alon} and {Nadav Sherman}}
}
@article{journals/teco/AlonFMOT19,
title = {Dynamics of Evolving Social Groups.},
year = {2019},
journal = {ACM Trans. Economics and Comput.},
author = {{Noga Alon} and {Michal Feldman} and {Yishay Mansour} and {Sigal Oren} and {Moshe Tennenholtz}}
}
@article{journals/tit/AlonBP19,
title = {List-Decodable Zero-Rate Codes.},
year = {2019},
journal = {IEEE Trans. Inf. Theory},
author = {{Noga Alon} and {Boris Bukh} and {Yury Polyanskiy}}
}
@inproceedings{conf/approx/AlonA20,
title = {Palette Sparsification Beyond (Δ+1) Vertex Coloring.},
year = {2020},
booktitle = {APPROX-RANDOM},
author = {{Noga Alon} and {Sepehr Assadi}},
publisher = {Schloss Dagstuhl - Leibniz-Zentrum für Informatik},
booktitle = {Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques, APPROX/RANDOM 2020, August 17-19, 2020, Virtual Conference.}
}
@inproceedings{conf/colt/AlonAV20,
title = {Hierarchical Clustering: A 0.585 Revenue Approximation.},
year = {2020},
booktitle = {COLT},
author = {{Noga Alon} and {Yossi Azar} and {Danny Vainstein}},
publisher = {PMLR},
booktitle = {Conference on Learning Theory, COLT 2020, 9-12 July 2020, Virtual Event [Graz, Austria].}
}
@inproceedings{conf/colt/AlonBMS20,
title = {Closure Properties for Private Classification and Online Prediction.},
year = {2020},
booktitle = {COLT},
author = {{Noga Alon} and {Amos Beimel} and {Shay Moran} and {Uri Stemmer}},
publisher = {PMLR},
booktitle = {Conference on Learning Theory, COLT 2020, 9-12 July 2020, Virtual Event [Graz, Austria].}
}
@article{journals/combinatorica/AlonKV20,
title = {Unbalancing Sets and An Almost Quadratic Lower Bound for Syntactically Multilinear Arithmetic Circuits.},
year = {2020},
journal = {Comb.},
author = {{Noga Alon} and {Mrinal Kumar 001} and {Ben Lee Volk}}
}
@article{journals/corr/abs-2001-00387,
title = {Algorithmic Number On the Forehead Protocols Yielding Dense Ruzsa-Szemerédi Graphs and Hypergraphs.},
year = {2020},
journal = {CoRR},
author = {{Noga Alon} and {Adi Shraibman}}
}
@article{journals/corr/abs-2006-16613,
title = {Efficient Splitting of Measures and Necklaces.},
year = {2020},
journal = {CoRR},
author = {{Noga Alon} and {Andrei Graur}}
}
@article{journals/cpc/AlonHKT20,
title = {Edge-statistics on large graphs.},
year = {2020},
journal = {Comb. Probab. Comput.},
author = {{Noga Alon} and {Dan Hefetz} and {Michael Krivelevich} and {Mykhaylo Tyomkyn}}
}
@article{journals/dm/AlonD20,
title = {Isoperimetry, stability, and irredundance in direct products.},
year = {2020},
journal = {Discret. Math.},
author = {{Noga Alon} and {Colin Defant}}
}
@article{journals/dm/AlonGG20,
title = {A probabilistic variant of Sperner 's theorem and of maximal r-cover free families.},
year = {2020},
journal = {Discret. Math.},
author = {{Noga Alon} and {Shoni Gilboa} and {Shay Gueron}}
}
@article{journals/ejc/AlonA20,
title = {On the product dimension of clique factors.},
year = {2020},
journal = {Eur. J. Comb.},
author = {{Noga Alon} and {Ryan Alweiss}}
}
@article{journals/jctb/AlonBST20,
title = {The hat guessing number of graphs.},
year = {2020},
journal = {J. Comb. Theory, Ser. B},
author = {{Noga Alon} and {Omri Ben-Eliezer} and {Chong Shangguan} and {Itzhak Tamo}}
}
@article{journals/jgt/AlonBB20,
title = {Out-colourings of digraphs.},
year = {2020},
journal = {J. Graph Theory},
author = {{Noga Alon} and {Jørgen Bang-Jensen} and {Stéphane Bessy}}
}
@article{journals/order/AlonB20,
title = {Efficient Removal Lemmas for Matrices.},
year = {2020},
journal = {Order},
author = {{Noga Alon} and {Omri Ben-Eliezer}}
}
@article{journals/siamdm/AlonCGMRSWK20,
title = {Multitasking Capacity: Hardness Results and Improved Constructions.},
year = {2020},
journal = {SIAM J. Discret. Math.},
author = {{Noga Alon} and {Jonathan D. Cohen 003} and {Thomas L. Griffiths 001} and {Pasin Manurangsi} and {Daniel Reichman 001} and {Igor Shinkar} and {Tal Wagner} and {Alexander Y. Ku}}
}
@article{journals/toc/AlonMP20,
title = {Distributed Corruption Detection in Networks.},
year = {2020},
journal = {Theory Comput.},
author = {{Noga Alon} and {Elchanan Mossel} and {Robin Pemantle}}
}
@inproceedings{conf/focs/AlonHHM21,
title = {A Theory of PAC Learnability of Partial Concept Classes.},
year = {2021},
booktitle = {FOCS},
author = {{Noga Alon} and {Steve Hanneke} and {Ron Holzman} and {Shay Moran}},
publisher = {IEEE},
booktitle = {62nd IEEE Annual Symposium on Foundations of Computer Science, FOCS 2021, Denver, CO, USA, February 7-10, 2022}
}
@inproceedings{conf/icalp/AlonG21,
title = {Efficient Splitting of Necklaces.},
year = {2021},
booktitle = {ICALP},
author = {{Noga Alon} and {Andrei Graur}},
publisher = {Schloss Dagstuhl - Leibniz-Zentrum für Informatik},
booktitle = {48th International Colloquium on Automata, Languages, and Programming, ICALP 2021, July 12-16, 2021, Glasgow, Scotland (Virtual Conference).}
}
@inproceedings{conf/stoc/AlonBDMNY21,
title = {Adversarial laws of large numbers and optimal regret in online classification.},
year = {2021},
booktitle = {STOC},
author = {{Noga Alon} and {Omri Ben-Eliezer} and {Yuval Dagan} and {Shay Moran} and {Moni Naor} and {Eylon Yogev}},
publisher = {ACM},
booktitle = {STOC '21: 53rd Annual ACM SIGACT Symposium on Theory of Computing, Virtual Event, Italy, June 21-25, 2021.}
}
@article{journals/aam/AlonM21,
title = {Limitations on regularity lemmas for clustering graphs.},
year = {2021},
journal = {Adv. Appl. Math.},
author = {{Noga Alon} and {Guy Moshkovitz}}
}
@article{journals/combinatorica/Alon21,
title = {Explicit Expanders of Every Degree and Size.},
year = {2021},
journal = {Comb.},
author = {{Noga Alon}}
}
@article{journals/corr/abs-2107-12741,
title = {Partitioning all k-subsets into r-wise intersecting families.},
year = {2021},
journal = {CoRR},
author = {{Noga Alon}}
}
@article{journals/cpc/AlonBCMS21,
title = {Mixing properties of colourings of the ℤd lattice.},
year = {2021},
journal = {Comb. Probab. Comput.},
author = {{Noga Alon} and {Raimundo Briceño} and {Nishant Chandgotia} and {Alexander Magazinov} and {Yinon Spinka}}
}
@article{journals/em/AlonCGKM21,
title = {Addressing Johnson Graphs, Complete Multipartite Graphs, Odd Cycles, and Random Graphs.},
year = {2021},
journal = {Exp. Math.},
author = {{Noga Alon} and {Sebastian M. Cioaba} and {Brandon D. Gilbert} and {Jack H. Koolen} and {Brendan D. McKay}}
}
@article{journals/jgt/AlonBKKS21,
title = {List Ramsey numbers.},
year = {2021},
journal = {J. Graph Theory},
author = {{Noga Alon} and {Matija Bucic} and {Tom Kalvari} and {Eden Kuperwasser} and {Tibor Szabó}}
}
@article{journals/jgt/AlonK21,
title = {Divisible subdivisions.},
year = {2021},
journal = {J. Graph Theory},
author = {{Noga Alon} and {Michael Krivelevich}}
}
@article{journals/topc/AlonAB21,
title = {The Price of Bounded Preemption.},
year = {2021},
journal = {ACM Trans. Parallel Comput.},
author = {{Noga Alon} and {Yossi Azar} and {Mark Berlin}}
}
@article{journals/aam/AlonDK22,
title = {The runsort permuton.},
year = {2022},
journal = {Adv. Appl. Math.},
author = {{Noga Alon} and {Colin Defant} and {Noah Kravitz}}
}
@article{journals/algorithmica/AlonS22,
title = {Additive Approximation of Generalized Turán Questions.},
year = {2022},
journal = {Algorithmica},
author = {{Noga Alon} and {Clara Shikhelman}}
}
@article{journals/corr/abs-2201-00328,
title = {Implicit representation of sparse hereditary families.},
year = {2022},
journal = {CoRR},
author = {{Noga Alon}}
}
@article{journals/corr/abs-2203-03744,
title = {Identifying the Deviator.},
year = {2022},
journal = {CoRR},
author = {{Noga Alon} and {Benjamin Gunby} and {Xiaoyu He} and {Eran Shmaya} and {Eilon Solan}}
}
@article{journals/cpc/AlonNS22,
title = {The diameter of the uniform spanning tree of dense graphs.},
year = {2022},
journal = {Comb. Probab. Comput.},
author = {{Noga Alon} and {Asaf Nachmias} and {Matan Shalev}}
}
@article{journals/dcg/AlonJKSY22,
title = {The ε-t-Net Problem.},
year = {2022},
journal = {Discret. Comput. Geom.},
author = {{Noga Alon} and {Bruno Jartoux} and {Chaya Keller} and {Shakhar Smorodinsky} and {Yelena Yuditsky}}
}
@article{journals/dm/AlonC22,
title = {On the hat guessing number of graphs.},
year = {2022},
journal = {Discret. Math.},
author = {{Noga Alon} and {Jeremy Chizewer}}
}
@article{journals/jacm/AlonBLMM22,
title = {Private and Online Learnability Are Equivalent.},
year = {2022},
journal = {J. ACM},
author = {{Noga Alon} and {Mark Bun} and {Roi Livni} and {Maryanthe Malliaris} and {Shay Moran}}
}
@inproceedings{conf/sigecom/AkramiACGMM23,
title = {EFX: A Simpler Approach and an (Almost) Optimal Guarantee via Rainbow Cycle Number.},
year = {2023},
booktitle = {EC},
author = {{Hannaneh Akrami} and {Noga Alon} and {Bhaskar Ray Chaudhury} and {Jugal Garg} and {Kurt Mehlhorn} and {Ruta Mehta}},
publisher = {ACM},
booktitle = {Proceedings of the 24th ACM Conference on Economics and Computation, EC 2023, London, United Kingdom, July 9-12, 2023}
}
@article{journals/corr/abs-2304-03996,
title = {A Unified Characterization of Private Learnability via Graph Theory.},
year = {2023},
journal = {CoRR},
author = {{Noga Alon} and {Shay Moran} and {Hilla Schefler} and {Amir Yehudayoff}}
}
@article{journals/corr/abs-2305-15297,
title = {Strong blocking sets and minimal codes from expander graphs.},
year = {2023},
journal = {CoRR},
author = {{Noga Alon} and {Anurag Bishnoi} and {Shagnik Das} and {Alessandro Neri 002}}
}
@article{journals/corr/abs-2307-06113,
title = {Sublinear Time Shortest Path in Expander Graphs.},
year = {2023},
journal = {CoRR},
author = {{Noga Alon} and {Allan Grønlund} and {Søren Fuglede Jørgensen} and {Kasper Green Larsen}}
}
@article{journals/corr/abs-2307-16784,
title = {On bipartite coverings of graphs and multigraphs.},
year = {2023},
journal = {CoRR},
author = {{Noga Alon}}
}
@article{journals/corr/abs-2312-00379,
title = {Optimal Sample Complexity of Contrastive Learning.},
year = {2023},
journal = {CoRR},
author = {{Noga Alon} and {Dmitrii Avdiukhin} and {Dor Elboim} and {Orr Fischer} and {Grigory Yaroslavtsev}}
}
@article{journals/eccc/AlonBLMM23,
title = {Diagonalization Games.},
year = {2023},
journal = {Electron. Colloquium Comput. Complex.},
author = {{Noga Alon} and {Olivier Bousquet} and {Kasper Green Larsen} and {Shay Moran} and {Shlomo Moran}}
}
@article{journals/jctb/AlonDK23,
title = {Typical and extremal aspects of friends-and-strangers graphs.},
year = {2023},
journal = {J. Comb. Theory, Ser. B},
author = {{Noga Alon} and {Colin Defant} and {Noah Kravitz}}
}
@article{journals/theoretics/AlonGHM23,
title = {Boosting Simple Learners.},
year = {2023},
journal = {TheoretiCS},
author = {{Noga Alon} and {Alon Gonen} and {Elad Hazan} and {Shay Moran}}
}
@article{journals/cpc/AlonW23,
title = {Irregular subgraphs.},
year = {2023},
month = {March},
journal = {Comb. Probab. Comput.},
author = {{Noga Alon} and {Fan Wei}}
}
@article{journals/siamdm/AlonGKMS23,
title = {Structured Codes of Graphs.},
year = {2023},
month = {March},
journal = {SIAM J. Discret. Math.},
author = {{Noga Alon} and {Anna Gujgiczer} and {János Körner} and {Aleksa Milojevic} and {Gábor Simonyi}}
}
@article{journals/jgt/AlonKS23,
title = {Complete minors and average degree: A short proof.},
year = {2023},
month = {July},
journal = {J. Graph Theory},
author = {{Noga Alon} and {Michael Krivelevich} and {Benny Sudakov}}
}
@article{journals/dm/AlonKS23,
title = {Largest subgraph from a hereditary property in a random graph.},
year = {2023},
month = {September},
journal = {Discret. Math.},
author = {{Noga Alon} and {Michael Krivelevich} and {Wojciech Samotij}}
}
@article{journals/ejc/AlonGKP23,
title = {New bounds on the maximum number of neighborly boxes in Rd.},
year = {2023},
month = {December},
journal = {Eur. J. Comb.},
author = {{Noga Alon} and {Jaroslaw Grytczuk} and {Andrzej P. Kisielewicz} and {Krzysztof Przeslawski}}
}
@article{journals/siamdm/AlonFKK23,
title = {The Success Probability in Levine's Hat Problem, and Independent Sets in Graphs.},
year = {2023},
month = {December},
journal = {SIAM J. Discret. Math.},
author = {{Noga Alon} and {Ehud Friedgut} and {Gil Kalai} and {Guy Kindler}}
}
@article{journals/tit/AlonBGHK24,
title = {Logarithmically Larger Deletion Codes of All Distances.},
year = {2024},
month = {January},
journal = {IEEE Trans. Inf. Theory},
author = {{Noga Alon} and {Gabriela Bourla} and {Ben Graham} and {Xiaoyu He} and {Noah Kravitz}}
}
@article{journals/ejc/Alon24,
title = {Graph-codes.},
year = {2024},
month = {February},
journal = {Eur. J. Comb.},
author = {{Noga Alon}}
}
@article{journals/jctb/AlonF24,
title = {Turán graphs with bounded matching number.},
year = {2024},
month = {March},
journal = {J. Comb. Theory, Ser. B},
author = {{Noga Alon} and {Peter Frankl}}
}
@article{journals/siamdm/AlonPSSW24,
title = {Invertibility of Digraphs and Tournaments.},
year = {2024},
month = {March},
journal = {SIAM J. Discret. Math.},
author = {{Noga Alon} and {Emil Powierski} and {Michael Savery} and {Alex D. Scott} and {Elizabeth Wilmer}}
}