Michael E. Saks

Orcid: 0000-0003-1659-7190

Affiliations:
  • Rutgers University, Department of Mathematics


According to our database1, Michael E. Saks authored at least 155 papers between 1979 and 2024.

Collaborative distances:
  • Dijkstra number2 of three.
  • Erdős number3 of one.

Timeline

Legend:

Book 
In proceedings 
Article 
PhD thesis 
Dataset
Other 

Links

Online presence:

On csauthors.net:

Bibliography

2024
Nearly Optimal List Labeling.
CoRR, 2024

Almost Linear Size Edit Distance Sketch.
Proceedings of the 56th Annual ACM Symposium on Theory of Computing, 2024

Local Enumeration and Majority Lower Bounds.
Proceedings of the 39th Computational Complexity Conference, 2024

2023
Simple, deterministic, fast (but weak) approximations to edit distance and Dyck edit distance.
Proceedings of the 2023 ACM-SIAM Symposium on Discrete Algorithms, 2023

2022
On Randomized Reductions to the Random Strings.
Electron. Colloquium Comput. Complex., 2022

2020
On the discrepancy of random matrices with many columns.
Random Struct. Algorithms, 2020

Approximating Edit Distance Within Constant Factor in Truly Sub-quadratic Time.
J. ACM, 2020

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

Constant factor approximations to edit distance on far input pairs in nearly linear time.
Proceedings of the 52nd Annual ACM SIGACT Symposium on Theory of Computing, 2020

Circuit Lower Bounds from NP-Hardness of MCSP Under Turing Reductions.
Proceedings of the 35th Computational Complexity Conference, 2020

2019
On Online Labeling with Large Label Set.
SIAM J. Discret. Math., 2019

2018
Tight Bound on the Number of Relevant Variables in a Bounded degree Boolean function.
CoRR, 2018

Lower Bounds for Combinatorial Algorithms for Boolean Matrix Multiplication.
Proceedings of the 35th Symposium on Theoretical Aspects of Computer Science, 2018

Online Labeling: Algorithms, Lower Bounds and Open Questions.
Proceedings of the Computer Science - Theory and Applications, 2018

2017
A Communication Game Related to the Sensitivity Conjecture.
Theory Comput., 2017

Estimating the Longest Increasing Sequence in Polylogarithmic Time.
SIAM J. Comput., 2017

Towards an algebraic natural proofs barrier via polynomial identity testing.
Electron. Colloquium Comput. Complex., 2017

Accurate and Nearly Optimal Sublinear Approximations to Ulam Distance.
Proceedings of the Twenty-Eighth Annual ACM-SIAM Symposium on Discrete Algorithms, 2017

2016
Backtracking Based <i>k</i>-SAT Algorithms.
Encyclopedia of Algorithms, 2016

Hellinger volume and number-on-the-forehead communication complexity.
J. Comput. Syst. Sci., 2016

Noisy population recovery in polynomial time.
Electron. Colloquium Comput. Complex., 2016

Composition limits and separating examples for some boolean function complexity measures.
Comb., 2016

2015
Tight Lower Bounds for the Online Labeling Problem.
SIAM J. Comput., 2015

A tail bound for read-<i>k</i> families of functions.
Random Struct. Algorithms, 2015

Efficient indexing of necklaces and irreducible polynomials over finite fields.
Electron. Colloquium Comput. Complex., 2015

Special issue "Conference on Computational Complexity 2014" Guest Editor's Foreword.
Comput. Complex., 2015

A polylogarithmic space deterministic streaming algorithm for approximating distance to monotonicity.
Proceedings of the Twenty-Sixth Annual ACM-SIAM Symposium on Discrete Algorithms, 2015

A New Approach to the Sensitivity Conjecture.
Proceedings of the 2015 Conference on Innovations in Theoretical Computer Science, 2015

2014
The Power of Super-logarithmic Number of Players.
Electron. Colloquium Comput. Complex., 2014

2013
On the practically interesting instances of MAXCUT.
Proceedings of the 30th International Symposium on Theoretical Aspects of Computer Science, 2013

Space efficient streaming algorithms for the distance to monotonicity and asymmetric edit distance.
Proceedings of the Twenty-Fourth Annual ACM-SIAM Symposium on Discrete Algorithms, 2013

On Randomized Online Labeling with Polynomially Many Labels.
Proceedings of the Automata, Languages, and Programming - 40th International Colloquium, 2013

A Polynomial Time Algorithm for Lossy Population Recovery.
Proceedings of the 54th Annual IEEE Symposium on Foundations of Computer Science, 2013

2012
A Tail Bound for Read-k Families of Functions.
Electron. Colloquium Comput. Complex., 2012

Clustering is difficult only when it does not matter
CoRR, 2012

On Online Labeling with Polynomially Many Labels.
Proceedings of the Algorithms - ESA 2012, 2012

2011
The Dual BKR Inequality and Rudich's Conjecture.
Comb. Probab. Comput., 2011

An Online Algorithm for a Problem in Scheduling with Set-ups and Release Times.
Algorithmica, 2011

2010
Rounds vs. Queries Tradeoff in Noisy Computation.
Theory Comput., 2010

Local Monotonicity Reconstruction.
SIAM J. Comput., 2010

Lower Bounds on the Randomized Communication Complexity of Read-Once Functions.
Comput. Complex., 2010

Local Property Reconstruction and Monotonicity.
Proceedings of the Property Testing - Current Research and Surveys, 2010

2009
The unlabelled speed of a hereditary graph property.
J. Comb. Theory B, 2009

2008
Backtracking Based k-SAT Algorithms.
Proceedings of the Encyclopedia of Algorithms - 2008 Edition, 2008

Lower Bounds for the Noisy Broadcast Problem.
SIAM J. Comput., 2008

Minimizing Disjunctive Normal Form Formulas and AC<sup>0</sup> Circuits Given a Truth Table.
SIAM J. Comput., 2008

Approximation algorithms for problems in scheduling with set-ups.
Discret. Appl. Math., 2008

Online multicast with egalitarian cost sharing.
Proceedings of the SPAA 2008: Proceedings of the 20th Annual ACM Symposium on Parallelism in Algorithms and Architectures, 2008

Parallel monotonicity reconstruction.
Proceedings of the Nineteenth Annual ACM-SIAM Symposium on Discrete Algorithms, 2008

2007
Probabilistic strategies for the partition and plurality problems.
Random Struct. Algorithms, 2007

2006
A localization inequality for set functions.
J. Comb. Theory A, 2006

Competitive auctions.
Games Econ. Behav., 2006

The Non-Crossing Graph.
Electron. J. Comb., 2006

Minimizing DNF Formulas and AC<sup>0</sup><sub>d</sub> Circuits Given a Truth Table.
Proceedings of the 21st Annual IEEE Conference on Computational Complexity (CCC 2006), 2006

2005
A parallel search game.
Random Struct. Algorithms, 2005

An improved exponential-time algorithm for <i>k</i>-SAT.
J. ACM, 2005

Minimizing DNF Formulas and AC0 Circuits Given a Truth Table
Electron. Colloquium Comput. Complex., 2005

Every decision tree has an influential variable
CoRR, 2005

Three Optimal Algorithms for Balls of Three Colors.
Proceedings of the STACS 2005, 2005

Rounds vs queries trade-off in noisy computation.
Proceedings of the Sixteenth Annual ACM-SIAM Symposium on Discrete Algorithms, 2005

Weak monotonicity suffices for truthfulness on convex domains.
Proceedings of the Proceedings 6th ACM Conference on Electronic Commerce (EC-2005), 2005

Every decision tree has an in.uential variable.
Proceedings of the 46th Annual IEEE Symposium on Foundations of Computer Science (FOCS 2005), 2005

2004
A lower bound on the quantum query complexity of read-once functions.
J. Comput. Syst. Sci., 2004

A Lower Bound On The Integrality Gap For Minimum Multicut In Directed Networks.
Comb., 2004

Multicolour Turán problems.
Adv. Appl. Math., 2004

A Lower Bound on the Competitive Ratio of Truthful Auctions.
Proceedings of the STACS 2004, 2004

2003
Time-space trade-off lower bounds for randomized computation of decision problems.
J. ACM, 2003

The Euclidean Distortion of Complete Binary Trees.
Discret. Comput. Geom., 2003

Complexity of some arithmetic problems for binary polynomials.
Comput. Complex., 2003

Optimal Separation of EROW and CROWPRAMs.
Proceedings of the 18th Annual IEEE Conference on Computational Complexity (Complexity 2003), 2003

Quantum query complexity and semi-definite programming.
Proceedings of the 18th Annual IEEE Conference on Computational Complexity (Complexity 2003), 2003

2002
On list update and work function algorithms.
Theor. Comput. Sci., 2002

Lower Bounds for Leader Election and Collective Coin-Flipping in the Perfect Information Model.
SIAM J. Comput., 2002

The Efficiency of Resolution and Davis--Putnam Procedures.
SIAM J. Comput., 2002

Kleitman and combinatorics.
Discret. Math., 2002

Space lower bounds for distance approximation in the data stream model.
Proceedings of the Proceedings on 34th Annual ACM Symposium on Theory of Computing, 2002

2001
Time-Space Tradeoffs for Branching Programs.
J. Comput. Syst. Sci., 2001

A Lower Bound for Primality.
J. Comput. Syst. Sci., 2001

Sample Spaces with Small Bias on Neighborhoods and Error-Correcting Communication Protocols.
Algorithmica, 2001

2000
Wait-Free k-Set Agreement is Impossible: The Topology of Public Knowledge.
SIAM J. Comput., 2000

A Decomposition Theorem for Task Systems and Bounds for Randomized Server Problems.
SIAM J. Comput., 2000

Low discrepancy sets yield approximate min-wise independent permutation families.
Inf. Process. Lett., 2000

Super-Linear Time-Space Tradeoff Lower Bounds for Randomized Computation
Electron. Colloquium Comput. Complex., 2000

Exponential lower bounds for depth three Boolean circuits.
Comput. Complex., 2000

A Dual Version of Reimer's Inequality and a Proof of Rudich's Conjecture.
Proceedings of the 15th Annual IEEE Conference on Computational Complexity, 2000

1999
Products and Help Bits in Decision Trees.
SIAM J. Comput., 1999

BP <sub>H</sub>Space(S) subseteq DSPACE(S<sup>3/2</sup>).
J. Comput. Syst. Sci., 1999

Optimal Space Distributed Order-Preserving Lists.
J. Algorithms, 1999

1998
Explicit OR-Dispersers with Polylogarithmic Degree.
J. ACM, 1998

Trees and Euclidean Metrics.
Proceedings of the Thirtieth Annual ACM Symposium on the Theory of Computing, 1998

On the Complexity of Unsatisfiability Proofs for Random <i>k</i>-CNF Formulas.
Proceedings of the Thirtieth Annual ACM Symposium on the Theory of Computing, 1998

1997
Size-Depth Tradeoffs for Threshold Circuits.
SIAM J. Comput., 1997

Efficient Construction of a Small Hitting Set for Combinatorial Rectangles in High Dimension.
Comb., 1997

Exponential Lower Bounds for Depth 3 Boolean Circuits.
Proceedings of the Twenty-Ninth Annual ACM Symposium on the Theory of Computing, 1997

1996
Witness Sets for Families of Binary Vectors.
J. Comb. Theory A, 1996

Local Management of a Global Resource in a Communication Network.
J. ACM, 1996

Randomized Robot Navigation Algorithms.
Proceedings of the Seventh Annual ACM-SIAM Symposium on Discrete Algorithms, 1996

Discrepancy Sets and Pseudorandom Generators for Combinatorial Rectangles.
Proceedings of the 37th Annual Symposium on Foundations of Computer Science, 1996

Randomization and Derandomization in Space_Bounded Computation.
Proceedings of the Eleveth Annual IEEE Conference on Computational Complexity, 1996

1995
On the bandwidth of triangulated triangles.
Discret. Math., 1995

Explicit dispersers with polylog degree.
Proceedings of the Twenty-Seventh Annual ACM Symposium on Theory of Computing, 1995

RSPACE(S) \subseteq DSPACE(S<sup>3/2</sup>).
Proceedings of the 36th Annual Symposium on Foundations of Computer Science, 1995

1994
Approximating Threshold Circuits by Rational Functions
Inf. Comput., August, 1994

A Complexity Index for Satisfiability Problems.
SIAM J. Comput., 1994

Non-Deterministic Communication Complexity with Few Witnesses.
J. Comput. Syst. Sci., 1994

1993
The Number of Distinct Subset Sums of a Finite Set of Vectors.
J. Comb. Theory A, 1993

Communication Complexity and Combinatorial Lattice Theory.
J. Comput. Syst. Sci., 1993

Combinatorial characterization of read-once formulae.
Discret. Math., 1993

Correlation inequalities and a conjecture for permanents.
Comb., 1993

Low diameter graph decompositions.
Comb., 1993

Size-depth trade-offs for threshold circuits.
Proceedings of the Twenty-Fifth Annual ACM Symposium on Theory of Computing, 1993

Sphere Packing and Local Majorities in Graphs.
Proceedings of the Second Israel Symposium on Theory of Computing Systems, 1993

1992
An Optimal On-Line Algorithm for Metrical Task System.
J. ACM, 1992

Sharpening the LYM inequality.
Comb., 1992

Adapting to Asynchronous Dynamic Networks (Extended Abstract)
Proceedings of the 24th Annual ACM Symposium on Theory of Computing, 1992

A Decomposition Theorem and Bounds for Randomized Server Problems
Proceedings of the 33rd Annual Symposium on Foundations of Computer Science, 1992

Non-deterministic Communication Complexity with Few Witness.
Proceedings of the Seventh Annual Structure in Complexity Theory Conference, 1992

1991
On computing majority by comparisons.
Comb., 1991

Optimal Time Randomized Consensus - Making Resilient Algorithms Fast in Practice.
Proceedings of the Second Annual ACM/SIGACT-SIAM Symposium on Discrete Algorithms, 1991

Decomposing Graphs into Regions of Small Diameter.
Proceedings of the Second Annual ACM/SIGACT-SIAM Symposium on Discrete Algorithms, 1991

Optimal Space Distributed Move-to-Front Lists.
Proceedings of the Tenth Annual ACM Symposium on Principles of Distributed Computing, 1991

1990
On Threshold Circuits for Parity
Proceedings of the 31st Annual Symposium on Foundations of Computer Science, 1990

A Dining Philosophers Algorithm with Polynomial Response Time
Proceedings of the 31st Annual Symposium on Foundations of Computer Science, 1990

On Threshold Circuits for Parity (Abstract).
Proceedings of the Third Annual Workshop on Computational Learning Theory, 1990

1989
A Robust Noncryptographic Protocol for Collective Coin Flipping.
SIAM J. Discret. Math., 1989

The periodic balanced sorting network.
J. ACM, 1989

An on-line graph coloring algorithm with sublinear performance ratio.
Discret. Math., 1989

Some extremal problems arising form discrete control processes.
Comb., 1989

A dynamic location problem for graphs.
Comb., 1989

The Cell Probe Complexity of Dynamic Data Structures
Proceedings of the 21st Annual ACM Symposium on Theory of Computing, 1989

1988
A Limit Theorem for (min, +) Matrix Multiplication.
Math. Oper. Res., 1988

An intersection problem for finite automata.
Discret. Appl. Math., 1988

Lattices, Möbius Functions and Communication Complexity
Proceedings of the 29th Annual Symposium on Foundations of Computer Science, 1988

1987
Subgraphs of large connectivity and chromatic number in graphs of large chromatic number.
J. Graph Theory, 1987

Every finite distributive lattice is a set of stable matchings for a small stable marriage instance.
J. Comb. Theory A, 1987

On the widths of finite distributive lattices.
Discret. Math., 1987

The smallets n-uniform hypergraph with positive discrepancy.
Comb., 1987

Imperfect Random Sources and Discrete Controlled Processes
Proceedings of the 19th Annual ACM Symposium on Theory of Computing, 1987

An Optimal Online Algorithm for Metrical Task Systems
Proceedings of the 19th Annual ACM Symposium on Theory of Computing, 1987

Detecting Global Termination Conditions in the Face of Uncertainty.
Proceedings of the Sixth Annual ACM Symposium on Principles of Distributed Computing, 1987

1986
Maximum induced trees in graphs.
J. Comb. Theory B, 1986

Some sequences associated with combinatorial structures.
Discret. Math., 1986

Probabilistic Boolean Decision Trees and the Complexity of Evaluating Game Trees
Proceedings of the 27th Annual Symposium on Foundations of Computer Science, 1986

On a Search Problem Related to Branch-and-Bound Procedures
Proceedings of the 27th Annual Symposium on Foundations of Computer Science, 1986

1985
Every Poset Has a Central Element.
J. Comb. Theory A, 1985

Searching Ordered Structures.
J. Algorithms, 1985

1984
A topological approach to evasiveness.
Comb., 1984

A polyomino with no stochastic function.
Comb., 1984

Every Poset Has a Good Comparison
Proceedings of the 16th Annual ACM Symposium on Theory of Computing, April 30, 1984

1983
Largest digraphs contained in all n-tournaments.
Comb., 1983

The Balanced Sorting Network.
Proceedings of the Second Annual ACM Symposium on Principles of Distributed Computing, 1983

Information Bounds Are Good for Search Problems on Ordered Data Structures
Proceedings of the 24th Annual Symposium on Foundations of Computer Science, 1983

1980
Dilworth Numbers, Incidence Maps and Product Partial Orders.
SIAM J. Algebraic Discret. Methods, 1980

Product partial orders with the sperner property.
Discret. Math., 1980

1979
Group labelings of graphs.
J. Graph Theory, 1979


  Loading...