Michael Saks

ScholarGPS® ID: 41753393993712

Affiliation

Rutgers, The State University of New Jersey, New Brunswick, Newark and Camden, United States

Affiliation History

Field

Physical Sciences and Mathematics

Discipline

Mathematics

Top Specialties

Metrics Summary

Publication Count

159

Predicted Citations

7,129

Predicted h-index

Ranking

Publications and Citation History

Publications based on Top Specialties

Types of Publication

Publications
Books
Patents
NIH/NSF

Add Delete
Almost Linear Size Edit Distance Sketch (conference) Koucký, Michal \| Saks, Michael E. STOC '24: 56th Annual ACM Symposium on Theory of Computing (2024) Vancouver BC Canada 10.1145/3618260.3649783 Cite \| Source
Simple, deterministic, fast (but weak) approximations to edit distance and Dyck edit distance (book chapter) In Proceedings of the 2023 Annual ACM-SIAM Symposium on Discrete Algorithms (SODA) Koucký, Michal \| Saks, Michael Society for Industrial and Applied Mathematics (2023) 10.1137/1.9781611977554.ch188 Cite \| Source
On the rational relationships among pseudo-roots of a non-commutative polynomial (journal article) Retakh, Vladimir \| Saks, Michael Journal of Pure and Applied Algebra, volume 225, issue 6, pages 106581- (2021). 10.1016/j.jpaa.2020.106581 Cite \| Source
Approximating Edit Distance Within Constant Factor in Truly Sub-quadratic Time (journal article) Chakraborty, Diptarka \| Das, Debarati \| Goldenberg, Elazar \| Koucký, Michal \| Saks, Michael Journal of the ACM, volume 67, issue 6, pages 1-22 (2020). 10.1145/3422823 Cited by (12) \| Cite \| Source
On the discrepancy of random matrices with many columns (journal article) Franks, Cole \| Saks, Michael Random Structures & Algorithms, volume 57, issue 1, pages 64-96 (2020). 10.1002/rsa.20909 Cited by (3) \| Cite \| Source
Constant factor approximations to edit distance on far input pairs in nearly linear time (conference) Koucký, Michal \| Saks, Michael STOC '20: 52nd Annual ACM SIGACT Symposium on Theory of Computing (2020) Chicago IL USA 10.1145/3357713.3384307 Cited by (15) \| Cite \| Source
An Asymptotically Tight Bound on the Number of Relevant Variables in a Bounded Degree Boolean function (journal article) Chiarelli, John \| Hatami, Pooya \| Saks, Michael Combinatorica, volume 40, issue 2, pages 237-244 (2020). 10.1007/s00493-019-4136-7 Cited by (4) \| Cite \| Source
On Online Labeling with Large Label Set (journal article) Babka, Martin \| Bulánek, Jan \| Čunát, Vladimŕ \| Koucký, Michal \| Saks, Michael E. SIAM Journal on Discrete Mathematics, volume 33, issue 3, pages 1175-1193 (2019). 10.1137/17M1117458 Cited by (3) \| Cite \| Source
Approximating Edit Distance within Constant Factor in Truly Sub-Quadratic Time (conference) Chakraborty, Diptarka \| Das, Debarati \| Goldenberg, Elazar \| Koucky, Michal \| Saks, Michael 2018 IEEE 59th Annual Symposium on Foundations of Computer Science (FOCS) (2018) Paris 10.1109/FOCS.2018.00096 Cited by (25) \| Cite \| Source
Lower Bounds for Combinatorial Algorithms for Boolean Matrix Multiplication. (conference) Das, Debarati \| Koucký, Michal \| Saks, Michael E. Symposium on Theoretical Aspects of Computer Science (2018) 10.4230/LIPIcs.STACS.2018.23 Cited by (1) \| Cite \| Source
Online Labeling: Algorithms, Lower Bounds and Open Questions (book chapter) In Computer Science – Theory and Applications Saks, Michael Springer International Publishing (2018) 10.1007/978-3-319-90530-3_3 Cited by (1) \| Cite \| Source
Accurate and Nearly Optimal Sublinear Approximations to Ulam Distance (conference) Naumovitz, Timothy \| Saks, Michael \| Seshadhri, C. Proceedings of the Twenty-Eighth Annual ACM-SIAM Symposium on Discrete Algorithms (2017) 10.1137/1.9781611974782.131 Cited by (8) \| Cite \| Source \| Open Access
Noisy Population Recovery in Polynomial Time (conference) De, Anindya \| Saks, Michael \| Tang, Sijian 2016 IEEE 57th Annual Symposium on Foundations of Computer Science (FOCS) (2016) New Brunswick, NJ, USA 10.1109/FOCS.2016.77 Cited by (3) \| Cite \| Source \| Open Access
Hellinger volume and number-on-the-forehead communication complexity (journal article) Lee, Troy \| Leonardos, Nikos \| Saks, Michael \| Wang, Fengming Journal of Computer and System Sciences, volume 82, issue 6, pages 1064-1074 (2016). 10.1016/j.jcss.2016.03.005 Cited by (1) \| Cite \| Source \| Open Access
Composition limits and separating examples for some boolean function complexity measures (journal article) Gilmer, Justin \| Saks, Michael \| Srinivasan, Srikanth Combinatorica, volume 36, issue 3, pages 265-311 (2016). 10.1007/s00493-014-3189-x Cited by (11) \| Cite \| Source
Backtracking Based k-SAT Algorithms (book chapter) In Encyclopedia of Algorithms Paturi, Ramamohan \| Pudlák, Pavel \| Saks, Michael \| Zane, Francis Springer New York (2016) 10.1007/978-1-4939-2864-4_45 Cite \| Source
A polylogarithmic space deterministic streaming algorithm for approximating distance to monotonicity (conference) Naumovitz, Timothy \| Saks, Michael Proceedings of the Twenty-Sixth Annual ACM-SIAM Symposium on Discrete Algorithms (2015) 10.1137/1.9781611973730.83 Cited by (5) \| Cite \| Source
A tail bound for read‐ k families of functions (journal article) Gavinsky, Dmitry \| Lovett, Shachar \| Saks, Michael \| Srinivasan, Srikanth Random Structures & Algorithms, volume 47, issue 1, pages 99-108 (2015). 10.1002/rsa.20532 Cited by (20) \| Cite \| Source \| Open Access
A New Approach to the Sensitivity Conjecture (conference) Gilmer, Justin \| Koucký, Michal \| Saks, Michael E. ITCS'15: Innovations in Theoretical Computer Science (2015) Rehovot Israel 10.1145/2688073.2688096 Cited by (10) \| Cite \| Source
Backtracking Based k-SAT Algorithms (book chapter) In Encyclopedia of Algorithms Paturi, Ramamohan \| Pudlák, Pavel \| Saks, Michael \| Zane, Francis Springer US (2015) 10.1007/978-3-642-27848-8_45-2 Cite \| Source

Title	Investigators	Year	Expiration	Amount
AF: Small: Efficient Approximations for Dynamic Programs and Other Topics in Algorithms	Saks, Michael	09-01-2012	08-31-2016	$400,000
Collaborative Research: Understanding, Coping with, and Benefiting from, Intractability	Allender, Eric \| Szegedy, Mario \| Saks, Michael	08-15-2008	07-31-2014	$1,496,023
Investigations in Concrete Complexity and Truthful Mechanism Design	Saks, Michael	07-01-2005	06-30-2009	$200,000
ITR: Project on Strengths and Limitations of Quantum Information Processing	Saks, Michael	08-15-2000	07-31-2002	$54,215
Further Studies in Complexity and Algorithms	Saks, Michael	08-15-2000	07-31-2004	$275,013
DIMACS Special Year on Computational Intractability	Roberts, Fred \| Saks, Michael	09-15-1999	08-31-2001	$252,734
Studies in Computational Complexity	Saks, Michael	06-01-1997	05-31-2001	$174,779
Deciding Compensation for Non-Economic Damages	Hart, Allen \| Saks, Michael \| Wissler, Roselle	05-01-1995	04-30-1998	$53,941
Studies in Concrete Complexity	Saks, Michael	07-01-1993	06-30-1997	$186,500
Coping with Complexity: A Workshop at UCSD January 15-19, 1990 and January 22-24, 1990	Papadimitriou, Christos \| Saks, Michael	09-15-1989	08-31-1990	$10,000
The Complexity of Dynamic Data Structures	Saks, Michael	08-01-1989	07-31-1993	$184,896
Mathematical Sciences: Some Combinatorial Investigations Arising From Theoretical Computer Science	Saks, Michael	06-01-1987	05-31-1990	$43,200
Subset Collections Exhibiting Various Duality Properties	Saks, Michael	06-01-1981	11-30-1983	$17,158