| 2026 | STOC | The Natural Proofs Barrier against Data-Structure Lower-Bounds. | Michal Kouck, Bruno Loff, Tulasimohan Molli, Michael E. Saks |
| 2024 | FOCS | Nearly Optimal List Labeling. | Michael A. Bender, Alex Conway, Martn Farach-Colton, Hanna Komls, Michal Kouck, William Kuszmaul, Michael E. Saks |
| 2024 | STOC | Almost Linear Size Edit Distance Sketch. | Michal Kouck, Michael E. Saks |
| 2023 | SODA | Simple, deterministic, fast (but weak) approximations to edit distance and Dyck edit distance. | Michal Kouck, Michael E. Saks |
| 2020 | STOC | Constant factor approximations to edit distance on far input pairs in nearly linear time. | Michal Kouck, Michael E. Saks |
| 2018 | CSR | Online Labeling: Algorithms, Lower Bounds and Open Questions. | Michael E. Saks |
| 2018 | FOCS | Approximating Edit Distance within Constant Factor in Truly Sub-Quadratic Time. | Diptarka Chakraborty, Debarati Das, Elazar Goldenberg, Michal Kouck, Michael E. Saks |
| 2018 | STACS | Lower Bounds for Combinatorial Algorithms for Boolean Matrix Multiplication. | Debarati Das, Michal Kouck, Michael E. Saks |
| 2017 | SODA | Accurate and Nearly Optimal Sublinear Approximations to Ulam Distance. | Timothy Naumovitz, Michael E. Saks, C. Seshadhri |
| 2016 | FOCS | Noisy Population Recovery in Polynomial Time. | Anindya De, Michael E. Saks, Sijian Tang |
| 2015 | SODA | A polylogarithmic space deterministic streaming algorithm for approximating distance to monotonicity. | Timothy Naumovitz, Michael E. Saks |
| 2014 | ICALP | Efficient Indexing of Necklaces and Irreducible Polynomials over Finite Fields. | Swastik Kopparty, Mrinal Kumar, Michael E. Saks |
| 2013 | FOCS | A Polynomial Time Algorithm for Lossy Population Recovery. | Ankur Moitra, Michael E. Saks |
| 2013 | ICALP | On Randomized Online Labeling with Polynomially Many Labels. | Jan Bulnek, Michal Kouck, Michael E. Saks |
| 2013 | SODA | Space efficient streaming algorithms for the distance to monotonicity and asymmetric edit distance. | Michael E. Saks, C. Seshadhri |
| 2013 | STACS | On the practically interesting instances of MAXCUT. | Yonatan Bilu, Amit Daniely, Nati Linial, Michael E. Saks |
| 2012 | ESA | On Online Labeling with Polynomially Many Labels. | Martin Babka, Jan Bulnek, Vladimr Cunt, Michal Kouck, Michael E. Saks |
| 2012 | STOC | Tight lower bounds for the online labeling problem. | Jan Bulnek, Michal Kouck, Michael E. Saks |
| 2010 | FOCS | Estimating the Longest Increasing Sequence in Polylogarithmic Time. | Michael E. Saks, C. Seshadhri |
| 2008 | SODA | Parallel monotonicity reconstruction. | Michael E. Saks, C. Seshadhri |
| 2008 | SPAA | Online multicast with egalitarian cost sharing. | Moses Charikar, Howard J. Karloff, Claire Mathieu, Joseph Naor, Michael E. Saks |
| 2005 | FOCS | Lower Bounds for the Noisy Broadcast Problem. | Navin Goyal, Guy Kindler, Michael E. Saks |
| 2005 | FOCS | Every decision tree has an in.uential variable. | Ryan O'Donnell, Michael E. Saks, Oded Schramm, Rocco A. Servedio |
| 2005 | SODA | Rounds vs queries trade-off in noisy computation. | Navin Goyal, Michael E. Saks |
| 2005 | STACS | Three Optimal Algorithms for Balls of Three Colors. | Zdenek Dvork, Vt Jelnek, Daniel Krl, Jan Kyncl, Michael E. Saks |
| 2004 | STACS | A Lower Bound on the Competitive Ratio of Truthful Auctions. | Andrew V. Goldberg, Jason D. Hartline, Anna R. Karlin, Michael E. Saks |
| 2002 | STOC | Space lower bounds for distance approximation in the data stream model. | Michael E. Saks, Xiaodong Sun |
| 2000 | FOCS | Super-linear time-space tradeoff lower bounds for randomized computation. | Paul Beame, Michael E. Saks, Xiaodong Sun, Erik Vee |
| 1999 | ESA | On List Update and Work Function Algorithms. | Eric J. Anderson, Kirsten Hildrum, Anna R. Karlin, April Rasala, Michael E. Saks |
| 1999 | STOC | Lower Bounds for Leader Election and Collective Coin-Flipping in the Perfect Information Model. | Alexander Russell, Michael E. Saks, David Zuckerman |
| 1998 | FOCS | Time-Space Tradeoffs for Branching Programs. | Paul Beame, Michael E. Saks, Jayram S. Thathachar |
| 1998 | FOCS | An Improved Exponential-Time Algorithm for | Ramamohan Paturi, Pavel Pudlk, Michael E. Saks, Francis Zane |
| 1998 | STOC | On the Complexity of Unsatisfiability Proofs for Random | Paul Beame, Richard M. Karp, Toniann Pitassi, Michael E. Saks |
| 1998 | STOC | Trees and Euclidean Metrics. | Nathan Linial, Avner Magen, Michael E. Saks |
| 1997 | STOC | Exponential Lower Bounds for Depth 3 Boolean Circuits. | Ramamohan Paturi, Michael E. Saks, Francis Zane |
| 1996 | FOCS | Discrepancy Sets and Pseudorandom Generators for Combinatorial Rectangles. | Roy Armoni, Michael E. Saks, Avi Wigderson, Shiyu Zhou |
| 1996 | SODA | Randomized Robot Navigation Algorithms. | Piotr Berman, Avrim Blum, Amos Fiat, Howard J. Karloff, Adi Rosn, Michael E. Saks |
| 1995 | FOCS | RSPACE(S) \subseteq DSPACE(S | Michael E. Saks, Shiyu Zhou |
| 1995 | STOC | Explicit dispersers with polylog degree. | Michael E. Saks, Aravind Srinivasan, Shiyu Zhou |
| 1994 | FOCS | Products and Help Bits in Decision Trees | Noam Nisan, Steven Rudich, Michael E. Saks |
| 1993 | STOC | Size-depth trade-offs for threshold circuits. | Russell Impagliazzo, Ramamohan Paturi, Michael E. Saks |
| 1993 | STOC | Efficient construction of a small hitting set for combinatorial rectangles in high dimension. | Nathan Linial, Michael Luby, Michael E. Saks, David Zuckerman |
| 1993 | STOC | Wait-free k-set agreement is impossible: the topology of public knowledge. | Michael E. Saks, Fotios Zaharoglou |
| 1992 | FOCS | A Decomposition Theorem and Bounds for Randomized Server Problems | Avrim Blum, Howard J. Karloff, Yuval Rabani, Michael E. Saks |
| 1992 | IPCO | A Complexity Index for Satisfiability Problems. | Endre Boros, Yves Crama, Peter L. Hammer, Michael E. Saks |
| 1992 | STOC | Adapting to Asynchronous Dynamic Networks (Extended Abstract) | Baruch Awerbuch, Boaz Patt-Shamir, David Peleg, Michael E. Saks |
| 1991 | PODC | Optimal Space Distributed Move-to-Front Lists. | Michael E. Saks, Fotios Zaharoglou |
| 1991 | SODA | Decomposing Graphs into Regions of Small Diameter. | Nathan Linial, Michael E. Saks |
| 1991 | SODA | Optimal Time Randomized Consensus - Making Resilient Algorithms Fast in Practice. | Michael E. Saks, Nir Shavit, Heather Woll |
| 1990 | COLT | On Threshold Circuits for Parity (Abstract). | Ramamohan Paturi, Michael E. Saks |
| 1990 | FOCS | A Dining Philosophers Algorithm with Polynomial Response Time | Baruch Awerbuch, Michael E. Saks |
| 1990 | FOCS | On Threshold Circuits for Parity | Ramamohan Paturi, Michael E. Saks |
| 1989 | STOC | The Cell Probe Complexity of Dynamic Data Structures | Michael L. Fredman, Michael E. Saks |
| 1988 | FOCS | Lattices, Mbius Functions and Communication Complexity | Lszl Lovsz, Michael E. Saks |
| 1987 | FOCS | Local Management of a Global Resource in a Communication Network | Yehuda Afek, Baruch Awerbuch, Serge A. Plotkin, Michael E. Saks |
| 1987 | PODC | Detecting Global Termination Conditions in the Face of Uncertainty. | Yehuda Afek, Michael E. Saks |
| 1987 | STOC | An Optimal Online Algorithm for Metrical Task Systems | Allan Borodin, Nathan Linial, Michael E. Saks |
| 1987 | STOC | Imperfect Random Sources and Discrete Controlled Processes | David Lichtenstein, Nathan Linial, Michael E. Saks |
| 1986 | FOCS | On a Search Problem Related to Branch-and-Bound Procedures | Richard M. Karp, Michael E. Saks, Avi Wigderson |
| 1986 | FOCS | Probabilistic Boolean Decision Trees and the Complexity of Evaluating Game Trees | Michael E. Saks, Avi Wigderson |
| 1984 | STOC | Every Poset Has a Good Comparison | Jeff Kahn, Michael E. Saks |
| 1983 | FOCS | A Topological Approach to Evasiveness | Jeff Kahn, Michael E. Saks, Dean Sturtevant |
| 1983 | FOCS | Information Bounds Are Good for Search Problems on Ordered Data Structures | Nathan Linial, Michael E. Saks |
| 1983 | PODC | The Balanced Sorting Network. | Martin Dowd, Yehoshua Perl, Michael E. Saks |