Arrow Research search

Author name cluster

Michael E. Saks

Possible papers associated with this exact author name in Arrow. This page groups case-insensitive exact name matches and is not a full identity disambiguation profile.

49 papers
1 author row

Possible papers

49

FOCS Conference 2024 Conference Paper

Nearly Optimal List Labeling

  • Michael A. Bender
  • Alex Conway 0001
  • Martín Farach-Colton
  • Hanna Komlós
  • Michal Koucký 0001
  • William Kuszmaul
  • Michael E. Saks

The list-labeling problem captures the basic task of storing a dynamically changing set of up to $n$ elements in sorted order in an array of size $m=(1+\Theta(1))n$ • The goal is to support insertions and deletions while moving around elements within the array as little as possible. Until recently, the best known upper bound stood at $O(\log^{2}n)$ amortized cost. This bound, which was first established in 1981, was finally improved two years ago, when a randomized $O(\log^{3/2}n)$ expected-cost algorithm was discovered. The best randomized lower bound for this problem remains $\Omega(\log n)$, and closing this gap is considered to be a major open problem in data structures. In this paper, we present the See-Saw Algorithm, a randomized list-labeling solution that achieves a nearly optimal bound of $O(\log n \text{polyloglog}\ n)$ amortized expected cost. This bound is achieved despite at least three lower bounds showing that this type of result is impossible for large classes of solutions.

Details

FOCS Conference 2018 Conference Paper

Approximating Edit Distance within Constant Factor in Truly Sub-Quadratic Time

  • Diptarka Chakraborty
  • Debarati Das 0001
  • Elazar Goldenberg
  • Michal Koucký 0001
  • Michael E. Saks

Edit distance is a measure of similarity of two strings based on the minimum number of character insertions, deletions, and substitutions required to transform one string into the other. The edit distance can be computed exactly using a dynamic programming algorithm that runs in quadratic time. Andoni, Krauthgamer and Onak (2010) gave a nearly linear time algorithm that approximates edit distance within approximation factor poly(log n). In this paper, we provide an algorithm with running time Õ(n^2-2/7) that approximates the edit distance within a constant factor.

Details

SODA Conference 2017 Conference Paper

Accurate and Nearly Optimal Sublinear Approximations to Ulam Distance

  • Timothy Naumovitz
  • Michael E. Saks
  • C. Seshadhri 0001

The Ulam distance between two permutations of length η is the minimum number of insertions and deletions needed to transform one sequence into the other. Equivalently, the Ulam distance d is n minus the length of the longest common subsequence (LCS) between the permutations. Our main result is an algorithm, that for any fixed ∊ > 0, provides a (1 + ∊)-multiplicative approximation for d in time, which has been shown to be optimal up to polylogarithmic factors. This is the first sublinear time algorithm (provided that d = (log n ) ω(1) ) that obtains arbitrarily good multiplicative approximations to the Ulam distance. The previous best bound is an O (1)-approximation (with a large constant) by Andoni and Nguyen (2010) with the same running time bound (ignoring polylogarithmic factors). The improvement in the approximation factor from O (1) to (1 + ∊) allows for significantly more powerful sublinear algorithms. For example, for any fixed δ > 0, we can get additive δη approximations for the LCS between permutations in time. Previous sublinear algorithms require δ to be at least 1–1 /C, where c is the approximation factor, which is close to 1 when c is large. Our algorithm is obtained by abstracting the basic algorithmic framework of Andoni and Nguyen, and combining it with the sublinear approximations for the longest increasing subsequence by Saks and Seshadhri (2010).

Details

FOCS Conference 2016 Conference Paper

Noisy Population Recovery in Polynomial Time

  • Anindya De
  • Michael E. Saks
  • Sijian Tang

In the noisy population recovery problem of Dvir et al. [6], the goal is to learn an unknown distribution f on binary strings of length n from noisy samples. A noisy sample with parameter μ ∈ [0, 1] is generated by selecting a sample from f, and independently flipping each coordinate of the sample with probability (1-μ)/2. We assume an upper bound k on the size of the support of the distribution, and the goal is to estimate the probability of any string to within some given error ε. It is known that the algorithmic complexity and sample complexity of this problem are polynomially related to each other. We describe an algorithm that for each μ > 0, provides the desired estimate of the distribution in time bounded by a polynomial in k, n and 1/ε improving upon the previous best result of poly(k log log k, n, 1/ε) due to Lovett and Zhang [9]. Our proof combines ideas from [9] with a noise attenuated version of Möbius inversion. The latter crucially uses the robust local inverse construction of Moitra and Saks [11].

Details

FOCS Conference 2013 Conference Paper

A Polynomial Time Algorithm for Lossy Population Recovery

  • Ankur Moitra
  • Michael E. Saks

We give a polynomial time algorithm for the lossy population recovery problem. In this problem, the goal is to approximately learn an unknown distribution on binary strings of length n from lossy samples: for some parameter μ each coordinate of the sample is preserved with probability μ and otherwise is replaced by a `? '. The running time and number of samples needed for our algorithm is polynomial in n and 1/ε for each fixed μ>0. This improves on algorithm of Wigderson and Yehudayoff that runs in quasi-polynomial time for any μ > 0 and the polynomial time algorithm of Dvir et al which was shown to work for μ > rapprox 0. 30 by Batman et al. In fact, our algorithm also works in the more general framework of Batman et al. in which there is no a priori bound on the size of the support of the distribution. The algorithm we analyze is implicit in previous work; our main contribution is to analyze the algorithm by showing (via linear programming duality and connections to complex analysis) that a certain matrix associated with the problem has a robust local inverse even though its condition number is exponentially small. A corollary of our result is the first polynomial time algorithm for learning DNFs in the restriction access model of Dvir et al [9].

Details

FOCS Conference 2010 Conference Paper

Estimating the Longest Increasing Sequence in Polylogarithmic Time

  • Michael E. Saks
  • C. Seshadhri 0001

Finding the length of the longest increasing subsequence (LIS) is a classic algorithmic problem. Let n denote the size of the array. Simple O(n log n) time algorithms are known that determine the LIS exactly. In this paper, we develop a randomized approximation algorithm, that for any constant δ > 0, runs in time polylogarithmic in n and estimates the length of the LIS of an array up to an additive error of δn. The algorithm presented in this extended abstract runs in time (log n) O(1/δ). In the full paper, we will give an improved version of the algorithm with running time (log n) c (1/δ) O(1/δ) where the exponent c is independent of δ. Previously, the best known polylogarithmic time algorithms could only achieve an additive n/2-approximation. Our techniques also yield a fast algorithm for estimating the distance to monotonicity to within a small multiplicative factor. The distance of f to monotonicity, ε f, is equal to 1 - |LIS|/n (the fractional length of the complement of the LIS). For any δ > 0, we give an algorithm with running time O((ε f -1 log n) O(1/δ) ) that outputs a (1 + δ)-multiplicative approximation to ε f. This can be improved so that the exponent is a fixed constant. The previously known polylogarithmic algorithms gave only a 2-approximation.

Details

FOCS Conference 2005 Conference Paper

Every decision tree has an in. uential variable

  • Ryan O'Donnell
  • Michael E. Saks
  • Oded Schramm
  • Rocco A. Servedio

We prove that for any decision tree calculating a Boolean function f: {-1, 1}/sup n/ /spl rarr/ {-1, 1}, Var[f] /spl les/ /spl Sigma/ /sub i=1/ /sup n/ /spl delta//sup i/Inf/sub i/(f), i = 1 where /spl delta//sup i/ is the probability that the ith input variable is read and Inf/sub i/(f) is the influence of the ith variable on f. The variance, influence and probability are taken with respect to an arbitrary product measure on {-1, 1}/sup n/n. It follows that the minimum depth of a decision tree calculating a given balanced function is at least the reciprocal of the largest influence of any input variable. Likewise, any balanced Boolean function with a decision tree of depth d has a variable with influence at least 1/d. The only previous nontrivial lower bound known was /spl Omega/(d2/sup -d/). Our inequality has many generalizations, allowing us to prove influence lower bounds for randomized decision trees, decision trees on arbitrary product probability spaces, and decision trees with nonBoolean outputs. As an application of our results we give a very easy proof that the randomized query complexity of nontrivial monotone graph properties is at least/spl Omega/(v/sup 4/3//p/sup 1/3/), where v is the number of vertices and p /spl les/ 1/2 is the critical threshold probability. This supersedes the milestone /spl Omega/(v/sup 4/3//p/sup 1/3/) bound of Hajnal (1991) and is sometimes superior to the best known lower bounds of Chakrabarti-Khot (2001) and Friedgut-Kahn-Wigderson (2002).

Details

FOCS Conference 2005 Conference Paper

Lower Bounds for the Noisy Broadcast Problem

  • Navin Goyal
  • Guy Kindler
  • Michael E. Saks

We prove the first nontrivial (superlinear) lower bound in the noisy broadcast model of distributed computation. In this model, there are n + 1 processors P/sub 0/, P/sub 1/, .. ., P/sub n/. Each P/sub i/, for i /spl ges/ 1, initially has a private bit x/sub i/ and the goal is for P/sub 0/ to learn f (x/sub l/, .. ., x/sub n/) for some specified function f. At each time step, a designated processor broadcasts some function of its private bit and the bits it has heard so far. Each broadcast is received by the other processors but each reception may be corrupted by noise. In this model, Gallager (1988) gave a noise-resistant protocol that allows P/sub 0/ to learn the entire input in O(n log log n) broadcasts. We prove that Gallager's protocol is optimal up to a constant factor. Our lower bound follows from a lower bound in a new model, the generalized noisy decision tree model, which may be of independent interest.

Details

FOCS Conference 2000 Conference Paper

Super-linear time-space tradeoff lower bounds for randomized computation

  • Paul Beame
  • Michael E. Saks
  • Xiaodong Sun
  • Erik Vee

We prove the first time-space lower bound tradeoffs for randomized computation of decision problems. The bounds hold even in the case that the computation is allowed to have arbitrary probability of error on a small fraction of inputs. Our techniques are an extension of those used by M. Ajtai (1999) in his time-space tradeoffs for deterministic RAM algorithms computing element distinctness and for deterministic Boolean branching programs computing an explicit function based on quadratic forms over GF(2). Our results also give a quantitative improvement over those given by Ajtai. Ajtai shows, for certain specific functions, that any branching program using space S=o(n) requires time T that is superlinear. The functional form of the superlinear bound is not given in his paper, but optimizing the parameters in his arguments gives T= /spl Omega/(n log log n/log log log n) for S=0(n/sup 1-/spl epsiv//). For the same functions considered by Ajtai, we prove a time-space tradeoff of the form T=/spl Omega/(n/spl radic/(log(n/S)/log log(n/S))). In particular for space 0(n/sup 1-/spl epsiv//), this improves the lower bound on time to /spl Omega/(n/spl radic/(log n/log log n)).

Details

FOCS Conference 1998 Conference Paper

An Improved Exponential-Time Algorithm for k -SAT

  • Ramamohan Paturi
  • Pavel Pudlák
  • Michael E. Saks
  • Francis Zane

We propose and analyze a simple new algorithm for finding satisfying assignments of Boolean formulae in conjunctive normal form. The algorithm, ResolveSat, is a randomized variant of the DDL procedure by M. Davis et al. (1962) or Davis-Putnam procedure. Rather than applying the DLL procedure to the input formula F, however; ResolveSat enlarges F by adding additional clauses using limited resolution before performing DLL. The basic idea behind our analysis is the same as by R. Paturi (1997): a critical clause for a variable at a satisfying assignment gives rise to a unit clause in the DLL procedure with sufficiently high probability, thus increasing the probability of finding a satisfying assignment. In the current paper, we analyze the effect of multiple critical clauses (obtained through resolution) in producing unit clauses. We show that, for each k, the running time of ResolveSat on a k-CNF formula is significantly better than 2/sup n/, even in the worst case. In particular we show that the algorithm finds a satisfying assignment of a general 3-CNF in time O(2/sup. 446n/) with high probability; where the best previous algorithm has running time O(2/sup. 582n/). We obtain a better upper bound of O(2/sup (2ln2-1)/n+0(n))=O(2/sup 0. 387n/) for 3-CNF that have at most one satisfying assignment (unique k-SAT). For each k, the bounds for general k-CNF are the best known for the worst-case complexity of finding a satisfying solution for k-SAT, the idea of succinctly encoding satisfying solutions can be applied to obtain lower bounds on circuit site. Here, we exhibit a function f such that any depth-3 AND-OR circuit with bottom fan-in bounded by k requires /spl Omega/(2(c/sub k/n/k)) gates (with c/sub k/>1). This is the first such lower bound with c/sub k/>1.

Details

FOCS Conference 1998 Conference Paper

Time-Space Tradeoffs for Branching Programs

  • Paul Beame
  • Michael E. Saks
  • T. S. Jayram

We obtain the first non-trivial time-space tradeoff lower bound for functions f: {0, 1}/sup n//spl rarr/{0, 1} on general branching programs by exhibiting a Boolean function f that requires exponential size to be computed by any branching program of length (1+/spl epsiv/)n, for some constant /spl epsiv/>0. We also give the first separation result between the syntactic and semantic read-k models for k>1 by showing that polynomial-size semantic read-twice branching programs can compute functions that require exponential size on any syntactic read-k branching program. We also show a time-space tradeoff result on the more general R-way branching program model: for any k, we give a function that requires exponential size to be computed by length kn q-way branching programs, for some q=q(k).

Details

FOCS Conference 1996 Conference Paper

Discrepancy Sets and Pseudorandom Generators for Combinatorial Rectangles

  • Roy Armoni
  • Michael E. Saks
  • Avi Wigderson
  • Shiyu Zhou

A common subproblem of DNF approximate counting and derandomizing RL is the discrepancy problem for combinatorial rectangles. We explicitly construct a poly(n)-size sample space that approximates the volume of any combinatorial rectangle in [n]/sup n/ to within o(1) error. The construction extends the previous techniques for the analogous hitting set problem, most notably via discrepancy preserving reductions.

Details

FOCS Conference 1995 Conference Paper

RSPACE(S) \subseteq DSPACE(S 3/2 )

  • Michael E. Saks
  • Shiyu Zhou

We prove that any language that can be recognized by a randomized algorithm (with possibly two-sided error) that runs in space S and expected time 2/sup 0(s)/ can be recognized by a deterministic algorithm running in space S/sup 3/2/. This improves over the best previously known result that such algorithms have deterministic space S/sup 2/ simulations which, for one-sided error algorithms, follows from Savitch's Theorem and for two-sided error algorithms follows by reduction to recursive matrix powering. Our result includes as a special case the result due to N. Nisan et al. (1992), that undirected connectivity can be computed in space log/sup 3/2/n. It is obtained via a new algorithm for repeated squaring of a matrix we show how to approximate the 2/sup /spl tau// power of a d/spl times/d matrix in space /spl tau//sup 1/2/ log d, improving on the bo und of /spl tau/ log d that comes from the natural recursive algorithm. The algorithm employs Nisan's pseudorandom generator for space bounded computation, together with some new techniques for reducing the number of random bits needed by an algorithm.

Details

FOCS Conference 1994 Conference Paper

Products and Help Bits in Decision Trees

  • Noam Nisan
  • Steven Rudich
  • Michael E. Saks

We investigate two problems concerning the complexity of evaluating a function f at k-tuple of unrelated inputs by k parallel decision tree algorithms. In the product problem, for some fixed depth bound d, we seek to maximize the fraction of input k-tuples for which all k decision trees are correct. Assume that for a single input to f, the best decision tree algorithm of depth d is correct on a fraction p of inputs. We prove that the maximum fraction of k-tuples on which k depth d algorithms are all correct is at most p/sup k/, which is the trivial lower bound. We show that if we replace the depth d restriction by "expected depth d", then this result fails. In the help-bit problem, we are permitted to ask k-1 arbitrary binary questions about the k-tuple of inputs. For each possible k-1-tuple of answers to these queries we will have a k-tuple of decision trees which are supposed to correctly compute all functions on k-tuples that are consistent with the particular answers. The complexity here is the maximum depth of any of the trees in the algorithm. We show that for all k sufficiently large, this complexity is equal to deg/sup s/(f) which is the minimum degree of a multivariate polynomial whose sign is equal to f. Finally, we give a brief discussion of these problems in the context of other complexity models. >

Details

FOCS Conference 1992 Conference Paper

A Decomposition Theorem and Bounds for Randomized Server Problems

  • Avrim Blum
  • Howard J. Karloff
  • Yuval Rabani
  • Michael E. Saks

The authors prove a lower bound of Omega ( square root logk/loglogk) for the competitive ratio of randomized algorithms for the k-server problem against an oblivious adversary. The bound holds for arbitrary metric spaces (of at least k+1 points) and provides a new lower bound for the metrical task system problem as well. This improves the previous best lower bound of Omega (loglogk) for arbitrary metric spaces, more closely approaching the conjectured lower bound of Omega (logk). They also prove a lower bound of Omega (/sup logk///sub loglogk/) for the server problem on k+1 equally-spaced points on a line, which corresponds to some natural motion-planning problems. >

Details

FOCS Conference 1990 Conference Paper

A Dining Philosophers Algorithm with Polynomial Response Time

  • Baruch Awerbuch
  • Michael E. Saks

Presents an efficient distributed online algorithm for scheduling jobs that are created dynamically, subject to resource constraints that require that certain pairs of jobs not run concurrently. The focus is on the response time of the system to each job, i. e. the length of the time interval that starts when the job is created or assigned to a processor and ends at the instant the execution of the job begins. The goal is to provide guarantees on the response time to each job j in terms of the density of arrivals of jobs that conflict with j. The model is completely asynchronous and includes various resource allocation problems that have been studied extensively, including the dining philosophers problem and its generalizations to arbitrary networks. In these versions of the problem, the resource requirements of each new job j determines an upper bound delta /sub j/ on the number of jobs that can exist concurrently in the system and conflict with j. Given such upper bounds, no scheduling algorithm can guarantee a response time better than delta /sub j/ times the maximum execution or message transmission time. A simple algorithm that guarantees response time that is essentially polynomial in delta /sub j/ is presented. It is based on the notion of a distribution queue and has a compact implementation. >

Details

FOCS Conference 1990 Conference Paper

On Threshold Circuits for Parity

  • Ramamohan Paturi
  • Michael E. Saks

Motivated by, the problem of understanding the limitations of neural networks for representing Boolean functions, the authors consider size-depth tradeoffs for threshold circuits that compute the parity function. They give an almost optimal lower bound on the number of edges of any depth-2 threshold circuit that computes the parity function with polynomially bounded weights. The main technique used in the proof, which is based on the theory of rational approximation, appears to be a potentially useful technique for the analysis of such networks. It is conjectured that there are no linear size, bounded-depth threshold circuits for computing parity. >

Details

FOCS Conference 1988 Conference Paper

Lattices, Möbius Functions and Communication Complexity

  • László Lovász 0001
  • Michael E. Saks

A general framework for the study of a broad class of communication problems is developed. It is based on a recent analysis of the communication complexity of graph connectivity. The approach makes use of combinatorial lattice theory. >

Details

FOCS Conference 1987 Conference Paper

Local Management of a Global Resource in a Communication Network

  • Yehuda Afek
  • Baruch Awerbuch
  • Serge A. Plotkin
  • Michael E. Saks

We introduce a new primitive, the Resource Controller, which abstracts the problem of controlling the total amount of resources consumed by a distributed algorithm. We present an efficient distributed algorithm to implement this abstraction. The message complexity of our algorithm per participating node is polylogarithmic in the size of the network, compared to the linear cost per node of the naive algorithm. The implementation of our algorithm is simple and practical and the techniques used are interesting because a global quantity is managed in a distributed way. The Resource Controller can be used to construct efficient algorithms for a number of important problems, such as the problem of bounding the worst-case message complexity of a protocol and the problem of dynamically assigning unique names to nodes participating in a protocol.

Details

FOCS Conference 1986 Conference Paper

Probabilistic Boolean Decision Trees and the Complexity of Evaluating Game Trees

  • Michael E. Saks
  • Avi Wigderson

The Boolean Decision tree model is perhaps the simplest model that computes Boolean functions; it charges only for reading an input variable. We study the power of randomness (vs. both determinism and non-determinism) in this model, and prove separation results between the three complexity measures. These results are obtained via general and efficient methods for computing upper and lower bounds on the probabilistic complexity of evaluating Boolean formulae in which every variable appears exactly once (AND/OR tree with distinct leaves). These bounds are shown to be exactly tight for interesting families of such tree functions. We then apply our results to the complexity of evaluating game trees, which is a central problem in AI. These trees are similar to Boolean tree functions, except that input variables (leaves) may take values from a large set (of valuations to game positions) and the AND/OR nodes are replaced by MIN/MAX nodes. Here the cost is the number of positions (leaves) probed by the algorithm. The best known algorithm for this problem is the alpha-beta pruning method. As a deterministic algorithm, it will in the worst case have to examine all positions. Many papers studied the expected behavior of alpha-beta pruning (on uniform trees) under the unreasonable assumption that position values are drawn independently from some distribution. We analyze a randomized variant of alphabeta pruning, show that it is considerably faster than the deterministic one in worst case, and prove it optimal for uniform trees.

Details

FOCS Conference 1983 Conference Paper

A Topological Approach to Evasiveness

  • Jeff Kahn 0001
  • Michael E. Saks
  • Dean Sturtevant

The complexity of a digraph property is the number of entries of the vertex adjacency matrix of a digraph which must be examined in worst case to determine whether the digraph has the property. Rivest and Vuillemin proved the result (conjectured by Aanderaa and Rosenberg) that every graph property that is monotone (preserved by addition of edges) and nontrivial (holds for some but not all graphs) has complexity θ(v2) where v is the number of vertices. Karp conjectured that every such property is evasive, i. e. , requires that every entry of the incidence matrix be examined. In this paper it is shown that Karp's conjecture follows from another conjecture concerning group actions on topological spaces. A special case of this conjecture is proved and applied to prove Karp's conjecture for the case of properties of graph and digraph properties on a prime power number of vertices.

Details