Michael E. Saks

ORCID

Publication Activity (10 Years)

Years Active: 1979-2023
Publications (10 Years): 31

Top Venues

CoRR

SODA

Electron. Colloquium Comput. Complex.

FOCS

Publications

Michal Koucký, Michael E. Saks
Simple, deterministic, fast (but weak) approximations to edit distance and Dyck edit distance. SODA (2023)
Michal Koucký, Michael E. Saks
Constant factor approximations to edit distance on far input pairs in nearly linear time. STOC (2020)
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) (2020)
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) (2020)
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) (2019)
Michal Koucký, Michael E. Saks
Constant factor approximations to edit distance on far input pairs in nearly linear time. CoRR (2019)
Diptarka Chakraborty, Debarati Das, Elazar Goldenberg, Michal Koucký, Michael E. Saks
Approximating Edit Distance within Constant Factor in Truly Sub-Quadratic Time. FOCS (2018)
Michael E. Saks
Online Labeling: Algorithms, Lower Bounds and Open Questions. CSR (2018)
Debarati Das, Michal Koucký, Michael E. Saks
Lower bounds for Combinatorial Algorithms for Boolean Matrix Multiplication. CoRR (2018)
John Chiarelli, Pooya Hatami, Michael E. Saks
Tight Bound on the Number of Relevant Variables in a Bounded degree Boolean function. CoRR (2018)
Diptarka Chakraborty, Debarati Das, Elazar Goldenberg, Michal Koucký, Michael E. Saks
Approximating Edit Distance Within Constant Factor in Truly Sub-Quadratic Time. CoRR (2018)
Debarati Das, Michal Koucký, Michael E. Saks
Lower Bounds for Combinatorial Algorithms for Boolean Matrix Multiplication. STACS (2018)
Joshua A. Grochow, Mrinal Kumar, Michael E. Saks, Shubhangi Saraf
Towards an algebraic natural proofs barrier via polynomial identity testing. Electron. Colloquium Comput. Complex. 24 (2017)
Michael E. Saks, C. Seshadhri
Estimating the Longest Increasing Sequence in Polylogarithmic Time. SIAM J. Comput. 46 (2) (2017)
Joshua A. Grochow, Mrinal Kumar, Michael E. Saks, Shubhangi Saraf
Towards an algebraic natural proofs barrier via polynomial identity testing. CoRR (2017)
Justin Gilmer, Michal Koucký, Michael E. Saks
A Communication Game Related to the Sensitivity Conjecture. Theory Comput. 13 (1) (2017)
Timothy Naumovitz, Michael E. Saks, C. Seshadhri
Accurate and Nearly Optimal Sublinear Approximations to Ulam Distance. SODA (2017)
Anindya De, Michael E. Saks, Sijian Tang
Noisy population recovery in polynomial time. Electron. Colloquium Comput. Complex. 23 (2016)
Anindya De, Michael E. Saks, Sijian Tang
Noisy population recovery in polynomial time. CoRR (2016)
Troy Lee, Nikos Leonardos, Michael E. Saks, Fengming Wang
Hellinger volume and number-on-the-forehead communication complexity. J. Comput. Syst. Sci. 82 (6) (2016)
Anindya De, Michael E. Saks, Sijian Tang
Noisy Population Recovery in Polynomial Time. FOCS (2016)
Justin Gilmer, Michael E. Saks, Srikanth Srinivasan
Composition limits and separating examples for some boolean function complexity measures. Comb. 36 (3) (2016)
Swastik Kopparty, Mrinal Kumar, Michael E. Saks
Efficient Indexing of Necklaces and Irreducible Polynomials over Finite Fields. Theory Comput. 12 (1) (2016)
Timothy Naumovitz, Michael E. Saks
A polylogarithmic space deterministic streaming algorithm for approximating distance to monotonicity. SODA (2015)
Michael E. Saks
Special issue "Conference on Computational Complexity 2014" Guest Editor's Foreword. Comput. Complex. 24 (2) (2015)
Dmitry Gavinsky, Shachar Lovett, Michael E. Saks, Srikanth Srinivasan
families of functions. Random Struct. Algorithms 47 (1) (2015)
Justin Gilmer, Michal Koucký, Michael E. Saks
A New Approach to the Sensitivity Conjecture. ITCS (2015)
Swastik Kopparty, Mrinal Kumar, Michael E. Saks
Efficient indexing of necklaces and irreducible polynomials over finite fields. CoRR (2015)
Jan Bulánek, Michal Koucký, Michael E. Saks
Tight Lower Bounds for the Online Labeling Problem. SIAM J. Comput. 44 (6) (2015)
Swastik Kopparty, Mrinal Kumar, Michael E. Saks
Efficient indexing of necklaces and irreducible polynomials over finite fields. Electron. Colloquium Comput. Complex. 22 (2015)
Justin Gilmer, Michal Koucký, Michael E. Saks
A communication game related to the sensitivity conjecture. CoRR (2015)
Arkadev Chattopadhyay, Michael E. Saks
The Power of Super-logarithmic Number of Players. Electron. Colloquium Comput. Complex. 21 (2014)
Swastik Kopparty, Mrinal Kumar, Michael E. Saks
Efficient Indexing of Necklaces and Irreducible Polynomials over Finite Fields. ICALP (1) (2014)
Troy Lee, Nikos Leonardos, Michael E. Saks, Fengming Wang
Hellinger volume and number-on-the-forehead communication complexity. CoRR (2014)
Arkadev Chattopadhyay, Michael E. Saks
The Power of Super-logarithmic Number of Players. APPROX-RANDOM (2014)
Michael E. Saks, C. Seshadhri
Space efficient streaming algorithms for the distance to monotonicity and asymmetric edit distance. SODA (2013)
Justin Gilmer, Michael E. Saks, Srikanth Srinivasan
Composition limits and separating examples for some Boolean function complexity measures. CoRR (2013)
Ankur Moitra, Michael E. Saks
A Polynomial Time Algorithm for Lossy Population Recovery. FOCS (2013)
Michael E. Saks, C. Seshadhri
Estimating the longest increasing sequence in polylogarithmic time. CoRR (2013)
Ankur Moitra, Michael E. Saks
A Polynomial Time Algorithm for Lossy Population Recovery CoRR (2013)
Justin Gilmer, Michael E. Saks, Srikanth Srinivasan
Composition Limits and Separating Examples for Some Boolean Function Complexity Measures. Computational Complexity Conference (2013)
Yonatan Bilu, Amit Daniely, Nati Linial, Michael E. Saks
On the practically interesting instances of MAXCUT. STACS (2013)
Jan Bulánek, Michal Koucký, Michael E. Saks
On Randomized Online Labeling with Polynomially Many Labels. ICALP (1) (2013)
Jan Bulánek, Michal Koucký, Michael E. Saks
Tight lower bounds for the online labeling problem. STOC (2012)
Martin Babka, Jan Bulánek, Vladimír Cunát, Michal Koucký, Michael E. Saks
On Online Labeling with Polynomially Many Labels. ESA (2012)
Martin Babka, Jan Bulánek, Vladimír Cunát, Michal Koucký, Michael E. Saks
On Online Labeling with Polynomially Many Labels CoRR (2012)
Dmitry Gavinsky, Shachar Lovett, Michael E. Saks, Srikanth Srinivasan
A Tail Bound for Read-k Families of Functions CoRR (2012)
Amit Daniely, Nati Linial, Michael E. Saks
Clustering is difficult only when it does not matter CoRR (2012)
Michael E. Saks, C. Seshadhri
Space efficient streaming algorithms for the distance to monotonicity and asymmetric edit distance CoRR (2012)
Yonatan Bilu, Amit Daniely, Nati Linial, Michael E. Saks
On the practically interesting instances of MAXCUT CoRR (2012)
Dmitry Gavinsky, Shachar Lovett, Michael E. Saks, Srikanth Srinivasan
A Tail Bound for Read-k Families of Functions. Electron. Colloquium Comput. Complex. 19 (2012)
Jeff Kahn, Michael E. Saks, Clifford D. Smyth
The Dual BKR Inequality and Rudich's Conjecture. Comb. Probab. Comput. 20 (2) (2011)
Srikrishnan Divakaran, Michael E. Saks
An Online Algorithm for a Problem in Scheduling with Set-ups and Release Times. Algorithmica 60 (2) (2011)
Jan Bulánek, Michal Koucký, Michael E. Saks
Tight lower bounds for online labeling problem CoRR (2011)
Michael E. Saks, C. Seshadhri
Estimating the Longest Increasing Sequence in Polylogarithmic Time. FOCS (2010)
Michael E. Saks, C. Seshadhri
Local Monotonicity Reconstruction. SIAM J. Comput. 39 (7) (2010)
Nikos Leonardos, Michael E. Saks
Lower Bounds on the Randomized Communication Complexity of Read-Once Functions. Comput. Complex. 19 (2) (2010)
Navin Goyal, Michael E. Saks
Rounds vs. Queries Tradeoff in Noisy Computation. Theory Comput. 6 (1) (2010)
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) (2009)
Nikos Leonardos, Michael E. Saks
Lower Bounds on the Randomized Communication Complexity of Read-Once Functions. Computational Complexity Conference (2009)
Nikos Leonardos, Michael E. Saks
Lower bounds on the randomized communication complexity of read-once functions. Electron. Colloquium Comput. Complex. 16 (2009)
Moses Charikar, Howard J. Karloff, Claire Mathieu, Joseph Naor, Michael E. Saks
Online multicast with egalitarian cost sharing. SPAA (2008)
Srikrishnan Divakaran, Michael E. Saks
Approximation algorithms for problems in scheduling with set-ups. Discret. Appl. Math. 156 (5) (2008)
Navin Goyal, Guy Kindler, Michael E. Saks
Lower Bounds for the Noisy Broadcast Problem. SIAM J. Comput. 37 (6) (2008)
Eric Allender, Lisa Hellerstein, Paul McCabe, Toniann Pitassi, Michael E. Saks
Circuits Given a Truth Table. SIAM J. Comput. 38 (1) (2008)
Michael E. Saks, C. Seshadhri
Parallel monotonicity reconstruction. SODA (2008)
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) (2007)
László Lovász, Michael E. Saks
A localization inequality for set functions. J. Comb. Theory, Ser. A 113 (4) (2006)
Andrew V. Goldberg, Jason D. Hartline, Anna R. Karlin, Michael E. Saks, Andrew Wright
Competitive auctions. Games Econ. Behav. 55 (2) (2006)
Nathan Linial, Michael E. Saks, David Statter
The Non-Crossing Graph. Electron. J. Comb. 13 (1) (2006)
Eric Allender, Lisa Hellerstein, Paul McCabe, Toniann Pitassi, Michael E. Saks
Circuits Given a Truth Table. Computational Complexity Conference (2006)
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)
Ramamohan Paturi, Pavel Pudlák, Michael E. Saks, Francis Zane
-SAT. J. ACM 52 (3) (2005)
Navin Goyal, Michael E. Saks
Rounds vs queries trade-off in noisy computation. SODA (2005)
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. (126) (2005)
Navin Goyal, Michael E. Saks
A parallel search game. Random Struct. Algorithms 27 (2) (2005)
Ryan O'Donnell, Michael E. Saks, Oded Schramm, Rocco A. Servedio
Every decision tree has an in.uential variable. FOCS (2005)
Navin Goyal, Guy Kindler, Michael E. Saks
Lower Bounds for the Noisy Broadcast Problem. FOCS (2005)
Michael E. Saks, Lan Yu
Weak monotonicity suffices for truthfulness on convex domains. EC (2005)
Ryan O'Donnell, Michael E. Saks, Oded Schramm, Rocco A. Servedio
Every decision tree has an influential variable CoRR (2005)
Michael E. Saks, Alex Samorodnitsky, Leonid Zosin
A Lower Bound On The Integrality Gap For Minimum Multicut In Directed Networks. Comb. 24 (3) (2004)
Andrew V. Goldberg, Jason D. Hartline, Anna R. Karlin, Michael E. Saks
A Lower Bound on the Competitive Ratio of Truthful Auctions. STACS (2004)
Howard Barnum, Michael E. Saks
A lower bound on the quantum query complexity of read-once functions. J. Comput. Syst. Sci. 69 (2) (2004)
Howard Barnum, Michael E. Saks, Mario Szegedy
Quantum query complexity and semi-definite programming. Computational Complexity Conference (2003)
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) (2003)
Navin Goyal, Michael E. Saks, Srinivasan Venkatesh
Optimal Separation of EROW and CROWPRAMs. Computational Complexity Conference (2003)
Nathan Linial, Michael E. Saks
The Euclidean Distortion of Complete Binary Trees. Discret. Comput. Geom. 29 (1) (2003)
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) (2003)
Michael E. Saks
Kleitman and combinatorics. Discret. Math. 257 (2-3) (2002)
Howard Barnum, Michael E. Saks
A lower bound on the quantum query complexity of read-once functions Electron. Colloquium Comput. Complex. (002) (2002)
Michael E. Saks, Xiaodong Sun
Space lower bounds for distance approximation in the data stream model. STOC (2002)
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) (2002)
Paul Beame, Richard M. Karp, Toniann Pitassi, Michael E. Saks
The Efficiency of Resolution and Davis--Putnam Procedures. SIAM J. Comput. 31 (4) (2002)
Howard Barnum, Michael E. Saks
A lower bound on the quantum query complexity of read-once functions CoRR (2002)
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) (2002)
Paul Beame, T. S. Jayram, Michael E. Saks
Time-Space Tradeoffs for Branching Programs. J. Comput. Syst. Sci. 63 (4) (2001)
Michael E. Saks, Shiyu Zhou
Sample Spaces with Small Bias on Neighborhoods and Error-Correcting Communication Protocols. Algorithmica 30 (3) (2001)
Eric Allender, Michael E. Saks, Igor E. Shparlinski
A Lower Bound for Primality. J. Comput. Syst. Sci. 62 (2) (2001)
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) (2000)
Paul Beame, Michael E. Saks, Xiaodong Sun, Erik Vee
Super-linear time-space tradeoff lower bounds for randomized computation. FOCS (2000)

Michael E. Saks.css-eqlu8i{font-size:small;padding-left:4px;}

Publication Activity (10 Years)

Top Topics

Top Venues

Michael E. Saks