Michael E. Saks

206 papers A* 54A 18B 2Misc 1Journal 121Unranked 7

Year	Rank	Type	Title / Venue / Authors
2026	J	`jnl`	Optimal Monotone Depth-Three Circuit Lower Bounds for Majority. CoRR Mohit Gurumukhani, Daniel Kleber, Ramamohan Paturi, Christopher D. Rosin, Michael E. Saks, Navid Talebanfard
2025	J	`jnl`	Local Enumeration: The Not-All-Equal Case. CoRR Mohit Gurumukhani, Ramamohan Paturi, Michael E. Saks, Navid Talebanfard
2024	A*	`conf`	Almost Linear Size Edit Distance Sketch. STOC Michal Koucký, Michael E. Saks
2024	A	`conf`	Local Enumeration and Majority Lower Bounds. CCC Mohit Gurumukhani, Ramamohan Paturi, Pavel Pudlák, Michael E. Saks, Navid Talebanfard
2024	J	`jnl`	Local Enumeration and Majority Lower Bounds. CoRR Mohit Gurumukhani, Ramamohan Paturi, Pavel Pudlák, Michael E. Saks, Navid Talebanfard
2024	A*	`conf`	Nearly Optimal List Labeling. FOCS Michael A. Bender, Alex Conway, Martín Farach-Colton, Hanna Komlós, Michal Koucký, William Kuszmaul, Michael E. Saks
2024	J	`jnl`	Nearly Optimal List Labeling. CoRR Michael A. Bender, Alex Conway, Martín Farach-Colton, Hanna Komlós, Michal Koucký, William Kuszmaul, Michael E. Saks
2023	A*	`conf`	Simple, deterministic, fast (but weak) approximations to edit distance and Dyck edit distance. SODA Michal Koucký, Michael E. Saks
2022	A	`conf`	On Randomized Reductions to the Random Strings. CCC Michael E. Saks, Rahul Santhanam
2022	J	`jnl`	On Randomized Reductions to the Random Strings. Electron. Colloquium Comput. Complex. Michael E. Saks, Rahul Santhanam
2020	J	`jnl`	An Asymptotically Tight Bound on the Number of Relevant Variables in a Bounded Degree Boolean function. Comb. John Chiarelli, Pooya Hatami, Michael E. Saks
2020	J	`jnl`	Approximating Edit Distance Within Constant Factor in Truly Sub-quadratic Time. J. ACM Diptarka Chakraborty, Debarati Das, Elazar Goldenberg, Michal Koucký, Michael E. Saks
2020	A	`conf`	Circuit Lower Bounds from NP-Hardness of MCSP Under Turing Reductions. CCC Michael E. Saks, Rahul Santhanam
2020	A*	`conf`	Constant factor approximations to edit distance on far input pairs in nearly linear time. STOC Michal Koucký, Michael E. Saks
2020	J	`jnl`	On the discrepancy of random matrices with many columns. Random Struct. Algorithms Cole Franks, Michael E. Saks
2019	J	`jnl`	Constant factor approximations to edit distance on far input pairs in nearly linear time. CoRR Michal Koucký, Michael E. Saks
2019	J	`jnl`	On Online Labeling with Large Label Set. SIAM J. Discret. Math. Martin Babka, Jan Bulánek, Vladimír Cunát, Michal Koucký, Michael E. Saks
2018	J	`jnl`	Approximating Edit Distance Within Constant Factor in Truly Sub-Quadratic Time. CoRR Diptarka Chakraborty, Debarati Das, Elazar Goldenberg, Michal Koucký, Michael E. Saks
2018	A*	`conf`	Approximating Edit Distance within Constant Factor in Truly Sub-Quadratic Time. FOCS Diptarka Chakraborty, Debarati Das, Elazar Goldenberg, Michal Koucký, Michael E. Saks
2018	A	`conf`	Lower Bounds for Combinatorial Algorithms for Boolean Matrix Multiplication. STACS Debarati Das, Michal Koucký, Michael E. Saks
2018	J	`jnl`	Lower bounds for Combinatorial Algorithms for Boolean Matrix Multiplication. CoRR Debarati Das, Michal Koucký, Michael E. Saks
2018	Misc	`conf`	Online Labeling: Algorithms, Lower Bounds and Open Questions. CSR Michael E. Saks
2018	J	`jnl`	Tight Bound on the Number of Relevant Variables in a Bounded degree Boolean function. CoRR John Chiarelli, Pooya Hatami, Michael E. Saks
2017	J	`jnl`	A Communication Game Related to the Sensitivity Conjecture. Theory Comput. Justin Gilmer, Michal Koucký, Michael E. Saks
2017	A*	`conf`	Accurate and Nearly Optimal Sublinear Approximations to Ulam Distance. SODA Timothy Naumovitz, Michael E. Saks, C. Seshadhri
2017	J	`jnl`	Estimating the Longest Increasing Sequence in Polylogarithmic Time. SIAM J. Comput. Michael E. Saks, C. Seshadhri
2017	J	`jnl`	Towards an algebraic natural proofs barrier via polynomial identity testing. CoRR Joshua A. Grochow, Mrinal Kumar, Michael E. Saks, Shubhangi Saraf
2017	J	`jnl`	Towards an algebraic natural proofs barrier via polynomial identity testing. Electron. Colloquium Comput. Complex. Joshua A. Grochow, Mrinal Kumar, Michael E. Saks, Shubhangi Saraf
2016	—	`ch.`	Backtracking Based Encyclopedia of Algorithms Ramamohan Paturi, Pavel Pudlák, Michael E. Saks, Francis Zane
2016	J	`jnl`	Composition limits and separating examples for some boolean function complexity measures. Comb. Justin Gilmer, Michael E. Saks, Srikanth Srinivasan
2016	J	`jnl`	Efficient Indexing of Necklaces and Irreducible Polynomials over Finite Fields. Theory Comput. Swastik Kopparty, Mrinal Kumar, Michael E. Saks
2016	J	`jnl`	Hellinger volume and number-on-the-forehead communication complexity. J. Comput. Syst. Sci. Troy Lee, Nikos Leonardos, Michael E. Saks, Fengming Wang
2016	A*	`conf`	Noisy Population Recovery in Polynomial Time. FOCS Anindya De, Michael E. Saks, Sijian Tang
2016	J	`jnl`	Noisy population recovery in polynomial time. CoRR Anindya De, Michael E. Saks, Sijian Tang
2016	J	`jnl`	Noisy population recovery in polynomial time. Electron. Colloquium Comput. Complex. Anindya De, Michael E. Saks, Sijian Tang
2015	A	`conf`	A New Approach to the Sensitivity Conjecture. ITCS Justin Gilmer, Michal Koucký, Michael E. Saks
2015	J	`jnl`	A communication game related to the sensitivity conjecture. CoRR Justin Gilmer, Michal Koucký, Michael E. Saks
2015	A*	`conf`	A polylogarithmic space deterministic streaming algorithm for approximating distance to monotonicity. SODA Timothy Naumovitz, Michael E. Saks
2015	J	`jnl`	A tail bound for read- Random Struct. Algorithms Dmitry Gavinsky, Shachar Lovett, Michael E. Saks, Srikanth Srinivasan
2015	J	`jnl`	Efficient indexing of necklaces and irreducible polynomials over finite fields. CoRR Swastik Kopparty, Mrinal Kumar, Michael E. Saks
2015	J	`jnl`	Efficient indexing of necklaces and irreducible polynomials over finite fields. Electron. Colloquium Comput. Complex. Swastik Kopparty, Mrinal Kumar, Michael E. Saks
2015	J	`jnl`	Special issue "Conference on Computational Complexity 2014" Guest Editor's Foreword. Comput. Complex. Michael E. Saks
2015	J	`jnl`	Tight Lower Bounds for the Online Labeling Problem. SIAM J. Comput. Jan Bulánek, Michal Koucký, Michael E. Saks
2014	—	`conf`	Efficient Indexing of Necklaces and Irreducible Polynomials over Finite Fields. ICALP (1) Swastik Kopparty, Mrinal Kumar, Michael E. Saks
2014	J	`jnl`	Hellinger volume and number-on-the-forehead communication complexity. CoRR Troy Lee, Nikos Leonardos, Michael E. Saks, Fengming Wang
2014	—	`conf`	The Power of Super-logarithmic Number of Players. APPROX-RANDOM Arkadev Chattopadhyay, Michael E. Saks
2014	J	`jnl`	The Power of Super-logarithmic Number of Players. Electron. Colloquium Comput. Complex. Arkadev Chattopadhyay, Michael E. Saks
2013	J	`jnl`	A Polynomial Time Algorithm for Lossy Population Recovery CoRR Ankur Moitra, Michael E. Saks
2013	A*	`conf`	A Polynomial Time Algorithm for Lossy Population Recovery. FOCS Ankur Moitra, Michael E. Saks
2013	A	`conf`	Composition Limits and Separating Examples for Some Boolean Function Complexity Measures. CCC Justin Gilmer, Michael E. Saks, Srikanth Srinivasan
2013	J	`jnl`	Composition limits and separating examples for some Boolean function complexity measures. CoRR Justin Gilmer, Michael E. Saks, Srikanth Srinivasan
2013	J	`jnl`	Estimating the longest increasing sequence in polylogarithmic time. CoRR Michael E. Saks, C. Seshadhri
2013	—	`conf`	On Randomized Online Labeling with Polynomially Many Labels. ICALP (1) Jan Bulánek, Michal Koucký, Michael E. Saks
2013	A	`conf`	On the practically interesting instances of MAXCUT. STACS Yonatan Bilu, Amit Daniely, Nati Linial, Michael E. Saks
2013	A*	`conf`	Space efficient streaming algorithms for the distance to monotonicity and asymmetric edit distance. SODA Michael E. Saks, C. Seshadhri
2012	J	`jnl`	A Tail Bound for Read-k Families of Functions CoRR Dmitry Gavinsky, Shachar Lovett, Michael E. Saks, Srikanth Srinivasan
2012	J	`jnl`	A Tail Bound for Read-k Families of Functions. Electron. Colloquium Comput. Complex. Dmitry Gavinsky, Shachar Lovett, Michael E. Saks, Srikanth Srinivasan
2012	J	`jnl`	Clustering is difficult only when it does not matter CoRR Amit Daniely, Nati Linial, Michael E. Saks
2012	J	`jnl`	On Online Labeling with Polynomially Many Labels CoRR Martin Babka, Jan Bulánek, Vladimír Cunát, Michal Koucký, Michael E. Saks
2012	A	`conf`	On Online Labeling with Polynomially Many Labels. ESA Martin Babka, Jan Bulánek, Vladimír Cunát, Michal Koucký, Michael E. Saks
2012	J	`jnl`	On the practically interesting instances of MAXCUT CoRR Yonatan Bilu, Amit Daniely, Nati Linial, Michael E. Saks
2012	J	`jnl`	Space efficient streaming algorithms for the distance to monotonicity and asymmetric edit distance CoRR Michael E. Saks, C. Seshadhri
2012	A*	`conf`	Tight lower bounds for the online labeling problem. STOC Jan Bulánek, Michal Koucký, Michael E. Saks
2011	J	`jnl`	An Online Algorithm for a Problem in Scheduling with Set-ups and Release Times. Algorithmica Srikrishnan Divakaran, Michael E. Saks
2011	J	`jnl`	The Dual BKR Inequality and Rudich's Conjecture. Comb. Probab. Comput. Jeff Kahn, Michael E. Saks, Clifford D. Smyth
2011	J	`jnl`	Tight lower bounds for online labeling problem CoRR Jan Bulánek, Michal Koucký, Michael E. Saks
2010	A*	`conf`	Estimating the Longest Increasing Sequence in Polylogarithmic Time. FOCS Michael E. Saks, C. Seshadhri
2010	J	`jnl`	Local Monotonicity Reconstruction. SIAM J. Comput. Michael E. Saks, C. Seshadhri
2010	—	`ch.`	Local Property Reconstruction and Monotonicity. Property Testing Michael E. Saks, C. Seshadhri
2010	J	`jnl`	Lower Bounds on the Randomized Communication Complexity of Read-Once Functions. Comput. Complex. Nikos Leonardos, Michael E. Saks
2010	J	`jnl`	Rounds vs. Queries Tradeoff in Noisy Computation. Theory Comput. Navin Goyal, Michael E. Saks
2009	A	`conf`	Lower Bounds on the Randomized Communication Complexity of Read-Once Functions. CCC Nikos Leonardos, Michael E. Saks
2009	J	`jnl`	Lower bounds on the randomized communication complexity of read-once functions. Electron. Colloquium Comput. Complex. Nikos Leonardos, Michael E. Saks
2009	J	`jnl`	The unlabelled speed of a hereditary graph property. J. Comb. Theory B József Balogh, Béla Bollobás, Michael E. Saks, Vera T. Sós
2008	J	`jnl`	Approximation algorithms for problems in scheduling with set-ups. Discret. Appl. Math. Srikrishnan Divakaran, Michael E. Saks
2008	—	`ch.`	Backtracking Based k-SAT Algorithms. Encyclopedia of Algorithms Ramamohan Paturi, Pavel Pudlák, Michael E. Saks, Francis Zane
2008	J	`jnl`	Lower Bounds for the Noisy Broadcast Problem. SIAM J. Comput. Navin Goyal, Guy Kindler, Michael E. Saks
2008	J	`jnl`	Minimizing Disjunctive Normal Form Formulas and AC SIAM J. Comput. Eric Allender, Lisa Hellerstein, Paul McCabe, Toniann Pitassi, Michael E. Saks
2008	B	`conf`	Online multicast with egalitarian cost sharing. SPAA Moses Charikar, Howard J. Karloff, Claire Mathieu, Joseph Naor, Michael E. Saks
2008	A*	`conf`	Parallel monotonicity reconstruction. SODA Michael E. Saks, C. Seshadhri
2007	J	`jnl`	Probabilistic strategies for the partition and plurality problems. Random Struct. Algorithms Zdenek Dvorák, Vít Jelínek, Daniel Král, Jan Kyncl, Michael E. Saks
2006	J	`jnl`	A localization inequality for set functions. J. Comb. Theory A László Lovász, Michael E. Saks
2006	J	`jnl`	Competitive auctions. Games Econ. Behav. Andrew V. Goldberg, Jason D. Hartline, Anna R. Karlin, Michael E. Saks, Andrew Wright
2006	A	`conf`	Minimizing DNF Formulas and AC CCC Eric Allender, Lisa Hellerstein, Paul McCabe, Toniann Pitassi, Michael E. Saks
2006	J	`jnl`	The Non-Crossing Graph. Electron. J. Comb. Nathan Linial, Michael E. Saks, David Statter
2005	J	`jnl`	A parallel search game. Random Struct. Algorithms Navin Goyal, Michael E. Saks
2005	J	`jnl`	An improved exponential-time algorithm for J. ACM Ramamohan Paturi, Pavel Pudlák, Michael E. Saks, Francis Zane
2005	A*	`conf`	Every decision tree has an in.uential variable. FOCS Ryan O'Donnell, Michael E. Saks, Oded Schramm, Rocco A. Servedio
2005	J	`jnl`	Every decision tree has an influential variable CoRR Ryan O'Donnell, Michael E. Saks, Oded Schramm, Rocco A. Servedio
2005	A*	`conf`	Lower Bounds for the Noisy Broadcast Problem. FOCS Navin Goyal, Guy Kindler, Michael E. Saks
2005	J	`jnl`	Minimizing DNF Formulas and AC0 Circuits Given a Truth Table Electron. Colloquium Comput. Complex. Eric Allender, Lisa Hellerstein, Paul McCabe, Toniann Pitassi, Michael E. Saks
2005	A*	`conf`	Rounds vs queries trade-off in noisy computation. SODA Navin Goyal, Michael E. Saks
2005	A	`conf`	Three Optimal Algorithms for Balls of Three Colors. STACS Zdenek Dvorák, Vít Jelínek, Daniel Král, Jan Kyncl, Michael E. Saks
2005	A*	`conf`	Weak monotonicity suffices for truthfulness on convex domains. EC Michael E. Saks, Lan Yu
2004	J	`jnl`	A Lower Bound On The Integrality Gap For Minimum Multicut In Directed Networks. Comb. Michael E. Saks, Alex Samorodnitsky, Leonid Zosin
2004	A	`conf`	A Lower Bound on the Competitive Ratio of Truthful Auctions. STACS Andrew V. Goldberg, Jason D. Hartline, Anna R. Karlin, Michael E. Saks
2004	J	`jnl`	A lower bound on the quantum query complexity of read-once functions. J. Comput. Syst. Sci. Howard Barnum, Michael E. Saks
2004	J	`jnl`	Multicolour Turán problems. Adv. Appl. Math. Peter Keevash, Michael E. Saks, Benny Sudakov, Jacques Verstraëte
2003	J	`jnl`	Complexity of some arithmetic problems for binary polynomials. Comput. Complex. Eric Allender, Anna Bernasconi, Carsten Damm, Joachim von zur Gathen, Michael E. Saks, Igor E. Shparlinski
2003	A	`conf`	Optimal Separation of EROW and CROWPRAMs. CCC Navin Goyal, Michael E. Saks, Srinivasan Venkatesh
2003	A	`conf`	Quantum query complexity and semi-definite programming. CCC Howard Barnum, Michael E. Saks, Mario Szegedy
2003	J	`jnl`	The Euclidean Distortion of Complete Binary Trees. Discret. Comput. Geom. Nathan Linial, Michael E. Saks
2003	J	`jnl`	Time-space trade-off lower bounds for randomized computation of decision problems. J. ACM Paul Beame, Michael E. Saks, Xiaodong Sun, Erik Vee
2002	J	`jnl`	A lower bound on the quantum query complexity of read-once functions CoRR Howard Barnum, Michael E. Saks
2002	J	`jnl`	A lower bound on the quantum query complexity of read-once functions Electron. Colloquium Comput. Complex. Howard Barnum, Michael E. Saks
2002	J	`jnl`	Kleitman and combinatorics. Discret. Math. Michael E. Saks
2002	J	`jnl`	Lower Bounds for Leader Election and Collective Coin-Flipping in the Perfect Information Model. SIAM J. Comput. Alexander Russell, Michael E. Saks, David Zuckerman
2002	J	`jnl`	On list update and work function algorithms. Theor. Comput. Sci. Eric J. Anderson, Kirsten Hildrum, Anna R. Karlin, April Rasala, Michael E. Saks
2002	A*	`conf`	Space lower bounds for distance approximation in the data stream model. STOC Michael E. Saks, Xiaodong Sun
2002	J	`jnl`	The Efficiency of Resolution and Davis--Putnam Procedures. SIAM J. Comput. Paul Beame, Richard M. Karp, Toniann Pitassi, Michael E. Saks
2001	J	`jnl`	A Lower Bound for Primality. J. Comput. Syst. Sci. Eric Allender, Michael E. Saks, Igor E. Shparlinski
2001	J	`jnl`	Sample Spaces with Small Bias on Neighborhoods and Error-Correcting Communication Protocols. Algorithmica Michael E. Saks, Shiyu Zhou
2001	J	`jnl`	Time-Space Tradeoffs for Branching Programs. J. Comput. Syst. Sci. Paul Beame, T. S. Jayram, Michael E. Saks
2000	J	`jnl`	A Decomposition Theorem for Task Systems and Bounds for Randomized Server Problems. SIAM J. Comput. Avrim Blum, Howard J. Karloff, Yuval Rabani, Michael E. Saks
2000	A	`conf`	A Dual Version of Reimer's Inequality and a Proof of Rudich's Conjecture. CCC Jeff Kahn, Michael E. Saks, Cliff Smyth
2000	J	`jnl`	Exponential lower bounds for depth three Boolean circuits. Comput. Complex. Ramamohan Paturi, Michael E. Saks, Francis Zane
2000	J	`jnl`	Low discrepancy sets yield approximate min-wise independent permutation families. Inf. Process. Lett. Michael E. Saks, Aravind Srinivasan, Shiyu Zhou, David Zuckerman
2000	J	`jnl`	Super-Linear Time-Space Tradeoff Lower Bounds for Randomized Computation Electron. Colloquium Comput. Complex. Paul Beame, Michael E. Saks, Xiaodong Sun, Erik Vee
2000	A*	`conf`	Super-linear time-space tradeoff lower bounds for randomized computation. FOCS Paul Beame, Michael E. Saks, Xiaodong Sun, Erik Vee
2000	J	`jnl`	Wait-Free k-Set Agreement is Impossible: The Topology of Public Knowledge. SIAM J. Comput. Michael E. Saks, Fotios Zaharoglou
1999	J	`jnl`	A Lower Bound for Primality Electron. Colloquium Comput. Complex. Eric Allender, Igor E. Shparlinski, Michael E. Saks
1999	A	`conf`	A Lower Bound for Primality. CCC Eric Allender, Michael E. Saks, Igor E. Shparlinski
1999	J	`jnl`	BP J. Comput. Syst. Sci. Michael E. Saks, Shiyu Zhou
1999	—	`conf`	Low Discrepancy Sets Yield Approximate Min-Wise Independent Permutation Families. RANDOM-APPROX Michael E. Saks, Aravind Srinivasan, Shiyu Zhou, David Zuckerman
1999	A*	`conf`	Lower Bounds for Leader Election and Collective Coin-Flipping in the Perfect Information Model. STOC Alexander Russell, Michael E. Saks, David Zuckerman
1999	A	`conf`	On List Update and Work Function Algorithms. ESA Eric J. Anderson, Kirsten Hildrum, Anna R. Karlin, April Rasala, Michael E. Saks
1999	J	`jnl`	Optimal Space Distributed Order-Preserving Lists. J. Algorithms Michael E. Saks, Fotios Zaharoglou
1999	J	`jnl`	Products and Help Bits in Decision Trees. SIAM J. Comput. Noam Nisan, Steven Rudich, Michael E. Saks
1998	A*	`conf`	An Improved Exponential-Time Algorithm for FOCS Ramamohan Paturi, Pavel Pudlák, Michael E. Saks, Francis Zane
1998	J	`jnl`	Explicit OR-Dispersers with Polylogarithmic Degree. J. ACM Michael E. Saks, Aravind Srinivasan, Shiyu Zhou
1998	A*	`conf`	On the Complexity of Unsatisfiability Proofs for Random STOC Paul Beame, Richard M. Karp, Toniann Pitassi, Michael E. Saks
1998	J	`jnl`	Time-Space Tradeoffs for Branching Programs Electron. Colloquium Comput. Complex. Paul Beame, Michael E. Saks, Jayram S. Thathachar
1998	A*	`conf`	Time-Space Tradeoffs for Branching Programs. FOCS Paul Beame, Michael E. Saks, Jayram S. Thathachar
1998	A*	`conf`	Trees and Euclidean Metrics. STOC Nathan Linial, Avner Magen, Michael E. Saks
1997	J	`jnl`	Efficient Construction of a Small Hitting Set for Combinatorial Rectangles in High Dimension. Comb. Nathan Linial, Michael Luby, Michael E. Saks, David Zuckerman
1997	A*	`conf`	Exponential Lower Bounds for Depth 3 Boolean Circuits. STOC Ramamohan Paturi, Michael E. Saks, Francis Zane
1997	A*	`ed.`	Proceedings of the Eighth Annual ACM-SIAM Symposium on Discrete Algorithms, 5-7 January 1997, New Orleans, Louisiana, USA. SODA Michael E. Saks
1997	—	`conf`	Sample Spaces with Small Bias on Neighborhoods and Error-Correcting Communication Protocols. RANDOM Michael E. Saks, Shiyu Zhou
1997	J	`jnl`	Size-Depth Tradeoffs for Threshold Circuits. SIAM J. Comput. Russell Impagliazzo, Ramamohan Paturi, Michael E. Saks
1996	A*	`conf`	Discrepancy Sets and Pseudorandom Generators for Combinatorial Rectangles. FOCS Roy Armoni, Michael E. Saks, Avi Wigderson, Shiyu Zhou
1996	J	`jnl`	Local Management of a Global Resource in a Communication Network. J. ACM Yehuda Afek, Baruch Awerbuch, Serge A. Plotkin, Michael E. Saks
1996	A	`conf`	Randomization and Derandomization in Space_Bounded Computation. CCC Michael E. Saks
1996	A*	`conf`	Randomized Robot Navigation Algorithms. SODA Piotr Berman, Avrim Blum, Amos Fiat, Howard J. Karloff, Adi Rosén, Michael E. Saks
1996	J	`jnl`	Witness Sets for Families of Binary Vectors. J. Comb. Theory A Eyal Kushilevitz, Nathan Linial, Yuri Rabinovich, Michael E. Saks
1995	A*	`conf`	Explicit dispersers with polylog degree. STOC Michael E. Saks, Aravind Srinivasan, Shiyu Zhou
1995	J	`jnl`	On the bandwidth of triangulated triangles. Discret. Math. Robert Hochberg, Colin McDiarmid, Michael E. Saks
1995	A*	`conf`	RSPACE(S) \subseteq DSPACE(S FOCS Michael E. Saks, Shiyu Zhou
1994	J	`jnl`	A Complexity Index for Satisfiability Problems. SIAM J. Comput. Endre Boros, Yves Crama, Peter L. Hammer, Michael E. Saks
1994	J	`jnl`	Approximating Threshold Circuits by Rational Functions Inf. Comput. Ramamohan Paturi, Michael E. Saks
1994	J	`jnl`	Non-Deterministic Communication Complexity with Few Witnesses. J. Comput. Syst. Sci. Mauricio Karchmer, Ilan Newman, Michael E. Saks, Avi Wigderson
1994	A*	`conf`	Products and Help Bits in Decision Trees FOCS Noam Nisan, Steven Rudich, Michael E. Saks
1993	J	`jnl`	Combinatorial characterization of read-once formulae. Discret. Math. Mauricio Karchmer, Nathan Linial, Ilan Newman, Michael E. Saks, Avi Wigderson
1993	J	`jnl`	Communication Complexity and Combinatorial Lattice Theory. J. Comput. Syst. Sci. László Lovász, Michael E. Saks
1993	J	`jnl`	Correlation inequalities and a conjecture for permanents. Comb. Yosef Rinott, Michael E. Saks
1993	A*	`conf`	Efficient construction of a small hitting set for combinatorial rectangles in high dimension. STOC Nathan Linial, Michael Luby, Michael E. Saks, David Zuckerman
1993	J	`jnl`	Low diameter graph decompositions. Comb. Nathan Linial, Michael E. Saks
1993	A*	`conf`	Size-depth trade-offs for threshold circuits. STOC Russell Impagliazzo, Ramamohan Paturi, Michael E. Saks
1993	—	`conf`	Sphere Packing and Local Majorities in Graphs. ISTCS Nathan Linial, David Peleg, Yuri Rabinovich, Michael E. Saks
1993	J	`jnl`	The Number of Distinct Subset Sums of a Finite Set of Vectors. J. Comb. Theory A Ernest F. Brickell, Michael E. Saks
1993	A*	`conf`	Wait-free k-set agreement is impossible: the topology of public knowledge. STOC Michael E. Saks, Fotios Zaharoglou
1992	B	`conf`	A Complexity Index for Satisfiability Problems. IPCO Endre Boros, Yves Crama, Peter L. Hammer, Michael E. Saks
1992	A*	`conf`	A Decomposition Theorem and Bounds for Randomized Server Problems FOCS Avrim Blum, Howard J. Karloff, Yuval Rabani, Michael E. Saks
1992	A*	`conf`	Adapting to Asynchronous Dynamic Networks (Extended Abstract) STOC Baruch Awerbuch, Boaz Patt-Shamir, David Peleg, Michael E. Saks
1992	J	`jnl`	An Optimal On-Line Algorithm for Metrical Task System. J. ACM Allan Borodin, Nathan Linial, Michael E. Saks
1992	—	`conf`	Non-deterministic Communication Complexity with Few Witness. SCT Mauricio Karchmer, Ilan Newman, Michael E. Saks, Avi Wigderson
1992	J	`jnl`	Sharpening the LYM inequality. Comb. Péter L. Erdös, Peter Frankl, Daniel J. Kleitman, Michael E. Saks, László A. Székely
1991	A*	`conf`	Decomposing Graphs into Regions of Small Diameter. SODA Nathan Linial, Michael E. Saks
1991	J	`jnl`	On computing majority by comparisons. Comb. Michael E. Saks, Michael Werman
1991	A*	`conf`	Optimal Space Distributed Move-to-Front Lists. PODC Michael E. Saks, Fotios Zaharoglou
1991	A*	`conf`	Optimal Time Randomized Consensus - Making Resilient Algorithms Fast in Practice. SODA Michael E. Saks, Nir Shavit, Heather Woll
1990	A*	`conf`	A Dining Philosophers Algorithm with Polynomial Response Time FOCS Baruch Awerbuch, Michael E. Saks
1990	A*	`conf`	On Threshold Circuits for Parity FOCS Ramamohan Paturi, Michael E. Saks
1990	A*	`conf`	On Threshold Circuits for Parity (Abstract). COLT Ramamohan Paturi, Michael E. Saks
1989	J	`jnl`	A Robust Noncryptographic Protocol for Collective Coin Flipping. SIAM J. Discret. Math. Michael E. Saks
1989	J	`jnl`	A dynamic location problem for graphs. Comb. Fan R. K. Chung, Ronald L. Graham, Michael E. Saks
1989	J	`jnl`	An on-line graph coloring algorithm with sublinear performance ratio. Discret. Math. László Lovász, Michael E. Saks, William T. Trotter
1989	J	`jnl`	Some extremal problems arising form discrete control processes. Comb. David Lichtenstein, Nathan Linial, Michael E. Saks
1989	A*	`conf`	The Cell Probe Complexity of Dynamic Data Structures STOC Michael L. Fredman, Michael E. Saks
1989	J	`jnl`	The periodic balanced sorting network. J. ACM Martin Dowd, Yehoshua Perl, Larry Rudolph, Michael E. Saks
1988	J	`jnl`	A Limit Theorem for (min, +) Matrix Multiplication. Math. Oper. Res. Michael E. Saks
1988	J	`jnl`	An intersection problem for finite automata. Discret. Appl. Math. Michael E. Saks, Rick Statman
1988	A*	`conf`	Lattices, Möbius Functions and Communication Complexity FOCS László Lovász, Michael E. Saks
1987	A*	`conf`	An Optimal Online Algorithm for Metrical Task Systems STOC Allan Borodin, Nathan Linial, Michael E. Saks
1987	A*	`conf`	Detecting Global Termination Conditions in the Face of Uncertainty. PODC Yehuda Afek, Michael E. Saks
1987	J	`jnl`	Every finite distributive lattice is a set of stable matchings for a small stable marriage instance. J. Comb. Theory A Dan Gusfield, Robert W. Irving, Paul Leather, Michael E. Saks
1987	A*	`conf`	Imperfect Random Sources and Discrete Controlled Processes STOC David Lichtenstein, Nathan Linial, Michael E. Saks
1987	A*	`conf`	Local Management of a Global Resource in a Communication Network FOCS Yehuda Afek, Baruch Awerbuch, Serge A. Plotkin, Michael E. Saks
1987	J	`jnl`	On the widths of finite distributive lattices. Discret. Math. Jeff Kahn, Michael E. Saks
1987	J	`jnl`	Subgraphs of large connectivity and chromatic number in graphs of large chromatic number. J. Graph Theory Noga Alon, Daniel J. Kleitman, Carsten Thomassen, Michael E. Saks, Paul D. Seymour
1987	J	`jnl`	The smallets n-uniform hypergraph with positive discrepancy. Comb. Noga Alon, Daniel J. Kleitman, Carl Pomerance, Michael E. Saks, Paul D. Seymour
1986	J	`jnl`	Maximum induced trees in graphs. J. Comb. Theory B Paul Erdös, Michael E. Saks, Vera T. Sós
1986	A*	`conf`	On a Search Problem Related to Branch-and-Bound Procedures FOCS Richard M. Karp, Michael E. Saks, Avi Wigderson
1986	A*	`conf`	Probabilistic Boolean Decision Trees and the Complexity of Evaluating Game Trees FOCS Michael E. Saks, Avi Wigderson
1986	J	`jnl`	Some sequences associated with combinatorial structures. Discret. Math. Michael E. Saks
1985	J	`jnl`	Every Poset Has a Central Element. J. Comb. Theory A Nathan Linial, Michael E. Saks
1985	J	`jnl`	Searching Ordered Structures. J. Algorithms Nathan Linial, Michael E. Saks
1984	J	`jnl`	A polyomino with no stochastic function. Comb. Jeff Kahn, Michael E. Saks
1984	J	`jnl`	A topological approach to evasiveness. Comb. Jeff Kahn, Michael E. Saks, Dean Sturtevant
1984	A*	`conf`	Every Poset Has a Good Comparison STOC Jeff Kahn, Michael E. Saks
1983	A*	`conf`	A Topological Approach to Evasiveness FOCS Jeff Kahn, Michael E. Saks, Dean Sturtevant
1983	A*	`conf`	Information Bounds Are Good for Search Problems on Ordered Data Structures FOCS Nathan Linial, Michael E. Saks
1983	J	`jnl`	Largest digraphs contained in all n-tournaments. Comb. Nathan Linial, Michael E. Saks, Vera T. Sós
1983	A*	`conf`	The Balanced Sorting Network. PODC Martin Dowd, Yehoshua Perl, Michael E. Saks
1980	J	`jnl`	Dilworth Numbers, Incidence Maps and Product Partial Orders. SIAM J. Algebraic Discret. Methods Michael E. Saks
1980	J	`jnl`	Product partial orders with the sperner property. Discret. Math. Robert A. Proctor, Michael E. Saks, Dean G. Sturtevant
1979	J	`jnl`	Group labelings of graphs. J. Graph Theory Paul H. Edelman, Michael E. Saks