2009 |
380 | EE | Noga Alon,
Uriel Feige:
On the power of two, three and four probes.
SODA 2009: 346-354 |
379 | EE | Noga Alon,
Béla Bollobás:
Introduction.
Combinatorics, Probability & Computing 18(1-2): 1 (2009) |
378 | EE | Noga Alon:
Perturbed Identity Matrices Have High Rank: Proof and Applications.
Combinatorics, Probability & Computing 18(1-2): 3-15 (2009) |
377 | EE | Noga Alon,
Rani Hod:
Optimal Monotone Encodings.
IEEE Transactions on Information Theory 55(3): 1343-1353 (2009) |
376 | EE | Noga Alon,
Alexandr V. Kostochka:
Induced subgraphs with distinct sizes.
Random Struct. Algorithms 34(1): 45-53 (2009) |
2008 |
375 | EE | Noga Alon,
Ido Ben-Eliezer,
Michael Krivelevich:
Small Sample Spaces Cannot Fool Low Degree Polynomials.
APPROX-RANDOM 2008: 266-275 |
374 | EE | Noga Alon,
Asaf Nussboim:
k-Wise Independent Random Graphs.
FOCS 2008: 813-822 |
373 | EE | Noga Alon,
Eyal Lubetzky,
Uri Stav,
Amit Weinstein,
Avinatan Hassidim:
Broadcasting with Side Information.
FOCS 2008: 823-832 |
372 | EE | Noga Alon,
Rani Hod:
Optimal Monotone Encodings.
ICALP (1) 2008: 258-270 |
371 | EE | Noga Alon,
Phuong Dao,
Iman Hajirasouliha,
Fereydoun Hormozdiari,
Süleyman Cenk Sahinalp:
Biomolecular network motif counting and discovery by color coding.
ISMB 2008: 241-249 |
370 | EE | Noga Alon,
Haim Kaplan,
Gabriel Nivasch,
Micha Sharir,
Shakhar Smorodinsky:
Weak ε-nets and interval chains.
SODA 2008: 1194-1203 |
369 | EE | Noga Alon,
Michael R. Capalbo:
Optimal universal graphs with deterministic embedding.
SODA 2008: 373-378 |
368 | EE | Noga Alon,
Chen Avin,
Michal Koucký,
Gady Kozma,
Zvi Lotker,
Mark R. Tuttle:
Many random walks are faster than one.
SPAA 2008: 119-128 |
367 | EE | Noga Alon,
Robert Berke,
Kevin Buchin,
Maike Buchin,
Péter Csorba,
Saswata Shannigrahi,
Bettina Speckmann,
Philipp Zumstein:
Polychromatic colorings of plane graphs.
Symposium on Computational Geometry 2008: 338-345 |
366 | EE | Noga Alon,
Dan Halperin,
Oren Nechushtan,
Micha Sharir:
The complexity of the outer face in arrangements of random segments.
Symposium on Computational Geometry 2008: 69-78 |
365 | EE | Noga Alon,
Raphael Yuster,
Uri Zwick:
Color Coding.
Encyclopedia of Algorithms 2008 |
364 | EE | Noga Alon,
Mihai Badoiu,
Erik D. Demaine,
Martin Farach-Colton,
Mohammad Taghi Hajiaghayi,
Anastasios Sidiropoulos:
Ordinal embeddings of minimum relaxation: General properties, trees, and ultrametrics.
ACM Transactions on Algorithms 4(4): (2008) |
363 | EE | Noga Alon,
Fedor V. Fomin,
Gregory Gutin,
Michael Krivelevich,
Saket Saurabh:
Spanning directed trees with many leaves
CoRR abs/0803.0701: (2008) |
362 | EE | Noga Alon,
Yossi Azar,
Shai Gutner:
Admission Control to Minimize Rejections and Online Set Cover with Repetitions
CoRR abs/0803.2842: (2008) |
361 | EE | Noga Alon,
Shai Gutner:
Balanced Families of Perfect Hash Functions and Their Applications
CoRR abs/0805.4300: (2008) |
360 | EE | Noga Alon,
Avinatan Hassidim,
Eyal Lubetzky,
Uri Stav,
Amit Weinstein:
Broadcasting with side information
CoRR abs/0806.3246: (2008) |
359 | EE | Noga Alon,
Shai Gutner:
Linear Time Algorithms for Finding a Dominating Set of Fixed Size in Degenerated Graphs
CoRR abs/0806.4735: (2008) |
358 | EE | Noga Alon,
Sonny Ben-Shimon,
Michael Krivelevich:
A note on regular Ramsey graphs
CoRR abs/0812.2386: (2008) |
357 | EE | Noga Alon,
Asaf Shapira:
A separation theorem in property testing.
Combinatorica 28(3): 261-281 (2008) |
356 | EE | Noga Alon,
Oded Schwartz,
Asaf Shapira:
An Elementary Construction of Constant-Degree Expanders.
Combinatorics, Probability & Computing 17(3): 319-327 (2008) |
355 | EE | Noga Alon:
Problems and results in extremal combinatorics - II.
Discrete Mathematics 308(19): 4460-4472 (2008) |
354 | EE | Noga Alon,
Adi Pinchasi,
Rom Pinchasi:
An isoperimetric inequality in the universal cover of the punctured plane.
Discrete Mathematics 308(23): 5691-5701 (2008) |
353 | EE | Noga Alon,
Jaroslaw Grytczuk:
Breaking the rhythm on graphs.
Discrete Mathematics 308(8): 1375-1380 (2008) |
352 | EE | Noga Alon,
Eli Berger:
The Grothendieck constant of random and pseudo-random graphs.
Discrete Optimization 5(2): 323-327 (2008) |
351 | EE | Noga Alon,
Rina Panigrahy,
Sergey Yekhanin:
Deterministic Approximation Algorithms for the Nearest Codeword Problem.
Electronic Colloquium on Computational Complexity (ECCC) 15(065): (2008) |
350 | EE | Noga Alon,
Shai Gutner:
Kernels for the Dominating Set Problem on Graphs with an Excluded Minor.
Electronic Colloquium on Computational Complexity (ECCC) 15(066): (2008) |
349 | EE | Noga Alon,
Shakhar Smorodinsky:
Conflict-Free colorings of Shallow Discs.
Int. J. Comput. Geometry Appl. 18(6): 599-604 (2008) |
348 | EE | Noga Alon,
Haim Kaplan,
Gabriel Nivasch,
Micha Sharir,
Shakhar Smorodinsky:
Weak &epsis;-nets and interval chains.
J. ACM 55(6): (2008) |
347 | EE | Noga Alon,
Uri Stav:
The maximum edit distance from hereditary graph properties.
J. Comb. Theory, Ser. B 98(4): 672-697 (2008) |
346 | EE | Noga Alon,
Uri Stav:
What is the furthest graph from a hereditary property?
Random Struct. Algorithms 33(1): 87-104 (2008) |
345 | EE | Noga Alon,
Asaf Shapira:
A Characterization of the (Natural) Graph Properties Testable with One-Sided Error.
SIAM J. Comput. 37(6): 1703-1727 (2008) |
344 | EE | Noga Alon,
Asaf Shapira:
Every Monotone Graph Property Is Testable.
SIAM J. Comput. 38(2): 505-522 (2008) |
343 | EE | Noga Alon,
Tali Kaufman,
Michael Krivelevich,
Dana Ron:
Testing Triangle-Freeness in General Graphs.
SIAM J. Discrete Math. 22(2): 786-819 (2008) |
2007 |
342 | EE | Noga Alon,
Shai Gutner:
Linear Time Algorithms for Finding a Dominating Set of Fixed Size in Degenerated Graphs.
COCOON 2007: 394-405 |
341 | EE | Noga Alon,
Asaf Shapira,
Uri Stav:
Can a Graph Have Distinct Regular Partitions?
COCOON 2007: 428-438 |
340 | EE | Noga Alon,
Raphael 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 |
339 | EE | Noga Alon,
Michael R. Capalbo:
Finding Disjoint Paths in Expanders Deterministically and Online.
FOCS 2007: 518-524 |
338 | EE | Noga Alon,
Fedor V. Fomin,
Gregory Gutin,
Michael Krivelevich,
Saket Saurabh:
Better Algorithms and Bounds for Directed Maximum Leaf Problems.
FSTTCS 2007: 316-327 |
337 | EE | Noga Alon,
Fedor V. Fomin,
Gregory Gutin,
Michael Krivelevich,
Saket Saurabh:
Parameterized Algorithms for Directed Maximum Leaf Problems.
ICALP 2007: 352-362 |
336 | EE | Noga Alon,
Shai Gutner:
Balanced Families of Perfect Hash Functions and Their Applications.
ICALP 2007: 435-446 |
335 | EE | Noga Alon,
Amin Coja-Oghlan,
Hiêp Hàn,
Mihyun Kang,
Vojtech Rödl,
Mathias Schacht:
Quasi-randomness and Algorithmic Regularity for Graphs with General Degree Distributions.
ICALP 2007: 789-800 |
334 | EE | Noga Alon,
Oded Schwartz,
Asaf Shapira:
An elementary construction of constant-degree expanders.
SODA 2007: 454-458 |
333 | EE | Noga Alon,
Alexandr Andoni,
Tali Kaufman,
Kevin Matulef,
Ronitt Rubinfeld,
Ning Xie:
Testing k-wise and almost k-wise independence.
STOC 2007: 496-505 |
332 | EE | Amit Agarwal,
Noga Alon,
Moses Charikar:
Improved approximation for directed cut problems.
STOC 2007: 671-680 |
331 | EE | Noga Alon,
Venkatesan Guruswami,
Tali Kaufman,
Madhu Sudan:
Guessing secrets efficiently via list decoding.
ACM Transactions on Algorithms 3(4): (2007) |
330 | EE | Noga Alon,
Fedor V. Fomin,
Gregory Gutin,
Michael Krivelevich,
Saket Saurabh:
Better Algorithms and Bounds for Directed Maximum Leaf Problems
CoRR abs/0707.1095: (2007) |
329 | EE | Noga Alon,
Fedor V. Fomin,
Gregory Gutin,
Michael Krivelevich,
Saket Saurabh:
Parameterized Algorithms for Directed Maximum Leaf Problems
CoRR abs/cs/0702049: (2007) |
328 | EE | Noga Alon,
Eyal Lubetzky:
Codes And Xor Graph Products.
Combinatorica 27(1): 13-33 (2007) |
327 | EE | Noga Alon,
Vera Asodi:
Edge Colouring with Delays.
Combinatorics, Probability & Computing 16(2): 173-191 (2007) |
326 | EE | Noga Alon,
Ilan Newman,
Alexander Shen,
Gábor Tardos,
Nikolai K. Vereshchagin:
Partitioning multi-dimensional sets in a small number of "uniform" parts.
Eur. J. Comb. 28(1): 134-144 (2007) |
325 | EE | Noga Alon,
Vera Asodi:
Tracing Many Users With Almost No Rate Penalty.
IEEE Transactions on Information Theory 53(1): 437-439 (2007) |
324 | EE | Noga Alon,
Haim Kaplan,
Michael Krivelevich,
Dahlia Malkhi,
Julien P. Stern:
Addendum to "Scalable secure storage when half the system is faulty" [Inform. Comput 174 (2)(2002) 203-213].
Inf. Comput. 205(7): 1114-1116 (2007) |
323 | EE | Nir Ailon,
Noga Alon:
Hardness of fully dense problems.
Inf. Comput. 205(8): 1117-1129 (2007) |
322 | EE | Noga Alon,
Eyal Lubetzky:
Independent sets in tensor graph powers.
Journal of Graph Theory 54(1): 73-87 (2007) |
321 | EE | Noga Alon,
Béla Bollobás,
András Gyárfás,
Jenö Lehel,
Alex D. Scott:
Maximum directed cuts in acyclic digraphs.
Journal of Graph Theory 55(1): 1-13 (2007) |
320 | EE | Noga Alon,
Benny Sudakov:
On graphs with subgraphs having large independence numbers.
Journal of Graph Theory 56(2): 149-157 (2007) |
319 | EE | Noga Alon,
Michael R. Capalbo:
Sparse universal graphs for bounded-degree graphs.
Random Struct. Algorithms 31(2): 123-133 (2007) |
318 | EE | Noga Alon,
Toshiya Itoh,
Tatsuya Nagatani:
On (epsilon, k)-min-wise independent permutations.
Random Struct. Algorithms 31(3): 384-389 (2007) |
317 | EE | Noga Alon,
Eldar Fischer,
Ilan Newman:
Efficient Testing of Bipartite Graphs for Forbidden Induced Subgraphs.
SIAM J. Comput. 37(3): 959-976 (2007) |
316 | EE | Noga Alon,
Anja Krech,
Tibor Szabó:
Tur[a-acute]n's Theorem in the Hypercube.
SIAM J. Discrete Math. 21(1): 66-72 (2007) |
315 | EE | Noga Alon,
Eyal Lubetzky:
Graph Powers, Delsarte, Hoffman, Ramsey, and Shannon.
SIAM J. Discrete Math. 21(2): 329-348 (2007) |
314 | EE | Noga Alon,
Andrzej Lingas,
Martin Wahlen:
Approximating the maximum clique minor and some subgraph homeomorphism problems.
Theor. Comput. Sci. 374(1-3): 149-158 (2007) |
2006 |
313 | EE | Noga Alon,
Asaf Shapira,
Benny Sudakov:
Additive Approximation for Edge-Deletion Problems (Abstract).
ICALP (1) 2006: 1-2 |
312 | EE | Noga Alon,
Tali Kaufman,
Michael Krivelevich,
Dana Ron:
Testing triangle-freeness in general graphs.
SODA 2006: 279-288 |
311 | EE | Noga Alon,
Baruch Awerbuch,
Yossi Azar,
Boaz Patt-Shamir:
Tell me who I am: an interactive recommendation system.
SPAA 2006: 1-10 |
310 | EE | Noga Alon,
Eldar Fischer,
Ilan Newman,
Asaf Shapira:
A combinatorial characterization of the testable graph properties: it's all about regularity.
STOC 2006: 251-260 |
309 | EE | Noga Alon,
Shakhar Smorodinsky:
Conflict-free colorings of shallow discs.
Symposium on Computational Geometry 2006: 41-43 |
308 | EE | Noga Alon,
Dana Moshkovitz,
Shmuel Safra:
Algorithmic construction of sets for k-restrictions.
ACM Transactions on Algorithms 2(2): 153-177 (2006) |
307 | EE | Noga Alon,
Baruch Awerbuch,
Yossi Azar,
Niv Buchbinder,
Joseph Naor:
A general approach to online network optimization problems.
ACM Transactions on Algorithms 2(4): 640-660 (2006) |
306 | EE | Noga Alon,
Eyal Lubetzky:
The Shannon capacity of a graph and the independence numbers of its powers
CoRR abs/cs/0608021: (2006) |
305 | EE | Noga Alon,
Raphael Yuster:
The Number Of Orientations Having No Fixed Tournament.
Combinatorica 26(1): 1-16 (2006) |
304 | EE | Noga Alon,
Asaf Shapira:
On An Extremal Hypergraph Problem Of Brown, Erdös And Sós.
Combinatorica 26(6): 627-645 (2006) |
303 | EE | Noga Alon,
Yoshiharu Kohayakawa,
Christian Mauduit,
C. G. Moreira,
Vojtech Rödl:
Measures of Pseudorandomness for Finite Sequences: Minimal Values.
Combinatorics, Probability & Computing 15(1-2): 1-29 (2006) |
302 | EE | Noga Alon:
Feasible Schedules for Rotating Transmissions.
Combinatorics, Probability & Computing 15(5): 783-787 (2006) |
301 | EE | Noga Alon,
Asaf Shapira:
A Characterization of Easily Testable Induced Subgraphs.
Combinatorics, Probability & Computing 15(6): 791-805 (2006) |
300 | EE | Noga Alon:
Splitting digraphs.
Combinatorics, Probability & Computing 15(6): 933-937 (2006) |
299 | EE | Noga Alon,
Fan R. K. Chung:
Explicit construction of linear sized tolerant networks.
Discrete Mathematics 306(10-11): 1068-1071 (2006) |
298 | EE | Noga Alon,
Benny Sudakov:
H-Free Graphs of Large Minimum Degree.
Electr. J. Comb. 13(1): (2006) |
297 | EE | Noga Alon,
Oded Schwartz,
Asaf Shapira:
An Elementary Construction of Constant-Degree Expanders.
Electronic Colloquium on Computational Complexity (ECCC) 13(119): (2006) |
296 | EE | Noga Alon,
Vera Asodi:
Tracing a single user.
Eur. J. Comb. 27(8): 1227-1234 (2006) |
295 | EE | Noga Alon,
Eyal Lubetzky:
The Shannon capacity of a graph and the independence numbers of its powers.
IEEE Transactions on Information Theory 52(5): 2172-2176 (2006) |
294 | EE | Noga Alon,
Graham Brightwell,
Hal A. Kierstead,
Alexandr V. Kostochka,
Peter Winkler:
Dominating sets in k-majority tournaments.
J. Comb. Theory, Ser. B 96(3): 374-387 (2006) |
293 | EE | Noga Alon,
Vera Asodi,
Charles Cantor,
Simon Kasif,
John Rachlin:
Multi-Node Graphs: A Framework for Multiplexed Biological Assays.
Journal of Computational Biology 13(10): 1659-1672 (2006) |
292 | EE | Noga Alon,
Rados Radoicic,
Benny Sudakov,
Jan Vondrák:
A Ramsey-type result for the hypercube.
Journal of Graph Theory 53(3): 196-208 (2006) |
291 | EE | Noga Alon,
Eitan Bachmat:
Regular graphs whose subgraphs tend to be acyclic.
Random Struct. Algorithms 29(3): 324-337 (2006) |
290 | EE | Noga Alon,
Assaf Naor:
Approximating the Cut-Norm via Grothendieck's Inequality.
SIAM J. Comput. 35(4): 787-803 (2006) |
289 | EE | Noga Alon:
Ranking Tournaments.
SIAM J. Discrete Math. 20(1): 137-142 (2006) |
2005 |
288 | EE | Noga Alon,
Asaf Shapira,
Benny Sudakov:
Additive Approximation for Edge-Deletion Problems.
FOCS 2005: 419-428 |
287 | EE | Noga Alon,
Asaf Shapira:
A Characterization of the (natural) Graph Properties Testable with One-Sided Error.
FOCS 2005: 429-438 |
286 | EE | Noga Alon,
Nick G. Duffield,
Carsten Lund,
Mikkel Thorup:
Estimating arbitrary subset sums with few probes.
PODS 2005: 317-325 |
285 | EE | Noga Alon,
Mihai Badoiu,
Erik D. Demaine,
Martin Farach-Colton,
Mohammad Taghi Hajiaghayi,
Anastasios Sidiropoulos:
Ordinal embeddings of minimum relaxation: general properties, trees, and ultrametrics.
SODA 2005: 650-659 |
284 | EE | Noga Alon,
Asaf Shapira:
Linear equations, arithmetic progressions and hypergraph property testing.
SODA 2005: 708-717 |
283 | EE | Noga Alon,
Yossi Azar,
Shai Gutner:
Admission control to minimize rejections and online set cover with repetitions.
SPAA 2005: 238-244 |
282 | EE | Noga Alon,
Asaf Shapira:
Every monotone graph property is testable.
STOC 2005: 128-137 |
281 | EE | Noga Alon,
Konstantin Makarychev,
Yury Makarychev,
Assaf Naor:
Quadratic forms on graphs.
STOC 2005: 486-493 |
280 | EE | Noga Alon,
Vojtech Rödl:
Sharp Bounds For Some Multicolor Ramsey Numbers.
Combinatorica 25(2): 125-141 (2005) |
279 | EE | Noga Alon,
Michael Merritt,
Omer Reingold,
Gadi Taubenfeld,
Rebecca N. Wright:
Tight bounds for shared memory systems accessed by Byzantine processes.
Distributed Computing 18(2): 99-109 (2005) |
278 | EE | Noga Alon,
Michael Krivelevich,
Joel Spencer,
Tibor Szabó:
Discrepancy Games.
Electr. J. Comb. 12: (2005) |
277 | EE | Asaf Shapira,
Noga Alon:
Homomorphisms in Graph Property Testing - A Survey
Electronic Colloquium on Computational Complexity (ECCC)(085): (2005) |
276 | EE | Noga Alon,
Ilan Newman,
Alexander Shen,
Gábor Tardos,
Nikolai K. Vereshchagin:
Partitioning multi-dimensional sets in a small number of ``uniform'' parts
Electronic Colloquium on Computational Complexity (ECCC)(095): (2005) |
275 | EE | Noga Alon,
Jaroslaw Grytczuk:
Nonrepetitive colorings of graphs.
Electronic Notes in Discrete Mathematics 22: 353-355 (2005) |
274 | EE | Noga Alon,
Raphael Yuster:
On a Hypergraph Matching Problem.
Graphs and Combinatorics 21(4): 377-384 (2005) |
273 | EE | Noga Alon,
Tali Kaufman,
Michael Krivelevich,
Simon Litsyn,
Dana Ron:
Testing Reed-Muller codes.
IEEE Transactions on Information Theory 51(11): 4032-4039 (2005) |
272 | EE | Noga Alon,
János Pach,
Rom Pinchasi,
Rados Radoicic,
Micha Sharir:
Crossing patterns of semi-algebraic sets.
J. Comb. Theory, Ser. A 111(2): 310-326 (2005) |
271 | EE | Noga Alon,
Vera Asodi:
Learning a Hidden Subgraph.
SIAM J. Discrete Math. 18(4): 697-712 (2005) |
270 | EE | Noga Alon,
Asaf Shapira:
Linear Equations, Arithmetic Progressions and Hypergraph Property Testing.
Theory of Computing 1(1): 177-216 (2005) |
2004 |
269 | EE | Noga Alon,
Vera Asodi:
Edge Coloring with Delays.
APPROX-RANDOM 2004: 237-248 |
268 | EE | Noga Alon,
Vera Asodi:
Learning a Hidden Subgraph.
ICALP 2004: 110-121 |
267 | EE | Nathan Srebro,
Noga Alon,
Tommi Jaakkola:
Generalization Error Bounds for Collaborative Prediction with Low-Rank Matrices.
NIPS 2004 |
266 | EE | Noga Alon,
Baruch Awerbuch,
Yossi Azar,
Niv Buchbinder,
Joseph Naor:
A general approach to online network optimization problems.
SODA 2004: 577-586 |
265 | EE | Noga Alon,
Asaf Shapira:
A characterization of easily testable induced subgraphs.
SODA 2004: 942-951 |
264 | EE | Noga Alon,
Assaf Naor:
Approximating the cut-norm via Grothendieck's inequality.
STOC 2004: 72-80 |
263 | EE | Noga Alon,
Uri Stav:
New Bounds on Parent-Identifying Codes: The Case of Multiple Parents.
Combinatorics, Probability & Computing 37(6): 795-807 (2004) |
262 | EE | Noga Alon,
Gregory Gutin,
Michael Krivelevich:
Algorithms with large domination ratio.
J. Algorithms 50(1): 118-131 (2004) |
261 | EE | Noga Alon,
Asaf Shapira:
Testing subgraphs in directed graphs.
J. Comput. Syst. Sci. 69(3): 354-382 (2004) |
260 | EE | Noga Alon,
Gil Kaplan,
Arieh Lev,
Yehuda Roditty,
Raphael Yuster:
Dense graphs are antimagic.
Journal of Graph Theory 47(4): 297-309 (2004) |
259 | EE | Noga Alon,
Richard Beigel,
Simon Kasif,
Steven Rudich,
Benny Sudakov:
Learning a Hidden Matching.
SIAM J. Comput. 33(2): 487-501 (2004) |
2003 |
258 | EE | Noga Alon,
Tali Kaufman,
Michael Krivelevich,
Simon Litsyn,
Dana Ron:
Testing Low-Degree Polynomials over GF(2(.
RANDOM-APPROX 2003: 188-199 |
257 | EE | Noga Alon,
Michael R. Capalbo:
Smaller explicit superconcentrators.
SODA 2003: 340-346 |
256 | EE | Noga Alon,
Baruch Awerbuch,
Yossi Azar,
Niv Buchbinder,
Joseph Naor:
The online set cover problem.
STOC 2003: 100-105 |
255 | EE | Noga Alon,
Asaf Shapira:
Testing subgraphs in directed graphs.
STOC 2003: 700-709 |
254 | EE | Noga Alon,
Tova Milo,
Frank Neven,
Dan Suciu,
Victor Vianu:
Typechecking XML views of relational databases.
ACM Trans. Comput. Log. 4(3): 315-354 (2003) |
253 | | Noga Alon,
Michael Krivelevich,
Benny Sudakov:
Tura'n Numbers of Bipartite Graphs and Related Ramsey-Type Questions.
Combinatorics, Probability & Computing 12(5-6): 477-494 (2003) |
252 | EE | Noga Alon,
Guillaume Fertin,
Arthur L. Liestman,
Thomas C. Shermer,
Ladislav Stacho:
Factor d-domatic colorings of graphs.
Discrete Mathematics 262(1-3): 17-25 (2003) |
251 | EE | Noga Alon:
Problems and results in extremal combinatorics--I.
Discrete Mathematics 273(1-3): 31-53 (2003) |
250 | EE | Noga Alon,
Simon Litsyn,
Raphael Yuster:
A Coding Theory Bound and Zero-Sum Square Matrices.
Graphs and Combinatorics 19(4): 449-457 (2003) |
249 | EE | Noga Alon:
A simple algorithm for edge-coloring bipartite multigraphs.
Inf. Process. Lett. 85(6): 301-302 (2003) |
248 | EE | Noga Alon,
Oded Goldreich,
Yishay Mansour:
Almost k-wise independence versus k-wise independence.
Inf. Process. Lett. 88(3): 107-110 (2003) |
247 | | Noga Alon,
Michael R. Capalbo:
Smaller Explicit Superconcentrators.
Internet Mathematics 1(2): (2003) |
246 | EE | Noga Alon,
Asaf Shapira:
Testing satisfiability.
J. Algorithms 47(2): 87-103 (2003) |
245 | EE | Noga Alon,
Gérard D. Cohen,
Michael Krivelevich,
Simon Litsyn:
Generalized hashing and parent-identifying codes.
J. Comb. Theory, Ser. A 104(1): 207-215 (2003) |
244 | EE | Noga Alon,
Guoli Ding,
Bogdan Oporowski,
Dirk Vertigan:
Partitioning into graphs with only small components.
J. Comb. Theory, Ser. B 87(2): 231-243 (2003) |
243 | EE | Noga Alon,
Béla Bollobás,
Michael Krivelevich,
Benny Sudakov:
Maximum cuts and judicious partitions in graphs without short cycles.
J. Comb. Theory, Ser. B 88(2): 329-346 (2003) |
242 | EE | Noga Alon,
Tova Milo,
Frank Neven,
Dan Suciu,
Victor Vianu:
XML with data values: typechecking revisited.
J. Comput. Syst. Sci. 66(4): 688-727 (2003) |
241 | EE | Noga Alon,
Wenceslas Fernandez de la Vega,
Ravi Kannan,
Marek Karpinski:
Random sampling and approximation of MAX-CSPs.
J. Comput. Syst. Sci. 67(2): 212-243 (2003) |
240 | EE | Noga Alon,
Tao Jiang,
Zevi Miller,
Dan Pritikin:
Properly colored subgraphs and rainbow subgraphs in edge-colorings with local constraints.
Random Struct. Algorithms 23(4): 409-433 (2003) |
239 | EE | Noga Alon,
Seannie Dar,
Michal Parnas,
Dana Ron:
Testing of Clustering.
SIAM J. Discrete Math. 16(3): 393-417 (2003) |
2002 |
238 | EE | Noga Alon,
Richard Beigel,
Simon Kasif,
Steven Rudich,
Benny Sudakov:
Learning a Hidden Matching.
FOCS 2002: 197- |
237 | EE | Noga Alon,
Michael R. Capalbo:
Explicit Unique-Neighbor Expanders.
FOCS 2002: 73- |
236 | EE | Noga Alon,
Venkatesan Guruswami,
Tali Kaufman,
Madhu Sudan:
Guessing secrets efficiently via list decoding.
SODA 2002: 254-262 |
235 | EE | Noga Alon,
Asaf Shapira:
Testing satisfiability.
SODA 2002: 645-654 |
234 | EE | Noga Alon,
Wenceslas Fernandez de la Vega,
Ravi Kannan,
Marek Karpinski:
Random sampling and approximation of MAX-CSP problems.
STOC 2002: 232-239 |
233 | EE | Noga Alon,
Ayal Zaks:
Algorithmic Aspects of Acyclic Edge Colorings.
Algorithmica 32(4): 611-614 (2002) |
232 | | Noga Alon,
Bojan Mohar:
The Chromatic Number Of Graph Powers.
Combinatorics, Probability & Computing 11(1): (2002) |
231 | EE | Noga Alon,
József Balogh,
Béla Bollobás,
Tamás Szabó:
Game domination number.
Discrete Mathematics 256(1-2): 23-33 (2002) |
230 | EE | Noga Alon:
Covering a hypergraph of subgraphs.
Discrete Mathematics 257(2-3): 249-254 (2002) |
229 | EE | Noga Alon,
Tom Bohman,
Ron Holzman,
Daniel J. Kleitman:
On partitions of discrete boxes.
Discrete Mathematics 257(2-3): 255-258 (2002) |
228 | EE | Noga Alon,
Oded Goldreich,
Yishay Mansour:
Almost k-wise independence versus k-wise independence
Electronic Colloquium on Computational Complexity (ECCC)(048): (2002) |
227 | EE | Noga Alon,
Shlomo Hoory,
Nathan Linial:
The Moore Bound for Irregular Graphs.
Graphs and Combinatorics 18(1): 53-57 (2002) |
226 | EE | Noga Alon,
Haim Kaplan,
Michael Krivelevich,
Dahlia Malkhi,
Julien P. Stern:
Scalable Secure Storage When Half the System Is Faulty.
Inf. Comput. 174(2): 203-213 (2002) |
225 | EE | Noga Alon,
Phillip B. Gibbons,
Yossi Matias,
Mario Szegedy:
Tracking Join and Self-Join Sizes in Limited Storage.
J. Comput. Syst. Sci. 64(3): 719-747 (2002) |
224 | EE | Noga Alon,
Benjamin Doerr,
Tomasz Luczak,
Tomasz Schoen:
On the discrepancy of combinatorial rectangles.
Random Struct. Algorithms 21(3-4): 205-215 (2002) |
223 | EE | Noga Alon,
Jaroslaw Grytczuk,
Mariusz Haluszczak,
Oliver Riordan:
Nonrepetitive colorings of graphs.
Random Struct. Algorithms 21(3-4): 336-346 (2002) |
222 | EE | Noga Alon:
Testing subgraphs in large graphs.
Random Struct. Algorithms 21(3-4): 359-370 (2002) |
221 | EE | Noga Alon,
Michael Krivelevich:
Testing k-colorability.
SIAM J. Discrete Math. 15(2): 211-227 (2002) |
2001 |
220 | | Noga Alon:
Testing Subgraphs in Large Graphs.
FOCS 2001: 434-441 |
219 | | Noga Alon,
Alexander Lubotzky,
Avi Wigderson:
Semi-Direct Product in Groups and Zig-Zag Product in Graphs: Connections and Applications.
FOCS 2001: 630-637 |
218 | EE | Noga Alon,
Richard Beigel:
Lower Bounds for Approximations by Low Degree Polynomials Over Zm.
IEEE Conference on Computational Complexity 2001: 184-187 |
217 | | Noga Alon,
Tova Milo,
Frank Neven,
Dan Suciu,
Victor Vianu:
Typechecking XML Views of Relational Databases.
LICS 2001: 421-430 |
216 | EE | Noga Alon,
Tova Milo,
Frank Neven,
Dan Suciu,
Victor Vianu:
XML with Data Values: Typechecking Revisited.
PODS 2001 |
215 | EE | Noga Alon,
Michael R. Capalbo,
Yoshiharu Kohayakawa,
Vojtech Rödl,
Andrzej Rucinski,
Endre Szemerédi:
Near-optimum Universal Graphs for Graphs with Bounded Degrees.
RANDOM-APPROX 2001: 170-180 |
214 | EE | Richard Beigel,
Noga Alon,
Simon Kasif,
Mehmet Serkan Apaydin,
Lance Fortnow:
An optimal procedure for gap closing in whole genome shotgun sequencing.
RECOMB 2001: 22-30 |
213 | EE | Noga Alon,
Benny Sudakov,
Uri Zwick:
Constructing worst case instances for semidefinite programming based approximation algorithms.
SODA 2001: 92-100 |
212 | EE | Noga Alon,
János Pach,
József Solymosi:
Ramsey-type Theorems with Forbidden Subgraphs.
Combinatorica 21(2): 155-170 (2001) |
211 | EE | Noga Alon,
Hagit Last,
Rom Pinchasi,
Micha Sharir:
On the Complexity of Arrangements of Circles in the Plane.
Discrete & Computational Geometry 26(4): 465-492 (2001) |
210 | EE | Noga Alon,
Wenceslas Fernandez de la Vega,
Ravi Kannan,
Marek Karpinski:
Random Sampling and Approximation of MAX-CSP Problems
Electronic Colloquium on Computational Complexity (ECCC)(100): (2001) |
209 | EE | Noga Alon,
Vanessa Teague,
Nicholas C. Wormald:
Linear Arboricity and Linear k-Arboricity of Regular Graphs.
Graphs and Combinatorics 17(1): 11-16 (2001) |
208 | EE | Noga Alon,
László Lovász:
Unextendible Product Bases.
J. Comb. Theory, Ser. A 95(1): 169-179 (2001) |
207 | EE | Noga Alon,
Eldar Fischer,
Mario Szegedy:
Parent-Identifying Codes.
J. Comb. Theory, Ser. A 95(2): 349-359 (2001) |
206 | | Ilan Adler,
Noga Alon,
Sheldon M. Ross:
On the maximum number of Hamiltonian paths in tournaments.
Random Struct. Algorithms 18(3): 291-296 (2001) |
205 | EE | Noga Alon,
Charles J. Colbourn,
Alan C. H. Ling,
Martin Tompa:
Equireplicate Balanced Binary Codes for Oligo Arrays.
SIAM J. Discrete Math. 14(4): 481-497 (2001) |
204 | EE | Noga Alon,
Benny Sudakov,
Uri Zwick:
Constructing Worst Case Instances for Semidefinite Programming Based Approximation Algorithms.
SIAM J. Discrete Math. 15(1): 58-72 (2001) |
2000 |
203 | | Noga Alon,
Michael R. Capalbo,
Yoshiharu Kohayakawa,
Vojtech Rödl,
Andrzej Rucinski,
Endre Szemerédi:
Universality and Tolerance.
FOCS 2000: 14-21 |
202 | | Noga Alon,
Seannie Dar,
Michal Parnas,
Dana Ron:
Testing of Clustering.
FOCS 2000: 240-250 |
201 | EE | Noga Alon,
Haim Kaplan,
Michael Krivelevich,
Dahlia Malkhi,
Julien P. Stern:
Scalable Secure Storage when Half the System Is Faulty.
ICALP 2000: 576-587 |
200 | EE | Noga Alon,
Eldar Fischer,
Michael Krivelevich,
Mario Szegedy:
Efficient Testing of Large Graphs.
Combinatorica 20(4): 451-476 (2000) |
199 | | Noga Alon,
Benny Sudakov:
Bipartite Subgraphs And The Smallest Eigenvalue.
Combinatorics, Probability & Computing 9(1): (2000) |
198 | | Noga Alon,
Miklós Bóna,
Joel Spencer:
Packing Ferrers Shapes.
Combinatorics, Probability & Computing 9(3): (2000) |
197 | | Noga Alon,
János Körner,
Angelo Monti:
String Quartets In Binary.
Combinatorics, Probability & Computing 9(5): (2000) |
196 | | Noga Alon,
Emanuela Fachini,
János Körner:
Locally Thin Set Families.
Combinatorics, Probability & Computing 9(6): (2000) |
195 | EE | Noga Alon,
Raphael Yuster:
EveryH-decomposition ofKnhas a Nearly Resolvable Alternative.
Eur. J. Comb. 21(7): 839-845 (2000) |
194 | EE | Noga Alon,
Ehud Friedgut:
On the Number of Permutations Avoiding a Given Pattern.
J. Comb. Theory, Ser. A 89(1): 133-140 (2000) |
193 | EE | Noga Alon,
Kenneth A. Berman,
Daniel J. Kleitman:
On a Problem in Shuffling.
J. Comb. Theory, Ser. A 91(1-2): 5-14 (2000) |
192 | | Noga Alon:
Degrees and choice numbers.
Random Struct. Algorithms 16(4): 364-368 (2000) |
191 | EE | Noga Alon,
Michael Krivelevich,
Ilan Newman,
Mario Szegedy:
Regular Languages are Testable with a Constant Number of Queries.
SIAM J. Comput. 30(6): 1842-1862 (2000) |
1999 |
190 | EE | Noga Alon,
Michael Krivelevich,
Ilan Newman,
Mario Szegedy:
Regular Languages Are Testable with a Constant Number of Queries.
FOCS 1999: 645-655 |
189 | EE | Noga Alon,
Eldar Fischer,
Michael Krivelevich,
Mario Szegedy:
Efficient Testing of Large Graphs.
FOCS 1999: 656-666 |
188 | EE | Noga Alon,
Phillip B. Gibbons,
Yossi Matias,
Mario Szegedy:
Tracking Join and Self-Join Sizes in Limited Storage.
PODS 1999: 10-20 |
187 | | Noga Alon,
Uri Arad,
Yossi Azar:
Independent Sets in Hypergraphs with Applications to Routing via Fixed Paths.
RANDOM-APPROX 1999: 16-27 |
186 | | Noga Alon,
Eldar Fischer:
Refining the Graph Density Condition for the Existence of Almost K-factors.
Ars Comb. 52: (1999) |
185 | EE | Noga Alon,
Michael Krivelevich,
Benny Sudakov:
List Coloring of Random and Pseudo-Random Graphs.
Combinatorica 19(4): 453-472 (1999) |
184 | EE | Noga Alon,
Shmuel Onn:
Separable Partitions.
Discrete Applied Mathematics 91(1-3): 39-51 (1999) |
183 | EE | Noga Alon,
Peter Hamburger,
Alexandr V. Kostochka:
Regular Honest Graphs, Isoperimetric Numbers, and Bisection of Weighted Graphs.
Eur. J. Comb. 20(6): 469-481 (1999) |
182 | EE | Noga Alon,
Martin Dietzfelbinger,
Peter Bro Miltersen,
Erez Petrank,
Gábor Tardos:
Linear Hash Functions.
J. ACM 46(5): 667-683 (1999) |
181 | | Noga Alon,
Benny Sudakov:
On Two Segmentation Problems.
J. Algorithms 33(1): 173-184 (1999) |
180 | EE | Noga Alon,
Imre Z. Ruzsa:
Non-averaging Subsets and Non-vanishing Transversals.
J. Comb. Theory, Ser. A 86(1): 1-13 (1999) |
179 | EE | Noga Alon,
Lajos Rónyai,
Tibor Szabó:
Norm-Graphs: Variations and Applications.
J. Comb. Theory, Ser. B 76(2): 280-290 (1999) |
178 | EE | Noga Alon,
Michael Krivelevich,
Benny Sudakov:
Coloring Graphs with Sparse Neighborhoods.
J. Comb. Theory, Ser. B 77(1): 73-82 (1999) |
177 | | Noga Alon,
Yossi Matias,
Mario Szegedy:
The Space Complexity of Approximating the Frequency Moments.
J. Comput. Syst. Sci. 58(1): 137-147 (1999) |
1998 |
176 | EE | Noga Alon:
Spectral Techniques in Graph Algorithms.
LATIN 1998: 206-215 |
175 | | Noga Alon,
Michael Krivelevich,
Benny Sudakov:
Finding a Large Hidden Clique in a Random Graph.
SODA 1998: 594-598 |
174 | | Noga Alon,
Yossi Azar,
János Csirik,
Leah Epstein,
Sergey V. Sevastianov,
Arjen P. A. Vestjens,
Gerhard J. Woeginger:
On-Line and Off-Line Approximation Algorithms for Vector Covering Problems.
Algorithmica 21(1): 104-118 (1998) |
173 | EE | Noga Alon:
The Shannon Capacity of a Union.
Combinatorica 18(3): 301-310 (1998) |
172 | EE | Noga Alon:
Piercing d -Intervals.
Discrete & Computational Geometry 19(3): 333-334 (1998) |
171 | EE | Noga Alon,
Ayal Zaks:
T-choosability in Graphs.
Discrete Applied Mathematics 82(1-3): 1-13 (1998) |
170 | EE | Noga Alon,
Eran Halperin:
Bipartite subgraphs of integer weighted graphs.
Discrete Mathematics 181(1-3): 19-29 (1998) |
169 | EE | Noga Alon,
Vojtech Rödl,
Andrzej Rucinski:
Perfect Matchings in $\epsilon$-regular Graphs.
Electr. J. Comb. 5: (1998) |
168 | EE | Noga Alon:
On the Capacity of Digraphs.
Eur. J. Comb. 19(1): 1-5 (1998) |
167 | EE | Noga Alon,
Ayal Zaks:
Progressions in Sequences of Nearly Consecutive Integers.
J. Comb. Theory, Ser. A 84(1): 99-109 (1998) |
166 | | Noga Alon,
Nabil Kahale:
Approximating the independence number via the theta-function.
Math. Program. 80: 253-264 (1998) |
165 | | Noga Alon,
Michael Krivelevich,
Benny Sudakov:
Finding a large hidden clique in a random graph.
Random Struct. Algorithms 13(3-4): 457-466 (1998) |
1997 |
164 | | Noga Alon,
Yossi Azar,
Gerhard J. Woeginger,
Tal Yadid:
Approximation Schemes for Scheduling.
SODA 1997: 493-500 |
163 | EE | Noga Alon,
Martin Dietzfelbinger,
Peter Bro Miltersen,
Erez Petrank,
Gábor Tardos:
Is Linear Hashing Good?
STOC 1997: 465-474 |
162 | | Noga Alon,
Raphael Yuster,
Uri Zwick:
Finding and Counting Given Length Cycles.
Algorithmica 17(3): 209-223 (1997) |
161 | | Noga Alon,
Aravind Srinivasan:
Improved Parallel Approximation of a Class of Integer Programming Problems.
Algorithmica 17(4): 449-462 (1997) |
160 | | Noga Alon,
Michael Krivelevich:
The Concentration of the Chromatic Number of Random Graphs.
Combinatorica 17(3): 303-313 (1997) |
159 | | Rudolf Ahlswede,
Noga Alon,
Péter L. Erdös,
Miklós Ruszinkó,
László A. Székely:
Intersecting Systems.
Combinatorics, Probability & Computing 6(2): 127-137 (1997) |
158 | | Noga Alon:
On the Edge-Expansion of Graphs.
Combinatorics, Probability & Computing 6(2): 145-152 (1997) |
157 | EE | Noga Alon,
Zsolt Tuza,
Margit Voigt:
Choosability and fractional chromatic numbers.
Discrete Mathematics 165-166: 31-38 (1997) |
156 | EE | Noga Alon:
Packings with large minimum kissing numbers.
Discrete Mathematics 175(1-3): 249-251 (1997) |
155 | EE | Noga Alon,
Miklós Ruszinkó:
Short Certificates for Tournaments.
Electr. J. Comb. 4(1): (1997) |
154 | EE | Noga Alon,
Daniel J. Kleitman:
A purely combinatorial proof of the Hadwiger Debrunner (p, q) Conjecture.
Electr. J. Comb. 4(2): (1997) |
153 | EE | Noga Alon,
Shai Ben-David,
Nicolò Cesa-Bianchi,
David Haussler:
Scale-sensitive dimensions, uniform convergence, and learnability.
J. ACM 44(4): 615-631 (1997) |
152 | | Noga Alon,
Dmitry N. Kozlov:
Coins with Arbitrary Weights.
J. Algorithms 25(1): 162-176 (1997) |
151 | EE | Noga Alon,
Jeong Han Kim:
On the Degree, Size, and Chromatic Index of a Uniform Hypergraph.
J. Comb. Theory, Ser. A 77(1): 165-170 (1997) |
150 | EE | Noga Alon,
Van H. Vu:
Anti-Hadamard Matrices, Coin Weighing, Threshold Gates, and Indecomposable Hypergraphs.
J. Comb. Theory, Ser. A 79(1): 133-160 (1997) |
149 | EE | Noga Alon,
Michael Tarsi:
A Note on Graph Colorings and Graph Polynomials.
J. Comb. Theory, Ser. B 70(1): 197-201 (1997) |
148 | EE | Noga Alon,
Yair Caro,
Raphael Yuster:
Covering the Edges of a Graph by a Prescribed Tree with Minimum Overlap.
J. Comb. Theory, Ser. B 71(2): 144-161 (1997) |
147 | | Noga Alon,
Zvi Galil,
Oded Margalit:
On the Exponent of the All Pairs Shortest Path Problem.
J. Comput. Syst. Sci. 54(2): 255-262 (1997) |
146 | | Noga Alon,
Gregory Gutin:
Properly colored Hamilton cycles in edge-colored complete graphs.
Random Struct. Algorithms 11(2): 179-186 (1997) |
145 | | Noga Alon,
Nabil Kahale:
A Spectral Technique for Coloring Random 3-Colorable Graphs.
SIAM J. Comput. 26(6): 1733-1748 (1997) |
1996 |
144 | | Noga Alon,
János Csirik,
Sergey V. Sevastianov,
Arjen P. A. Vestjens,
Gerhard J. Woeginger:
On-line and Off-line Approximation Algorithms for Vector Covering Problems.
ESA 1996: 406-418 |
143 | | Noga Alon,
Dmitry N. Kozlov,
Van H. Vu:
The Geometry of Coin-Weighing Problems.
FOCS 1996: 524-532 |
142 | | Noga Alon,
Aravind Srinivasan:
Improved Parallel Approximation of a Class of Integer Programming Programming Problems.
ICALP 1996: 562-573 |
141 | EE | Noga Alon,
Yossi Matias,
Mario Szegedy:
The Space Complexity of Approximating the Frequency Moments.
STOC 1996: 20-29 |
140 | | Noga Alon:
Derandomization Via Small Sample Spaces (Abstract).
SWAT 1996: 1-3 |
139 | | Noga Alon,
Moni Naor:
Derandomization, Witnesses for Boolean Matrix Multiplication and Construction of Perfect Hash Functions.
Algorithmica 16(4/5): 434-449 (1996) |
138 | | Noga Alon:
Bipartite Subgraphs.
Combinatorica 16(3): 301-311 (1996) |
137 | EE | Noga Alon,
Eldar Fischer:
2-factors in dense graphs.
Discrete Mathematics 152(1-3): 13-23 (1996) |
136 | | Noga Alon,
Alon Orlitsky:
Source coding and graph entropies.
IEEE Transactions on Information Theory 42(5): 1329-1339 (1996) |
135 | | Noga Alon,
Michael Luby:
A linear time erasure-resilient code with nearly optimal recovery.
IEEE Transactions on Information Theory 42(6): 1732-1736 (1996) |
134 | EE | Noga Alon,
Phillip G. Bradford,
Rudolf Fleischer:
Matching Nuts and Bolts Faster.
Inf. Process. Lett. 59(3): 123-127 (1996) |
133 | EE | Noga Alon,
Raphael Yuster:
H-Factors in Dense Graphs.
J. Comb. Theory, Ser. B 66(2): 269-282 (1996) |
132 | EE | Noga Alon:
Disjoint Directed Cycles.
J. Comb. Theory, Ser. B 68(2): 167-178 (1996) |
131 | | Noga Alon,
Pierre Kelsen,
Sanjeev Mahajan,
Ramesh Hariharan:
Approximate Hypergraph Coloring.
Nord. J. Comput. 3(4): 425-439 (1996) |
130 | | Noga Alon:
Independence numbers of locally sparse graphs and a Ramsey type problem.
Random Struct. Algorithms 9(3): 271-278 (1996) |
1995 |
129 | | Noga Alon,
Zvi Galil,
Moti Yung:
Efficient Dynamic-Resharing "Verifiable Secret Sharing" Against Mobile Adversary.
ESA 1995: 523-537 |
128 | | Noga Alon,
Jeff Edmonds,
Michael Luby:
Linear Time Erasure Codes with Nearly Optimal Recovery (Extended Abstract).
FOCS 1995: 512-519 |
127 | | Noga Alon,
Moshe Dubiner:
A Lattice Point Problem and Additive Number Theory.
Combinatorica 15(3): 301-309 (1995) |
126 | | Noga Alon,
Uriel Feige,
Avi Wigderson,
David Zuckerman:
Derandomized Graph Products.
Computational Complexity 5(1): 60-75 (1995) |
125 | | Noga Alon,
Gil Kalai:
Bounding the Piercing Number.
Discrete & Computational Geometry 13: 245-256 (1995) |
124 | EE | Noga Alon,
Joel Spencer,
Prasad Tetali:
Covering with Latin Transversals.
Discrete Applied Mathematics 57(1): 1-10 (1995) |
123 | | Noga Alon,
Sridhar Rajagopalan,
Subhash Suri:
Long Non-Crossing Configurations in the Plane.
Fundam. Inform. 22(4): 385-394 (1995) |
122 | | Noga Alon,
Alon Orlitsky:
Repeated communication and Ramsey graphs.
IEEE Transactions on Information Theory 41(5): 1276-1289 (1995) |
121 | EE | Noga Alon,
Yishay Mansour:
epsilon-Discrepancy Sets and Their Application for Interpolation of Sparse Polynomials.
Inf. Process. Lett. 54(6): 337-342 (1995) |
120 | EE | Noga Alon,
Raphael Yuster,
Uri Zwick:
Color-Coding.
J. ACM 42(4): 844-856 (1995) |
119 | | Noga Alon,
Raphael Yuster:
The 123 Theorem and Its Extensions.
J. Comb. Theory, Ser. A 72(2): 322-331 (1995) |
118 | | Noga Alon,
Benny Sudakov:
Disjoint Systems.
Random Struct. Algorithms 6(1): 13-20 (1995) |
117 | | Noga Alon,
Zsolt Tuza:
The Acyclic Orientation Game on Random Graphs.
Random Struct. Algorithms 6(2/3): 261-268 (1995) |
116 | | Noga Alon,
Alan M. Frieze,
Dominic Welsh:
Polynomial Time Randomized Approximation Schemes for Tutte-Gröthendieck Invariants: The Dense Case.
Random Struct. Algorithms 6(4): 459-478 (1995) |
115 | | Noga Alon,
Richard M. Karp,
David Peleg,
Douglas B. West:
A Graph-Theoretic Game and Its Application to the k-Server Problem.
SIAM J. Comput. 24(1): 78-100 (1995) |
1994 |
114 | | Noga Alon,
Raphael Yuster,
Uri Zwick:
Finding and Counting Given Length Cycles (Extended Abstract).
ESA 1994: 354-364 |
113 | | Noga Alon,
Alan M. Frieze,
Dominic Welsh:
Polynomial time randomised approxmiation schemes for the Tutte polynomial of dense graphs
FOCS 1994: 24-35 |
112 | | Noga Alon,
Manuel Blum,
Amos Fiat,
Sampath Kannan,
Moni Naor,
Rafail Ostrovsky:
Matching Nuts and Bolts.
SODA 1994: 690-696 |
111 | EE | Noga Alon,
Raphael Yuster,
Uri Zwick:
Color-coding: a new method for finding simple paths, cycles and other small subgraphs within large graphs.
STOC 1994: 326-335 |
110 | EE | Noga Alon,
Nabil Kahale:
A spectral technique for coloring random 3-colorable graphs (preliminary version).
STOC 1994: 346-355 |
109 | | Pankaj K. Agarwal,
Noga Alon,
Boris Aronov,
Subhash Suri:
Can Visibility Graphs Be Represented Compactly?.
Discrete & Computational Geometry 12: 347-365 (1994) |
108 | EE | Noga Alon:
Probabilistic methods in coloring and decomposition problems.
Discrete Mathematics 127(1-3): 31-46 (1994) |
107 | EE | Noga Alon:
Explicit Ramsey graphs and orthonormal labelings.
Electr. J. Comb. 1: (1994) |
106 | EE | Noga Alon,
Alan M. Frieze,
Dominic Welsh:
Polynomial Time Randomised Approximation Schemes for Tutte-Gröthendieck Invariants: The Dense Case
Electronic Colloquium on Computational Complexity (ECCC) 1(5): (1994) |
105 | EE | Noga Alon,
Raphael Yuster,
Uri Zwick:
Color-Coding
Electronic Colloquium on Computational Complexity (ECCC) 1(9): (1994) |
104 | | Noga Alon,
Alon Orlitsky:
A lower bound on the expected length of one-to-one codes.
IEEE Transactions on Information Theory 40(5): 1670- (1994) |
103 | EE | Noga Alon,
Nimrod Megiddo:
Parallel Linear Programming in Fixed Dimension Almost Surely in Constant Time.
J. ACM 41(2): 422-434 (1994) |
102 | | Noga Alon,
Richard A. Duke,
Hanno Lefmann,
Vojtech Rödl,
Raphael Yuster:
The Algorithmic Aspects of the Regularity Lemma.
J. Algorithms 16(1): 80-109 (1994) |
101 | | Noga Alon,
Pavel Pudlák:
Superconcentrators of Depths 2 and 3; Odd Levels Help (Rarely).
J. Comput. Syst. Sci. 48(1): 194-202 (1994) |
100 | | Noga Alon,
Yuval Roichman:
Random Cayley Graphs and Expanders.
Random Struct. Algorithms 5(2): 271-285 (1994) |
99 | EE | Noga Alon,
Jehoshua Bruck:
Explicit Constructions of Depth-2 Majority Circuits for Comparison and Addition.
SIAM J. Discrete Math. 7(1): 1-8 (1994) |
98 | EE | Noga Alon,
Paul D. Seymour,
Robin Thomas:
Planar Separators.
SIAM J. Discrete Math. 7(2): 184-193 (1994) |
97 | EE | Noga Alon,
Fan R. K. Chung,
Ronald L. Graham:
Routing Permutations on Graphs Via Matchings.
SIAM J. Discrete Math. 7(3): 513-530 (1994) |
96 | | Noga Alon,
Gil Kalai,
Moty Ricklin,
Larry J. Stockmeyer:
Lower Bounds on the Competitive Ratio for Mobile User Tracking and Distributed Job Scheduling.
Theor. Comput. Sci. 130(1): 175-201 (1994) |
1993 |
95 | | Noga Alon,
Benny Sudakov:
Disjoint Systems (Extended Abstract).
Algebraic Coding 1993: 159-163 |
94 | | Noga Alon,
Shai Ben-David,
Nicolò Cesa-Bianchi,
David Haussler:
Scale-sensitive Dimensions, Uniform Convergence, and Learnability
FOCS 1993: 292-301 |
93 | EE | Noga Alon,
Fan R. K. Chung,
Ronald L. Graham:
Routing permutations on graphs via matchings.
STOC 1993: 583-591 |
92 | EE | Noga Alon,
Sridhar Rajagopalan,
Subhash Suri:
Long Non-Crossing Configurations in the Plane.
Symposium on Computational Geometry 1993: 257-263 |
91 | EE | Pankaj K. Agarwal,
Noga Alon,
Boris Aronov,
Subhash Suri:
Can Visibility Graphs be Represented Compactly?
Symposium on Computational Geometry 1993: 338-347 |
90 | | Noga Alon,
Raphael Yuster:
Threshold Functions for H-factors.
Combinatorics, Probability & Computing 2: 137-144 (1993) |
89 | | Noga Alon,
Yossi Azar:
On-Line Steine Trees in the Euclidean Plane.
Discrete & Computational Geometry 10: 113-121 (1993) |
88 | EE | Noga Alon,
Yair Caro,
Ilia Krasikov:
Bisection of trees and sequences.
Discrete Mathematics 114(1-3): 3-7 (1993) |
87 | EE | Noga Alon,
Zoltán Füredi:
Covering the Cube by Affine Hyperplanes.
Eur. J. Comb. 14(2): 79-83 (1993) |
86 | | Noga Alon,
Oded Goldreich,
Johan Håstad,
René Peralta:
Addendum to "Simple Construction of Almost k-wise Independent Random Variables".
Random Struct. Algorithms 4(1): 119-120 (1993) |
85 | | Noga Alon,
Moni Naor:
Coin-Flipping Games Immune Against Linear-Sized Coalitions.
SIAM J. Comput. 22(2): 403-417 (1993) |
1992 |
84 | | Noga Alon,
Joel Spencer:
The Probabilistic Method
John Wiley 1992 |
83 | | Noga Alon,
Gil Kalai,
Moty Ricklin,
Larry J. Stockmeyer:
Lower Bounds on the Competitive Ratio for Mobile User Tracking and Distributed Job Scheduling (Extended Abstract)
FOCS 1992: 334-343 |
82 | | Noga Alon,
Zvi Galil,
Oded Margalit,
Moni Naor:
Witnesses for Boolean Matrix Multiplication and for Shortest Paths
FOCS 1992: 417-426 |
81 | | Noga Alon,
Richard A. Duke,
Hanno Lefmann,
Vojtech Rödl,
Raphael Yuster:
The Algorithmic Aspects of the Regularity Lemma (Extended Abstract)
FOCS 1992: 473-481 |
80 | | Miklós Ajtai,
Noga Alon,
Jehoshua Bruck,
Robert Cypher,
Ching-Tien Ho,
Moni Naor,
Endre Szemerédi:
Fault Tolerant Graphs, Perfect Hash Functions and Disjoint Paths
FOCS 1992: 693-702 |
79 | EE | Noga Alon,
Yossi Azar:
Comparison-Sorting and Selecting in Totally Monotone Matrices.
SODA 1992: 403-408 |
78 | EE | Noga Alon,
Daniel J. Kleitman:
Piercing Convex Sets.
Symposium on Computational Geometry 1992: 157-160 |
77 | EE | Noga Alon,
Yossi Azar:
On-Line Steiner Trees in the Euclidean Plane.
Symposium on Computational Geometry 1992: 337-343 |
76 | | Noga Alon,
Michael Tarsi:
Colorings and orientations of graphs.
Combinatorica 12(2): 125-134 (1992) |
75 | | Noga Alon,
Colin McDiarmid,
Bruce A. Reed:
Star arboricity.
Combinatorica 12(4): 375-380 (1992) |
74 | | Noga Alon:
Choice Numbers of Graphs: a Probabilistic Approach.
Combinatorics, Probability & Computing 1: 107-114 (1992) |
73 | | Noga Alon,
Imre Bárány,
Zoltán Füredi,
Daniel J. Kleitman:
Point Selections and Weak e-Nets for Convex Hulls.
Combinatorics, Probability & Computing 1: 189-200 (1992) |
72 | EE | Noga Alon:
Transmitting in the n-Dimensional Cube.
Discrete Applied Mathematics 37/38: 9-11 (1992) |
71 | EE | Noga Alon,
Daniel J. Kleitman:
Partitioning a rectangle into small perimeter rectangles.
Discrete Mathematics 103(2): 111-119 (1992) |
70 | | Noga Alon,
Jehoshua Bruck,
Joseph Naor,
Moni Naor,
Ron M. Roth:
Construction of asymptotically good low-rate error-correcting codes through pseudo-random graphs.
IEEE Transactions on Information Theory 38(2): 509- (1992) |
69 | | Noga Alon,
Amotz Bar-Noy,
Nathan Linial,
David Peleg:
Single Round Simulation on Radio Networks.
J. Algorithms 13(2): 188-210 (1992) |
68 | | Noga Alon:
The String Chromatic Number of a Graph.
Random Struct. Algorithms 3(1): 1-8 (1992) |
67 | | Noga Alon,
Oded Goldreich,
Johan Håstad,
René Peralta:
Simple Construction of Almost k-wise Independent Random Variables.
Random Struct. Algorithms 3(3): 289-304 (1992) |
1991 |
66 | | Noga Alon,
Zvi Galil,
Oded Margalit:
On the Exponent of the All Pairs Shortest Path Problem
FOCS 1991: 569-575 |
65 | | Noga Alon:
A parallel algorithmic version of the Local Lemma
FOCS 1991: 586-593 |
64 | | Noga Alon,
Yossi Azar:
Parallel comparison algorithms for approximation problems.
Combinatorica 11(2): 97-122 (1991) |
63 | EE | Noga Alon,
A. K. Dewdney,
Teunis J. Ott:
Efficient Simulation of Finite Automata by Neural Nets.
J. ACM 38(2): 495-514 (1991) |
62 | EE | Noga Alon,
Nathan Linial,
Roy Meshulam:
Additive bases of vector spaces over prime fields.
J. Comb. Theory, Ser. A 57(2): 203-210 (1991) |
61 | EE | Noga Alon,
László Babai,
H. Suzuki:
Multilinear polynomials and Frankl-Ray-Chaudhuri-Wilson type intersection theorems.
J. Comb. Theory, Ser. A 58(2): 165-180 (1991) |
60 | EE | Noga Alon,
Richard A. Brualdi,
Bryan L. Shader:
Multicolored forests in bipartite decompositions of graphs.
J. Comb. Theory, Ser. B 53(1): 143-148 (1991) |
59 | | Noga Alon,
Amotz Bar-Noy,
Nathan Linial,
David Peleg:
A Lower Bound for Radio Broadcast.
J. Comput. Syst. Sci. 43(2): 290-298 (1991) |
58 | | Noga Alon,
Colin McDiarmid,
Bruce A. Reed:
Acyclic Coloring of Graphs.
Random Struct. Algorithms 2(3): 277-288 (1991) |
57 | | Noga Alon:
A Parallel Algorithmic Version of the Local Lemma.
Random Struct. Algorithms 2(4): 367-378 (1991) |
1990 |
56 | | Noga Alon,
Moni Naor:
Coin-Flipping Games Immune against Linear-Sized Coalitions (Extended Abstract)
FOCS 1990: 46-54 |
55 | | Noga Alon,
Oded Goldreich,
Johan Håstad,
René Peralta:
Simple Constructions of Almost k-Wise Independent Random Variables
FOCS 1990: 544-553 |
54 | | Noga Alon,
Nimrod Megiddo:
Parallel Linear Programming in Fixed Dimension Almost Surely in Constant Time
FOCS 1990: 574-582 |
53 | | Noga Alon,
Paul D. Seymour,
Robin Thomas:
A Separator Theorem for Graphs with an Excluded Minor and its Applications
STOC 1990: 293-299 |
52 | | Noga Alon:
The maximum number of Hamiltonian paths in tournaments.
Combinatorica 10(4): 319-324 (1990) |
51 | EE | Noga Alon,
Yossi Azar,
Yiftach Ravid:
Universal sequences for complete graphs.
Discrete Applied Mathematics 27(1-2): 25-28 (1990) |
50 | | Noga Alon:
Generating Pseudo-Random Permutations and Maximum Flow Algorithms.
Inf. Process. Lett. 35(4): 201-204 (1990) |
49 | | Noga Alon:
The Number of Spanning Trees in Regular Graphs.
Random Struct. Algorithms 1(2): 175-182 (1990) |
48 | | Noga Alon,
Mauricio Karchmer,
Avi Wigderson:
Linear Circuits over GF(2).
SIAM J. Comput. 19(6): 1064-1067 (1990) |
1989 |
47 | | Noga Alon,
Amotz Bar-Noy,
Nathan Linial,
David Peleg:
On the Complexity of Radio Communication (Extended Abstract)
STOC 1989: 274-285 |
46 | | Noga Alon,
Michael Tarsi:
A nowhere-zero point in liner mappings.
Combinatorica 9(4): 393-396 (1989) |
45 | | Noga Alon,
Meir Katchalski,
William R. Pulleyblank:
Cutting Disjoint Disks by Straight Lines.
Discrete & Computational Geometry 4: 239-243 (1989) |
44 | | Noga Alon,
Meir Katchalski,
William R. Pulleyblank:
The Maximum Size of a Convex Polygon in a Restricted Set in the Plane.
Discrete & Computational Geometry 4: 245-251 (1989) |
43 | | Noga Alon,
Paul Erdös:
Disjoint Edges in Geometric Graphs.
Discrete & Computational Geometry 4: 287-290 (1989) |
42 | EE | I. Algor,
Noga Alon:
The star arboricity of graphs.
Discrete Mathematics 75(1-3): 11-22 (1989) |
41 | EE | Noga Alon,
Béla Bollobás:
Graphs with a small number of distinct induced subgraphs.
Discrete Mathematics 75(1-3): 23-30 (1989) |
40 | EE | Noga Alon,
Joel H. Spencer:
Ascending waves.
J. Comb. Theory, Ser. A 52(2): 275-287 (1989) |
39 | EE | Noga Alon,
Nathan Linial:
Cycles of length 0 modulo k in directed graphs.
J. Comb. Theory, Ser. B 47(1): 114-119 (1989) |
38 | EE | Noga Alon,
Yair Caro,
Ilia Krasikov,
Yehuda Roditty:
Combinatorial reconstruction problems.
J. Comb. Theory, Ser. B 47(2): 153-161 (1989) |
37 | | Noga Alon,
Yossi Azar:
Finding an Approximate Maximum.
SIAM J. Comput. 18(2): 258-267 (1989) |
36 | | Noga Alon,
Uri Zwick:
On Neciporuk's Theorem for Branching Programs.
Theor. Comput. Sci. 64(3): 331-342 (1989) |
1988 |
35 | | Noga Alon,
Yossi Azar:
Parallel Comparison Algorithms for Approximation Problems
FOCS 1988: 194-203 |
34 | | Noga Alon,
Gregory Freiman:
On sums of subsets of a set of integers.
Combinatorica 8(4): 297-306 (1988) |
33 | EE | Noga Alon:
Sums of subsequences modulo prime powers.
Discrete Mathematics 71(1): 87-88 (1988) |
32 | EE | Noga Alon,
Fan R. K. Chung:
Explicit construction of linear sized tolerant networks.
Discrete Mathematics 72(1-3): 15-19 (1988) |
31 | | Noga Alon,
E. E. Bergmann,
Don Coppersmith,
Andrew M. Odlyzko:
Balancing sets of vectors.
IEEE Transactions on Information Theory 34(1): 128- (1988) |
30 | | Noga Alon,
Wolfgang Maass:
Meanders and Their Applications in Lower Bounds Arguments.
J. Comput. Syst. Sci. 37(2): 118-129 (1988) |
29 | | Noga Alon,
Yossi Azar:
The Average Complexity of Deterministic and Randomized Parallel Comparison-Sorting Algorithms.
SIAM J. Comput. 17(6): 1178-1192 (1988) |
28 | | Noga Alon,
Yossi Azar:
Sorting, Approximate Sorting, and Searching in Rounds.
SIAM J. Discrete Math. 1(3): 269-280 (1988) |
1987 |
27 | | Noga Alon,
Yossi Azar:
The Average Complexity of Deterministic and Randomized Parallel Comparison Sorting Algorithms
FOCS 1987: 489-498 |
26 | | Noga Alon,
Amnon Barak,
Udi Manber:
On Disseminating Information Reliably without Broadcasting.
ICDCS 1987: 74-81 |
25 | EE | Noga Alon,
David Haussler,
Emo Welzl:
Partitioning and Geometric Embedding of Range Spaces of Finite Vapnik-Chervonenkis Dimension.
Symposium on Computational Geometry 1987: 331-340 |
24 | | Noga Alon,
Ravi B. Boppana:
The monotone circuit complexity of Boolean functions.
Combinatorica 7(1): 1-22 (1987) |
23 | | Noga Alon,
Daniel J. Kleitman,
Carl Pomerance,
Michael E. Saks,
Paul D. Seymour:
The smallets n-uniform hypergraph with positive discrepancy.
Combinatorica 7(2): 151-160 (1987) |
22 | | Noga Alon,
Zvi Galil,
V. D. Milman:
Better Expanders and Superconcentrators.
J. Algorithms 8(3): 337-347 (1987) |
1986 |
21 | | Noga Alon,
Wolfgang Maass:
Meanders, Ramsey Theory and Lower Bounds for Branching Programs
FOCS 1986: 410-417 |
20 | | Noga Alon,
Yossi Azar,
Uzi Vishkin:
Tight Complexity Bounds for Parallel Comparison Sorting
FOCS 1986: 502-510 |
19 | | Noga Alon:
Eigenvalues and expanders.
Combinatorica 6(2): 83-96 (1986) |
18 | | Noga Alon:
Covering graphs by the minimum number of equivalence relations.
Combinatorica 6(3): 201-206 (1986) |
17 | | Noga Alon:
Eigenvalues, geometric expanders, sorting in rounds, and Ramsey theory.
Combinatorica 6(3): 207-219 (1986) |
16 | | Noga Alon,
Daniel J. Kleitman:
Covering a Square by Small Perimeter Rectangles.
Discrete & Computational Geometry 1: 1-7 (1986) |
15 | EE | Noga Alon:
Explicit construction of exponential sized families of k-independent sets.
Discrete Mathematics 58(2): 191-193 (1986) |
14 | EE | Noga Alon,
Micha A. Perles:
On the intersection of edges of a geometric graph by straight lines.
Discrete Mathematics 60: 75-90 (1986) |
13 | | Noga Alon,
László Babai,
Alon Itai:
A Fast and Simple Randomized Parallel Algorithm for the Maximal Independent Set Problem.
J. Algorithms 7(4): 567-583 (1986) |
12 | EE | Noga Alon,
Ervin Györi:
The number of small semispaces of a finite set of points in the plane.
J. Comb. Theory, Ser. A 41(1): 154-157 (1986) |
11 | EE | Noga Alon,
Kenneth A. Berman:
Regular hypergraphs, Gordon's lemma, Steinitz' lemma and invariant theory.
J. Comb. Theory, Ser. A 43(1): 91-97 (1986) |
1985 |
10 | | Noga Alon,
Peter Frankl,
Vojtech Rödl:
Geometrical Realization of Set Systems and Probabilistic Communication Complexity
FOCS 1985: 277-280 |
9 | | Noga Alon:
Expanders, Sorting in Rounds and Superconcentrators of Limited Depth
STOC 1985: 98-102 |
8 | | Noga Alon:
An Extremal Problem for Sets with Applications to Graph Theory.
J. Comb. Theory, Ser. A 40(1): 82-89 (1985) |
7 | EE | Noga Alon,
V. D. Milman:
lambda1, Isoperimetric inequalities for graphs, and superconcentrators.
J. Comb. Theory, Ser. B 38(1): 73-88 (1985) |
6 | EE | Noga Alon,
Yoshimi Egawa:
Even edge colorings of a graph.
J. Comb. Theory, Ser. B 38(1): 93-94 (1985) |
1984 |
5 | | Noga Alon,
V. D. Milman:
Eigenvalues, Expanders and Superconcentrators (Extended Abstract)
FOCS 1984: 320-322 |
4 | EE | Noga Alon:
A note on subdigraphs of digraphs with large outdegrees.
Discrete Mathematics 49(3): 321-322 (1984) |
3 | EE | Noga Alon,
S. Friedland,
Gil Kalai:
Regular subgraphs of almost regular graphs.
J. Comb. Theory, Ser. B 37(1): 79-91 (1984) |
2 | EE | Noga Alon,
S. Friedland,
Gil Kalai:
Every 4-regular graph plus an edge contains a 3-regular subgraph.
J. Comb. Theory, Ser. B 37(1): 92-93 (1984) |
1983 |
1 | EE | Noga Alon:
On the density of sets of vectors.
Discrete Mathematics 46(2): 199-202 (1983) |