☰

Michael E. Saks - Publications

Affiliations: 
Rutgers University, New Brunswick, New Brunswick, NJ, United States 
Area:
Mathematics
Tree Info Similar researchers PubMed Report error

50 high-probability publications. We are testing a new system for linking publications to authors. You can help! If you notice any inaccuracies, please sign in and mark papers as correct or incorrect matches. If you identify any major omissions or other inaccuracies in the publication list, please let us know.

Year Citation  Score
2020 Chiarelli J, Hatami P, Saks ME. An Asymptotically Tight Bound on the Number of Relevant Variables in a Bounded Degree Boolean function Combinatorica. 40: 237-244. DOI: 10.1007/S00493-019-4136-7  0.322
2019 Babka M, Bulánek J, Cunát V, Koucký M, Saks ME. On Online Labeling with Large Label Set Siam Journal On Discrete Mathematics. 33: 1175-1193. DOI: 10.1137/17M1117458  0.345
2011 Kahn J, Saks M, Smyth C. The dual bkr inequality and rudich's conjecture Combinatorics, Probability & Computing. 20: 257-266. DOI: 10.1017/S0963548310000465  0.332
2011 Divakaran S, Saks M. An online algorithm for a problem in scheduling with set-ups and release times Algorithmica (New York). 60: 301-315. DOI: 10.1007/S00453-009-9337-9  0.622
2010 Goyal N, Saks ME. Rounds vs. Queries Tradeoff in Noisy Computation Theory of Computing. 6: 113-134. DOI: 10.4086/Toc.2010.V006A006  0.527
2009 Balogh J, Bollobás B, Saks M, Sós VT. The unlabelled speed of a hereditary graph property Journal of Combinatorial Theory, Series B. 99: 9-19. DOI: 10.1016/J.Jctb.2008.03.004  0.406
2008 Allender E, Hellerstein L, Mccabe P, Pitassi T, Saks M. Minimizing disjunctive normal form formulas and AC0 circuits given a truth table Siam Journal On Computing. 38: 63-84. DOI: 10.1137/060664537  0.391
2008 Goyal N, Kindler G, Saks M. Lower Bounds for the Noisy Broadcast Problem Siam Journal On Computing. 37: 1806-1841. DOI: 10.1137/060654864  0.58
2008 Divakaran S, Saks M. Approximation algorithms for problems in scheduling with set-ups Discrete Applied Mathematics. 156: 719-729. DOI: 10.1016/J.Dam.2007.08.010  0.63
2006 Linial N, Saks ME, Statter D. The Non-Crossing Graph Electronic Journal of Combinatorics. 13: 2. DOI: 10.37236/1140  0.402
2005 Paturi R, Pudlák P, Saks ME, Zane F. An improved exponential-time algorithm for k-SAT Journal of the Acm. 52: 337-364. DOI: 10.1145/1066100.1066101  0.423
2004 Condon A, Saks M. A limit theorem for sets of stochastic matrices Linear Algebra and Its Applications. 381: 61-76. DOI: 10.1016/J.Laa.2003.09.020  0.343
2004 Barnum H, Saks M. A lower bound on the quantum query complexity of read-once functions Journal of Computer and System Sciences. 69: 244-258. DOI: 10.1016/J.Jcss.2004.02.002  0.359
2004 Saks M, Samorodnitsky A, Zosin L. A Lower Bound On The Integrality Gap For Minimum Multicut In Directed Networks Combinatorica. 24: 525-530. DOI: 10.1007/S00493-004-0031-X  0.359
2004 Allender E, Bernasconi A, Damm C, Gathen JvZ, Saks M, Shparlinski I. Complexity of some arithmetic problems for binary polynomials Computational Complexity. 12: 23-47. DOI: 10.1007/S00037-003-0176-9  0.375
2003 Beame P, Saks M, Sun X, Vee E. Time-space trade-off lower bounds for randomized computation of decision problems Journal of the Acm. 50: 154-195. DOI: 10.1145/636865.636867  0.432
2002 Beame P, Karp R, Pitassi T, Saks M. The efficiency of resolution and Davis-Putnam procedures Siam Journal On Computing. 31: 1048-1075. DOI: 10.1137/S0097539700369156  0.45
2002 Linial N, Saks ME. The Euclidean Distortion of Complete Binary Trees Discrete and Computational Geometry. 29: 19-21. DOI: 10.1007/S00454-002-2827-Z  0.379
2001 Beame P, Jayram TS, Saks M. Time-Space Tradeoffs for Branching Programs Journal of Computer and System Sciences. 63: 542-572. DOI: 10.1006/Jcss.2001.1778  0.343
2000 Blum A, Karloff H, Rabani Y, Saks M. A Decomposition Theorem for Task Systems and Bounds for Randomized Server Problems Siam Journal On Computing. 30: 1624-1661. DOI: 10.1137/S0097539799351882  0.36
2000 Saks M, Zaharoglou F. Wait-Free k -Set Agreement is Impossible: The Topology of Public Knowledge Siam Journal On Computing. 29: 1449-1483. DOI: 10.1137/S0097539796307698  0.383
2000 Lovász L, Saks M, Schrijver A. A correction: orthogonal representations and connectivity of graphs Linear Algebra and Its Applications. 313: 101-105. DOI: 10.1016/S0024-3795(00)00091-4  0.317
2000 Saks M, Srinivasan A, Zhou S, Zuckerman D. Low discrepancy sets yield approximate min-wise independent permutation families Information Processing Letters. 73: 29-32. DOI: 10.1016/S0020-0190(99)00163-5  0.375
2000 Paturi R, Saks ME, Zane F. Exponential lower bounds for depth three Boolean circuits Computational Complexity. 9: 1-15. DOI: 10.1007/Pl00001598  0.387
1999 Nisan N, Rudich S, Saks M. Products and Help Bits in Decision Trees Siam Journal On Computing. 28: 1035-1050. DOI: 10.1137/S0097539795282444  0.361
1999 Saks M, Zaharoglou F. Optimal Space Distributed Order-Preserving Lists Journal of Algorithms. 31: 320-334. DOI: 10.1006/Jagm.1998.1000  0.315
1998 Saks M, Srinivasan A, Zhou S. Explicit OR-dispersers with polylogarithmic degree Journal of the Acm (Jacm). 45: 123-154. DOI: 10.1145/273865.273915  0.398
1998 Linial N, Magen A, Saks ME. Low distortion euclidean embeddings of trees Israel Journal of Mathematics. 106: 339-348. DOI: 10.1007/Bf02773475  0.322
1997 Impagliazzo R, Paturi R, Saks ME. Size-depth tradeoffs for threshold circuits Siam Journal On Computing. 26: 693-707. DOI: 10.1137/S0097539792282965  0.38
1993 Brickell E, Saks M. The number of distinct subset sums of a finite set of vectors Journal of Combinatorial Theory, Series A. 63: 234-256. DOI: 10.1016/0097-3165(93)90059-H  0.415
1993 Karchmer M, Linial N, Newman I, Saks M, Wigderson A. Combinatorial characterization of read-once formulae Discrete Mathematics. 114: 275-282. DOI: 10.1016/0012-365X(93)90372-Z  0.311
1993 Linial N, Saks ME. Low diameter graph decompositions Combinatorica. 13: 441-454. DOI: 10.1007/Bf01303516  0.418
1992 Borodin A, Linial N, Saks ME. An optimal on-line algorithm for metrical task system Journal of the Acm. 39: 745-763. DOI: 10.1145/146585.146588  0.307
1992 Erdos PL, Frankl P, Kleitman DJ, Saks ME, Székely LA. Sharpening the LYM inequality Combinatorica. 12: 287-293. DOI: 10.1007/Bf01285817  0.527
1991 Saks ME, Werman M. On computing majority by comparisons Combinatorica. 11: 383-387. DOI: 10.1007/Bf01275672  0.376
1989 Dowd M, Perl Y, Rudolph L, Saks M. The Periodic Balanced Sorting Network Journal of the Acm (Jacm). 36: 738-757. DOI: 10.1145/76359.76362  0.304
1989 Saks M. A robust noncrytographic protocol for collective coin flipping Siam Journal On Discrete Mathematics. 2: 240-244. DOI: 10.1137/0402020  0.345
1989 Lovász L, Saks M, Schrijver A. Orthogonal representations and connectivity of graphs Linear Algebra and Its Applications. 114: 439-454. DOI: 10.1016/0024-3795(89)90475-8  0.373
1989 Lovsz L, Saks M, Trotter WT. An on-line graph coloring algorithm with sublinear performance ratio Discrete Mathematics. 75: 319-325. DOI: 10.1016/0012-365X(89)90096-4  0.364
1989 Lichtenstein D, Linial N, Saks ME. Some extremal problems arising from discrete control processes Combinatorica. 9: 269-287. DOI: 10.1007/Bf02125896  0.369
1989 Chung FRK, Graham RL, Saks ME. A Dynamic location problem for graphs Combinatorica. 9: 111-131. DOI: 10.1007/Bf02124674  0.347
1989 Kahn JD, Linial N, Nisan N, Saks ME. On the cover time of random walks on graphs Journal of Theoretical Probability. 2: 121-128. DOI: 10.1007/Bf01048274  0.391
1988 Saks M, Statman R. An intersection problem for finite automata Discrete Applied Mathematics. 21: 245-255. DOI: 10.1016/0166-218X(88)90070-4  0.345
1988 Edelman PH, Saks ME. Combinatorial representation and convex dimension of convex geometries Order. 5: 23-32. DOI: 10.1007/Bf00143895  0.333
1986 Erdös P, Saks M, Sós VT. Maximum induced trees in graphs Journal of Combinatorial Theory, Series B. 41: 61-79. DOI: 10.1016/0095-8956(86)90028-6  0.41
1986 Saks M. Some sequences associated with combinatoral structures Discrete Mathematics. 59: 135-166. DOI: 10.1016/0012-365X(86)90077-4  0.387
1985 Linial N, Saks ME. Every poset has a central element Journal of Combinatorial Theory, Series A. 40: 195-210. DOI: 10.1016/0097-3165(85)90087-1  0.336
1984 Kahn J, Saks ME, Sturtevant D. A topological approach to evasiveness Combinatorica. 4: 297-306. DOI: 10.1007/Bf02579140  0.341
1984 Kahn J, Saks M. Balancing poset extensions Order. 1: 113-126. DOI: 10.1007/Bf00565647  0.3
1983 Linial N, Saks ME, Sós VT. LARGEST DIGRAPHS CONTAINED IN ALL n-TOURNAMENTS Combinatorica. 3: 101-104. DOI: 10.1007/Bf02579345  0.349
Show low-probability matches.