default search action
Google
Google Scholar
Semantic Scholar
Internet Archive Scholar
CiteSeerX
ORCIDNoga Alon
Alon Nilli – נוגה אלון
Person information
- unicode name: נוגה אלון
- affiliation: Princeton University, USA
- affiliation: Tel Aviv University, Sackler School of Mathematics, Israel
- award (2019): ACM Paris Kanellakis Theory and Practice Award
- award (2016): Dijkstra Prize
- award (2005): Gödel Prize
Refine list
refinements active!
zoomed in on ?? of ?? records
view refined list in
export refined list as
showing all ?? records
2020 – today
- 2025
[j448]Noga Alon, Colin Defant, Noah Kravitz, Daniel G. Zhu:
Ordering Candidates via Vantage Points. Comb. 45(2): 25 (2025)- [j447]Hannaneh Akrami
, Noga Alon, Bhaskar Ray Chaudhury, Jugal Garg, Kurt Mehlhorn, Ruta Mehta:
EFX: A Simpler Approach and an (Almost) Optimal Guarantee via Rainbow Cycle Number. Oper. Res. 73(2): 738-751 (2025) - [j446]Noga Alon, Or Zamir:
Sumsets in the Hypercube. SIAM J. Discret. Math. 39(1): 314-326 (2025) - [c181]Noga Alon, Nick Gravin, Tristan Pollner, Aviad Rubinstein, Hongao Wang, S. Matthew Weinberg, Qianfan Zhang:
A Bicriterion Concentration Inequality and Prophet Inequalities for k-Fold Matroid Unions. ITCS 2025: 4:1-4:22 - 2024
- [j445]Noah Kravitz, Noga Alon:
Cats in Cubes. Electron. J. Comb. 31(3) (2024) - [j444]Noga Alon:
Implicit Representation of Sparse Hereditary Families. Discret. Comput. Geom. 72(2): 476-482 (2024) - [j443]Noga Alon:
Graph-codes. Eur. J. Comb. 116: 103880 (2024) - [j442]Noga Alon:
Erasure list-decodable codes and Turán hypercube problems. Finite Fields Their Appl. 100: 102513 (2024) - [j441]Noga Alon, Peter Frankl:
Turán graphs with bounded matching number. J. Comb. Theory B 165: 223-229 (2024) - [j440]Noga Alon:
Connectivity graph-codes. Random Struct. Algorithms 65(3): 451-459 (2024) - [j439]Noga Alon, Emil Powierski, Michael Savery, Alex D. Scott, Elizabeth Wilmer:
Invertibility of Digraphs and Tournaments. SIAM J. Discret. Math. 38(1): 327-347 (2024) - [j438]Noga Alon, Dor Elboim, János Pach, Gábor Tardos:
Random Necklaces Require Fewer Cuts. SIAM J. Discret. Math. 38(2): 1381-1408 (2024) - [j437]Noga Alon, Jonathan D. Cohen, Thomas L. Griffiths, Pasin Manurangsi, Daniel Reichman, Igor Shinkar, Tal Wagner:
Erratum: Multitasking Capacity: Hardness Results and Improved Constructions. SIAM J. Discret. Math. 38(2): 2001-2003 (2024) - [j436]Noga Alon, Olivier Bousquet, Kasper Green Larsen, Shay Moran, Shlomo Moran:
Diagonalization Games. Am. Math. Mon. 131(10): 866-879 (2024) - [j435]Noga Alon, Gabriela Bourla, Ben Graham, Xiaoyu He, Noah Kravitz:
Logarithmically Larger Deletion Codes of All Distances. IEEE Trans. Inf. Theory 70(1): 125-130 (2024) - [c180]Noga Alon, Shay Moran, Hilla Schefler, Amir Yehudayoff:
A Unified Characterization of Private Learnability via Graph Theory. COLT 2024: 94-129 - [c179]Noga Alon, Dmitrii Avdiukhin, Dor Elboim, Orr Fischer, Grigory Yaroslavtsev:
Optimal Sample Complexity of Contrastive Learning. ICLR 2024 - [c178]Noga Alon, Allan Grønlund, Søren Fuglede Jørgensen, Kasper Green Larsen:
Sublinear Time Shortest Path in Expander Graphs. MFCS 2024: 8:1-8:13 - [i92]Noga Alon, Or Zamir:
Sumsets in the Hypercube. CoRR abs/2403.16589 (2024) - [i91]Noga Alon, Baruch Schieber:
Optimal Preprocessing for Answering On-Line Product Queries. CoRR abs/2406.06321 (2024) - [i90]Noga Alon, Nick Gravin, Tristan Pollner, Aviad Rubinstein, Hongao Wang, S. Matthew Weinberg, Qianfan Zhang:
A Bicriterion Concentration Inequality and Prophet Inequalities for k-Fold Matroid Unions. CoRR abs/2411.11741 (2024) - 2023
- [j434]Noga Alon, Fan Wei:
Irregular subgraphs. Comb. Probab. Comput. 32(2): 269-283 (2023) - [j433]Noga Alon, Michael Krivelevich, Wojciech Samotij:
Largest subgraph from a hereditary property in a random graph. Discret. Math. 346(9): 113480 (2023) - [j432]Noga Alon, Jaroslaw Grytczuk, Andrzej P. Kisielewicz, Krzysztof Przeslawski:
New bounds on the maximum number of neighborly boxes in Rd. Eur. J. Comb. 114: 103797 (2023) - [j431]Noga Alon, Colin Defant, Noah Kravitz:
Typical and extremal aspects of friends-and-strangers graphs. J. Comb. Theory B 158(Part): 3-42 (2023) - [j430]Noga Alon, Michael Krivelevich, Benny Sudakov:
Complete minors and average degree: A short proof. J. Graph Theory 103(3): 599-602 (2023) - [j429]Noga Alon, Anna Gujgiczer, János Körner, Aleksa Milojevic, Gábor Simonyi:
Structured Codes of Graphs. SIAM J. Discret. Math. 37(1): 379-403 (2023) - [j428]Noga Alon, Ehud Friedgut, Gil Kalai, Guy Kindler:
The Success Probability in Levine's Hat Problem, and Independent Sets in Graphs. SIAM J. Discret. Math. 37(4): 2717-2729 (2023) - [j427]Noga Alon, Alon Gonen, Elad Hazan, Shay Moran:
Boosting Simple Learners. TheoretiCS 2 (2023) - [c177]Hannaneh Akrami, Noga Alon, Bhaskar Ray Chaudhury, Jugal Garg, Kurt Mehlhorn, Ruta Mehta:
EFX: A Simpler Approach and an (Almost) Optimal Guarantee via Rainbow Cycle Number. EC 2023: 61 - [i89]Noga Alon, Olivier Bousquet, Kasper Green Larsen, Shay Moran, Shlomo Moran:
Diagonalization Games. CoRR abs/2301.01924 (2023) - [i88]Noga Alon, Shay Moran, Hilla Schefler, Amir Yehudayoff:
A Unified Characterization of Private Learnability via Graph Theory. CoRR abs/2304.03996 (2023) - [i87]Noga Alon, Anurag Bishnoi, Shagnik Das, Alessandro Neri:
Strong blocking sets and minimal codes from expander graphs. CoRR abs/2305.15297 (2023) - [i86]Noga Alon, Allan Grønlund, Søren Fuglede Jørgensen, Kasper Green Larsen:
Sublinear Time Shortest Path in Expander Graphs. CoRR abs/2307.06113 (2023) - [i85]Noga Alon:
On bipartite coverings of graphs and multigraphs. CoRR abs/2307.16784 (2023) - [i84]Noga Alon, Dmitrii Avdiukhin, Dor Elboim, Orr Fischer, Grigory Yaroslavtsev:
Optimal Sample Complexity of Contrastive Learning. CoRR abs/2312.00379 (2023) - [i83]Noga Alon, Olivier Bousquet, Kasper Green Larsen, Shay Moran, Shlomo Moran:
Diagonalization Games. Electron. Colloquium Comput. Complex. TR23 (2023) - 2022
- [j426]Noga Alon, Colin Defant, Noah Kravitz:
The runsort permuton. Adv. Appl. Math. 139: 102361 (2022) - [j425]Noga Alon, Clara Shikhelman:
Additive Approximation of Generalized Turán Questions. Algorithmica 84(2): 464-481 (2022) - [j424]Noga Alon, Asaf Nachmias, Matan Shalev:
The diameter of the uniform spanning tree of dense graphs. Comb. Probab. Comput. 31(6): 1010-1030 (2022) - [j423]Noga Alon, Bruno Jartoux, Chaya Keller, Shakhar Smorodinsky, Yelena Yuditsky:
The ε-t-Net Problem. Discret. Comput. Geom. 68(2): 618-644 (2022) - [j422]Noga Alon, Jeremy Chizewer:
On the hat guessing number of graphs. Discret. Math. 345(4): 112785 (2022) - [j421]Noga Alon, Mark Bun, Roi Livni, Maryanthe Malliaris, Shay Moran:
Private and Online Learnability Are Equivalent. J. ACM 69(4): 28:1-28:34 (2022) - [i82]Noga Alon:
Implicit representation of sparse hereditary families. CoRR abs/2201.00328 (2022) - [i81]Noga Alon, Benjamin Gunby, Xiaoyu He, Eran Shmaya, Eilon Solan:
Identifying the Deviator. CoRR abs/2203.03744 (2022) - [i80]Noga Alon, Gabriela Bourla, Ben Graham, Xiaoyu He, Noah Kravitz:
Logarithmically larger deletion codes of all distances. CoRR abs/2209.11882 (2022) - [i79]Noga Alon, Peter Frankl:
Turán graphs with bounded matching number. CoRR abs/2210.15076 (2022) - [i78]Noga Alon, Emil Powierski, Michael Savery, Alex Scott, Elizabeth Wilmer:
Invertibility of digraphs and tournaments. CoRR abs/2212.11969 (2022) - 2021
- [j420]Noga Alon, Guy Moshkovitz:
Limitations on regularity lemmas for clustering graphs. Adv. Appl. Math. 124: 102135 (2021) - [j419]Noga Alon:
Explicit Expanders of Every Degree and Size. Comb. 41(4): 447-463 (2021) - [j418]Noga Alon, Raimundo Briceño, Nishant Chandgotia, Alexander Magazinov, Yinon Spinka:
Mixing properties of colourings of the ℤd lattice. Comb. Probab. Comput. 30(3): 360-373 (2021) - [j417]Noga Alon, Sebastian M. Cioaba, Brandon D. Gilbert, Jack H. Koolen, Brendan D. McKay:
Addressing Johnson Graphs, Complete Multipartite Graphs, Odd Cycles, and Random Graphs. Exp. Math. 30(3): 372-382 (2021) - [j416]Noga Alon, Matija Bucic, Tom Kalvari, Eden Kuperwasser, Tibor Szabó:
List Ramsey numbers. J. Graph Theory 96(1): 109-128 (2021) - [j415]Noga Alon, Michael Krivelevich:
Divisible subdivisions. J. Graph Theory 98(4): 623-629 (2021) - [j414]Noga Alon, Yossi Azar, Mark Berlin:
The Price of Bounded Preemption. ACM Trans. Parallel Comput. 8(1): 3:1-3:21 (2021) - [c176]Noga Alon, Steve Hanneke, Ron Holzman, Shay Moran:
A Theory of PAC Learnability of Partial Concept Classes. FOCS 2021: 658-671 - [c175]Noga Alon, Andrei Graur:
Efficient Splitting of Necklaces. ICALP 2021: 14:1-14:17 - [c174]Noga Alon, Omri Ben-Eliezer, Yuval Dagan, Shay Moran, Moni Naor, Eylon Yogev:
Adversarial laws of large numbers and optimal regret in online classification. STOC 2021: 447-455 - [c173]Noga Alon, Alon Gonen, Elad Hazan, Shay Moran:
Boosting simple learners. STOC 2021: 481-489 - [i77]Noga Alon, Omri Ben-Eliezer, Yuval Dagan, Shay Moran, Moni Naor, Eylon Yogev:
Adversarial Laws of Large Numbers and Optimal Regret in Online Classification. CoRR abs/2101.09054 (2021) - [i76]Noga Alon, Jeremy Chizewer:
On the Hat Guessing Number of Graphs. CoRR abs/2107.05995 (2021) - [i75]Noga Alon, Steve Hanneke, Ron Holzman, Shay Moran:
A Theory of PAC Learnability of Partial Concept Classes. CoRR abs/2107.08444 (2021) - [i74]Noga Alon:
Partitioning all k-subsets into r-wise intersecting families. CoRR abs/2107.12741 (2021) - 2020
- [j413]Noga Alon, Mrinal Kumar, Ben Lee Volk:
Unbalancing Sets and An Almost Quadratic Lower Bound for Syntactically Multilinear Arithmetic Circuits. Comb. 40(2): 149-178 (2020) - [j412]Noga Alon, Dan Hefetz, Michael Krivelevich, Mykhaylo Tyomkyn:
Edge-statistics on large graphs. Comb. Probab. Comput. 29(2): 163-189 (2020) - [j411]Noga Alon, Colin Defant:
Isoperimetry, stability, and irredundance in direct products. Discret. Math. 343(7): 111902 (2020) - [j410]Noga Alon, Shoni Gilboa, Shay Gueron:
A probabilistic variant of Sperner 's theorem and of maximal r-cover free families. Discret. Math. 343(10): 112027 (2020) - [j409]Noga Alon, Ryan Alweiss:
On the product dimension of clique factors. Eur. J. Comb. 86: 103097 (2020) - [j408]Noga Alon, Omri Ben-Eliezer, Chong Shangguan, Itzhak Tamo:
The hat guessing number of graphs. J. Comb. Theory B 144: 119-149 (2020) - [j407]Noga Alon, Jørgen Bang-Jensen, Stéphane Bessy:
Out-colourings of digraphs. J. Graph Theory 93(1): 88-112 (2020) - [j406]Noga Alon, Omri Ben-Eliezer:
Efficient Removal Lemmas for Matrices. Order 37(1): 83-101 (2020) - [j405]Noga Alon, Jonathan D. Cohen, Thomas L. Griffiths, Pasin Manurangsi, Daniel Reichman, Igor Shinkar, Tal Wagner, Alexander Y. Ku:
Multitasking Capacity: Hardness Results and Improved Constructions. SIAM J. Discret. Math. 34(1): 885-903 (2020) - [j404]Noga Alon, Elchanan Mossel, Robin Pemantle:
Distributed Corruption Detection in Networks. Theory Comput. 16: 1-23 (2020) - [c172]Noga Alon, Sepehr Assadi:
Palette Sparsification Beyond (Δ+1) Vertex Coloring. APPROX-RANDOM 2020: 6:1-6:22 - [c171]Noga Alon, Amos Beimel, Shay Moran, Uri Stemmer:
Closure Properties for Private Classification and Online Prediction. COLT 2020: 119-152 - [c170]Noga Alon, Yossi Azar, Danny Vainstein:
Hierarchical Clustering: A 0.585 Revenue Approximation. COLT 2020: 153-162 - [c169]Noga Alon, Bruno Jartoux, Chaya Keller, Shakhar Smorodinsky, Yelena Yuditsky:
The ε-t-Net Problem. SoCG 2020: 5:1-5:15 - [i73]Noga Alon, Adi Shraibman:
Algorithmic Number On the Forehead Protocols Yielding Dense Ruzsa-Szemerédi Graphs and Hypergraphs. CoRR abs/2001.00387 (2020) - [i72]Noga Alon, Alon Gonen, Elad Hazan, Shay Moran:
Boosting Simple Learners. CoRR abs/2001.11704 (2020) - [i71]Noga Alon, Amos Beimel, Shay Moran, Uri Stemmer:
Closure Properties for Private Classification and Online Prediction. CoRR abs/2003.04509 (2020) - [i70]Noga Alon, Bruno Jartoux, Chaya Keller, Shakhar Smorodinsky, Yelena Yuditsky:
The ε-t-Net Problem. CoRR abs/2003.07061 (2020) - [i69]Noga Alon:
Explicit expanders of every degree and size. CoRR abs/2003.11673 (2020) - [i68]Noga Alon, Yossi Azar, Danny Vainstein:
Hierarchical Clustering: a 0.585 Revenue Approximation. CoRR abs/2006.01933 (2020) - [i67]Noga Alon, Sepehr Assadi:
Palette Sparsification Beyond (Δ+1) Vertex Coloring. CoRR abs/2006.10456 (2020) - [i66]Noga Alon, Andrei Graur:
Efficient Splitting of Measures and Necklaces. CoRR abs/2006.16613 (2020) - [i65]Noga Alon, Colin Defant, Noah Kravitz:
Typical and Extremal Aspects of Friends-and-Strangers Graphs. CoRR abs/2009.07840 (2020)
2010 – 2019
- 2019
- [j403]Noga Alon, Mark Braverman, Klim Efremenko, Ran Gelles, Bernhard Haeupler:
Reliable communication over highly connected noisy networks. Distributed Comput. 32(6): 505-515 (2019) - [j402]Noga Alon, Clara Shikhelman:
H-free subgraphs of dense graphs maximizing the number of cliques and their blow-ups. Discret. Math. 342(4): 988-996 (2019) - [j401]Noga Alon, Guy Moshkovitz, Noam Solomon:
Traces of hypergraphs. J. Lond. Math. Soc. 100(2): 498-517 (2019) - [j400]Noga Alon, Nadav Sherman:
Induced Universal Hypergraphs. SIAM J. Discret. Math. 33(2): 629-642 (2019) - [j399]Noga Alon, Michal Feldman, Yishay Mansour, Sigal Oren, Moshe Tennenholtz:
Dynamics of Evolving Social Groups. ACM Trans. Economics and Comput. 7(3): 14:1-14:27 (2019) - [j398]Noga Alon, Boris Bukh, Yury Polyanskiy:
List-Decodable Zero-Rate Codes. IEEE Trans. Inf. Theory 65(3): 1657-1667 (2019) - [c168]Noga Alon, Shiri Chechik, Sarel Cohen:
Deterministic Combinatorial Replacement Paths and Distance Sensitivity Oracles. ICALP 2019: 12:1-12:14 - [c167]Noga Alon, Omri Ben-Eliezer, Chong Shangguan, Itzhak Tamo:
The Hat Guessing Number of Graphs. ISIT 2019: 490-494 - [c166]Raef Bassily, Shay Moran, Noga Alon:
Limits of Private Learning with Access to Public Data. NeurIPS 2019: 10342-10352 - [c165]Noga Alon, Roi Livni, Maryanthe Malliaris, Shay Moran:
Private PAC learning implies finite Littlestone dimension. STOC 2019: 852-860 - [i64]Noga Alon, Shiri Chechik, Sarel Cohen:
Deterministic Combinatorial Replacement Paths and Distance Sensitivity Oracles. CoRR abs/1905.07483 (2019) - [i63]Noga Alon, Shirshendu Ganguly, Nikhil Srivastava:
High-girth near-Ramanujan graphs with localized eigenvectors. CoRR abs/1908.03694 (2019) - [i62]Noga Alon, Raef Bassily, Shay Moran:
Limits of Private Learning with Access to Public Data. CoRR abs/1910.11519 (2019) - [i61]Noga Alon, Guy Moshkovitz:
On Generalized Regularity. CoRR abs/1911.02000 (2019) - 2018
- [j397]Noga Alon:
Uniformly Discrete Forests with Poor Visibility. Comb. Probab. Comput. 27(4): 442-448 (2018) - [j396]Ron Aharoni, Noga Alon, Michal Amir, Penny Haxell, Dan Hefetz, Zilin Jiang, Gal Kronenberg, Alon Naor:
Ramsey-nice families of graphs. Eur. J. Comb. 72: 29-44 (2018) - [j395]Noga Alon, Michael Krivelevich:
Clique coloring of dense random graphs. J. Graph Theory 88(3): 428-433 (2018) - [j394]Slava Bronfman, Noga Alon, Avinatan Hassidim, Assaf Romm:
Redesigning the Israeli Medical Internship Match. ACM Trans. Economics and Comput. 6(3-4): 21:1-21:18 (2018) - [c164]Noga Alon, Mrinal Kumar, Ben Lee Volk:
Unbalancing Sets and an Almost Quadratic Lower Bound for Syntactically Multilinear Arithmetic Circuits. CCC 2018: 11:1-11:16 - [c163]Noga Alon, Yossi Azar, Mark Berlin:
The Price of Bounded Preemption. SPAA 2018: 301-310 - [i60]Noga Alon, Roi Livni, Maryanthe Malliaris, Shay Moran:
Private PAC learning implies finite Littlestone dimension. CoRR abs/1806.00949 (2018) - [i59]Noga Alon, Igor Balla, Lior Gishboliner, Adva Mond, Frank Mousset:
The Minrank of Random Graphs over Arbitrary Fields. CoRR abs/1809.01873 (2018) - [i58]Noga Alon, Jonathan D. Cohen, Thomas L. Griffiths, Pasin Manurangsi, Daniel Reichman, Igor Shinkar, Tal Wagner, Alexander Y. Ku:
Multitasking Capacity: Hardness Results and Improved Constructions. CoRR abs/1809.02835 (2018) - [i57]Noga Alon, Omri Ben-Eliezer, Chong Shangguan, Itzhak Tamo:
The hat guessing number of graphs. CoRR abs/1812.09752 (2018) - 2017
- [j393]Noga Alon, Moran Feldman, Moshe Tennenholtz:
Revenue and Reserve Prices in a Probabilistic Single Item Auction. Algorithmica 77(1): 1-15 (2017) - [j392]Noga Alon, Tom Bohman, Hao Huang:
More on the Bipartite Decomposition of Random Graphs. J. Graph Theory 84(1): 45-52 (2017) - [j391]Noga Alon, Nicolò Cesa-Bianchi, Claudio Gentile, Shie Mannor, Yishay Mansour, Ohad Shamir:
Nonstochastic Multi-Armed Bandits with Graph-Structured Feedback. SIAM J. Comput. 46(6): 1785-1826 (2017) - [j390]Noga Alon, Guy Rutenberg:
Broadcast Transmission to Prioritizing Receivers. SIAM J. Discret. Math. 31(4): 2517-2529 (2017) - [j389]Noga Alon, Klim Efremenko, Benny Sudakov:
Testing Equality in Communication Graphs. IEEE Trans. Inf. Theory 63(11): 7569-7574 (2017) - [j388]Noga Alon, Jehoshua Bruck, Farzad Farnoud Hassanzadeh, Siddharth Jain:
Duplication Distance to the Root for Binary Sequences. IEEE Trans. Inf. Theory 63(12): 7793-7803 (2017) - [c162]Noga Alon, Omri Ben-Eliezer:
Efficient Removal Lemmas for Matrices. APPROX-RANDOM 2017: 25:1-25:18 - [c161]Noga Alon, Bo'az Klartag:
Optimal Compression of Approximate Inner Products and Dimension Reduction. FOCS 2017: 639-650 - [c160]Noga Alon, Omri Ben-Eliezer, Eldar Fischer:
Testing Hereditary Properties of Ordered Graphs and Matrices. FOCS 2017: 848-858 - [c159]Noga Alon, Moshe Babaioff, Yannai A. Gonczarowski, Yishay Mansour, Shay Moran, Amir Yehudayoff:
Submultiplicative Glivenko-Cantelli and Uniform Convergence of Revenues. NIPS 2017: 1656-1665 - [c158]Noga Alon, Daniel Reichman, Igor Shinkar, Tal Wagner, Sebastian Musslick, Jonathan D. Cohen, Tom Griffiths, Biswadip Dey, Kayhan Özcimder:
A graph-theoretic approach to multitasking. NIPS 2017: 2100-2109 - [c157]Noga Alon, Rajko Nenadov:
Optimal induced universal graphs for bounded-degree graphs. SODA 2017: 1149-1157 - [i56]Noga Alon, Omri Ben-Eliezer, Eldar Fischer:
Testing hereditary properties of ordered graphs and matrices. CoRR abs/1704.02367 (2017) - [i55]Noga Alon, Moshe Babaioff, Yannai A. Gonczarowski, Yishay Mansour, Shay Moran, Amir Yehudayoff:
Submultiplicative Glivenko-Cantelli and Uniform Convergence of Revenues. CoRR abs/1705.08430 (2017) - [i54]Noga Alon, Jørgen Bang-Jensen, Stéphane Bessy:
Out-colourings of Digraphs. CoRR abs/1706.06441 (2017) - [i53]Noga Alon, Boris Bukh, Yury Polyanskiy:
List-decodable zero-rate codes. CoRR abs/1710.10663 (2017) - [i52]Noga Alon, Omri Ben-Eliezer, Eldar Fischer:
Testing hereditary properties of ordered graphs and matrices. Electron. Colloquium Comput. Complex. TR17 (2017) - 2016
- [j387]Noga Alon, Rani Hod, Amit Weinstein:
On Active and Passive Testing. Comb. Probab. Comput. 25(1): 1-20 (2016) - [j386]Noga Alon, Omri Ben-Eliezer:
Local and global colorability of graphs. Discret. Math. 339(2): 428-442 (2016) - [j385]Noga Alon, Clara Shikhelman:
Many T copies in H-free graphs. J. Comb. Theory B 121: 146-172 (2016) - [j384]Noga Alon:
High girth augmented trees are huge. J. Comb. Theory A 144: 7-15 (2016) - [j383]Ron Aharoni, Noga Alon, Eli Berger:
Eigenvalues of K1, k-Free Graphs and the Connectivity of Their Independence Complexes. J. Graph Theory 83(4): 384-391 (2016) - [j382]Noga Alon, Humberto Naves, Benny Sudakov:
On the Maximum Quartet Distance between Phylogenetic Trees. SIAM J. Discret. Math. 30(2): 718-735 (2016) - [j381]Emmanuel Abbe, Noga Alon, Afonso S. Bandeira, Colin Sandon:
Linear Boolean Classification, Coding and the Critical Problem. IEEE Trans. Inf. Theory 62(4): 1667-1673 (2016) - [c156]Noga Alon, Shay Moran, Amir Yehudayoff:
Sign rank versus VC dimension. COLT 2016: 47-80 - [c155]Noga Alon, Jehoshua Bruck, Farzad Farnoud, Siddharth Jain:
On the duplication distance of binary strings. ISIT 2016: 260-264 - [c154]Noga Alon, Mark Braverman, Klim Efremenko, Ran Gelles, Bernhard Haeupler:
Reliable Communication over Highly Connected Noisy Networks. PODC 2016: 165-173 - [c153]Noga Alon, Michal Feldman, Yishay Mansour, Sigal Oren, Moshe Tennenholtz:
Dynamics of Evolving Social Groups. EC 2016: 637-654 - [c152]Noga Alon, Humberto Naves, Benny Sudakov:
On the maximum quartet distance between phylogenetic trees. SODA 2016: 2095-2106 - [r2]Noga Alon, Raphael Yuster, Uri Zwick:
Color Coding. Encyclopedia of Algorithms 2016: 335-338 - [i51]Noga Alon, Michal Feldman, Yishay Mansour, Sigal Oren, Moshe Tennenholtz:
Dynamics of Evolving Social Groups. CoRR abs/1605.09548 (2016) - [i50]Noga Alon, Omri Ben-Eliezer:
Removal Lemmas for Matrices. CoRR abs/1609.04235 (2016) - [i49]Noga Alon, Jehoshua Bruck, Farzad Farnoud, Siddharth Jain:
Duplication Distance to the Root for Binary Sequences. CoRR abs/1611.05537 (2016) - [i48]Noga Alon, Klim Efremenko, Benny Sudakov:
Testing Equality in Communication Graphs. Electron. Colloquium Comput. Complex. TR16 (2016) - 2015
- [j380]Noga Alon, Amit Weinstein:
Local Correction with Constant Error Rate. Algorithmica 71(2): 496-516 (2015) - [j379]Noga Alon, Gil Cohen:
On Rigid Matrices and U-Polynomials. Comput. Complex. 24(4): 851-879 (2015) - [j378]Jonathan Berant, Noga Alon, Ido Dagan, Jacob Goldberger:
Efficient Global Learning of Entailment Graphs. Comput. Linguistics 41(2): 249-291 (2015) - [j377]Noga Alon, Ohad N. Feldheim:
Drawing outerplanar graphs using three edge lengths. Comput. Geom. 48(3): 260-267 (2015) - [j376]Noga Alon, Jacob Fox:
Easily Testable Graph Properties. Comb. Probab. Comput. 24(4): 646-657 (2015) - [j375]Noga Alon, Clara Shikhelman:
Many T copies in H-free graphs. Electron. Notes Discret. Math. 49: 683-689 (2015) - [j374]Noga Alon:
Size and Degree Anti-Ramsey Numbers. Graphs Comb. 31(6): 1833-1839 (2015) - [j373]Noga Alon, Hagit Attiya, Shlomi Dolev, Swan Dubois, Maria Potop-Butucaru, Sébastien Tixeuil:
Practically stabilizing SWMR atomic memory in message-passing systems. J. Comput. Syst. Sci. 81(4): 692-701 (2015) - [j372]Noga Alon:
Bipartite decomposition of random graphs. J. Comb. Theory B 113: 220-235 (2015) - [j371]Noga Alon, Shagnik Das, Roman Glebov, Benny Sudakov:
Comparable pairs in families of sets. J. Comb. Theory B 115: 164-185 (2015) - [j370]Noga Alon, Abbas Mehrabian:
Chasing a Fast Robber on Planar Graphs and Random Graphs. J. Graph Theory 78(2): 81-96 (2015) - [j369]Noga Alon, Manu Basavaraju, L. Sunil Chandran, Rogers Mathew, Deepak Rajendraprasad:
Separation Dimension of Bounded Degree Graphs. SIAM J. Discret. Math. 29(1): 59-64 (2015) - [j368]Noga Alon, Robert Bredereck, Jiehua Chen, Stefan Kratsch, Rolf Niedermeier, Gerhard J. Woeginger:
How to Put Through Your Agenda in Collective Binary Decisions. ACM Trans. Economics and Comput. 4(1): 5:1-5:28 (2015) - [c151]Noga Alon, Nicolò Cesa-Bianchi, Ofer Dekel, Tomer Koren:
Online Learning with Feedback Graphs: Beyond Bandits. COLT 2015: 23-35 - [c150]Noga Alon, Noam Nisan, Ran Raz, Omri Weinstein:
Welfare Maximization with Limited Interaction. FOCS 2015: 1499-1512 - [c149]Noga Alon, Michal Feldman, Omer Lev, Moshe Tennenholtz:
How Robust Is the Wisdom of the Crowds? IJCAI 2015: 2055-2061 - [c148]Slava Bronfman, Noga Alon, Avinatan Hassidim, Assaf Romm:
Redesigning the Israeli Medical Internship Match. EC 2015: 753-754 - [i47]Noga Alon, Nicolò Cesa-Bianchi, Ofer Dekel, Tomer Koren:
Online Learning with Feedback Graphs: Beyond Bandits. CoRR abs/1502.07617 (2015) - [i46]Noga Alon, Noam Nisan, Ran Raz, Omri Weinstein:
Welfare Maximization with Limited Interaction. CoRR abs/1504.01780 (2015) - [i45]Noga Alon, Humberto Naves, Benny Sudakov:
On the maximum quartet distance between phylogenetic trees. CoRR abs/1505.04344 (2015) - [i44]Noga Alon, Elchanan Mossel, Robin Pemantle:
Corruption Detection on Networks. CoRR abs/1505.05637 (2015) - [i43]Noga Alon, Mark Braverman, Klim Efremenko, Ran Gelles, Bernhard Haeupler:
Reliable Communication over Highly Connected Noisy Networks. Electron. Colloquium Comput. Complex. TR15 (2015) - [i42]Noga Alon, Noam Nisan, Ran Raz, Omri Weinstein:
Welfare Maximization with Limited Interaction. Electron. Colloquium Comput. Complex. TR15 (2015) - 2014
- [j367]Noga Alon, Pawel Pralat:
Chasing robbers on random geometric graphs - An alternative approach. Discret. Appl. Math. 178: 149-152 (2014) - [j366]Noga Alon, Andrey Kupavskii:
Two notions of unit distance graphs. J. Comb. Theory A 125: 1-17 (2014) - [j365]Noga Alon, Harout K. Aydinian, Hao Huang:
Maximizing the Number of Nonnegative Subsets. SIAM J. Discret. Math. 28(2): 811-816 (2014) - [j364]Noga Alon, Sagi Snir, Raphael Yuster:
On the Compatibility of Quartet Trees. SIAM J. Discret. Math. 28(3): 1493-1507 (2014) - [j363]Noga Alon, Erik D. Demaine, MohammadTaghi Hajiaghayi, Panagiotis Kanellopoulos, Tom Leighton:
Correction: Basic Network Creation Games. SIAM J. Discret. Math. 28(3): 1638-1640 (2014) - [c147]Noga Alon, Troy Lee, Adi Shraibman:
The Cover Number of a Matrix and its Algorithmic Applications. APPROX-RANDOM 2014: 34-47 - [c146]Emmanuel Abbe, Noga Alon, Afonso S. Bandeira:
Linear Boolean classification, coding and "the critical problem". ISIT 2014: 1231-1235 - [c145]Noga Alon, Sagi Snir, Raphael Yuster:
On the compatibility of quartet trees. SODA 2014: 535-545 - [c144]Noga Alon, Mohsen Ghaffari, Bernhard Haeupler, Majid Khabbazian:
Broadcast Throughput in Radio Networks: Routing vs. Network Coding. SODA 2014: 1831-1843 - [i41]Emmanuel Abbe, Noga Alon, Afonso S. Bandeira:
Linear Boolean classification, coding and "the critical problem". CoRR abs/1401.6528 (2014) - [i40]Noga Alon, Manu Basavaraju, L. Sunil Chandran, Rogers Mathew, Deepak Rajendraprasad:
Separation dimension of bounded degree graphs. CoRR abs/1407.5075 (2014) - [i39]Noga Alon, Nicolò Cesa-Bianchi, Claudio Gentile, Shie Mannor, Yishay Mansour, Ohad Shamir:
Nonstochastic Multi-Armed Bandits with Graph-Structured Feedback. CoRR abs/1409.8428 (2014) - [i38]Noga Alon, Shay Moran, Amir Yehudayoff:
Sign rank, VC dimension and spectral gaps. Electron. Colloquium Comput. Complex. TR14 (2014) - 2013
- [j362]Noga Alon, Amir Shpilka, Christopher Umans:
On sunflowers and matrix multiplication. Comput. Complex. 22(2): 219-243 (2013) - [j361]Yehuda Afek, Noga Alon, Ziv Bar-Joseph, Alejandro Cornejo, Bernhard Haeupler, Fabian Kuhn:
Beeping a maximal independent set. Distributed Comput. 26(4): 195-208 (2013) - [j360]Noga Alon:
The chromatic number of random Cayley graphs. Eur. J. Comb. 34(8): 1232-1243 (2013) - [j359]Noga Alon:
Restricted Integer Partition Functions. Integers 13: A16 (2013) - [j358]Noga Alon, Raphael Yuster:
Matrix sparsification and nested dissection over arbitrary fields. J. ACM 60(4): 25:1-25:18 (2013) - [j357]Noga Alon, Raphael Yuster:
The Turán number of sparse spanning graphs. J. Comb. Theory B 103(3): 337-343 (2013) - [j356]Noga Alon:
A Note on Degenerate and Spectrally Degenerate Graphs. J. Graph Theory 72(1): 1-6 (2013) - [j355]Noga Alon, Eric Blais, Sourav Chakraborty, David García-Soriano, Arie Matsliah:
Nearly Tight Bounds for Testing Function Isomorphism. SIAM J. Comput. 42(2): 459-493 (2013) - [j354]Noga Alon, Yuval Emek, Michal Feldman, Moshe Tennenholtz:
Adversarial Leakage in Games. SIAM J. Discret. Math. 27(1): 363-385 (2013) - [j353]Noga Alon:
Minimizing the Number of Carries in Addition. SIAM J. Discret. Math. 27(1): 562-566 (2013) - [j352]Noga Alon, Erik D. Demaine, Mohammad Taghi Hajiaghayi, Tom Leighton:
Basic Network Creation Games. SIAM J. Discret. Math. 27(2): 656-668 (2013) - [j351]Noga Alon, Shachar Lovett:
Almost k-Wise vs. k-Wise Independent Permutations, and Uniformity for General Group Actions. Theory Comput. 9: 559-577 (2013) - [c143]Noga Alon, Dvir Falik, Reshef Meir, Moshe Tennenholtz:
Bundling Attacks in Judgment Aggregation. AAAI 2013: 39-45 - [c142]Noga Alon, Reshef Meir, Moshe Tennenholtz:
The Value of Ignorance about the Number of Players. AAAI (Late-Breaking Developments) 2013 - [c141]Noga Alon, Robert Bredereck, Jiehua Chen, Stefan Kratsch, Rolf Niedermeier, Gerhard J. Woeginger:
How to Put through Your Agenda in Collective Binary Decisions. ADT 2013: 30-44 - [c140]Noga Alon, Gil Cohen:
On Rigid Matrices and U-polynomials. CCC 2013: 197-206 - [c139]Noga Alon, Nicolò Cesa-Bianchi, Claudio Gentile, Yishay Mansour:
From Bandits to Experts: A Tale of Domination and Independence. NIPS 2013: 1610-1618 - [c138]Noga Alon, Yishay Mansour, Moshe Tennenholtz:
Differential pricing with inequity aversion in social networks. EC 2013: 9-24 - [c137]Noga Alon, Troy Lee, Adi Shraibman, Santosh S. Vempala:
The approximate rank of a matrix and its algorithmic applications: approximate rank. STOC 2013: 675-684 - [c136]Noga Alon, Michal Feldman, Iftah Gamzu, Moshe Tennenholtz:
The Asymmetric Matrix Partition Problem. WINE 2013: 1-14 - [p2]Noga Alon:
Neighborly Families of Boxes and Bipartite Coverings. The Mathematics of Paul Erdős II 2013: 15-20 - [i37]Noga Alon, Andrey Kupavskii:
Two notions of unit distance graphs. CoRR abs/1306.3916 (2013) - [i36]Noga Alon, Nicolò Cesa-Bianchi, Claudio Gentile, Yishay Mansour:
From Bandits to Experts: A Tale of Domination and Independence. CoRR abs/1307.4564 (2013) - [i35]Noga Alon, Rani Hod, Amit Weinstein:
On active and passive testing. CoRR abs/1307.7364 (2013) - 2012
- [j350]Noga Alon, Keith E. Mellinger, Dhruv Mubayi, Jacques Verstraëte:
The de Bruijn-Erdős theorem for hypergraphs. Des. Codes Cryptogr. 65(3): 233-245 (2012) - [j349]Noga Alon:
A Non-linear Lower Bound for Planar Epsilon-nets. Discret. Comput. Geom. 47(2): 235-244 (2012) - [j348]Noga Alon, Alexandr V. Kostochka:
Dense uniform hypergraphs have high list chromatic number. Discret. Math. 312(14): 2119-2125 (2012) - [j347]Noga Alon, Amit Weinstein:
Local correction of juntas. Inf. Process. Lett. 112(6): 223-226 (2012) - [j346]Noga Alon, Hao Huang, Benny Sudakov:
Nonnegative k-sums, fractional covers, and probability of small deviations. J. Comb. Theory B 102(3): 784-796 (2012) - [j345]Noga Alon, Peter Frankl, Hao Huang, Vojtech Rödl, Andrzej Rucinski, Benny Sudakov:
Large matchings in uniform hypergraphs and the conjectures of Erdős and Samuels. J. Comb. Theory A 119(6): 1200-1215 (2012) - [j344]Noga Alon, Yuval Emek, Michal Feldman, Moshe Tennenholtz:
Bayesian ignorance. Theor. Comput. Sci. 452: 1-11 (2012) - [c135]Noga Alon, Shachar Lovett:
Almost K-Wise vs. K-Wise Independent Permutations, and Uniformity for General Group Actions. APPROX-RANDOM 2012: 350-361 - [c134]Noga Alon, Amir Shpilka, Christopher Umans:
On Sunflowers and Matrix Multiplication. CCC 2012: 214-223 - [c133]Noga Alon, Moshe Babaioff, Ron Karidi, Ron Lavi, Moshe Tennenholtz:
Sequential voting with externalities: herding in social networks. EC 2012: 36 - [c132]Noga Alon, Ronitt Rubinfeld, Shai Vardi, Ning Xie:
Space-efficient local computation algorithms. SODA 2012: 1132-1139 - [c131]Noga Alon, Ankur Moitra, Benny Sudakov:
Nearly complete graphs decomposable into large induced matchings and their applications. STOC 2012: 1079-1090 - [c130]Noga Alon, Iftah Gamzu, Moshe Tennenholtz:
Optimizing budget allocation among channels and influencers. WWW 2012: 381-388 - [i34]Yehuda Afek, Noga Alon, Ziv Bar-Joseph, Alejandro Cornejo, Bernhard Haeupler, Fabian Kuhn:
Beeping a Maximal Independent Set. CoRR abs/1206.0150 (2012) - [i33]Noga Alon, Amit Weinstein:
Local Correction with Constant Error Rate. CoRR abs/1210.5677 (2012) - [i32]Noga Alon, Gil Cohen:
On Rigid Matrices and Subspace Polynomials. Electron. Colloquium Comput. Complex. TR12 (2012) - [i31]Noga Alon, Santosh S. Vempala:
The Approximate Rank of a Matrix and its Algorithmic Applications. Electron. Colloquium Comput. Complex. TR12 (2012) - 2011
- [j343]Noga Alon, Gregory Z. Gutin, Eun Jung Kim, Stefan Szeider, Anders Yeo:
Solving MAX-r-SAT Above a Tight Lower Bound. Algorithmica 61(3): 638-655 (2011) - [j342]Noga Alon, Simi Haber, Michael Krivelevich:
The Number of f-Matchings in Almost Every Tree is a Zero Residue. Electron. J. Comb. 18(1) (2011) - [j341]Noga Alon, Abbas Mehrabian:
On a Generalization of Meyniel's Conjecture on the Cops and Robbers Game. Electron. J. Comb. 18(1) (2011) - [j340]Noga Alon, Pawel Pralat:
Modular Orientations of Random and Quasi-Random Regular Graphs. Comb. Probab. Comput. 20(3): 321-329 (2011) - [j339]Noga Alon, Chen Avin, Michal Koucký, Gady Kozma, Zvi Lotker, Mark R. Tuttle:
Many Random Walks Are Faster Than One. Comb. Probab. Comput. 20(4): 481-502 (2011) - [j338]Noga Alon, József Balogh, Béla Bollobás, Robert Morris:
The structure of almost all graphs in a hereditary property. J. Comb. Theory B 101(2): 85-110 (2011) - [j337]Noga Alon, H. Tracy Hall, Christian Knauer, Rom Pinchasi, Raphael Yuster:
On graphs and algebraic graphs that do not contain cycles of length 4. J. Graph Theory 68(2): 91-102 (2011) - [j336]Noga Alon, Alexandr V. Kostochka:
Hypergraph list coloring and Euclidean Ramsey theory. Random Struct. Algorithms 39(3): 377-390 (2011) - [j335]Noga Alon, Dániel Marx:
Sparse Balanced Partitions and the Complexity of Subgraph Problems. SIAM J. Discret. Math. 25(2): 631-644 (2011) - [c129]Noga Alon:
List coloring and Euclidean Ramsey Theory. CCCG 2011 - [c128]Noga Alon, Yuval Emek, Michal Feldman, Moshe Tennenholtz:
Economical Graph Discovery. ICS 2011: 476-486 - [c127]Noga Alon, Hagit Attiya, Shlomi Dolev, Swan Dubois, Maria Potop-Butucaru, Sébastien Tixeuil:
Pragmatic Self-stabilization of Atomic Memory in Message-Passing Systems. SSS 2011: 19-31 - [c126]Noga Alon, Felix A. Fischer, Ariel D. Procaccia, Moshe Tennenholtz:
Sum of us: strategyproof selection from the selectors. TARK 2011: 101-110 - [c125]Yehuda Afek, Noga Alon, Ziv Bar-Joseph, Alejandro Cornejo, Bernhard Haeupler, Fabian Kuhn:
Beeping a Maximal Independent Set. DISC 2011: 32-50 - [i30]Yehuda Afek, Noga Alon, Ziv Bar-Joseph:
MIS on the fly. CoRR abs/1106.2126 (2011) - [i29]Noga Alon, Amit Weinstein:
Local Correction of Boolean Functions. CoRR abs/1109.3639 (2011) - [i28]Noga Alon, Ronitt Rubinfeld, Shai Vardi, Ning Xie:
Space-efficient Local Computation Algorithms. CoRR abs/1109.6178 (2011) - [i27]Noga Alon, Jacob Fox:
Testing perfection is hard. CoRR abs/1110.2828 (2011) - [i26]Noga Alon, Ankur Moitra, Benny Sudakov:
Nearly Complete Graphs Decomposable into Large Induced Matchings and their Applications. CoRR abs/1111.0253 (2011) - [i25]Noga Alon, Shachar Lovett:
Almost k-wise vs. k-wise independent permutations, and uniformity for general group actions. Electron. Colloquium Comput. Complex. TR11 (2011) - [i24]Noga Alon, Amir Shpilka, Christopher Umans:
On Sunflowers and Matrix Multiplication. Electron. Colloquium Comput. Complex. TR11 (2011) - 2010
- [j334]Noga Alon, Ehsan Chiniforooshan, Vasek Chvátal, François Genest:
Another Abstraction of the Erdös-Szekeres Happy End Theorem. Electron. J. Comb. 17(1) (2010) - [j333]Noga Alon, Dan Hefetz, Michael Krivelevich:
Playing to Retain the Advantage. Comb. Probab. Comput. 19(4): 481-491 (2010) - [j332]Noga Alon, Béla Bollobás:
Introduction. Comb. Probab. Comput. 19(5-6): 641 (2010) - [j331]Noga Alon, Michal Feldman, Ariel D. Procaccia, Moshe Tennenholtz:
Walking in circles. Discret. Math. 310(23): 3432-3435 (2010) - [j330]Noga Alon, Michal Feldman, Ariel D. Procaccia, Moshe Tennenholtz:
A note on competitive diffusion through social networks. Inf. Process. Lett. 110(6): 221-225 (2010) - [j329]Noga Alon, Sonny Ben-Shimon, Michael Krivelevich:
A note on regular Ramsey graphs. J. Graph Theory 64(3): 244-249 (2010) - [j328]Noga Alon, Michal Feldman, Ariel D. Procaccia, Moshe Tennenholtz:
Strategyproof Approximation of the Minimax on Networks. Math. Oper. Res. 35(3): 513-526 (2010) - [j327]Noga Alon, Paul H. Edelman:
The inverse Banzhaf problem. Soc. Choice Welf. 34(3): 371-377 (2010) - [j326]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. SIAM J. Comput. 39(6): 2336-2362 (2010) - [j325]Noga Alon, Ohad N. Feldheim:
The Brunn--Minkowski Inequality and Nontrivial Cycles in the Discrete Torus. SIAM J. Discret. Math. 24(3): 892-894 (2010) - [j324]Noga Alon, Shai Gutner:
Balanced families of perfect hash functions and their applications. ACM Trans. Algorithms 6(3): 54:1-54:12 (2010) - [j323]Noga Alon, Benny Chor, Fabio Pardi, Anat Rapoport:
Approximate Maximum Parsimony and Ancestral Maximum Likelihood. IEEE ACM Trans. Comput. Biol. Bioinform. 7(1): 183-187 (2010) - [j322]Noga Alon, Simon Litsyn, Alexander Shpunt:
Typical peak sidelobe level of binary sequences. IEEE Trans. Inf. Theory 56(1): 545-554 (2010) - [c124]Noga Alon, Eric Blais:
Testing Boolean Function Isomorphism. APPROX-RANDOM 2010: 394-405 - [c123]Noga Alon:
Voting Paradoxes. COLT 2010: 27 - [c122]Noga Alon, Raphael Yuster:
Solving Linear Systems through Nested Dissection. FOCS 2010: 225-234 - [c121]Noga Alon:
A Non-linear Lower Bound for Planar Epsilon-Nets. FOCS 2010: 341-346 - [c120]Noga Alon, Yuval Emek, Michal Feldman, Moshe Tennenholtz:
Adversarial Leakage in Games. ICS 2010: 111-119 - [c119]Noga Alon, Yuval Emek, Michal Feldman, Moshe Tennenholtz:
Bayesian ignorance. PODC 2010: 384-391 - [c118]Noga Alon, Gregory Z. Gutin, Eun Jung Kim, Stefan Szeider, Anders Yeo:
Solving MAX-r-SAT Above a Tight Lower Bound. SODA 2010: 511-517 - [c117]Noga Alon, Erik D. Demaine, MohammadTaghi Hajiaghayi, Tom Leighton:
Basic network creation games. SPAA 2010: 106-113 - [c116]Noga Alon, Hagit Attiya, Shlomi Dolev, Swan Dubois, Maria Gradinariu, Sébastien Tixeuil:
Brief Announcement: Sharing Memory in a Self-stabilizing Manner. DISC 2010: 525-527 - [p1]Noga Alon:
On Constant Time Approximation of Parameters of Bounded Degree Graphs. Property Testing 2010: 234-239 - [i23]Noga Alon, Hagit Attiya, Shlomi Dolev, Swan Dubois, Maria Gradinariu, Sébastien Tixeuil:
Practically Stabilizing Atomic Memory. CoRR abs/1007.1802 (2010)
2000 – 2009
- 2009
- [j321]Noga Alon, Shai Gutner:
Linear Time Algorithms for Finding a Dominating Set of Fixed Size in Degenerated Graphs. Algorithmica 54(4): 544-556 (2009) - [j320]Noga Alon, Eyal Lubetzky:
Uniformly cross intersecting families. Comb. 29(4): 389-431 (2009) - [j319]Noga Alon, Béla Bollobás:
Introduction. Comb. Probab. Comput. 18(1-2): 1 (2009) - [j318]Noga Alon:
Perturbed Identity Matrices Have High Rank: Proof and Applications. Comb. Probab. Comput. 18(1-2): 3-15 (2009) - [j317]Noga Alon, József Balogh, Alexandr V. Kostochka, Wojciech Samotij:
Sizes of Induced Subgraphs of Ramsey Graphs. Comb. Probab. Comput. 18(4): 459-476 (2009) - [j316]Noga Alon:
Economical Elimination of Cycles in the Torus. Comb. Probab. Comput. 18(5): 619-627 (2009) - [j315]Noga Alon, Robert Berke, Kevin Buchin, Maike Buchin, Péter Csorba, Saswata Shannigrahi, Bettina Speckmann, Philipp Zumstein:
Polychromatic Colorings of Plane Graphs. Discret. Comput. Geom. 42(3): 421-442 (2009) - [j314]Dan Hefetz, Noga Alon, Michael Krivelevich:
Playing to retain the advantage. Electron. Notes Discret. Math. 34: 423-427 (2009) - [j313]Noga Alon, Uri Stav:
Stability-type results for hereditary properties. J. Graph Theory 62(1): 65-83 (2009) - [j312]Noga Alon, Baruch Awerbuch, Yossi Azar, Boaz Patt-Shamir:
Tell Me Who I Am: An Interactive Recommendation System. Theory Comput. Syst. 45(2): 261-279 (2009) - [j311]Noga Alon, Alexandr V. Kostochka:
Induced subgraphs with distinct sizes. Random Struct. Algorithms 34(1): 45-53 (2009) - [j310]Noga Alon, Eldar Fischer, Ilan Newman, Asaf Shapira:
A Combinatorial Characterization of the Testable Graph Properties: It's All About Regularity. SIAM J. Comput. 39(1): 143-167 (2009) - [j309]Noga Alon, Baruch Awerbuch, Yossi Azar, Niv Buchbinder, Joseph Naor:
The Online Set Cover Problem. SIAM J. Comput. 39(2): 361-370 (2009) - [j308]Noga Alon, Asaf Shapira, Uri Stav:
Can a Graph Have Distinct Regular Partitions? SIAM J. Discret. Math. 23(1): 278-287 (2009) - [j307]Noga Alon, Fedor V. Fomin, Gregory Z. Gutin, Michael Krivelevich, Saket Saurabh:
Spanning Directed Trees with Many Leaves. SIAM J. Discret. Math. 23(1): 466-476 (2009) - [j306]Noga Alon, Yossi Azar, Shai Gutner:
Admission control to minimize rejections and online set cover with repetitions. ACM Trans. Algorithms 6(1): 11:1-11:13 (2009) - [j305]Noga Alon, Uri Stav:
Hardness of edge-modification problems. Theor. Comput. Sci. 410(47-49): 4920-4927 (2009) - [j304]Noga Alon, Rani Hod:
Optimal Monotone Encodings. IEEE Trans. Inf. Theory 55(3): 1343-1353 (2009) - [c115]Noga Alon, Rina Panigrahy, Sergey Yekhanin:
Deterministic Approximation Algorithms for the Nearest Codeword Problem. APPROX-RANDOM 2009: 339-351 - [c114]Noga Alon, Eyal Lubetzky, Ori Gurel-Gurevich:
Choice-Memory Tradeoff in Allocations. FOCS 2009: 230-238 - [c113]Noga Alon, Daniel Lokshtanov, Saket Saurabh:
Fast FAST. ICALP (1) 2009: 49-58 - [c112]Noga Alon, Shai Gutner:
Balanced Hashing, Color Coding and Approximate Counting. IWPEC 2009: 1-16 - [c111]Noga Alon, Uriel Feige:
On the power of two, three and four probes. SODA 2009: 346-354 - [i22]Noga Alon, Rina Panigrahy, Sergey Yekhanin:
Deterministic approximation algorithms for the nearest codeword problem. Algebraic Methods in Computational Complexity 2009 - [i21]Noga Alon, Michal Feldman, Ariel D. Procaccia, Moshe Tennenholtz:
Strategyproof Approximation Mechanisms for Location on Networks. CoRR abs/0907.2049 (2009) - [i20]Noga Alon, Felix A. Fischer, Ariel D. Procaccia, Moshe Tennenholtz:
Sum of Us: Strategyproof Selection from the Selectors. CoRR abs/0910.4699 (2009) - [i19]Noga Alon, Shai Gutner:
Balanced Hashing, Color Coding and Approximate Counting. Electron. Colloquium Comput. Complex. TR09 (2009) - 2008
- [b3]Noga Alon, Joel H. Spencer:
The Probabilistic Method, Third Edition. Wiley-Interscience series in discrete mathematics and optimization, Wiley 2008, ISBN 978-0-470-17020-5, pp. I-XV, 1-352 - [j303]Noga Alon, Asaf Shapira:
A separation theorem in property testing. Comb. 28(3): 261-281 (2008) - [j302]Noga Alon, Shmuel Friedland:
The Maximum Number of Perfect Matchings in Graphs with a Given Degree Sequence. Electron. J. Comb. 15(1) (2008) - [j301]Noga Alon, Oded Schwartz, Asaf Shapira:
An Elementary Construction of Constant-Degree Expanders. Comb. Probab. Comput. 17(3): 319-327 (2008) - [j300]Noga Alon, Eli Berger:
The Grothendieck constant of random and pseudo-random graphs. Discret. Optim. 5(2): 323-327 (2008) - [j299]Noga Alon, Jaroslaw Grytczuk:
Breaking the rhythm on graphs. Discret. Math. 308(8): 1375-1380 (2008) - [j298]Noga Alon:
Problems and results in extremal combinatorics - II. Discret. Math. 308(19): 4460-4472 (2008) - [j297]Noga Alon, Adi Pinchasi, Rom Pinchasi:
An isoperimetric inequality in the universal cover of the punctured plane. Discret. Math. 308(23): 5691-5701 (2008) - [j296]Noga Alon, Shakhar Smorodinsky:
Conflict-Free colorings of Shallow Discs. Int. J. Comput. Geom. Appl. 18(6): 599-604 (2008) - [j295]Noga Alon, Haim Kaplan, Gabriel Nivasch, Micha Sharir, Shakhar Smorodinsky:
Weak ε-nets and interval chains. J. ACM 55(6): 28:1-28:32 (2008) - [j294]Noga Alon, Uri Stav:
The maximum edit distance from hereditary graph properties. J. Comb. Theory B 98(4): 672-697 (2008) - [j293]Noga Alon, Uri Stav:
What is the furthest graph from a hereditary property? Random Struct. Algorithms 33(1): 87-104 (2008) - [j292]Noga Alon, Asaf Shapira:
A Characterization of the (Natural) Graph Properties Testable with One-Sided Error. SIAM J. Comput. 37(6): 1703-1727 (2008) - [j291]Noga Alon, Asaf Shapira:
Every Monotone Graph Property Is Testable. SIAM J. Comput. 38(2): 505-522 (2008) - [j290]Noga Alon, Tali Kaufman, Michael Krivelevich, Dana Ron:
Testing Triangle-Freeness in General Graphs. SIAM J. Discret. Math. 22(2): 786-819 (2008) - [j289]Noga Alon, Michael Krivelevich, Benny Sudakov:
Large Nearly Regular Induced Subgraphs. SIAM J. Discret. Math. 22(4): 1325-1337 (2008) - [j288]Noga Alon, Pawel Pralat, Nicholas C. Wormald:
Cleaning Regular Graphs with Brushes. SIAM J. Discret. Math. 23(1): 233-250 (2008) - [j287]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 Trans. Algorithms 4(4): 46:1-46:21 (2008) - [c110]Noga Alon, Ido Ben-Eliezer, Michael Krivelevich:
Small Sample Spaces Cannot Fool Low Degree Polynomials. APPROX-RANDOM 2008: 266-275 - [c109]Noga Alon, Dan Halperin, Oren Nechushtan, Micha Sharir:
The complexity of the outer face in arrangements of random segments. SCG 2008: 69-78 - [c108]Noga Alon, Robert Berke, Kevin Buchin, Maike Buchin, Péter Csorba, Saswata Shannigrahi, Bettina Speckmann, Philipp Zumstein:
Polychromatic colorings of plane graphs. SCG 2008: 338-345 - [c107]Noga Alon, Asaf Nussboim:
k-Wise Independent Random Graphs. FOCS 2008: 813-822 - [c106]Noga Alon, Eyal Lubetzky, Uri Stav, Amit Weinstein, Avinatan Hassidim:
Broadcasting with Side Information. FOCS 2008: 823-832 - [c105]Noga Alon, Rani Hod:
Optimal Monotone Encodings. ICALP (1) 2008: 258-270 - [c104]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 - [c103]Noga Alon, Michael R. Capalbo:
Optimal universal graphs with deterministic embedding. SODA 2008: 373-378 - [c102]Noga Alon, Haim Kaplan, Gabriel Nivasch, Micha Sharir, Shakhar Smorodinsky:
Weak ε-nets and interval chains. SODA 2008: 1194-1203 - [c101]Noga Alon, Chen Avin, Michal Koucký, Gady Kozma, Zvi Lotker, Mark R. Tuttle:
Many random walks are faster than one. SPAA 2008: 119-128 - [r1]Noga Alon, Raphael Yuster, Uri Zwick:
Color Coding. Encyclopedia of Algorithms 2008 - [i18]Noga Alon, Fedor V. Fomin, Gregory Z. Gutin, Michael Krivelevich, Saket Saurabh:
Spanning directed trees with many leaves. CoRR abs/0803.0701 (2008) - [i17]Noga Alon, Yossi Azar, Shai Gutner:
Admission Control to Minimize Rejections and Online Set Cover with Repetitions. CoRR abs/0803.2842 (2008) - [i16]Noga Alon, Shai Gutner:
Balanced Families of Perfect Hash Functions and Their Applications. CoRR abs/0805.4300 (2008) - [i15]Noga Alon, Avinatan Hassidim, Eyal Lubetzky, Uri Stav, Amit Weinstein:
Broadcasting with side information. CoRR abs/0806.3246 (2008) - [i14]Noga Alon, Shai Gutner:
Linear Time Algorithms for Finding a Dominating Set of Fixed Size in Degenerated Graphs. CoRR abs/0806.4735 (2008) - [i13]Noga Alon, Sonny Ben-Shimon, Michael Krivelevich:
A note on regular Ramsey graphs. CoRR abs/0812.2386 (2008) - [i12]Noga Alon, Shai Gutner:
Kernels for the Dominating Set Problem on Graphs with an Excluded Minor. Electron. Colloquium Comput. Complex. TR08 (2008) - [i11]Noga Alon, Rina Panigrahy, Sergey Yekhanin:
Deterministic Approximation Algorithms for the Nearest Codeword Problem. Electron. Colloquium Comput. Complex. TR08 (2008) - 2007
- [j286]Noga Alon, Eyal Lubetzky:
Codes And Xor Graph Products. Comb. 27(1): 13-33 (2007) - [j285]Noga Alon, Michael Krivelevich, Benny Sudakov:
Embedding nearly-spanning bounded degree trees. Comb. 27(6): 629-644 (2007) - [j284]Noga Alon, Eyal Lubetzky:
Privileged users in zero-error transmission over a noisy channel. Comb. 27(6): 737-743 (2007) - [j283]Noga Alon, Vera Asodi:
Edge Colouring with Delays. Comb. Probab. Comput. 16(2): 173-191 (2007) - [j282]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) - [j281]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) - [j280]Nir Ailon, Noga Alon:
Hardness of fully dense problems. Inf. Comput. 205(8): 1117-1129 (2007) - [j279]Noga Alon, Eyal Lubetzky:
Independent sets in tensor graph powers. J. Graph Theory 54(1): 73-87 (2007) - [j278]Noga Alon, Béla Bollobás, András Gyárfás, Jenö Lehel, Alex D. Scott:
Maximum directed cuts in acyclic digraphs. J. Graph Theory 55(1): 1-13 (2007) - [j277]Noga Alon, Benny Sudakov:
On graphs with subgraphs having large independence numbers. J. Graph Theory 56(2): 149-157 (2007) - [j276]Noga Alon, Michael R. Capalbo:
Sparse universal graphs for bounded-degree graphs. Random Struct. Algorithms 31(2): 123-133 (2007) - [j275]Noga Alon, Toshiya Itoh, Tatsuya Nagatani:
On (epsilon, k)-min-wise independent permutations. Random Struct. Algorithms 31(3): 384-389 (2007) - [j274]Noga Alon, Eldar Fischer, Ilan Newman:
Efficient Testing of Bipartite Graphs for Forbidden Induced Subgraphs. SIAM J. Comput. 37(3): 959-976 (2007) - [j273]Noga Alon, Anja Krech, Tibor Szabó:
Turán's Theorem in the Hypercube. SIAM J. Discret. Math. 21(1): 66-72 (2007) - [j272]Noga Alon, Eyal Lubetzky:
Graph Powers, Delsarte, Hoffman, Ramsey, and Shannon. SIAM J. Discret. Math. 21(2): 329-348 (2007) - [j271]Noga Alon, Venkatesan Guruswami, Tali Kaufman, Madhu Sudan:
Guessing secrets efficiently via list decoding. ACM Trans. Algorithms 3(4): 42 (2007) - [j270]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) - [j269]Noga Alon, Vera Asodi:
Tracing Many Users With Almost No Rate Penalty. IEEE Trans. Inf. Theory 53(1): 437-439 (2007) - [c100]Noga Alon, Shai Gutner:
Linear Time Algorithms for Finding a Dominating Set of Fixed Size in Degenerated Graphs. COCOON 2007: 394-405 - [c99]Noga Alon, Asaf Shapira, Uri Stav:
Can a Graph Have Distinct Regular Partitions? COCOON 2007: 428-438 - [c98]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 - [c97]Noga Alon, Michael R. Capalbo:
Finding Disjoint Paths in Expanders Deterministically and Online. FOCS 2007: 518-524 - [c96]Noga Alon, Fedor V. Fomin, Gregory Z. Gutin, Michael Krivelevich, Saket Saurabh:
Better Algorithms and Bounds for Directed Maximum Leaf Problems. FSTTCS 2007: 316-327 - [c95]Noga Alon, Fedor V. Fomin, Gregory Z. Gutin, Michael Krivelevich, Saket Saurabh:
Parameterized Algorithms for Directed Maximum Leaf Problems. ICALP 2007: 352-362 - [c94]Noga Alon, Shai Gutner:
Balanced Families of Perfect Hash Functions and Their Applications. ICALP 2007: 435-446 - [c93]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 - [c92]Noga Alon, Oded Schwartz, Asaf Shapira:
An elementary construction of constant-degree expanders. SODA 2007: 454-458 - [c91]Noga Alon, Alexandr Andoni, Tali Kaufman, Kevin Matulef, Ronitt Rubinfeld, Ning Xie:
Testing k-wise and almost k-wise independence. STOC 2007: 496-505 - [c90]Amit Agarwal, Noga Alon, Moses Charikar:
Improved approximation for directed cut problems. STOC 2007: 671-680 - [i10]Noga Alon, Fedor V. Fomin, Gregory Z. Gutin, Michael Krivelevich, Saket Saurabh:
Better Algorithms and Bounds for Directed Maximum Leaf Problems. CoRR abs/0707.1095 (2007) - [i9]Noga Alon, Fedor V. Fomin, Gregory Z. Gutin, Michael Krivelevich, Saket Saurabh:
Parameterized Algorithms for Directed Maximum Leaf Problems. CoRR abs/cs/0702049 (2007) - 2006
- [j268]Noga Alon, Raphael Yuster:
The Number Of Orientations Having No Fixed Tournament. Comb. 26(1): 1-16 (2006) - [j267]Noga Alon, Asaf Shapira:
On An Extremal Hypergraph Problem Of Brown, Erdös And Sós. Comb. 26(6): 627-645 (2006) - [j266]Noga Alon, Benny Sudakov:
H-Free Graphs of Large Minimum Degree. Electron. J. Comb. 13(1) (2006) - [j265]Noga Alon, Yoshiharu Kohayakawa, Christian Mauduit, Carlos Gustavo T. de A. Moreira, Vojtech Rödl:
Measures of Pseudorandomness for Finite Sequences: Minimal Values. Comb. Probab. Comput. 15(1-2): 1-29 (2006) - [j264]Noga Alon:
Feasible Schedules for Rotating Transmissions. Comb. Probab. Comput. 15(5): 783-787 (2006) - [j263]Noga Alon, Asaf Shapira:
A Characterization of Easily Testable Induced Subgraphs. Comb. Probab. Comput. 15(6): 791-805 (2006) - [j262]Noga Alon:
Splitting digraphs. Comb. Probab. Comput. 15(6): 933-937 (2006) - [j261]Noga Alon, Fan R. K. Chung:
Explicit construction of linear sized tolerant networks. Discret. Math. 306(10-11): 1068-1071 (2006) - [j260]Noga Alon, Vera Asodi:
Tracing a single user. Eur. J. Comb. 27(8): 1227-1234 (2006) - [j259]Noga Alon, Vera Asodi, Charles Cantor, Simon Kasif, John Rachlin:
Multi-Node Graphs: A Framework for Multiplexed Biological Assays. J. Comput. Biol. 13(10): 1659-1672 (2006) - [j258]Noga Alon, Graham R. Brightwell, Hal A. Kierstead, Alexandr V. Kostochka, Peter Winkler:
Dominating sets in k-majority tournaments. J. Comb. Theory B 96(3): 374-387 (2006) - [j257]Noga Alon, Rados Radoicic, Benny Sudakov, Jan Vondrák:
A Ramsey-type result for the hypercube. J. Graph Theory 53(3): 196-208 (2006) - [j256]Noga Alon, Eitan Bachmat:
Regular graphs whose subgraphs tend to be acyclic. Random Struct. Algorithms 29(3): 324-337 (2006) - [j255]Noga Alon, Assaf Naor:
Approximating the Cut-Norm via Grothendieck's Inequality. SIAM J. Comput. 35(4): 787-803 (2006) - [j254]Noga Alon:
Ranking Tournaments. SIAM J. Discret. Math. 20(1): 137-142 (2006) - [j253]Noga Alon, Dana Moshkovitz, Shmuel Safra:
Algorithmic construction of sets for k-restrictions. ACM Trans. Algorithms 2(2): 153-177 (2006) - [j252]Noga Alon, Baruch Awerbuch, Yossi Azar, Niv Buchbinder, Joseph Naor:
A general approach to online network optimization problems. ACM Trans. Algorithms 2(4): 640-660 (2006) - [j251]Noga Alon, Eyal Lubetzky:
The Shannon capacity of a graph and the independence numbers of its powers. IEEE Trans. Inf. Theory 52(5): 2172-2176 (2006) - [c89]Noga Alon, Shakhar Smorodinsky:
Conflict-free colorings of shallow discs. SCG 2006: 41-43 - [c88]Noga Alon, Asaf Shapira, Benny Sudakov:
Additive Approximation for Edge-Deletion Problems (Abstract). ICALP (1) 2006: 1-2 - [c87]Noga Alon, Tali Kaufman, Michael Krivelevich, Dana Ron:
Testing triangle-freeness in general graphs. SODA 2006: 279-288 - [c86]Noga Alon, Baruch Awerbuch, Yossi Azar, Boaz Patt-Shamir:
Tell me who I am: an interactive recommendation system. SPAA 2006: 1-10 - [c85]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 - [i8]Noga Alon, Eyal Lubetzky:
The Shannon capacity of a graph and the independence numbers of its powers. CoRR abs/cs/0608021 (2006) - [i7]Noga Alon, Oded Schwartz, Asaf Shapira:
An Elementary Construction of Constant-Degree Expanders. Electron. Colloquium Comput. Complex. TR06 (2006) - 2005
- [j250]Noga Alon, Vojtech Rödl:
Sharp Bounds For Some Multicolor Ramsey Numbers. Comb. 25(2): 125-141 (2005) - [j249]Noga Alon, Michael Krivelevich, Joel Spencer, Tibor Szabó:
Discrepancy Games. Electron. J. Comb. 12 (2005) - [j248]Noga Alon, Michael Merritt, Omer Reingold, Gadi Taubenfeld, Rebecca N. Wright:
Tight bounds for shared memory systems accessed by Byzantine processes. Distributed Comput. 18(2): 99-109 (2005) - [j247]Noga Alon, Jaroslaw Grytczuk:
Nonrepetitive colorings of graphs. Electron. Notes Discret. Math. 22: 353-355 (2005) - [j246]Noga Alon, Raphael Yuster:
On a Hypergraph Matching Problem. Graphs Comb. 21(4): 377-384 (2005) - [j245]Noga Alon, János Pach, Rom Pinchasi, Rados Radoicic, Micha Sharir:
Crossing patterns of semi-algebraic sets. J. Comb. Theory A 111(2): 310-326 (2005) - [j244]Noga Alon, Vera Asodi:
Learning a Hidden Subgraph. SIAM J. Discret. Math. 18(4): 697-712 (2005) - [j243]Noga Alon, Tali Kaufman, Michael Krivelevich, Simon Litsyn, Dana Ron:
Testing Reed-Muller codes. IEEE Trans. Inf. Theory 51(11): 4032-4039 (2005) - [j242]Noga Alon, Asaf Shapira:
Linear Equations, Arithmetic Progressions and Hypergraph Property Testing. Theory Comput. 1(1): 177-216 (2005) - [c84]Noga Alon, Asaf Shapira, Benny Sudakov:
Additive Approximation for Edge-Deletion Problems. FOCS 2005: 419-428 - [c83]Noga Alon, Asaf Shapira:
A Characterization of the (natural) Graph Properties Testable with One-Sided Error. FOCS 2005: 429-438 - [c82]Noga Alon, Nick G. Duffield, Carsten Lund, Mikkel Thorup:
Estimating arbitrary subset sums with few probes. PODS 2005: 317-325 - [c81]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 - [c80]Noga Alon, Asaf Shapira:
Linear equations, arithmetic progressions and hypergraph property testing. SODA 2005: 708-717 - [c79]Noga Alon, Yossi Azar, Shai Gutner:
Admission control to minimize rejections and online set cover with repetitions. SPAA 2005: 238-244 - [c78]Noga Alon, Asaf Shapira:
Every monotone graph property is testable. STOC 2005: 128-137 - [c77]Noga Alon, Konstantin Makarychev, Yury Makarychev, Assaf Naor:
Quadratic forms on graphs. STOC 2005: 486-493 - [i6]Asaf Shapira, Noga Alon:
Homomorphisms in Graph Property Testing - A Survey. Electron. Colloquium Comput. Complex. TR05 (2005) - [i5]Noga Alon, Ilan Newman, Alexander Shen, Gábor Tardos, Nikolai K. Vereshchagin:
Partitioning multi-dimensional sets in a small number of "uniform" parts. Electron. Colloquium Comput. Complex. TR05 (2005) - 2004
- [j241]Alon Nilli:
Tight Estimates for Eigenvalues of Regular Graphs. Electron. J. Comb. 11(1) (2004) - [j240]Noga Alon, Uri Stav:
New Bounds on Parent-Identifying Codes: The Case of Multiple Parents. Comb. Probab. Comput. 13(6): 795-807 (2004) - [j239]Noga Alon, Gregory Z. Gutin, Michael Krivelevich:
Algorithms with large domination ratio. J. Algorithms 50(1): 118-131 (2004) - [j238]Noga Alon, Asaf Shapira:
Testing subgraphs in directed graphs. J. Comput. Syst. Sci. 69(3): 354-382 (2004) - [j237]Noga Alon, Gil Kaplan, Arieh Lev, Yehuda Roditty, Raphael Yuster:
Dense graphs are antimagic. J. Graph Theory 47(4): 297-309 (2004) - [j236]Noga Alon, Richard Beigel, Simon Kasif, Steven Rudich, Benny Sudakov:
Learning a Hidden Matching. SIAM J. Comput. 33(2): 487-501 (2004) - [j235]Noga Alon, Seannie Dar, Michal Parnas, Dana Ron:
Testing of Clustering. SIAM Rev. 46(2): 285-308 (2004) - [c76]Noga Alon, Vera Asodi:
Edge Coloring with Delays. APPROX-RANDOM 2004: 237-248 - [c75]Noga Alon, Vera Asodi:
Learning a Hidden Subgraph. ICALP 2004: 110-121 - [c74]Nathan Srebro, Noga Alon, Tommi S. Jaakkola:
Generalization Error Bounds for Collaborative Prediction with Low-Rank Matrices. NIPS 2004: 1321-1328 - [c73]Noga Alon, Baruch Awerbuch, Yossi Azar, Niv Buchbinder, Joseph Naor:
A general approach to online network optimization problems. SODA 2004: 577-586 - [c72]Noga Alon, Asaf Shapira:
A characterization of easily testable induced subgraphs. SODA 2004: 942-951 - [c71]Noga Alon, Assaf Naor:
Approximating the cut-norm via Grothendieck's inequality. STOC 2004: 72-80 - 2003
- [j234]Noga Alon, Michael Krivelevich, Benny Sudakov:
Tura'n Numbers of Bipartite Graphs and Related Ramsey-Type Questions. Comb. Probab. Comput. 12(5-6): 477-494 (2003) - [j233]Noga Alon, Guillaume Fertin, Arthur L. Liestman, Thomas C. Shermer, Ladislav Stacho:
Factor d-domatic colorings of graphs. Discret. Math. 262(1-3): 17-25 (2003) - [j232]Noga Alon:
Problems and results in extremal combinatorics--I. Discret. Math. 273(1-3): 31-53 (2003) - [j231]Noga Alon, Simon Litsyn, Raphael Yuster:
A Coding Theory Bound and Zero-Sum Square Matrices. Graphs Comb. 19(4): 449-457 (2003) - [j230]Noga Alon, Michael R. Capalbo:
Smaller Explicit Superconcentrators. Internet Math. 1(2): 151-163 (2003) - [j229]Noga Alon:
A simple algorithm for edge-coloring bipartite multigraphs. Inf. Process. Lett. 85(6): 301-302 (2003) - [j228]Noga Alon, Oded Goldreich, Yishay Mansour:
Almost k-wise independence versus k-wise independence. Inf. Process. Lett. 88(3): 107-110 (2003) - [j227]Noga Alon, Asaf Shapira:
Testing satisfiability. J. Algorithms 47(2): 87-103 (2003) - [j226]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) - [j225]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) - [j224]Noga Alon, Guoli Ding, Bogdan Oporowski, Dirk Vertigan:
Partitioning into graphs with only small components. J. Comb. Theory B 87(2): 231-243 (2003) - [j223]Noga Alon, Béla Bollobás, Michael Krivelevich, Benny Sudakov:
Maximum cuts and judicious partitions in graphs without short cycles. J. Comb. Theory B 88(2): 329-346 (2003) - [j222]Noga Alon, Gérard D. Cohen, Michael Krivelevich, Simon Litsyn:
Generalized hashing and parent-identifying codes. J. Comb. Theory A 104(1): 207-215 (2003) - [j221]Noga Alon, Michael Krivelevich, Benny Sudakov:
Induced subgraphs of prescribed size. J. Graph Theory 43(4): 239-251 (2003) - [j220]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) - [j219]Noga Alon, Seannie Dar, Michal Parnas, Dana Ron:
Testing of Clustering. SIAM J. Discret. Math. 16(3): 393-417 (2003) - [j218]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) - [c70]Noga Alon, Tali Kaufman, Michael Krivelevich, Simon Litsyn, Dana Ron:
Testing Low-Degree Polynomials over GF(2(. RANDOM-APPROX 2003: 188-199 - [c69]Noga Alon, Michael R. Capalbo:
Smaller explicit superconcentrators. SODA 2003: 340-346 - [c68]Noga Alon, Baruch Awerbuch, Yossi Azar, Niv Buchbinder, Joseph Naor:
The online set cover problem. STOC 2003: 100-105 - [c67]Noga Alon, Asaf Shapira:
Testing subgraphs in directed graphs. STOC 2003: 700-709 - 2002
- [j217]Noga Alon, Gil Kalai, Jirí Matousek, Roy Meshulam:
Transversal numbers for hypergraphs arising in geometry. Adv. Appl. Math. 29(1): 79-101 (2002) - [j216]Noga Alon:
Voting paradoxes and digraphs realizations. Adv. Appl. Math. 29(1): 126-135 (2002) - [j215]Noga Alon, Ayal Zaks:
Algorithmic Aspects of Acyclic Edge Colorings. Algorithmica 32(4): 611-614 (2002) - [j214]Noga Alon, Bojan Mohar:
The Chromatic Number Of Graph Powers. Comb. Probab. Comput. 11(1): 1-10 (2002) - [j213]Noga Alon, József Balogh, Béla Bollobás, Tamás Szabó:
Game domination number. Discret. Math. 256(1-2): 23-33 (2002) - [j212]Noga Alon:
Covering a hypergraph of subgraphs. Discret. Math. 257(2-3): 249-254 (2002) - [j211]Noga Alon, Tom Bohman, Ron Holzman, Daniel J. Kleitman:
On partitions of discrete boxes. Discret. Math. 257(2-3): 255-258 (2002) - [j210]Noga Alon, Shlomo Hoory, Nathan Linial:
The Moore Bound for Irregular Graphs. Graphs Comb. 18(1): 53-57 (2002) - [j209]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) - [j208]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) - [j207]Noga Alon, Paul Erdös, David S. Gunderson, Michael Molloy:
A Ramsey-type problem and the Turán numbers. J. Graph Theory 40(2): 120-129 (2002) - [j206]Noga Alon, Benjamin Doerr, Tomasz Luczak, Tomasz Schoen:
On the discrepancy of combinatorial rectangles. Random Struct. Algorithms 21(3-4): 205-215 (2002) - [j205]Noga Alon, Jaroslaw Grytczuk, Mariusz Haluszczak, Oliver Riordan:
Nonrepetitive colorings of graphs. Random Struct. Algorithms 21(3-4): 336-346 (2002) - [j204]Noga Alon:
Testing subgraphs in large graphs. Random Struct. Algorithms 21(3-4): 359-370 (2002) - [j203]Noga Alon, Michael Krivelevich:
Testing k-colorability. SIAM J. Discret. Math. 15(2): 211-227 (2002) - [c66]Noga Alon, Michael R. Capalbo:
Explicit Unique-Neighbor Expanders. FOCS 2002: 73- - [c65]Noga Alon, Richard Beigel, Simon Kasif, Steven Rudich, Benny Sudakov:
Learning a Hidden Matching. FOCS 2002: 197- - [c64]Noga Alon, Venkatesan Guruswami, Tali Kaufman, Madhu Sudan:
Guessing secrets efficiently via list decoding. SODA 2002: 254-262 - [c63]Noga Alon, Asaf Shapira:
Testing satisfiability. SODA 2002: 645-654 - [c62]Noga Alon, Wenceslas Fernandez de la Vega, Ravi Kannan, Marek Karpinski:
Random sampling and approximation of MAX-CSP problems. STOC 2002: 232-239 - [i4]Noga Alon, Oded Goldreich, Yishay Mansour:
Almost k-wise independence versus k-wise independence. Electron. Colloquium Comput. Complex. TR02 (2002) - 2001
- [j202]Noga Alon, János Pach, József Solymosi:
Ramsey-type Theorems with Forbidden Subgraphs. Comb. 21(2): 155-170 (2001) - [j201]Emanuela Fachini, Alon Nilli:
Recursive bounds for perfect hashing. Discret. Appl. Math. 111(3): 307-311 (2001) - [j200]Noga Alon, Hagit Last, Rom Pinchasi, Micha Sharir:
On the Complexity of Arrangements of Circles in the Plane. Discret. Comput. Geom. 26(4): 465-492 (2001) - [j199]Noga Alon, Vanessa Teague, Nicholas C. Wormald:
Linear Arboricity and Linear k-Arboricity of Regular Graphs. Graphs Comb. 17(1): 11-16 (2001) - [j198]Noga Alon, László Lovász:
Unextendible Product Bases. J. Comb. Theory A 95(1): 169-179 (2001) - [j197]Noga Alon, Eldar Fischer, Mario Szegedy:
Parent-Identifying Codes. J. Comb. Theory A 95(2): 349-359 (2001) - [j196]Noga Alon, Benny Sudakov, Ayal Zaks:
Acyclic edge colorings of graphs. J. Graph Theory 37(3): 157-167 (2001) - [j195]Noga Alon, Dhruv Mubayi, Robin Thomas:
Large induced forests in sparse graphs. J. Graph Theory 38(3): 113-123 (2001) - [j194]Ilan Adler, Noga Alon, Sheldon M. Ross:
On the maximum number of Hamiltonian paths in tournaments. Random Struct. Algorithms 18(3): 291-296 (2001) - [j193]Noga Alon, Charles J. Colbourn, Alan C. H. Ling, Martin Tompa:
Equireplicate Balanced Binary Codes for Oligo Arrays. SIAM J. Discret. Math. 14(4): 481-497 (2001) - [j192]Noga Alon, Benny Sudakov, Uri Zwick:
Constructing Worst Case Instances for Semidefinite Programming Based Approximation Algorithms. SIAM J. Discret. Math. 15(1): 58-72 (2001) - [c61]Noga Alon, Richard Beigel:
Lower Bounds for Approximations by Low Degree Polynomials Over Zm. CCC 2001: 184-187 - [c60]Noga Alon:
Testing Subgraphs in Large Graphs. FOCS 2001: 434-441 - [c59]Noga Alon, Alexander Lubotzky, Avi Wigderson:
Semi-Direct Product in Groups and Zig-Zag Product in Graphs: Connections and Applications. FOCS 2001: 630-637 - [c58]Noga Alon, Tova Milo, Frank Neven, Dan Suciu, Victor Vianu:
Typechecking XML Views of Relational Databases. LICS 2001: 421-430 - [c57]Noga Alon, Tova Milo, Frank Neven, Dan Suciu, Victor Vianu:
XML with Data Values: Typechecking Revisited. PODS 2001 - [c56]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 - [c55]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 - [c54]Noga Alon, Benny Sudakov, Uri Zwick:
Constructing worst case instances for semidefinite programming based approximation algorithms. SODA 2001: 92-100 - [i3]Noga Alon, Wenceslas Fernandez de la Vega, Ravi Kannan, Marek Karpinski:
Random Sampling and Approximation of MAX-CSP Problems. Electron. Colloquium Comput. Complex. TR01 (2001) - 2000
- [b2]Noga Alon, Joel H. Spencer:
The Probabilistic Method, Second Edition. John Wiley 2000, ISBN 978-0-47137046-8 - [j191]Noga Alon, Eldar Fischer, Michael Krivelevich, Mario Szegedy:
Efficient Testing of Large Graphs. Comb. 20(4): 451-476 (2000) - [j190]Noga Alon, Benny Sudakov:
Bipartite Subgraphs And The Smallest Eigenvalue. Comb. Probab. Comput. 9(1): 1-12 (2000) - [j189]Noga Alon, Miklós Bóna, Joel Spencer:
Packing Ferrers Shapes. Comb. Probab. Comput. 9(3): 205-211 (2000) - [j188]Noga Alon, János Körner, Angelo Monti:
String Quartets In Binary. Comb. Probab. Comput. 9(5): 381-390 (2000) - [j187]Noga Alon, Emanuela Fachini, János Körner:
Locally Thin Set Families. Comb. Probab. Comput. 9(6): 481-488 (2000) - [j186]Alon Nilli:
Triangle-free graphs with large chromatic numbers. Discret. Math. 211: 261-262 (2000) - [j185]Noga Alon, Raphael Yuster:
EveryH-decomposition ofKnhas a Nearly Resolvable Alternative. Eur. J. Comb. 21(7): 839-845 (2000) - [j184]Noga Alon, Ehud Friedgut:
On the Number of Permutations Avoiding a Given Pattern. J. Comb. Theory A 89(1): 133-140 (2000) - [j183]Noga Alon, Kenneth A. Berman, Daniel J. Kleitman:
On a Problem in Shuffling. J. Comb. Theory A 91(1-2): 5-14 (2000) - [j182]Noga Alon, András Gyárfás, Miklós Ruszinkó:
Decreasing the diameter of bounded degree graphs. J. Graph Theory 35(3): 161-172 (2000) - [j181]Noga Alon, Michael Krivelevich, Paul D. Seymour:
Long cycles in critical graphs. J. Graph Theory 35(3): 193-196 (2000) - [j180]Noga Alon:
Degrees and choice numbers. Random Struct. Algorithms 16(4): 364-368 (2000) - [j179]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) - [c53]Noga Alon, Michael R. Capalbo, Yoshiharu Kohayakawa, Vojtech Rödl, Andrzej Rucinski, Endre Szemerédi:
Universality and Tolerance. FOCS 2000: 14-21 - [c52]Noga Alon, Seannie Dar, Michal Parnas, Dana Ron:
Testing of Clustering. FOCS 2000: 240-250 - [c51]Noga Alon, Haim Kaplan, Michael Krivelevich, Dahlia Malkhi, Julien P. Stern:
Scalable Secure Storage when Half the System Is Faulty. ICALP 2000: 576-587
1990 – 1999
- 1999
- [j178]Noga Alon, Eldar Fischer:
Refining the Graph Density Condition for the Existence of Almost K-factors. Ars Comb. 52 (1999) - [j177]Noga Alon, Michael Krivelevich, Benny Sudakov:
List Coloring of Random and Pseudo-Random Graphs. Comb. 19(4): 453-472 (1999) - [j176]Noga Alon, Shmuel Onn:
Separable Partitions. Discret. Appl. Math. 91(1-3): 39-51 (1999) - [j175]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) - [j174]Noga Alon, Mario Szegedy:
Large Sets of Nearly Orthogonal Vectors. Graphs Comb. 15(1): 1-4 (1999) - [j173]Noga Alon, Martin Dietzfelbinger, Peter Bro Miltersen, Erez Petrank, Gábor Tardos:
Linear Hash Functions. J. ACM 46(5): 667-683 (1999) - [j172]Noga Alon, Benny Sudakov:
On Two Segmentation Problems. J. Algorithms 33(1): 173-184 (1999) - [j171]Noga Alon, Yossi Matias, Mario Szegedy:
The Space Complexity of Approximating the Frequency Moments. J. Comput. Syst. Sci. 58(1): 137-147 (1999) - [j170]Noga Alon, Lajos Rónyai, Tibor Szabó:
Norm-Graphs: Variations and Applications. J. Comb. Theory B 76(2): 280-290 (1999) - [j169]Noga Alon, Michael Krivelevich, Benny Sudakov:
Coloring Graphs with Sparse Neighborhoods. J. Comb. Theory B 77(1): 73-82 (1999) - [j168]Noga Alon, Imre Z. Ruzsa:
Non-averaging Subsets and Non-vanishing Transversals. J. Comb. Theory A 86(1): 1-13 (1999) - [j167]Alon Nilli:
Short odd cycles in 4-chromatic graphs. J. Graph Theory 31(2): 145-147 (1999) - [c50]Noga Alon, Michael Krivelevich, Ilan Newman, Mario Szegedy:
Regular Languages Are Testable with a Constant Number of Queries. FOCS 1999: 645-655 - [c49]Noga Alon, Eldar Fischer, Michael Krivelevich, Mario Szegedy:
Efficient Testing of Large Graphs. FOCS 1999: 656-666 - [c48]Noga Alon, Phillip B. Gibbons, Yossi Matias, Mario Szegedy:
Tracking Join and Self-Join Sizes in Limited Storage. PODS 1999: 10-20 - [c47]Noga Alon, Uri Arad, Yossi Azar:
Independent Sets in Hypergraphs with Applications to Routing via Fixed Paths. RANDOM-APPROX 1999: 16-27 - 1998
- [j166]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) - [j165]Noga Alon:
The Shannon Capacity of a Union. Comb. 18(3): 301-310 (1998) - [j164]Noga Alon, Vojtech Rödl, Andrzej Rucinski:
Perfect Matchings in ε-regular Graphs. Electron. J. Comb. 5 (1998) - [j163]Noga Alon, Ayal Zaks:
T-choosability in Graphs. Discret. Appl. Math. 82(1-3): 1-13 (1998) - [j162]Noga Alon:
Piercing d -Intervals. Discret. Comput. Geom. 19(3): 333-334 (1998) - [j161]Noga Alon, Eran Halperin:
Bipartite subgraphs of integer weighted graphs. Discret. Math. 181(1-3): 19-29 (1998) - [j160]Noga Alon:
On the Capacity of Digraphs. Eur. J. Comb. 19(1): 1-5 (1998) - [j159]Noga Alon, Ayal Zaks:
Progressions in Sequences of Nearly Consecutive Integers. J. Comb. Theory A 84(1): 99-109 (1998) - [j158]Noga Alon, Nabil Kahalé:
Approximating the independence number via the theta-function. Math. Program. 80: 253-264 (1998) - [j157]Noga Alon, Michael Krivelevich, Benny Sudakov:
Finding a large hidden clique in a random graph. Random Struct. Algorithms 13(3-4): 457-466 (1998) - [c46]Noga Alon:
Spectral Techniques in Graph Algorithms. LATIN 1998: 206-215 - [c45]Noga Alon, Michael Krivelevich, Benny Sudakov:
Finding a Large Hidden Clique in a Random Graph. SODA 1998: 594-598 - 1997
- [j156]Noga Alon, Raphael Yuster, Uri Zwick:
Finding and Counting Given Length Cycles. Algorithmica 17(3): 209-223 (1997) - [j155]Noga Alon, Aravind Srinivasan:
Improved Parallel Approximation of a Class of Integer Programming Problems. Algorithmica 17(4): 449-462 (1997) - [j154]Noga Alon, Michael Krivelevich:
The Concentration of the Chromatic Number of Random Graphs. Comb. 17(3): 303-313 (1997) - [j153]Noga Alon, Miklós Ruszinkó:
Short Certificates for Tournaments. Electron. J. Comb. 4(1) (1997) - [j152]Noga Alon, Daniel J. Kleitman:
A purely combinatorial proof of the Hadwiger Debrunner (p, q) Conjecture. Electron. J. Comb. 4(2) (1997) - [j151]Rudolf Ahlswede, Noga Alon, Péter L. Erdös, Miklós Ruszinkó, László A. Székely:
Intersecting Systems. Comb. Probab. Comput. 6(2): 127-137 (1997) - [j150]Noga Alon:
On the Edge-Expansion of Graphs. Comb. Probab. Comput. 6(2): 145-152 (1997) - [j149]Noga Alon, Zsolt Tuza, Margit Voigt:
Choosability and fractional chromatic numbers. Discret. Math. 165-166: 31-38 (1997) - [j148]Noga Alon:
Packings with large minimum kissing numbers. Discret. Math. 175(1-3): 249-251 (1997) - [j147]Noga Alon, Michael Krivelevich:
Constructive Bounds for a Ramsey-Type Problem. Graphs Comb. 13(3): 217-225 (1997) - [j146]Noga Alon, Shai Ben-David, Nicolò Cesa-Bianchi, David Haussler:
Scale-sensitive dimensions, uniform convergence, and learnability. J. ACM 44(4): 615-631 (1997) - [j145]Noga Alon, Dmitry N. Kozlov:
Coins with Arbitrary Weights. J. Algorithms 25(1): 162-176 (1997) - [j144]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) - [j143]Noga Alon, Michael Tarsi:
A Note on Graph Colorings and Graph Polynomials. J. Comb. Theory B 70(1): 197-201 (1997) - [j142]Noga Alon, Yair Caro, Raphael Yuster:
Covering the Edges of a Graph by a Prescribed Tree with Minimum Overlap. J. Comb. Theory B 71(2): 144-161 (1997) - [j141]Noga Alon, Jeong Han Kim:
On the Degree, Size, and Chromatic Index of a Uniform Hypergraph. J. Comb. Theory A 77(1): 165-170 (1997) - [j140]Noga Alon, Van H. Vu:
Anti-Hadamard Matrices, Coin Weighing, Threshold Gates, and Indecomposable Hypergraphs. J. Comb. Theory A 79(1): 133-160 (1997) - [j139]Noga Alon, Gregory Z. Gutin:
Properly colored Hamilton cycles in edge-colored complete graphs. Random Struct. Algorithms 11(2): 179-186 (1997) - [j138]Noga Alon, Nabil Kahalé:
A Spectral Technique for Coloring Random 3-Colorable Graphs. SIAM J. Comput. 26(6): 1733-1748 (1997) - [c44]Noga Alon, Yossi Azar, Gerhard J. Woeginger, Tal Yadid:
Approximation Schemes for Scheduling. SODA 1997: 493-500 - [c43]Noga Alon, Martin Dietzfelbinger, Peter Bro Miltersen, Erez Petrank, Gábor Tardos:
Is Linear Hashing Good? STOC 1997: 465-474 - 1996
- [j137]Noga Alon, Moni Naor:
Derandomization, Witnesses for Boolean Matrix Multiplication and Construction of Perfect Hash Functions. Algorithmica 16(4/5): 434-449 (1996) - [j136]Noga Alon:
Bipartite Subgraphs. Comb. 16(3): 301-311 (1996) - [j135]Noga Alon, Eldar Fischer:
2-factors in dense graphs. Discret. Math. 152(1-3): 13-23 (1996) - [j134]Noga Alon, Phillip G. Bradford, Rudolf Fleischer:
Matching Nuts and Bolts Faster. Inf. Process. Lett. 59(3): 123-127 (1996) - [j133]Noga Alon, Raphael Yuster:
H-Factors in Dense Graphs. J. Comb. Theory B 66(2): 269-282 (1996) - [j132]Noga Alon:
Disjoint Directed Cycles. J. Comb. Theory, Ser. B 68(2): 167-178 (1996) - [j131]Noga Alon, Michael R. Fellows, Donovan R. Hare:
Vertex transversals that dominate. J. Graph Theory 21(1): 21-31 (1996) - [j130]Noga Alon, Colin McDiarmid, Michael Molloy:
Edge-disjoint cycles in regular directed graphs. J. Graph Theory 22(3): 231-237 (1996) - [j129]Noga Alon, Paul Erdös, Ron Holzman, Michael Krivelevich:
On k-saturated graphs with restrictions on the degrees. J. Graph Theory 23(1): 1-20 (1996) - [j128]Noga Alon, Pierre Kelsen, Sanjeev Mahajan, Ramesh Hariharan:
Approximate Hypergraph Coloring. Nord. J. Comput. 3(4): 425-439 (1996) - [j127]Noga Alon:
Independence numbers of locally sparse graphs and a Ramsey type problem. Random Struct. Algorithms 9(3): 271-278 (1996) - [j126]Noga Alon, Alon Orlitsky:
Source coding and graph entropies. IEEE Trans. Inf. Theory 42(5): 1329-1339 (1996) - [j125]Noga Alon, Michael Luby:
A linear time erasure-resilient code with nearly optimal recovery. IEEE Trans. Inf. Theory 42(6): 1732-1736 (1996) - [c42]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 - [c41]Noga Alon, Dmitry N. Kozlov, Van H. Vu:
The Geometry of Coin-Weighing Problems. FOCS 1996: 524-532 - [c40]Noga Alon, Aravind Srinivasan:
Improved Parallel Approximation of a Class of Integer Programming Programming Problems. ICALP 1996: 562-573 - [c39]Noga Alon, Yossi Matias, Mario Szegedy:
The Space Complexity of Approximating the Frequency Moments. STOC 1996: 20-29 - [c38]Noga Alon:
Derandomization Via Small Sample Spaces (Abstract). SWAT 1996: 1-3 - 1995
- [j124]Noga Alon, Uriel Feige, Avi Wigderson, David Zuckerman:
Derandomized Graph Products. Comput. Complex. 5(1): 60-75 (1995) - [j123]Noga Alon, Moshe Dubiner:
A Lattice Point Problem and Additive Number Theory. Comb. 15(3): 301-309 (1995) - [j122]Noga Alon, Joel Spencer, Prasad Tetali:
Covering with Latin Transversals. Discret. Appl. Math. 57(1): 1-10 (1995) - [j121]Noga Alon, Gil Kalai:
Bounding the Piercing Number. Discret. Comput. Geom. 13: 245-256 (1995) - [j120]Noga Alon, Sridhar Rajagopalan, Subhash Suri:
Long Non-Crossing Configurations in the Plane. Fundam. Informaticae 22(4): 385-394 (1995) - [j119]Noga Alon, Yishay Mansour:
epsilon-Discrepancy Sets and Their Application for Interpolation of Sparse Polynomials. Inf. Process. Lett. 54(6): 337-342 (1995) - [j118]Noga Alon, Raphael Yuster, Uri Zwick:
Color-Coding. J. ACM 42(4): 844-856 (1995) - [j117]Noga Alon, Raphael Yuster:
The 123 Theorem and Its Extensions. J. Comb. Theory A 72(2): 322-331 (1995) - [j116]Noga Alon, Benny Sudakov:
Disjoint Systems. Random Struct. Algorithms 6(1): 13-20 (1995) - [j115]Noga Alon, Zsolt Tuza:
The Acyclic Orientation Game on Random Graphs. Random Struct. Algorithms 6(2/3): 261-268 (1995) - [j114]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) - [j113]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) - [j112]Noga Alon, Alon Orlitsky:
Repeated communication and Ramsey graphs. IEEE Trans. Inf. Theory 41(5): 1276-1289 (1995) - [c37]Noga Alon, Zvi Galil, Moti Yung:
Efficient Dynamic-Resharing "Verifiable Secret Sharing" Against Mobile Adversary. ESA 1995: 523-537 - [c36]Noga Alon, Jeff Edmonds, Michael Luby:
Linear Time Erasure Codes with Nearly Optimal Recovery (Extended Abstract). FOCS 1995: 512-519 - 1994
- [j111]Noga Alon:
Explicit Ramsey graphs and orthonormal labelings. Electron. J. Comb. 1 (1994) - [j110]Alon Nilli:
Perfect Hashing and Probability. Comb. Probab. Comput. 3: 407-409 (1994) - [j109]Pankaj K. Agarwal, Noga Alon, Boris Aronov, Subhash Suri:
Can Visibility Graphs Be Represented Compactly?. Discret. Comput. Geom. 12: 347-365 (1994) - [j108]Noga Alon:
Probabilistic methods in coloring and decomposition problems. Discret. Math. 127(1-3): 31-46 (1994) - [j107]Noga Alon:
Packing of partial designs. Graphs Comb. 10(1): 11-18 (1994) - [j106]Noga Alon, Nimrod Megiddo:
Parallel Linear Programming in Fixed Dimension Almost Surely in Constant Time. J. ACM 41(2): 422-434 (1994) - [j105]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) - [j104]Noga Alon, Pavel Pudlák:
Superconcentrators of Depths 2 and 3; Odd Levels Help (Rarely). J. Comput. Syst. Sci. 48(1): 194-202 (1994) - [j103]Noga Alon:
Subdivided graphs have linear ramsey numbers. J. Graph Theory 18(4): 343-347 (1994) - [j102]Noga Alon, Yuval Roichman:
Random Cayley Graphs and Expanders. Random Struct. Algorithms 5(2): 271-285 (1994) - [j101]Noga Alon, Jehoshua Bruck:
Explicit Constructions of Depth-2 Majority Circuits for Comparison and Addition. SIAM J. Discret. Math. 7(1): 1-8 (1994) - [j100]Noga Alon, Paul D. Seymour, Robin Thomas:
Planar Separators. SIAM J. Discret. Math. 7(2): 184-193 (1994) - [j99]Noga Alon, Fan R. K. Chung, Ronald L. Graham:
Routing Permutations on Graphs Via Matchings. SIAM J. Discret. Math. 7(3): 513-530 (1994) - [j98]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) - [j97]Noga Alon, Alon Orlitsky:
A lower bound on the expected length of one-to-one codes. IEEE Trans. Inf. Theory 40(5): 1670-1672 (1994) - [c35]Noga Alon, Raphael Yuster, Uri Zwick:
Finding and Counting Given Length Cycles (Extended Abstract). ESA 1994: 354-364 - [c34]Noga Alon, Alan M. Frieze, Dominic Welsh:
Polynomial time randomised approxmiation schemes for the Tutte polynomial of dense graphs. FOCS 1994: 24-35 - [c33]Noga Alon, Manuel Blum, Amos Fiat, Sampath Kannan, Moni Naor, Rafail Ostrovsky:
Matching Nuts and Bolts. SODA 1994: 690-696 - [c32]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 - [c31]Noga Alon, Nabil Kahalé:
A spectral technique for coloring random 3-colorable graphs (preliminary version). STOC 1994: 346-355 - [i2]Noga Alon, Alan M. Frieze, Dominic Welsh:
Polynomial Time Randomised Approximation Schemes for Tutte-Gröthendieck Invariants: The Dense Case. Electron. Colloquium Comput. Complex. TR94 (1994) - [i1]Noga Alon, Raphael Yuster, Uri Zwick:
Color-Coding. Electron. Colloquium Comput. Complex. TR94 (1994) - 1993
- [j96]Noga Alon, Raphael Yuster:
Threshold Functions for H-factors. Comb. Probab. Comput. 2: 137-144 (1993) - [j95]Noga Alon, Yossi Azar:
On-Line Steine Trees in the Euclidean Plane. Discret. Comput. Geom. 10: 113-121 (1993) - [j94]Noga Alon, Yair Caro, Ilia Krasikov:
Bisection of trees and sequences. Discret. Math. 114(1-3): 3-7 (1993) - [j93]Noga Alon, Zoltán Füredi:
Covering the Cube by Affine Hyperplanes. Eur. J. Comb. 14(2): 79-83 (1993) - [j92]Noga Alon, Yair Caro:
On three zero-sum Ramsey-type problems. J. Graph Theory 17(2): 177-192 (1993) - [j91]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) - [j90]Noga Alon, Moni Naor:
Coin-Flipping Games Immune Against Linear-Sized Coalitions. SIAM J. Comput. 22(2): 403-417 (1993) - [c30]Noga Alon, Sridhar Rajagopalan, Subhash Suri:
Long Non-Crossing Configurations in the Plane. SCG 1993: 257-263 - [c29]Pankaj K. Agarwal, Noga Alon, Boris Aronov, Subhash Suri:
Can Visibility Graphs be Represented Compactly? SCG 1993: 338-347 - [c28]Noga Alon, Benny Sudakov:
Disjoint Systems (Extended Abstract). Algebraic Coding 1993: 159-163 - [c27]Noga Alon, Shai Ben-David, Nicolò Cesa-Bianchi, David Haussler:
Scale-sensitive Dimensions, Uniform Convergence, and Learnability. FOCS 1993: 292-301 - [c26]Noga Alon, Fan R. K. Chung, Ronald L. Graham:
Routing permutations on graphs via matchings. STOC 1993: 583-591 - 1992
- [b1]Noga Alon, Joel Spencer:
The Probabilistic Method. John Wiley 1992, ISBN 0-471-53588-5 - [j89]Noga Alon, Michael Tarsi:
Colorings and orientations of graphs. Comb. 12(2): 125-134 (1992) - [j88]Noga Alon, Colin McDiarmid, Bruce A. Reed:
Star arboricity. Comb. 12(4): 375-380 (1992) - [j87]Noga Alon:
Choice Numbers of Graphs: a Probabilistic Approach. Comb. Probab. Comput. 1: 107-114 (1992) - [j86]Noga Alon, Imre Bárány, Zoltán Füredi, Daniel J. Kleitman:
Point Selections and Weak e-Nets for Convex Hulls. Comb. Probab. Comput. 1: 189-200 (1992) - [j85]Noga Alon:
Transmitting in the n-Dimensional Cube. Discret. Appl. Math. 37/38: 9-11 (1992) - [j84]Noga Alon, Daniel J. Kleitman:
Partitioning a rectangle into small perimeter rectangles. Discret. Math. 103(2): 111-119 (1992) - [j83]Noga Alon, Edward R. Scheinerman:
Generalized sum graphs. Graphs Comb. 8(1): 23-29 (1992) - [j82]Noga Alon, Zoltán Füredi:
Spanning subgraphs of random graphs. Graphs Comb. 8(1): 91-94 (1992) - [j81]Noga Alon, Raphael Yuster:
AlmostH-factors in dense graphs. Graphs Comb. 8(2): 95-102 (1992) - [j80]Noga Alon, Amotz Bar-Noy, Nathan Linial, David Peleg:
Single Round Simulation on Radio Networks. J. Algorithms 13(2): 188-210 (1992) - [j79]Noga Alon:
The String Chromatic Number of a Graph. Random Struct. Algorithms 3(1): 1-8 (1992) - [j78]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) - [j77]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 Trans. Inf. Theory 38(2): 509-516 (1992) - [c25]Noga Alon, Daniel J. Kleitman:
Piercing Convex Sets. SCG 1992: 157-160 - [c24]Noga Alon, Yossi Azar:
On-Line Steiner Trees in the Euclidean Plane. SCG 1992: 337-343 - [c23]Noga Alon, Yuval Roichman:
Random Cayley Graphs and Expanders (Abstract). Expanding Graphs 1992: 1-3 - [c22]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 - [c21]Noga Alon, Zvi Galil, Oded Margalit, Moni Naor:
Witnesses for Boolean Matrix Multiplication and for Shortest Paths. FOCS 1992: 417-426 - [c20]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 - [c19]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 - [c18]Noga Alon, Yossi Azar:
Comparison-Sorting and Selecting in Totally Monotone Matrices. SODA 1992: 403-408 - 1991
- [j76]Noga Alon, Yossi Azar:
Parallel comparison algorithms for approximation problems. Comb. 11(2): 97-122 (1991) - [j75]Alon Nilli:
On the second eigenvalue of a graph. Discret. Math. 91(2): 207-210 (1991) - [j74]Noga Alon, András Hajnal:
Ramsey graphs contain many distinct induced subgraphs. Graphs Comb. 7(1): 1-6 (1991) - [j73]Noga Alon, Daniel J. Kleitman, Richard J. Lipton, Roy Meshulam, Michael O. Rabin, Joel H. Spencer:
Set systems with no union of cardinality 0 modulom. Graphs Comb. 7(2): 97-99 (1991) - [j72]Noga Alon, A. K. Dewdney, Teunis J. Ott:
Efficient Simulation of Finite Automata by Neural Nets. J. ACM 38(2): 495-514 (1991) - [j71]Noga Alon, Amotz Bar-Noy, Nathan Linial, David Peleg:
A Lower Bound for Radio Broadcast. J. Comput. Syst. Sci. 43(2): 290-298 (1991) - [j70]Noga Alon, Richard A. Brualdi, Bryan L. Shader:
Multicolored forests in bipartite decompositions of graphs. J. Comb. Theory B 53(1): 143-148 (1991) - [j69]Noga Alon, Nathan Linial, Roy Meshulam:
Additive bases of vector spaces over prime fields. J. Comb. Theory A 57(2): 203-210 (1991) - [j68]Noga Alon, László Babai, Hiroshi Suzuki:
Multilinear polynomials and Frankl-Ray-Chaudhuri-Wilson type intersection theorems. J. Comb. Theory A 58(2): 165-180 (1991) - [j67]Noga Alon, Colin McDiarmid, Bruce A. Reed:
Acyclic Coloring of Graphs. Random Struct. Algorithms 2(3): 277-288 (1991) - [j66]Noga Alon:
A Parallel Algorithmic Version of the Local Lemma. Random Struct. Algorithms 2(4): 367-378 (1991) - [c17]Noga Alon, Richard M. Karp, David Peleg, Douglas B. West:
A Graph-Theoretic Game and its Application to the k-Server Problem (Extended Abstract). On-Line Algorithms 1991: 1-10 - [c16]Noga Alon, Zvi Galil, Oded Margalit:
On the Exponent of the All Pairs Shortest Path Problem. FOCS 1991: 569-575 - [c15]