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.
- 1 Similar Profiles
Network
Recent external collaboration on country/territory level. Dive into details by clicking on the dots or
Projects
- 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
Research output
-
On the rational relationships among pseudo-roots of a non-commutative polynomial
Retakh, V. & Saks, M., Jun 2021, In: Journal of Pure and Applied Algebra. 225, 6, 106581.Research output: Contribution to journal › Article › peer-review
-
An Asymptotically Tight Bound on the Number of Relevant Variables in a Bounded Degree Boolean function
Chiarelli, J., Hatami, P. & Saks, M., Apr 1 2020, In: Combinatorica. 40, 2, p. 237-244 8 p.Research output: Contribution to journal › Article › peer-review
4 Scopus citations -
Approximating Edit Distance within Constant Factor in Truly Sub-quadratic Time
Chakraborty, D., Das, D., Goldenberg, E., Koucký, M. & Saks, M., Nov 2020, In: Journal of the ACM. 67, 6, 36.Research output: Contribution to journal › Article › peer-review
4 Scopus citations -
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
2 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
Open Access12 Scopus citations