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
5141992
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
3791989
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
3252005
Competitive auctions
AV Goldberg, JD Hartline, AR Karlin, M Saks, A Wright
Games and Economic Behavior 55 (2), 242-269, 2006
2982006
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
2502000
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
2241986
A topological approach to evasiveness
J Kahn, M Saks, D Sturtevant
Combinatorica 4 (4), 297-306, 1984
1891984
Weak monotonicity suffices for truthfulness on convex domains
M Saks, L Yu
Proceedings of the 6th ACM conference on Electronic commerce, 286-293, 2005
1852005
Low diameter graph decompositions
N Linial, M Saks
Combinatorica 13 (4), 441-454, 1993
1571993
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
1531989
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
1401993
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
1382002
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
1351998
The periodic balanced sorting network
M Dowd, Y Perl, L Rudolph, M Saks
Journal of the ACM (JACM) 36 (4), 738-757, 1989
1301989
Lattices, mobius functions and communications complexity
L Lovász, M Saks
[Proceedings 1988] 29th Annual Symposium on Foundations of Computer Science …, 1988
1261988
Maximum induced trees in graphs
P Erdös, M Saks, VT Sós
Journal of Combinatorial Theory, Series B 41 (1), 61-79, 1986
1231986
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
1082002
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
1051989
Time–space tradeoffs for branching programs
P Beame, TS Jayram, M Saks
Journal of Computer and System Sciences 63 (4), 542-572, 2001
1042001
Time-space trade-off lower bounds for randomized computation of decision problems
P Beame, M Saks, X Sun, E Vee
Journal of the ACM (JACM) 50 (2), 154-195, 2003
972003
The system can't perform the operation now. Try again later.
Articles 1–20