×

zbMATH — the first resource for mathematics

Saks, Michael E.

Compute Distance To:
Author ID: saks.michael-e Recent zbMATH articles by "Saks, Michael E."
Published as: Saks, M.; Saks, M. E.; Saks, Michael; Saks, Michael E.
Documents Indexed: 137 Publications since 1979
all top 5

Co-Authors

11 single-authored
18 Linial, Nathan
9 Koucký, Michal
6 Kahn, Jeff D.
6 Kleitman, Daniel J.
6 Paturi, Ramamohan
6 Seshadhri, Comandur
6 Zhou, Shiyu
6 Zuckerman, David
5 Bulánek, Jan
5 Lovász, László
4 Beame, Paul W.
4 Goyal, Navin
4 Sós, Vera Turán
4 Srinivasan, Aravind
4 Zaharoglou, Fotios
3 Allender, Eric W.
3 Blum, Avrim L.
3 Gilmer, Justin
3 Karlin, Anna R.
3 Karloff, Howard J.
3 Pitassi, Toniann
3 Sturtevant, Dean G.
3 Zane, Francis X.
2 Alon, Noga M.
2 Awerbuch, Baruch
2 Babka, Martin
2 Ben-Or, Michael
2 Chung Graham, Fan-Rong King
2 Divakaran, Srikrishnan
2 Dvořák, Zdeněk
2 Edelman, Paul H.
2 Goldberg, Andrew V.
2 Graham, Ronald Lewis
2 Hartline, Jason D.
2 Impagliazzo, Russell
2 Jelínek, Vít
2 Karp, Richard Manning
2 Kopparty, Swastik
2 Král’, Daniel
2 Kumar, Mrinal
2 Kyncl, Jan
2 Leonardos, Nikos
2 Luby, Michael G.
2 Magen, Avner
2 Naumovitz, Timothy
2 Nisan, Noam
2 Rabani, Yuval
2 Rinott, Yosef
2 Russell, Alexander C.
2 Schrijver, Alexander
2 Seymour, Paul D.
2 Shparlinski, Igor E.
2 Srinivasan, Srikanth
2 Sun, Xiaodong
2 von zur Gathen, Joachim
1 Afek, Yehuda
1 Anderson, Eric J.
1 Balogh, József
1 Barnum, Howard
1 Berman, Piotr
1 Bernasconi, Anna
1 Bilu, Yonatan
1 Bollobás, Béla
1 Borodin, Allan B.
1 Brickell, Ernest F.
1 Chaiken, Seth
1 Chandra, Ashok K.
1 Chattopadhyay, Arkadev
1 Chiarelli, John
1 Condon, Anne E.
1 Čunát, Vladimír
1 Čunát, Vladimŕ
1 Damm, Carsten
1 Daniely, Amit
1 Das, Debarati
1 Dowd, Martin
1 Erdős, Pál
1 Erdős, Péter L.
1 Feigenbaum, Joan
1 Fiat, Amos
1 Frankl, Péter
1 Franks, Cole
1 Gavinsky, Dmitry
1 Griggs, Jerrold R.
1 Guibas, Leonidas John
1 Gusfield, Dan
1 Halpern, Joseph Yehuda
1 Hatami, Pooya
1 Hellerstein, Lisa
1 Hildrum, Kirsten
1 Hochberg, Robert A.
1 Irving, Robert W.
1 Jayram, T. S.
1 Kindler, Guy
1 Kushilevitz, Eyal
1 Leather, Paul
1 Lee, Troy
1 Lichtenstein, David
1 Lovett, Shachar
1 McCabe, Paul
...and 34 more Co-Authors

Publications by Year

Citations contained in zbMATH

117 Publications have been cited 1,146 times in 1,011 Documents Cited by Year
Wait-free \(k\)-set agreement is impossible: The topology of public knowledge. Zbl 0952.68159
Saks, Michael; Zaharoglou, Fotios
44
2000
An improved exponential-time algorithm for \(k\)-SAT. Zbl 1297.68217
Paturi, Ramamohan; Pudlák, Pavel; Saks, Michael E.; Zane, Francis
41
2005
An optimal on-line algorithm for metrical task system. Zbl 0799.68035
Borodin, Allan; Linial, Nathan; Saks, Michael E.
40
1992
A topological approach to evasiveness. Zbl 0577.05061
Kahn, Jeff; Saks, Michael; Sturtevant, Dean
40
1984
An on-line graph coloring algorithm with sublinear performance ratio. Zbl 0679.05031
Lovász, László; Saks, Michael; Trotter, W. T.
39
1989
Competitive auctions. Zbl 1125.91041
Goldberg, Andrew V.; Hartline, Jason D.; Karlin, Anna R.; Saks, Michael; Wright, Andrew
35
2006
Orthogonal representations and connectivity of graphs. Zbl 0681.05048
Lovász, László; Saks, M.; Schrijver, A.
32
1989
Low diameter graph decompositions. Zbl 0790.05067
Linial, Nathan; Saks, Michael
31
1993
On computing majority by comparisons. Zbl 0739.05006
Saks, Michael E.; Werman, Michael
29
1991
Every finite distributive lattice is a set of stable matchings for a small stable marriage instance. Zbl 0616.06009
Gusfield, Dan; Irving, Robert; Leather, Paul; Saks, Michael
29
1987
Maximum induced trees in graphs. Zbl 0603.05023
Erdős, Paul; Saks, Michael; Sós, Vera T.
29
1986
On the cover time of random walks on graphs. Zbl 0681.60064
Kahn, Jeff D.; Linial, Nathan; Nisan, Noam; Saks, Michael E.
28
1989
A short proof of the existence of k-saturated partitions of partially ordered sets. Zbl 0429.05010
Saks, Michael
26
1979
The efficiency of resolution and Davis-Putnam procedures. Zbl 1004.03048
Beame, Paul; Karp, Richard; Pitassi, Toniann; Saks, Michael
23
2002
A dynamic location problem for graphs. Zbl 0692.05055
Chung, F. R. K.; Graham, R. L.; Saks, M. E.
23
1989
Product partial orders with the Sperner property. Zbl 0458.06001
Proctor, Robert A.; Saks, Michael E.; Sturtevant, Dean G.
23
1980
Slicing the hypercube. Zbl 0790.05062
Saks, Michael E.
21
1993
Combinatorial characterization of read-once formulae. Zbl 0781.06012
Karchmer, M.; Linial, N.; Newman, I.; Saks, M.; Wigderson, A.
21
1993
Balancing poset extensions. Zbl 0561.06004
Kahn, Jeff; Saks, Michael
20
1984
A complexity index for satisfiability problems. Zbl 0793.90038
Boros, E.; Crama, Y.; Hammer, P. L.; Saks, M.
19
1994
A correction: Orthogonal representations and connectivity of graphs. Zbl 0954.05032
Lovász, L.; Saks, M.; Schrijver, A.
18
2000
Covering regions by rectangles. Zbl 0506.05022
Chaiken, Seth; Kleitman, Daniel J.; Saks, Michael; Shearer, James
18
1981
Wait-free \(k\)-set agreement is impossible, the topology of public knowledge. Zbl 1310.68041
Saks, Michael; Zaharoglou, Fotios
17
1993
Communication complexity and combinatorial lattice theory. Zbl 0791.68083
Lovász, László; Saks, Michael
17
1993
Collective coin flipping and other models of imperfect randomness. Zbl 0675.90107
Ben Or, M.; Linial, N.; Saks, M.
17
1988
Combinatorial representation and convex dimension of convex geometries. Zbl 0659.06005
Edelman, Paul H.; Saks, Michael E.
17
1988
Searching ordered structures. Zbl 0578.68050
Linial, N.; Saks, M.
17
1985
Time-space tradeoffs for branching programs. Zbl 1052.68049
Beame, Paul; Jayram, T. S.; Saks, Michael
16
2001
The periodic balanced sorting network. Zbl 0698.68042
Dowd, Martin; Perl, Yehoshua; Rudolph, Larry; Saks, Michael
14
1989
Dynamic search in graphs. Zbl 0643.68083
Chung, F. R. K.; Graham, R. L.; Saks, M. E.
14
1987
Dilworth numbers, incidence maps and product partial orders. Zbl 0501.06003
Saks, Michael
14
1980
Minimizing disjunctive normal form formulas and \(\text{AC}^0\) circuits given a truth table. Zbl 1165.68030
Allender, Eric; Hellerstein, Lisa; McCabe, Paul; Pitassi, Toniann; Saks, Michael
13
2008
Time-space trade-off lower bounds for randomized computation of decision problems. Zbl 1326.68144
Beame, Paul; Saks, Michael; Sun, Xiaodong; Vee, Erik
13
2003
Optimal time randomized consensus - Making resilient algorithms fast in practice. Zbl 0800.68463
Saks, Michael; Shavit, Nir; Woll, Heather
12
1991
Local monotonicity reconstruction. Zbl 1213.68420
Saks, Michael; Seshadhri, C.
11
2010
On the complexity of unsatisfiability proofs for random \(k\)-CNF formulas. Zbl 1028.68067
Beame, Paul; Karp, Richard; Pitassi, Toniann; Saks, Michael
11
1998
Products and help bits in decision trees. Zbl 0918.68026
Nisan, Noam; Rudich, Steven; Saks, Michael
10
1999
On the bandwidth of triangulated triangles. Zbl 0823.05048
Hochberg, Robert; McDiarmid, Colin; Saks, Michael
10
1995
Largest digraphs contained in all n-tournaments. Zbl 0532.05032
Linial, N.; Saks, M.; Sós, Vera T.
10
1983
Space lower bounds for distance approximation in the data stream model. Zbl 1192.68331
Saks, Michael; Sun, Xiaodong
9
2002
Efficient construction of a small hitting set for combinatorial rectangles in high dimension. Zbl 0886.68076
Linial, N.; Luby, M.; Saks, M.; Zuckerman, D.
9
1997
Local management of a global resource in a communication network. Zbl 0882.68005
Afek, Yehuda; Awerbuch, Baruch; Plotkin, Serge; Saks, Michael
9
1996
Approximating threshold circuits by rational functions. Zbl 0820.68054
Paturi, Ramamohan; Saks, Michael E.
9
1994
Some sequences associated with combinatorial structures. Zbl 0588.05004
Saks, Michael
9
1986
A decomposition theorem for task systems and bounds for randomized server problems. Zbl 0977.68039
Blum, Avrim; Karloff, Howard; Rabani, Yuval; Saks, Michael
8
2000
Correlation inequalities and a conjecture for permanents. Zbl 0782.60020
Rinott, Yosef; Saks, Michael
8
1993
A decomposition theorem and bounds for randomized server problems. Zbl 0977.68543
Blum, Avrim; Karloff, Howard; Rabani, Yuval; Saks, Michael
8
1992
On unavoidable subgraphs of tournaments. Zbl 0566.05032
Saks, M.; Sós, Vera T.
8
1984
Size-depth tradeoffs for threshold circuits. Zbl 0870.68069
Impagliazzo, Russell; Paturi, Ramamohan; Saks, Michael E.
7
1997
Randomized robot navigation algorithms. Zbl 0960.68593
Berman, Piotr; Blum, Avrim; Fiat, Amos; Karloff, Howard; Rosén, Adi; Saks, Michael
7
1996
Decomposing graphs into regions of small diameter. Zbl 0785.05073
Linial, Nathan; Saks, Michael
7
1991
Every poset has a central element. Zbl 0582.06002
Linial, Nathan; Saks, Michael
7
1985
On chains and Sperner k-families in ranked posets. II. Zbl 0463.06004
Griggs, Jerrold R.; Sturtevant, Dean; Saks, Michael
7
1980
Probabilistic strategies for the partition and plurality problems. Zbl 1281.91008
Dvořák, Zdeněk; Jelínek, Vít; Král’, Daniel; Kynčl, Jan; Saks, Michael
6
2007
A lower bound on the integrality gap for minimum multicut in directed networks. Zbl 1058.05033
Saks, Michael; Samorodnitsky, Alex; Zosin, Leonid
6
2004
Some extremal problems arising from discrete control processes. Zbl 0699.90110
Lichtenstein, D.; Linial, N.; Saks, M.
6
1989
A robust noncryptographic protocol for collective coin flipping. Zbl 0671.90109
Saks, Michael
6
1989
The smallest n-uniform hypergraph with positive discrepancy. Zbl 0629.05053
Alon, N.; Kleitman, D. J.; Pomerance, C.; Saks, M.; Seymour, P.
6
1987
Estimating the longest increasing sequence in polylogarithmic time. Zbl 1370.68342
Saks, M.; Seshadhri, C.
5
2017
A new approach to the sensitivity conjecture. Zbl 1364.68197
Gilmer, Justin; Koucký, Michal; Saks, Michael E.
5
2015
A lower bound on the quantum query complexity of read-once functions. Zbl 1083.68045
Barnum, Howard; Saks, Michael
5
2004
Low discrepancy sets yield approximate min-wise independent permutation families. Zbl 1339.68196
Saks, Michael; Srinivasan, Aravind; Zhou, Shiyu; Zuckerman, David
5
2000
Composition limits and separating examples for some Boolean function complexity measures. Zbl 1399.68074
Gilmer, Justin; Saks, Michael; Srinivasan, Srikanth
4
2016
An online algorithm for a problem in scheduling with set-ups and release times. Zbl 1215.68275
Divakaran, Srikrishnan; Saks, Michael
4
2011
The dual BKR inequality and Rudich’s conjecture. Zbl 1237.05190
Kahn, Jeff; Saks, Michael; Smyth, Clifford
4
2011
The unlabelled speed of a hereditary graph property. Zbl 1168.05042
Balogh, József; Bollobás, Béla; Saks, Michael; Sós, Vera T.
4
2009
Approximation algorithms for problems in scheduling with set-ups. Zbl 1135.90014
Divakaran, Srikrishnan; Saks, Michael
4
2008
The Euclidean distortion of complete binary trees. Zbl 1008.05040
Linial, Nathan; Saks, Michael
4
2003
A lower bound for primality. Zbl 1032.11058
Allender, Eric; Saks, Michael; Shparlinski, Igor
4
2001
Exponential lower bounds for depth three Boolean circuits. Zbl 0963.68147
Paturi, Ramamohan; Saks, Michael E.; Zane, Francis
4
2000
\(\text{BP}_{\text{H}}\text{SPACE}(S) \subseteq \text{DSPACE}(S^{3/2})\). Zbl 0922.68083
Saks, Michael; Zhou, Shiyu
4
1999
Witness sets for families of binary vectors. Zbl 0840.68103
Kushilevitz, Eyal; Linial, Nathan; Rabinovich, Yuri; Saks, Michael
4
1996
Sharpening the LYM inequality. Zbl 0769.05088
Erdös, Péter L.; Frankl, P.; Kleitman, D. J.; Saks, M. E.; Székely, László A.
4
1992
Efficient indexing of necklaces and irreducible polynomials over finite fields. Zbl 1373.11079
Kopparty, Swastik; Kumar, Mrinal; Saks, Michael
3
2014
Space efficient streaming algorithms for the distance to monotonicity and asymmetric edit distance. Zbl 1422.68333
Saks, Michael; Seshadhri, C.
3
2013
On the practically interesting instances of MAXCUT. Zbl 1354.68106
Bilu, Yonatan; Daniely, Amit; Linial, Nati; Saks, Michael
3
2013
Lower bounds on the randomized communication complexity of read-once functions. Zbl 1229.68042
Leonardos, Nikos; Saks, Michael
3
2010
Parallel monotonicity reconstruction. Zbl 1192.68842
Saks, Michael; Seshadhri, C.
3
2008
Kleitman and combinatorics. Zbl 1008.05148
Saks, Michael
3
2002
\(RSPACE(S)\subseteq DSPACE(S^{3/2})\). Zbl 0938.68706
Saks, Michael; Zhou, Shiyu
3
1995
Explicit dispersers with polylog degree. Zbl 0978.68555
Saks, Michael; Srinivasan, Aravind; Zhou, Shiyu
3
1995
Subgraphs of large connectivity and chromatic number in graphs of large chromatic number. Zbl 0647.05022
Alon, N.; Kleitman, D.; Thomassen, C.; Saks, M.; Seymour, P.
3
1987
Efficient indexing of necklaces and irreducible polynomials over finite fields. Zbl 1373.11080
Kopparty, Swastik; Kumar, Mrinal; Saks, Michael
2
2016
A tail bound for read-\(k\) families of functions. Zbl 1338.60082
Gavinsky, Dmitry; Lovett, Shachar; Saks, Michael; Srinivasan, Srikanth
2
2015
On online labeling with polynomially many labels. Zbl 1365.68475
Babka, Martin; Bulánek, Jan; Čunát, Vladimír; Koucký, Michal; Saks, Michael
2
2012
Three optimal algorithms for balls of three colors. Zbl 1118.91307
Dvořák, Zdeněk; Jelínek, Vít; Král’, Daniel; Kynčl, Jan; Saks, Michael
2
2005
A parallel search game. Zbl 1087.68025
Goyal, Navin; Saks, Michael
2
2005
Lower bounds for leader election and collective coin-flipping in the perfect information model. Zbl 1008.68053
Russell, Alexander; Saks, Michael; Zuckerman, David
2
2002
Lower bounds for leader election and collective coin-flipping in the perfect information model. Zbl 1345.68020
Russell, Alexander; Saks, Michael; Zuckerman, David
2
1999
Low discrepancy sets yield approximate min-wise independent permutation families. Zbl 0949.60015
Saks, Michael; Srinivasan, Aravind; Zhou, Shiyu; Zuckerman, David
2
1999
Trees and Euclidean metrics. Zbl 1029.68952
Linial, Nathan; Magen, Avner; Saks, Michael E.
2
1998
Explicit OR-dispersers with polylogarithmic degree. Zbl 0902.68081
Saks, Michael; Srinivasan, Aravind; Zhou, Shiyu
2
1998
Efficient construction of a small hitting set for combinatorial rectangles in high dimension. Zbl 1310.68207
Linial, Nati; Luby, Michael; Saks, Michael; Zuckerman, David
2
1993
On FKG-type and permanental inequalities. Zbl 1400.60035
Rinott, Yosef; Saks, Michael
2
1992
A limit theorem for \((\min,+)\) matrix multiplication. Zbl 0663.05012
Saks, Michael E.
2
1988
On the widths of finite distributive lattices. Zbl 0616.06010
Kahn, Jeff; Saks, Michael
2
1987
The information theoretic bound for problems on ordered sets and graphs. Zbl 0569.68036
Saks, Michael
2
1985
Set orderings requiring costliest alphabetic binary trees. Zbl 0498.68038
Kleitman, D. J.; Saks, Michael E.
2
1981
An asymptotically tight bound on the number of relevant variables in a bounded degree Boolean function. Zbl 07254955
Chiarelli, John; Hatami, Pooya; Saks, Michael
1
2020
A communication game related to the sensitivity conjecture. Zbl 1379.68151
Gilmer, Justin; Koucký, Michal; Saks, Michael
1
2017
An asymptotically tight bound on the number of relevant variables in a bounded degree Boolean function. Zbl 07254955
Chiarelli, John; Hatami, Pooya; Saks, Michael
1
2020
Estimating the longest increasing sequence in polylogarithmic time. Zbl 1370.68342
Saks, M.; Seshadhri, C.
5
2017
A communication game related to the sensitivity conjecture. Zbl 1379.68151
Gilmer, Justin; Koucký, Michal; Saks, Michael
1
2017
Composition limits and separating examples for some Boolean function complexity measures. Zbl 1399.68074
Gilmer, Justin; Saks, Michael; Srinivasan, Srikanth
4
2016
Efficient indexing of necklaces and irreducible polynomials over finite fields. Zbl 1373.11080
Kopparty, Swastik; Kumar, Mrinal; Saks, Michael
2
2016
A new approach to the sensitivity conjecture. Zbl 1364.68197
Gilmer, Justin; Koucký, Michal; Saks, Michael E.
5
2015
A tail bound for read-\(k\) families of functions. Zbl 1338.60082
Gavinsky, Dmitry; Lovett, Shachar; Saks, Michael; Srinivasan, Srikanth
2
2015
A polylogarithmic space deterministic streaming algorithm for approximating distance to monotonicity. Zbl 1372.68304
Naumovitz, Timothy; Saks, Michael
1
2015
Tight lower bounds for the online labeling problem. Zbl 1333.68096
Bulánek, Jan; Koucký, Michal; Saks, Michael
1
2015
Efficient indexing of necklaces and irreducible polynomials over finite fields. Zbl 1373.11079
Kopparty, Swastik; Kumar, Mrinal; Saks, Michael
3
2014
The power of super-logarithmic number of players. Zbl 1359.68084
Chattopadhyay, Arkadev; Saks, Michael E.
1
2014
Space efficient streaming algorithms for the distance to monotonicity and asymmetric edit distance. Zbl 1422.68333
Saks, Michael; Seshadhri, C.
3
2013
On the practically interesting instances of MAXCUT. Zbl 1354.68106
Bilu, Yonatan; Daniely, Amit; Linial, Nati; Saks, Michael
3
2013
On randomized online labeling with polynomially many labels. Zbl 1336.68284
Bulánek, Jan; Koucký, Michal; Saks, Michael
1
2013
On online labeling with polynomially many labels. Zbl 1365.68475
Babka, Martin; Bulánek, Jan; Čunát, Vladimír; Koucký, Michal; Saks, Michael
2
2012
An online algorithm for a problem in scheduling with set-ups and release times. Zbl 1215.68275
Divakaran, Srikrishnan; Saks, Michael
4
2011
The dual BKR inequality and Rudich’s conjecture. Zbl 1237.05190
Kahn, Jeff; Saks, Michael; Smyth, Clifford
4
2011
Local monotonicity reconstruction. Zbl 1213.68420
Saks, Michael; Seshadhri, C.
11
2010
Lower bounds on the randomized communication complexity of read-once functions. Zbl 1229.68042
Leonardos, Nikos; Saks, Michael
3
2010
The unlabelled speed of a hereditary graph property. Zbl 1168.05042
Balogh, József; Bollobás, Béla; Saks, Michael; Sós, Vera T.
4
2009
Minimizing disjunctive normal form formulas and \(\text{AC}^0\) circuits given a truth table. Zbl 1165.68030
Allender, Eric; Hellerstein, Lisa; McCabe, Paul; Pitassi, Toniann; Saks, Michael
13
2008
Approximation algorithms for problems in scheduling with set-ups. Zbl 1135.90014
Divakaran, Srikrishnan; Saks, Michael
4
2008
Parallel monotonicity reconstruction. Zbl 1192.68842
Saks, Michael; Seshadhri, C.
3
2008
Lower bounds for the noisy broadcast problem. Zbl 1178.68263
Goyal, Navin; Kindler, Guy; Saks, Michael
1
2008
Probabilistic strategies for the partition and plurality problems. Zbl 1281.91008
Dvořák, Zdeněk; Jelínek, Vít; Král’, Daniel; Kynčl, Jan; Saks, Michael
6
2007
Competitive auctions. Zbl 1125.91041
Goldberg, Andrew V.; Hartline, Jason D.; Karlin, Anna R.; Saks, Michael; Wright, Andrew
35
2006
A localization inequality for set functions. Zbl 1111.26018
Lovász, László; Saks, Michael
1
2006
An improved exponential-time algorithm for \(k\)-SAT. Zbl 1297.68217
Paturi, Ramamohan; Pudlák, Pavel; Saks, Michael E.; Zane, Francis
41
2005
Three optimal algorithms for balls of three colors. Zbl 1118.91307
Dvořák, Zdeněk; Jelínek, Vít; Král’, Daniel; Kynčl, Jan; Saks, Michael
2
2005
A parallel search game. Zbl 1087.68025
Goyal, Navin; Saks, Michael
2
2005
Rounds vs queries trade-off in noisy computation. Zbl 1297.68084
Goyal, Navin; Saks, Michael
1
2005
A lower bound on the integrality gap for minimum multicut in directed networks. Zbl 1058.05033
Saks, Michael; Samorodnitsky, Alex; Zosin, Leonid
6
2004
A lower bound on the quantum query complexity of read-once functions. Zbl 1083.68045
Barnum, Howard; Saks, Michael
5
2004
A lower bound on the competitive ratio of truthful auctions. Zbl 1122.91322
Goldberg, Andrew V.; Hartline, Jason D.; Karlin, Anna R.; Saks, Michael
1
2004
A limit theorem for sets of stochastic matrices. Zbl 1049.15015
Condon, Anne; Saks, Michael
1
2004
Time-space trade-off lower bounds for randomized computation of decision problems. Zbl 1326.68144
Beame, Paul; Saks, Michael; Sun, Xiaodong; Vee, Erik
13
2003
The Euclidean distortion of complete binary trees. Zbl 1008.05040
Linial, Nathan; Saks, Michael
4
2003
Complexity of some arithmetic problems for binary polynomials. Zbl 1084.68053
Allender, Eric; Bernasconi, Anna; Damm, Carsten; von zur Gathen, Joachim; Saks, Michael; Shparlinski, Igor
1
2003
The efficiency of resolution and Davis-Putnam procedures. Zbl 1004.03048
Beame, Paul; Karp, Richard; Pitassi, Toniann; Saks, Michael
23
2002
Space lower bounds for distance approximation in the data stream model. Zbl 1192.68331
Saks, Michael; Sun, Xiaodong
9
2002
Kleitman and combinatorics. Zbl 1008.05148
Saks, Michael
3
2002
Lower bounds for leader election and collective coin-flipping in the perfect information model. Zbl 1008.68053
Russell, Alexander; Saks, Michael; Zuckerman, David
2
2002
Time-space tradeoffs for branching programs. Zbl 1052.68049
Beame, Paul; Jayram, T. S.; Saks, Michael
16
2001
A lower bound for primality. Zbl 1032.11058
Allender, Eric; Saks, Michael; Shparlinski, Igor
4
2001
Wait-free \(k\)-set agreement is impossible: The topology of public knowledge. Zbl 0952.68159
Saks, Michael; Zaharoglou, Fotios
44
2000
A correction: Orthogonal representations and connectivity of graphs. Zbl 0954.05032
Lovász, L.; Saks, M.; Schrijver, A.
18
2000
A decomposition theorem for task systems and bounds for randomized server problems. Zbl 0977.68039
Blum, Avrim; Karloff, Howard; Rabani, Yuval; Saks, Michael
8
2000
Low discrepancy sets yield approximate min-wise independent permutation families. Zbl 1339.68196
Saks, Michael; Srinivasan, Aravind; Zhou, Shiyu; Zuckerman, David
5
2000
Exponential lower bounds for depth three Boolean circuits. Zbl 0963.68147
Paturi, Ramamohan; Saks, Michael E.; Zane, Francis
4
2000
Products and help bits in decision trees. Zbl 0918.68026
Nisan, Noam; Rudich, Steven; Saks, Michael
10
1999
\(\text{BP}_{\text{H}}\text{SPACE}(S) \subseteq \text{DSPACE}(S^{3/2})\). Zbl 0922.68083
Saks, Michael; Zhou, Shiyu
4
1999
Lower bounds for leader election and collective coin-flipping in the perfect information model. Zbl 1345.68020
Russell, Alexander; Saks, Michael; Zuckerman, David
2
1999
Low discrepancy sets yield approximate min-wise independent permutation families. Zbl 0949.60015
Saks, Michael; Srinivasan, Aravind; Zhou, Shiyu; Zuckerman, David
2
1999
Exponential lower bounds for depth 3 Boolean circuits. Zbl 0962.68129
Paturi, Ramamohan; Saks, Michael E.; Zane, Francis
1
1999
On the complexity of unsatisfiability proofs for random \(k\)-CNF formulas. Zbl 1028.68067
Beame, Paul; Karp, Richard; Pitassi, Toniann; Saks, Michael
11
1998
Trees and Euclidean metrics. Zbl 1029.68952
Linial, Nathan; Magen, Avner; Saks, Michael E.
2
1998
Explicit OR-dispersers with polylogarithmic degree. Zbl 0902.68081
Saks, Michael; Srinivasan, Aravind; Zhou, Shiyu
2
1998
Low distortion Euclidean embeddings of trees. Zbl 0938.46017
Linial, Nathan; Magen, Avner; Saks, Michael E.
1
1998
Efficient construction of a small hitting set for combinatorial rectangles in high dimension. Zbl 0886.68076
Linial, N.; Luby, M.; Saks, M.; Zuckerman, D.
9
1997
Size-depth tradeoffs for threshold circuits. Zbl 0870.68069
Impagliazzo, Russell; Paturi, Ramamohan; Saks, Michael E.
7
1997
Local management of a global resource in a communication network. Zbl 0882.68005
Afek, Yehuda; Awerbuch, Baruch; Plotkin, Serge; Saks, Michael
9
1996
Randomized robot navigation algorithms. Zbl 0960.68593
Berman, Piotr; Blum, Avrim; Fiat, Amos; Karloff, Howard; Rosén, Adi; Saks, Michael
7
1996
Witness sets for families of binary vectors. Zbl 0840.68103
Kushilevitz, Eyal; Linial, Nathan; Rabinovich, Yuri; Saks, Michael
4
1996
On the bandwidth of triangulated triangles. Zbl 0823.05048
Hochberg, Robert; McDiarmid, Colin; Saks, Michael
10
1995
\(RSPACE(S)\subseteq DSPACE(S^{3/2})\). Zbl 0938.68706
Saks, Michael; Zhou, Shiyu
3
1995
Explicit dispersers with polylog degree. Zbl 0978.68555
Saks, Michael; Srinivasan, Aravind; Zhou, Shiyu
3
1995
A complexity index for satisfiability problems. Zbl 0793.90038
Boros, E.; Crama, Y.; Hammer, P. L.; Saks, M.
19
1994
Approximating threshold circuits by rational functions. Zbl 0820.68054
Paturi, Ramamohan; Saks, Michael E.
9
1994
Low diameter graph decompositions. Zbl 0790.05067
Linial, Nathan; Saks, Michael
31
1993
Slicing the hypercube. Zbl 0790.05062
Saks, Michael E.
21
1993
Combinatorial characterization of read-once formulae. Zbl 0781.06012
Karchmer, M.; Linial, N.; Newman, I.; Saks, M.; Wigderson, A.
21
1993
Wait-free \(k\)-set agreement is impossible, the topology of public knowledge. Zbl 1310.68041
Saks, Michael; Zaharoglou, Fotios
17
1993
Communication complexity and combinatorial lattice theory. Zbl 0791.68083
Lovász, László; Saks, Michael
17
1993
Correlation inequalities and a conjecture for permanents. Zbl 0782.60020
Rinott, Yosef; Saks, Michael
8
1993
Efficient construction of a small hitting set for combinatorial rectangles in high dimension. Zbl 1310.68207
Linial, Nati; Luby, Michael; Saks, Michael; Zuckerman, David
2
1993
Size-depth trade-offs for threshold circuits. Zbl 1310.94243
Impagliazzo, Russell; Paturi, Ramamohan; Saks, Michael E.
1
1993
An optimal on-line algorithm for metrical task system. Zbl 0799.68035
Borodin, Allan; Linial, Nathan; Saks, Michael E.
40
1992
A decomposition theorem and bounds for randomized server problems. Zbl 0977.68543
Blum, Avrim; Karloff, Howard; Rabani, Yuval; Saks, Michael
8
1992
Sharpening the LYM inequality. Zbl 0769.05088
Erdös, Péter L.; Frankl, P.; Kleitman, D. J.; Saks, M. E.; Székely, László A.
4
1992
On FKG-type and permanental inequalities. Zbl 1400.60035
Rinott, Yosef; Saks, Michael
2
1992
On computing majority by comparisons. Zbl 0739.05006
Saks, Michael E.; Werman, Michael
29
1991
Optimal time randomized consensus - Making resilient algorithms fast in practice. Zbl 0800.68463
Saks, Michael; Shavit, Nir; Woll, Heather
12
1991
Decomposing graphs into regions of small diameter. Zbl 0785.05073
Linial, Nathan; Saks, Michael
7
1991
Optimal space distributed move-to-front lists. Zbl 1314.68145
Saks, Michael; Zaharoglou, Fotios
1
1991
An on-line graph coloring algorithm with sublinear performance ratio. Zbl 0679.05031
Lovász, László; Saks, Michael; Trotter, W. T.
39
1989
Orthogonal representations and connectivity of graphs. Zbl 0681.05048
Lovász, László; Saks, M.; Schrijver, A.
32
1989
On the cover time of random walks on graphs. Zbl 0681.60064
Kahn, Jeff D.; Linial, Nathan; Nisan, Noam; Saks, Michael E.
28
1989
A dynamic location problem for graphs. Zbl 0692.05055
Chung, F. R. K.; Graham, R. L.; Saks, M. E.
23
1989
The periodic balanced sorting network. Zbl 0698.68042
Dowd, Martin; Perl, Yehoshua; Rudolph, Larry; Saks, Michael
14
1989
Some extremal problems arising from discrete control processes. Zbl 0699.90110
Lichtenstein, D.; Linial, N.; Saks, M.
6
1989
A robust noncryptographic protocol for collective coin flipping. Zbl 0671.90109
Saks, Michael
6
1989
Collective coin flipping and other models of imperfect randomness. Zbl 0675.90107
Ben Or, M.; Linial, N.; Saks, M.
17
1988
Combinatorial representation and convex dimension of convex geometries. Zbl 0659.06005
Edelman, Paul H.; Saks, Michael E.
17
1988
A limit theorem for \((\min,+)\) matrix multiplication. Zbl 0663.05012
Saks, Michael E.
2
1988
An intersection problem for finite automata. Zbl 0668.68066
Saks, Michael; Statman, Rick
1
1988
Every finite distributive lattice is a set of stable matchings for a small stable marriage instance. Zbl 0616.06009
Gusfield, Dan; Irving, Robert; Leather, Paul; Saks, Michael
29
1987
Dynamic search in graphs. Zbl 0643.68083
Chung, F. R. K.; Graham, R. L.; Saks, M. E.
14
1987
The smallest n-uniform hypergraph with positive discrepancy. Zbl 0629.05053
Alon, N.; Kleitman, D. J.; Pomerance, C.; Saks, M.; Seymour, P.
6
1987
Subgraphs of large connectivity and chromatic number in graphs of large chromatic number. Zbl 0647.05022
Alon, N.; Kleitman, D.; Thomassen, C.; Saks, M.; Seymour, P.
3
1987
On the widths of finite distributive lattices. Zbl 0616.06010
Kahn, Jeff; Saks, Michael
2
1987
...and 17 more Documents
all top 5

Cited by 1,538 Authors

22 Saks, Michael E.
19 Rajsbaum, Sergio
16 Raynal, Michel
13 Linial, Nathan
11 Alon, Noga M.
11 Gafni, Eli M.
11 Herlihy, Maurice P.
8 Boros, Endre
8 Makino, Kazuhisa
8 Naor, Assaf
8 Zuckerman, David
7 Castañeda, Armando
7 Cicalese, Ferdinando
7 Fauconnier, Hugues
7 Gurvich, Vladimir A.
7 Lee, James R.
7 O’Donnell, Ryan
7 Travers, Corentin
6 Delporte-Gallet, Carole
6 Fraigniaud, Pierre
6 Hartman, Irith Ben-Arroyo
6 Rubinfeld, Ronitt
6 Sudakov, Benny
5 Ambainis, Andris
5 Balogh, József
5 Bandelt, Hans-Jürgen
5 Bartal, Yair
5 Braverman, Mark
5 Brightwell, Graham R.
5 Gerbner, Dániel
5 Guerraoui, Rachid
5 Hirsch, Edward A.
5 Impagliazzo, Russell
5 Iwama, Kazuo
5 Karlin, Anna R.
5 Keszegh, Balázs
5 Klavžar, Sandi
5 Korman, Amos
5 Koucký, Michal
5 Krauthgamer, Robert
5 Kuznetsov, Petr
5 Lovász, László
5 Matoušek, Jiří
5 Nisan, Noam
5 Pálvölgyi, Dömötör
5 Paturi, Ramamohan
5 Raskhodnikova, Sofya
5 Roughgarden, Tim
5 Servedio, Rocco A.
5 Sherstov, Alexander A.
5 Srinivasan, Aravind
5 Tamaki, Suguru
5 Wiener, Gábor
4 Albers, Susanne
4 Attiya, Hagit
4 Benedetti, Bruno
4 Bertsimas, Dimitris John
4 Borodin, Allan B.
4 Brešar, Boštjan
4 Broder, Andrei Z.
4 Elkin, Michael
4 Epstein, Leah
4 Feige, Uriel
4 Fiat, Amos
4 Gao, Suixiang
4 Halldórsson, Magnús Mar
4 Harper, Lawrence H.
4 Hogben, Leslie
4 Irving, Robert W.
4 Keller, Nathan
4 Khatami, Leila
4 Koutsoupias, Elias
4 Laber, Eduardo Sany
4 Liu, Yanpei
4 Manlove, David F.
4 Melnikov, Alexander G.
4 Mostefaoui, Achour
4 Motwani, Rajeev
4 Narayan, Sivaram K.
4 Papadimitriou, Christos Harilaos
4 Patkós, Balázs
4 Pelc, Andrzej
4 Proctor, Robert A.
4 Sauerhoff, Martin
4 Shaltiel, Ronen
4 Sun, Xiaoming
4 Takimoto, Eiji
4 Talebanfard, Navid
4 Tardos, Gábor
4 Taubenfeld, Gadi
4 van der Holst, Hein
4 Vizer, Máté
4 Yukna, Stasys P.
3 Adiprasito, Karim Alexander
3 Afek, Yehuda
3 Allender, Eric W.
3 Alonso, Laurent
3 Amano, Kazuyuki
3 Anthony, Martin H. G.
3 Arora, Sanjeev
...and 1,438 more Authors
all top 5

Cited in 143 Serials

125 Theoretical Computer Science
72 Discrete Applied Mathematics
60 Discrete Mathematics
44 Information Processing Letters
41 Journal of Computer and System Sciences
41 Algorithmica
40 Distributed Computing
34 Combinatorica
30 SIAM Journal on Computing
25 Information and Computation
20 Journal of Combinatorial Theory. Series A
17 Order
17 Computational Complexity
16 European Journal of Combinatorics
16 Linear Algebra and its Applications
16 Theory of Computing Systems
14 Random Structures & Algorithms
13 Journal of Combinatorial Theory. Series B
9 Games and Economic Behavior
9 Combinatorics, Probability and Computing
8 Artificial Intelligence
8 SIAM Journal on Algebraic and Discrete Methods
8 Discrete & Computational Geometry
8 SIAM Journal on Discrete Mathematics
7 Israel Journal of Mathematics
7 Journal of Economic Theory
6 Linear and Multilinear Algebra
6 Journal of Graph Theory
6 European Journal of Operational Research
5 Networks
5 Advances in Applied Mathematics
5 Journal of Theoretical Probability
5 Journal of Algebraic Combinatorics
5 Annals of Mathematics and Artificial Intelligence
5 Journal of Discrete Algorithms
4 Computers & Mathematics with Applications
4 Advances in Mathematics
4 Operations Research Letters
4 Mathematical Programming. Series A. Series B
4 Journal of Combinatorial Optimization
3 Mathematics of Operations Research
3 Graphs and Combinatorics
3 Journal of Cryptology
3 Annals of Operations Research
3 Computational Geometry
3 International Journal of Computer Mathematics
3 The Electronic Journal of Combinatorics
3 Annals of Mathematics. Second Series
3 Computer Science Review
2 Journal of Mathematical Analysis and Applications
2 The Annals of Probability
2 Information Sciences
2 Inventiones Mathematicae
2 Proceedings of the American Mathematical Society
2 Topology and its Applications
2 Mathematical Social Sciences
2 Statistics & Probability Letters
2 Annals of Pure and Applied Logic
2 Probability Theory and Related Fields
2 Applied Mathematics Letters
2 The Annals of Applied Probability
2 International Journal of Foundations of Computer Science
2 Designs, Codes and Cryptography
2 Journal of Mathematical Sciences (New York)
2 The Bulletin of Symbolic Logic
2 Discussiones Mathematicae. Graph Theory
2 Chicago Journal of Theoretical Computer Science
2 Annals of Combinatorics
2 International Game Theory Review
2 Journal of the Australian Mathematical Society
2 Comptes Rendus. Mathématique. Académie des Sciences, Paris
2 Discrete Optimization
2 Mathematics in Computer Science
2 Journal of Physics A: Mathematical and Theoretical
2 Discrete Mathematics, Algorithms and Applications
2 RAIRO. Theoretical Informatics and Applications
2 ACM Transactions on Computation Theory
2 Journal of Applied and Computational Topology
1 Communications in Mathematical Physics
1 Mathematical Notes
1 Russian Mathematical Surveys
1 The Mathematical Intelligencer
1 Abhandlungen aus dem Mathematischen Seminar der Universität Hamburg
1 Geometriae Dedicata
1 Glasgow Mathematical Journal
1 International Journal of Mathematics and Mathematical Sciences
1 Journal of Algebra
1 Journal of Functional Analysis
1 Journal of the London Mathematical Society. Second Series
1 Journal of Multivariate Analysis
1 Journal of Number Theory
1 Journal of Pure and Applied Algebra
1 Journal of Statistical Planning and Inference
1 Operations Research
1 Transactions of the American Mathematical Society
1 Acta Mathematicae Applicatae Sinica. English Series
1 Optimization
1 Journal of Complexity
1 Journal of Computer Science and Technology
1 Computers & Operations Research
...and 43 more Serials
all top 5

Cited in 42 Fields

594 Computer science (68-XX)
361 Combinatorics (05-XX)
99 Order, lattices, ordered algebraic structures (06-XX)
88 Operations research, mathematical programming (90-XX)
74 Game theory, economics, finance, and other social and behavioral sciences (91-XX)
66 Information and communication theory, circuits (94-XX)
42 Probability theory and stochastic processes (60-XX)
30 Mathematical logic and foundations (03-XX)
28 Linear and multilinear algebra; matrix theory (15-XX)
26 Convex and discrete geometry (52-XX)
15 Functional analysis (46-XX)
14 Group theory and generalizations (20-XX)
13 Quantum theory (81-XX)
9 Algebraic topology (55-XX)
8 Number theory (11-XX)
7 Manifolds and cell complexes (57-XX)
6 Statistical mechanics, structure of matter (82-XX)
5 Algebraic geometry (14-XX)
5 Statistics (62-XX)
4 Real functions (26-XX)
4 Geometry (51-XX)
4 General topology (54-XX)
4 Biology and other natural sciences (92-XX)
3 Commutative algebra (13-XX)
3 Functions of a complex variable (30-XX)
3 Dynamical systems and ergodic theory (37-XX)
3 Harmonic analysis on Euclidean spaces (42-XX)
3 Numerical analysis (65-XX)
3 Systems theory; control (93-XX)
2 History and biography (01-XX)
2 General algebraic systems (08-XX)
2 Partial differential equations (35-XX)
2 Operator theory (47-XX)
2 Differential geometry (53-XX)
1 General and overarching topics; collections (00-XX)
1 Field theory and polynomials (12-XX)
1 Measure and integration (28-XX)
1 Special functions (33-XX)
1 Approximations and expansions (41-XX)
1 Calculus of variations and optimal control; optimization (49-XX)
1 Mechanics of particles and systems (70-XX)
1 Mathematics education (97-XX)

Citations by Year