Search filters

List of works by Michael Saks

A lower bound on the quantum query complexity of read-once functions

scientific article published in September 2004

A topological approach to evasiveness

An improved exponential-time algorithm for k-SAT

scientific article published in May 2005

An optimal on-line algorithm for metrical task system

scientific article (publication date: October 1992)

Low discrepancy sets yield approximate min-wise independent permutation families

Maximum induced trees in graphs

On the complexity of unsatisfiability proofs for random k-CNF formulas

article

Probabilistic Boolean decision trees and the complexity of evaluating game trees

Probabilistic strategies for the partition and plurality problems

scholarly article by Zdeněk Dvořák et al published 2006 in Random Structures and Algorithms

The Efficiency of Resolution and Davis--Putnam Procedures

Wait-Free k-Set Agreement is Impossible: The Topology of Public Knowledge

Paulina is supported by:

About Paulina

Help