No photo of Michael Saks

View Scopus Profile

Michael Saks

 https://orcid.org/0000-0003-1659-7190
Calculated based on number of publications stored in Pure and citations from Scopus
1979 …2023

Research activity per year

If you made any changes in Pure these will be visible here soon.
Filter
Conference contribution

Search results

  • 2022

    On Randomized Reductions to the Random Strings

    Saks, M. & Santhanam, R., Jul 1 2022, 37th Computational Complexity Conference, CCC 2022. Lovett, S. (ed.). Schloss Dagstuhl- Leibniz-Zentrum fur Informatik GmbH, Dagstuhl Publishing, 29. (Leibniz International Proceedings in Informatics, LIPIcs; vol. 234).

    Research output: Chapter in Book/Report/Conference proceeding › Conference contribution

    1 Scopus citations
  • 2020

    Circuit lower bounds from NP-hardness of MCSP under turing reductions

    Saks, M. & Santhanam, R., Jul 1 2020, 35th Computational Complexity Conference, CCC 2020. Saraf, S. (ed.). Schloss Dagstuhl- Leibniz-Zentrum fur Informatik GmbH, Dagstuhl Publishing, 26. (Leibniz International Proceedings in Informatics, LIPIcs; vol. 169).

    Research output: Chapter in Book/Report/Conference proceeding › Conference contribution

    7 Scopus citations

  • Constant factor approximations to edit distance on far input pairs in nearly linear time

    Koucký, M. & Saks, M., Jun 8 2020, STOC 2020 - Proceedings of the 52nd Annual ACM SIGACT Symposium on Theory of Computing. Makarychev, K., Makarychev, Y., Tulsiani, M., Kamath, G. & Chuzhoy, J. (eds.). Association for Computing Machinery, p. 699-712 14 p. (Proceedings of the Annual ACM Symposium on Theory of Computing).

    Research output: Chapter in Book/Report/Conference proceeding › Conference contribution

    23 Scopus citations
  • 2018

    Approximating edit distance within constant factor in truly sub-quadratic time

    Chakraborty, D., Das, D., Goldenberg, E., Koucký, M. & Saks, M., Nov 30 2018, Proceedings - 59th Annual IEEE Symposium on Foundations of Computer Science, FOCS 2018. Thorup, M. (ed.). IEEE Computer Society, p. 979-990 12 p. 8555174. (Proceedings - Annual IEEE Symposium on Foundations of Computer Science, FOCS; vol. 2018-October).

    Research output: Chapter in Book/Report/Conference proceeding › Conference contribution

    47 Scopus citations

  • Lower bounds for combinatorial algorithms for Boolean Matrix Multiplication

    Das, D., Koucký, M. & Saks, M., Feb 2 2018, 35th Symposium on Theoretical Aspects of Computer Science, STACS 2018. Vallee, B. & Niedermeier, R. (eds.). Schloss Dagstuhl- Leibniz-Zentrum fur Informatik GmbH, Dagstuhl Publishing, 23. (Leibniz International Proceedings in Informatics, LIPIcs; vol. 96).

    Research output: Chapter in Book/Report/Conference proceeding › Conference contribution

  • Online labeling: Algorithms, lower bounds and open questions

    Saks, M., 2018, Computer Science - Theory and Applications - 13th International Computer Science Symposium in Russia, CSR 2018, Proceedings. Podolskii, V. V. & Fomin, F. V. (eds.). Springer Verlag, p. 23-28 6 p. (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); vol. 10846 LNCS).

    Research output: Chapter in Book/Report/Conference proceeding › Conference contribution

    1 Scopus citations
  • 2017

    Accurate and nearly optimal sublinear approximations to ulam distance

    Naumovitz, T., Saks, M. & Seshadhri, C., 2017, 28th Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2017. Klein, P. N. (ed.). Association for Computing Machinery, p. 2012-2031 20 p. (Proceedings of the Annual ACM-SIAM Symposium on Discrete Algorithms; vol. 0).

    Research output: Chapter in Book/Report/Conference proceeding › Conference contribution

    Open Access
    16 Scopus citations
  • 2016

    Noisy Population Recovery in Polynomial Time

    De, A., Saks, M. & Tang, S., Dec 14 2016, Proceedings - 57th Annual IEEE Symposium on Foundations of Computer Science, FOCS 2016. IEEE Computer Society, p. 675-684 10 p. 7782982. (Proceedings - Annual IEEE Symposium on Foundations of Computer Science, FOCS; vol. 2016-December).

    Research output: Chapter in Book/Report/Conference proceeding › Conference contribution

    5 Scopus citations
  • 2015

    A new approach to the sensitivity conjecture

    Gilmer, J., Koucký, M. & Saks, M., Jan 11 2015, ITCS 2015 - Proceedings of the 6th Innovations in Theoretical Computer Science. Association for Computing Machinery, Inc, p. 247-254 8 p. (ITCS 2015 - Proceedings of the 6th Innovations in Theoretical Computer Science).

    Research output: Chapter in Book/Report/Conference proceeding › Conference contribution

    14 Scopus citations

  • A polylogarithmic space deterministic streaming algorithm for approximating distance to monotonicity

    Naumovitz, T. & Saks, M., 2015, Proceedings of the 26th Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2015. January ed. Association for Computing Machinery, p. 1252-1262 11 p. (Proceedings of the Annual ACM-SIAM Symposium on Discrete Algorithms; vol. 2015-January, no. January).

    Research output: Chapter in Book/Report/Conference proceeding › Conference contribution

    Open Access
    7 Scopus citations
  • 2014

    Efficient indexing of necklaces and irreducible polynomials over finite fields

    Kopparty, S., Kumar, M. & Saks, M., 2014, Automata, Languages, and Programming - 41st International Colloquium, ICALP 2014, Proceedings. PART 1 ed. Springer Verlag, p. 726-737 12 p. (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); vol. 8572 LNCS, no. PART 1).

    Research output: Chapter in Book/Report/Conference proceeding › Conference contribution

    5 Scopus citations

  • The power of super-logarithmic number of players

    Chattopadhyay, A. & Saks, M. E., Sep 1 2014, Leibniz International Proceedings in Informatics, LIPIcs. Jansen, K., Rolim, J. D. P., Devanur, N. R. & Moore, C. (eds.). Schloss Dagstuhl- Leibniz-Zentrum fur Informatik GmbH, Dagstuhl Publishing, p. 596-603 8 p. (Leibniz International Proceedings in Informatics, LIPIcs; vol. 28).

    Research output: Chapter in Book/Report/Conference proceeding › Conference contribution

    6 Scopus citations
  • 2013

    A polynomial time algorithm for lossy population recovery

    Moitra, A. & Saks, M., 2013, Proceedings - 2013 IEEE 54th Annual Symposium on Foundations of Computer Science, FOCS 2013. p. 110-116 7 p. 6686146. (Proceedings - Annual IEEE Symposium on Foundations of Computer Science, FOCS).

    Research output: Chapter in Book/Report/Conference proceeding › Conference contribution

    14 Scopus citations

  • Composition limits and separating examples for some boolean function complexity measures

    Gilmer, J., Saks, M. & Srinivasan, S., 2013, Proceedings - 2013 IEEE Conference on Computational Complexity, CCC 2013. p. 185-196 12 p. 6597761. (Proceedings of the Annual IEEE Conference on Computational Complexity).

    Research output: Chapter in Book/Report/Conference proceeding › Conference contribution

    7 Scopus citations

  • On randomized online labeling with polynomially many labels

    Bulánek, J., Koucký, M. & Saks, M., 2013, Automata, Languages, and Programming - 40th International Colloquium, ICALP 2013, Proceedings. PART 1 ed. p. 291-302 12 p. (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); vol. 7965 LNCS, no. PART 1).

    Research output: Chapter in Book/Report/Conference proceeding › Conference contribution

    4 Scopus citations

  • On the practically interesting instances of MAXCUT

    Bilu, Y., Daniely, A., Linial, N. & Saks, M., 2013, 30th International Symposium on Theoretical Aspects of Computer Science, STACS 2013. p. 526-537 12 p. (Leibniz International Proceedings in Informatics, LIPIcs; vol. 20).

    Research output: Chapter in Book/Report/Conference proceeding › Conference contribution

    16 Scopus citations

  • Space efficient streaming algorithms for the distance to monotonicity and asymmetric edit distance

    Saks, M. & Seshadhri, C., 2013, Proceedings of the 24th Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2013. p. 1698-1709 12 p. (Proceedings of the Annual ACM-SIAM Symposium on Discrete Algorithms).

    Research output: Chapter in Book/Report/Conference proceeding › Conference contribution

    18 Scopus citations
  • 2012

    On online labeling with polynomially many labels

    Babka, M., Bulánek, J., Čunát, V., Koucký, M. & Saks, M., 2012, Algorithms, ESA 2012 - 20th Annual European Symposium, Proceedings. p. 121-132 12 p. (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); vol. 7501 LNCS).

    Research output: Chapter in Book/Report/Conference proceeding › Conference contribution

    5 Scopus citations

  • Tight lower bounds for the online labeling problem

    Bulánek, J., Koucḱ, M. & Saks, M., 2012, STOC '12 - Proceedings of the 2012 ACM Symposium on Theory of Computing. p. 1185-1198 14 p. (Proceedings of the Annual ACM Symposium on Theory of Computing).

    Research output: Chapter in Book/Report/Conference proceeding › Conference contribution

    10 Scopus citations
  • 2010

    Estimating the longest increasing sequence in polylogarithmic time

    Saks, M. & Seshadhri, C., 2010, Proceedings - 2010 IEEE 51st Annual Symposium on Foundations of Computer Science, FOCS 2010. IEEE Computer Society, p. 458-467 10 p. 5671233. (Proceedings - Annual IEEE Symposium on Foundations of Computer Science, FOCS).

    Research output: Chapter in Book/Report/Conference proceeding › Conference contribution

    18 Scopus citations

  • Local property reconstruction and monotonicity

    Saks, M. & Seshadhri, C., 2010, Property Testing - Current Research and Surveys. p. 346-354 9 p. (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); vol. 6390 LNCS).

    Research output: Chapter in Book/Report/Conference proceeding › Conference contribution

  • 2009

    Lower bounds on the randomized communication complexity of read-once functions

    Leonardos, N. & Saks, M., 2009, Proceedings of the 2009 24th Annual IEEE Conference on Computational Complexity, CCC 2009. p. 341-350 10 p. 5231417. (Proceedings of the Annual IEEE Conference on Computational Complexity).

    Research output: Chapter in Book/Report/Conference proceeding › Conference contribution

    1 Scopus citations
  • 2008

    Online multicast with egalitarian cost sharing

    Charikar, M., Karloff, H., Mathieu, C., Naor, J. & Saks, M., 2008, SPAA'08 - Proceedings of the 20th Annual Symposium on Parallelism in Algorithms and Architectures. p. 70-76 7 p. (Annual ACM Symposium on Parallelism in Algorithms and Architectures).

    Research output: Chapter in Book/Report/Conference proceeding › Conference contribution

    42 Scopus citations

  • Parallel monotonicity reconstruction

    Saks, M. & Seshadhri, C., 2008, Proceedings of the 19th Annual ACM-SIAM Symposium on Discrete Algorithms. p. 962-971 10 p. (Proceedings of the Annual ACM-SIAM Symposium on Discrete Algorithms).

    Research output: Chapter in Book/Report/Conference proceeding › Conference contribution

    7 Scopus citations
  • 2006

    Inimizing DNF formulas and ACd0 circuits given a truth table

    Allender, E., Hellerstein, L., McCabe, P., Pitassi, T. & Saks, M., 2006, Proceedings - Twenty-First Annual IEEE Conference on Computational Complexity, CCC 2006. p. 237-251 15 p. 1663741. (Proceedings of the Annual IEEE Conference on Computational Complexity; vol. 2006).

    Research output: Chapter in Book/Report/Conference proceeding › Conference contribution

    15 Scopus citations
  • 2005

    Every decision tree has an influential variable

    O'Donnell, R., Saks, M., Schramm, O. & Servedio, R. A., 2005, Proceedings - 46th Annual IEEE Symposium on Foundations of Computer Science, FOCS 2005. p. 31-39 9 p. 1530699. (Proceedings - Annual IEEE Symposium on Foundations of Computer Science, FOCS; vol. 2005).

    Research output: Chapter in Book/Report/Conference proceeding › Conference contribution

    58 Scopus citations

  • Lower bounds for the noisy broadcast problem

    Goyal, N., Kindlert, G. & Saks, M., 2005, Proceedings - 46th Annual IEEE Symposium on Foundations of Computer Science, FOCS 2005. p. 40-49 10 p. 1530700. (Proceedings - Annual IEEE Symposium on Foundations of Computer Science, FOCS; vol. 2005).

    Research output: Chapter in Book/Report/Conference proceeding › Conference contribution

    13 Scopus citations
  • 1999

    Low discrepancy sets yield approximate min-wise independent permutation families

    Saks, M., Srinivasan, A., Zhou, S. & Zuckerman, D., 1999, Randomization, Approximation, and Combinatorial Optimization: Algorithms and Techniques - 3rd International Workshop on Randomization and Approximation Techniques in Computer Science and 2nd International Workshop on Approximation Algorithms for Combinatorial Optimization Problems, RANDOM-APPROX 1999, Proceedings. Rolim, J. D. P., Sinclair, A., Hochbaum, D. & Jansen, K. (eds.). Springer Verlag, p. 11-15 5 p. (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); vol. 1671).

    Research output: Chapter in Book/Report/Conference proceeding › Conference contribution

  • Lower bound for primality

    Allender, E., Saks, M. & Shparlinski, I., 1999, Proceedings of the Annual IEEE Conference on Computational Complexity. IEEE Comp Soc, p. 10-14 5 p. (Proceedings of the Annual IEEE Conference on Computational Complexity).

    Research output: Chapter in Book/Report/Conference proceeding › Conference contribution

    1 Scopus citations

  • On list update and work function algorithms

    Anderson, E. J., Hildrum, K., Karlin, A. R., Rasala, A. & Saks, M., 1999, Algorithms - ESA 1999 - 7th Annual European Symposium, Proceedings. Nešetřil, J. (ed.). Springer Verlag, p. 289-300 12 p. (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); vol. 1643).

    Research output: Chapter in Book/Report/Conference proceeding › Conference contribution

  • 1997

    Sample spaces with small bias on neighborhoods and error-correcting communication protocols

    Saks, M. & Zhou, S., 1997, Randomization and Approximation Techniques in Computer Science - International Workshop, RANDOM 1997, Proceedings. Rolim, J. (ed.). Springer Verlag, p. 95-109 15 p. (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); vol. 1269).

    Research output: Chapter in Book/Report/Conference proceeding › Conference contribution

    1 Scopus citations
  • 1996

    Randomized robot navigation algorithms

    Berman, P., Blum, A., Fiat, A., Karloff, H., Rosén, A. & Saks, M., Jan 28 1996, Proceedings of the 7th Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 1996. Association for Computing Machinery, p. 75-84 10 p. (Proceedings of the Annual ACM-SIAM Symposium on Discrete Algorithms; vol. Part F129447).

    Research output: Chapter in Book/Report/Conference proceeding › Conference contribution

    33 Scopus citations
  • 1993

    Efficient construction of a small hitting set for combinatorial rectangles in high dimension

    Linial, N., Luby, M., Saks, M. & Zuckerman, D., Jun 1 1993, Proceedings of the 25th Annual ACM Symposium on Theory of Computing, STOC 1993. Association for Computing Machinery, p. 258-267 10 p. (Proceedings of the Annual ACM Symposium on Theory of Computing; vol. Part F129585).

    Research output: Chapter in Book/Report/Conference proceeding › Conference contribution

  • Size-depth trade-offs for threshold circuits

    Impagliazzo, R., Paturi, R. & Saks, M. E., Jun 1 1993, Proceedings of the 25th Annual ACM Symposium on Theory of Computing, STOC 1993. Association for Computing Machinery, p. 541-550 10 p. (Proceedings of the Annual ACM Symposium on Theory of Computing; vol. Part F129585).

    Research output: Chapter in Book/Report/Conference proceeding › Conference contribution

    2 Scopus citations

  • Wait-free k-set agreement is impossible: The topology of public knowledge (Extended abstract)

    Saks, M. & Zaharoglou, F., Jun 1 1993, Proceedings of the 25th Annual ACM Symposium on Theory of Computing, STOC 1993. Association for Computing Machinery, p. 101-110 10 p. (Proceedings of the Annual ACM Symposium on Theory of Computing; vol. Part F129585).

    Research output: Chapter in Book/Report/Conference proceeding › Conference contribution

    45 Scopus citations
  • 1992

    Adapting to asynchronous dynamic networks

    Awerbuch, B., Patt-Shamir, B., Peleg, D. & Saks, M., Jul 1 1992, Proceedings of the 24th Annual ACM Symposium on Theory of Computing, STOC 1992. Association for Computing Machinery, p. 557-570 14 p. (Proceedings of the Annual ACM Symposium on Theory of Computing; vol. Part F129722).

    Research output: Chapter in Book/Report/Conference proceeding › Conference contribution

    35 Scopus citations

  • A decomposition theorem and bounds for randomized server problems

    Blum, A., Karloff, H., Rabani, Y. & Saks, M., 1992, Proceedings - 33rd Annual Symposium on Foundations of Computer Science, FOCS 1992. IEEE Computer Society, p. 197-207 11 p. 267772. (Proceedings - Annual IEEE Symposium on Foundations of Computer Science, FOCS; vol. 1992-October).

    Research output: Chapter in Book/Report/Conference proceeding › Conference contribution

    21 Scopus citations

  • Non-deterministic communication complexity with few witnesses

    Karchmer, M., Saks, M., Newman, I. & Wigderson, A., 1992, Proceedings of the Seventh Annual Structure in Complexity Theory Conference. Publ by ERROR: no PUB record found for PX none CN nonpie IG 75516, p. 275-281 7 p. (Proceedings of the Seventh Annual Structure in Complexity Theory Conference).

    Research output: Chapter in Book/Report/Conference proceeding › Conference contribution

  • 1991

    Decomposing graphs into regions of small diameter

    Linial, N. & Saks, M., Mar 1 1991, Proceedings of the 2nd Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 1991. Association for Computing Machinery, p. 320-330 11 p. (Proceedings of the Annual ACM-SIAM Symposium on Discrete Algorithms).

    Research output: Chapter in Book/Report/Conference proceeding › Conference contribution

    29 Scopus citations

  • Optimal space distributed move-to-front lists

    Saks, M. & Zaharoglou, F., Jul 1 1991, Proceedings of the Annual ACM Symposium on Principles of Distributed Computing. Association for Computing Machinery, p. 65-73 9 p. (Proceedings of the Annual ACM Symposium on Principles of Distributed Computing).

    Research output: Chapter in Book/Report/Conference proceeding › Conference contribution

    Open Access
    2 Scopus citations

  • Optimal time randomized consensus - Making resilient algorithms fast in practice

    Saks, M., Shavit, N. & Woll, H., Mar 1 1991, Proceedings of the 2nd Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 1991. Association for Computing Machinery, p. 351-362 12 p. (Proceedings of the Annual ACM-SIAM Symposium on Discrete Algorithms).

    Research output: Chapter in Book/Report/Conference proceeding › Conference contribution

    45 Scopus citations
  • 1990

    On threshold circuits for parity (abstract)

    Paturi, R. & Saks, M. E., Jul 1 1990, Proceedings of the 3rd Annual Workshop on Computational Learning Theory, COLT 1990. Association for Computing Machinery, Inc, 1 p. (Proceedings of the 3rd Annual Workshop on Computational Learning Theory, COLT 1990).

    Research output: Chapter in Book/Report/Conference proceeding › Conference contribution

  • 1989

    Cell probe complexity of dynamic data structures

    Fredman, M. L. & Saks, M. E., 1989, Proc Twenty First Annu ACM Symp Theory Comput. Publ by ACM, p. 345-354 10 p. (Proc Twenty First Annu ACM Symp Theory Comput).

    Research output: Chapter in Book/Report/Conference proceeding › Conference contribution

    Open Access
    166 Scopus citations
  • 1988

    Lattices, mobius functions and communication complexity

    Lovasz, L. & Saks, M., 1988, Annual Symposium on Foundations of Computer Science (Proceedings). Publ by IEEE, p. 81-90 10 p. (Annual Symposium on Foundations of Computer Science (Proceedings)).

    Research output: Chapter in Book/Report/Conference proceeding › Conference contribution

    60 Scopus citations
  • 1987

    Detecting global termination conditions in the face of uncertainty

    Afek, Y. & Saks, M., Dec 1 1987, Proceedings of the 6th Annual ACM Symposium on Principles of Distributed Computing, PODC 1987. Schneider, F. B. (ed.). Association for Computing Machinery, p. 109-124 16 p. (Proceedings of the Annual ACM Symposium on Principles of Distributed Computing; vol. Part F130235).

    Research output: Chapter in Book/Report/Conference proceeding › Conference contribution

    8 Scopus citations

  • LOCAL MANAGEMENT OF A GLOBAL RESOURCE IN A COMMUNICATION NETWORK.

    Afek, Y., Awerbuch, B., Plotkin, S. A. & Saks, M., 1987, Annual Symposium on Foundations of Computer Science (Proceedings). IEEE, p. 347-357 11 p. (Annual Symposium on Foundations of Computer Science (Proceedings)).

    Research output: Chapter in Book/Report/Conference proceeding › Conference contribution

    3 Scopus citations
  • 1986

    ON A SEARCH PROBLEM RELATED TO BRANCH-AND-BOUND PROCEDURES.

    Karp, R. M., Saks, M. & Wigderson, A., 1986, Annual Symposium on Foundations of Computer Science (Proceedings). IEEE, p. 19-28 10 p. (Annual Symposium on Foundations of Computer Science (Proceedings)).

    Research output: Chapter in Book/Report/Conference proceeding › Conference contribution

    9 Scopus citations

  • PROBABILISTIC BOOLEAN DECISION TREES AND THE COMPLEXITY OF EVALUATING GAME TREES.

    Saks, M. & Wigderson, A., 1986, Annual Symposium on Foundations of Computer Science (Proceedings). IEEE, p. 29-38 10 p. (Annual Symposium on Foundations of Computer Science (Proceedings)).

    Research output: Chapter in Book/Report/Conference proceeding › Conference contribution

    110 Scopus citations
  • 1984

    Every poset has a good comparison

    Kahn, J. & Saks, M., Dec 1 1984, Proceedings of the 16th Annual ACM Symposium on Theory of Computing, STOC 1984. Association for Computing Machinery, p. 299-301 3 p. (Proceedings of the Annual ACM Symposium on Theory of Computing).

    Research output: Chapter in Book/Report/Conference proceeding › Conference contribution

    Open Access
  • 1983

    BALANCED SORTING NETWORK.

    Dowd, M., Perl, Y., Saks, M. & Rudolph, L., 1983, Unknown Host Publication Title. ACM, p. 161-172 12 p.

    Research output: Chapter in Book/Report/Conference proceeding › Conference contribution

    13 Scopus citations