Google
Google Scholar
MS Academic
CiteSeerX
CORE
Semantic ScholarMichael 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
2020 – today
- 2020
[j82]John Chiarelli, Pooya Hatami, Michael E. Saks:
An Asymptotically Tight Bound on the Number of Relevant Variables in a Bounded Degree Boolean function. Combinatorica 40(1): 237-244 (2020)
2010 – 2019
- 2019
- [j81]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) - [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
- [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 - [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
- [j80]Michael E. Saks, C. Seshadhri:
Estimating the Longest Increasing Sequence in Polylogarithmic Time. SIAM J. Comput. 46(2): 774-823 (2017) - [j79]Justin Gilmer, Michal Koucký, Michael E. Saks:
A Communication Game Related to the Sensitivity Conjecture. Theory of Computing 13(1): 1-18 (2017) - [c71]Timothy Naumovitz, Michael E. Saks, C. Seshadhri:
Accurate and Nearly Optimal Sublinear Approximations to Ulam Distance. SODA 2017: 2012-2031 - [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. Electronic Colloquium on Computational Complexity (ECCC) 24: 9 (2017) - 2016
- [j78]Justin Gilmer, Michael E. Saks, Srikanth Srinivasan:
Composition limits and separating examples for some boolean function complexity measures. Combinatorica 36(3): 265-311 (2016) - [j77]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) - [j76]Swastik Kopparty, Mrinal Kumar, Michael E. Saks:
Efficient Indexing of Necklaces and Irreducible Polynomials over Finite Fields. Theory of Computing 12(1): 1-27 (2016) - [c70]Anindya De, Michael E. Saks, Sijian Tang:
Noisy Population Recovery in Polynomial Time. FOCS 2016: 675-684 - [r2]Ramamohan Paturi, Pavel Pudlák, Michael E. Saks, Francis Zane:
Backtracking Based k-SAT Algorithms. Encyclopedia of Algorithms 2016: 170-174 - [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. Electronic Colloquium on Computational Complexity (ECCC) 23: 26 (2016) - 2015
- [j75]Michael E. Saks:
Special issue "Conference on Computational Complexity 2014" Guest Editor's Foreword. Comput. Complex. 24(2): 197-199 (2015) - [j74]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) - [j73]Jan Bulánek, Michal Koucký, Michael E. Saks:
Tight Lower Bounds for the Online Labeling Problem. SIAM J. Comput. 44(6): 1765-1797 (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 - [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. Electronic Colloquium on Computational Complexity (ECCC) 22: 47 (2015) - 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 - [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. Electronic Colloquium on Computational Complexity (ECCC) 21: 64 (2014) - 2013
- [c65]Justin Gilmer, Michael E. Saks, Srikanth Srinivasan:
Composition Limits and Separating Examples for Some Boolean Function Complexity Measures. Computational Complexity Conference 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 - [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
- [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 - [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. Electronic Colloquium on Computational Complexity (ECCC) 19: 51 (2012) - 2011
- [j72]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) - [j71]Jeff Kahn, Michael E. Saks, Clifford D. Smyth:
The Dual BKR Inequality and Rudich's Conjecture. Comb. Probab. Comput. 20(2): 257-266 (2011) - [i9]Jan Bulánek, Michal Koucký, Michael E. Saks:
Tight lower bounds for online labeling problem. CoRR abs/1112.5636 (2011) - 2010
- [j70]Nikos Leonardos, Michael E. Saks:
Lower Bounds on the Randomized Communication Complexity of Read-Once Functions. Comput. Complex. 19(2): 153-181 (2010) - [j69]Michael E. Saks, C. Seshadhri:
Local Monotonicity Reconstruction. SIAM J. Comput. 39(7): 2897-2926 (2010) - [j68]Navin Goyal, Michael E. Saks:
Rounds vs. Queries Tradeoff in Noisy Computation. Theory of Computing 6(1): 113-134 (2010) - [c58]Michael E. Saks, C. Seshadhri:
Estimating the Longest Increasing Sequence in Polylogarithmic Time. FOCS 2010: 458-467 - [p1]Michael E. Saks, C. Seshadhri:
Local Property Reconstruction and Monotonicity. Property Testing 2010: 346-354
2000 – 2009
- 2009
- [j67]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) - [c57]Nikos Leonardos, Michael E. Saks:
Lower Bounds on the Randomized Communication Complexity of Read-Once Functions. Computational Complexity Conference 2009: 341-350 - [i8]Nikos Leonardos, Michael E. Saks:
Lower bounds on the randomized communication complexity of read-once functions. Electronic Colloquium on Computational Complexity (ECCC) 16: 10 (2009) - 2008
- [j66]Srikrishnan Divakaran, Michael E. Saks:
Approximation algorithms for problems in scheduling with set-ups. Discret. Appl. Math. 156(5): 719-729 (2008) - [j65]Navin Goyal, Guy Kindler, Michael E. Saks:
Lower Bounds for the Noisy Broadcast Problem. SIAM J. Comput. 37(6): 1806-1841 (2008) - [j64]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) - [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 - [r1]Ramamohan Paturi, Pavel Pudlák, Michael E. Saks, Francis Zane:
Backtracking Based k-SAT Algorithms. Encyclopedia of Algorithms 2008 - 2007
- [j63]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
- [j62]Nathan Linial, Michael E. Saks, David Statter:
The Non-Crossing Graph. Electr. J. Comb. 13(1) (2006) - [j61]Andrew V. Goldberg, Jason D. Hartline, Anna R. Karlin, Michael E. Saks, Andrew Wright:
Competitive auctions. Games Econ. Behav. 55(2): 242-269 (2006) - [j60]László Lovász, Michael E. Saks:
A localization inequality for set functions. J. Comb. Theory, Ser. A 113(4): 726-735 (2006) - [c54]Eric Allender, Lisa Hellerstein, Paul McCabe, Toniann Pitassi, Michael E. Saks:
Minimizing DNF Formulas and AC0d Circuits Given a Truth Table. Computational Complexity Conference 2006: 237-251 - 2005
- [j59]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) - [j58]Navin Goyal, Michael E. Saks:
A parallel search game. Random Struct. Algorithms 27(2): 227-234 (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 - [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. Electronic Colloquium on Computational Complexity (ECCC)(126) (2005) - 2004
- [j57]Michael E. Saks, Alex Samorodnitsky, Leonid Zosin:
A Lower Bound On The Integrality Gap For Minimum Multicut In Directed Networks. Combinatorica 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) - [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
- [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) - [c47]Navin Goyal, Michael E. Saks, Srinivasan Venkatesh:
Optimal Separation of EROW and CROWPRAMs. Computational Complexity Conference 2003: 93- - [c46]Howard Barnum, Michael E. Saks, Mario Szegedy:
Quantum query complexity and semi-definite programming. Computational Complexity Conference 2003: 179-193 - 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) - [c45]Michael E. Saks, Xiaodong Sun:
Space lower bounds for distance approximation in the data stream model. STOC 2002: 360-369 - [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. Electronic Colloquium on Computational Complexity (ECCC)(002) (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) - [c44]Jeff Kahn, Michael E. Saks, Clifford D. Smyth:
A Dual Version of Reimer's Inequality and a Proof of Rudich's Conjecture. Computational Complexity Conference 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 - [i3]Paul Beame, Michael E. Saks, Xiaodong Sun, Erik Vee:
Super-Linear Time-Space Tradeoff Lower Bounds for Randomized Computation. Electronic Colloquium on Computational Complexity (ECCC) 7(25) (2000)
1990 – 1999
- 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) - [c42]Eric Allender, Michael E. Saks, Igor E. Shparlinski:
A Lower Bound for Primality. Computational Complexity Conference 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 - [i2]Eric Allender, Igor E. Shparlinski, Michael E. Saks:
A Lower Bound for Primality. Electronic Colloquium on Computational Complexity (ECCC) 6(10) (1999) - 1998
- [j38]Michael E. Saks, Aravind Srinivasan, Shiyu Zhou:
Explicit OR-Dispersers with Polylogarithmic Degree. J. ACM 45(1): 123-154 (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 - [i1]Paul Beame, Michael E. Saks, Jayram S. Thathachar:
Time-Space Tradeoffs for Branching Programs. Electronic Colloquium on Computational Complexity (ECCC) 5(53) (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. Combinatorica 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) - [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 - [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] - 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)