Michael Saks
Title
Cited by
Cited by
Year
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
5281992
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
4101989
Competitive auctions
AV Goldberg, JD Hartline, AR Karlin, M Saks, A Wright
Games and Economic Behavior 55 (2), 242-269, 2006
3502006
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
3462005
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
2692000
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
2291986
A topological approach to evasiveness
J Kahn, M Saks, D Sturtevant
Combinatorica 4 (4), 297-306, 1984
1981984
Weak monotonicity suffices for truthfulness on convex domains
M Saks, L Yu
Proceedings of the 6th ACM conference on Electronic commerce, 286-293, 2005
1962005
Low diameter graph decompositions
N Linial, M Saks
Combinatorica 13 (4), 441-454, 1993
1761993
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
1561989
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
1431993
Lattices, mobius functions and communications complexity
L Lovász, M Saks
[Proceedings 1988] 29th Annual Symposium on Foundations of Computer Science …, 1988
1391988
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
1362002
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
1341998
The periodic balanced sorting network
M Dowd, Y Perl, L Rudolph, M Saks
Journal of the ACM (JACM) 36 (4), 738-757, 1989
1341989
Maximum induced trees in graphs
P Erdös, M Saks, VT Sós
Journal of Combinatorial Theory, Series B 41 (1), 61-79, 1986
1291986
On the cover time of random walks on graphs
JD Kahn, N Linial, N Nisan, ME Saks
Journal of Theoretical Probability 2 (1), 121-128, 1989
1151989
Space lower bounds for distance approximation in the data stream model
M Saks, X Sun
Proceedings of the thiry-fourth annual ACM symposium on Theory of computing …, 2002
1112002
Optimal time randomized consensus—making resilient algorithms fast in practice
M Saks, N Shavit, H Woll
Proceedings of the second annual ACM-SIAM Symposium on Discrete algorithms …, 1991
1051991
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
1032005
The system can't perform the operation now. Try again later.
Articles 1–20