Michael E. Saks

Michael Saks, C. Seshadhri: Space efficient streaming algorithms for the distance to monotonicity and asymmetric edit distance. SODA 2013: 1698-1709

Yonatan Bilu, Amit Daniely, Nati Linial, Michael Saks: On the practically interesting instances of MAXCUT. STACS 2013: 526-537

Ankur Moitra, Michael Saks: A Polynomial Time Algorithm for Lossy Population Recovery. CoRR abs/1302.1515 (2013)

Martin Babka, Jan Bulánek, Vladimír Cunát, Michal Koucký, Michael Saks: On Online Labeling with Polynomially Many Labels. ESA 2012: 121-132

Jan Bulánek, Michal Koucký, Michael Saks: Tight lower bounds for the online labeling problem. STOC 2012: 1185-1198

Michael Saks, C. Seshadhri: Space efficient streaming algorithms for the distance to monotonicity and asymmetric edit distance. CoRR abs/1204.1098 (2012)

Dmitry Gavinsky, Shachar Lovett, Michael Saks, Srikanth Srinivasan: A Tail Bound for Read-k Families of Functions. CoRR abs/1205.1478 (2012)

Amit Daniely, Nati Linial, Michael Saks: Clustering is difficult only when it does not matter. CoRR abs/1205.4891 (2012)

Yonatan Bilu, Amit Daniely, Nati Linial, Michael Saks: On the practically interesting instances of MAXCUT. CoRR abs/1205.4893 (2012)

Martin Babka, Jan Bulánek, Vladimír Cunát, Michal Koucký, Michael Saks: On Online Labeling with Polynomially Many Labels. CoRR abs/1210.3197 (2012)

Dmitry Gavinsky, Shachar Lovett, Michael E. Saks, Srikanth Srinivasan: A Tail Bound for Read-k Families of Functions. Electronic Colloquium on Computational Complexity (ECCC) 19: 51 (2012)

Srikrishnan Divakaran, Michael E. Saks: An Online Algorithm for a Problem in Scheduling with Set-ups and Release Times. Algorithmica 60(2): 301-315 (2011)

Jeff Kahn, Michael Saks, Clifford D. Smyth: The Dual BKR Inequality and Rudich's Conjecture. Combinatorics, Probability & Computing 20(2): 257-266 (2011)

Jan Bulánek, Michal Koucký, Michael Saks: Tight lower bounds for online labeling problem. CoRR abs/1112.5636 (2011)

Nikos Leonardos, Michael Saks: Lower Bounds on the Randomized Communication Complexity of Read-Once Functions. Computational Complexity 19(2): 153-181 (2010)

Michael E. Saks, C. Seshadhri: Local Monotonicity Reconstruction. SIAM J. Comput. 39(7): 2897-2926 (2010)

Navin Goyal, Michael Saks: Rounds vs. Queries Tradeoff in Noisy Computation. Theory of Computing 6(1): 113-134 (2010)

Michael Saks, C. Seshadhri: Estimating the Longest Increasing Sequence in Polylogarithmic Time. FOCS 2010: 458-467

Michael Saks, C. Seshadhri: Local Property Reconstruction and Monotonicity. Property Testing 2010: 346-354

József Balogh, Béla Bollobás, Michael E. Saks, Vera T. Sós: The unlabelled speed of a hereditary graph property. J. Comb. Theory, Ser. B 99(1): 9-19 (2009)

Nikos Leonardos, Michael Saks: Lower Bounds on the Randomized Communication Complexity of Read-Once Functions. IEEE Conference on Computational Complexity 2009: 341-350

Nikos Leonardos, Michael E. Saks: Lower bounds on the randomized communication complexity of read-once functions. Electronic Colloquium on Computational Complexity (ECCC) 16: 10 (2009)

Srikrishnan Divakaran, Michael E. Saks: Approximation algorithms for problems in scheduling with set-ups. Discrete Applied Mathematics 156(5): 719-729 (2008)

Navin Goyal, Guy Kindler, Michael E. Saks: Lower Bounds for the Noisy Broadcast Problem. SIAM J. Comput. 37(6): 1806-1841 (2008)

Eric Allender, Lisa Hellerstein, Paul McCabe, Toniann Pitassi, Michael E. Saks: Minimizing Disjunctive Normal Form Formulas and AC⁰ Circuits Given a Truth Table. SIAM J. Comput. 38(1): 63-84 (2008)

Michael E. Saks, C. Seshadhri: Parallel monotonicity reconstruction. SODA 2008: 962-971

Moses Charikar, Howard J. Karloff, Claire Mathieu, Joseph Naor, Michael E. Saks: Online multicast with egalitarian cost sharing. SPAA 2008: 70-76

Ramamohan Paturi, Pavel Pudlák, Michael E. Saks, Francis Zane: Backtracking Based k-SAT Algorithms. Encyclopedia of Algorithms 2008

Zdenek Dvorak, Vít Jelínek, Daniel Král, Jan Kyncl, Michael E. Saks: Probabilistic strategies for the partition and plurality problems. Random Struct. Algorithms 30(1-2): 63-77 (2007)

Nathan Linial, Michael E. Saks, David Statter: The Non-Crossing Graph. Electr. J. Comb. 13(1) (2006)

Andrew V. Goldberg, Jason D. Hartline, Anna R. Karlin, Michael Saks, Andrew Wright: Competitive auctions. Games and Economic Behavior 55(2): 242-269 (2006)

László Lovász, Michael E. Saks: A localization inequality for set functions. J. Comb. Theory, Ser. A 113(4): 726-735 (2006)

Eric Allender, Lisa Hellerstein, Paul McCabe, Toniann Pitassi, Michael E. Saks: Minimizing DNF Formulas and AC⁰_d Circuits Given a Truth Table. IEEE Conference on Computational Complexity 2006: 237-251

Ramamohan Paturi, Pavel Pudlák, Michael E. Saks, Francis Zane: An improved exponential-time algorithm for k-SAT. J. ACM 52(3): 337-364 (2005)

Navin Goyal, Michael E. Saks: A parallel search game. Random Struct. Algorithms 27(2): 227-234 (2005)

Ryan O'Donnell, Michael E. Saks, Oded Schramm, Rocco A. Servedio: Every decision tree has an in.uential variable. FOCS 2005: 31-39

Navin Goyal, Guy Kindler, Michael E. Saks: Lower Bounds for the Noisy Broadcast Problem. FOCS 2005: 40-52

Michael E. Saks, Lan Yu: Weak monotonicity suffices for truthfulness on convex domains. ACM Conference on Electronic Commerce 2005: 286-293

Navin Goyal, Michael E. Saks: Rounds vs queries trade-off in noisy computation. SODA 2005: 632-639

Zdenek Dvorak, Vít Jelínek, Daniel Král, Jan Kyncl, Michael E. Saks: Three Optimal Algorithms for Balls of Three Colors. STACS 2005: 206-217

Ryan O'Donnell, Michael E. Saks, Oded Schramm, Rocco A. Servedio: Every decision tree has an influential variable. CoRR abs/cs/0508071 (2005)

Eric Allender, Lisa Hellerstein, Paul McCabe, Toniann Pitassi, Michael E. Saks: Minimizing DNF Formulas and AC0 Circuits Given a Truth Table. Electronic Colloquium on Computational Complexity (ECCC)(126) (2005)

Michael E. Saks, Alex Samorodnitsky, Leonid Zosin: A Lower Bound On The Integrality Gap For Minimum Multicut In Directed Networks. Combinatorica 24(3): 525-530 (2004)

Howard Barnum, Michael E. Saks: A lower bound on the quantum query complexity of read-once functions. J. Comput. Syst. Sci. 69(2): 244-258 (2004)

Andrew V. Goldberg, Jason D. Hartline, Anna R. Karlin, Michael E. Saks: A Lower Bound on the Competitive Ratio of Truthful Auctions. STACS 2004: 644-655

Eric Allender, Anna Bernasconi, Carsten Damm, Joachim von zur Gathen, Michael E. Saks, Igor Shparlinski: Complexity of some arithmetic problems for binary polynomials. Computational Complexity 12(1-2): 23-47 (2003)

Nathan Linial, Michael E. Saks: The Euclidean Distortion of Complete Binary Trees. Discrete & Computational Geometry 29(1): 19-21 (2003)

Paul Beame, Michael E. Saks, Xiaodong Sun, Erik Vee: Time-space trade-off lower bounds for randomized computation of decision problems. J. ACM 50(2): 154-195 (2003)

Navin Goyal, Michael E. Saks, Srinivasan Venkatesh: Optimal Separation of EROW and CROWPRAMs. IEEE Conference on Computational Complexity 2003: 93-

Howard Barnum, Michael E. Saks, Mario Szegedy: Quantum query complexity and semi-definite programming. IEEE Conference on Computational Complexity 2003: 179-193

Michael E. Saks: Kleitman and combinatorics. Discrete Mathematics 257(2-3): 225-247 (2002)

Paul Beame, Richard M. Karp, Toniann Pitassi, Michael E. Saks: The Efficiency of Resolution and Davis--Putnam Procedures. SIAM J. Comput. 31(4): 1048-1075 (2002)

Alexander Russell, Michael E. Saks, David Zuckerman: Lower Bounds for Leader Election and Collective Coin-Flipping in the Perfect Information Model. SIAM J. Comput. 31(6): 1645-1662 (2002)

Eric J. Anderson, Kirsten Hildrum, Anna R. Karlin, April Rasala, Michael E. Saks: On list update and work function algorithms. Theor. Comput. Sci. 287(2): 393-418 (2002)

Michael E. Saks, Xiaodong Sun: Space lower bounds for distance approximation in the data stream model. STOC 2002: 360-369

Howard Barnum, Michael E. Saks: A lower bound on the quantum query complexity of read-once functions. CoRR quant-ph/0201007 (2002)

Howard Barnum, Michael E. Saks: A lower bound on the quantum query complexity of read-once functions. Electronic Colloquium on Computational Complexity (ECCC)(002) (2002)

Michael E. Saks, Shiyu Zhou: Sample Spaces with Small Bias on Neighborhoods and Error-Correcting Communication Protocols. Algorithmica 30(3): 418-431 (2001)

Eric Allender, Michael E. Saks, Igor Shparlinski: A Lower Bound for Primality. J. Comput. Syst. Sci. 62(2): 356-366 (2001)

Paul Beame, T. S. Jayram, Michael E. Saks: Time-Space Tradeoffs for Branching Programs. J. Comput. Syst. Sci. 63(4): 542-572 (2001)

Ramamohan Paturi, Michael E. Saks, Francis Zane: Exponential lower bounds for depth three Boolean circuits. Computational Complexity 9(1): 1-15 (2000)

Michael E. Saks, Aravind Srinivasan, Shiyu Zhou, David Zuckerman: Low discrepancy sets yield approximate min-wise independent permutation families. Inf. Process. Lett. 73(1-2): 29-32 (2000)

Michael E. Saks, Fotios Zaharoglou: Wait-Free k-Set Agreement is Impossible: The Topology of Public Knowledge. SIAM J. Comput. 29(5): 1449-1483 (2000)

Avrim Blum, Howard J. Karloff, Yuval Rabani, Michael E. Saks: A Decomposition Theorem for Task Systems and Bounds for Randomized Server Problems. SIAM J. Comput. 30(5): 1624-1661 (2000)

Jeff Kahn, Michael E. Saks, Clifford D. Smyth: A Dual Version of Reimer's Inequality and a Proof of Rudich's Conjecture. IEEE Conference on Computational Complexity 2000: 98-103

Paul Beame, Michael E. Saks, Xiaodong Sun, Erik Vee: Super-linear time-space tradeoff lower bounds for randomized computation. FOCS 2000: 169-179

Paul Beame, Michael E. Saks, Xiaodong Sun, Erik Vee: Super-Linear Time-Space Tradeoff Lower Bounds for Randomized Computation. Electronic Colloquium on Computational Complexity (ECCC) 7(25) (2000)

Michael E. Saks, Fotios Zaharoglou: Optimal Space Distributed Order-Preserving Lists. J. Algorithms 31(2): 320-334 (1999)

Michael E. Saks, Shiyu Zhou: BP _HSpace(S) subseteq DSPACE(S^3/2). J. Comput. Syst. Sci. 58(2): 376-403 (1999)

Noam Nisan, Steven Rudich, Michael E. Saks: Products and Help Bits in Decision Trees. SIAM J. Comput. 28(3): 1035-1050 (1999)

Eric Allender, Michael E. Saks, Igor Shparlinski: A Lower Bound for Primality. IEEE Conference on Computational Complexity 1999: 10-14

Eric J. Anderson, Kirsten Hildrum, Anna R. Karlin, April Rasala, Michael E. Saks: On List Update and Work Function Algorithms. ESA 1999: 289-300

Michael E. Saks, Aravind Srinivasan, Shiyu Zhou, David Zuckerman: Low Discrepancy Sets Yield Approximate Min-Wise Independent Permutation Families. RANDOM-APPROX 1999: 11-15

Alexander Russell, Michael E. Saks, David Zuckerman: Lower Bounds for Leader Election and Collective Coin-Flipping in the Perfect Information Model. STOC 1999: 339-347

Eric Allender, Igor Shparlinski, Michael E. Saks: A Lower Bound for Primality. Electronic Colloquium on Computational Complexity (ECCC) 6(10) (1999)

Michael E. Saks, Aravind Srinivasan, Shiyu Zhou: Explicit OR-Dispersers with Polylogarithmic Degree. J. ACM 45(1): 123-154 (1998)

Paul Beame, Michael E. Saks, Jayram S. Thathachar: Time-Space Tradeoffs for Branching Programs. FOCS 1998: 254-263

Ramamohan Paturi, Pavel Pudlák, Michael E. Saks, Francis Zane: An Improved Exponential-Time Algorithm for k-SAT. FOCS 1998: 628-637

Nathan Linial, Avner Magen, Michael E. Saks: Trees and Euclidean Metrics. STOC 1998: 169-175

Paul Beame, Richard M. Karp, Toniann Pitassi, Michael E. Saks: On the Complexity of Unsatisfiability Proofs for Random k-CNF Formulas. STOC 1998: 561-571

Paul Beame, Michael E. Saks, Jayram S. Thathachar: Time-Space Tradeoffs for Branching Programs. Electronic Colloquium on Computational Complexity (ECCC) 5(53) (1998)

Nathan Linial, Michael Luby, Michael E. Saks, David Zuckerman: Efficient Construction of a Small Hitting Set for Combinatorial Rectangles in High Dimension. Combinatorica 17(2): 215-234 (1997)

Russell Impagliazzo, Ramamohan Paturi, Michael E. Saks: Size-Depth Tradeoffs for Threshold Circuits. SIAM J. Comput. 26(3): 693-707 (1997)

Michael E. Saks, Shiyu Zhou: Sample Spaces with Small Bias on Neighborhoods and Error-Correcting Communication Protocols. RANDOM 1997: 95-109

Ramamohan Paturi, Michael E. Saks, Francis Zane: Exponential Lower Bounds for Depth 3 Boolean Circuits. STOC 1997: 86-91

Michael E. Saks (Ed.): Proceedings of the Eighth Annual ACM-SIAM Symposium on Discrete Algorithms, 5-7 January 1997, New Orleans, Louisiana. ACM/SIAM 1997, isbn 0-89871-390-0

Yehuda Afek, Baruch Awerbuch, Serge A. Plotkin, Michael E. Saks: Local Management of a Global Resource in a Communication Network. J. ACM 43(1): 1-19 (1996)

Eyal Kushilevitz, Nathan Linial, Yuri Rabinovich, Michael E. Saks: Witness Sets for Families of Binary Vectors. J. Comb. Theory, Ser. A 73(2): 376-380 (1996)

Michael E. Saks: Randomization and Derandomization in Space_Bounded Computation. IEEE Conference on Computational Complexity 1996: 128-149

Roy Armoni, Michael E. Saks, Avi Wigderson, Shiyu Zhou: Discrepancy Sets and Pseudorandom Generators for Combinatorial Rectangles. FOCS 1996: 412-421

Piotr Berman, Avrim Blum, Amos Fiat, Howard J. Karloff, Adi Rosén, Michael E. Saks: Randomized Robot Navigation Algorithms. SODA 1996: 75-84

Robert Hochberg, Colin McDiarmid, Michael E. Saks: On the bandwidth of triangulated triangles. Discrete Mathematics 138(1-3): 261-265 (1995)

Michael E. Saks, Shiyu Zhou: RSPACE(S) \subseteq DSPACE(S^3/2). FOCS 1995: 344-353

Michael E. Saks, Aravind Srinivasan, Shiyu Zhou: Explicit dispersers with polylog degree. STOC 1995: 479-488

Ramamohan Paturi, Michael E. Saks: Approximating Threshold Circuits by Rational Functions. Inf. Comput. 112(2): 257-272 (1994)

Mauricio Karchmer, Ilan Newman, Michael E. Saks, Avi Wigderson: Non-Deterministic Communication Complexity with Few Witnesses. J. Comput. Syst. Sci. 49(2): 247-257 (1994)

Endre Boros, Yves Crama, Peter L. Hammer, Michael E. Saks: A Complexity Index for Satisfiability Problems. SIAM J. Comput. 23(1): 45-49 (1994)

Noam Nisan, Steven Rudich, Michael E. Saks: Products and Help Bits in Decision Trees. FOCS 1994: 318-329

Yosef Rinott, Michael E. Saks: Correlation inequalities and a conjecture for permanents. Combinatorica 13(3): 269-277 (1993)

Nathan Linial, Michael E. Saks: Low diameter graph decompositions. Combinatorica 13(4): 441-454 (1993)

Mauricio Karchmer, Nathan Linial, Ilan Newman, Michael E. Saks, Avi Wigderson: Combinatorial characterization of read-once formulae. Discrete Mathematics 114(1-3): 275-282 (1993)

László Lovász, Michael E. Saks: Communication Complexity and Combinatorial Lattice Theory. J. Comput. Syst. Sci. 47(2): 322-349 (1993)

Ernest Brickell, Michael E. Saks: The Number of Distinct Subset Sums of a Finite Set of Vectors. J. Comb. Theory, Ser. A 63(2): 234-256 (1993)

Nathan Linial, David Peleg, Yuri Rabinovich, Michael E. Saks: Sphere Packing and Local Majorities in Graphs. ISTCS 1993: 141-149

Michael E. Saks, Fotios Zaharoglou: Wait-free k-set agreement is impossible: the topology of public knowledge. STOC 1993: 101-110

Nathan Linial, Michael Luby, Michael E. Saks, David Zuckerman: Efficient construction of a small hitting set for combinatorial rectangles in high dimension. STOC 1993: 258-267

Russell Impagliazzo, Ramamohan Paturi, Michael E. Saks: Size-depth trade-offs for threshold circuits. STOC 1993: 541-550

Péter L. Erdös, Peter Frankl, Daniel J. Kleitman, Michael E. Saks, László A. Székely: Sharpening the LYM inequality. Combinatorica 12(3): 287-293 (1992)

Allan Borodin, Nathan Linial, Michael E. Saks: An Optimal On-Line Algorithm for Metrical Task System. J. ACM 39(4): 745-763 (1992)

Mauricio Karchmer, Ilan Newman, Michael E. Saks, Avi Wigderson: Non-deterministic Communication Complexity with Few Witness. Structure in Complexity Theory Conference 1992: 275-281

Avrim Blum, Howard J. Karloff, Yuval Rabani, Michael E. Saks: A Decomposition Theorem and Bounds for Randomized Server Problems. FOCS 1992: 197-207

Endre Boros, Yves Crama, Peter L. Hammer, Michael E. Saks: A Complexity Index for Satisfiability Problems. IPCO 1992: 220-226

Baruch Awerbuch, Boaz Patt-Shamir, David Peleg, Michael E. Saks: Adapting to Asynchronous Dynamic Networks (Extended Abstract). STOC 1992: 557-570

Michael E. Saks, Michael Werman: On computing majority by comparisons. Combinatorica 11(4): 383-387 (1991)

Michael E. Saks, Fotios Zaharoglou: Optimal Space Distributed Move-to-Front Lists. PODC 1991: 65-73

Nathan Linial, Michael E. Saks: Decomposing Graphs into Regions of Small Diameter. SODA 1991: 320-330

Michael E. Saks, Nir Shavit, Heather Woll: Optimal Time Randomized Consensus - Making Resilient Algorithms Fast in Practice. SODA 1991: 351-362

Ramamohan Paturi, Michael E. Saks: On Threshold Circuits for Parity (Abstract). COLT 1990: 390

Baruch Awerbuch, Michael E. Saks: A Dining Philosophers Algorithm with Polynomial Response Time. FOCS 1990: 65-74

Ramamohan Paturi, Michael E. Saks: On Threshold Circuits for Parity. FOCS 1990: 397-404

Fan R. K. Chung, Ronald L. Graham, Michael E. Saks: A dynamic location problem for graphs. Combinatorica 9(2): 111-131 (1989)

David Lichtenstein, Nathan Linial, Michael E. Saks: Some extremal problems arising form discrete control processes. Combinatorica 9(3): 269-287 (1989)

László Lovász, Michael E. Saks, William T. Trotter: An on-line graph coloring algorithm with sublinear performance ratio. Discrete Mathematics 75(1-3): 319-325 (1989)

Martin Dowd, Yehoshua Perl, Larry Rudolph, Michael E. Saks: The periodic balanced sorting network. J. ACM 36(4): 738-757 (1989)

Michael E. Saks: A Robust Noncryptographic Protocol for Collective Coin Flipping. SIAM J. Discrete Math. 2(2): 240-244 (1989)

Michael L. Fredman, Michael E. Saks: The Cell Probe Complexity of Dynamic Data Structures. STOC 1989: 345-354

Michael Saks, Rick Statman: An intersection problem for finite automata. Discrete Applied Mathematics 21(3): 245-255 (1988)

László Lovász, Michael E. Saks: Lattices, Möbius Functions and Communication Complexity. FOCS 1988: 81-90

Noga Alon, Daniel J. Kleitman, Carl Pomerance, Michael E. Saks, Paul D. Seymour: The smallets n-uniform hypergraph with positive discrepancy. Combinatorica 7(2): 151-160 (1987)

Jeff Kahn, Michael E. Saks: On the widths of finite distributive lattices. Discrete Mathematics 63(2-3): 183-195 (1987)

Dan Gusfield, Robert W. Irving, Paul Leather, Michael E. Saks: Every finite distributive lattice is a set of stable matchings for a small stable marriage instance. J. Comb. Theory, Ser. A 44(2): 304-309 (1987)

Yehuda Afek, Baruch Awerbuch, Serge A. Plotkin, Michael E. Saks: Local Management of a Global Resource in a Communication Network. FOCS 1987: 347-357

Yehuda Afek, Michael E. Saks: Detecting Global Termination Conditions in the Face of Uncertainty. PODC 1987: 109-124

David Lichtenstein, Nathan Linial, Michael E. Saks: Imperfect Random Sources and Discrete Controlled Processes. STOC 1987: 169-177

Allan Borodin, Nathan Linial, Michael E. Saks: An Optimal Online Algorithm for Metrical Task Systems. STOC 1987: 373-382

Michael E. Saks: Some sequences associated with combinatorial structures. Discrete Mathematics 59(1-2): 135-166 (1986)

Paul Erdös, Michael E. Saks, Vera T. Sós: Maximum induced trees in graphs. J. Comb. Theory, Ser. B 41(1): 61-79 (1986)

Richard M. Karp, Michael E. Saks, Avi Wigderson: On a Search Problem Related to Branch-and-Bound Procedures. FOCS 1986: 19-28

Michael E. Saks, Avi Wigderson: Probabilistic Boolean Decision Trees and the Complexity of Evaluating Game Trees. FOCS 1986: 29-38

Nathan Linial, Michael E. Saks: Searching Ordered Structures. J. Algorithms 6(1): 86-103 (1985)

Jeff Kahn, Michael E. Saks: A polyomino with no stochastic function. Combinatorica 4(2): 181-182 (1984)

Jeff Kahn, Michael E. Saks, Dean Sturtevant: A topological approach to evasiveness. Combinatorica 4(4): 297-306 (1984)

Jeff Kahn, Michael E. Saks: Every Poset Has a Good Comparison. STOC 1984: 299-301

Nathan Linial, Michael E. Saks, Vera T. Sós: Largest digraphs contained in all n-tournaments. Combinatorica 3(1): 101-104 (1983)

Jeff Kahn, Michael E. Saks, Dean Sturtevant: A Topological Approach to Evasiveness. FOCS 1983: 31-33

Nathan Linial, Michael E. Saks: Information Bounds Are Good for Search Problems on Ordered Data Structures. FOCS 1983: 473-475

Martin Dowd, Yehoshua Perl, Michael E. Saks: The Balanced Sorting Network. PODC 1983: 161-172