


Остановите войну!
for scientists:
Noga Alon
Alon Nilli – נוגה אלון
Person information

- unicode name: נוגה אלון
- 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
- 2022
- [j423]Noga Alon, Colin Defant, Noah Kravitz:
The runsort permuton. Adv. Appl. Math. 139: 102361 (2022) - [j422]Noga Alon, Clara Shikhelman
:
Additive Approximation of Generalized Turán Questions. Algorithmica 84(2): 464-481 (2022) - [j421]Noga Alon, Jeremy Chizewer
:
On the hat guessing number of graphs. Discret. Math. 345(4): 112785 (2022) - [i79]Noga Alon:
Implicit representation of sparse hereditary families. CoRR abs/2201.00328 (2022) - [i78]Noga Alon, Benjamin Gunby, Xiaoyu He, Eran Shmaya, Eilon Solan:
Identifying the Deviator. CoRR abs/2203.03744 (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, Ser. 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. Computational Complexity Conference 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. 24: 58 (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, Ser. B 121: 146-172 (2016) - [j384]Noga Alon:
High girth augmented trees are huge. J. Comb. Theory, Ser. 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. 23: 86 (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, Ser. B 113: 220-235 (2015) - [j371]Noga Alon, Shagnik Das, Roman Glebov, Benny Sudakov:
Comparable pairs in families of sets. J. Comb. Theory, Ser. 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. 22: 14 (2015) - [i42]Noga Alon, Noam Nisan, Ran Raz, Omri Weinstein:
Welfare Maximization with Limited Interaction. Electron. Colloquium Comput. Complex. 22: 54 (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, Ser. A 125: 1-17 (2014) - [j365]