• 3914 Citations
  • 36 h-Index
1979 …2019
If you made any changes in Pure, your changes will be visible here soon.

Fingerprint Dive into the research topics where Michael Saks is active. These topic labels come from the works of this person. Together they form a unique fingerprint.

  • 3 Similar Profiles
Lower bound Mathematics
Polynomials Engineering & Materials Science
Boolean functions Engineering & Materials Science
Graph in graph theory Mathematics
Boolean Functions Mathematics
Networks (circuits) Engineering & Materials Science
Communication Engineering & Materials Science
Communication Complexity Mathematics

Network Recent external collaboration on country level. Dive into details by clicking on the dots.

Projects 2012 2015

Parallel programming
Computational complexity
Students
Costs

Research Output 1979 2019

On online labeling with large label Set

Babka, M., Bulanek, J., Cun, V., Koucky, M. & Saks, M. E., Jan 1 2019, In : SIAM Journal on Discrete Mathematics. 33, 3, p. 1175-1193 19 p.

Research output: Contribution to journalArticle

Labeling
Lower bound
Prefix
Asymptotically Optimal
Costs
12 Citations (Scopus)

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

Dynamic programming
Substitution reactions

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

Online labeling: Algorithms, lower bounds and open questions

Saks, M., Jan 1 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

Labeling Algorithm
Online Algorithms
Labeling
Labels
Lower bound

Accurate and nearly optimal sublinear approximations to ulam distance

Naumovitz, T., Saks, M. & Seshadhri, C., Jan 1 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).

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

Approximation
Longest Common Subsequence
Permutation
Multiplicative
Longest Increasing Subsequence