List of publications and papers available on-line
-
N. Alon,
On the number of subgraphs of prescribed type pf
graphs with a given number of edges, Israel J. Math. 38(1981),
116-130.
-
N. Alon,
A note on the decomposition of trees into isomorphic
subtrees, Ars Combinatoria 12(1981), 117-121.
-
N. Alon and Y. Caro,
More on the decomposition of trees into
isomorphic subtrees, Ars Combinatoria 14(1982), 123-130.
-
N. Alon,
On the density of sets of vectors, Discrete Math.
46(1983), 199-202.
-
N. Alon and V. D. Milman,
Embedding of $ l_{\infty}^k $ in
finite dimensional Banach spaces, Israel J. Math. 45(1983),
265-280.
-
N. Alon,
On a conjecture of Erdős, Simonovits and Sòs concerning
Anti-Ramsey Theorems, J. Graph Theory 7(1983), 91-94.
-
N. Alon,
A note on the decomposition of graphs into isomorphic
matchings, Acta Math. Acad. Sci. Hungar. 42(1983), 221-223.
-
N. Alon and Y. Caro,
On the number of subgraphs of prescribed type
of planar graphs with a given number of vertices, Annals of
Discrete Math. 20(1984), 25-36.
-
N. Alon and V. D. Milman,
Concentration of measure phenomena in the
discrete case and the Laplace operator of a graph, Seminar on
Functional Analysis 1983/84, Publ. Math. Univ. Paris VII, 20, Univ.
Paris VII, Paris 1984, 55-68.
-
N. Alon, S. Friedland and G. Kalai,
Regular subgraphs of almost
regular graphs, J. Combinatorial Theory, Ser. B 37(1984), 79-91.
-
N. Alon, S. Friedland and G. Kalai,
Every 4-regular graph plus an
edge contains a 3-regular subgraph, J. Combinatorial Theory, Ser. B
37(1984), 92-93.
-
N. Alon,
A note on subdigraphs of digraphs with large outdegrees,
Discrete Math. 49(1984), 321-322.
-
N. Alon and V. D. Milman,
Eigenvalues, expanders and
superconcentrators, Proc. 25th Annual Symp. on Foundations of
Computer Science (FOCS), Singer Island, Florida, IEEE(1984), 320-322.
-
N. Alon and M. Tarsi,
Covering multigraphs by simple circuits, SIAM
J. Alg. Discrete Methods 6(1985), 345-350.
-
N. Alon and V. D. Milman,
$ \lambda_1 $, isoperimetric
inequalities for graphs and superconcentrators, J. Combinatorial
Theory, Ser. B 38(1985), 73-88.
-
N. Alon,
Expanders, sorting in rounds and superconcentrators of
limited depth, Proc. 17th ACM Symp. on the Theory of Computing
(STOC), Providence, RI(1985), 98-102.
-
N. Alon and P. Erdős,
An application of graph theory to additive
number theory, European J. Combinatorics 6(1985), 201-203.
-
N. Alon,
Eigenvalues, geometric expanders and sorting in rounds, in
"Graph Theory with Applications to Algorithms and Computer
Science", (Y. Alavi et. al. eds.), Wiley Interscience, New York,
1985, 15-24.
-
N. Alon, P. Frankl and V. Rödl,
Geometrical realization of set
systems and probabilistic communication complexity, Proc.
26th
Annual Symp. on Foundations of Computer Science (FOCS),
Portland, Oregon,
IEEE(1985),277-280.
-
N. Alon,
An extremal problem for sets with applications to graph
theory, J. Combinatorial Theory, Ser. A 40 (1985), 82-89.
-
N. Alon and Y. Egawa,
Even edge colorings of a graph, J.
Combinatorial Theory, Ser. B 38(1985), 93-94.
-
N. Alon and G. Kalai,
A simple proof of the upper bound theorem,
European J. Combinatorics 6(1985), 211-214.
-
N. Alon and P. Frankl,
The maximum number of disjoint pairs in a
family of subsets, Graphs and Combinatorics 1(1985), 13-21.
-
N. Alon, Z. Füredi and M. Katchalski,
Separating pairs of points by
standard boxes, European J. Combinatorics 6(1985), 205-210.
-
N. Alon,
Asynchronous threshold networks, Graphs and Combinatorics
1 (1985), 305-310.
-
N. Alon,
Hypergraphs with high chromatic number, Graphs and
Combinatorics 1(1985), 387-389.
-
J. Akiyama and N. Alon,
Disjoint simplices, Sugako Seminar
12-85 (1985), 60 (in Japanese).
-
N. Alon,
The longest cycle of a graph with a large minimum degree,
J. Graph Theory 10 (1986), 123-127.
-
N. Alon and E. Györi,
The number of small semispaces of a finite
set of points in the plane, J. Combinatorial Theory, Ser. A
41(1986), 154-157.
-
N. Alon and D. J. Kleitman,
Covering a square by small perimeter
rectangles, Discrete and Computational Geometry 1(1986), 1-7.
-
N. Alon,
Eigenvalues and expanders, Combinatorica 6(1986), 83-96.
-
N. Alon,
Covering graphs by the minimum number of equivalence
relations, Combinatorica 6(1986), 201-206.
-
N. Alon,
Eigenvalues, geometric expanders, sorting in rounds and
Ramsey Theory, Combinatorica 6(1986), 207-219.
-
N. Alon,
On the number of certain subgraphs contained in graphs
with a given number of edges, Israel J. Math. 53(1986), 97-120.
-
N. Alon,
Explicit construction of exponential sized families of
k-independent sets, Discrete Math. 58(1986), 191-193.
-
N. Alon, Y. Azar and U. Vishkin,
Tight complexity bounds for
parallel comparison sorting, Proc. 27th
Annual Symp. on Foundations
of Computer Science (FOCS), Toronto(1986), 502-510.
-
N. Alon and W. Maass,
Meanders, Ramsey Theory and lower bounds for
branching programs, Proc. 27th Annual Symp. on Foundations
of Computer Science (FOCS), Toronto(1986), 410-417.
-
N. Alon,
The number of polytopes, configurations, and real
matroids, Mathematika 33(1986), 62-71.
-
N. Alon, P. Frankl and L. Lovàsz,
The chromatic number of Kneser
hypergraphs, Trans. Amer. Math. Soc. 298(1986), 359-370.
-
N. Alon and M. A. Perles,
On the intersection of edges of a
geometric graph by straight lines, Discrete Math. 60(1986), 75-90.
-
N. Alon and K. Berman,
Regular hypergraphs, Gordon's lemma,
Steinitz's lemma and Invariant Theory, J. Combinatorial Theory, Ser.
A 43(1986), 91-97.
-
N. Alon and Y. Caro,
Extremal problems concerning transformations
of the set of edges of the complete graph, European J.
Combinatorics 7(1986), 93-104.
-
N. Alon,
Decomposition of the complete r-graph into complete
r-partite r-graphs, Graphs and Combinatorics 2(1986),95-100.
-
N. Alon and D. B. West,
The Borsuk-Ulam Theorem and bisection of
necklaces, Proc. Amer. Math. Soc. 98(1986), 623-628.
-
N. Alon, L. Babai and A. Itai,
A fast and simple randomized parallel algorithm
for the maximal independent set problem, J. Algorithms 7 (1986),
567-583.
-
N. Alon, Z. Galil and V. D. Milman,
Better expanders and
superconcentrators, J. Algorithms 8 (1987), 337-347.
-
N. Alon and R. B. Boppana,
The monotone circuit complexity of
Boolean functions, Combinatorica 7 (1987), 1-22.
-
N. Alon,
Splitting necklaces, Advances in Mathematics 63 (1987),
247-253.
-
N. Alon, D. J. Kleitman, K. Pomerance, M. Saks and P. D. Seymour,
The smallest n-uniform hypergraph with positive discrepancy,
Combinatorica 7 (1987), 151-160.
-
N. Alon,
Monochromatic directed walks in arc colored directed
graphs, Acta Math. Acad. Sci. Hungar. 49 (1987), 163-167.
-
N. Alon, D. J. Kleitman, M. Saks, P. D. Seymour and C. Thomassen,
Subgraphs of large connectivity and chromatic number in graphs of
large chromatic number, J. Graph Theory 11 (1987), 367-371.
-
N. Alon,
Subset sums, J. Number Theory 27(1987), 196-205.
-
N. Alon and Z. Füredi,
On the kernel of intersecting families,
Graphs and Combinatorics 3(1987), 91-94.
-
N. Alon, J. Kahn and P. D. Seymour,
Large induced degenerate
subgraphs in graphs, Graphs and Combinatorics 3(1987), 203-211.
-
N. Alon, E. E. Bergmann, D. Coppersmith and A. M. Odlyzko,
Balancing sets of vectors, IEEE Transactions on Information Theory
34 (1988), 128-130.
-
N. Alon, D. Haussler and E. Welzl,
Partitioning and geometric
embedding of range spaces of finite Vapnik-Chervonenkis dimension,
Proc. of the Third Annual Symposium on Computational Geometry,
Waterloo, Canada, ACM Press, (1987), 331-340.
-
N. Alon,
Some recent combinatorial applications of Borsuk-type
theorems, in : "Algebraic, Extremal and Metric Combinatorics"
(M. M. Deza, P. Frankl and I. G. Rosenberg eds. ),
Cambridga Univ. Press, Cambridge, 1988, pp. 1-12.
-
N. Alon and F. R. K. Chung,
Explicit construction of linear sized
tolerant networks, Discrete Math. 72(1988), 15-19;
( Proc. of the First Japan Conference on Graph
Theory and Applications, Hakone, Japan, 1986.)
-
N. Alon and A. Liu,
An application of set theory to coding theory,
Mathematics Magazine 62(1989), 233-237.
-
N. Alon, A. Barak and U. Manber,
On disseminating information
reliably without broadcasting, Proc. of the 7th
International Conference on Distributed Computing Systems (ICDS),
Berlin, September 1987, pp. 74-81.
-
N. Alon and Y. Azar,
The average complexity of deterministic and
randomized parallel comparison sorting algorithms, Proc.
28th Annual IEEE Symposium on Foundations of Computer
Science (FOCS), Los Angeles, CA, 1987, 489-498. Also: SIAM Journal on
Computing 17(1988), 1178-1192.
-
N. Alon and W. Maass,
Meanders and their applications in lower
bounds arguments, J. Computer and System Sciences 37(1988),
118-129.
-
N. Alon and P. Frankl,
Families in which disjoint sets have large
union,
in : Combinatorial Mathematics;
Proc. of the Third International Conference , New York, NY 1985
(G. S. Blum, R. L. Graham
and J. Malkevitch, eds.),
Annals of the New York Academy of Sciences, Vol. 555 (1989), 9-16.
-
N. Alon, R. Faudree and Z. Füredi,
A Turan-like neighborhood
condition and cliques in graphs,
in : Combinatorial Mathematics;
Proc. of the Third International Conference, New York, NY 1985
(G. S. Blum, R. L. Graham
and J. Malkevitch, eds.),
Annals of the New York Academy of Sciences, Vol. 555 (1989), 4-8.
-
N. Alon and G. Freiman,
On sums of subsets of a set of integers,
Combinatorica 8(1988), 297-306.
-
N. Alon, W. T. Trotter and D. B. West,
Regressions and monotone
chains II: The poset of integer intervals, Order 4 (1987), 155-164.
-
J. Akiyama and N. Alon,
Disjoint simplices and geometric
hypergraphs,
in : Combinatorial Mathematics;
Proc. of the Third International Conference , New York, NY 1985
(G. S. Blum, R. L. Graham
and J. Malkevitch, eds.),
Annals of the New York Academy of Sciences, Vol. 555 (1989), 1-3.
-
N. Alon,
Tools from higher algebra, in : "Handbook of
Combinatorics", R.L. Graham, M. Grötschel and L. Lovàsz, eds,
North Holland (1995), Chapter 32, pp. 1749-1783.
-
N. Alon, M. Katchalski and W. R. Pulleyblank,
Cutting disjoint discs
by straight lines, Discrete and Computational Geometry 4(1989),
239-243.
-
N. Alon, S. Cosares, D. S. Hochbaum and R. Shamir,
An algorithm for the
detection and construction of Monge sequences, Linear Algebra and
its Applications 114(1989), 669-680.
-
N. Alon, Y. Caro, I. Krasikov and Y. Roditty,
Combinatorial reconstruction problems,
J. Combinatorial Theory, Ser. B 47(1989),
153-161.
-
N. Alon and Y. Azar,
Sorting, approximate sorting and searching in
rounds, SIAM J. Discrete Math. 1(1988), 269-280.
-
N. Alon, I. Krasikov and Y. Peres,
Reflection sequences,
Amer. Math. Monthly 96(1989), 820-823.
-
N. Alon and E. R. Scheinerman,
Degrees of freedom versus dimension
for containment orders, Order 5(1988), 11-16.
-
N. Alon and Y. Peres,
A note on Euclidean Ramsey Theory and a construction of
Bourgain, Acta Math. Hungar. 57 (1991), 61-64.
-
N. Alon, M. Katchalski and W. R. Pulleyblank,
The maximum size of a
convex polygon in a restricted set of points in the plane,
Discrete and Computational Geometry 4(1989), 245-251.
-
N. Alon and M. O. Rabin,
Biased coins and randomized
algorithms, in "Randomness and Computation", Advances
in Computing Research, (S. Micali ed.), Vol. 5 (1989),
JAI Press, pp. 499-507.
-
N. Alon, Y. Azar and Y. Ravid,
Universal sequences for complete graphs,
Discrete Applied Math. 27(1990), 25-28.
-
N. Alon and J. Spencer,
Ascending waves, J. Combinatorial Theory,
Ser. A 52(1989), 275-287.
-
N. Alon and N. Linial,
Cycles of length 0
modulo k in directed graphs, J. Combinatorial Theory, Ser. B
47(1989), 114-119.
-
N. Alon and Z. Bregman,
Every 8-uniform 8-regular hypergraph is
2-colorable, Graphs and Combinatorics 4(1988), 303-305.
-
N. Alon, M. Katchalski and E.R. Scheinerman,
Not all graphs are
segment T-graphs, European J. Combinatorics 11(1990), 7-13.
-
N. Alon and U. Zwick,
On Nechiporuk's Theorem for branching
programs, Theoretical Computer Science 64(1989), 331-342.
-
N. Alon and Y. Azar,
Finding an approximate maximum, SIAM J. on
Computing 18(1989), 258-267.
-
N. Alon,
The linear arboricity of graphs, Israel J. Math.,
62 (1988), 311-325.
-
I. Algor and N. Alon,
The star arboricity of graphs,
Discrete Math. 75(1989), 11-22.
-
N. Alon and M. Luby,
A linear time erasure-resilient code with
nearly optimal recovery, IEEE Transactions on Information Theory
42 (1996), 1732-1736.
-
N. Alon,
Sums of subsequences modulo prime powers, Discrete Math.
71(1988), 87-88.
-
N. Alon and M. Tarsi,
A nowhere-zero point in linear mappings,
Combinatorica 9 (1989), 393-395.
-
N. Alon and Z. Füredi,
Legitimate colorings of projective planes,
Graphs and Combinatorics 5(1989), 95-106.
-
N. Alon and Y. Azar,
Parallel comparison algorithms for
approximation problems, Proc. 29th Annual Symp. on
Foundations of Computer Science (FOCS),
Yorktown Heights, NY, IEEE (1988),
194-203. Also: Combinatorica 11 (1991), 97-122.
-
N. Alon and P. Erdős,
Disjoint edges in geometric graphs, Discrete and
Computational Geometry 4(1989), 287-290.
-
N. Alon and B. Bollobàs,
Graphs with a small number of distinct
induced subgraphs, Discrete Math. 75(1989), 23-30.
-
N. Alon, A. K. Dewdney and T. J. Ott,
Efficient simulations of
finite automata by neural nets, J. ACM 38 (1991), 495-514.
-
N. Alon and D. J. Kleitman,
Sum-free subsets, in : "A
Tribute to Paul Erdős" (A. Baker, B. Bollobàs
and A. Hajnal eds.),
Cambridge University Press, Cambridge, England 1990, 13-26.
-
N. Alon and P. D. Seymour,
A counter-example to the rank-coloring
conjecture, J. Graph Theory 13(1989), 523-525.
-
N. Alon,
Transmitting in the n-dimensional cube, Discrete Applied
Math. 37/38 (1992), 9-11.
-
N. Alon,
The maximum number of Hamiltonian paths in tournaments,
Combinatorica 10 (1990), 319-324.
-
N. Alon,
Transversal numbers of uniform hypergraphs, Graphs and
Combinatorics 6 (1990), 1-4.
-
N. Alon, A. Bar Noy, N. Linial and D. Peleg,
A lower bound for
radio broadcast, J. Computer and System Sci. 43 (1991), 290-298.
-
N. Alon, N. Linial and R. Meshulam,
Additive bases of vector spaces
over prime fields, J. Combinatorial Theory, Ser. A 57 (1991),
203-210.
-
N. Alon, L. Babai and H. Suzuki,
Multilinear polynomials and
Frankl-Ray-Chaudhuri-Wilson type intersection theorems, J.
Combinatorial Theory, Ser. A 58 (1991), 165-180.
-
N. Alon, Y. Caro and Zs. Tuza,
Sub-Ramsey numbers for arithmetic
progressions, Graphs and Combinatorics 5 (1989), 307-314.
-
N. Alon, Y. Caro and I. Krasikov,
Bisection of trees and sequences,
Discrete Mathematics 114 (1993), 3-7.
-
N. Alon,
Probabilistic proofs of existence of rare events,
Springer Lecture Notes in Mathematics No. 1376 (J. Lindenstrauss
and V. D. Milman Eds.), Springer-Verlag (1988), 186-201.
-
N. Alon,
Independent sets in regular graphs and sum-free subsets of
abelian groups, Israel J. Math. 73 (1991), 247-256.
-
N. Alon, A. Bar Noy, N. Linial and D. Peleg,
On the complexity of
radio communication, Proc. 21th ACM Symp. on the Theory
of Computing (STOC), Seattle, Washington, ACM Press (1989), 274-285.
-
N. Alon and E. R. Scheinerman,
Generalized sum-graphs, Graphs
and Combinatorics 8 (1992), 23-29.
-
N. Alon,
The CW-Inequalities for vectors in $l_1$, European
J. Combinatorics 11(1990), 1-5.
-
N. Alon,
The number of spanning trees in regular graphs, Random
Structures and Algorithms 1 (1990), 175-181.
-
N. Alon and M. Tarsi,
Colorings and orientations of graphs,
Combinatorica 12 (1992), 125-134.
-
N. Alon,
Ramsey graphs cannot be defined by real polynomials,
J. Graph Theory 14(1990), 651-661.
-
N. Alon and A. Hajnal,
Ramsey graphs contain many distinct induced subgraphs,
Graphs and Combinatorics 7 (1991), 1-6.
-
N. Alon, M. Karchmer and A. Wigderson,
Linear circuits over GF(2),
SIAM J. Comput. 19 (1990), 1064-1067.
-
N. Alon, C. McDiarmid and B. Reed,
Star arboricity,
Combinatorica 12 (1992), 375-380.
-
N. Alon and D. J. Kleitman,
Partitioning a rectangle into small
perimeter rectangles, Discrete Mathematics 103 (1992), 111-119.
-
N. Alon, P. D. Seymour and R. Thomas,
A separator theorem for
graphs with an excluded minor and its applications, Proc.
22nd annual ACM Symp. on the Theory of Computing (STOC),
Baltimore, Maryland, 1990, ACM Press, 293-299.
-
N. Alon, R. A. Brualdi and B. L. Shader,
Multicolored forests
in bipartite decompositions of graphs, J. Combinatorial Theory
Ser. B 53 (1991), 143-148.
-
N. Alon and N. Megiddo,
Parallel linear programming in fixed
dimension almost surely in constant time, Proc. 31
IEEE FOCS, St. Louis, Missouri, IEEE (1990), 574-582.
Also: J. ACM 41 (1994), 422-434.
-
N. Alon,
The strong chromatic number of a graph, Random
Structures and Algorithms 3 (1992), 1-7.
-
N. Alon,
Generating pseudo-random permutations and maximum-flow
algorithms, Infor. Proc. Letters 35 (1990), 201-204.
-
N. Alon, P. D. Seymour and R. Thomas,
A separator theorem
for non-planar graphs,
J. Amer. Math. Soc. 3 (1990), 801-808.
-
N. Alon, J. Bruck, J. Naor, M. Naor and R. Roth,
Construction of
asymptotically good, low-rate error-correcting codes through
pseudo-random graphs, IEEE Transactions on Information Theory,
38 (1992), 509-516.
-
N. Alon, A. Bar-Noy, N. Linial and D. Peleg,
Single round
simulation on radio networks, J. of Algorithms 13 (1992), 188-210.
-
N. Alon, C. McDiarmid and B. Reed,
Acyclic colouring of
graphs, Random Structures and Algorithms 2 (1991), 277-288.
-
N. Alon and M. Naor,
Coin-flipping games immune against
linear-sized coalitions, Proc. 31 IEEE FOCS, St. Louis,
Missouri, IEEE (1990), 46-54.
Also:
SIAM J. Comput. 22 (1993),
403-417.
-
N. Alon, D. Kleitman, R. Lipton, R. Meshulam, M. Rabin and
J. Spencer,
Set systems with no union of cardinality 0 modulo
m, Graphs and Combinatorics 7 (1991), 97-99.
-
N. Alon,
Non-constructive proofs in Combinatorics, Proc. of the
International Congress of Mathematicians, Kyoto 1990, Japan,
Springer Verlag, Tokyo (1991), 1421-1429.
-
N. Alon, O. Goldreich, J. Hastad and R. Peralta,
Simple constructions of almost k-wise independent
random variables, Proc. 31 IEEE FOCS, St. Louis,
Missouri, IEEE (1990), 544-553. Also: Random Structures and
Algorithms 3 (1992), 289-304. (Addendum: Random Structures and
Algorithms 4 (1993), 119-120.)
-
N. Alon,
Probabilistic methods in coloring and decomposition problems,
Discrete Mathematics 127 (1994), 31-46.
-
N. Alon,
A parallel algorithmic version of the local lemma,
Random Structures and Algorithms 2 (1991), 367-378.
Also:
Proc. 32 Annual FOCS, IEEE (1991), 586-593 .
-
N. Alon,
Economical coverings of sets of lattice points,
Geometric and Functional Analysis 1 (1991), 224-230.
-
N. Alon,
Probabilistic methods in extremal finite set theory,
in: Extremal Problems for Finite Sets,
(P. Frankl, Z. Füredi, G. O. H. Katona and D. Miklòs Eds.),
Bolyai Society Mathematical Studies,3,
Visegràd, Hungary, 1991,
39-57.
-
N. Alon and R. Yuster,
Almost H-factors in dense graphs,
Graphs and Combinatorics 8 (1992), 95-102.
-
N. Alon, P. D. Seymour and R. Thomas,
Planar separators, SIAM J. Discrete Math. 7 (1994), 184-193.
-
N. Alon and Z. Füredi,
Spanning subgraphs of random graphs, Graphs and Combinatorics
8 (1992), 91-94.
-
N. Alon and Y. Caro,
On three zero-sum Ramsey-type problems, J. Graph Theory 17 (1993),
177-192.
-
N. Alon, Z. Galil and O. Margalit,
On the Exponent of the All Pairs Shortest Path Problem,
Proc. 32 Annual FOCS, IEEE (1991), 569-575.
Also: J. Computer System Sciences
54 (1997), 255-261.
-
N. Alon and Y. Azar,
Comparison sorting and selecting in totally monotone matrices,
Proc. of the Third Annual ACM-SIAM SODA, Orlando, Florida, (1992),
403-408.
-
N. Alon and D. J. Kleitman,
Piercing convex sets and the Hadwiger Debrunner (p,q)-problem,
Advances in Mathematics 96 (1992), 103-112.
-
N. Alon and D. J. Kleitman,
Piercing convex sets,
Proc. 8th ACM Symp. on Computational Geometry, ACM Press
(1992), 157-160. See also: Piercing convex sets (research
announcement), Bulletin of the AMS 27 (1992), 252-256.
-
N. Alon and P. Pudlak,
Superconcentrators of depth 2 and 3; odd levels help (rarely),
J. Comp. Sys. Sci. 48 (1994), 194-202.
-
N. Alon, R. M. Karp, D. Peleg and D. B. West,
A graph-theoretic game and its application to the k-servers
problem, DIMACS Series in Discrete Mathematics and Theoretical
Computer Science, Vol. 7 (1992), 1-9. Also: SIAM J. Comp. 24
(1995), 78-100.
-
N. Alon and J. Bruck,
Explicit construction of depth 2 majority circuits for comparison
and addition, SIAM J. Discrete Math. 7 (1994), 1-8.
-
N. Alon,
Choice numbers of graphs; a probabilistic approach,
Combinatorics, Probability and Computing 1 (1992), 107-114.
-
N. Alon, I. Bàràny, Z. Füredi and D. J. Kleitman,
Point selections and weak $\epsilon$-nets for convex hulls,
Combinatorics, Probability and Computing 1 (1992), 189-200.
-
N. Alon and Y. Peres,
Uniform dilations, Geometric and Functional Analysis 2 (1992),
1-28.
-
N. Alon and J. H. Spencer,
The Probabilistic Method,
Wiley, 1992, xiii+254 pp.
-
N. Alon, I. Kriz and J. Nesetril,
How to color shift hypergraphs, Studia Scientiarum Mathematicarum
Hungarica 30 (1995), 1-11. Also in: Combinatorics and its
Applications to Regularity and Irregularity of Structures
(W. A. Deuber and V. T. Sòs, eds.), Akadèmiai Kiadò, Budapest
1995, 1-11.
-
N. Alon and Y. Azar,
On line Steiner trees in the Euclidean plane,
Proc. 8th ACM Symp. on Computational Geometry, ACM Press
(1992), 337-343. Also: Discrete and Computational Geometry
10 (1993), 113-121.
-
N. Alon, G. Kalai, M. Ricklin and L. Stockmeyer,
Lower bounds on
the competitive ratio for mobile user tracking and distributed
job-scheduling,
Proc. 33 IEEE FOCS, Pittsburgh, IEEE (1992), 334-343.
Also: Theoretical Computer Science 130 (1994), 175-201.
-
N. Alon, H. Lefmann and V. Rödl,
On an anti-Ramsey type result, Colloq. Math. Soc.
Jànos Bolyai 60; Sets, Graphs and Numbers, Budapest (Hungary),
1991, 9-22.
-
N. Alon and Y. Roichman,
Random Cayley graphs and expanders, Random Structures and
Algorithms 5 (1994), 271-284.
-
M. Ajtai, N. Alon, J. Bruck, R. Cypher, C. T. Ho, M. Naor and E.
Szemerèdi,
Fault tolerant graphs, perfect hash functions and
disjoint paths,
Proc. 33 IEEE FOCS, Pittsburgh, IEEE (1992), 693-702.
-
N. Alon, Z. Galil, O. Margalit and M. Naor,
Witnesses for Boolean
matrix multiplication and for shortest paths,
Proc. 33 IEEE FOCS, Pittsburgh, IEEE (1992), 417-426.
-
N. Alon, R. A. Duke, H. Lefmann, V. Rödl and R. Yuster,
The algorithmic aspects of the Regularity Lemma,
Proc. 33 IEEE FOCS, Pittsburgh, IEEE (1992), 473-481.
Also: J. of Algorithms 16 (1994), 80-109.
-
N. Alon and Z. Füredi,
Covering the cube by affine hyperplanes, European J. Combinatorics
14 (1993), 79-83.
-
N. Alon,
Packing of partial designs, Graphs and Combinatorics
10 (1994), 11-18.
-
N. Alon,
Subdivided graphs have linear Ramsey numbers, J. Graph
Theory 18 (1994), 343-347.
-
N. Alon, J. Spencer and P. Tetali,
Covering with latin
transversals, Discrete Applied Math. 57 (1995), 1-10.
-
N. Alon, B. Bollobàs, G. Brightwell and S. Janson,
Linear extensions of a random partial order, Ann. Appl. Probab.
4 (1994), 108-123.
-
N. Alon,
Restricted colorings of graphs, in ''Surveys in Combinatorics",
Proc. 14th British
Combinatorial Conference, London Mathematical Society Lecture
Notes Series 187, edited by K. Walker, Cambridge University Press,
1993, 1-33.
-
N. Alon, F. R. K. Chung and R. L. Graham,
Routing permutations on graphs via matchings,
Proc. 25th ACM Symp. on the Theory of Computing (STOC), San Diego,
CA, 1993, 583-591. Also: SIAM J. Discrete Math. 7(1994), 513-530.
-
N. Alon, S. Rajagopalan and S. Suri,
Long non-crossing configurations in the plane,
Proc.9th ACM Symp. on Computational Geometry, ACM Press
(1993), 257-263. Also: Fundamenta Informaticae 22 (1995), 385-394.
-
P. K. Agarwal, N. Alon, B. Aronov and S. Suri,
Can visibility graphs be represented compactly?,
Proc. 9th ACM Symp. on Computational Geometry, ACM Press
(1993), 338-347. Also: Discrete and Computational Geometry 12
(1994), 347-365.
-
N. Alon and M. Naor,
Derandomization, witnesses for Boolean matrix multiplication
and construction of perfect hash functions, Algorithmica 16 (1996),
434-449.
-
N. Alon and R. Yuster,
The 123 Theorem and its extensions, J. Combinatorial Theory Ser.
A 72 (1995), 322- 331.
-
N. Alon and R. Yuster,
Threshold functions for H-factors, Combinatorics, Probability and
Computing 2 (1993), 137-144.
-
N. Alon and M. Dubiner,
Zero-sum sets of prescribed size, in: "Combinatorics, Paul Erdős
is Eighty", Bolyai Society, Mathematical Studies, Keszthely,
Hungary, 1993, 33-50.
-
N. Alon, S. Ben-David, N. Cesa-Bianchi and D. Haussler,
Scale-sensitive dimensions, uniform convergence and learnability,
Proc. 34th IEEE FOCS, IEEE (1993), 292-301. Also:
J. ACM 44 (1997), 615-631.
-
N. Alon and M. Szegedy,
Large sets of nearly orthogonal vectors,
Graphs and Combinatorics 15 (1999), 1-4.
-
N. Alon and B. Sudakov,
Disjoint systems, Lecture Notes in Computer Science 781, Springer
Verlag (1994), 159-163. Full version in:
Random Structures and Algorithms 6 (1995), 13-20.
-
N. Alon and M. Dubiner,
A lattice point problem and additive number theory, Combinatorica
15 (1995), 301-309.
-
N. Alon, R. Yuster and U. Zwick,
Color-coding: a new method for finding simple paths, cycles,
and other small subgraphs within large graphs,
Proc. of the 26th ACM STOC, ACM Press (1994), 326-335.
Also:
Color-coding, J. ACM 42 (1995), 844-856.
Also: Encyclopedia of Algorithms (2016), 335-338.
-
N. Alon, M. Blum, A. Fiat, S. K. Kannan, M. Naor and R. Ostrovsky,
Matching nuts and bolts,
Proc. of the Fifth Annual ACM-SIAM SODA, (1994), ACM Press,
690-696.
-
N. Alon,
Tough Ramsey graphs without short cycles, J. Algebraic
Combinatorics 4 (1995), 189-195.
-
N. Alon and Zs. Tuza,
The acyclic orientation game on random graphs,
Random Structures and Algorithms 6 (1995), 261-268.
-
N. Alon and N. Kahale,
A spectral technique for coloring random
3-colorable graphs,
Proc. of the 26th ACM STOC, ACM Press (1994), 346-355.
Also; SIAM J. Comput. 26 (1997), 1733-1748.
-
N. Alon,
A note on network reliability, in: Discrete Probability
and Algorithms (D. Aldous, P. Diaconis, J. Spencer and J. M. Steele
eds.), IMA Volumes in Mathematics and its applications, Vol. 72,
Springer Verlag (1995), 11-14.
-
N. Alon,
Neighborly families of boxes and bipartite coverings,
in: The Mathematics of Paul Erdős, R. L. Graham and J.
Nesetril, eds., Springer Verlag, Vol II, Berlin (1997),
27-31.
-
N. Alon and A. Orlitsky,
A lower bound on the expected
length of 1-1 codes, IEEE Transactions on Information Theory
40 (1994), 1670-1672.
-
N. Alon and Y. Mansour,
$\epsilon$-discrepancy sets and their
application for interpolation of sparse polynomials,
Infor. Proc. Letters 54 (1995), 337-342.
-
N. Alon, M. B. Nathanson and I. Ruzsa,
Adding distinct congruence
classes modulo a prime, Amer. Math. Monthly 102 (1995), 250-255.
-
N. Alon, M. R. Fellows and D. R. Hare,
Vertex transversals that
dominate, J. Graph Theory 21 (1996), 21-31.
-
N. Alon, U. Feige, A. Wigderson and D. Zuckerman,
Derandomized
graph products, Computational Complexity 5 (1995), 60-75.
-
N. Alon, R. Yuster and U. Zwick,
Finding and counting given length
cycles, Proc. of the 2 Annual European Symposium on
Algorithms (ESA 94), Utrecht, The Netherlands,
Springer Verlag (1994), pp. 354-364. Also: Algorithmica 17 (1997),
209-223.
See also: Erratum
-
N. Alon and A. Orlitsky,
Repeated communication and Ramsey graphs,
IEEE Transactions on Information Theory 41 (1995), 1276-1289.
-
N. Alon, A. Frieze and D. Welsh,
Polynomial time randomised
approximation schemes for the Tutte polynomial of dense graphs,
Proc. 35th IEEE FOCS, IEEE (1994), 24-35.
Also:
Polynomial time randomized approximation schemes for
Tutte-Gröthendieck invariants: the dense case,
Random Structures and Algorithms 6 (1995), 459-478.
-
N. Alon, M. B. Nathanson and I. Ruzsa,
The polynomial method
and restricted sums of congruence classes, J. Number Theory
56 (1996), 404-417.
-
N. Alon and G. Kalai,
Bounding the piercing number, Discrete and
Computational Geometry 13 (1995), 245-256.
-
N. Alon, M. Katchalski, A. Liu and B. Zhou,
On short edges in straight-edge triangulations,
Mathematica Scandinavica 77 (1995), 184-188.
-
N. Alon, B. Mohar and D. P. Sanders,
On acyclic colorings of graphs on surfaces, Israel J. Math. 94
(1996), 273-283.
-
N. Alon,
Explicit Ramsey graphs and orthonormal labelings,
The Electronic J. Combinatorics 1 (1994), R12, 8pp.
-
N. Alon and E. Fischer,
2-factors in dense graphs, Discrete
Math. 152 (1996), 13-23.
-
N. Alon and A. Srinivasan,
Improved parallel approximation of a
class of integer programming problems, ICALP, 1996, 562-573. Also:
Algorithmica 17 (1997), 449-462.
-
N. Alon,
C. McDiarmid and M. Molloy,
Edge-disjoint cycles in
regular directed graphs, J. Graph Theory 22 (1996), 231-237.
-
N. Alon and N. Kahale,
Approximating the independence number via
the $\theta$-function, Math. Programming 80 (1998), 253-264.
-
N. Alon and M. Krivelevich,
Constructive bounds for a Ramsey-type
problem, Graphs and Combinatorics 13 (1997), 217-225.
-
N. Alon and R. Yuster,
H-factors in dense graphs, J.
Combinatorial Theory, Ser. B 66 (1996), 269-282.
-
N. Alon, P. Erdős, R. Holzman and M. Krivelevich,
On k-saturated graphs with restrictions on the degrees,
J. Graph Theory 23 (1996), 1-20.
-
N. Alon and M. Kolountzakis,
On a problem of Erdős and Turàn
and some related results, J. Number Theory 55 (1995), 82-93.
-
N. Alon and A. Orlitsky,
Source coding and graph entropies,
IEEE Transactions on Information Theory 42 (1996), 1329-1339.
-
N. Alon, J. Edmonds and M. Luby,
Linear time erasure codes with
nearly optimal recovery,
Proc. 36th IEEE FOCS, IEEE (1995), 512-519.
-
N. Alon and P. Erdős,
Sure monochromatic subset sums, Acta
Arithmetica 74 (1996), 269-272.
-
N. Alon,
Bipartite subgraphs, Combinatorica 16 (1996), 301-311.
-
N. Alon, Z. Galil and M. Yung,
Efficient dynamic-resharing
"Verifiable Secret Sharing" against mobile adversary,
Proc. of the 3 Annual European Symposium on
Algorithms (ESA 95), Springer Verlag, LNCS 979, (1995), pp.
523-537.
-
N. Alon and G. Gutin,
Properly colored Hamilton cycles in edge
colored complete graphs, Random Structures and Algorithms 11
(1997), 179-186.
-
R. Ahlswede, N. Alon, P. L. Erdős, M. Ruszinkò and L. A.
Szèkely,
Intersecting systems, Combinatorics, Probability and
Computing 6 (1997), 127-137.
-
N. Alon,
Disjoint directed cycles,
J. Combinatorial Theory, Ser. B 68 (1996), 167-178.
-
N. Alon, J. H. Kim and J. Spencer,
Nearly perfect matchings in
regular simple hypergraphs, Israel J. Math. 100 (1997),
171-187.
-
N. Alon and E. Fischer,
Refining the graph density condition for
the existence of almost K-factors, Ars Combinatoria 52 (1999),
296-308.
-
N. Alon, Zs. Tuza and M. Voigt,
Choosability and fractional
chromatic numbers, Discrete Math. 165/166 (1997), 31-38.
-
N. Alon, Y. Matias and M. Szegedy,
The space complexity of
approximating the frequency moments, Proc. of the 28th ACM
STOC, ACM Press (1996), 20-29. Also; J. Comp. Sys. Sci. 58 (1999),
137-147.
-
N. Alon,
On the edge-expansion of graphs, Combinatorics,
Probability and Computing 6 (1997), 145-152.
-
N. Alon,
Independence numbers of locally sparse graphs and a Ramsey
type problem, Random Structures and Algorithms 9 (1996), 271-278.
-
N. Alon and J. H. Kim,
On the degree, size and chromatic index of
a uniform hypergraph, J. Combinatorial Theory,
Ser. A 77 (1997), 165-170.
-
N. Alon, C. K Fan, D. J. Kleitman and J. Losonczy,
Acyclic
matchings, Advances in Math. 122 (1996), 234-236.
-
N. Alon, Y. Caro and R. Yuster,
Covering the edges of a graph by a
prescribed tree with minimum overlap, J. Combinatorial Theory,
Ser. B 71 (1997), 144-161.
-
N. Alon and T. Marshall,
Homomorphisms of edge-coloured graphs and
Coxeter groups, J. Algebraic Combinatorics 8 (1998), 5-13.
-
N. Alon and B. Sudakov,
On two segmentation problems, J. of
Algorithms 33 (1999), 173-184.
-
N. Alon, P. G. Bradford and R. Fleischer,
Matching nuts and bolts
faster, Infor. Proc. Letters 59 (1996), 123-127.
-
N. Alon and A. Zaks,
T-choosability in graphs, Discrete Applied
Math. 82 (1998), 1-13.
-
N. Alon, M. Krivelevich and B. Sudakov,
Subgraphs with a
large cochromatic number, J. Graph Theory 25 (1997), 295-298.
-
N. Alon, D. N. Kozlov and V. H. Vu,
The geometry of coin-weighing
problems, Proc. 37th IEEE FOCS, IEEE (1996), 524-532.
-
N. Alon,
Derandomization via small sample spaces (abstract),
Proc. SWAT 1996, Lecture Notes in Computer Science 1097,
Springer (1996), 1-3.
-
N. Alon, Y. Azar, G. J. Woeginger and T. Yadid,
Approximation schemes for
scheduling, Proc. of the Eighth Annual ACM-SIAM SODA (1997),
493-500.
-
N. Alon, J. Csirik, S. V. Sevastianov, A. P. A. Vestjens and G. J.
Woeginger,
On-line and off-line approximation algorithms for vector
covering problems,
Proc. of the 4th Annual European Symposium on
Algorithms (ESA 96), LNCS, Springer, 1996, 406-418. Also:
N. Alon, Y. Azar, J. Csirik, L. Epstein,
S. V. Sevastianov, A. P. A. Vestjens and G. J.
Woeginger, On-line and off-line approximation algorithms for vector
covering problems,
Algorithmica 21 (1998), 104-118.
-
N. Alon and D. N. Kozlov,
Coins with arbitrary weights, J.
Algorithms 25 (1997), 162-176.
-
N. Alon and E. Halperin,
Bipartite subgraphs of integer weighted
graphs, Discrete Mathematics 181 (1998), 19-29.
-
N. Alon and M. Krivelevich,
The concentration of the chromatic
number of random graphs, Combinatorica 17 (1997), 303-313.
-
N. Alon,
Randomness and pseudo-randomness in Discrete Mathematics,
Proc. of the 2 European Congress of Mathematics, Progress in
Mathematics 168 (1998), 1-14.
-
N. Alon and D. J. Kleitman,
A purely combinatorial proof of the
Hadwiger Debrunner (p,q)-conjecture,
The Electronic J. Combinatorics 4(2) (1997) R1, 8pp.
-
N. Alon and M. Tarsi,
A note on graph colorings and graph polynomials,
J. Combinatorial Theory Ser. B 70 (1997), 197-201.
-
N. Alon and V. H. Vu,
Anti-Hadamard matrices, coin weighing,
threshold gates and indecomposable hypergraphs, J. Combinatorial
Theory, Ser. A 79 (1997), 133-160.
-
N. Alon,
Piercing d-intervals, Discrete and Computational
Geometry 19 (1998), 333-334.
-
N. Alon,
Combinatorial Nullstellensatz, Combinatorics, Probability
and Computing 8 (1999), 7-29.
-
N. Alon and M. Ruszinkò,
Short certificates for tournaments,
The Electronic J. Combinatorics 4 (1997) R12, 6pp.
-
N. Alon, M. Dietzfelbinger, P. Bro Miltersen, E. Petrank and G. Tardos,
Is linear hashing good?,
Proc. of the 29th ACM
STOC, ACM Press (1997), 465-474. Also: Linear hash functions,
J. ACM 46 (1999), 667-683.
-
N. Alon,
Packings with large minimum kissing numbers, Discrete
Math. 175 (1997), 249-251.
-
N. Alon,
On the capacity of digraphs, European J. Combinatorics
19 (1998), 1-5.
-
N. Alon, P. Kelsen, S. Mahajan and H. Ramesh,
Approximate hypergraph
coloring, Nordic J. Computing 3 (1996), 425-439.
-
N. Alon, M. Krivelevich and B. Sudakov,
Finding a large hidden clique in a random graph,
Proc. of the Ninth Annual ACM-SIAM SODA, ACM Press (1998),
594-598. Also: Random Structures and Algorithms 13 (1998), 457-466.
-
N. Alon, R. Boppana and J. H. Spencer,
An asymptotic isoperimetric
inequality, Geometric and Functional Analysis 8 (1998), 411-436.
-
N. Alon and S. Onn,
Separable partitions, Discrete Applied Math.
91 (1999), 39-51.
-
N. Alon, M. Krivelevich and B. Sudakov,
List coloring of random and
pseudo-random graphs, Combinatorica 19 (1999), 453-472.
-
N. Alon, Y. Caro and R. Yuster,
Packing and covering dense graphs,
J. Combinatorial Designs 6 (1998), 451-472.
-
N. Alon and A. Zaks,
Progressions in sequences of nearly
consecutive integers, J. Combinatorial Theory, Ser. A
84 (1998), 99-109.
-
N. Alon,
The Shannon capacity of a union, Combinatorica
18 (1998), 301-310.
-
N. Alon, V. Rödl and A. Rucinski,
Perfect matchings in
$\epsilon$-regular graphs,
The Electronic J. Combinatorics 5(1) (1998), R13, 4pp.
-
N. Alon, Y. Azar, G. J. Woeginger and T. Yadid,
Approximation schemes for
scheduling on parallel machines, J. of Scheduling
1 (1998), 55--66.
-
N. Alon,
Spectral techniques in graph algorithms, Lecture Notes
in Computer Science 1380 (C. L. Lucchesi and A. V. Moura, Eds.),
Sringer, Berlin, 1998, 206-215.
-
N. Alon, P. Hamburger and A. V. Kostochka,
Regular honest graphs,
isoperimetric numbers, and bisection of weighted graphs,
European J. Combinatorics 20 (1999), 469-481.
-
N. Alon and B. Sudakov,
Bipartite subgraphs and the smallest eigenvalue, Combinatorics,
Probability and Computing 9 (2000), 1-12.
-
N. Alon and I. Ruzsa,
Non-averaging subsets and
non-vanishing transversals,
J. Combinatorial Theory, Ser. A 86 (1999), 1-13.
-
N. Alon, L. Rònyai and T. Szabò,
Norm-graphs: variations and applications, J. Combinatorial Theory,
Ser. B 76 (1999), 280-290.
-
N. Alon, M. Krivelevich and B. Sudakov,
Coloring graphs with sparse neighborhoods, J. Combinatorial Theory,
Ser. B 77 (1999), 73-82.
-
N. Alon,
Graph Powers,
in: Contemporary Combinatorics,
(B. Bollobàs, ed.), Bolyai Society
Mathematical Studies, Springer 2002, pp. 11-28.
-
N. Alon, A. Gyàrfàs and M. Ruszinkò,
Decreasing the Diameter of Bounded Degree Graphs,
J. Graph Theory 35 (2000), 161-172.
-
N. Alon and M. Krivelevich,
The choice number of random bipartite
graphs, Annals of Combinatorics 2 (1998), 291-297.
-
N. Alon, M. Bòna and J. Spencer,
Packing Ferrers Shapes,
Combinatorics, Probability and Computing 9 (2000), 205-211.
-
N. Alon, V. J. Teague and N. C. Wormald,
Linear
arboricity and linear k-arboricity of regular graphs,
Graphs and Combinatorics 17 (2001), 11-16.
-
N. Alon and E. Friedgut,
On the number of permutations avoiding a
given pattern, J. Combinatorial Theory, Ser. A 89 (2000), 133-140.
-
N. Alon, P. D. Seymour and M. Krivelevich,
Long cycles in critical
graphs, J. Graph Theory 35 (2000), 193-196.
-
N. Alon,
Additive
latin transversals, Israel J. Math. 117 (2000),
125-130.
-
N. Alon, P. Gibbons, Y. Matias and M. Szegedy,
Tracking join and
self-join sizes in limited storage,
Proc. of the 18th ACM SIGACT-SIGMOD-SIGART Symposium
on Principles of Database Systems (PODS), Philadelphia, ACM Press,
(1999), 10-20.
Also: JCSS 64 (2002), 719-747.
-
N. Alon, U. Arad and Y. Azar,
Independent sets in hypergraphs with applications to routing via
fixed paths,
Proc. 2nd Workshop on Approximation Algorithms for
Combinatorial Optimization Problems (APPROX),
Berkeley, California, 1999, pp. 16-27.
-
N. Alon, E. Fischer, M. Krivelevich and M. Szegedy,
Efficient testing of large graphs,
Proc. 40th Annual Symp. on
Foundations of Computer Science (FOCS),
New York, NY, IEEE (1999), 656--666.
Also: Combinatorica 20 (2000), 451-476.
-
N. Alon, M. Krivelevich, I. Newman and M. Szegedy,
Regular languages are testable with a
constant number of queries,
Proc. 40th Annual Symp. on
Foundations of Computer Science (FOCS),
New York, NY, IEEE (1999), 645--655.
Also: SIAM J. on Computing 30 (2001), 1842-1862.
-
N. Alon, J. Körner and A. Monti,
String quartets in binary,
Combinatorics, Probability and Computing 9 (2000), 381-390.
-
N. Alon and M. Krivelevich,
Testing k-colorability, SIAM J. Discrete Math.
15 (2002), 211-227.
-
N. Alon, B. Sudakov and A. Zaks,
Acyclic edge-colorings of graphs,
J. Graph Theory 37 (2001), 157-167.
-
N. Alon and R. Yuster,
Every H-decomposition of $K_n$ has a nearly resolvable
alternative, European J. Comb. 21 (2000), 839-845.
-
N. Alon, J. Pach and J. Solymosi,
Ramsey-type theorems with
forbidden subgraphs, Combinatorica 21 (2001), 155-170.
-
N. Alon,
Covering a hypergraph of
subgraphs, Discrete Mathematics 257 (2002), 249-254.
-
N. Alon,
Degrees and choice numbers, Random Structures and
Algorithms 16 (2000), 364-368.
-
N. Alon, E. Fachini and J. Körner,
Locally thin set families,
Combinatorics, Probability and Computing 9 (2000), 481-488.
-
N. Alon and L. Lovàsz,
Unextendible product bases, J.
Combinatorial Theory, Ser. A 95 (2001), 169-179.
-
N. Alon, T. Bohman, R. Holzman and D. J. Kleitman,
On partitions of
discrete boxes, Discrete Math. 257 (2002), 255-258.
-
N. Alon and P. Pudlak,
Constructive lower bounds for off-diagonal
Ramsey numbers, Israel J. Math. 122 (2001), 243-251.
-
N. Alon and V. Asodi,
Sparse universal graphs,
Journal of Computational and Applied Mathematics 142 (2002),
1-11.
-
N. Alon, H. Kaplan, M. Krivelevich, D. Malkhi and J. Stern,
Scalable secure storage when half the system is faulty,
Proc. 27th International Colloquium on Automata, Languages and
Programming (ICALP'2000), Lecture Notes in Computer Science 1853,
576--587. Also: Information and Computation 174 (2002), 203-213.
-
N. Alon, P. Erdős, D. Gunderson and M. Molloy,
A Ramsey-type problem and the Turàn numbers,
J. Graph Theory 40 (2002), 120-129.
-
N. Alon, D. Mubayi and R. Thomas,
Large induced forests in sparse
graphs, J. Graph Theory 38 (2001), 113-123.
-
N. Alon, M. Capalbo, Y. Kohayakawa, V. Rödl, A. Rucinski
and E. Szemerèdi,
Universality and Tolerance,
Proc. 41 IEEE FOCS, IEEE (2000), 14-21.
-
N. Alon, S. Dar, M. Parnas and D. Ron,
Testing of clustering,
Proc. 41 IEEE FOCS, IEEE (2000), 240-250.
Also: SIAM J. Discrete Math. 16 (2003), 393-417 and
SIAM Review 46 (2004), 285-308.
See also: Correction
-
N. Alon, E. Fischer and M. Szegedy,
Parent-identifying codes,
J. Combinatorial Theory, Ser. A 95 (2001), 349-359.
-
N. Alon, S. Hoory and N. Linial,
The Moore bound for irregular
graphs, Graphs and Combinatorics 18 (2002), 53-57.
-
N. Alon, H. Last, R. Pinchasi and M. Sharir,
On the complexity of arrangements of circles in the plane,
Discrete and Comput. Geometry 26 (2001), 465-492.
-
N. Alon,
Algebraic and probabilistic methods in Discrete Mathematics,
in: "Visions in Mathematics, Towards 2000", (N. Alon et. al. eds.),
Birkhäuser, 2000, pp. 455-470.
-
N. Alon, B. Sudakov and U. Zwick,
Constructing worst case
instances for semidefinite programming based approximation algorithms,
Proc. of the Twelfth Annual ACM-SIAM SODA, Washington DC, (2001),
92-100. Also: SIAM J. Discrete Math. 15 (2001/02), 58-72.
-
N. Alon and J. H. Spencer,
The Probabilistic Method,
Second Edition,
Wiley, 2000, xvi+301 pp.
-
I. Adler, N. Alon and S. M. Ross,
On the Maximum Number of Hamiltonian Paths in Tournaments, Random
Structures and Algorithms 18 (2001), 291-296.
-
N. Alon and B. Mohar,
The chromatic number of graph powers,
Combinatorics, Probability and Computing 11 (2002), 1-10.
-
N. Alon, K. Berman and D. J. Kleitman,
On a problem in shuffling, J. Combinatorial Theory, Ser. A 91 (2000),
5-14.
-
N. Alon, M. Capalbo, Y. Kohayakawa, V. Rödl, A. Rucinski
and E. Szemerèdi,
Near-optimum universal graphs for graphs with bounded
degrees, Proc. 5th International Workshop on Randomization and
Approximation Techniques in Computer Science (RANDOM-APPROX), Berkeley,
California, 2001, 170-180.
-
N. Alon and A. Zaks,
Algorithmic Aspects of Acyclic Edge Colorings,
Algorithmica 32 (2002), 611-614.
-
N. Alon, G. Fertin, A. L. Liestman, T. C. Shermer and L. Stacho,
Factor d-domatic colorings of graphs, Discrete Math. 262 (2003), 17-25.
-
N. Alon, T. Milo, F. Neven, D. Suciu and V. Vianu,
XML with data values: typechecking revisted,
Proc. of the 20th ACM SIGACT-SIGMOD-SIGART Symposium
on Principles of Database Systems (PODS), 2001.
Also: JCSS 66 (2003), 688-727.
-
N. Alon, M. Krivelevich and V. H. Vu,
On the concetration of eigenvalues of
random symmetric matrices, Israel J. Math. 131 (2002), 259-267.
-
N. Alon, C. J. Colbourn, A. C. H. Ling and M. Tompa,
Equireplicate Balanced Binary Codes for Oligo Arrays, SIAM J.
Discrete Math. 14 (2001), 481-497.
-
N. Alon and R. Beigel,
Lower Bounds for Approximations by Low Degree Polynomials Over $Z_m$,
Proc. of the 16th Annual
IEEE Conference on Computational Complexity
(CCC), IEEE (2001), 184-187.
-
N. Alon, T. Milo, F. Neven, D. Suciu and V. Vianu,
Typechecking XML Views of Relational Databases,
Proc. of the 2001 IEEE Symposium on Logic in Computer Science
(LICS), 421-430.
Also: ACM Transactions on Computational Logic 4 (2003),
315-354.
-
N. Alon, B. Bollobàs, J. H. Kim and V. H. Vu,
Economical covers with geometric applications,
Proc. London Math. Soc. 86 (2003), 273-301.
-
N. Alon,
Testing subgraphs in large graphs,
Proc. 42 IEEE FOCS, IEEE (2001), 434-441.
Also: Random Structures and Algorithms 21 (2002), 359-370.
-
N. Alon, A. Lubotzky and A. Wigderson,
Semi-direct product in groups and Zig-zag product in graphs:
connections and applications,
Proc. 42 IEEE FOCS, IEEE (2001), 630-637.
-
R. Beigel, N. Alon, M. S. Apaydin, L. Fortnow and S. Kasif,
An optimal procedure for gap closing in whole genome shotgun
sequencing, Proc. 2001 RECOMB, ACM Press, pp. 22-30.
-
N. Alon, G. Kalai, J. Matousek and R. Meshulam,
Transversal Numbers for Hypergraphs Arising in Geometry,
Advances in Applied Math. 29 (2002), 79-101.
-
N. Alon and A. Shapira,
Testing satisfiability,
Proc. of the 13th Annual ACM-SIAM SODA, ACM Press (2002),
645-654. Also: J. Algorithms, 47 (2003), 87-103.
-
N. Alon, V. Guruswami, T. Kaufman and M. Sudan,
Guessing secrets efficiently via list decoding,
Proc. of the 13th Annual ACM-SIAM SODA, ACM Press (2002),
254-262.
Also: ACM Transactions on Algorithms 3 (2007), no. 4, Art. 42, 16 pp.
-
N. Alon, J. Grytczuk, M. Haluszczak and O. Riordan,
Nonrepetitive colorings of graphs,
Random Structures and Algorithms 21 (2002), 336-346.
-
N. Alon, G. Ding, B. Oporowski and D. Vertigan,
Partitioning into graphs with only small components,
J. Combinatorial Theory, Ser. B. 87 (2003), 231-243.
-
N. Alon, R. Beigel, S. Kasif, S. Rudich and B. Sudakov,
Learning a hidden matching, Proc. of the 43 IEEE
FOCS, IEEE (2002), 197-206. Also: SIAM J. Computing 33 (2004), 487-501.
-
N. Alon, W. F. de la Vega, R. Kannan and M. Karpinski,
Random Sampling and Approximation of MAX-CSP Problems,
Proc. of the 34 ACM STOC, ACM Press (2002), 232-239.
Also: JCSS 67 (2003), 212-243.
-
N. Alon,
Voting paradoxes and digraphs realizations,
Advances in Applied Math. 29 (2002), 126-135.
-
N. Alon,
Problems and results in extremal combinatorics,
I, Discrete Math. 273 (2003), 31-53.
-
N. Alon, B. Doerr, T. Luczak and T. Schoen,
On the discrepancy of combinatorial rectangles,
Random Structures and Algorithms 21 (2002), 205-215.
-
N. Alon, B. Bollobàs, M. Krivelevich and B. Sudakov,
Maximum cuts and judicious partitions in graphs without short
cycles, J. Combinatorial Theory, Ser. B 88 (2003), 329-346.
-
N. Alon, M. Krivelevich and B. Sudakov,
Turàn numbers of bipartite graphs and related Ramsey-type
questions, Combinatorics, Probability and Computing 12 (2003), 477-494.
-
N. Alon and M. Capalbo,
Explicit unique-neighbor expanders,
Proc. of the 43 IEEE FOCS, IEEE (2002), 73-79.
-
N. Alon, S. Litsyn and R. Yuster,
A coding theory bound and zero-sum square matrices,
Graphs and Combinatorics 19 (2003), 449-457.
-
N. Alon and V. Rödl,
Sharp bounds
for some multicolor Ramsey numbers, Combinatorica 25 (2005), 125-141.
-
N. Alon and P. Pudlak,
Equilateral sets in $l^n_p$,
Geometric and Functional Analysis 13 (2003), 467-482.
-
N. Alon, M. Krivelevich and B. Sudakov,
Induced subgraphs of prescribed size, J. Graph Theory 43 (2003), 239-251.
-
N. Alon, J. Balogh, P. Keevash and B. Sudakov,
The number of edge colorings with no monochromatic cliques,
J. London Math. Soc. 70 (2004), 273-288.
-
N. Alon,
Discrete Mathematics: methods and challenges, Proc. of the
International Congress of Mathematicians (ICM), Beijing 2002, China,
Higher Education Press (2003), 119-135.
-
N. Alon and R. Yuster,
The number of orientations having no fixed tournament,
Combinatorica 26 (2006), 1-16.
-
N. Alon and M. Capalbo,
Smaller explicit superconcentrators,
Proc. of the Fourteenth Annual ACM-SIAM SODA (2003), 340-346.
Also: Internet Mathematics 1 (2004), 151-163.
-
N. Alon, T. Jiang, Z. Miller and D. Pritikin,
Properly colored subgraphs and rainbow subgraphs
in edge-colorings with local constraints,
Random Structures and Algorithms 23 (2003), 409-433.
-
N. Alon,
A simple algorithm for edge-coloring bipartite multigraphs,
Information Processing Letters 85 (2003), 301-302.
-
N. Alon, I. Benjamini and A. Stacey,
Percolation on finite graphs and isoperimetric inequalities,
Ann. Probab. 32 (2004), 1727-1745.
-
N. Alon and U. Stav,
New bounds on parent-identifying codes:
The case of multiple parents,
Combinatorics, Probability and Computing
13 (2004), 795-807.
-
N. Alon and A. Shapira,
Testing subgraphs in directed graphs,
Proc. of the 35 ACM STOC, ACM Press (2003), 700-709.
Also: JCSS 69 (2004), 354-382.
-
N. Alon, B. Awerbuch, Y. Azar, N. Buchbinder and J. Naor,
The online set cover problem,
Proc. of the 35 ACM STOC, ACM Press (2003), 100-105.
Also: SIAM J. Comput. 39 (2009), 361-370.
-
N. Alon, J. Balogh, B. Bollobàs and T. Szabò,
Game domination number,
Discrete Mathematics 256 (2002), 23-33.
-
N. Alon, O. Goldreich and Y. Mansour,
Almost k-wise independence versus
k-wise independence, Information Processing Letters 88 (2003), 107-110.
-
N. Alon, G. Cohen, M. Krivelevich and S. Litsyn,
Generalized hashing and parent-identifying codes, J. Combinatorial Theory,
Ser. A 104 (2003), 207-215.
-
N. Alon and E. Bachmat,
Regular graphs whose subgraphs tend to be acyclic,
Random Structures and Algorithms 29 (2006), 324-337.
-
N. Alon, G. Gutin and M. Krivelevich,
Algorithms with large domination ratio, J. Algorithms 50 (2004), 118-131.
-
N. Alon and A. Shapira,
A characterization of easily testable induced subgraphs,
Proc. of the Fifteenth Annual ACM-SIAM SODA (2004), 935-944.
Also: Combinatorics, Probability and Computing 15 (2006), 791-805.
-
N. Alon, T. Kaufman, M. Krivelevich, S. Litsyn and D. Ron,
Testing low-degree polynomials over GF(2), RANDOM-APPROX 2003, 188-199.
Also: Testing Reed-Muller codes,
IEEE Transactions on Information Theory 51 (2005), 4032--4039.
-
N. Alon and V. Asodi,
Learning a hidden subgraph, ICALP, 2004, LNCS 3142, 110-121.
Also: SIAM J. Discrete Math. 18 (2005), 697-712.
-
N. Alon, G. Kaplan, A. Lev, Y. Roditty and R. Yuster,
Dense graphs are antimagic,
J. Graph Theory 47 (2004), 297-309.
-
N. Alon, I. Dinur, E. Friedgut and B. Sudakov,
Graph products, Fourier Analysis and Spectral techniques,
Geometric and Functional Analysis 14 (2004), 913-940.
-
N. Alon, B. Awerbuch, Y. Azar, N. Buchbinder and J. Naor,
A general approach to
online network optimization problems,
Proc. of the Fifteenth Annual ACM-SIAM SODA (2004), 577-586.
Also: ACM Transactions on Algorithms 2 (2006), 640-660.
-
N. Alon and A. Naor,
Approximating the Cut-Norm via Grothendieck's Inequality,
Proc. of the 36 ACM STOC, Chicago, ACM Press (2004), 72-80.
Also: SIAM J. Computing 35 (2006), 787-803.
-
N. Alon, M. Krivelevich and B. Sudakov,
MaxCut in H-free graphs, Combinatorics, Probability and Computing 14 (2005),
629-647.
-
N. Alon and A. Shapira,
Linear equations, arithmetic progressions and hypergraph
property testing,
Proc. of the Sixteenth Annual ACM-SIAM SODA (2005), 708-717.
Also: Theory of Computing 1 (2005), 177-216.
-
N. Alon, D. Moshkovitz and M. Safra,
Algorithmic construction of sets for k-restrictions,
ACM Transactions on Algorithms 2 (2006), 153-177.
-
N. Alon,
Problems and results in extremal combinatorics, II,
Discrete Math. 308 (2008), 4460--4472.
-
N. Alon and R. Yuster,
On a hypergraph matching problem,
Graphs and Combinatorics 21 (2005), 377-384.
-
N. Alon, Y. Kohayakawa, C. Mauduit, C. G. Moreira and V. Rödl,
Measures of pseudorandomness for finite sequences: minimal values,
Combinatorics, Probability and Computing 15 (2006), 1-29.
-
N. Alon and V. Asodi,
Edge Coloring with Delays, RANDOM-APPROX 2004, LNCS 3122, 237-248.
Also: Combinatorics, Probability and Computing 16 (2007), 173-191.
-
N. Alon and A. Shapira,
On an Extremal Hypergraph Problem of
Brown, Erdős and Sòs,
Combinatorica 26 (2006), 627-645.
-
N. Alon, G. Brightwell, H. A. Kierstead, A. V. Kostochka and P. Winkler,
Dominating Sets in k-Majority Tournaments,
J. Combinatorial Theory, Ser. B 96 (2006), 374-387.
-
N. Alon, J. Pach, R. Pinchasi, R. Radoicic and M. Sharir,
Crossing Patterns of Semi-algebraic Sets,
J. Combinatorial Theory, Ser. A 111 (2005), 310--326.
-
N. Alon,
Feasible schedules for rotating transmissions,
Combinatorics, Probability and Computing 15 (2006), 783-787.
-
N. Alon, N. Duffield, C. Lund and M. Thorup,
Estimating arbitrary subset sums with few probes,
Proc. of the 24 ACM SIGACT-SIGMOD-SIGART Symposium
on Principles of Database Systems (PODS),
2005, 317-325.
-
N. Alon, K. Makarychev, Y. Makarychev and A. Naor,
Quadratic forms on graphs,
Proc. of the 37 ACM STOC, Baltimore, ACM Press (2005), 486-493.
Also: Inventiones Mathematicae 163 (2006), 499-522.
-
N. Srebro, N. Alon and T. Jaakkola,
Generalization error bounds for
collaborative prediction with low-rank matrices,
Advances in Neural Information Processing Systems (NIPS) 2004.
-
N. Alon, M. Merritt, O. Reingold, G. Taubenfeld and R. W. Wright,
Tight bounds for shared memory systems accessed by
byzantine processes, Distributed Computing 18 (2005), 99-109.
-
N. Alon, M. Badoiu, E. D. Demaine, M. Farach-Colton, M.
Hajiaghayi and A. Sidiropoulos,
Ordinal Embeddings of Minimum Relaxation: General Properties, Trees, and
Ultrametrics,
Proc. of the Sixteenth Annual ACM-SIAM SODA (2005), 650-659.
Also: ACM Trans. Algorithms 4 (2008), no. 4, Art. 46, 21 pp.
-
N. Alon and A. Shapira,
A separation theorem in property testing,
Combinatorica 28 (2008), 261-281.
-
N. Alon and A. Shapira,
Every monotone graph property is testable,
Proc. of the 37 ACM STOC, Baltimore, ACM Press (2005), 128-137.
Also: SIAM J. Computing 38 (2008), 505-522.
-
N. Alon and V. Asodi,
Tracing a single user, European J. of Combinatorics 27 (2006), 1227-1234
-
N. Alon, S. Gutner and Y. Azar,
Admission control to minimize rejections and online set cover with
repetitions, Proc. of the 2005 SPAA, 238-244.
Also: ACM Transactions on Algorithms 6(1), 2009.
-
N. Alon, A. Lingas and M. Wahlen,
Approximating the maximum clique minor
and some subgraph homeomorphism problems,
Theoretical Computer Science 374 (2007), 149-158.
-
N. Alon, M. Krivelevich and B. Sudakov,
Embedding nearly-spanning bounded degree trees,
Combinatorica 27 (2007), 629-644.
-
N. Alon, E. Fischer and I. Newman,
Testing of bipartite graph properties, SIAM J. Comput.
37 (2007), 959-976.
-
N. Alon,
Ranking tournaments,
SIAM J. Discrete Math. 20 (2006), 137-142.
-
N. Alon and A. Shapira,
A characterization of the (natural) graph properties testable
with one-sided error,
Proc. of the 46 IEEE FOCS, IEEE (2005), 429-438.
Also: SIAM J. Computing 37 (2008), 1703--1727.
-
N. Alon, A. Shapira and B. Sudakov,
Additive approximation for edge-deletion problems,
Proc. of the 46 IEEE FOCS, IEEE (2005), 419-428.
Also: Annals of Mathematics 170 (2009), 371-411.
-
N. Alon, B. Awerbuch, Y. Azar and B. Patt-Shamir,
Tell me who I am: an interactive recommendation system,
18th ACM Symposium on Parallelism in
Algorithms and Architectures (SPAA '06), 1-10.
Also: Theory Comput. Syst. 45 (2009), no. 2, 261--279.
-
N. Alon, M. Krivelevich, J. Spencer and T. Szabò,
Discrepancy games, The Electronic J. Combinatorics 12 (2005), R51, 9pp.
-
N. Alon, I. Newman, A. Shen, G. Tardos and N. Vereshchagin,
Partitioning multi-dimensional sets
in a small number of uniform parts,
European J. Combinatorics 28 (2007), 134-144.
-
N. Alon, B. Bollobàs, Gyàrfàs, A. J. Lehel and A. Scott,
Maximum directed cuts in acyclic digraphs, J. Graph Theory 55 (2007), 1-13.
-
N. Alon and E. Lubetzky,
The Shannon capacity of a graph and the independence
numbers of its powers,
IEEE Transactions on Information Theory 52 (2006), 2172-2176.
-
N. Alon and E. Lubetzky,
Codes and Xor graph products, Combinatorica 27 (2007), 13-33.
-
N. Alon, M. Krivelevich, T. Kaufman and D. Ron,
Testing triangle-freeness in general graphs,
Proc. of the Seventeenth Annual ACM-SIAM SODA (2006), 279-288.
Also: SIAM J. Discrete Math. 22 (2008), 786--819.
-
N. Alon, R. Radoicic, B. Sudakov and J. Vondrak,
A Ramsey-type result for the hypercube,
J. Graph Theory 53 (2006), 196-208.
-
N. Alon and S. Smorodinsky,
Conflict-free colorings of shallow discs,
Proc. of the 22nd Annual Symposium on Computational Geometry,
Sedona, Arizona, ACM Press, (2006), 41-43.
Also: Internat. J. Comput. Geom. Appl. 18 (2008), no. 6, 599--604.
-
N. Ailon and N. Alon,
Hardness of Fully Dense Problems,
Information and Computation 205 (2007), 1117-1129.
-
N. Alon and A. Shapira,
Homomorphisms in Graph Property Testing,
in:
Topics in Discrete Mathematics, Dedicated to Jarik Nesetril on the Occasion of his
60th Birthday,
M. Klazar, J. Kratochvil, M. Loebl, J. Matousek, R. Thomas and P. Valtr, eds.,
pp. 281--313.
-
N. Alon and B. Sudakov,
$H$-free graphs of large minimum degree,
The Electronic J. Combinatorics 13 (2006), R19, 9pp.
-
N. Alon and E. Lubetzky,
Independent sets in tensor graph
powers, J. Graph Theory 54 (2007), 73-87.
-
N. Alon and E. Lubetzky,
Privileged users in zero-error transmission over a noisy
channel, Combinatorica 27 (2007), 737--743.
-
N. Alon and M. Capalbo,
Sparse universal graphs for bounded degree graphs,
Random Structures and Algorithms 31 (2007), 123-133.
-
E. Carmi, S. Liu, N. Alon, A. Fiat and D. Fiat,
Resolution enhancement in MRI,
Magnetic resonance imaging 24 (2006), 133-154.
-
N. Alon, E. Fischer, I. Newman and A. Shapira,
A combinatorial characterization of the testable graph
properties: it's all about regularity,
Proc. of the 38 ACM STOC, ACM Press (2006), 251-260.
Also: SIAM J. Computing 39 (2009), 143-167.
-
N. Alon and E. Berger,
The Grothendieck constant of random and pseudo-random graphs,
Discrete Optimization 5 (2008), 323-327.
-
N. Alon, A. Krech and T. Szabò,
Turàn's theorem in the hypercube,
SIAM J. on Disc. Math.
21 (2007), 66-72.
-
N. Alon and V. Asodi,
Tracing many users with almost no rate penalty,
IEEE Transactions on Information Theory 53 (2007), 437-439.
-
N. Alon and E. Lubetzky,
Graph powers, Delsarte, Hoffman, Ramsey and
Shannon, SIAM J. Discrete Math. 21 (2007), 329-348.
-
N. Alon, Y. Kohayakawa, C. Mauduit, C. G. Moreira and V. Rödl,
Measures of pseudorandomness for finite sequences: typical values,
Proc. Lond. Math. Soc. 95 (2007), 778--812.
-
N. Alon,
Splitting digraphs,
Combinatorics, Probability and Computing 15 (2006), 933-937.
-
N. Alon and U. Stav,
What is the furthest graph from a hereditary property ?
Random Structures and Algorithms 33 (2008), 87-104.
-
N. Alon and J. Grytczuk,
Breaking the rhythm on graphs, Discrete Math. 308 (2008), 1375--1380.
-
N. Alon, O. Schwartz and A. Shapira,
An elementary construction of constant-degree expanders,
Proc. of the Eighteenth Annual ACM-SIAM SODA (2007), 454-458.
Also: Combinatorics, Probability and Computing 17 (2008), 319--327.
-
N. Alon, V. Asodi, C. Cantor, S. Kasif and J. Rachlin,
Multi-node graphs: a framework for multiplexed biological assays,
Journal of Computational Biology 13 (2006), 1659-1672.
-
N. Alon, T. Itoh, and T. Nagatani,
On $(\epsilon,k)$-min-wise independent permutations,
Random Structures and Algorithms 31 (2007), 384-389.
-
N. Alon and E. Lubetzky,
Uniformly cross intersecting families, Combinatorica 29 (2009),
389-431.
-
N. Alon and B. Sudakov,
On graphs with subgraphs having large independence numbers,
J. Graph Theory 56 (2007), 149-157.
-
N. Alon and M. Krivelevich,
Extremal and Probabilistic Combinatorics,
In: Princeton Companion to Mathematics, W. T. Gowers, Ed.,
Princeton University Press 2008, pp. 562-575.
-
N. Alon and U. Stav,
The maximum edit distance from hereditary graph properties,
J. Combinatorial Theory, Ser. B 98 (2008), 672-697.
-
N. Alon,
Large sets in finite fields are sumsets, J. Number Theory 126 (2007), 110-118.
-
N. Alon, I. Benjamini, E. Lubetzky and S. Sodin,
Non-backtracking random walks mix faster,
Communications in Contemporary Mathematics 9 (2007), 585-603.
-
N. Alon and S. Gutner,
Balanced families of perfect hash functions and their applications,
Proc. ICALP 2007, 435-446.
Also; ACM Transactions on Algorithms 6 (2010).
-
N. Alon and M. Capalbo,
Optimal universal graphs with deterministic embedding,
Proc. of the Nineteenth Annual ACM-SIAM SODA (2008), 373-378.
-
N. Alon,
Perturbed identity matrices have high rank: proof and applications,
Combinatorics, Probability and Computing 18 (2009), 3-15.
-
A. Agarwal, N. Alon and M. Charikar,
Improved Approximation for Directed Multicut and Directed Sparsest Cut,
Proc. of the 39 ACM STOC, 671-680.
-
N. Alon, A. Andoni, T. Kaufman, K. Matulef, R. Rubinfeld and N. Xie,
Testing k-wise and Almost k-wise Independence,
Proc. of the 39 ACM STOC, 496-505.
-
N. Alon, A. Coja-Oghlan, H. Han, M. Kang, V. Rödl and M. Schacht,
Quasi-Randomness and Algorithmic Regularity for Graphs with General Degree
Distributions, Proc. ICALP 2007, 789-800. Also:
SIAM J. Comput. 39 (2010), 2336-2362.
-
N. Alon, F. V. Fomin, G. Gutin, M. Krivelevich and S. Saurabh,
Parameterized Algorithms for Directed Maximum Leaf Problems,
Proc. ICALP 2007, 352-362.
-
N. Alon, A. Pinchasi and R. Pinchasi,
An isoperimetric inequality in the universal cover of the punctured
plane, Discrete Math. 308 (2008), no. 23, 5691--5701.
-
N. Alon, A. Shapira and U. Stav,
Can a Graph Have Distinct Regular Partitions ?
Proc. COCOON 2007, 428-438.
Also: SIAM J. Discrete Math. 23 (2009), 278-287.
-
N. Alon and S. Gutner,
Linear Time Algorithms for Finding a Dominating
Set of Fixed Size in Degenerated
Graphs, Proc. COCOON 2007, 394-405.
Also: Algorithmica 54 (2009), 544-556.
-
N. Alon,
Poker, Chance and Skill.
-
N. Alon and R. Yuster,
Fast algorithms for Maximum Subset
Matching and All-Pairs Shortest Paths in graphs
with a (not so) small vertex cover, ESA 2007, 175-186.
-
N. Alon, B. Chor, F. Pardi and A. Rapoport,
Approximate Maximum Parsimony and Ancestral Maximum Likelihood,
IEEE/ACM Transactions on Computational Biology
and Bioinformatics 7 (2010), 183-187.
-
N. Alon and M. Capalbo,
Finding disjoint paths in expanders deterministically and online,
Proc. of the 48th IEEE FOCS (2007), 518-524.
-
N. Alon, C. Avin, M. Koucky, G. Kozma, Z. Lotker and M. R. Tuttle,
Many random walks are faster than one,
Proc. SPAA 2008, 119-128.
Also: Combinatorics, Probability and Computing 20 (2011), 481-502.
-
N. Alon and E. Lubetzky,
Poisson approximation for non-backtracking random walks,
Israel J. Math. 174 (2009), 227-252.
-
N. Alon, H. T. Hall, C. Knauer, R. Pinchasi and R. Yuster,
On graphs and algebraic graphs that do not contain cycles of length 4,
J. Graph Theory 68 (2011), 91-102.
-
N. Alon, H. Kaplan, G. Nivasch, M. Sharir and S. Smorodinsky,
Weak $\epsilon$-nets and
interval chains,
Proc. of the Nineteenth Annual ACM-SIAM SODA (2008), 1194-1203.
Also: J. ACM 55 (2008), no. 6, Art. 28, 32 pp.
-
N. Alon, F. V. Fomin, G. Gutin, M. Krivelevich and S. Saurabh,
Better Algorithms and Bounds for Directed Maximum Leaf Problems,
FSTTCS 2007, 316-327. Also:
Spanning directed trees with many leaves,
SIAM J. Discrete Math. 23 (2008/09), no. 1, 466--476.
-
N. Alon and A. V. Kostochka,
Induced subgraphs with distinct sizes,
Random Structures and Algorithms 34 (2009), 45-53.
-
N. Alon and U. Stav,
Stability type results for hereditary properties.
J. Graph Theory 62 (2009), 65-83.
-
N. Alon, M. Krivelevich and B. Sudakov,
Large nearly regular induced subgraphs,
SIAM J. Discrete Math. 22 (2008), no. 4, 1325--1337.
-
N. Alon, P. Pralat and N. Wormald,
Cleaning d-regular graphs with brushes,
SIAM J. Discrete Math. 23 (2008), 233-250.
-
N. Alon, B. Bukh and B. Sudakov,
Discrete Kakeya-type problems and small bases,
Israel J. Math. 174 (2009), 285--301.
-
N. Alon, R. Berke, K. Buchin, M. Buchin,
P. Csorba, S. Shannigrahi, B. Speckmann and
P. Zumstein,
Polychromatic colorings of plane graphs,
Proc. of the 24 Annual Symposium on Computational Geometry,
2008, 338-345.
Also: Discrete and Computational Geometry 42 (2009), no. 3,
421-442.
-
N. Alon and R. Hod,
Optimal monotone encodings,
Proc. ICALP 2008, 258-270.
Also: IEEE Transactions on Information Theory 55 (2009), 1343-1353.
-
N. Alon, I. Ben-Eliezer and M. Krivelevich,
Small sample spaces cannot fool low degree polynomials,
Proc. APPROX-RANDOM 2008, 266-275.
-
N. Alon, A. Hassidim, E. Lubetzky, U. Stav and A. Weinstein,
Broadcasting with side information,
Proc. of the 49th IEEE FOCS (2008), 823-832.
-
N. Alon, D. Halperin, O. Nechushtan and M. Sharir,
The complexity of the outer face in arrangements of random
segments,
Proc. of the 24 Annual Symposium on Computational Geometry,
2008, 69-78.
-
N. Alon, P. Dao,I. Hajirasouliha, F. Hormozdiari and S. C.
Sahinalp,
Biomolecular Network Motif Counting and Discovery by Color Coding,
ISMB 2008, 241-249.
-
N. Alon, L. Drewnowski and T. Luczak,
Stable Kneser hypergraphs and ideals in N with the Nikodym property,
Proc. Amer. Math. Soc. 137 (2009), 467--471.
-
N. Alon and S. Friedland,
The Maximum Number of Perfect Matchings in Graphs
with a Given Degree Sequence,
The Electronic J. Combinatorics 15 (2008), N13.
-
N. Alon, J. Grytczuk, M. Lason and M. Michalek,
Splitting necklaces and measurable colorings of the real line.
Proc. Amer. Math. Soc. 137 (2009), no. 5, 1593--1599.
-
N. Alon and A. Nussboim,
k-wise independent random graphs,
Proc. of the 49 IEEE FOCS (2008), 813-822.
-
N. Alon and U. Feige,
On the power of two, three and four probes,
Proc. of the 20th Annual ACM-SIAM SODA (2009), 346-354.
-
N. Alon, R. Panigrahy and S. Yekhanin,
Deterministic approximation algorithms for the nearest codeword problem.
RANDOM-APPROX 2009, 339-351.
-
N. Alon, O. Gurel-Gurevich and E. Lubetzky,
Choice-memory tradeoff in allocations,
Proc. of the 50th IEEE FOCS (2009), 230-238.
Also: Ann. Appl. Probab. 20 (2010), 1470--1511.
-
N. Alon and B. Klartag,
Economical toric spines via Cheeger's Inequality.
Journal of Topology and Analysis 1 (2009), 101-111.
-
N. Alon and J. H. Spencer,
The Probabilistic Method,
Third Edition,
Wiley, 2008, xv+352 pp.
-
N. Alon, S. Litsyn and A. Shpunt,
Typical peak sidelobe level of binary sequences,
IEEE Transactions on Information Theory 56 (2010), 545-554.
-
O. Ahmadi, N. Alon, I. F. Blake and I. E. Shparlinski,
Graphs with integral spectrum,
Linear Algebra and Applications 430 (2009), 547-552.
-
N. Alon and U. Stav,
Hardness of edge-modification problems,
Theoretical Computer Science 410 (2009), 4920--4927
-
N. Alon and N. Wormald,
High degree graphs contain large-star factors,
in "Fete of Combinatorics", Bolyai Soc. Math. Studies, 20
(Gy. Katona, A. Schrijver and T. Szonyi, eds.), Springer 2010,
pp.9-21.
-
N. Alon and P. Edelman,
The inverse Banzhaf problem,
Soc. Choice Welf. 34 (2010), no. 3, 371--377.
-
N. Alon and S. Gutner,
Balanced Hashing, Color Coding and Approximate Counting,
Proc. IWPEC 2009, (J. Chen and F. V. Fomin, Eds.), LNCS 5917 (2009),
1-16.
-
N. Alon,
Economical elimination of cycles in the torus,
Combinatorics, Probability and Computing 18 (2009), 619-627.
-
N. Alon, A. Granville and A. Ubis,
The number of sumsets in a finite field,
Bull. Lond. Math. Soc. 42 (2010), 784--794.
-
N. Alon, S. Ben-Shimon and M. Krivelevich,
A note on regular Ramsey graphs, J. Graph Theory 64 (2010),
244-249.
-
N. Alon, J. Balogh, A. Kostochka and W. Samotij,
Sizes of induced subgraphs of Ramsey graphs,
Combinatorics, Probability and Computing 18 (2009), 459-476.
-
N. Alon, E. D. Demaine, M. Hajiaghayi and F. T. Leighton,
Basic network creation games, Proc. SPAA 2010, 106-113.
Also: SIAM J. Discrete Math. 27 (2013), no. 2, 656--668.
-
Also: N. Alon, E. D. Demaine, M. Hajiaghayi, P. Kanellopoulos
and F. T. Leighton,
Correction: Basic network creation games,
SIAM J. Discrete Math. 28 (2014), 1638--1640.
-
N. Alon, D. Hefetz and M. Krivelevich,
Playing to retain the advantage, Combinatorics, Probability and
Computing 19 (2010), 481-491.
-
N. Alon, D. Lokshtanov and S. Saurabh,
fast FAST, Proc. ICALP 2009, 49-58.
-
N. Alon, M. Feldman, A. Procaccia and M. Tennenholtz,
Strategyproof Approximation of the minimax on Networks,
Math. Oper. Res. 35 (2010), 513--526.
-
N. Alon, J. Balogh, B. Bollobàs and R. Morris,
The structure of almost all graphs in a hereditary property,
J. Comb. Theory, Ser. B 101 (2011), 85--110.
-
N. Alon, F. Fischer, A. D. Procaccia and M. Tennenholtz,
Sum of Us: Strategyproof selection from the selectors,
Proc. TARK 2011, 101-110.
-
N. Alon, E. Chiniforooshan, V. Chvatal and F. Genest,
Another abstraction of the Erdős-Szekeres Happy End Theorem.
The Electronic J. Combinatorics 17 (2010), N11, 6pp.
-
N. Alon, M. Feldman, A. Procaccia and M. Tennenholtz,
A note on competitive diffusion through social networks,
Infor. Proc. Letters 110 (2010), 221-225.
See also: Erratum
-
N. Alon, O. Angel, I. Benjamini and E. Lubetzky,
Sums and products along sparse graphs, Israel J. Math.
188 (2012), 353--384.
-
N. Alon, Y. Emek, M. Feldman and M. Tennenholtz,
Adversarial leakage in games, Proc. 1st Symposium on Innovations
in Computer Science (ICS 2010), 111-119.
Also: SIAM J. Discrete Math. 27 (2013), no. 1, 363--385.
-
N. Alon,
Combinatorial reasoning in Information Theory,
IEEE Information Theory Society Newsletter 59(2009), 10-13.
-
N. Alon, G. Gutin, E. J. Kim, S. Szeider and A. Yeo,
Solving MAX-r-SAT above a Tight Lower Bound,
Proc. of the 21th Annual ACM-SIAM SODA (2010), 511-517.
Also: Algorithmica: Volume 61, Issue 3 (2011), Page 638-655.
-
N. Alon,
Universality, tolerance, chaos and order,
in: An Irreglar Mind
(I. Barany and J. Solymosi, eds.), Bolyai Soc. Math. Studies
21, Springer 2010, pp. 21-37.
-
N. Alon,
On constant time approximation of parameters of bounded degree
graphs,
in: O. Goldreich (Ed.), "Property Testing",
LNCS 6390, pp. 234--239, Springer, Heidelberg (2010).
-
N. Alon and B. Sudakov,
Increasing the chromatic number of a random graph,
J. of Combinatorics 1 (2010), 345--356.
-
N. Alon, Y. Emek, M. Feldman and M. Tennenholtz,
Bayesian Ignorance, Proc. PODC 2010, 384-391.
Also: Theoret. Comput. Sci. 452 (2012), 1-11.
-
N. Alon,
A non-linear lower bound for planar epsilon-nets,
Proc. of the 51th IEEE FOCS (2010), 341-346.
Also: Discrete and Computational Geometry 47 (2012), 235--244.
-
N. Alon and O. N. Feldheim,
The Brunn-Minkowski Inequality and nontrivial cycles in the
discrete torus, SIAM J. Discrete Math. 24 (2010), 892--894.
-
N. Alon and R. Yuster,
Solving linear systems through nested dissection.
Proc. of the 51th IEEE FOCS (2010), 225-234.
-
N. Alon and R. Yuster,
Matrix sparsification and nested dissection over
arbitrary fields, J. ACM, Volume 60, Issue 4, August 2013.
-
N. Alon, M. Feldman, A. Procaccia and M. Tennenholtz,
Walking in circles, Discrete Math. 310 (2010), 3432--3435.
-
N. Alon and E. Blais,
Testing boolean function isomorphism,
Proc. APPROX-RANDOM 2010, 394-405.
-
N. Alon and A. V. Kostochka,
Hypergraph list coloring and Euclidean Ramsey Theory,
Random Structures and Algorithms 39 (2011), 377-390.
-
N. Alon, H. Attiya, S. Dolev, S. Dubios, M. Gradinariu and S.
Tixeuil,
Sharing memory in a self-stabilizing manner (abstract), DISC 2010, 525-527.
Also:
Practically stabilizing
SWMR atomic memory in message-passing systems. J. Comput. System
Sci. 81 (2015), no. 4, 692--701.
-
N. Alon, S. Haber and M. Krivelevich,
The number of F-matchings in almost every tree is a zero residue,
The Electronic J. Combinatorics 18 (2011), P30, 10pp.
-
N. Alon and Daniel Marx,
Sparse balanced partitions and the complexity of subgraph problems,
SIAM J. Discrete Math. 25(2011), 631--644.
-
N. Alon, K. E. Mellinger, D. Mubayi and J. Verstraete,
The de Bruijn-Erdős Theorem for Hypergraphs, Designs, Codes
and Cryptography 65 (2012), 233-245.
-
N. Alon and P. Pralat,
Modular orientations of random and quasi-random regular graphs,
Combinatorics, Probability and Computing 20 (2011), 321-329.
-
N. Alon, Y. Emek, M. Feldman and M. Tennenholtz,
Economical graph discovery, Proc. 2nd Symposium on Innovations
in Computer Science (ICS 2011), 476-486.
Also: Operations Research 62 (2014), 1236-1246.
-
N. Alon and A. Mehrabian,
On a generalization of Meyniel's Conjecture on the Cops and
Robbers game,
The Electronic J. Combinatorics 18 (2011), P19, 7pp.
-
N. Alon and A. Kostochka,
Dense uniform hypergraphs have high list chromatic number,
Discrete Math. 312 (2012), 2119--2125.
-
N. Alon,
Multicolored matchings in hypergraphs,
Moscow Journal of Combinatorics and Number Theory
1 (2011), 3-10.
-
Y. Afek, N. Alon, O. Barad, N. Barkai, E. Hornstein and Z.
Bar-Joseph,
A biological solution to a fundamental distributed computing
problem,
Science, Vol. 331 no. 6014 (January 2011), pp. 183-185.
-
N. Alon,
A note on degenerate and spectrally degenerate graphs,
J. Graph Theory 72 (2013), 1--6.
-
Y. Afek, N. Alon, Z. Bar-Joseph, A. Cornejo, B. Haeupler and F.
Kuhn,
Beeping a Maximal Independent Set, DISC 2011, 32-50.
Also: Distributed Computing 26(4) (2013), 195-208.
-
N. Alon and S. Lovett,
Almost k-wise vs. k-wise independent permutations, and
uniformity for general group actions,
Proc. APPROX-RANDOM 2012, 350-361.
Also: Theory of Computing 9(15) (2013), 559-577.
-
N. Alon and I. Ben-Eliezer,
Local rainbow colorings, J. of Combinatorics 2 (2011), 293--304.
-
N. Alon, S. Arora, R. Manokaran, D. Moshkovitz and O. Weinstein,
Inapproximabilty of Densest k-Subgraph from Average Case
Hardness
-
N. Alon, A. Shpilka and C. Umans,
On Sunflowers and Matrix Multiplication,
IEEE Conference on Computational Complexity 2012, 214-223.
Also: Computational Complexity 22 (2013), 219-243.
-
N. Alon, E. Blais, S. Chakraborty, D. Garcia-Soriano and A.
Matsliah,
Nearly Tight Bounds for Testing Function Isomorphism,
SIAM J. Comput. 42 (2013), no. 2, 459--493.
-
N. Alon, P. Frankl, H. Huang, V. Rodl, A. Rucinski and B.
Sudakov,
Large matchings in uniform hypergraphs and the conjectures of
Erdos and Samuels, J. Combinatorial Theory, Ser. A
119(2012), 1200--1215.
-
N. Alon, H. Huang and B. Sudakov,
Nonnegative k-sums, fractional covers, and probability of
small deviations, J. Combinatorial Theory, Ser. B
102 (2012), 784--796.
-
N. Alon, I. Gamzu, M. Felmdan and M. Tennenholtz,
The asymmetric matrix partition problem,
Proc. WINE 2013, 1-14.
-
N. Alon, R. Rubinfeld, S. Vardi and N. Xie,
Space-efficient Local Computation Algorithms,
Proc. of the 23th Annual ACM-SIAM SODA (2012),
1132-1139.
-
N. Alon and A. Weinstein,
Local Correction of Juntas, Information Proc. Letters
112 (2012), 223-226.
-
N. Alon and J. Fox,
Easily testable graph properties,
Combin. Probab. Comput. 24 (2015), no. 4, 646--657.
-
N. Alon, A. Moitra and B. Sudakov,
Nearly Complete Graphs Decomposable into
Large Induced Matchings and their Applications,
Proc. of the 44th ACM STOC (2012), 1079-1089.
Also: J. Eur. Math. Soc. (JEMS) 15 (2013), no. 5, 1575--1596.
-
N. Alon, I. Gamzu and M. Tennenholtz,
Optimizing Budget Allocation Among Channels and Influencers,
Proc. WWW 2012, 381-388.
-
N. Alon,
The chromatic number of random Cayley graphs,
European Journal of Combinatorics 34 (2013),
1232-1243.
-
N. Alon and R. Yuster,
The Turàn number of sparse spanning graphs,
J. Combinatorial Theory, Ser. B 103 (2013), no. 3, 337--343.
-
N. Alon, J. Balogh, R. Morris and W. Samotij,
Counting sum-free sets in abelian groups,
Israel J. Math. 199 (2014), no. 1, 309--344.
-
N. Alon, M. Babaioff, R. Karidi, R. Lavi and M. Tennenholtz,
Sequential Voting with Externalities: Herding in Social Networks,
Proc. EC 2012.
-
N. Alon, J. Balogh, R. Morris and W. Samotij,
A refinement of the Cameron-Erdős Conjecture,
Proc. London Math. Soc. (3) 108 (2014), no. 1, 44--72.
-
N. Alon,
Restricted integer partition functions, Integers
13 (2013), A16, 9 pp.
-
N. Alon and A. Mehrabian,
Chasing a Fast Robber on Planar Graphs and Random Graphs,
J. Graph Theory 78 (2015), 81-96.
See also: Correction
-
N. Alon,
Minimizing the number of carries in addition,
SIAM J. Discrete Math. 27 (2013), no. 1, 562--566.
-
N. Alon and G. Cohen,
On Rigid Matrices and U-Polynomials,
IEEE Conference on Computational Complexity (CCC) 2013, 197-206.
Also: Computational Complexity 24 (2015), 851--879.
-
N. Alon and A. Weinstein,
Local correction with constant error rate,
Algorithmica 71 (2015), 496--516.
-
N. Alon, T. Lee, A. Shraibman and S. Vempala,
The approximate rank of a matrix and its algorithmic applications,
Proc. STOC 2013, 675-684.
-
N. Alon and O. Feldheim,
Drawing outerplanar graphs using three edge lengths,
Comput. Geom. 48 (2015), no. 3, 260--267.
-
N. Alon,
Paul Erdős and Probabilistic Reasoning,
In: Erdős Centennial Volume, Bolyai Soc. Math. Stud. 25
(L. Lovàsz, I. Ruzsa and V. Sòs, eds.), Springer, 2013, 11-33.
-
N. Alon, D. Falik, R. Meir and M. Tennenholtz,
Bundling Attacks in Judgment Aggregation,
Proc. AAAI 2013.
-
N. Alon, M. Feldman and M. Tennenholtz,
Revenue and Reserve Prices in a Probabilistic Single Item Auction,
Algorithmica 77 (2017), 1--15.
-
N. Alon, Y. Mansour and M. Tennenholtz,
Differential pricing with inequity aversion in social networks,
Proc. ACM Conference on Electronic Commerce 2013, 9-24.
-
N. Alon, R. Bredereck, J. Chen, S. Kratsch, R. Niedermeier and G.
J. Woeginger,
How to put through your agenda in collective binary
decisions, Proc. 3rd International Conference on Algorithmic
Decision Theory (LNCS), Vol. 8176, 30-44.
-
N. Alon and A. Kupavskii,
Two notions of unit distance graphs,
J. Combinatorial Theory, Ser. A 125 (2014), 1--17.
-
N. Alon, N. Cesa-Bianchi , C. Gentile and Y. Mansour,
From Bandits to Experts: A Tale of Domination and Independence,
Proc. NIPS 2013, 1610-1618.
-
N. Alon, S. Snir and R. Yuster,
On the compatibility of quartet trees,
Proc. SODA 2014, 535-545.
Also: SIAM J. Discrete Math. 28 (2014), 1493-1507.
-
R. Aharoni, N. Alon and E. Berger,
Eigenvalues of K(1,k)-free graphs and
the connectivity of their independence complexes,
J. Graph Theory 83 (2016), 384--391.
-
N. Alon, M. Ghaffari, B. Haeupler and M. Khabbazian,
Broadcast Throughput in Radio Networks: Routing vs. Network
Coding, Proc. SODA 2014, 1831-1843.
-
N. Alon, R. Hod and A. Weinstein,
On active and passive testing,
Combinatorics, Probability and Computing,
25 (2016), no. 1, 1--20.
-
N. Alon,T. Lee and A. Shraibman,
The cover number of a matrix and its algorithmic applications,
Proc. APPROX 2014, 34-47.
-
N. Alon,
Paul Erdős and the Probabilistic Method,
Notices of the AMS 62 (2015), 226-230.
-
N. Alon, H. Aydinian and H. Huang,
Maximizing the number of nonnegative subsets,
SIAM J. Discrete Math. 28 (2014), 811-816.
-
N. Alon and J. Bourgain,
Additive patterns in multiplicative subgroups, Geometric and
Functional Analysis 24 (2014), no. 3, 721--739.
-
N. Alon and P. Pralat,
Chasing robbers on random geometric graphs---an
alternative approach, Discrete Applied Math. 178 (2014), 149-152.
-
E. Abbe, N. Alon and A. S. Bandeira,
Linear Boolean classification, coding and the critical
problem, Proc. ISIT 2014, 1231-1235.
Also: E. Abbe, N. Alon, A. S. Bandeira and C. Sandon,
Linear Boolean classification, coding and the critical
problem, IEEE Transactions on Information Theory 62 (2016),
1667-1673.
-
N. Alon and O. N. Feldheim,
A note on general sliding window processes,
Electronic Communications in Prob.
19 (2014), No. 66, 7pp.
-
N. Alon,
Bipartite decomposition of random graphs,
J. Combinatorial Theory, Ser. B 113 (2015), 220-235.
-
N. Alon, M. Basavaraju, L. S. Chandran, R. Mathew and D.
Rajendraprasad,
Separation dimension of bounded degree graphs,
SIAM J. Discrete Math. 29 (2015), no. 1, 59--64.
-
N. Alon,
Size and degree anti-Ramsey numbers, Graphs and Combinatorics
31 (2015), 1833--1839.
-
N. Alon and C. Shikhelman,
Many T-copies in H-free graphs, J. Combinatorial Theory, Ser. B,
121 (2016), 146--172.
-
N. Alon,
Problems and results in Extremal Combinatorics - III,
J. of Combinatorics 7 (2016), 233--256.
-
N. Alon,T. Bohman and H. Huang,
More on the bipartite decomposition of random graphs,
J. Graph Theory 84 (2017), 45--52.
-
N. Alon, N. Cesa-Bianchi , C. Gentile, S. Manor, Y. Mansour and O.
Shamir,
Nonstochastic Multi-Armed bandits with Graph-Structured Feedback,
SIAM J. Comput. 46 (2017), 1785-1826.
-
N. Alon,
Approximating sparse binary matrices in the cut-norm,
Linear Alg. and Applications 486 (2015), 409--418.
-
N. Alon, S. Moran and A. Yehudayoff,
Sign rank versus VC dimension,
Proc. COLT 2016, 47-80.
Also:
Sign rank versus Vapnik-Chrevonenkis dimension,
Mat. Sbornik 208:12 (2017), 1724-1757.
-
N. Alon and O. Ben-Eliezer,
Local And Global Colorability of Graphs,
Discrete Mathematics 339 (2016), 428-442.
-
N. Alon. M. Feldman, O. Lev and M. Tennenholtz,
How robust is the wisdom of the crowd?,
Proc. IJCAI 2015, 2055-2061.
-
J. Berant, I. Dagan, N. Alon and J. Goldberger,
Efficient global learning of entailment graphs,
Comput. Linguist. 41 (2015), no. 2,
221--263.
-
N. Alon, S. Das, R. Glebov and B. Sudakov,
Comparable pairs in families of sets,
J. Combinatorial Theory, Ser. B 115 (2015), 164--185.
-
N. Alon, A. Kostochka, B. Reiniger, D. B. West and X. Zhu,
Coloring, sparseness, and girth, Israel J. Math.
214 (2016), 315-331.
-
N. Alon, M. Braverman, K. Efremenko, R. Gelles and B. Haeupler,
Reliable Communication over Highly Connected Noisy Networks,
Proc. PODC 2016, 165--173. Also: Distrib. Comput. 32 (2019),
no. 6, 505--515.
-
S. Bronfman, N. Alon, A. Hassidim and A. Romm,
Redesigning the Israeli Medical Internship Match,
Proc. EC 2015, 753-754.
Also: ACM Trans. Econ. Comput. 6 (2018), no. 3-4, Art. 21, 18 pp.
-
N. Alon, N. Cesa-Bianchi, O. Dekel and T. Koren,
Online Learning with Feedback Graphs: Beyond Bandits,
Proc. COLT 2015, 23-35.
-
N. Alon, N. Nisan, R. Raz and O. Weinstein,
Welfare Maximization with Limited Interaction,
Proc. FOCS 2015, 1499-1512.
-
N. Alon, M. Feldman, Y. Mansour, S. Oren and M. Tennenholtz,
Dynamics of Evolving Social Groups,
Proc. EC 2016, 637-654. Also:
ACM Trans. Economics and Comput. 7(3): 14:1-14:27 (2019).
-
N. Alon, H. Naves and B. Sudakov,
On the maximum quartet distance between phylogenetic trees,
Proc. SODA 2016, 2095-2106. Also: SIAM J. Discrete Math. 30 (2016),
718-735.
-
N. Alon, E. Mossel and R. Pemantle,
Distributed Corruption Detection on Networks,
Theory of Computing 16(1), 2020, 1--23.
-
R. Aharoni, N. Alon, E. Berger, M. Chudnovsky, D.
Kotlar, M. Loebl and R. Ziv,
Fair representation by independent sets,
in: "A Journey through Discrete Mathematics. A Tribute to Jiri
Matousek"
(Jan Kratochvil, Martin Loebl, Jarik Nesetril, Robin Thomas and
Pavel Valtr, editors), Springer (2017), 31--58
-
N. Alon, J. Bruck, F. Farnoud and S. Jain,
On the Duplication Distance of Binary Strings,
Proc. ISIT 2016, 260-264.
Also:
Duplication Distance to the Root
for Binary Sequences,
IEEE Transactions on Information Theory 63 (2017), 7793-7803.
-
N. Alon and J. H. Spencer,
The Probabilistic Method,
Fourth Edition,
Wiley, 2016, xv+375 pp.
-
N. Alon,
Uniformly discrete forests with poor visibility,
Combinatorics, Probability and Computing 27 (2018), 442--448.
-
N. Alon,
High girth augmented trees are huge,
J. Combinatorial Theory, Ser. A 144
(2016), 7--15.
-
N. Alon,
Asymptotically optimal induced universal graphs,
Geometric and Functional Analysis 27(2017), 1-32.
-
N. Alon, K. Efremenko and B. Sudakov,
Testing equality in communication graphs,
IEEE Transactions on Information Theory 63 (2017), 7569-7574.
-
N. Alon, R. Bissacot and E. O. Endo,
Counting contours on trees,
Lett. Math. Phys. 107 (2017), no. 5, 887--899.
-
N. Alon and R. Nenadov,
Optimal induced universal graphs for bounded-degree graphs,
Proc. SODA 2017, 1149-1157. Also: Math. Proc. Cambridge Phil. Soc.
166 (2019), 61--74.
-
N. Alon, A. Pokrovskiy and B. Sudakov,
Random subgraphs of properly edge-coloured complete graphs and long
rainbow cycles, Israel J. Math. 222(2017), 317-331
-
N. Alon and O. Ben-Eliezer,
Efficient Removal Lemmas for Matrices, Proc. APPROX-RANDOM 2017,
25:1-25:18. Also: Order 37 (2020), 83--101.
-
N. Alon and B. Klartag,
Optimal compression of approximate inner products and dimension
reduction, Proc. FOCS 2017, 639-650.
-
N. Alon and G. Rutenberg,
Broadcast Transmission to Prioritizing Receivers,
SIAM J. on Discrete Math. 31 (2017), 2517-2529.
-
N. Alon and M. Krivelevich,
Clique coloring of dense random graphs, J. Graph Theory
88 (2018), 428--433.
-
N. Alon, A. Kostochka and C. Shikhelman,
Many cliques in H-free subgraphs of random graphs, J. of
Combinatorics 9 (2018), 567--597.
-
N. Alon, M. Basavaraju, L. S. Chandran, R. Mathew and D.
Rajendraprasad,
Separation Dimension and Sparsity, J. Graph Theory 89 (2018),
14-25.
-
N. Alon, M. Babaioff, Y. A. Gonczarowski, Y. Mansour, S. Moran,
and Amir Yehudayoff,
Submultiplicative Glivenko-Cantelli and Uniform Convergence of
Revenues, Proc. NIPS 2017, 1655-1664.
-
N. Alon, O. Ben-Eliezer and E. Fischer
Testing hereditary properties of ordered graphs and
matrices, Proc. FOCS 2017, 848-858.
-
N. Alon, J. D. Cohen, B. Dey, T. Griffiths, S. Musslick, K.
Ozcimder, D. Reichman, I. Shinkar and T. Wagner,
A graph-theoretic approach to multitasking, Proc. NIPS 2017,
2097-2106.
-
N. Alon, S. Butler, R. Graham and U. C. Rajkumar,
Permutations resilient to deletions,
Annals of Combinatorics 22 (2018), 673-680.
-
N. Alon and C. Shikhelman,
H-free subgraphs of dense graphs maximizing the number of
cliques and their blow-ups,
Discrete Math. 342 (2019), no. 4, 988--996.
-
N. Alon, J. Bang-Jensen and S. Bessy,
Out-colourings of Digraphs, J. Graph Theory 93 (2020), 88-112.
-
R. Aharoni, N. Alon, M. Amir, P. Haxell, D. Hefetz, Z. Jiang,
G. Kronenberg and A. Naor,
Ramsey-nice families of graphs, European J. Combin. 72 (2018),
29--44.
-
N. Alon, M. Kumar and B. L. Volk,
Unbalancing sets and an almost quadratic lower bound for
syntactically multilinear arithmetic circuits, Proc. CCC 2018,
11:1-11:16. Also: Combinatorica 40 (2020), no. 2, 149--178.
-
N. Alon, B. Bukh and Y. Polyanskiy,
List-decodable zero-rate codes, IEEE Transactions on Information
Theory 65 (2019), 1657-1667.
-
N. Alon and N. Sherman,
Induced universal hypergraphs, SIAM J. Disc. Math.
33 (2019), no. 2, 629--642.
-
N. Alon, J. Fox and Y. Zhao,
Efficient arithmetic regularity and removal lemmas for induced
bipartite patterns, Discrete Anal. 2019, Paper No. 3, 14 pp.
-
N. Alon, Y. Azar and M. Berlin,
The price of bounded preemption, Proc. SPAA 2018, 301-310.
Also: ACM Trans. Parallel Comput. 8(1) (2021), 3:1-3:21.
-
N. Alon, S. Chechik and S. Cohen,
Deterministic Combinatorial Replacement Paths And Distance
Sensitivity Oracles, Proc. ICALP 2019, 12:1-12:14.
-
N. Alon, I. Ruzsa and J. Solymosi,
Sums, products and ratios along the edges of a graph,
Publicacions Matematiques 64(1), 2020, 143--155.
Also:
On sums and products along the edges, II,
Annales Univ. Sci. Budapest., Sec. Math. Vol. LXVI., 2023, 91--98.
-
N. Alon,
Lovàsz, vectors, graphs and codes,
In: Barany, I.,
Katona G., Sali A. (eds) Building Bridges II. Bolyai Society
Mathematical Studies, vol 28 (2020). Springer, Berlin, Heidelberg.
-
N. Alon, J. D. Cohen, P. Manurangsi, D. Reichman, I. Shinkar, T.
Wagner and A. Yu,
Multitasking capacity: hardness results and improved
constructions, SIAM J. Discrete Math. 34 (2020), no. 1, 885--903.
See also: Erratum
-
N. Alon, G. Moshkovitz and N. Solomon,
Traces of Hypergraphs, J. London Math. 100 (2019), no. 2, 498--517.
-
N. Alon, D. Hefetz, M. Krivelevich and M. Tyomkyn,
Edge-statistics on large graphs,
Combin. Probab. Comput. 29 (2020), no. 2, 163--189.
-
N. Alon, R. Livni, M. Malliaris and S. Moran,
Private PAC learning implies finite Littlestone dimension,
Proc. STOC 2019, 852-860.
-
N. Alon, I. Balla, L. Gishboliner, A. Mond and F. Mousset,
The Minrank of Random Graphs over Arbitrary Fields,
Israel J. Math. 235 (2020), no. 1, 63--77.
-
N. Alon, S. Cioaba, B. Gilbert, J. Koolen and B. McKay,
Addressing Johnson graphs, complete multipartite graphs, odd cycles
and random graphs, Experimental Mathematics 30 (2021), no. 3,
372--382.
-
N. Alon and C. Shikhelman,
Additive Approximation of Generalized Turan Questions,
Algorithmica 84 (2022), no. 2, 464--481.
-
N. Alon and C. Defant,
Isoperimetry, Stability, and Irredundance in Direct Products,
Discrete Math. 343 (2020), no. 7, 111902.
-
N. Alon, O. Ben-Eliezer, C. Shangguan and I. Tamo,
The hat guessing number of graphs, J. Combinatorial Theory, Ser. B
144 (2020), 119--149.
-
N. Alon, M. Bucic, E. Kuperwasser, T. Kalvari and T. Szabo,
List Ramsey numbers, J. Graph Theory 96 (2021), 109--128.
-
N. Alon, R. Briceno, N. Chandgotia, A. Magazinov and Y. Spinka,
Mixing properties of colorings of the Z^d lattice, Combinatorics,
Probability and Computing 30 (2021), 360--373.
-
N. Alon,
High School Coalitions
-
N. Alon, S. Moran and R. Bassily,
Limits of Private Learning with Access to Public Data,
Proc. NeurIPS 2019, 10342-10352.
-
N. Alon and R. Alweiss,
On the product dimension of clique factors,
European J. Combin. 86 (2020), 103097.
-
N. Alon and S. Assadi,
Palette sparsification beyond D+1 vertex coloring,
Proc. APPROX/RANDOM 2020: 6:1-6:22.
-
N. Alon, S. Ganguly and N. Srivastava,
High-girth near-Ramanujan graphs with localized eigenvectors,
Israel J. Math. 246 (2021), no. 1, 1--20.
-
N. Alon and G. Moshkovitz,
Limitations on regularity lemmas for clustering graphs,
Adv. in Appl. Math. 124 (2021), 102135.
-
Noga Alon, Bruno Jartoux, Chaya Keller, Shakhar Smorodinsky
and Yelena Yuditsky,
The Epsilon-t-Net Problem,
Proc. Symposium on Computational Geometry 2020: 5:1-5:15.
Also: Discrete Comput. Geom. 68 (2022), no. 2, 618--644.
-
N. Alon and A. Shraibman,
Number on the Forehead Protocols Yielding
Dense Ruzsa-Szemeredi Graphs and Hypergraphs,
Acta Mathematica Hungarica, 161(2), 2020, 488-506.
-
N. Alon,
Explicit expanders of every degree and size, Combinatorica
41 (2021), no. 4, 447--463.
-
N. Alon, A. Gonen, E. Hazan and S. Moran,
Boosting Simple Learners, Proc. STOC 2021, 481-489.
Also: TheoretiCS 2 (2023), Art. 7, 44 pp
-
N. Alon, Y. Azar and D. Vainstein,
Hierarchical Clustering: a 0.585 Revenue Approximation,
Proc. COLT 2020, 153--162.
-
N. Alon, A. Beimel, S. Moran and U. Stemmer,
Closure Properties for Private Classification and Online
Prediction, Proc. COLT 2020, 119--152.
-
N. Alon and K. Zheng,
Unitary signings and induced subgraphs of Cayley graphs of
(Z_2)^n, Advances in Combinatorics 2020, 11, 12pp.
-
Noga Alon, Shoni Gilboa and Shay Gueron,
A probabilistic variant of Sperner's theorem and of maximal
r-cover free families, Discrete Math. 343 (2020), no. 10, 112027.
-
Noga Alon, Matija Bucic and Benny Sudakov,
Large cliques and independent sets all over the place,
Proc. AMS 149 (2021), 3145-3157.
-
Noga Alon, Stijn Cambie and Ross J. Kang,
Asymmetric list sizes in bipartite graphs,
Ann. Comb. 25 (2021), no. 4, 913--933.
-
Noga Alon, Noah Kravitz and Matt Larson,
Inverse problems for minimal complements and maximal supplements,
J. Number theory 223 (2021), 307--324.
-
Noga Alon and Andrei Graur,
Efficient Splitting of Necklaces, Proc. ICALP 2021,
Article No. 14, pp. 14:1--14:17.
-
N. Alon,
Problems and results in Extremal Combinatorics - IV
-
Noga Alon, Colin Defant and Noah Kravitz,
Typical and Extremal Aspects of Friends-and-Strangers Graphs,
J. Combin. Theory Ser. B 158 (2023), part 1, 3--42.
-
Noga Alon, Asaf Nachmias and Matan Shalev,
The diameter of the uniform spanning tree of dense graphs,
Combin. Probab. Comput. 31 (2022), no. 6, 1010--1030.
-
Noga Alon, Mark Bun, Shay Moran, Maryanthe Malliaris and Roi Livni,
Private and online learnability are equivalent, J. ACM 69 Issue 4
(2022), Art. 28, 34pp.
-
Noga Alon and Ron Holzman,
Near-sunflowers and focal families, Israel J. Math. 256 (2023), 21--33.
-
Noga Alon, Omri Ben-Eliezer, Yuval Dagan, Shay Moran, Moni Naor
and Eylon Yogev,
Adversarial Laws of Large Numbers and Optimal Regret in
Online Classification, Proc. STOC 2021, 447-455.
-
Noga Alon and Michael Krivelevich,
Divisible subdivisions, J. Graph Theory 98 (2021), no. 4,
623--629.
-
Noga Alon, Ryan Alweiss, Yang P. Liu,
Anders Martinsson and Shyam Narayanan,
Arithmetic Progressions in Sumsets of Sparse Sets,
Integers 21A (2021), Ron Graham Memorial Volume, Paper No. A3, 7
pp.
-
Noga Alon,
Hitting all maximum independent sets
-
Noga Alon, Steve Hanneke, Ron Holzman and Shay Moran,
A Theory of PAC Learnability of Partial Concept Classes,
Proc. FOCS 2021, 658-671.
-
Noga Alon, Colin Defant and Noah Kravitz,
The runsort permuton, Adv. in Appl. Math. 139 (2022), Paper No.
102361, 18 pp.
-
Noga Alon and Fan Wei,
Irregular subgraphs, Comb. Probab. Comput. 32(2) (2023), 269--283.
-
Noga Alon,
Fair partitions, in: Surveys in combinatorics 2022,
1--20, London Math. Soc. Lecture Note Ser., 481,
Cambridge Univ. Press, Cambridge, 2022.
-
Noga Alon and Jeremy Chizewer,
On the Hat Guessing Number of Graphs, Discrete Math. 345 (2022),
no. 4, Paper No. 112785, 5 pp.
-
Noga Alon,
Partitioning all k-subsets into r-wise intersecting families
-
N. Alon and J. Solymosi,
Rank of matrices with entries from a multiplicative group,
Int. Math. Res. Not. IMRN 2023, no. 14, 12383–12399.
-
Noga Alon,
Implicit representation of sparse hereditary families,
Discret. Comput. Geom. 72(2): 476--482 (2024).
-
N. Alon, D. Elboim, J. Pach and G. Tardos,
Random necklaces require fewer cuts,
SIAM J. Discrete Math. 38 (2024), 1381--1408.
-
N. Alon,
Spanning trees with few non-leaves, Israel J. Math. 256 (2023), 9--20.
-
Noga Alon, Michael Krivelevich and Benny Sudakov,
Complete minors and average degree: a short proof, J. Graph
Theory 103 (2023), no. 3, 599--602.
-
Noga Alon, Benjamin Gunby, Xiaoyu He, Eran Shmaya and Eilon Solan,
Identifying the Deviator,
Annals of Applied Probability 2024, Vol. 34, No. 5, 4694--4708.
-
Anders Aamand, Noga Alon, Jakob Baek Tejs Houen and Mikkel
Thorup,
On sums of monotone random integer variables,
Electronic Communications in Probability 2022, Vol. 27, paper no.
64, 8pp.
-
Noga Alon, Dor Elboim and Allan Sly,
On a random model of forgetting,
Annals of Applied Probability 2024, Vol. 34, No. 2, 2190--2207.
-
Noga Alon, Anna Gujgiczer, Janos Korner,
Aleksa Milojevic and Gabor Simonyi,
Structured Codes of Graphs, SIAM J. Discrete Math. 37 (2023),
no. 1, 379--403.
-
Noga Alon and Fan Wei,
The limit points of the top and bottom eigenvalues of regular
graphs, Israel J. Math., to appear.
-
Noga Alon, Noah Kravitz and Kevin O'Bryant,
Counting Dope Matrices, J. Algebra 620 (2023), 502--518.
-
Noga Alon, Ehud Friedgut, Gil Kalai and Guy Kindler,
The success probability in Levine's hat problem, and independent
sets in graphs, SIAM J. Discrete Math. 37 (2023), no. 4, 2717--2729.
-
Noga Alon and Yaakov Malinovsky,
Hitting a prime in 2.43 dice rolls (on average), The American
Statistician Volume 77 Issue 3 (2023), 301-303.
-
Noga Alon, Gabriela Bourla, Ben Graham, Xiaoyu He and Noah Kravitz,
Logarithmically larger deletion codes of all distances,
IEEE Transactions on Information Theory 70 (1) (2024), 125--130.
-
Noga Alon, Michael Krivelevich and Wojciech Samotij,
Largest subgraph from a hereditary property in a random graph,
Discrete Math. 346 (2023), no. 9, Paper No. 113480, 4 pp.
-
Noga Alon and Peter Frankl,
Turan graphs with bounded matching number, J. Combinatorial Theory,
Ser. B 165 (2024), 223-229.
-
Noga Alon and Noah Kravitz,
Cats in cubes, Electron. J. Comb. 31(3) (2024).
-
Hannaneh Akrami, Noga Alon, Bhaskar Ray Chaudhury, Jugal Garg,
Kurt Mehlhorn and Ruta Mehta,
EFX: A Simpler Approach and an (Almost) Optimal Guarantee via
Rainbow Cycle Number, Proc. EC 2023, 61.
-
Noga Alon, Emil Powierski, Michael Savery,
Alex Scott and Elizabeth Wilmer,
Invertibility of digraphs and tournaments,
SIAM J. Discrete Math. 38 (2024), no. 1, 327--347.
-
Noga Alon, Olivier Bousquet, Kasper Green Larsen,
Shay Moran and Shlomo Moran,
Diagonalization Games, Amer. Math. Monthly 131 (2024), no. 10, 866--879.
-
Noga Alon,
Graph-Codes, European J. Combinatorics 116 (2024), Paper No. 103880.
-
Noga Alon, Jaroslaw Grytczuk, Andrzej P. Kisielewicz
and Krzysztof Przeslawski,
New bounds on the number of neighborly boxes in R^d, European J.
Comb. 114 (2023), Paper No. 103797, 15pp.
-
Noga Alon, Matija Bucic and Lisa Sauermann,
Unit and distinct distances in typical norms,
Geometric and Functional Analysis, to appear.
-
Noga Alon, Anurag Bishnoi, Shagnik Das and Alessandro Neri,
Strong blocking sets and minimal codes from expander graphs,
Trans. Amer. Math. Soc. 377 (2024), 5389-–5410.
-
Noga Alon, Shay Moran, Hilla Schefler and Amir Yehudayoff,
A Unified Characterization of Private Learnability via Graph Theory,
Proc. COLT 2024 247 (2024), 94--129.
-
Noga Alon, Dmitrii Avdiukhin, Dor Elboim, Orr Fischer
and Grigory Yaroslavtsev,
Optimal Sample Complexity of Contrastive Learning,
Proc. ICLR 2024.
-
Noga Alon, Allan Gronlund, Soren Fuglede Jorgensen
and Kasper Green Larsen,
Sublinear Time Shortest Path in Expander Graphs,
Proc. MFCS 2024, LIPIcs Volume 306 (2024), pp. 8:1--8:13.
-
Noga Alon,
On bipartite coverings of graphs and multigraphs
-
Noga Alon, Colin Defant, Noah Kravitz and Daniel Zhu,
Ordering candidates via vantage points
-
Noga Alon,
Connectivity Graph-Codes, Random Structures and Algorithms 65 (2024),
no. 3, 451--459.
-
Noga Alon, Matija Bucic, Micha Christoph and Michael Krivelevich,
The power of many colours, Forum of Mathematics, Sigma, in press.
-
Noga Alon, Matija Bucic, Lisa Sauermann, Dmitrii Zakharov and Or Zamir,
Essentially tight bounds for rainbow cycles in proper edge-colourings
-
Janos Pach, Micha Sharir, Noga Alon and Andreas Holmsen,
Eli Goodman (1933–2021) and Ricky Pollack (1935–2018),
Notices Amer. Math. Soc. 71 (2024), no. 8, 1044–1053.
-
N. Alon, J. Balogh and V. Potapov,
Partitioning the hypercube into smaller hypercubes, Illinois J. Math.,
to appear.
-
N. Alon, N. Dodson, C. Jackson, R. McCarty, R. Nenadov and L. Southern,
Universality for graphs with bounded density
-
N. Alon,
Erasure list-decodable codes and Turan hypercube problems,
Finite Fields Appl. 100 (2024), Paper No. 102513.
-
Noga Alon and Or Zamir,
Sumsets in the hypercube
-
Noga Alon, Zhihan Jin and Benny Sudakov,
The Helly number of Hamming balls and related problems
-
N. Alon, C. Defant and N. Kravitz,
Rainbow Stackings of Random Edge-Colorings
-
N. Alon,
Triangle-free graphs of diameter two
-
N. Alon,
Blocking partial designs and block-compatible sequences
-
Noga Alon, Varun Sivashankar and Daniel Zhu,
Maximum shattering
-
Noga Alon, Maria Axenovich and John Goldwasser,
On Hypercube Statistics
-
Noga Alon,
Problems and results in Extremal combinatorics - V
redesigned by barak soreq