Michael Saks | Academic Influence

Michael Saks 's AcademicInfluence.com Rankings

Michael Saks

Mathematics

#4174

World Rank

#5985

Historical Rank

#1467

USA Rank

Measure Theory

#2362

World Rank

#2824

Historical Rank

#668

USA Rank

mathematics Degrees

Download Badge

Mathematics

Michael Saks 's Degrees

PhD Mathematics Princeton University
Bachelors Mathematics Princeton University

Similar Degrees You Can Earn

Best Online Bachelor's in Math 2025

Why Is Michael Saks Influential?

(Suggest an Edit or Addition)

According to Wikipedia, Michael Ezra Saks is an American mathematician. He is currently the Department Chair of the Mathematics Department at Rutgers University and from 2006 until 2010 was director of the Mathematics Graduate Program at Rutgers University. Saks received his Ph.D. from the Massachusetts Institute of Technology in 1980 after completing his dissertation titled Duality Properties of Finite Set Systems under his advisor Daniel J. Kleitman.

(See a Problem?)

Michael Saks 's Published Works

Number of citations in a given year to any of this author's works

Total number of citations to an author for the works they published in a given year. This highlights publication of the most important work(s) by the author

Published Works

Wait-free k-set agreement is impossible: the topology of public knowledge (1993) (383)
The cell probe complexity of dynamic data structures (1989) (382)
An optimal on-line algorithm for metrical task system (1992) (338)
An improved exponential-time algorithm for k-SAT (1998) (329)
Competitive auctions (2006) (244)
An optimal online algorithm for metrical task systems (1987) (238)
Probabilistic Boolean decision trees and the complexity of evaluating game trees (1986) (205)
Weak monotonicity suffices for truthfulness on convex domains (2005) (199)
Low diameter graph decompositions (1993) (177)
An on-line graph coloring algorithm with sublinear performance ratio (1989) (155)
Orthogonal representations and connectivity of graphs (1989) (129)
Every decision tree has an influential variable (2005) (121)
Lattices, mobius functions and communications complexity (1988) (120)
The periodic balanced sorting network (1989) (119)
Space lower bounds for distance approximation in the data stream model (2002) (115)
The Efficiency of Resolution and Davis--Putnam Procedures (2002) (112)
A topological approach to evasiveness (1983) (107)
On the complexity of unsatisfiability proofs for random k-CNF formulas (1998) (107)
Maximum induced trees in graphs (1986) (100)
Time-space tradeoffs for branching programs (1998) (92)
Quantum query complexity and semi-definite programming (2003) (92)
Optimal time randomized consensus—making resilient algorithms fast in practice (1991) (91)
Balancing poset extensions (1984) (87)
Approximating Edit Distance within Constant Factor in Truly Sub-Quadratic Time (2018) (87)
Time-space trade-off lower bounds for randomized computation of decision problems (2003) (86)
Slicing the hypercube (1993) (83)
Sphere packing and local majorities in graphs (1993) (76)
Covering Regions by Rectangles (1981) (76)
Size-Depth Tradeoffs for Threshold Circuits (1997) (74)
On computing majority by comparisons (1991) (74)
On the cover time of random walks on graphs (1989) (72)
A dining philosophers algorithm with polynomial response time (1990) (71)
Decomposing graphs into regions of small diameter (1991) (69)
Searching Ordered Structures (1985) (69)
BP H SPACE(S)⊆DSPACE(S 3/2 ) (1999) (66)
A Robust Noncryptographic Protocol for Collective Coin Flipping (1989) (64)
A lower bound on the quantum query complexity of read-once functions (2001) (64)
Local management of a global resource in a communication network (1987) (63)
Randomization and derandomization in space-bounded computation (1996) (63)
Efficient construction of a small hitting set for combinatorial rectangles in high dimension (1993) (61)
Lower bounds for the noisy broadcast problem (2005) (61)
Communication Complexity and Combinatorial Lattice Theory (1993) (56)
Randomized robot navigation algorithms (1996) (55)
Adapting to asynchronous dynamic networks (extended abstract) (1992) (53)
A Dynamic location problem for graphs (1989) (53)
Online multicast with egalitarian cost sharing (2008) (53)
Minimizing Disjunctive Normal Form Formulas and AC0 Circuits Given a Truth Table (2008) (53)
Combinatorial characterization of read-once formulae (1993) (52)
Some extremal problems arising from discrete control processes (1989) (52)
A correction: orthogonal representations and connectivity of graphs (2000) (50)
A Complexity Index for Satisfiability Problems (1994) (50)
Local Monotonicity Reconstruction (2010) (49)
Super-linear time-space tradeoff lower bounds for randomized computation (2000) (48)
A short proof of the existence of k-saturated partitions of partially ordered sets (1979) (47)
Every Poset Has a Central Element (1985) (46)
Lower bounds for leader election and collective coin-flipping in the perfect information model (1999) (46)
Quantum Decision Trees and Semidefinite Programming. (2001) (46)
A dual version of Reimer's inequality and a proof of Rudich's conjecture (2000) (46)
Discrepancy sets and pseudorandom generators for combinatorial rectangles (1996) (44)
Adapting to Asynchronous Dynamic Networks (1992) (44)
Combinatorial representation and convex dimension of convex geometries (1988) (43)
The balanced sorting network (1983) (42)
Approximating Threshold Circuits by Rational Functions (1994) (42)
On threshold circuits for parity (1990) (42)
Products and help bits in decision trees (1994) (41)
Constant factor approximations to edit distance on far input pairs in nearly linear time (2019) (40)
Estimating the Longest Increasing Sequence in Polylogarithmic Time (2010) (39)
A decomposition theorem and bounds for randomized server problems (1992) (39)
A tail bound for read‐k families of functions (2012) (38)
Dynamic Search in Graphs (1987) (37)
Product partial orders with the sperner property (1980) (36)
Space efficient streaming algorithms for the distance to monotonicity and asymmetric edit distance (2012) (34)
Every finite distributive lattice is a set of stable matchings for a small stable marriage instance (1987) (34)
On the practically interesting instances of MAXCUT (2012) (32)
Clustering is difficult only when it does not matter (2012) (32)
Towards an algebraic natural proofs barrier via polynomial identity testing (2017) (31)
A Decomposition Theorem for Task Systems and Bounds for Randomized Server Problems (2000) (31)
A Lower Bound On The Integrality Gap For Minimum Multicut In Directed Networks (2004) (31)
BPHSPACE ( S ) ⊆ DSPACE ( S 3 / 2 ) ∗ (1999) (30)
Composition limits and separating examples for some boolean function complexity measures (2013) (30)
A Polynomial Time Algorithm for Lossy Population Recovery (2013) (29)
Minimizing DNF Formulas and AC0 Circuits Given a Truth Table (2005) (28)
On the bandwidth of triangulated triangles (1995) (27)
On a search problem related to branch-and-bound procedures (1986) (27)
Explicit OR-dispersers with polylogarithmic degree (1998) (26)
Size-depth trade-offs for threshold circuits (1993) (26)
Witness Sets for Families of Binary Vectors (1996) (24)
Explicit dispersers with polylog degree (1995) (24)
Detecting global termination conditions in the face of uncertainty (1987) (24)
A Lower Bound on the Competitive Ratio of Truthful Auctions (2004) (24)
Some sequences associated with combinatorial structures (1986) (23)
Non-deterministic communication complexity with few witnesses (1992) (23)
Low Discrepancy Sets Yield Approximate Min-Wise Independent Permutation Families (1999) (23)
The unlabelled speed of a hereditary graph property (2009) (22)
Dilworth Numbers, Incidence Maps and Product Partial Orders (1980) (22)
A lower bound for primality (1999) (22)
An Asymptotically Tight Bound on the Number of Relevant Variables in a Bounded Degree Boolean function (2018) (21)
A New Approach to the Sensitivity Conjecture (2015) (20)
Parallel monotonicity reconstruction (2008) (19)
Minimizing DNF formulas and AC/sup 0//sub d/ circuits given a truth table (2006) (19)
Multicolour Turán problems (2004) (19)
Subgraphs of large connectivity and chromatic number in graphs of large chromatic number (1987) (19)
Lower Bounds on the Randomized Communication Complexity of Read-Once Functions (2009) (18)
Tight lower bounds for the online labeling problem (2011) (18)
Correlation inequalities and a conjecture for permanents (1993) (18)
Exponential lower bounds for depth three Boolean circuits (2000) (17)
Accurate and Nearly Optimal Sublinear Approximations to Ulam Distance (2017) (16)
Trees and Euclidean metrics (1998) (16)
The Euclidean Distortion of Complete Binary Trees (2002) (16)
Exponential lower bounds for depth 3 Boolean circuits (1997) (16)
Noisy Population Recovery in Polynomial Time (2016) (15)
Largest digraphs contained in alln-tournaments (1983) (15)
On the discrepancy of random matrices with many columns (2018) (14)
The Information Theoretic Bound for Problems on Ordered Sets and Graphs (1985) (13)
Low distortion euclidean embeddings of trees (1998) (13)
Set Orderings Requiring Costliest Alphabetic Binary Trees (1981) (13)
Efficient Indexing of Necklaces and Irreducible Polynomials over Finite Fields (2014) (13)
A polylogarithmic space deterministic streaming algorithm for approximating distance to monotonicity (2015) (12)
The Power of Super-logarithmic Number of Players (2014) (12)
The Dual BKR Inequality and Rudich's Conjecture (2010) (12)
Information bounds are good for search problems on ordered data structures (1983) (12)
Three Optimal Algorithms for Balls of Three Colors (2005) (11)
Probabilistic strategies for the partition and plurality problems (2007) (11)
Every poset has a good comparison (1984) (10)
Sharpening the LYM inequality (1992) (10)
An Online Algorithm for a Problem in Scheduling with Set-ups and Release Times (2011) (10)
The smallestn-uniform hypergraph with positive discrepancy (1987) (10)
Imperfect random sources and discrete controlled processes (1987) (10)
A parallel search game (2005) (10)
Rounds vs queries trade-off in noisy computation (2005) (9)
On Online Labeling with Polynomially Many Labels (2012) (9)
ON FKG-TYPE AND PERMANENTAL INEQUALITIES (1992) (8)
Circuit lower bounds from NP-hardness of MCSP under turing reductions (2020) (7)
omization and Derandomization in Space-Bounded Computation (1996) (7)
On Randomized Online Labeling with Polynomially Many Labels (2013) (7)
Approximation algorithms for problems in scheduling with set-ups (2008) (7)
A limit theorem for sets of stochastic matrices (2004) (6)
Complexity of some arithmetic problems for binary polynomials (2004) (5)
Optimal space distributed move-to-front lists (1991) (5)
Kleitman and combinatorics (2002) (5)
Group labelings of graphs (1979) (4)
Time-space Tradeoos for Branching Programs (1998) (4)
A Class of Perfect Graphs Associated with Planar Rectilinear Regions (1982) (3)
A Limit Theorem for (min, +) Matrix Multiplication (1988) (3)
A Communication Game Related to the Sensitivity Conjecture (2015) (3)
Largest induced suborders satisfying the chain condition (1985) (3)
On the widths of finite distributive lattices (1987) (3)
Information theory methods in communication complexity (2012) (3)
Composition limits and separating examples for some boolean function complexity measures (2016) (3)
A localization inequality for set functions (2006) (3)
Games and Economic Behavior (2006) (3)
Lower Bounds for Combinatorial Algorithms for Boolean Matrix Multiplication (2018) (2)
On list update and work function algorithms (1999) (2)
Proceedings of the Eighth Annual ACM-SIAM Symposium on Discrete Algorithms, 5-7 January 1997, New Orleans, Louisiana, USA (1997) (2)
On Online Labeling with Large Label Set (2019) (2)
Sphere Packing and Local (1993) (2)
RSPACE(S) \subseteq DSPACE(S3/2) (1995) (2)
On randomized reductions to the random strings (2022) (1)
Optimal separation of EROW and CROW PRAMs (2003) (1)
On threshold circuits for parity (abstract) (1990) (1)
Optimal Space Distributed Order-Preserving Lists (1999) (1)
Discrete Localization and Correlation Inequalities for Set Functions (2003) (1)
An Asymptotically Tight Bound on the Number of Relevant Variables in a Bounded Degree Boolean function (2020) (1)
An intersection problem for finite automata (1988) (1)
8 concluding remarks. (2007) (1)
Online Labeling: Algorithms, Lower Bounds and Open Questions (2018) (1)
RSPACE(S) contained as a subset within DSPACE(S3/2) (1995) (0)
8 Using and Abusing Variables (2015) (0)
Selected papers of the 23rd annual ACM symposium on Theory of computing (1995) (0)
Backtracking Based k-SAT Algorithms (2008) (0)
8. Concluding Remarks by Deenition of the Vectors E (1995) (0)
On the Complexity of Some Arithmetic Problems over IF 2 [ T ] (0)
North-Holland 245 SECT (2001) (0)
Distributed data structures and wait-free computation (1993) (0)
Mathematisches Forschungsinstitut Oberwolfach Proving Hard-core Predicates Using List Decoding Proving Integrality Gaps without Knowing the Linear Program How to Go beyond the Black-box Simulation Barrier Derandomization in Cryptography Formula Caching Proof Systems Algebras of Minimal Rank over Arb (2003) (0)
Hellinger volume and number-on-the-forehead communication complexity (2014) (0)
An example using the well-ordering principle (2005) (0)
Lower Bounds for the Noisy Broadcast Problem Extended Abstract (2005) (0)
RSPACE(S)/spl sube/DSPACE(S/sup 3/2/) (1995) (0)
TWO PROBLEMS IN NOISE TOLERANT COMPUTING (2018) (0)
Analyzing the game of Pan via a game-theoretic and computational approach (2015) (0)
Now We Look at the 2-dimensional Layout of M (1994) (0)
Simple, deterministic, fast (but weak) approximations to edit distance and Dyck edit distance (2023) (0)
Reducing randomness in computation via explicit constructions (1996) (0)
Sample Spaces with Small Bias on Neighborhoods and Error-Correcting Communication Protocols (1997) (0)
The Non-Crossing Graph (2006) (0)
Small Deviations of Sums of Random Variables by Brian Garnett Dissertation Director : Swastik Kopparty (2016) (0)
A Tutorial on Algebraic Topology and Distributed Computation Version of December 13, 1994 (1994) (0)
Algorithmic applications to social networks, secretary problems and differential privacy (2011) (0)
Unsolved problems (1985) (0)
Information theoretic limitations on computation (2005) (0)
A Statistical Procedure for Cluster Recognition with Application to Atlanta Leukemia‐Lymphoma Data (1983) (0)
A polyomino with no stochastic function (1984) (0)
Special issue “Conference on Computational Complexity 2014” Guest Editor’s Foreword (2015) (0)
Session details: Session 11A (2002) (0)
Special issue “Conference on Computational Complexity 2014” Guest Editor’s Foreword (2015) (0)
Local Property Reconstruction and Monotonicity (2010) (0)
11 Mathematical Induction In philosophy (2015) (0)
The Number of Distinct Subset Sums of a Finite Set of Vectors (1993) (0)
On the rational relationships among pseudo-roots of a non-commutative polynomial (2020) (0)

This paper list is powered by the following services:

Other Resources About Michael Saks

en.wikipedia.org

What Schools Are Affiliated With Michael Saks ?

Michael Saks is affiliated with the following schools: