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

STOC Conference 2024 Conference Paper

Almost Linear Size Edit Distance Sketch

  • Michal Koucký 0001
  • Michael E. Saks

We design an almost linear-size sketching scheme for computing edit distance up to a given threshold k . The scheme consists of two algorithms, a sketching algorithm and a recovery algorithm. The sketching algorithm depends on the parameter k and takes as input a string x and a public random string ρ and computes a sketch sk ρ ( x ; k ), which is a compressed version of x . The recovery algorithm is given two sketches sk ρ ( x ; k ) and sk ρ ( y ; k ) as well as the public random string ρ used to create the two sketches, and (with high probability) if the edit distance ED ( x , y ) between x and y is at most k , will output ED ( x , y ) together with an optimal sequence of edit operations that transforms x to y , and if ED ( x , y ) > k will output large. The size of the sketch output by the sketching algorithm on input x is k 2 O (√log( n )loglog( n )) (where n is an upper bound on length of x ). The sketching and recovery algorithms both run in time polynomial in n . The dependence of sketch size on k is information theoretically optimal and improves over the quadratic dependence on k in schemes of Kociumaka, Porat and Starikovskaya (FOCS’2021), and Bhattacharya and Koucký (STOC’2023).

Details

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

STOC Conference 2020 Conference Paper

Constant factor approximations to edit distance on far input pairs in nearly linear time

  • Michal Koucký 0001
  • Michael E. Saks

For any T ≥ 1, there are constants R = R ( T ) ≥ 1 and ζ=ζ( T )>0 and a randomized algorithm that takes as input an integer n and two strings x , y of length at most n , and runs in time O ( n 1+1/ T ) and outputs an upper bound U on the edit distance of edit ( x , y ) that with high probability, satisfies U ≤ R ( edit ( x , y )+ n 1−ζ ). In particular, on any input with edit ( x , y ) ≥ n 1−ζ the algorithm outputs a constant factor approximation with high probability. A similar result has been proven independently by Brakensiek and Rubinstein (this proceedings).

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

SODA Conference 2013 Conference Paper

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

  • Michael E. Saks
  • C. Seshadhri 0001

Approximating the length of the longest increasing sequence (LIS) of an array is a well-studied problem. We study this problem in the data stream model, where the algorithm is allowed to make a single left-to-right pass through the array and the key resource to be minimized is the amount of additional memory used. We present an algorithm which, for any δ > 0, given streaming access to an array of length n provides a (1 + δ)-multiplicative approximation to the distance to monotonicity ( n minus the length of the LIS), and uses only O((log 2 n )/δ) space. The previous best known approximation using polylogarithmic space was a multiplicative 2-factor. The improved approximation factor reflects a qualitative difference between our algorithm and previous algorithms: previous polylogarithmic space algorithms could not reliably detect increasing subsequences of length as large as n /2, while ours can detect increasing subsequences of length βn for any β > 0. More precisely, our algorithm can be used to estimate the length of the LIS to within an additive δn for any δ > 0 while previous algorithms could only achieve additive error n (1/2 − o (1)). Our algorithm is very simple, being just 3 lines of pseudocode, and has a small update time. It is essentially a polylogarithmic space approximate implementation of a classic dynamic program that computes the LIS. We also show how our technique can be applied to other problems solvable by dynamic programs. For example, we give a streaming algorithm for approximating LCS ( x, y ), the length of the longest common subsequence between strings x and y, each of length n. Our algorithm works in the asymmetric setting (inspired by [AKO10]), in which we have random access to y and streaming access to x, and runs in small space provided that no single symbol appears very often in y. More precisely, it gives an additive- δn approximation to LCS ( x, y ) (and hence also to E ( x, y ) = n − LCS ( x, y ), the edit distance between x and y when insertions and deletions, but not substitutions, are allowed), with space complexity O ( k (log 2 n )/δ), where k is the maximum number of times any one symbol appears in y. We also provide a deterministic 1-pass streaming algorithm that outputs a (1 + δ)-multiplicative approximation for E ( x, y ) (which is also an additive δn-approximation), in the asymmetric setting, and uses ) space. All these algorithms are obtained by carefully trading space and accuracy within a standard dynamic program.

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

STOC Conference 2002 Conference Paper

Space lower bounds for distance approximation in the data stream model

  • Michael E. Saks
  • Xiaodong Sun

(MATH) We consider the problem of approximating the distance of two d -dimensional vectors x and y in the data stream model. In this model, the 2 d coordinates are presented as a "stream" of data in some arbitrary order, where each data item includes the index and value of some coordinate and a bit that identifies the vector ( x or y ) to which it belongs. The goal is to minimize the amount of memory needed to approximate the distance. For the case of L p -distance with p ε [1,2], there are good approximation algorithms that run in polylogarithmic space in d (here we assume that each coordinate is an integer with O (log d ) bits). Here we prove that they do not exist for p <2. In particular, we prove an optimal approximation-space tradeoff of approximating L ∞ distance of two vectors. We show that any randomized algorithm that approximates L ∞ distance of two length d vectors within factor of d δ requires ω( d 1—4δ ) space. As a consequence we show that for p <2/(1—4δ), any randomized algorithm that approximate L p distance of two length d vectors within a factor d δ requires ω( d 1— 2 < \over p —4δ ) space.The lower bound follows from a lower bound on the two-party one-round communication complexity of this problem. This lower bound is proved using a combination of information theory and Fourier analysis.

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

STOC Conference 1992 Conference Paper

Adapting to Asynchronous Dynamic Networks (Extended Abstract)

  • Baruch Awerbuch
  • Boaz Patt-Shamir
  • David Peleg
  • Michael E. Saks

The computational power of different communication models is a fundamental question in the theory of distributed computation. For example, in the synchronous model messages are assumed to be delivered within one time unit, whereas in the asynchronous model message delays may be arbitrary. Another important parameter of the model is the assumptions about the topology. In the dynamic topology model, links are assumed to crash and recover dynamically, but their status is known to the incident node processors. A meaningful computation can be carried out if the topology stabilizes for a sufficiently long period.

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

STOC Conference 1989 Conference Paper

The Cell Probe Complexity of Dynamic Data Structures

  • Michael L. Fredman
  • Michael E. Saks

Dynamic data structure problems involve the representation of data in memory in such a way as to permit certain types of modifications of the data (updates) and certain types of questions about the data (queries). This paradigm encompasses many fundamental problems in computer science. The purpose of this paper is to prove new lower and upper bounds on the time per operation to implement solutions to some familiar dynamic data structure problems including list representation, subset ranking, partial sums, and the set union problem. The main features of our lower bounds are: They hold in the cell probe model of computation (A. Yao [18]) in which the time complexity of a sequential computation is defined to be the number of words of memory that are accessed. (The number of bits b in a single word of memory is a parameter of the model). All other computations are free. This model is at least as powerful as a random access machine and allows for unusual representation of data, indirect addressing etc. This contrasts with most previous lower bounds which are proved in models (e.g., algebraic, comparison, pointer manipulation) which require restrictions on the way data is represented and manipulated. The lower bound method presented here can be used to derive amortized complexities, worst case per operation complexities, and randomized complexities. The results occasionally provide (nearly tight) tradeoffs between the number R of words of memory that are read per operation, the number W of memory words rewritten per operation and the size b of each word. For the problems considered here there is a parameter n that represents the size of the data set being manipulated and for these problems b = log n is a natural register size to consider. By letting b vary, our results illustrate the effect of register size on time complexity. For instance, one consequence of the results is that for some of the problems considered here, increasing the register size from log n to polylog( n ) only reduces the time complexity by a constant factor. On the other hand, decreasing the register size from log n to 1 increases time complexity by a log n factor for one of the problems we consider and only a loglog n factor for some other problems. The first two specific data structure problems for which we obtain bounds are: List Representation. This problem concerns the representation of an ordered list of at most n (not necessarily distinct) elements from the universe U = {1, 2,…, n }. The operations to be supported are report( k ), which returns the k th element of the list, insert( k , u ) which inserts element u into the list between the elements in positions k - 1 and k , delete( k ), which deletes the k th item. Subset Rank. This problem concerns the representation of a subset S of U = {1, 2,…, n }. The operations that must be supported are the updates “insert item j into the set” and “delete item j from the set” and the queries rank( j ), which returns the number of elements in S that are less than or equal to j . The natural word size for these problems is b = log n , which allows an item of U or an index into the list to be stored in one register. One simple solution to the list representation problem is to maintain a vector v , whose k th entry contains the k th item of the list. The report operation can be done in constant time, but the insert and delete operations may take time linear in the length of the list. Alternatively, one could store the items of the list with each element having a pointer to its predecessor and successor in the list. This allows for constant time updates (given a pointer to the appropriate location), but requires linear cost for queries. This problem can be solved must more efficiently by use of balanced trees (such as AVL trees). When b = log n , the worst case cost per operation using AVL trees is O (log n ). If instead b = 1, so that each bit access costs 1, then the AVL three solution requires O (log 2 n ) per operation. It is not hard to find similar upper bounds for the subset rank problem (the algorithms for this problem are actually simpler than AVL trees). The question is: are these upper bounds bet possible? Our results show that the upper bounds for the case of log n bit registers are within a loglog n factor of optimal. On the other hand, somewhat surprisingly, for the case of single bit registers there are implementations for both of these problems that run in time significantly faster than O (log 2 n ) per operation. Let CPROBE( b ) denote the cell probe computational model with register size b . Theorem 1. If b ≤ (log n ) t for some t , then any CPROBE( b ) implementation of either list representation or the subset rank requires Ω(log n /loglog n ) amortized time per operation. Theorem 2. Subset rank and list representation have CPROBE(1) implementations with respective complexities O ((log n )(loglog n )) and O ((log n )(loglog n ) 2 ) per operation. Paul Dietz (personal communication) has found an implementation of list representation with log n bit registers that requires only O (log n /loglog n ) time per operation, and thus the result of theorem 1 is best possible. The lower bounds of theorem 1 are derived from lower bounds for a third problem: Partial sum mode k. An array A [1],…, A [ N ] of integers mod k is to be represented. Updates are add( i , δ) which implements A [ i ] ← A [ i ] + δ; and queries are sum(j) which returns Σ i ≤ j A [ i ] (mod k ). This problem is demoted PS(n, k). Our main lower bound theorems provide tradeoffs between the number of register rewrites and register reads as a function of n , k , and b . Two corollaries of these results are: Theorem 3. Any CPROBE( b ) implementation of PS(n, 2) (partial sums mod 2) requires Ω(log n /(loglog n + log b )) amortized time per operation, and for b ≥ log n , there is an implementation that achieves this. In particular, if b = Θ((log n ) c ) for some constant c , then the optimal time complexity of PS(n, 2) is θ(log n /loglog n ). Theorem 4. Any CPROBE(1) implementation of PS(n, n) with single bit registers requires Ω((log n /loglog n ) 2 ) amortized time per operation, and there is an implementation that achieves O (log 2 n ) time per operation. It can be shown that a lower bound of PS(n, 2) is also a lower bound for both list representation and subset rank (the details, which are not difficult, are omitted from this report), and thus theorem 1 follows from theorem 3. The results of theorem 4 make an interesting contrast with those of theorem 2. For the three problems, list representation, subset rank and PS(n, k), there are standard algorithms that can be implemented on a CPROBE(log n ) that use time O (log n per operation, and their implementations on CPROBE(1) require O (log 2 n ) time. Theorem 4 says that for the problem PS(n, n) this algorithm is essentially best possible, while theorem 2 says that for list representation and rank, the algorithm can be significantly improved. In fact, the rank problem an be viewed as a special case of PS(n, n) where the variables take on values on {0, 1}, and apparently this specialization is enough to reduce the complexity on a CPROBE(1) by a factor of log n /loglog n , even though on a CPROBE(log n ) the complexities of the two problems differ by no more than a loglog n factor. The third problem we consider is the set union problem. This problem concerns the design of a data structure for the on-line manipulation of sets in the following setting. Initially, there are n singleton sets {1}, {2},…, { n } with i chosen as the name of the set { i }. Our data structure is required to implement two operations, Find( j ), and Union( A , B , C ). The operation Find( j ) returns the name of the set containing j . The operation Union( A , B , C ) combines the sets with names A and B . The names of the existing sets at any moment must be unique and chosen to be integers in the range from 1 to 2 n . The sets existing at any time are disjoint and define a partition of the elements into equivalence classes. A well known data structure for the set union problem represents the sets as trees and stores the name of a set in the root of its corresponding tree. A Union operation is performed by attaching the root of the smaller set as a child of the root of the larger set (weight rule). A Find operation is implemented by following the path from the appropriate node to the root of the tree containing it, and then redirecting to the root the parent pointers of the nodes encountered along this path (path compression). From now on we consider sequences of Union and Find operations consisting of n -1 Union operations and m Find operations with m ≥ n . Tarjan [14] demonstrated that the above algorithm requires time θ( m α( m , n )), where α( m , n ) is an inverse to Ackermann's function, to execute n -1 Union and m Find operations. In particular, if m = θ( n ), then the running time is almost, but not quite, linear. Tarjan conjectured [14] that no linear time algorithm exists for the set union problem, and provided significant evidence in favor of this conjecture (which we discuss in the following section). We affirm Tarjan's conjecture in the CPROBE(log n ) model. Theorem 5. Any CPROBE(log n ) implementation of the set union problem requires Ω( m α( m , n )) time to execute m Find's and n -1 Union's, beginning with n singleton sets. N. Blum [2] has given a log n /loglog n algorithm (worst case time per operation) for the set union problem. This algorithm is also optimal in the CPROBE(polylog n ) model. The following Section provides further discussion of these results, Section 3 outlines our lower bound method, and Section 4 contains some proofs.

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

STOC Conference 1984 Conference Paper

Every Poset Has a Good Comparison

  • Jeff Kahn 0001
  • Michael E. Saks

We show that any finite partially ordered set P contains a pair of elements x and y such that the proportion of linear extensions of P in which x lies below y is between 3/11 and 8/11. A consequence is that the information-theoretic lower bound for sorting under partial information is tight up to a multiplicative constant. Precisely: if X is a totally ordered set about which we are given some partial information, and if e(X) is the number of total orderings of X compatible with this partial information, then it is possible to sort X using no more than c log 2 e(X) comparisons (c@@@@2.17).

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
v2026.09.13