Stop the war!Остановите войну!
for scientists:
default search action
Google
Google Scholar
Semantic Scholar
Internet Archive Scholar
CiteSeerX
ORCIDMichael E. Saks
Person information
- affiliation: Rutgers University, Department of Mathematics
- award (2004): Gödel Prize
Refine list
refinements active!
zoomed in on ?? of ?? records
view refined list in
export refined list as
showing all ?? records
Journal Articles
- 2020
[j85]John Chiarelli, Pooya Hatami, Michael E. Saks:
An Asymptotically Tight Bound on the Number of Relevant Variables in a Bounded Degree Boolean function. Comb. 40(2): 237-244 (2020)- [j84]Diptarka Chakraborty
, Debarati Das, Elazar Goldenberg, Michal Koucký, Michael E. Saks:
Approximating Edit Distance Within Constant Factor in Truly Sub-quadratic Time. J. ACM 67(6): 36:1-36:22 (2020) - [j83]Cole Franks, Michael E. Saks:
On the discrepancy of random matrices with many columns. Random Struct. Algorithms 57(1): 64-96 (2020) - 2019
- [j82]Martin Babka, Jan Bulánek, Vladimír Cunát, Michal Koucký, Michael E. Saks:
On Online Labeling with Large Label Set. SIAM J. Discret. Math. 33(3): 1175-1193 (2019) - 2017
- [j81]Michael E. Saks, C. Seshadhri:
Estimating the Longest Increasing Sequence in Polylogarithmic Time. SIAM J. Comput. 46(2): 774-823 (2017) - [j80]Justin Gilmer, Michal Koucký, Michael E. Saks:
A Communication Game Related to the Sensitivity Conjecture. Theory Comput. 13(1): 1-18 (2017) - 2016
- [j79]Justin Gilmer, Michael E. Saks, Srikanth Srinivasan:
Composition limits and separating examples for some boolean function complexity measures. Comb. 36(3): 265-311 (2016) - [j78]Troy Lee, Nikos Leonardos, Michael E. Saks, Fengming Wang:
Hellinger volume and number-on-the-forehead communication complexity. J. Comput. Syst. Sci. 82(6): 1064-1074 (2016) - [j77]Swastik Kopparty, Mrinal Kumar, Michael E. Saks:
Efficient Indexing of Necklaces and Irreducible Polynomials over Finite Fields. Theory Comput. 12(1): 1-27 (2016) - 2015
- [j76]Michael E. Saks:
Special issue "Conference on Computational Complexity 2014" Guest Editor's Foreword. Comput. Complex. 24(2): 197-199 (2015) - [j75]Dmitry Gavinsky, Shachar Lovett, Michael E. Saks, Srikanth Srinivasan:
A tail bound for read-k families of functions. Random Struct. Algorithms 47(1): 99-108 (2015) - [j74]Jan Bulánek, Michal Koucký, Michael E. Saks:
Tight Lower Bounds for the Online Labeling Problem. SIAM J. Comput. 44(6): 1765-1797 (2015) - 2011
- [j73]Srikrishnan Divakaran, Michael E. Saks:
An Online Algorithm for a Problem in Scheduling with Set-ups and Release Times. Algorithmica 60(2): 301-315 (2011) - [j72]Jeff Kahn, Michael E. Saks, Clifford D. Smyth:
The Dual BKR Inequality and Rudich's Conjecture. Comb. Probab. Comput. 20(2): 257-266 (2011) - 2010
- [j71]Nikos Leonardos, Michael E. Saks:
Lower Bounds on the Randomized Communication Complexity of Read-Once Functions. Comput. Complex. 19(2): 153-181 (2010) - [j70]Michael E. Saks, C. Seshadhri:
Local Monotonicity Reconstruction. SIAM J. Comput. 39(7): 2897-2926 (2010) - [j69]Navin Goyal, Michael E. Saks:
Rounds vs. Queries Tradeoff in Noisy Computation. Theory Comput. 6(1): 113-134 (2010) - 2009
- [j68]József Balogh, Béla Bollobás, Michael E. Saks, Vera T. Sós:
The unlabelled speed of a hereditary graph property. J. Comb. Theory, Ser. B 99(1): 9-19 (2009) - 2008
- [j67]Srikrishnan Divakaran, Michael E. Saks:
Approximation algorithms for problems in scheduling with set-ups. Discret. Appl. Math. 156(5): 719-729 (2008) - [j66]Navin Goyal, Guy Kindler, Michael E. Saks:
Lower Bounds for the Noisy Broadcast Problem. SIAM J. Comput. 37(6): 1806-1841 (2008) - [j65]Eric Allender, Lisa Hellerstein, Paul McCabe, Toniann Pitassi, Michael E. Saks:
Minimizing Disjunctive Normal Form Formulas and AC0 Circuits Given a Truth Table. SIAM J. Comput. 38(1): 63-84 (2008) - 2007
- [j64]Zdenek Dvorák, Vít Jelínek, Daniel Král, Jan Kyncl, Michael E. Saks:
Probabilistic strategies for the partition and plurality problems. Random Struct. Algorithms 30(1-2): 63-77 (2007) - 2006
- [j63]Nathan Linial, Michael E. Saks, David Statter:
The Non-Crossing Graph. Electron. J. Comb. 13(1) (2006) - [j62]Andrew V. Goldberg, Jason D. Hartline, Anna R. Karlin, Michael E. Saks, Andrew Wright:
Competitive auctions. Games Econ. Behav. 55(2): 242-269 (2006) - [j61]László Lovász, Michael E. Saks:
A localization inequality for set functions. J. Comb. Theory, Ser. A 113(4): 726-735 (2006) - 2005
- [j60]Ramamohan Paturi, Pavel Pudlák, Michael E. Saks, Francis Zane:
An improved exponential-time algorithm for k-SAT. J. ACM 52(3): 337-364 (2005) - [j59]Navin Goyal, Michael E. Saks:
A parallel search game. Random Struct. Algorithms 27(2): 227-234 (2005) - 2004
- [j58]Peter Keevash, Michael E. Saks, Benny Sudakov, Jacques Verstraëte:
Multicolour Turán problems. Adv. Appl. Math. 33(2): 238-262 (2004) - [j57]Michael E. Saks, Alex Samorodnitsky, Leonid Zosin:
A Lower Bound On The Integrality Gap For Minimum Multicut In Directed Networks. Comb. 24(3): 525-530 (2004) - [j56]Howard Barnum, Michael E. Saks:
A lower bound on the quantum query complexity of read-once functions. J. Comput. Syst. Sci. 69(2): 244-258 (2004) - 2003
- [j55]Eric Allender, Anna Bernasconi, Carsten Damm, Joachim von zur Gathen, Michael E. Saks, Igor E. Shparlinski:
Complexity of some arithmetic problems for binary polynomials. Comput. Complex. 12(1-2): 23-47 (2003) - [j54]Nathan Linial, Michael E. Saks:
The Euclidean Distortion of Complete Binary Trees. Discret. Comput. Geom. 29(1): 19-21 (2003) - [j53]Paul Beame, Michael E. Saks, Xiaodong Sun, Erik Vee:
Time-space trade-off lower bounds for randomized computation of decision problems. J. ACM 50(2): 154-195 (2003) - 2002
- [j52]Michael E. Saks:
Kleitman and combinatorics. Discret. Math. 257(2-3): 225-247 (2002) - [j51]Paul Beame, Richard M. Karp, Toniann Pitassi, Michael E. Saks:
The Efficiency of Resolution and Davis--Putnam Procedures. SIAM J. Comput. 31(4): 1048-1075 (2002) - [j50]Alexander Russell, Michael E. Saks, David Zuckerman:
Lower Bounds for Leader Election and Collective Coin-Flipping in the Perfect Information Model. SIAM J. Comput. 31(6): 1645-1662 (2002) - [j49]Eric J. Anderson, Kirsten Hildrum, Anna R. Karlin, April Rasala, Michael E. Saks:
On list update and work function algorithms. Theor. Comput. Sci. 287(2): 393-418 (2002) - 2001
- [j48]Michael E. Saks, Shiyu Zhou:
Sample Spaces with Small Bias on Neighborhoods and Error-Correcting Communication Protocols. Algorithmica 30(3): 418-431 (2001) - [j47]Eric Allender, Michael E. Saks, Igor E. Shparlinski:
A Lower Bound for Primality. J. Comput. Syst. Sci. 62(2): 356-366 (2001) - [j46]Paul Beame, T. S. Jayram, Michael E. Saks:
Time-Space Tradeoffs for Branching Programs. J. Comput. Syst. Sci. 63(4): 542-572 (2001) - 2000
- [j45]Ramamohan Paturi, Michael E. Saks, Francis Zane:
Exponential lower bounds for depth three Boolean circuits. Comput. Complex. 9(1): 1-15 (2000) - [j44]Michael E. Saks, Aravind Srinivasan, Shiyu Zhou, David Zuckerman:
Low discrepancy sets yield approximate min-wise independent permutation families. Inf. Process. Lett. 73(1-2): 29-32 (2000) - [j43]Michael E. Saks, Fotios Zaharoglou:
Wait-Free k-Set Agreement is Impossible: The Topology of Public Knowledge. SIAM J. Comput. 29(5): 1449-1483 (2000) - [j42]Avrim Blum, Howard J. Karloff, Yuval Rabani, Michael E. Saks:
A Decomposition Theorem for Task Systems and Bounds for Randomized Server Problems. SIAM J. Comput. 30(5): 1624-1661 (2000) - 1999
- [j41]Michael E. Saks, Fotios Zaharoglou:
Optimal Space Distributed Order-Preserving Lists. J. Algorithms 31(2): 320-334 (1999) - [j40]Michael E. Saks, Shiyu Zhou:
BP HSpace(S) subseteq DSPACE(S3/2). J. Comput. Syst. Sci. 58(2): 376-403 (1999) - [j39]Noam Nisan, Steven Rudich, Michael E. Saks:
Products and Help Bits in Decision Trees. SIAM J. Comput. 28(3): 1035-1050 (1999) - 1998
- [j38]Michael E. Saks, Aravind Srinivasan, Shiyu Zhou:
Explicit OR-Dispersers with Polylogarithmic Degree. J. ACM 45(1): 123-154 (1998) - 1997
- [j37]Nathan Linial, Michael Luby, Michael E. Saks, David Zuckerman:
Efficient Construction of a Small Hitting Set for Combinatorial Rectangles in High Dimension. Comb. 17(2): 215-234 (1997) - [j36]Russell Impagliazzo, Ramamohan Paturi, Michael E. Saks:
Size-Depth Tradeoffs for Threshold Circuits. SIAM J. Comput. 26(3): 693-707 (1997) - 1996
- [j35]Yehuda Afek, Baruch Awerbuch, Serge A. Plotkin, Michael E. Saks:
Local Management of a Global Resource in a Communication Network. J. ACM 43(1): 1-19 (1996) - [j34]Eyal Kushilevitz, Nathan Linial, Yuri Rabinovich, Michael E. Saks:
Witness Sets for Families of Binary Vectors. J. Comb. Theory, Ser. A 73(2): 376-380 (1996) - 1995
- [j33]Robert Hochberg, Colin McDiarmid, Michael E. Saks:
On the bandwidth of triangulated triangles. Discret. Math. 138(1-3): 261-265 (1995) - 1994
- [j32]Ramamohan Paturi, Michael E. Saks:
Approximating Threshold Circuits by Rational Functions. Inf. Comput. 112(2): 257-272 (1994) - [j31]Mauricio Karchmer, Ilan Newman, Michael E. Saks, Avi Wigderson:
Non-Deterministic Communication Complexity with Few Witnesses. J. Comput. Syst. Sci. 49(2): 247-257 (1994) - [j30]Endre Boros, Yves Crama, Peter L. Hammer, Michael E. Saks:
A Complexity Index for Satisfiability Problems. SIAM J. Comput. 23(1): 45-49 (1994) - 1993
- [j29]Yosef Rinott, Michael E. Saks:
Correlation inequalities and a conjecture for permanents. Comb. 13(3): 269-277 (1993) - [j28]Nathan Linial, Michael E. Saks:
Low diameter graph decompositions. Comb. 13(4): 441-454 (1993) - [j27]Mauricio Karchmer, Nathan Linial, Ilan Newman, Michael E. Saks, Avi Wigderson:
Combinatorial characterization of read-once formulae. Discret. Math. 114(1-3): 275-282 (1993) - [j26]László Lovász, Michael E. Saks:
Communication Complexity and Combinatorial Lattice Theory. J. Comput. Syst. Sci. 47(2): 322-349 (1993) - [j25]Ernest F. Brickell, Michael E. Saks:
The Number of Distinct Subset Sums of a Finite Set of Vectors. J. Comb. Theory, Ser. A 63(2): 234-256 (1993) - 1992
- [j24]Péter L. Erdös, Peter Frankl, Daniel J. Kleitman, Michael E. Saks, László A. Székely:
Sharpening the LYM inequality. Comb. 12(3): 287-293 (1992) - [j23]Allan Borodin, Nathan Linial, Michael E. Saks:
An Optimal On-Line Algorithm for Metrical Task System. J. ACM 39(4): 745-763 (1992) - 1991
- [j22]Michael E. Saks, Michael Werman:
On computing majority by comparisons. Comb. 11(4): 383-387 (1991) - 1989
- [j21]Fan R. K. Chung, Ronald L. Graham, Michael E. Saks:
A dynamic location problem for graphs. Comb. 9(2): 111-131 (1989) - [j20]David Lichtenstein, Nathan Linial, Michael E. Saks:
Some extremal problems arising form discrete control processes. Comb. 9(3): 269-287 (1989) - [j19]László Lovász, Michael E. Saks, William T. Trotter:
An on-line graph coloring algorithm with sublinear performance ratio. Discret. Math. 75(1-3): 319-325 (1989) - [j18]Martin Dowd, Yehoshua Perl, Larry Rudolph, Michael E. Saks:
The periodic balanced sorting network. J. ACM 36(4): 738-757 (1989) - [j17]Michael E. Saks:
A Robust Noncryptographic Protocol for Collective Coin Flipping. SIAM J. Discret. Math. 2(2): 240-244 (1989) - 1988
- [j16]Michael E. Saks, Rick Statman:
An intersection problem for finite automata. Discret. Appl. Math. 21(3): 245-255 (1988) - [j15]Michael E. Saks:
A Limit Theorem for (min, +) Matrix Multiplication. Math. Oper. Res. 13(4): 606-618 (1988) - 1987
- [j14]Noga Alon, Daniel J. Kleitman, Carl Pomerance, Michael E. Saks, Paul D. Seymour:
The smallets n-uniform hypergraph with positive discrepancy. Comb. 7(2): 151-160 (1987) - [j13]Jeff Kahn, Michael E. Saks:
On the widths of finite distributive lattices. Discret. Math. 63(2-3): 183-195 (1987) - [j12]Dan Gusfield, Robert W. Irving, Paul Leather, Michael E. Saks:
Every finite distributive lattice is a set of stable matchings for a small stable marriage instance. J. Comb. Theory, Ser. A 44(2): 304-309 (1987) - [j11]Noga Alon, Daniel J. Kleitman, Carsten Thomassen, Michael E. Saks, Paul D. Seymour:
Subgraphs of large connectivity and chromatic number in graphs of large chromatic number. J. Graph Theory 11(3): 367-371 (1987) - 1986
- [j10]Michael E. Saks:
Some sequences associated with combinatorial structures. Discret. Math. 59(1-2): 135-166 (1986) - [j9]Paul Erdös, Michael E. Saks, Vera T. Sós:
Maximum induced trees in graphs. J. Comb. Theory, Ser. B 41(1): 61-79 (1986) - 1985
- [j8]Nathan Linial, Michael E. Saks:
Searching Ordered Structures. J. Algorithms 6(1): 86-103 (1985) - [j7]Nathan Linial, Michael E. Saks:
Every Poset Has a Central Element. J. Comb. Theory, Ser. A 40(2): 195-210 (1985) - 1984
- [j6]Jeff Kahn, Michael E. Saks:
A polyomino with no stochastic function. Comb. 4(2): 181-182 (1984) - [j5]Jeff Kahn, Michael E. Saks, Dean Sturtevant:
A topological approach to evasiveness. Comb. 4(4): 297-306 (1984) - 1983
- [j4]Nathan Linial, Michael E. Saks, Vera T. Sós:
Largest digraphs contained in all n-tournaments. Comb. 3(1): 101-104 (1983) - 1980
- [j3]Robert A. Proctor, Michael E. Saks, Dean G. Sturtevant:
Product partial orders with the sperner property. Discret. Math. 30(2): 173-180 (1980) - [j2]Michael E. Saks:
Dilworth Numbers, Incidence Maps and Product Partial Orders. SIAM J. Algebraic Discret. Methods 1(2): 211-215 (1980) - 1979
- [j1]Paul H. Edelman, Michael E. Saks:
Group labelings of graphs. J. Graph Theory 3(2): 135-140 (1979)
Conference and Workshop Papers
- 2023
- [c78]Michal Koucký, Michael E. Saks:
Simple, deterministic, fast (but weak) approximations to edit distance and Dyck edit distance. SODA 2023: 5203-5219 - 2022
- [c77]Michael E. Saks, Rahul Santhanam:
On Randomized Reductions to the Random Strings. CCC 2022: 29:1-29:30 - 2020
- [c76]Michael E. Saks, Rahul Santhanam:
Circuit Lower Bounds from NP-Hardness of MCSP Under Turing Reductions. CCC 2020: 26:1-26:13 - [c75]Michal Koucký, Michael E. Saks:
Constant factor approximations to edit distance on far input pairs in nearly linear time. STOC 2020: 699-712 - 2018
- [c74]Michael E. Saks:
Online Labeling: Algorithms, Lower Bounds and Open Questions. CSR 2018: 23-28 - [c73]Diptarka Chakraborty, Debarati Das, Elazar Goldenberg, Michal Koucký, Michael E. Saks:
Approximating Edit Distance within Constant Factor in Truly Sub-Quadratic Time. FOCS 2018: 979-990 - [c72]Debarati Das, Michal Koucký, Michael E. Saks:
Lower Bounds for Combinatorial Algorithms for Boolean Matrix Multiplication. STACS 2018: 23:1-23:14 - 2017
- [c71]Timothy Naumovitz, Michael E. Saks, C. Seshadhri:
Accurate and Nearly Optimal Sublinear Approximations to Ulam Distance. SODA 2017: 2012-2031 - 2016
- [c70]Anindya De, Michael E. Saks, Sijian Tang:
Noisy Population Recovery in Polynomial Time. FOCS 2016: 675-684 - 2015
- [c69]Justin Gilmer, Michal Koucký, Michael E. Saks:
A New Approach to the Sensitivity Conjecture. ITCS 2015: 247-254 - [c68]Timothy Naumovitz, Michael E. Saks:
A polylogarithmic space deterministic streaming algorithm for approximating distance to monotonicity. SODA 2015: 1252-1262 - 2014
- [c67]Arkadev Chattopadhyay, Michael E. Saks:
The Power of Super-logarithmic Number of Players. APPROX-RANDOM 2014: 596-603 - [c66]Swastik Kopparty, Mrinal Kumar, Michael E. Saks:
Efficient Indexing of Necklaces and Irreducible Polynomials over Finite Fields. ICALP (1) 2014: 726-737 - 2013
- [c65]Justin Gilmer, Michael E. Saks, Srikanth Srinivasan:
Composition Limits and Separating Examples for Some Boolean Function Complexity Measures. CCC 2013: 185-196 - [c64]Ankur Moitra, Michael E. Saks:
A Polynomial Time Algorithm for Lossy Population Recovery. FOCS 2013: 110-116 - [c63]Jan Bulánek, Michal Koucký, Michael E. Saks:
On Randomized Online Labeling with Polynomially Many Labels. ICALP (1) 2013: 291-302 - [c62]Michael E. Saks, C. Seshadhri:
Space efficient streaming algorithms for the distance to monotonicity and asymmetric edit distance. SODA 2013: 1698-1709 - [c61]Yonatan Bilu, Amit Daniely, Nati Linial, Michael E. Saks:
On the practically interesting instances of MAXCUT. STACS 2013: 526-537 - 2012
- [c60]Martin Babka, Jan Bulánek, Vladimír Cunát, Michal Koucký, Michael E. Saks:
On Online Labeling with Polynomially Many Labels. ESA 2012: 121-132 - [c59]Jan Bulánek, Michal Koucký, Michael E. Saks:
Tight lower bounds for the online labeling problem. STOC 2012: 1185-1198 - 2010
- [c58]Michael E. Saks, C. Seshadhri:
Estimating the Longest Increasing Sequence in Polylogarithmic Time. FOCS 2010: 458-467 - 2009
- [c57]Nikos Leonardos, Michael E. Saks:
Lower Bounds on the Randomized Communication Complexity of Read-Once Functions. CCC 2009: 341-350 - 2008
- [c56]Michael E. Saks, C. Seshadhri:
Parallel monotonicity reconstruction. SODA 2008: 962-971 - [c55]Moses Charikar, Howard J. Karloff, Claire Mathieu, Joseph Naor, Michael E. Saks:
Online multicast with egalitarian cost sharing. SPAA 2008: 70-76 - 2006
- [c54]Eric Allender, Lisa Hellerstein, Paul McCabe, Toniann Pitassi, Michael E. Saks:
Minimizing DNF Formulas and AC0d Circuits Given a Truth Table. CCC 2006: 237-251 - 2005
- [c53]Ryan O'Donnell, Michael E. Saks, Oded Schramm, Rocco A. Servedio:
Every decision tree has an in.uential variable. FOCS 2005: 31-39 - [c52]Navin Goyal, Guy Kindler, Michael E. Saks:
Lower Bounds for the Noisy Broadcast Problem. FOCS 2005: 40-52 - [c51]Michael E. Saks, Lan Yu:
Weak monotonicity suffices for truthfulness on convex domains. EC 2005: 286-293 - [c50]Navin Goyal, Michael E. Saks:
Rounds vs queries trade-off in noisy computation. SODA 2005: 632-639 - [c49]Zdenek Dvorák, Vít Jelínek, Daniel Král, Jan Kyncl, Michael E. Saks:
Three Optimal Algorithms for Balls of Three Colors. STACS 2005: 206-217 - 2004
- [c48]Andrew V. Goldberg, Jason D. Hartline, Anna R. Karlin, Michael E. Saks:
A Lower Bound on the Competitive Ratio of Truthful Auctions. STACS 2004: 644-655 - 2003
- [c47]Navin Goyal, Michael E. Saks, Srinivasan Venkatesh:
Optimal Separation of EROW and CROWPRAMs. CCC 2003: 93- - [c46]Howard Barnum, Michael E. Saks, Mario Szegedy:
Quantum query complexity and semi-definite programming. CCC 2003: 179-193 - 2002
- [c45]Michael E. Saks, Xiaodong Sun:
Space lower bounds for distance approximation in the data stream model. STOC 2002: 360-369 - 2000
- [c44]Jeff Kahn, Michael E. Saks, Cliff Smyth:
A Dual Version of Reimer's Inequality and a Proof of Rudich's Conjecture. CCC 2000: 98-103 - [c43]Paul Beame, Michael E. Saks, Xiaodong Sun, Erik Vee:
Super-linear time-space tradeoff lower bounds for randomized computation. FOCS 2000: 169-179 - 1999
- [c42]Eric Allender, Michael E. Saks, Igor E. Shparlinski:
A Lower Bound for Primality. CCC 1999: 10-14 - [c41]Eric J. Anderson, Kirsten Hildrum, Anna R. Karlin, April Rasala, Michael E. Saks:
On List Update and Work Function Algorithms. ESA 1999: 289-300 - [c40]Michael E. Saks, Aravind Srinivasan, Shiyu Zhou, David Zuckerman:
Low Discrepancy Sets Yield Approximate Min-Wise Independent Permutation Families. RANDOM-APPROX 1999: 11-15 - [c39]Alexander Russell, Michael E. Saks, David Zuckerman:
Lower Bounds for Leader Election and Collective Coin-Flipping in the Perfect Information Model. STOC 1999: 339-347 - 1998
- [c38]Paul Beame, Michael E. Saks, Jayram S. Thathachar:
Time-Space Tradeoffs for Branching Programs. FOCS 1998: 254-263 - [c37]Ramamohan Paturi, Pavel Pudlák, Michael E. Saks, Francis Zane:
An Improved Exponential-Time Algorithm for k-SAT. FOCS 1998: 628-637 - [c36]Nathan Linial, Avner Magen, Michael E. Saks:
Trees and Euclidean Metrics. STOC 1998: 169-175 - [c35]Paul Beame, Richard M. Karp, Toniann Pitassi, Michael E. Saks:
On the Complexity of Unsatisfiability Proofs for Random k-CNF Formulas. STOC 1998: 561-571 - 1997
- [c34]Michael E. Saks, Shiyu Zhou:
Sample Spaces with Small Bias on Neighborhoods and Error-Correcting Communication Protocols. RANDOM 1997: 95-109 - [c33]Ramamohan Paturi, Michael E. Saks, Francis Zane:
Exponential Lower Bounds for Depth 3 Boolean Circuits. STOC 1997: 86-91 - 1996
- [c32]Michael E. Saks:
Randomization and Derandomization in Space_Bounded Computation. CCC 1996: 128-149 - [c31]Roy Armoni, Michael E. Saks, Avi Wigderson, Shiyu Zhou:
Discrepancy Sets and Pseudorandom Generators for Combinatorial Rectangles. FOCS 1996: 412-421 - [c30]Piotr Berman, Avrim Blum, Amos Fiat, Howard J. Karloff, Adi Rosén, Michael E. Saks:
Randomized Robot Navigation Algorithms. SODA 1996: 75-84 - 1995
- [c29]Michael E. Saks, Shiyu Zhou:
RSPACE(S) \subseteq DSPACE(S3/2). FOCS 1995: 344-353 - [c28]Michael E. Saks, Aravind Srinivasan, Shiyu Zhou:
Explicit dispersers with polylog degree. STOC 1995: 479-488 - 1994
- [c27]Noam Nisan, Steven Rudich, Michael E. Saks:
Products and Help Bits in Decision Trees. FOCS 1994: 318-329 - 1993
- [c26]Nathan Linial, David Peleg, Yuri Rabinovich, Michael E. Saks:
Sphere Packing and Local Majorities in Graphs. ISTCS 1993: 141-149 - [c25]Michael E. Saks, Fotios Zaharoglou:
Wait-free k-set agreement is impossible: the topology of public knowledge. STOC 1993: 101-110 - [c24]Nathan Linial, Michael Luby, Michael E. Saks, David Zuckerman:
Efficient construction of a small hitting set for combinatorial rectangles in high dimension. STOC 1993: 258-267 - [c23]Russell Impagliazzo, Ramamohan Paturi, Michael E. Saks:
Size-depth trade-offs for threshold circuits. STOC 1993: 541-550 - 1992
- [c22]Mauricio Karchmer, Ilan Newman, Michael E. Saks, Avi Wigderson:
Non-deterministic Communication Complexity with Few Witness. SCT 1992: 275-281 - [c21]Avrim Blum, Howard J. Karloff, Yuval Rabani, Michael E. Saks:
A Decomposition Theorem and Bounds for Randomized Server Problems. FOCS 1992: 197-207 - [c20]Endre Boros, Yves Crama, Peter L. Hammer, Michael E. Saks:
A Complexity Index for Satisfiability Problems. IPCO 1992: 220-226 - [c19]Baruch Awerbuch, Boaz Patt-Shamir, David Peleg, Michael E. Saks:
Adapting to Asynchronous Dynamic Networks (Extended Abstract). STOC 1992: 557-570 - 1991
- [c18]Michael E. Saks, Fotios Zaharoglou:
Optimal Space Distributed Move-to-Front Lists. PODC 1991: 65-73 - [c17]Nathan Linial, Michael E. Saks:
Decomposing Graphs into Regions of Small Diameter. SODA 1991: 320-330 - [c16]Michael E. Saks, Nir Shavit, Heather Woll:
Optimal Time Randomized Consensus - Making Resilient Algorithms Fast in Practice. SODA 1991: 351-362 - 1990
- [c15]Ramamohan Paturi, Michael E. Saks:
On Threshold Circuits for Parity (Abstract). COLT 1990: 390 - [c14]Baruch Awerbuch, Michael E. Saks:
A Dining Philosophers Algorithm with Polynomial Response Time. FOCS 1990: 65-74 - [c13]Ramamohan Paturi, Michael E. Saks:
On Threshold Circuits for Parity. FOCS 1990: 397-404 - 1989
- [c12]Michael L. Fredman, Michael E. Saks:
The Cell Probe Complexity of Dynamic Data Structures. STOC 1989: 345-354 - 1988
- [c11]László Lovász, Michael E. Saks:
Lattices, Möbius Functions and Communication Complexity. FOCS 1988: 81-90 - 1987
- [c10]Yehuda Afek, Baruch Awerbuch, Serge A. Plotkin, Michael E. Saks:
Local Management of a Global Resource in a Communication Network. FOCS 1987: 347-357 - [c9]Yehuda Afek, Michael E. Saks:
Detecting Global Termination Conditions in the Face of Uncertainty. PODC 1987: 109-124 - [c8]David Lichtenstein, Nathan Linial, Michael E. Saks:
Imperfect Random Sources and Discrete Controlled Processes. STOC 1987: 169-177 - [c7]Allan Borodin, Nathan Linial, Michael E. Saks:
An Optimal Online Algorithm for Metrical Task Systems. STOC 1987: 373-382 - 1986
- [c6]Richard M. Karp, Michael E. Saks, Avi Wigderson:
On a Search Problem Related to Branch-and-Bound Procedures. FOCS 1986: 19-28 - [c5]Michael E. Saks, Avi Wigderson:
Probabilistic Boolean Decision Trees and the Complexity of Evaluating Game Trees. FOCS 1986: 29-38 - 1984
- [c4]Jeff Kahn, Michael E. Saks:
Every Poset Has a Good Comparison. STOC 1984: 299-301 - 1983
- [c3]Jeff Kahn, Michael E. Saks, Dean Sturtevant:
A Topological Approach to Evasiveness. FOCS 1983: 31-33 - [c2]Nathan Linial, Michael E. Saks:
Information Bounds Are Good for Search Problems on Ordered Data Structures. FOCS 1983: 473-475 - [c1]Martin Dowd, Yehoshua Perl, Michael E. Saks:
The Balanced Sorting Network. PODC 1983: 161-172
Parts in Books or Collections
- 2010
- [p1]Michael E. Saks, C. Seshadhri:
Local Property Reconstruction and Monotonicity. Property Testing 2010: 346-354
Editorship
- 1997
- [e1]Michael E. Saks:
Proceedings of the Eighth Annual ACM-SIAM Symposium on Discrete Algorithms, 5-7 January 1997, New Orleans, Louisiana, USA. ACM/SIAM 1997, ISBN 0-89871-390-0 [contents]
Reference Works
- 2016
- [r2]Ramamohan Paturi, Pavel Pudlák, Michael E. Saks, Francis Zane:
Backtracking Based k-SAT Algorithms. Encyclopedia of Algorithms 2016: 170-174 - 2008
- [r1]Ramamohan Paturi, Pavel Pudlák, Michael E. Saks, Francis Zane:
Backtracking Based k-SAT Algorithms. Encyclopedia of Algorithms 2008
Informal and Other Publications
- 2024
- [i33]Mohit Gurumukhani, Ramamohan Paturi, Pavel Pudlák, Michael E. Saks, Navid Talebanfard:
Local Enumeration and Majority Lower Bounds. CoRR abs/2403.09134 (2024) - 2022
- [i32]Michael E. Saks, Rahul Santhanam:
On Randomized Reductions to the Random Strings. Electron. Colloquium Comput. Complex. TR22 (2022) - 2019
- [i31]Michal Koucký, Michael E. Saks:
Constant factor approximations to edit distance on far input pairs in nearly linear time. CoRR abs/1904.05459 (2019) - 2018
- [i30]Debarati Das, Michal Koucký, Michael E. Saks:
Lower bounds for Combinatorial Algorithms for Boolean Matrix Multiplication. CoRR abs/1801.05202 (2018) - [i29]John Chiarelli, Pooya Hatami, Michael E. Saks:
Tight Bound on the Number of Relevant Variables in a Bounded degree Boolean function. CoRR abs/1801.08564 (2018) - [i28]Diptarka Chakraborty, Debarati Das, Elazar Goldenberg, Michal Koucký, Michael E. Saks:
Approximating Edit Distance Within Constant Factor in Truly Sub-Quadratic Time. CoRR abs/1810.03664 (2018) - 2017
- [i27]Joshua A. Grochow, Mrinal Kumar, Michael E. Saks, Shubhangi Saraf:
Towards an algebraic natural proofs barrier via polynomial identity testing. CoRR abs/1701.01717 (2017) - [i26]Joshua A. Grochow, Mrinal Kumar, Michael E. Saks, Shubhangi Saraf:
Towards an algebraic natural proofs barrier via polynomial identity testing. Electron. Colloquium Comput. Complex. TR17 (2017) - 2016
- [i25]Anindya De, Michael E. Saks, Sijian Tang:
Noisy population recovery in polynomial time. CoRR abs/1602.07616 (2016) - [i24]Anindya De, Michael E. Saks, Sijian Tang:
Noisy population recovery in polynomial time. Electron. Colloquium Comput. Complex. TR16 (2016) - 2015
- [i23]Swastik Kopparty, Mrinal Kumar, Michael E. Saks:
Efficient indexing of necklaces and irreducible polynomials over finite fields. CoRR abs/1504.00572 (2015) - [i22]Justin Gilmer, Michal Koucký, Michael E. Saks:
A communication game related to the sensitivity conjecture. CoRR abs/1511.07729 (2015) - [i21]Swastik Kopparty, Mrinal Kumar, Michael E. Saks:
Efficient indexing of necklaces and irreducible polynomials over finite fields. Electron. Colloquium Comput. Complex. TR15 (2015) - 2014
- [i20]Troy Lee, Nikos Leonardos, Michael E. Saks, Fengming Wang:
Hellinger volume and number-on-the-forehead communication complexity. CoRR abs/1407.5425 (2014) - [i19]Arkadev Chattopadhyay, Michael E. Saks:
The Power of Super-logarithmic Number of Players. Electron. Colloquium Comput. Complex. TR14 (2014) - 2013
- [i18]Ankur Moitra, Michael E. Saks:
A Polynomial Time Algorithm for Lossy Population Recovery. CoRR abs/1302.1515 (2013) - [i17]Justin Gilmer, Michael E. Saks, Srikanth Srinivasan:
Composition limits and separating examples for some Boolean function complexity measures. CoRR abs/1306.0630 (2013) - [i16]Michael E. Saks, C. Seshadhri:
Estimating the longest increasing sequence in polylogarithmic time. CoRR abs/1308.0626 (2013) - 2012
- [i15]Michael E. Saks, C. Seshadhri:
Space efficient streaming algorithms for the distance to monotonicity and asymmetric edit distance. CoRR abs/1204.1098 (2012) - [i14]Dmitry Gavinsky, Shachar Lovett, Michael E. Saks, Srikanth Srinivasan:
A Tail Bound for Read-k Families of Functions. CoRR abs/1205.1478 (2012) - [i13]Amit Daniely, Nati Linial, Michael E. Saks:
Clustering is difficult only when it does not matter. CoRR abs/1205.4891 (2012) - [i12]Yonatan Bilu, Amit Daniely, Nati Linial, Michael E. Saks:
On the practically interesting instances of MAXCUT. CoRR abs/1205.4893 (2012) - [i11]Martin Babka, Jan Bulánek, Vladimír Cunát, Michal Koucký, Michael E. Saks:
On Online Labeling with Polynomially Many Labels. CoRR abs/1210.3197 (2012) - [i10]Dmitry Gavinsky, Shachar Lovett, Michael E. Saks, Srikanth Srinivasan:
A Tail Bound for Read-k Families of Functions. Electron. Colloquium Comput. Complex. TR12 (2012) - 2011
- [i9]Jan Bulánek, Michal Koucký, Michael E. Saks:
Tight lower bounds for online labeling problem. CoRR abs/1112.5636 (2011) - 2009
- [i8]Nikos Leonardos, Michael E. Saks:
Lower bounds on the randomized communication complexity of read-once functions. Electron. Colloquium Comput. Complex. TR09 (2009) - 2005
- [i7]Ryan O'Donnell, Michael E. Saks, Oded Schramm, Rocco A. Servedio:
Every decision tree has an influential variable. CoRR abs/cs/0508071 (2005) - [i6]Eric Allender, Lisa Hellerstein, Paul McCabe, Toniann Pitassi, Michael E. Saks:
Minimizing DNF Formulas and AC0 Circuits Given a Truth Table. Electron. Colloquium Comput. Complex. TR05 (2005) - 2002
- [i5]Howard Barnum, Michael E. Saks:
A lower bound on the quantum query complexity of read-once functions. CoRR quant-ph/0201007 (2002) - [i4]Howard Barnum, Michael E. Saks:
A lower bound on the quantum query complexity of read-once functions. Electron. Colloquium Comput. Complex. TR02 (2002) - 2000
- [i3]Paul Beame, Michael E. Saks, Xiaodong Sun, Erik Vee:
Super-Linear Time-Space Tradeoff Lower Bounds for Randomized Computation. Electron. Colloquium Comput. Complex. TR00 (2000) - 1999
- [i2]Eric Allender, Igor E. Shparlinski, Michael E. Saks:
A Lower Bound for Primality. Electron. Colloquium Comput. Complex. TR99 (1999) - 1998
- [i1]Paul Beame, Michael E. Saks, Jayram S. Thathachar:
Time-Space Tradeoffs for Branching Programs. Electron. Colloquium Comput. Complex. TR98 (1998)
Coauthor Index
Nathan Linial
aka: Nati Linial
aka: Nati Linial
a service of 
manage site settings
To protect your privacy, all features that rely on external API calls from your browser are turned off by default. You need to opt-in for them to become active. All settings here will be stored as cookies with your web browser. For more information see our F.A.Q.
Unpaywalled article links
Add open access links from 
to the list of external document links (if available).
Privacy notice: By enabling the option above, your browser will contact the API of unpaywall.org to load hyperlinks to open access articles. Although we do not have any reason to believe that your call will be tracked, we do not have any control over how the remote server uses your data. So please proceed with care and consider checking the Unpaywall privacy policy.
Archived links via Wayback Machine
For web page which are no longer available, try to retrieve content from the 
of the Internet Archive (if available).
Privacy notice: By enabling the option above, your browser will contact the API of archive.org to check for archived content of web pages that are no longer available. Although we do not have any reason to believe that your call will be tracked, we do not have any control over how the remote server uses your data. So please proceed with care and consider checking the Internet Archive privacy policy.
Reference lists
Add a list of references from 
, 
, and 
to record detail pages.
load references from crossref.org and opencitations.net
Privacy notice: By enabling the option above, your browser will contact the APIs of crossref.org, opencitations.net, and semanticscholar.org to load article reference information. Although we do not have any reason to believe that your call will be tracked, we do not have any control over how the remote server uses your data. So please proceed with care and consider checking the Crossref privacy policy and the OpenCitations privacy policy, as well as the AI2 Privacy Policy covering Semantic Scholar.
Citation data
Add a list of citing articles from and to record detail pages.
load citations from opencitations.net
Privacy notice: By enabling the option above, your browser will contact the API of opencitations.net and semanticscholar.org to load citation information. Although we do not have any reason to believe that your call will be tracked, we do not have any control over how the remote server uses your data. So please proceed with care and consider checking the OpenCitations privacy policy as well as the AI2 Privacy Policy covering Semantic Scholar.
OpenAlex data
Load additional information about publications from 
.
Privacy notice: By enabling the option above, your browser will contact the API of openalex.org to load additional information. Although we do not have any reason to believe that your call will be tracked, we do not have any control over how the remote server uses your data. So please proceed with care and consider checking the information given by OpenAlex.
last updated on 2024-04-07 22:30 CEST by the dblp team
all metadata released as open data under CC0 1.0 license
see also: Terms of Use | Privacy Policy | Imprint
dblp was originally created in 1993 at:
since 2018, dblp has been operated and maintained by:
the dblp computer science bibliography is funded and supported by:
