Michael E. Saks

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

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

Timeline

Legend:

Book 
In proceedings 
Article 
PhD thesis 
Other 

Links

Homepages:

On csauthors.net:

Bibliography

2018
Approximating Edit Distance Within Constant Factor in Truly Sub-Quadratic Time.
CoRR, 2018

Lower bounds for Combinatorial Algorithms for Boolean Matrix Multiplication.
CoRR, 2018

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

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

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

Towards an algebraic natural proofs barrier via polynomial identity testing.
Electronic Colloquium on Computational Complexity (ECCC), 2017

Towards an algebraic natural proofs barrier via polynomial identity testing.
CoRR, 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 k-SAT Algorithms.
Encyclopedia of Algorithms, 2016

Efficient Indexing of Necklaces and Irreducible Polynomials over Finite Fields.
Theory of Computing, 2016

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

Noisy population recovery in polynomial time.
Electronic Colloquium on Computational Complexity (ECCC), 2016

Noisy population recovery in polynomial time.
CoRR, 2016

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

Noisy Population Recovery in Polynomial Time.
Proceedings of the IEEE 57th Annual Symposium on Foundations of Computer Science, 2016

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

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

Efficient indexing of necklaces and irreducible polynomials over finite fields.
Electronic Colloquium on Computational Complexity (ECCC), 2015

Efficient indexing of necklaces and irreducible polynomials over finite fields.
CoRR, 2015

A communication game related to the sensitivity conjecture.
CoRR, 2015

Special issue "Conference on Computational Complexity 2014" Guest Editor's Foreword.
Computational Complexity, 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.
Electronic Colloquium on Computational Complexity (ECCC), 2014

Hellinger volume and number-on-the-forehead communication complexity.
CoRR, 2014

Efficient Indexing of Necklaces and Irreducible Polynomials over Finite Fields.
Proceedings of the Automata, Languages, and Programming - 41st International Colloquium, 2014

The Power of Super-logarithmic Number of Players.
Proceedings of the Approximation, 2014

2013
A Polynomial Time Algorithm for Lossy Population Recovery
CoRR, 2013

Estimating the longest increasing sequence in polylogarithmic time.
CoRR, 2013

Composition limits and separating examples for some Boolean function complexity measures.
CoRR, 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

Composition Limits and Separating Examples for Some Boolean Function Complexity Measures.
Proceedings of the 28th Conference on Computational Complexity, 2013

2012
A Tail Bound for Read-k Families of Functions.
Electronic Colloquium on Computational Complexity (ECCC), 2012

On Online Labeling with Polynomially Many Labels
CoRR, 2012

On the practically interesting instances of MAXCUT
CoRR, 2012

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

A Tail Bound for Read-k Families of Functions
CoRR, 2012

Space efficient streaming algorithms for the distance to monotonicity and asymmetric edit distance
CoRR, 2012

Tight lower bounds for the online labeling problem.
Proceedings of the 44th Symposium on Theory of Computing Conference, 2012

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

2011
The Dual BKR Inequality and Rudich's Conjecture.
Combinatorics, Probability & Computing, 2011

Tight lower bounds for online labeling problem
CoRR, 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 of Computing, 2010

Local Monotonicity Reconstruction.
SIAM J. Comput., 2010

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

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

Estimating the Longest Increasing Sequence in Polylogarithmic Time.
Proceedings of the 51th Annual IEEE Symposium on Foundations of Computer Science, 2010

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

Lower bounds on the randomized communication complexity of read-once functions.
Electronic Colloquium on Computational Complexity (ECCC), 2009

Lower Bounds on the Randomized Communication Complexity of Read-Once Functions.
Proceedings of the 24th Annual IEEE Conference on Computational Complexity, 2009

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

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

Minimizing Disjunctive Normal Form Formulas and AC0 Circuits Given a Truth Table.
SIAM J. Comput., 2008

Approximation algorithms for problems in scheduling with set-ups.
Discrete Applied Mathematics, 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, Ser. A, 2006

Competitive auctions.
Games and Economic Behavior, 2006

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

Minimizing DNF Formulas and AC0d 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 k-SAT.
J. ACM, 2005

Minimizing DNF Formulas and AC0 Circuits Given a Truth Table
Electronic Colloquium on Computational Complexity (ECCC), 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

Lower Bounds for the Noisy Broadcast Problem.
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.
Combinatorica, 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.
Discrete & Computational Geometry, 2003

Complexity of some arithmetic problems for binary polynomials.
Computational Complexity, 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

A lower bound on the quantum query complexity of read-once functions
Electronic Colloquium on Computational Complexity (ECCC), 2002

Kleitman and combinatorics.
Discrete Mathematics, 2002

A lower bound on the quantum query complexity of read-once functions
CoRR, 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
Electronic Colloquium on Computational Complexity (ECCC), 2000

Exponential lower bounds for depth three Boolean circuits.
Computational Complexity, 2000

Super-linear time-space tradeoff lower bounds for randomized computation.
Proceedings of the 41st Annual Symposium on Foundations of Computer Science, 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 HSpace(S) subseteq DSPACE(S3/2).
J. Comput. Syst. Sci., 1999

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

A Lower Bound for Primality
Electronic Colloquium on Computational Complexity (ECCC), 1999

Lower Bounds for Leader Election and Collective Coin-Flipping in the Perfect Information Model.
Proceedings of the Thirty-First Annual ACM Symposium on Theory of Computing, 1999

Low Discrepancy Sets Yield Approximate Min-Wise Independent Permutation Families.
Proceedings of the Randomization, 1999

On List Update and Work Function Algorithms.
Proceedings of the Algorithms, 1999

A Lower Bound for Primality.
Proceedings of the 14th Annual IEEE Conference on Computational Complexity, 1999

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

Time-Space Tradeoffs for Branching Programs
Electronic Colloquium on Computational Complexity (ECCC), 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 k-CNF Formulas.
Proceedings of the Thirtieth Annual ACM Symposium on the Theory of Computing, 1998

An Improved Exponential-Time Algorithm for k-SAT.
Proceedings of the 39th Annual Symposium on Foundations of Computer Science, 1998

Time-Space Tradeoffs for Branching Programs.
Proceedings of the 39th Annual Symposium on Foundations of Computer Science, 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.
Combinatorica, 1997

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

Sample Spaces with Small Bias on Neighborhoods and Error-Correcting Communication Protocols.
Proceedings of the Randomization and Approximation Techniques in Computer Science, 1997

1996
Witness Sets for Families of Binary Vectors.
J. Comb. Theory, Ser. 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.
Discrete Mathematics, 1995

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

RSPACE(S) \subseteq DSPACE(S3/2).
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

Products and Help Bits in Decision Trees
Proceedings of the 35th Annual Symposium on Foundations of Computer Science, 1994

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

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

Combinatorial characterization of read-once formulae.
Discrete Mathematics, 1993

Correlation inequalities and a conjecture for permanents.
Combinatorica, 1993

Low diameter graph decompositions.
Combinatorica, 1993

Wait-free k-set agreement is impossible: the topology of public knowledge.
Proceedings of the Twenty-Fifth Annual ACM Symposium on Theory of Computing, 1993

Efficient construction of a small hitting set for combinatorial rectangles in high dimension.
Proceedings of the Twenty-Fifth Annual ACM Symposium on Theory of Computing, 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.
Combinatorica, 1992

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

A Complexity Index for Satisfiability Problems.
Proceedings of the 2nd Integer Programming and Combinatorial Optimization Conference, 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.
Combinatorica, 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. Discrete Math., 1989

The periodic balanced sorting network.
J. ACM, 1989

An on-line graph coloring algorithm with sublinear performance ratio.
Discrete Mathematics, 1989

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

A dynamic location problem for graphs.
Combinatorica, 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.
Discrete Applied Mathematics, 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.
Journal of Graph Theory, 1987

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

On the widths of finite distributive lattices.
Discrete Mathematics, 1987

The smallets n-uniform hypergraph with positive discrepancy.
Combinatorica, 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

Local Management of a Global Resource in a Communication Network
Proceedings of the 28th Annual Symposium on Foundations of Computer Science, 1987

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

Some sequences associated with combinatorial structures.
Discrete Mathematics, 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, Ser. A, 1985

Searching Ordered Structures.
J. Algorithms, 1985

1984
A topological approach to evasiveness.
Combinatorica, 1984

A polyomino with no stochastic function.
Combinatorica, 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.
Combinatorica, 1983

The Balanced Sorting Network.
Proceedings of the Second Annual ACM SIGACT-SIGOPS 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

A Topological Approach to Evasiveness
Proceedings of the 24th Annual Symposium on Foundations of Computer Science, 1983

1980
Dilworth Numbers, Incidence Maps and Product Partial Orders.
SIAM J. Matrix Analysis Applications, 1980

Product partial orders with the sperner property.
Discrete Mathematics, 1980

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


  Loading...