default search action
Noga 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
- 2024
- [j443]Noah Kravitz, Noga Alon:
Cats in Cubes. Electron. J. Comb. 31(3) (2024) - [j442]Noga Alon:
Implicit Representation of Sparse Hereditary Families. Discret. Comput. Geom. 72(2): 476-482 (2024) - [j441]Noga Alon:
Graph-codes. Eur. J. Comb. 116: 103880 (2024) - [j440]Noga Alon:
Erasure list-decodable codes and Turán hypercube problems. Finite Fields Their Appl. 100: 102513 (2024) - [j439]Noga Alon, Peter Frankl:
Turán graphs with bounded matching number. J. Comb. Theory B 165: 223-229 (2024) - [j438]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) - [j437]Noga Alon, Dor Elboim, János Pach, Gábor Tardos:
Random Necklaces Require Fewer Cuts. SIAM J. Discret. Math. 38(2): 1381-1408 (2024) - [j436]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) - [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 - [i91]Noga Alon, Or Zamir:
Sumsets in the Hypercube. CoRR abs/2403.16589 (2024) - [i90]Noga Alon, Baruch Schieber:
Optimal Preprocessing for Answering On-Line Product Queries. CoRR abs/2406.06321 (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]