An optimal on-line algorithm for metrical task system A Borodin, N Linial, ME Saks Journal of the ACM (JACM) 39 (4), 745-763, 1992 | 632 | 1992 |
The cell probe complexity of dynamic data structures M Fredman, M Saks Proceedings of the twenty-first annual ACM symposium on Theory of computing …, 1989 | 467 | 1989 |
An improved exponential-time algorithm for k-SAT R Paturi, P Pudlák, ME Saks, F Zane Journal of the ACM (JACM) 52 (3), 337-364, 2005 | 407 | 2005 |
Competitive auctions AV Goldberg, JD Hartline, AR Karlin, M Saks, A Wright Games and Economic behavior 55 (2), 242-269, 2006 | 399 | 2006 |
Wait-free k-set agreement is impossible: The topology of public knowledge M Saks, F Zaharoglou SIAM Journal on Computing 29 (5), 1449-1483, 2000 | 313 | 2000 |
Probabilistic Boolean decision trees and the complexity of evaluating game trees M Saks, A Wigderson 27th Annual Symposium on Foundations of Computer Science (sfcs 1986), 29-38, 1986 | 257 | 1986 |
A topological approach to evasiveness J Kahn, M Saks, D Sturtevant Combinatorica 4, 297-306, 1984 | 229 | 1984 |
Weak monotonicity suffices for truthfulness on convex domains M Saks, L Yu Proceedings of the 6th ACM conference on Electronic commerce, 286-293, 2005 | 226 | 2005 |
Low diameter graph decompositions N Linial, M Saks Combinatorica 13 (4), 441-454, 1993 | 220 | 1993 |
An on-line graph coloring algorithm with sublinear performance ratio L Lovász, M Saks, WT Trotter Discrete Mathematics 75 (1-3), 319-325, 1989 | 189 | 1989 |
Wait-free k-set agreement is impossible: the topology of public knowledge M Saks, F Zaharoglou Proceedings of the twenty-fifth annual ACM symposium on Theory of computing …, 1993 | 178 | 1993 |
Lattices, mobius functions and communications complexity L Lovász, M Saks [Proceedings 1988] 29th Annual Symposium on Foundations of Computer Science …, 1988 | 170 | 1988 |
Every decision tree has an influential variable R O'Donnell, M Saks, O Schramm, RA Servedio 46th annual IEEE symposium on foundations of computer science (FOCS'05), 31-39, 2005 | 157 | 2005 |
The efficiency of resolution and Davis--Putnam procedures P Beame, R Karp, T Pitassi, M Saks SIAM Journal on Computing 31 (4), 1048-1075, 2002 | 150 | 2002 |
On the complexity of unsatisfiability proofs for random k-CNF formulas P Beame, R Karp, T Pitassi, M Saks Proceedings of the thirtieth annual ACM symposium on Theory of computing …, 1998 | 149 | 1998 |
Orthogonal representations and connectivity of graphs L Lovász, M Saks, A Schrijver Linear Algebra and its applications 114, 439-454, 1989 | 147 | 1989 |
Maximum induced trees in graphs P Erdös, M Saks, VT Sós Journal of Combinatorial Theory, Series B 41 (1), 61-79, 1986 | 147 | 1986 |
The periodic balanced sorting network M Dowd, Y Perl, L Rudolph, M Saks Journal of the ACM (JACM) 36 (4), 738-757, 1989 | 138 | 1989 |
bphspace (S)⊆ dspace (S3/2) M Saks, S Zhou Journal of computer and system sciences 58 (2), 376-403, 1999 | 137 | 1999 |
On the cover time of random walks on graphs JD Kahn, N Linial, N Nisan, ME Saks Journal of Theoretical Probability 2, 121-128, 1989 | 134 | 1989 |