Calculated based on number of publications stored in Pure and citations from Scopus
1979 …2023

Research activity per year

Filter
Conference contribution

Search results

  • 2023

    Simple, deterministic, fast (but weak) approximations to edit distance and Dyck edit distance

    Koucký, M. & Saks, M., 2023, 34th Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2023. Association for Computing Machinery, p. 5203-5219 17 p. (Proceedings of the Annual ACM-SIAM Symposium on Discrete Algorithms; vol. 2023-January).

    Research output: Chapter in Book/Report/Conference proceedingConference contribution

    1 Scopus citations
  • 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 proceedingConference contribution

    3 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 proceedingConference contribution

    11 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 proceedingConference contribution

    32 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 proceedingConference contribution

    Open Access
    51 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 proceedingConference contribution

    1 Scopus citations
  • 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 proceedingConference 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 proceedingConference contribution

    Open Access
    18 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 proceedingConference contribution

    6 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 proceedingConference 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 proceedingConference contribution

    Open Access
    9 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 proceedingConference contribution

    Open Access
    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 proceedingConference 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 proceedingConference contribution

    Open Access
    16 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 proceedingConference contribution

    Open Access
    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 proceedingConference 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 proceedingConference contribution

    17 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 proceedingConference contribution

    19 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 proceedingConference contribution

    Open Access
    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 proceedingConference 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 proceedingConference contribution

    Open Access
    19 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 proceedingConference contribution

    Open Access
  • 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 proceedingConference contribution

    2 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 proceedingConference contribution

    41 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 proceedingConference contribution

    9 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 proceedingConference 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 proceedingConference contribution

    77 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 proceedingConference contribution

    Open Access
    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 proceedingConference 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 proceedingConference contribution

    3 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 proceedingConference 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 proceedingConference 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 proceedingConference contribution

    34 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 proceedingConference contribution

    Open Access
    8 Scopus citations
  • 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 proceedingConference contribution

    10 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 proceedingConference contribution

    83 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 proceedingConference contribution

    Open Access
    41 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 proceedingConference contribution

    25 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 proceedingConference 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 proceedingConference contribution

    50 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 proceedingConference 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 proceedingConference contribution

    67 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, p. 390 1 p. (Proceedings of the 3rd Annual Workshop on Computational Learning Theory, COLT 1990).

    Research output: Chapter in Book/Report/Conference proceedingConference 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 proceedingConference contribution

    Open Access
    238 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 proceedingConference contribution

    89 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 proceedingConference contribution

    15 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 proceedingConference contribution

    15 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 proceedingConference contribution

    18 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 proceedingConference contribution

    138 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 proceedingConference contribution

    Open Access
    1 Scopus citations