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) |