 | 2009 |
|---|
| 123 |       | 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) |
| 2008 |
|---|
| 122 | | Michael E. Saks,
C. Seshadhri:
Parallel monotonicity reconstruction.
SODA 2008: 962-971 |
| 121 | | Moses Charikar,
Howard J. Karloff,
Claire Mathieu,
Joseph Naor,
Michael E. Saks:
Online multicast with egalitarian cost sharing.
SPAA 2008: 70-76 |
| 120 | | Ramamohan Paturi,
Pavel Pudlák,
Michael E. Saks,
Francis Zane:
Backtracking Based k-SAT Algorithms.
Encyclopedia of Algorithms 2008 |
| 119 | | Srikrishnan Divakaran,
Michael E. Saks:
Approximation algorithms for problems in scheduling with set-ups.
Discrete Applied Mathematics 156(5): 719-729 (2008) |
| 118 | | Navin Goyal,
Guy Kindler,
Michael E. Saks:
Lower Bounds for the Noisy Broadcast Problem.
SIAM J. Comput. 37(6): 1806-1841 (2008) |
| 117 | | Eric Allender,
Lisa Hellerstein,
Paul McCabe,
Toniann Pitassi,
Michael E. Saks:
Minimizing Disjunctive Normal Form Formulas and AC0 Circuits Given a Truth Table.
SIAM J. Comput. 38(1): 63-84 (2008) |
| 2007 |
|---|
| 116 | | 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) |
| 2006 |
|---|
| 115 | | Eric Allender,
Lisa Hellerstein,
Paul McCabe,
Toniann Pitassi,
Michael E. Saks:
Minimizing DNF Formulas and AC0d Circuits Given a Truth Table.
IEEE Conference on Computational Complexity 2006: 237-251 |
| 114 | | Nathan Linial,
Michael E. Saks,
David Statter:
The Non-Crossing Graph.
Electr. J. Comb. 13(1): (2006) |
| 113 | | László Lovász,
Michael E. Saks:
A localization inequality for set functions.
J. Comb. Theory, Ser. A 113(4): 726-735 (2006) |
| 2005 |
|---|
| 112 | | Michael E. Saks,
Lan Yu:
Weak monotonicity suffices for truthfulness on convex domains.
ACM Conference on Electronic Commerce 2005: 286-293 |
| 111 | | Ryan O'Donnell,
Michael E. Saks,
Oded Schramm,
Rocco A. Servedio:
Every decision tree has an in.uential variable.
FOCS 2005: 31-39 |
| 110 | | Navin Goyal,
Guy Kindler,
Michael E. Saks:
Lower Bounds for the Noisy Broadcast Problem.
FOCS 2005: 40-52 |
| 109 | | Navin Goyal,
Michael E. Saks:
Rounds vs queries trade-off in noisy computation.
SODA 2005: 632-639 |
| 108 | | 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 |
| 107 | | Ryan O'Donnell,
Michael E. Saks,
Oded Schramm,
Rocco A. Servedio:
Every decision tree has an influential variable
CoRR abs/cs/0508071: (2005) |
| 106 | | 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) |
| 105 | | 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) |
| 104 | | Navin Goyal,
Michael E. Saks:
A parallel search game.
Random Struct. Algorithms 27(2): 227-234 (2005) |
| 2004 |
|---|
| 103 | | 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 |
| 102 | | 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) |
| 101 | | 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) |
| 2003 |
|---|
| 100 | | Howard Barnum,
Michael E. Saks,
Mario Szegedy:
Quantum query complexity and semi-definite programming.
IEEE Conference on Computational Complexity 2003: 179-193 |
| 99 | | Navin Goyal,
Michael E. Saks,
Srinivasan Venkatesh:
Optimal Separation of EROW and CROWPRAMs.
IEEE Conference on Computational Complexity 2003: 93- |
| 98 | | 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) |
| 97 | | Nathan Linial,
Michael E. Saks:
The Euclidean Distortion of Complete Binary Trees.
Discrete & Computational Geometry 29(1): 19-21 (2003) |
| 96 | | 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) |
| 2002 |
|---|
| 95 | | Michael E. Saks,
Xiaodong Sun:
Space lower bounds for distance approximation in the data stream model.
STOC 2002: 360-369 |
| 94 | | Howard Barnum,
Michael E. Saks:
A lower bound on the quantum query complexity of read-once functions
CoRR quant-ph/0201007: (2002) |
| 93 | | Michael E. Saks:
Kleitman and combinatorics.
Discrete Mathematics 257(2-3): 225-247 (2002) |
| 92 | | 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) |
| 91 | | 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) |
| 90 | | 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) |
| 89 |  | 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) |
| 2001 |
|---|
| 88 | | Michael E. Saks,
Shiyu Zhou:
Sample Spaces with Small Bias on Neighborhoods and Error-Correcting Communication Protocols.
Algorithmica 30(3): 418-431 (2001) |
| 87 | | Eric Allender,
Michael E. Saks,
Igor Shparlinski:
A Lower Bound for Primality.
J. Comput. Syst. Sci. 62(2): 356-366 (2001) |
| 86 | | Paul Beame,
T. S. Jayram,
Michael E. Saks:
Time-Space Tradeoffs for Branching Programs.
J. Comput. Syst. Sci. 63(4): 542-572 (2001) |
| 2000 |
|---|
| 85 | | Paul Beame,
Michael E. Saks,
Xiaodong Sun,
Erik Vee:
Super-linear time-space tradeoff lower bounds for randomized computation.
FOCS 2000: 169-179 |
| 84 | | 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 |
| 83 | | Ramamohan Paturi,
Michael E. Saks,
Francis Zane:
Exponential lower bounds for depth three Boolean circuits.
Computational Complexity 9(1): 1-15 (2000) |
| 82 | | 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) |
| 81 | | 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) |
| 80 | | 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) |
| 79 | | 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) |
| 1999 |
|---|
| 78 | | Eric J. Anderson,
Kirsten Hildrum,
Anna R. Karlin,
April Rasala,
Michael E. Saks:
On List Update and Work Function Algorithms.
ESA 1999: 289-300 |
| 77 | | Eric Allender,
Michael E. Saks,
Igor Shparlinski:
A Lower Bound for Primality.
IEEE Conference on Computational Complexity 1999: 10-14 |
| 76 | | Michael E. Saks,
Aravind Srinivasan,
Shiyu Zhou,
David Zuckerman:
Low Discrepancy Sets Yield Approximate Min-Wise Independent Permutation Families.
RANDOM-APPROX 1999: 11-15 |
| 75 | | 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 |
| 74 | | Eric Allender,
Igor Shparlinski,
Michael E. Saks:
A Lower Bound for Primality
Electronic Colloquium on Computational Complexity (ECCC) 6(10): (1999) |
| 73 | | Michael E. Saks,
Fotios Zaharoglou:
Optimal Space Distributed Order-Preserving Lists.
J. Algorithms 31(2): 320-334 (1999) |
| 72 | | Michael E. Saks,
Shiyu Zhou:
BP HSpace(S) subseteq DSPACE(S3/2).
J. Comput. Syst. Sci. 58(2): 376-403 (1999) |
| 71 | | Noam Nisan,
Steven Rudich,
Michael E. Saks:
Products and Help Bits in Decision Trees.
SIAM J. Comput. 28(3): 1035-1050 (1999) |
| 1998 |
|---|
| 70 | | Paul Beame,
Michael E. Saks,
Jayram S. Thathachar:
Time-Space Tradeoffs for Branching Programs.
FOCS 1998: 254-263 |
| 69 | | Ramamohan Paturi,
Pavel Pudlák,
Michael E. Saks,
Francis Zane:
An Improved Exponential-Time Algorithm for k-SAT.
FOCS 1998: 628-637 |
| 68 | | Nathan Linial,
Avner Magen,
Michael E. Saks:
Trees and Euclidean Metrics.
STOC 1998: 169-175 |
| 67 | | 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 |
| 66 | | Paul Beame,
Michael E. Saks,
Jayram S. Thathachar:
Time-Space Tradeoffs for Branching Programs
Electronic Colloquium on Computational Complexity (ECCC) 5(53): (1998) |
| 65 | | Michael E. Saks,
Aravind Srinivasan,
Shiyu Zhou:
Explicit OR-Dispersers with Polylogarithmic Degree.
J. ACM 45(1): 123-154 (1998) |
| 1997 |
|---|
| 64 | | Michael E. Saks,
Shiyu Zhou:
Sample Spaces with Small Bias on Neighborhoods and Error-Correcting Communication Protocols.
RANDOM 1997: 95-109 |
| 63 | | Ramamohan Paturi,
Michael E. Saks,
Francis Zane:
Exponential Lower Bounds for Depth 3 Boolean Circuits.
STOC 1997: 86-91 |
| 62 | | 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) |
| 61 | | Russell Impagliazzo,
Ramamohan Paturi,
Michael E. Saks:
Size-Depth Tradeoffs for Threshold Circuits.
SIAM J. Comput. 26(3): 693-707 (1997) |
| 1996 |
|---|
| 60 | | Roy Armoni,
Michael E. Saks,
Avi Wigderson,
Shiyu Zhou:
Discrepancy Sets and Pseudorandom Generators for Combinatorial Rectangles.
FOCS 1996: 412-421 |
| 59 | | Michael E. Saks:
Randomization and Derandomization in Space_Bounded Computation.
IEEE Conference on Computational Complexity 1996: 128-149 |
| 58 | | Piotr Berman,
Avrim Blum,
Amos Fiat,
Howard J. Karloff,
Adi Rosén,
Michael E. Saks:
Randomized Robot Navigation Algorithms.
SODA 1996: 75-84 |
| 57 | | 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) |
| 56 | | 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) |
| 1995 |
|---|
| 55 | | Michael E. Saks,
Shiyu Zhou:
RSPACE(S) \subseteq DSPACE(S3/2).
FOCS 1995: 344-353 |
| 54 | | Michael E. Saks,
Aravind Srinivasan,
Shiyu Zhou:
Explicit dispersers with polylog degree.
STOC 1995: 479-488 |
| 53 | | Robert Hochberg,
Colin McDiarmid,
Michael E. Saks:
On the bandwidth of triangulated triangles.
Discrete Mathematics 138(1-3): 261-265 (1995) |
| 1994 |
|---|
| 52 | | Noam Nisan,
Steven Rudich,
Michael E. Saks:
Products and Help Bits in Decision Trees
FOCS 1994: 318-329 |
| 51 | | Ramamohan Paturi,
Michael E. Saks:
Approximating Threshold Circuits by Rational Functions
Inf. Comput. 112(2): 257-272 (1994) |
| 50 | | 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) |
| 49 | | Endre Boros,
Yves Crama,
Peter L. Hammer,
Michael E. Saks:
A Complexity Index for Satisfiability Problems.
SIAM J. Comput. 23(1): 45-49 (1994) |
| 1993 |
|---|
| 48 | | Nathan Linial,
David Peleg,
Yuri Rabinovich,
Michael E. Saks:
Sphere Packing and Local Majorities in Graphs.
ISTCS 1993: 141-149 |
| 47 | | Michael E. Saks,
Fotios Zaharoglou:
Wait-free k-set agreement is impossible: the topology of public knowledge.
STOC 1993: 101-110 |
| 46 | | 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 |
| 45 | | Russell Impagliazzo,
Ramamohan Paturi,
Michael E. Saks:
Size-depth trade-offs for threshold circuits.
STOC 1993: 541-550 |
| 44 | | Yosef Rinott,
Michael E. Saks:
Correlation inequalities and a conjecture for permanents.
Combinatorica 13(3): 269-277 (1993) |
| 43 | | Nathan Linial,
Michael E. Saks:
Low diameter graph decompositions.
Combinatorica 13(4): 441-454 (1993) |
| 42 | | 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) |
| 41 | | 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) |
| 40 | | László Lovász,
Michael E. Saks:
Communication Complexity and Combinatorial Lattice Theory.
J. Comput. Syst. Sci. 47(2): 322-349 (1993) |
| 1992 |
|---|
| 39 | | Avrim Blum,
Howard J. Karloff,
Yuval Rabani,
Michael E. Saks:
A Decomposition Theorem and Bounds for Randomized Server Problems
FOCS 1992: 197-207 |
| 38 | | Endre Boros,
Yves Crama,
Peter L. Hammer,
Michael E. Saks:
A Complexity Index for Satisfiability Problems.
IPCO 1992: 220-226 |
| 37 | | Baruch Awerbuch,
Boaz Patt-Shamir,
David Peleg,
Michael E. Saks:
Adapting to Asynchronous Dynamic Networks (Extended Abstract)
STOC 1992: 557-570 |
| 36 | | Mauricio Karchmer,
Ilan Newman,
Michael E. Saks,
Avi Wigderson:
Non-deterministic Communication Complexity with Few Witness.
Structure in Complexity Theory Conference 1992: 275-281 |
| 35 | | 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) |
| 34 | | Allan Borodin,
Nathan Linial,
Michael E. Saks:
An Optimal On-Line Algorithm for Metrical Task System.
J. ACM 39(4): 745-763 (1992) |
| 1991 |
|---|
| 33 | | Michael E. Saks,
Fotios Zaharoglou:
Optimal Space Distributed Move-to-Front Lists.
PODC 1991: 65-73 |
| 32 | | Nathan Linial,
Michael E. Saks:
Decomposing Graphs into Regions of Small Diameter.
SODA 1991: 320-330 |
| 31 | | Michael E. Saks,
Nir Shavit,
Heather Woll:
Optimal Time Randomized Consensus - Making Resilient Algorithms Fast in Practice.
SODA 1991: 351-362 |
| 30 | | Michael E. Saks,
Michael Werman:
On computing majority by comparisons.
Combinatorica 11(4): 383-387 (1991) |
| 1990 |
|---|
| 29 | | Ramamohan Paturi,
Michael E. Saks:
On Threshold Circuits for Parity (Abstract).
COLT 1990: 390 |
| 28 | | Ramamohan Paturi,
Michael E. Saks:
On Threshold Circuits for Parity
FOCS 1990: 397-404 |
| 27 | | Baruch Awerbuch,
Michael E. Saks:
A Dining Philosophers Algorithm with Polynomial Response Time
FOCS 1990: 65-74 |
| 1989 |
|---|
| 26 | | Michael L. Fredman,
Michael E. Saks:
The Cell Probe Complexity of Dynamic Data Structures
STOC 1989: 345-354 |
| 25 | | Fan R. K. Chung,
Ronald L. Graham,
Michael E. Saks:
A dynamic location problem for graphs.
Combinatorica 9(2): 111-131 (1989) |
| 24 | | David Lichtenstein,
Nathan Linial,
Michael E. Saks:
Some extremal problems arising form discrete control processes.
Combinatorica 9(3): 269-287 (1989) |
| 23 | | 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) |
| 22 | | Martin Dowd,
Yehoshua Perl,
Larry Rudolph,
Michael E. Saks:
The periodic balanced sorting network.
J. ACM 36(4): 738-757 (1989) |
| 21 | | Michael E. Saks:
A Robust Noncryptographic Protocol for Collective Coin Flipping.
SIAM J. Discrete Math. 2(2): 240-244 (1989) |
| 1988 |
|---|
| 20 | | László Lovász,
Michael E. Saks:
Lattices, Möbius Functions and Communication Complexity
FOCS 1988: 81-90 |
| 1987 |
|---|
| 19 | | Yehuda Afek,
Baruch Awerbuch,
Serge A. Plotkin,
Michael E. Saks:
Local Management of a Global Resource in a Communication Network
FOCS 1987: 347-357 |
| 18 | | Yehuda Afek,
Michael E. Saks:
Detecting Global Termination Conditions in the Face of Uncertainty.
PODC 1987: 109-124 |
| 17 | | David Lichtenstein,
Nathan Linial,
Michael E. Saks:
Imperfect Random Sources and Discrete Controlled Processes
STOC 1987: 169-177 |
| 16 | | Allan Borodin,
Nathan Linial,
Michael E. Saks:
An Optimal Online Algorithm for Metrical Task Systems
STOC 1987: 373-382 |
| 15 | | 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) |
| 14 | | Jeff Kahn,
Michael E. Saks:
On the widths of finite distributive lattices.
Discrete Mathematics 63(2-3): 183-195 (1987) |
| 13 | | 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) |
| 1986 |
|---|
| 12 | | Richard M. Karp,
Michael E. Saks,
Avi Wigderson:
On a Search Problem Related to Branch-and-Bound Procedures
FOCS 1986: 19-28 |
| 11 | | Michael E. Saks,
Avi Wigderson:
Probabilistic Boolean Decision Trees and the Complexity of Evaluating Game Trees
FOCS 1986: 29-38 |
| 10 | | Michael E. Saks:
Some sequences associated with combinatorial structures.
Discrete Mathematics 59(1-2): 135-166 (1986) |
| 9 | | 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) |
| 1985 |
|---|
| 8 | | Nathan Linial,
Michael E. Saks:
Searching Ordered Structures.
J. Algorithms 6(1): 86-103 (1985) |
| 1984 |
|---|
| 7 | | Jeff Kahn,
Michael E. Saks:
Every Poset Has a Good Comparison
STOC 1984: 299-301 |
| 6 | | Jeff Kahn,
Michael E. Saks:
A polyomino with no stochastic function.
Combinatorica 4(2): 181-182 (1984) |
| 5 | | Jeff Kahn,
Michael E. Saks,
Dean Sturtevant:
A topological approach to evasiveness.
Combinatorica 4(4): 297-306 (1984) |
| 1983 |
|---|
| 4 | | Jeff Kahn,
Michael E. Saks,
Dean Sturtevant:
A Topological Approach to Evasiveness
FOCS 1983: 31-33 |
| 3 | | Nathan Linial,
Michael E. Saks:
Information Bounds Are Good for Search Problems on Ordered Data Structures
FOCS 1983: 473-475 |
| 2 | | Martin Dowd,
Yehoshua Perl,
Michael E. Saks:
The Balanced Sorting Network.
PODC 1983: 161-172 |
| 1 | | Nathan Linial,
Michael E. Saks,
Vera T. Sós:
Largest digraphs contained in all n-tournaments.
Combinatorica 3(1): 101-104 (1983) |
