2009 |
123 | EE | 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 | EE | Michael E. Saks,
C. Seshadhri:
Parallel monotonicity reconstruction.
SODA 2008: 962-971 |
121 | EE | Moses Charikar,
Howard J. Karloff,
Claire Mathieu,
Joseph Naor,
Michael E. Saks:
Online multicast with egalitarian cost sharing.
SPAA 2008: 70-76 |
120 | EE | Ramamohan Paturi,
Pavel Pudlák,
Michael E. Saks,
Francis Zane:
Backtracking Based k-SAT Algorithms.
Encyclopedia of Algorithms 2008 |
119 | EE | Srikrishnan Divakaran,
Michael E. Saks:
Approximation algorithms for problems in scheduling with set-ups.
Discrete Applied Mathematics 156(5): 719-729 (2008) |
118 | EE | Navin Goyal,
Guy Kindler,
Michael E. Saks:
Lower Bounds for the Noisy Broadcast Problem.
SIAM J. Comput. 37(6): 1806-1841 (2008) |
117 | EE | 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 | EE | 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 | EE | 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 | EE | Nathan Linial,
Michael E. Saks,
David Statter:
The Non-Crossing Graph.
Electr. J. Comb. 13(1): (2006) |
113 | EE | 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 | EE | Michael E. Saks,
Lan Yu:
Weak monotonicity suffices for truthfulness on convex domains.
ACM Conference on Electronic Commerce 2005: 286-293 |
111 | EE | Ryan O'Donnell,
Michael E. Saks,
Oded Schramm,
Rocco A. Servedio:
Every decision tree has an in.uential variable.
FOCS 2005: 31-39 |
110 | EE | Navin Goyal,
Guy Kindler,
Michael E. Saks:
Lower Bounds for the Noisy Broadcast Problem.
FOCS 2005: 40-52 |
109 | EE | Navin Goyal,
Michael E. Saks:
Rounds vs queries trade-off in noisy computation.
SODA 2005: 632-639 |
108 | EE | 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 | EE | Ryan O'Donnell,
Michael E. Saks,
Oded Schramm,
Rocco A. Servedio:
Every decision tree has an influential variable
CoRR abs/cs/0508071: (2005) |
106 | EE | 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 | EE | 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 | EE | Navin Goyal,
Michael E. Saks:
A parallel search game.
Random Struct. Algorithms 27(2): 227-234 (2005) |
2004 |
103 | EE | 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 | EE | 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 | EE | 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 | EE | Howard Barnum,
Michael E. Saks,
Mario Szegedy:
Quantum query complexity and semi-definite programming.
IEEE Conference on Computational Complexity 2003: 179-193 |
99 | EE | Navin Goyal,
Michael E. Saks,
Srinivasan Venkatesh:
Optimal Separation of EROW and CROWPRAMs.
IEEE Conference on Computational Complexity 2003: 93- |
98 | EE | 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 | EE | Nathan Linial,
Michael E. Saks:
The Euclidean Distortion of Complete Binary Trees.
Discrete & Computational Geometry 29(1): 19-21 (2003) |
96 | EE | 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 | EE | Michael E. Saks,
Xiaodong Sun:
Space lower bounds for distance approximation in the data stream model.
STOC 2002: 360-369 |
94 | EE | Howard Barnum,
Michael E. Saks:
A lower bound on the quantum query complexity of read-once functions
CoRR quant-ph/0201007: (2002) |
93 | EE | Michael E. Saks:
Kleitman and combinatorics.
Discrete Mathematics 257(2-3): 225-247 (2002) |
92 | EE | 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 | EE | 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 | EE | 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 | EE | 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 | EE | 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 | EE | 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 | EE | Ramamohan Paturi,
Michael E. Saks,
Francis Zane:
Exponential lower bounds for depth three Boolean circuits.
Computational Complexity 9(1): 1-15 (2000) |
82 | EE | 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 | EE | 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 | EE | 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 | EE | 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 | EE | 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 | EE | 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 | EE | 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 | EE | Paul Beame,
Michael E. Saks,
Jayram S. Thathachar:
Time-Space Tradeoffs for Branching Programs.
FOCS 1998: 254-263 |
69 | EE | Ramamohan Paturi,
Pavel Pudlák,
Michael E. Saks,
Francis Zane:
An Improved Exponential-Time Algorithm for k-SAT.
FOCS 1998: 628-637 |
68 | EE | Nathan Linial,
Avner Magen,
Michael E. Saks:
Trees and Euclidean Metrics.
STOC 1998: 169-175 |
67 | EE | 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 | EE | Paul Beame,
Michael E. Saks,
Jayram S. Thathachar:
Time-Space Tradeoffs for Branching Programs
Electronic Colloquium on Computational Complexity (ECCC) 5(53): (1998) |
65 | EE | 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 | EE | 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 | EE | 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 | EE | 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 | EE | 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 | EE | Michael E. Saks,
Aravind Srinivasan,
Shiyu Zhou:
Explicit dispersers with polylog degree.
STOC 1995: 479-488 |
53 | EE | 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 | EE | Michael E. Saks,
Fotios Zaharoglou:
Wait-free k-set agreement is impossible: the topology of public knowledge.
STOC 1993: 101-110 |
46 | EE | 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 | EE | 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 | EE | 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 | EE | 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 | EE | 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 | EE | 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 | EE | 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 | EE | Jeff Kahn,
Michael E. Saks:
On the widths of finite distributive lattices.
Discrete Mathematics 63(2-3): 183-195 (1987) |
13 | EE | 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 | EE | Michael E. Saks:
Some sequences associated with combinatorial structures.
Discrete Mathematics 59(1-2): 135-166 (1986) |
9 | EE | 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) |