Michael Saks

Research activity per year

If you made any changes in Pure these 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.

1 Similar Profiles

1 Finished

AF: SMALL: EFFICIENT APPROXIMATIONS FOR DYNAMIC PROGRAMS AND OTHER TOPICS IN ALGORITHMS
Saks, M.
National Science Foundation (National Science Foundation (NSF))
9/1/12 → 8/31/15
Rutgers, The State University
Project: Research project

4254 Citations
37 h-Index
93 Article
51 Conference contribution
21 Conference article
3 Editorial
More
- 2 Chapter
- 2 Paper

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.
Rutgers, The State University
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.
Rutgers, The State University
Research output: Contribution to journal › Article › peer-review
3 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.
Rutgers, The State University
Research output: Contribution to journal › Article › peer-review
1 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).
Rutgers, The State University
Research output: Chapter in Book/Report/Conference proceeding › Conference contribution
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).
Rutgers, The State University
Research output: Chapter in Book/Report/Conference proceeding › Conference contribution

Open Access

5 Scopus citations

Michael Saks

Fingerprint

Network

Dive into details

AF: SMALL: EFFICIENT APPROXIMATIONS FOR DYNAMIC PROGRAMS AND OTHER TOPICS IN ALGORITHMS

On the rational relationships among pseudo-roots of a non-commutative polynomial

An Asymptotically Tight Bound on the Number of Relevant Variables in a Bounded Degree Boolean function

Approximating Edit Distance within Constant Factor in Truly Sub-quadratic Time

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

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

Michael Saks

Fingerprint

Network

Projects

AF: SMALL: EFFICIENT APPROXIMATIONS FOR DYNAMIC PROGRAMS AND OTHER TOPICS IN ALGORITHMS

Research output

On the rational relationships among pseudo-roots of a non-commutative polynomial

An Asymptotically Tight Bound on the Number of Relevant Variables in a Bounded Degree Boolean function

Approximating Edit Distance within Constant Factor in Truly Sub-quadratic Time

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

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