| 2026 | SODA | Extended VC-dimension, and Radon and Tverberg type theorems for unions of convex sets. | Noga Alon, Shakhar Smorodinsky |
| 2024 | COLT | A Unified Characterization of Private Learnability via Graph Theory. | Noga Alon, Shay Moran, Hilla Schefler, Amir Yehudayoff |
| 2024 | ICLR | Optimal Sample Complexity of Contrastive Learning. | Noga Alon, Dmitrii Avdiukhin, Dor Elboim, Orr Fischer, Grigory Yaroslavtsev |
| 2024 | MFCS | Sublinear Time Shortest Path in Expander Graphs. | Noga Alon, Allan Grnlund, Sren Fuglede Jrgensen, Kasper Green Larsen |
| 2021 | FOCS | A Theory of PAC Learnability of Partial Concept Classes. | Noga Alon, Steve Hanneke, Ron Holzman, Shay Moran |
| 2021 | ICALP | Efficient Splitting of Necklaces. | Noga Alon, Andrei Graur |
| 2021 | STOC | Adversarial laws of large numbers and optimal regret in online classification. | Noga Alon, Omri Ben-Eliezer, Yuval Dagan, Shay Moran, Moni Naor, Eylon Yogev |
| 2021 | STOC | Boosting simple learners. | Noga Alon, Alon Gonen, Elad Hazan, Shay Moran |
| 2020 | COLT | Hierarchical Clustering: A 0.585 Revenue Approximation. | Noga Alon, Yossi Azar, Danny Vainstein |
| 2020 | COLT | Closure Properties for Private Classification and Online Prediction. | Noga Alon, Amos Beimel, Shay Moran, Uri Stemmer |
| 2019 | ICALP | Deterministic Combinatorial Replacement Paths and Distance Sensitivity Oracles. | Noga Alon, Shiri Chechik, Sarel Cohen |
| 2019 | ISIT | The Hat Guessing Number of Graphs. | Noga Alon, Omri Ben-Eliezer, Chong Shangguan, Itzhak Tamo |
| 2019 | STOC | Private PAC learning implies finite Littlestone dimension. | Noga Alon, Roi Livni, Maryanthe Malliaris, Shay Moran |
| 2018 | SPAA | The Price of Bounded Preemption. | Noga Alon, Yossi Azar, Mark Berlin |
| 2017 | FOCS | Testing Hereditary Properties of Ordered Graphs and Matrices. | Noga Alon, Omri Ben-Eliezer, Eldar Fischer |
| 2017 | FOCS | Optimal Compression of Approximate Inner Products and Dimension Reduction. | Noga Alon, Bo'az Klartag |
| 2017 | SODA | Optimal induced universal graphs for bounded-degree graphs. | Noga Alon, Rajko Nenadov |
| 2016 | COLT | Sign rank versus VC dimension. | Noga Alon, Shay Moran, Amir Yehudayoff |
| 2016 | ISIT | On the duplication distance of binary strings. | Noga Alon, Jehoshua Bruck, Farzad Farnoud, Siddharth Jain |
| 2016 | PODC | Reliable Communication over Highly Connected Noisy Networks. | Noga Alon, Mark Braverman, Klim Efremenko, Ran Gelles, Bernhard Haeupler |
| 2016 | SODA | On the maximum quartet distance between phylogenetic trees. | Noga Alon, Humberto Naves, Benny Sudakov |
| 2015 | COLT | Online Learning with Feedback Graphs: Beyond Bandits. | Noga Alon, Nicol Cesa-Bianchi, Ofer Dekel, Tomer Koren |
| 2015 | FOCS | Welfare Maximization with Limited Interaction. | Noga Alon, Noam Nisan, Ran Raz, Omri Weinstein |
| 2015 | IJCAI | How Robust Is the Wisdom of the Crowds? | Noga Alon, Michal Feldman, Omer Lev, Moshe Tennenholtz |
| 2014 | ISIT | Linear Boolean classification, coding and "the critical problem". | Emmanuel Abbe, Noga Alon, Afonso S. Bandeira |
| 2014 | SODA | Broadcast Throughput in Radio Networks: Routing vs. Network Coding. | Noga Alon, Mohsen Ghaffari, Bernhard Haeupler, Majid Khabbazian |
| 2014 | SODA | On the compatibility of quartet trees. | Noga Alon, Sagi Snir, Raphael Yuster |
| 2013 | AAAI | Bundling Attacks in Judgment Aggregation. | Noga Alon, Dvir Falik, Reshef Meir, Moshe Tennenholtz |
| 2013 | AAAI | The Value of Ignorance about the Number of Players. | Noga Alon, Reshef Meir, Moshe Tennenholtz |
| 2013 | STOC | The approximate rank of a matrix and its algorithmic applications: approximate rank. | Noga Alon, Troy Lee, Adi Shraibman, Santosh S. Vempala |
| 2012 | WWW | Optimizing budget allocation among channels and influencers. | Noga Alon, Iftah Gamzu, Moshe Tennenholtz |
| 2012 | SODA | Space-efficient local computation algorithms. | Noga Alon, Ronitt Rubinfeld, Shai Vardi, Ning Xie |
| 2012 | STOC | Nearly complete graphs decomposable into large induced matchings and their applications. | Noga Alon, Ankur Moitra, Benny Sudakov |
| 2011 | SSS | Pragmatic Self-stabilization of Atomic Memory in Message-Passing Systems. | Noga Alon, Hagit Attiya, Shlomi Dolev, Swan Dubois, Maria Potop-Butucaru, Sbastien Tixeuil |
| 2011 | TARK | Sum of us: strategyproof selection from the selectors. | Noga Alon, Felix A. Fischer, Ariel D. Procaccia, Moshe Tennenholtz |
| 2010 | COLT | Voting Paradoxes. | Noga Alon |
| 2010 | FOCS | A Non-linear Lower Bound for Planar Epsilon-Nets. | Noga Alon |
| 2010 | FOCS | Solving Linear Systems through Nested Dissection. | Noga Alon, Raphael Yuster |
| 2010 | PODC | Bayesian ignorance. | Noga Alon, Yuval Emek, Michal Feldman, Moshe Tennenholtz |
| 2010 | SODA | Solving MAX-r-SAT Above a Tight Lower Bound. | Noga Alon, Gregory Z. Gutin, Eun Jung Kim, Stefan Szeider, Anders Yeo |
| 2010 | SPAA | Basic network creation games. | Noga Alon, Erik D. Demaine, MohammadTaghi Hajiaghayi, Tom Leighton |
| 2009 | FOCS | Choice-Memory Tradeoff in Allocations. | Noga Alon, Eyal Lubetzky, Ori Gurel-Gurevich |
| 2009 | ICALP | Fast FAST. | Noga Alon, Daniel Lokshtanov, Saket Saurabh |
| 2009 | SODA | On the power of two, three and four probes. | Noga Alon, Uriel Feige |
| 2008 | FOCS | Broadcasting with Side Information. | Noga Alon, Eyal Lubetzky, Uri Stav, Amit Weinstein, Avinatan Hassidim |
| 2008 | FOCS | k-Wise Independent Random Graphs. | Noga Alon, Asaf Nussboim |
| 2008 | ICALP | Optimal Monotone Encodings. | Noga Alon, Rani Hod |
| 2008 | ISMB | Biomolecular network motif counting and discovery by color coding. | Noga Alon, Phuong Dao, Iman Hajirasouliha, Fereydoun Hormozdiari, Sleyman Cenk Sahinalp |
| 2008 | SODA | Optimal universal graphs with deterministic embedding. | Noga Alon, Michael R. Capalbo |
| 2008 | SODA | Weak ε-nets and interval chains. | Noga Alon, Haim Kaplan, Gabriel Nivasch, Micha Sharir, Shakhar Smorodinsky |
| 2008 | SPAA | Many random walks are faster than one. | Noga Alon, Chen Avin, Michal Kouck, Gady Kozma, Zvi Lotker, Mark R. Tuttle |
| 2007 | COCOON | Linear Time Algorithms for Finding a Dominating Set of Fixed Size in Degenerated Graphs. | Noga Alon, Shai Gutner |
| 2007 | COCOON | Can a Graph Have Distinct Regular Partitions? | Noga Alon, Asaf Shapira, Uri Stav |
| 2007 | ESA | Fast Algorithms for Maximum Subset Matching and All-Pairs Shortest Paths in Graphs with a (Not So) Small Vertex Cover. | Noga Alon, Raphael Yuster |
| 2007 | FOCS | Finding Disjoint Paths in Expanders Deterministically and Online. | Noga Alon, Michael R. Capalbo |
| 2007 | ICALP | Quasi-randomness and Algorithmic Regularity for Graphs with General Degree Distributions. | Noga Alon, Amin Coja-Oghlan, Hip Hn, Mihyun Kang, Vojtech Rdl, Mathias Schacht |
| 2007 | ICALP | Parameterized Algorithms for Directed Maximum Leaf Problems. | Noga Alon, Fedor V. Fomin, Gregory Z. Gutin, Michael Krivelevich, Saket Saurabh |
| 2007 | ICALP | Balanced Families of Perfect Hash Functions and Their Applications. | Noga Alon, Shai Gutner |
| 2007 | SODA | An elementary construction of constant-degree expanders. | Noga Alon, Oded Schwartz, Asaf Shapira |
| 2007 | STOC | Improved approximation for directed cut problems. | Amit Agarwal, Noga Alon, Moses Charikar |
| 2007 | STOC | Testing k-wise and almost k-wise independence. | Noga Alon, Alexandr Andoni, Tali Kaufman, Kevin Matulef, Ronitt Rubinfeld, Ning Xie |
| 2006 | ICALP | Additive Approximation for Edge-Deletion Problems (Abstract). | Noga Alon, Asaf Shapira, Benny Sudakov |
| 2006 | SODA | Testing triangle-freeness in general graphs. | Noga Alon, Tali Kaufman, Michael Krivelevich, Dana Ron |
| 2006 | STOC | A combinatorial characterization of the testable graph properties: it's all about regularity. | Noga Alon, Eldar Fischer, Ilan Newman, Asaf Shapira |
| 2006 | SPAA | Tell me who I am: an interactive recommendation system. | Noga Alon, Baruch Awerbuch, Yossi Azar, Boaz Patt-Shamir |
| 2005 | FOCS | A Characterization of the (natural) Graph Properties Testable with One-Sided Error. | Noga Alon, Asaf Shapira |
| 2005 | FOCS | Additive Approximation for Edge-Deletion Problems. | Noga Alon, Asaf Shapira, Benny Sudakov |
| 2005 | PODS | Estimating arbitrary subset sums with few probes. | Noga Alon, Nick G. Duffield, Carsten Lund, Mikkel Thorup |
| 2005 | SODA | Ordinal embeddings of minimum relaxation: general properties, trees, and ultrametrics. | Noga Alon, Mihai Badoiu, Erik D. Demaine, Martin Farach-Colton, Mohammad Taghi Hajiaghayi, Anastasios Sidiropoulos |
| 2005 | SODA | Linear equations, arithmetic progressions and hypergraph property testing. | Noga Alon, Asaf Shapira |
| 2005 | STOC | Quadratic forms on graphs. | Noga Alon, Konstantin Makarychev, Yury Makarychev, Assaf Naor |
| 2005 | STOC | Every monotone graph property is testable. | Noga Alon, Asaf Shapira |
| 2005 | SPAA | Admission control to minimize rejections and online set cover with repetitions. | Noga Alon, Yossi Azar, Shai Gutner |
| 2004 | ICALP | Learning a Hidden Subgraph. | Noga Alon, Vera Asodi |
| 2004 | SODA | A general approach to online network optimization problems. | Noga Alon, Baruch Awerbuch, Yossi Azar, Niv Buchbinder, Joseph Naor |
| 2004 | SODA | A characterization of easily testable induced subgraphs. | Noga Alon, Asaf Shapira |
| 2004 | STOC | Approximating the cut-norm via Grothendieck's inequality. | Noga Alon, Assaf Naor |
| 2003 | SODA | Smaller explicit superconcentrators. | Noga Alon, Michael R. Capalbo |
| 2003 | STOC | The online set cover problem. | Noga Alon, Baruch Awerbuch, Yossi Azar, Niv Buchbinder, Joseph Naor |
| 2003 | STOC | Testing subgraphs in directed graphs. | Noga Alon, Asaf Shapira |
| 2002 | FOCS | Learning a Hidden Matching. | Noga Alon, Richard Beigel, Simon Kasif, Steven Rudich, Benny Sudakov |
| 2002 | FOCS | Explicit Unique-Neighbor Expanders. | Noga Alon, Michael R. Capalbo |
| 2002 | SODA | Guessing secrets efficiently via list decoding. | Noga Alon, Venkatesan Guruswami, Tali Kaufman, Madhu Sudan |
| 2002 | SODA | Testing satisfiability. | Noga Alon, Asaf Shapira |
| 2002 | STOC | Random sampling and approximation of MAX-CSP problems. | Noga Alon, Wenceslas Fernandez de la Vega, Ravi Kannan, Marek Karpinski |
| 2001 | FOCS | Testing Subgraphs in Large Graphs. | Noga Alon |
| 2001 | FOCS | Semi-Direct Product in Groups and Zig-Zag Product in Graphs: Connections and Applications. | Noga Alon, Alexander Lubotzky, Avi Wigderson |
| 2001 | LICS | Typechecking XML Views of Relational Databases. | Noga Alon, Tova Milo, Frank Neven, Dan Suciu, Victor Vianu |
| 2001 | PODS | XML with Data Values: Typechecking Revisited. | Noga Alon, Tova Milo, Frank Neven, Dan Suciu, Victor Vianu |
| 2001 | RECOMB | An optimal procedure for gap closing in whole genome shotgun sequencing. | Richard Beigel, Noga Alon, Simon Kasif, Mehmet Serkan Apaydin, Lance Fortnow |
| 2001 | SODA | Constructing worst case instances for semidefinite programming based approximation algorithms. | Noga Alon, Benny Sudakov, Uri Zwick |
| 2000 | FOCS | Universality and Tolerance. | Noga Alon, Michael R. Capalbo, Yoshiharu Kohayakawa, Vojtech Rdl, Andrzej Rucinski, Endre Szemerdi |
| 2000 | FOCS | Testing of Clustering. | Noga Alon, Seannie Dar, Michal Parnas, Dana Ron |
| 2000 | ICALP | Scalable Secure Storage when Half the System Is Faulty. | Noga Alon, Haim Kaplan, Michael Krivelevich, Dahlia Malkhi, Julien P. Stern |
| 1999 | FOCS | Efficient Testing of Large Graphs. | Noga Alon, Eldar Fischer, Michael Krivelevich, Mario Szegedy |
| 1999 | FOCS | Regular Languages Are Testable with a Constant Number of Queries. | Noga Alon, Michael Krivelevich, Ilan Newman, Mario Szegedy |
| 1999 | PODS | Tracking Join and Self-Join Sizes in Limited Storage. | Noga Alon, Phillip B. Gibbons, Yossi Matias, Mario Szegedy |
| 1998 | LATIN | Spectral Techniques in Graph Algorithms. | Noga Alon |
| 1998 | SODA | Finding a Large Hidden Clique in a Random Graph. | Noga Alon, Michael Krivelevich, Benny Sudakov |
| 1997 | SODA | Approximation Schemes for Scheduling. | Noga Alon, Yossi Azar, Gerhard J. Woeginger, Tal Yadid |
| 1997 | STOC | Is Linear Hashing Good? | Noga Alon, Martin Dietzfelbinger, Peter Bro Miltersen, Erez Petrank, Gbor Tardos |
| 1996 | ESA | On-line and Off-line Approximation Algorithms for Vector Covering Problems. | Noga Alon, Jnos Csirik, Sergey V. Sevastianov, Arjen P. A. Vestjens, Gerhard J. Woeginger |
| 1996 | FOCS | The Geometry of Coin-Weighing Problems. | Noga Alon, Dmitry N. Kozlov, Van H. Vu |
| 1996 | ICALP | Improved Parallel Approximation of a Class of Integer Programming Programming Problems. | Noga Alon, Aravind Srinivasan |
| 1996 | STOC | The Space Complexity of Approximating the Frequency Moments. | Noga Alon, Yossi Matias, Mario Szegedy |
| 1995 | ESA | Efficient Dynamic-Resharing "Verifiable Secret Sharing" Against Mobile Adversary. | Noga Alon, Zvi Galil, Moti Yung |
| 1995 | FOCS | Linear Time Erasure Codes with Nearly Optimal Recovery (Extended Abstract). | Noga Alon, Jeff Edmonds, Michael Luby |
| 1994 | ESA | Finding and Counting Given Length Cycles (Extended Abstract). | Noga Alon, Raphael Yuster, Uri Zwick |
| 1994 | FOCS | Polynomial time randomised approxmiation schemes for the Tutte polynomial of dense graphs | Noga Alon, Alan M. Frieze, Dominic Welsh |
| 1994 | SODA | Matching Nuts and Bolts. | Noga Alon, Manuel Blum, Amos Fiat, Sampath Kannan, Moni Naor, Rafail Ostrovsky |
| 1994 | STOC | A spectral technique for coloring random 3-colorable graphs (preliminary version). | Noga Alon, Nabil Kahal |
| 1994 | STOC | Color-coding: a new method for finding simple paths, cycles and other small subgraphs within large graphs. | Noga Alon, Raphael Yuster, Uri Zwick |
| 1993 | FOCS | Scale-sensitive Dimensions, Uniform Convergence, and Learnability | Noga Alon, Shai Ben-David, Nicol Cesa-Bianchi, David Haussler |
| 1993 | STOC | Routing permutations on graphs via matchings. | Noga Alon, Fan R. K. Chung, Ronald L. Graham |
| 1992 | FOCS | Fault Tolerant Graphs, Perfect Hash Functions and Disjoint Paths | Mikls Ajtai, Noga Alon, Jehoshua Bruck, Robert Cypher, Ching-Tien Ho, Moni Naor, Endre Szemerdi |
| 1992 | FOCS | The Algorithmic Aspects of the Regularity Lemma (Extended Abstract) | Noga Alon, Richard A. Duke, Hanno Lefmann, Vojtech Rdl, Raphael Yuster |
| 1992 | FOCS | Witnesses for Boolean Matrix Multiplication and for Shortest Paths | Noga Alon, Zvi Galil, Oded Margalit, Moni Naor |
| 1992 | FOCS | Lower Bounds on the Competitive Ratio for Mobile User Tracking and Distributed Job Scheduling (Extended Abstract) | Noga Alon, Gil Kalai, Moty Ricklin, Larry J. Stockmeyer |
| 1992 | SODA | Comparison-Sorting and Selecting in Totally Monotone Matrices. | Noga Alon, Yossi Azar |
| 1991 | FOCS | A parallel algorithmic version of the Local Lemma | Noga Alon |
| 1991 | FOCS | On the Exponent of the All Pairs Shortest Path Problem | Noga Alon, Zvi Galil, Oded Margalit |
| 1990 | FOCS | Simple Constructions of Almost k-Wise Independent Random Variables | Noga Alon, Oded Goldreich, Johan Hstad, Ren Peralta |
| 1990 | FOCS | Parallel Linear Programming in Fixed Dimension Almost Surely in Constant Time | Noga Alon, Nimrod Megiddo |
| 1990 | FOCS | Coin-Flipping Games Immune against Linear-Sized Coalitions (Extended Abstract) | Noga Alon, Moni Naor |
| 1990 | STOC | A Separator Theorem for Graphs with an Excluded Minor and its Applications | Noga Alon, Paul D. Seymour, Robin Thomas |
| 1989 | STOC | On the Complexity of Radio Communication (Extended Abstract) | Noga Alon, Amotz Bar-Noy, Nathan Linial, David Peleg |
| 1988 | FOCS | Parallel Comparison Algorithms for Approximation Problems | Noga Alon, Yossi Azar |
| 1987 | FOCS | The Average Complexity of Deterministic and Randomized Parallel Comparison Sorting Algorithms | Noga Alon, Yossi Azar |
| 1987 | ICDCS | On Disseminating Information Reliably without Broadcasting. | Noga Alon, Amnon Barak, Udi Manber |
| 1986 | FOCS | Tight Complexity Bounds for Parallel Comparison Sorting | Noga Alon, Yossi Azar, Uzi Vishkin |
| 1986 | FOCS | Meanders, Ramsey Theory and Lower Bounds for Branching Programs | Noga Alon, Wolfgang Maass |
| 1985 | FOCS | Geometrical Realization of Set Systems and Probabilistic Communication Complexity | Noga Alon, Peter Frankl, Vojtech Rdl |
| 1985 | STOC | Expanders, Sorting in Rounds and Superconcentrators of Limited Depth | Noga Alon |
| 1984 | FOCS | Eigenvalues, Expanders and Superconcentrators (Extended Abstract) | Noga Alon, V. D. Milman |