Projects per year
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
- 1 Finished
AF: SMALL: EFFICIENT APPROXIMATIONS FOR DYNAMIC PROGRAMS AND OTHER TOPICS IN ALGORITHMS
National Science Foundation (National Science Foundation (NSF))
9/1/12 → 8/31/15
Project: Research project
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 journal › Article
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 proceeding › Conference 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 proceeding › Conference 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 proceeding › Conference 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 proceeding › Conference contribution
Approximation
Longest Common Subsequence
Permutation
Multiplicative
Longest Increasing Subsequence