Soheil Ehsani

Search for another author

Author Description

Ask a Question About This Mathematician

Prophet Secretary for Combinatorial Auctions and Matroids

2018-01-01

Soheil Ehsani , MohammadTaghi Hajiaghayi , Thomas Keßelheim +1 more

The secretary and the prophet inequality problems are central to the field of Stopping Theory. Recently, there has been a lot of work in generalizing these models to multiple items … The secretary and the prophet inequality problems are central to the field of Stopping Theory. Recently, there has been a lot of work in generalizing these models to multiple items because of their applications in mechanism design. The most important of these generalizations are to matroids and to combinatorial auctions (extends bipartite matching). Kleinberg-Weinberg [33] and Feldman et al. [17] show that for adversarial arrival order of random variables the optimal prophet inequalities give a 1/2-approximation. For many settings, however, it's conceivable that the arrival order is chosen uniformly at random, akin to the secretary problem. For such a random arrival model, we improve upon the 1/2-approximation and obtain (1 – 1/e)-approximation prophet inequalities for both matroids and combinatorial auctions. This also gives improvements to the results of Yan [45] and Esfandiari et al. [15] who worked in the special cases where we can fully control the arrival order or when there is only a single item.Our techniques are threshold based. We convert our discrete problem into a continuous setting and then give a generic template on how to dynamically adjust these thresholds to lower bound the expected total welfare.

View PDF Chat

Beating 1-1/e for ordered prophets

2017-06-15

Melika Abolhassani , Soheil Ehsani , Hossein Esfandiari +3 more

Hill and Kertz studied the prophet inequality on iid distributions [The Annals of Probability 1982]. They proved a theoretical bound of 1 - 1/e on the approximation factor of their … Hill and Kertz studied the prophet inequality on iid distributions [The Annals of Probability 1982]. They proved a theoretical bound of 1 - 1/e on the approximation factor of their algorithm. They conjectured that the best approximation factor for arbitrarily large n is 1/1+1/e ≃ 0.731. This conjecture remained open prior to this paper for over 30 years. In this paper we present a threshold-based algorithm for the prophet inequality with n iid distributions. Using a nontrivial and novel approach we show that our algorithm is a 0.738-approximation algorithm. By beating the bound of 1/1+1/e, this refutes the conjecture of Hill and Kertz. Moreover, we generalize our results to non-uniform distributions and discuss its applications in mechanism design.

View PDF Chat

Approximating Edit Distance in Truly Subquadratic Time: Quantum and MapReduce

2018-01-01

Mahdi Boroujeni , Soheil Ehsani , Mohammad Ghodsi +2 more

The edit distance between two strings is defined as the smallest number of insertions, deletions, and substitutions that need to be made to transform one of the strings to another … The edit distance between two strings is defined as the smallest number of insertions, deletions, and substitutions that need to be made to transform one of the strings to another one. Approximating edit distance in subquadratic time is "one of the biggest unsolved problems in the field of combinatorial pattern matching" [21]. Our main result is a quantum constant approximation algorithm for computing the edit distance in truly subquadratic time. More precisely, we give an O(n1.858) quantum algorithm that approximates the edit distance within a factor of 7. We further extend this result to an O(n1.781) quantum algorithm that approximates the edit distance within a larger constant factor.Our solutions are based on a framework for approximating edit distance in parallel settings. This framework requires as black box an algorithm that computes the distances of several smaller strings all at once. For a quantum algorithm, we reduce the black box to metric estimation and provide efficient algorithms for approximating it. We further show that this framework enables us to approximate edit distance in distributed settings. To this end, we provide a MapReduce algorithm to approximate edit distance within a factor of 3, with sublinearly many machines and sublinear memory. Also, our algorithm runs in a logarithmic number of rounds.

View PDF Chat

Approximating Edit Distance in Truly Subquadratic Time: Quantum and MapReduce

2021-05-13

Mahdi Boroujeni , Soheil Ehsani , Mohammad Ghodsi +2 more

The edit distance between two strings is defined as the smallest number of insertions , deletions , and substitutions that need to be made to transform one of the strings … The edit distance between two strings is defined as the smallest number of insertions , deletions , and substitutions that need to be made to transform one of the strings to another one. Approximating edit distance in subquadratic time is “one of the biggest unsolved problems in the field of combinatorial pattern matching” [37]. Our main result is a quantum constant approximation algorithm for computing the edit distance in truly subquadratic time. More precisely, we give an <?TeX $O(n^{1.810})$?> quantum algorithm that approximates the edit distance within a factor of 3. We further extend this result to an <?TeX $O(n^{1.708})$?> quantum algorithm that approximates the edit distance within a larger constant factor. Our solutions are based on a framework for approximating edit distance in parallel settings. This framework requires as black box an algorithm that computes the distances of several smaller strings all at once. For a quantum algorithm, we reduce the black box to metric estimation and provide efficient algorithms for approximating it. We further show that this framework enables us to approximate edit distance in distributed settings. To this end, we provide a MapReduce algorithm to approximate edit distance within a factor of <?TeX $1+\epsilon$?> , with sublinearly many machines and sublinear memory. Also, our algorithm runs in a logarithmic number of rounds.

View PDF Chat

Stochastic k-Server: How Should Uber Work?

2017-05-01

Sina Dehghani , Soheil Ehsani , MohammadTaghi Hajiaghayi +2 more

In this paper, we study a stochastic variant of the celebrated k-server problem. In the k-server problem, we are required to minimize the total movement of k servers that are … In this paper, we study a stochastic variant of the celebrated k-server problem. In the k-server problem, we are required to minimize the total movement of k servers that are serving an online sequence of t requests in a metric. In the stochastic setting we are given t independent distributions in advance, and at every time step i a request is drawn from Pi. Designing the optimal online algorithm in such setting is NP-hard, therefore the emphasis of our work is on designing an approximately optimal online algorithm. We first show a structural characterization for a certain class of non-adaptive online algorithms. We prove that in general metrics, the best of such algorithms has a cost of no worse than three times that of the optimal online algorithm. Next, we present an integer program that finds the optimal algorithm of this class for any arbitrary metric. Finally, by rounding the solution of the linear relaxation of this program, we present an online algorithm for the stochastic k-server problem with the approximation factor of 3 in the line and circle metrics and O(log n) in a general metric of size n. Moreover, we define the Uber problem, in which each demand consists of two endpoints, a source and a destination. We show that given an a-approximation algorithm for the k-server problem, we can obtain an (a+2)-approximation algorithm for the Uber problem. Motivated by the fact that demands are usually highly correlated with the time we study the stochastic Uber problem. Furthermore, we extend our results to the correlated setting where the probability of a request arriving at a certain point depends not only on the time step but also on the previously arrived requests.

Approximating Edit Distance in Truly Subquadratic Time: Quantum and MapReduce

2018-04-11

Mahdi Boroujeni , Soheil Ehsani , Mohammad Ghodsi +2 more

The edit distance between two strings is defined as the smallest number of insertions, deletions, and substitutions that need to be made to transform of the strings to another one. … The edit distance between two strings is defined as the smallest number of insertions, deletions, and substitutions that need to be made to transform of the strings to another one. Approximating edit distance in subquadratic time is one of the biggest unsolved problems in the field of combinatorial pattern matching. Our main result is a quantum constant approximation algorithm for computing the edit distance in truly subquadratic time. More precisely, we give an $O(n^{1.858})$ quantum algorithm that approximates the edit distance within a factor of $7$. We further extend this result to an $O(n^{1.781})$ quantum algorithm that approximates the edit distance within a larger constant factor. Our solutions are based on a framework for approximating edit distance in parallel settings. This framework requires as black box an algorithm that computes the distances of several smaller strings all at once. For a quantum algorithm, we reduce the black box to \textit{metric estimation} and provide efficient algorithms for approximating it. We further show that this framework enables us to approximate edit distance in distributed settings. To this end, we provide a MapReduce algorithm to approximate edit distance within a factor of $3$, with sublinearly many machines and sublinear memory. Also, our algorithm runs in a logarithmic number of rounds.

Online Degree-Bounded Steiner Network Design

2015-12-21

Sina Dehghani , Soheil Ehsani , MohammadTaghi Hajiaghayi +1 more

We initiate the study of degree-bounded network design problems in the online setting. The degree-bounded Steiner tree problem – which asks for a subgraph with minimum degree that connects a … We initiate the study of degree-bounded network design problems in the online setting. The degree-bounded Steiner tree problem – which asks for a subgraph with minimum degree that connects a given set of vertices – is perhaps one of the most representative problems in this class. This paper deals with its well-studied generalization called the degree-bounded Steiner forest problem where the connectivity demands are represented by vertex pairs that need to be individually connected. In the classical online model, the input graph is given offline but the demand pairs arrive sequentially in online steps. The selected subgraph starts off as the empty subgraph, but has to be augmented to satisfy the new connectivity constraint in each online step. The goal is to be competitive against an adversary that knows the input in advance.The standard techniques for solving degree-bounded problems often fall in the category of iterative and dependent rounding techniques. Unfortunately, these rounding methods are inherently difficult to adapt to an online settings since the underlying fractional solution may change dramatically in between the rounding steps. Indeed, this might be the very reason that despite many advances in the online network design paradigm in the past two decades, the natural family of degree-bounded problems has remained widely open.In this paper, we design an intuitive greedy-like algorithm that achieves a competitive ratio of O(log n) where n is the number of vertices. We show that no (randomized) algorithm can achieve a (multiplicative) competitive ratio o(log n); thus our result is asymptotically tight. We further show strong hardness results for the group Steiner tree and the edge-weighted variants of degree-bounded connectivity problems.Fürer and Raghavachari resolved the offline variant of degree-bounded Steiner forest in their paper in SODA'92. Since then, the family of degree-bounded network design problems has been extensively studied in the literature resulting in the development of many interesting tools and numerous papers on the topic. We hope that our approach and its dual analysis, paves the way for solving the online variants of the classical problems in this family of problems.

View PDF Chat

Stochastic k-Server: How Should Uber Work?

2017-05-16

Sina Dehghani , Soheil Ehsani , MohammadTaghi Hajiaghayi +2 more

Online Weighted Degree-Bounded Steiner Networks via Novel Online Mixed Packing/Covering

2016-01-01

Sina Dehghani , Soheil Ehsani , Mohammad Taghi Hajiaghayi +3 more

We design the first online algorithm with poly-logarithmic competitive ratio for the edge-weighted degree-bounded Steiner forest (EW-DB-SF) problem and its generalized variant. We obtain our result by demonstrating a new … We design the first online algorithm with poly-logarithmic competitive ratio for the edge-weighted degree-bounded Steiner forest (EW-DB-SF) problem and its generalized variant. We obtain our result by demonstrating a new generic approach for solving mixed packing/covering integer programs in the online paradigm. In EW-DB-SF, we are given an edge-weighted graph with a degree bound for every vertex. Given a root vertex in advance, we receive a sequence of terminal vertices in an online manner. Upon the arrival of a terminal, we need to augment our solution subgraph to connect the new terminal to the root. The goal is to minimize the total weight of the solution while respecting the degree bounds on the vertices. In the offline setting, edge-weighted degree-bounded Steiner tree (EW-DB-ST) and its many variations have been extensively studied since early eighties. Unfortunately, the recent advancements in the online network design problems are inherently difficult to adapt for degree-bounded problems. In particular, it is not known whether the fractional solution obtained by standard primal-dual techniques for mixed packing/covering LPs can be rounded online. In contrast, in this paper we obtain our result by using structural properties of the optimal solution, and reducing the EW-DB-SF problem to an exponential-size mixed packing/covering integer program in which every variable appears only once in covering constraints. We then design a generic integral algorithm for solving this restricted family of IPs. As mentioned above, we demonstrate a new technique for solving mixed packing/covering integer programs. Define the covering frequency k of a program as the maximum number of covering constraints in which a variable can participate. Let m denote the number of packing constraints. We design an online deterministic integral algorithm with competitive ratio of O(k*log(m)) for the mixed packing/covering integer programs. We prove the tightness of our result by providing a matching lower bound for any randomized algorithm. We note that our solution solely depends on m and k. Indeed, there can be exponentially many variables. Furthermore, our algorithm directly provides an integral solution, even if the integrality gap of the program is unbounded. We believe this technique can be used as an interesting alternative for the standard primal-dual techniques in solving online problems.

Prophet Secretary for Combinatorial Auctions and Matroids

2024-11-12

Soheil Ehsani , MohammadTaghi Hajiaghayi , Thomas Keßelheim +1 more

The secretary and the prophet inequality problems are central to the field of Stopping Theory. Recently, there has been a lot of work in generalizing these models to multiple items … The secretary and the prophet inequality problems are central to the field of Stopping Theory. Recently, there has been a lot of work in generalizing these models to multiple items because of their applications in mechanism design. The most important of these generalizations are to matroids and to combinatorial auctions (extends bipartite matching). Kleinberg-Weinberg \cite{KW-STOC12} and Feldman et al. \cite{feldman2015combinatorial} show that for adversarial arrival order of random variables the optimal prophet inequalities give a $1/2$-approximation. For many settings, however, it's conceivable that the arrival order is chosen uniformly at random, akin to the secretary problem. For such a random arrival model, we improve upon the $1/2$-approximation and obtain $(1-1/e)$-approximation prophet inequalities for both matroids and combinatorial auctions. This also gives improvements to the results of Yan \cite{yan2011mechanism} and Esfandiari et al. \cite{esfandiari2015prophet} who worked in the special cases where we can fully control the arrival order or when there is only a single item. Our techniques are threshold based. We convert our discrete problem into a continuous setting and then give a generic template on how to dynamically adjust these thresholds to lower bound the expected total welfare.

View PDF Chat

Subcubic Equivalences Between Graph Centrality Measures and Complementary Problems

2019-01-01

Mahdi Boroujeni , Sina Dehghani , Soheil Ehsani +2 more

Despite persistent efforts, there is no known technique for obtaining unconditional super-linear lower bounds for the computational complexity of the problems in P. Vassilevska Williams and Williams introduce a fruitful … Despite persistent efforts, there is no known technique for obtaining unconditional super-linear lower bounds for the computational complexity of the problems in P. Vassilevska Williams and Williams introduce a fruitful approach to advance a better understanding of the computational complexity of the problems in P. In particular, they consider All Pairs Shortest Paths (APSP) and other fundamental problems such as checking whether a matrix defines a metric, verifying the correctness of a matrix product, and detecting a negative triangle in a graph. Abboud, Grandoni, and Vassilevska Williams study well-known graph centrality problems such as Radius, Median, etc., and make a connection between their computational complexity to that of two fundamental problems, namely APSP and Diameter. They show any algorithm with subcubic running time for these centrality problems, implies a subcubic algorithm for either APSP or Diameter. In this paper, we define vertex versions for these centrality problems and based on that we introduce new complementary problems. The main open problem of Abboud et al. is whether or not APSP and Diameter are equivalent under subcubic reduction. One of the results of this paper is APSP and CoDiameter, which is the complementary version of Diameter, are equivalent. Moreover, for some of the problems in this set, we show that they are equivalent to their complementary versions. Considering the slight difference between a problem and its complementary version, these equivalences give us the impression that every problem has such a property, and thus APSP and Diameter are equivalent. This paper is a step forward in showing a subcubic equivalence between APSP and Diameter, and we hope that the approach introduced in our paper can be helpful to make this breakthrough happen.

Stochastic k-Server Problem: How Should Uber Work?

2017-05-16

Sina Dehghani , Soheil Ehsani , MohammadTaghi Hajiaghayi +2 more

Approximating Edit Distance in Truly Subquadratic Time: Quantum and MapReduce

2018-01-01

Mahdi Eskandarian Boroujeni , Soheil Ehsani , Mohammad Ghodsi +2 more

The edit distance between two strings is defined as the smallest number of insertions, deletions, and substitutions that need to be made to transform one of the strings to another … The edit distance between two strings is defined as the smallest number of insertions, deletions, and substitutions that need to be made to transform one of the strings to another one. Approximating edit distance in subquadratic time is "one of the biggest unsolved problems in the field of combinatorial pattern matching". Our main result is a quantum constant approximation algorithm for computing the edit distance in truly subquadratic time. More precisely, we give an $O(n^{1.858})$ quantum algorithm that approximates the edit distance within a factor of $7$. We further extend this result to an $O(n^{1.781})$ quantum algorithm that approximates the edit distance within a larger constant factor. Our solutions are based on a framework for approximating edit distance in parallel settings. This framework requires as black box an algorithm that computes the distances of several smaller strings all at once. For a quantum algorithm, we reduce the black box to \textit{metric estimation} and provide efficient algorithms for approximating it. We further show that this framework enables us to approximate edit distance in distributed settings. To this end, we provide a MapReduce algorithm to approximate edit distance within a factor of $3$, with sublinearly many machines and sublinear memory. Also, our algorithm runs in a logarithmic number of rounds.

View PDF Chat

Prophet Secretary for Combinatorial Auctions and Matroids

2017-01-01

Soheil Ehsani , MohammadTaghi Hajiaghayi , Thomas Keßelheim +1 more

The secretary and the prophet inequality problems are central to the field of Stopping Theory. Recently, there has been a lot of work in generalizing these models to multiple items … The secretary and the prophet inequality problems are central to the field of Stopping Theory. Recently, there has been a lot of work in generalizing these models to multiple items because of their applications in mechanism design. The most important of these generalizations are to matroids and to combinatorial auctions (extends bipartite matching). Kleinberg-Weinberg \cite{KW-STOC12} and Feldman et al. \cite{feldman2015combinatorial} show that for adversarial arrival order of random variables the optimal prophet inequalities give a $1/2$-approximation. For many settings, however, it's conceivable that the arrival order is chosen uniformly at random, akin to the secretary problem. For such a random arrival model, we improve upon the $1/2$-approximation and obtain $(1-1/e)$-approximation prophet inequalities for both matroids and combinatorial auctions. This also gives improvements to the results of Yan \cite{yan2011mechanism} and Esfandiari et al. \cite{esfandiari2015prophet} who worked in the special cases where we can fully control the arrival order or when there is only a single item. Our techniques are threshold based. We convert our discrete problem into a continuous setting and then give a generic template on how to dynamically adjust these thresholds to lower bound the expected total welfare.

Online Weighted Degree-Bounded Steiner Networks via Novel Online Mixed Packing/Covering

2017-01-01

Sina Dehghani , Soheil Ehsani , MohammadTaghi Hajiaghayi +3 more

We design the first online algorithm with poly-logarithmic competitive ratio for the edge-weighted degree-bounded Steiner forest(EW-DB-SF) problem and its generalized variant. We obtain our result by demonstrating a new generic … We design the first online algorithm with poly-logarithmic competitive ratio for the edge-weighted degree-bounded Steiner forest(EW-DB-SF) problem and its generalized variant. We obtain our result by demonstrating a new generic approach for solving mixed packing/covering integer programs in the online paradigm. In EW-DB-SF we are given an edge-weighted graph with a degree bound for every vertex. Given a root vertex in advance we receive a sequence of terminal vertices in an online manner. Upon the arrival of a terminal we need to augment our solution subgraph to connect the new terminal to the root. The goal is to minimize the total weight of the solution while respecting the degree bounds on the vertices. In the offline setting edge-weighted degree-bounded Steiner tree (EW-DB-ST) and its many variations have been extensively studied since early eighties. Unfortunately the recent advancements in the online network design problems are inherently difficult to adapt for degree-bounded problems. In contrast in this paper we obtain our result by using structural properties of the optimal solution, and reducing the EW-DB-SF problem to an exponential-size mixed packing/covering integer program in which every variable appears only once in covering constraints. We then design a generic integral algorithm for solving this restricted family of IPs. We demonstrate a new technique for solving mixed packing/covering integer programs. Define the covering frequency k of a program as the maximum number of covering constraints in which a variable can participate. Let m denote the number of packing constraints. We design an online deterministic integral algorithm with competitive ratio of O(k log m) for the mixed packing/covering integer programs. We believe this technique can be used as an interesting alternative for the standard primal-dual techniques in solving online problems.

Online Degree-Bounded Steiner Network Design

2017-01-01

Sina Dahghani , Soheil Ehsani , MohammadTaghi Hajiaghayi +2 more

We initiate the study of degree-bounded network design problems in the online setting. The degree-bounded Steiner tree problem { which asks for a subgraph with minimum degree that connects a … We initiate the study of degree-bounded network design problems in the online setting. The degree-bounded Steiner tree problem { which asks for a subgraph with minimum degree that connects a given set of vertices { is perhaps one of the most representative problems in this class. This paper deals with its well-studied generalization called the degree-bounded Steiner forest problem where the connectivity demands are represented by vertex pairs that need to be individually connected. In the classical online model, the input graph is given online but the demand pairs arrive sequentially in online steps. The selected subgraph starts off as the empty subgraph, but has to be augmented to satisfy the new connectivity constraint in each online step. The goal is to be competitive against an adversary that knows the input in advance. We design a simple greedy-like algorithm that achieves a competitive ratio of O(log n) where n is the number of vertices. We show that no (randomized) algorithm can achieve a (multiplicative) competitive ratio o(log n); thus our result is asymptotically tight. We further show strong hardness results for the group Steiner tree and the edge-weighted variants of degree-bounded connectivity problems. Fourer and Raghavachari resolved the online variant of degree-bounded Steiner forest in their paper in SODA'92. Since then, the natural family of degree-bounded network design problems has been extensively studied in the literature resulting in the development of many interesting tools and numerous papers on the topic. We hope that our approach in this paper, paves the way for solving the online variants of the classical problems in this family of network design problems.

View PDF Chat

Prophet Secretary for Combinatorial Auctions and Matroids

2024-11-12

Soheil Ehsani , MohammadTaghi Hajiaghayi , Thomas Keßelheim +1 more

The secretary and the prophet inequality problems are central to the field of Stopping Theory. Recently, there has been a lot of work in generalizing these models to multiple items … The secretary and the prophet inequality problems are central to the field of Stopping Theory. Recently, there has been a lot of work in generalizing these models to multiple items because of their applications in mechanism design. The most important of these generalizations are to matroids and to combinatorial auctions (extends bipartite matching). Kleinberg-Weinberg \cite{KW-STOC12} and Feldman et al. \cite{feldman2015combinatorial} show that for adversarial arrival order of random variables the optimal prophet inequalities give a $1/2$-approximation. For many settings, however, it's conceivable that the arrival order is chosen uniformly at random, akin to the secretary problem. For such a random arrival model, we improve upon the $1/2$-approximation and obtain $(1-1/e)$-approximation prophet inequalities for both matroids and combinatorial auctions. This also gives improvements to the results of Yan \cite{yan2011mechanism} and Esfandiari et al. \cite{esfandiari2015prophet} who worked in the special cases where we can fully control the arrival order or when there is only a single item. Our techniques are threshold based. We convert our discrete problem into a continuous setting and then give a generic template on how to dynamically adjust these thresholds to lower bound the expected total welfare.

View PDF Chat

Approximating Edit Distance in Truly Subquadratic Time: Quantum and MapReduce

2021-05-13

Mahdi Boroujeni , Soheil Ehsani , Mohammad Ghodsi +2 more

View PDF Chat

Subcubic Equivalences Between Graph Centrality Measures and Complementary Problems

2019-01-01

Mahdi Boroujeni , Sina Dehghani , Soheil Ehsani +2 more

Approximating Edit Distance in Truly Subquadratic Time: Quantum and MapReduce

2018-04-11

Mahdi Boroujeni , Soheil Ehsani , Mohammad Ghodsi +2 more

Approximating Edit Distance in Truly Subquadratic Time: Quantum and MapReduce

2018-01-01

Mahdi Boroujeni , Soheil Ehsani , Mohammad Ghodsi +2 more

View PDF Chat

Prophet Secretary for Combinatorial Auctions and Matroids

2018-01-01

Soheil Ehsani , MohammadTaghi Hajiaghayi , Thomas Keßelheim +1 more

View PDF Chat

Approximating Edit Distance in Truly Subquadratic Time: Quantum and MapReduce

2018-01-01

Mahdi Eskandarian Boroujeni , Soheil Ehsani , Mohammad Ghodsi +2 more

The edit distance between two strings is defined as the smallest number of insertions, deletions, and substitutions that need to be made to transform one of the strings to another … The edit distance between two strings is defined as the smallest number of insertions, deletions, and substitutions that need to be made to transform one of the strings to another one. Approximating edit distance in subquadratic time is "one of the biggest unsolved problems in the field of combinatorial pattern matching". Our main result is a quantum constant approximation algorithm for computing the edit distance in truly subquadratic time. More precisely, we give an $O(n^{1.858})$ quantum algorithm that approximates the edit distance within a factor of $7$. We further extend this result to an $O(n^{1.781})$ quantum algorithm that approximates the edit distance within a larger constant factor. Our solutions are based on a framework for approximating edit distance in parallel settings. This framework requires as black box an algorithm that computes the distances of several smaller strings all at once. For a quantum algorithm, we reduce the black box to \textit{metric estimation} and provide efficient algorithms for approximating it. We further show that this framework enables us to approximate edit distance in distributed settings. To this end, we provide a MapReduce algorithm to approximate edit distance within a factor of $3$, with sublinearly many machines and sublinear memory. Also, our algorithm runs in a logarithmic number of rounds.

View PDF Chat

Beating 1-1/e for ordered prophets

2017-06-15

Melika Abolhassani , Soheil Ehsani , Hossein Esfandiari +3 more

View PDF Chat

Stochastic k-Server: How Should Uber Work?

2017-05-16

Sina Dehghani , Soheil Ehsani , MohammadTaghi Hajiaghayi +2 more

Stochastic k-Server Problem: How Should Uber Work?

2017-05-16

Sina Dehghani , Soheil Ehsani , MohammadTaghi Hajiaghayi +2 more

Stochastic k-Server: How Should Uber Work?

2017-05-01

Sina Dehghani , Soheil Ehsani , MohammadTaghi Hajiaghayi +2 more

Online Weighted Degree-Bounded Steiner Networks via Novel Online Mixed Packing/Covering

2017-01-01

Sina Dehghani , Soheil Ehsani , MohammadTaghi Hajiaghayi +3 more

We design the first online algorithm with poly-logarithmic competitive ratio for the edge-weighted degree-bounded Steiner forest(EW-DB-SF) problem and its generalized variant. We obtain our result by demonstrating a new generic … We design the first online algorithm with poly-logarithmic competitive ratio for the edge-weighted degree-bounded Steiner forest(EW-DB-SF) problem and its generalized variant. We obtain our result by demonstrating a new generic approach for solving mixed packing/covering integer programs in the online paradigm. In EW-DB-SF we are given an edge-weighted graph with a degree bound for every vertex. Given a root vertex in advance we receive a sequence of terminal vertices in an online manner. Upon the arrival of a terminal we need to augment our solution subgraph to connect the new terminal to the root. The goal is to minimize the total weight of the solution while respecting the degree bounds on the vertices. In the offline setting edge-weighted degree-bounded Steiner tree (EW-DB-ST) and its many variations have been extensively studied since early eighties. Unfortunately the recent advancements in the online network design problems are inherently difficult to adapt for degree-bounded problems. In contrast in this paper we obtain our result by using structural properties of the optimal solution, and reducing the EW-DB-SF problem to an exponential-size mixed packing/covering integer program in which every variable appears only once in covering constraints. We then design a generic integral algorithm for solving this restricted family of IPs. We demonstrate a new technique for solving mixed packing/covering integer programs. Define the covering frequency k of a program as the maximum number of covering constraints in which a variable can participate. Let m denote the number of packing constraints. We design an online deterministic integral algorithm with competitive ratio of O(k log m) for the mixed packing/covering integer programs. We believe this technique can be used as an interesting alternative for the standard primal-dual techniques in solving online problems.

Online Degree-Bounded Steiner Network Design

2017-01-01

Sina Dahghani , Soheil Ehsani , MohammadTaghi Hajiaghayi +2 more

View PDF Chat

Prophet Secretary for Combinatorial Auctions and Matroids

2017-01-01

Soheil Ehsani , MohammadTaghi Hajiaghayi , Thomas Keßelheim +1 more

The secretary and the prophet inequality problems are central to the field of Stopping Theory. Recently, there has been a lot of work in generalizing these models to multiple items … The secretary and the prophet inequality problems are central to the field of Stopping Theory. Recently, there has been a lot of work in generalizing these models to multiple items because of their applications in mechanism design. The most important of these generalizations are to matroids and to combinatorial auctions (extends bipartite matching). Kleinberg-Weinberg \cite{KW-STOC12} and Feldman et al. \cite{feldman2015combinatorial} show that for adversarial arrival order of random variables the optimal prophet inequalities give a $1/2$-approximation. For many settings, however, it's conceivable that the arrival order is chosen uniformly at random, akin to the secretary problem. For such a random arrival model, we improve upon the $1/2$-approximation and obtain $(1-1/e)$-approximation prophet inequalities for both matroids and combinatorial auctions. This also gives improvements to the results of Yan \cite{yan2011mechanism} and Esfandiari et al. \cite{esfandiari2015prophet} who worked in the special cases where we can fully control the arrival order or when there is only a single item. Our techniques are threshold based. We convert our discrete problem into a continuous setting and then give a generic template on how to dynamically adjust these thresholds to lower bound the expected total welfare.

Online Weighted Degree-Bounded Steiner Networks via Novel Online Mixed Packing/Covering

2016-01-01

Sina Dehghani , Soheil Ehsani , Mohammad Taghi Hajiaghayi +3 more

Online Degree-Bounded Steiner Network Design

2015-12-21

Sina Dehghani , Soheil Ehsani , MohammadTaghi Hajiaghayi +1 more

View PDF Chat

Coauthor	Papers Together
MohammadTaghi Hajiaghayi	14
Saeed Seddighin	9
Vahid Liaghat	7
Sina Dehghani	7
Mahdi Boroujeni	4
Mohammad Ghodsi	4
Thomas Keßelheim	3
Harald Räcke	3
Sahil Singla	3
Mohammad Taghi Hajiaghayi	2
Brendan Lucier	1
Hossein Esfandiari	1
Sina Dahghani	1
Robert Kleinberg	1
Melika Abolhassani	1
Mahdi Eskandarian Boroujeni	1
SaeedReza Seddighin	1

Edit Distance Cannot Be Computed in Strongly Subquadratic Time (unless SETH is false)

2015-06-03

Artūrs Bačkurs , Piotr Indyk

The edit distance (a.k.a. the Levenshtein distance) between two strings is defined as the minimum number of insertions, deletions or substitutions of symbols needed to transform one string into another. … The edit distance (a.k.a. the Levenshtein distance) between two strings is defined as the minimum number of insertions, deletions or substitutions of symbols needed to transform one string into another. The problem of computing the edit distance between two strings is a classical computational task, with a well-known algorithm based on dynamic programming. Unfortunately, all known algorithms for this problem run in nearly quadratic time.

View PDF Chat

Quantum Query Complexity of Some Graph Problems

2006-01-01

Christoph Dürr , Mark Heiligman , Peter Høyer +1 more

Quantum algorithms for graph problems are considered, both in the adjacency matrix model and in an adjacency list-like array model. We give almost tight lower and upper bounds for the … Quantum algorithms for graph problems are considered, both in the adjacency matrix model and in an adjacency list-like array model. We give almost tight lower and upper bounds for the bounded error quantum query complexity of Connectivity, Strong Connectivity, Minimum Spanning Tree, and Single Source Shortest Paths. For example, we show that the query complexity of Minimum Spanning Tree is in $\Theta(n^{3/2})$ in the matrix model and in $\Theta(\sqrt{nm})$ in the array model, while the complexity of Connectivity is also in $\Theta(n^{3/2})$ in the matrix model but in $\Theta(n)$ in the array model. The upper bounds utilize search procedures for finding minima of functions under various conditions.

View PDF Chat

Invariant Quantum Algorithms for Insertion into an Ordered List

1999-01-01

Edward Farhi , Michael Sipser , Sam Gutmann +1 more

We consider the problem of inserting one item into a list of N-1 ordered items. We previously showed that no quantum algorithm could solve this problem in fewer than log … We consider the problem of inserting one item into a list of N-1 ordered items. We previously showed that no quantum algorithm could solve this problem in fewer than log N/(2 log log N) queries, for N large. We transform the problem into a "translationally invariant" problem and restrict attention to invariant algorithms. We construct the "greedy" invariant algorithm and show numerically that it outperforms the best classical algorithm for various N. We also find invariant algorithms that succeed exactly in fewer queries than is classically possible, and iterating one of them shows that the insertion problem can be solved in fewer than 0.53 log N quantum queries for large N (where log N is the classical lower bound). We don't know whether a o(log N) algorithm exists.

Limit on the Speed of Quantum Computation in Determining Parity

1998-12-14

Edward Farhi , Jeffrey Goldstone , Sam Gutmann +1 more

Consider a function $f$ which is defined on the integers from 1 to $N$ and takes the values $\ensuremath{-}1$ and $+1$. The parity of $f$ is the product over all … Consider a function $f$ which is defined on the integers from 1 to $N$ and takes the values $\ensuremath{-}1$ and $+1$. The parity of $f$ is the product over all $x$ from 1 to $N$ of $f(x)$. With no further information about $f$, to classically determine the parity of $f$ requires $N$ calls of the function $f$. We show that any quantum algorithm capable of determining the parity of $f$ contains at least $N/2$ applications of the unitary operator which evaluates $f$. Thus, for this problem, quantum computers cannot outperform classical computers.

View PDF Chat

On Exact Quantum Query Complexity

2013-08-29

Ashley Montanaro , Richard Jozsa , Graeme Mitchison

View PDF Chat

Quantum Fourier Transforms and the Complexity of Link Invariants for Quantum Doubles of Finite Groups

2015-01-12

Hari Krovi , Alexander Russell

View PDF Chat

Learning-Graph-Based Quantum Algorithm for k-Distinctness

2012-10-01

Aleksandrs Belovs

We present a quantum algorithm solving the k-distinctness problem in a less number of queries than the previous algorithm by Ambainis. The construction uses a modified learning graph approach. Compared … We present a quantum algorithm solving the k-distinctness problem in a less number of queries than the previous algorithm by Ambainis. The construction uses a modified learning graph approach. Compared to the recent paper by Belovs and Lee, the algorithm doesn't require any prior information on the input, and the complexity analysis is much simpler.

View PDF Chat

Improved Quantum Algorithm for Triangle Finding via Combinatorial Arguments

2014-10-01

François Le Gall

In this paper we present a quantum algorithm solving the triangle finding problem in unweighted graphs with query complexity Õ(n 5/4 ), where n denotes the number of … In this paper we present a quantum algorithm solving the triangle finding problem in unweighted graphs with query complexity Õ(n 5/4 ), where n denotes the number of vertices in the graph. This improves the previous upper bound O(n 9/7 ) = O(n 1.285 ) recently obtained by Lee, Magniez and Santha. Our result shows, for the first time, that in the quantum query complexity setting unweighted triangle finding is easier than its edge-weighted version, since for finding an edge-weighted triangle Belovs and Rosmanis proved that any quantum algorithm requires O(n 9/7 / √log n) queries. Our result also illustrates some limitations of the non-adaptive learning graph approach used to obtain the previous O(n 9/7 ) upper bound since, even over unweighted graphs, any quantum algorithm for triangle finding obtained using this approach requires v(n 9/7 / √log n) queries as well. To bypass the obstacles characterized by these lower bounds, our quantum algorithm uses combinatorial ideas exploiting the graph-theoretic properties of triangle finding, which cannot be used when considering edge-weighted graphs or the non-adaptive learning graph approach.

View PDF Chat

Parallel algorithms for geometric graph problems

2014-05-31

Alexandr Andoni , Aleksandar Nikolov , Krzysztof Onak +1 more

We give algorithms for geometric graph problems in the modern parallel models such as MapReduce. For example, for the Minimum Spanning Tree (MST) problem over a set of points in … We give algorithms for geometric graph problems in the modern parallel models such as MapReduce. For example, for the Minimum Spanning Tree (MST) problem over a set of points in the two-dimensional space, our algorithm computes a (1 + ε)-approximate MST. Our algorithms work in a constant number of rounds of communication, while using total space and communication proportional to the size of the data (linear space and near linear time algorithms). In contrast, for general graphs, achieving the same result for MST (or even connectivity) remains a challenging open problem [9], despite drawing significant attention in recent years.

View PDF Chat

Tight Bounds on Quantum Searching

1998-06-01

Michel Boyer , Gilles Brassard , Peter Høyer +1 more

We provide a tight analysis of Grover's algorithm for quantum database searching. We give a simple closed-form formula for the probability of success after any given number of iterations of … We provide a tight analysis of Grover's algorithm for quantum database searching. We give a simple closed-form formula for the probability of success after any given number of iterations of the algorithm. This allows us to determine the number of iterations necessary to achieve almost certainty of finding the answer. Furthermore, we analyse the behaviour of the algorithm when the element to be found appears more than once in the table and we provide a new algorithm to find such an element even when the number of solutions is not known ahead of time. Finally, we provide a lower bound on the efficiency of any possible quantum database searching algorithm and we show that Grover's algorithm comes within 2.62% of being optimal.

View PDF Chat

Bayesian Combinatorial Auctions: Expanding Single Buyer Mechanisms to Many Buyers

2011-06-06

Saeed Alaei

For Bayesian combinatorial auctions, we present a general framework for approximately reducing the mechanism design problem for multiple buyers to single buyer sub-problems. Our framework can be applied to any … For Bayesian combinatorial auctions, we present a general framework for approximately reducing the mechanism design problem for multiple buyers to single buyer sub-problems. Our framework can be applied to any setting which roughly satisfies the following assumptions: (i) buyers' types must be distributed independently (not necessarily identically), (ii) objective function must be linearly separable over the buyers, and (iii) except for the supply constraints, there should be no other inter-buyer constraints. Our framework is general in the sense that it makes no explicit assumption about buyers' valuations, type distributions, and single buyer constraints (e.g., budget, incentive compatibility, etc). We present two generic multi buyer mechanisms which use single buyer mechanisms as black boxes; if an $\alpha$-approximate single buyer mechanism can be constructed for each buyer, and if no buyer requires more than $\frac{1}{k}$ of all units of each item, then our generic multi buyer mechanisms are $\gamma_k\alpha$-approximation of the optimal multi buyer mechanism, where $\gamma_k$ is a constant which is at least $1-\frac{1}{\sqrt{k+3}}$. Observe that $\gamma_k$ is at least 1/2 (for $k=1$) and approaches 1 as $k \to \infty$. As a byproduct of our construction, we present a generalization of prophet inequalities. Furthermore, as applications of our framework, we present multi buyer mechanisms with improved approximation factor for several settings from the literature.

Online Stochastic Matching: Beating 1-1/e

2009-01-01

Jon Feldman , Aranyak Mehta , Vahab Mirrokni +1 more

We study the online stochastic bipartite matching problem, in a form motivated by display ad allocation on the Internet. In the online, but adversarial case, the celebrated result of Karp, … We study the online stochastic bipartite matching problem, in a form motivated by display ad allocation on the Internet. In the online, but adversarial case, the celebrated result of Karp, Vazirani and Vazirani gives an approximation ratio of $1-1/e$. In the online, stochastic case when nodes are drawn repeatedly from a known distribution, the greedy algorithm matches this approximation ratio, but still, no algorithm is known that beats the $1 - 1/e$ bound. Our main result is a 0.67-approximation online algorithm for stochastic bipartite matching, breaking this $1 - {1/e}$ barrier. Furthermore, we show that no online algorithm can produce a $1-ε$ approximation for an arbitrarily small $ε$ for this problem. We employ a novel application of the idea of the power of two choices from load balancing: we compute two disjoint solutions to the expected instance, and use both of them in the online algorithm in a prescribed preference order. To identify these two disjoint solutions, we solve a max flow problem in a boosted flow graph, and then carefully decompose this maximum flow to two edge-disjoint (near-)matchings. These two offline solutions are used to characterize an upper bound for the optimum in any scenario. This is done by identifying a cut whose value we can bound under the arrival distribution.

Beyond matroids: Secretary Problem and Prophet Inequality with general constraints

2016-04-01

Aviad Rubinstein

We study generalizations of the Prophet Inequality and Secretary Problem, where the algorithm is restricted to an arbitrary downward-closed set system. For {0,1}-values, we give O(log n)-competitive algorithms for both … We study generalizations of the Prophet Inequality and Secretary Problem, where the algorithm is restricted to an arbitrary downward-closed set system. For {0,1}-values, we give O(log n)-competitive algorithms for both problems. This is close to the \Omega(log n / loglog n) lower bound due to Babaioff, Immorlica, and Kleinberg. For general values, our results translate to O(log n log r)-competitive algorithms, where r is the cardinality of the largest feasible set. This resolves (up to the O(log r loglog n) factors) an open question posed to us by Bobby Kleinberg.

Mechanism Design via Correlation Gap

2010-01-01

Qiqi Yan

For revenue and welfare maximization in single-dimensional Bayesian settings, Chawla et al. (STOC10) recently showed that sequential posted-price mechanisms (SPMs), though simple in form, can perform surprisingly well compared to … For revenue and welfare maximization in single-dimensional Bayesian settings, Chawla et al. (STOC10) recently showed that sequential posted-price mechanisms (SPMs), though simple in form, can perform surprisingly well compared to the optimal mechanisms. In this paper, we give a theoretical explanation of this fact, based on a connection to the notion of correlation gap. Loosely speaking, for auction environments with matroid constraints, we can relate the performance of a mechanism to the expectation of a monotone submodular function over a random set. This random set corresponds to the winner set for the optimal mechanism, which is highly correlated, and corresponds to certain demand set for SPMs, which is independent. The notion of correlation gap of Agrawal et al.\ (SODA10) quantifies how much we {}"lose" in the expectation of the function by ignoring correlation in the random set, and hence bounds our loss in using certain SPM instead of the optimal mechanism. Furthermore, the correlation gap of a monotone and submodular function is known to be small, and it follows that certain SPM can approximate the optimal mechanism by a good constant factor. Exploiting this connection, we give tight analysis of a greedy-based SPM of Chawla et al.\ for several environments. In particular, we show that it gives an $e/(e-1)$-approximation for matroid environments, gives asymptotically a $1/(1-1/\sqrt{2\pi k})$-approximation for the important sub-case of $k$-unit auctions, and gives a $(p+1)$-approximation for environments with $p$-independent set system constraints.

View PDF Chat

Quantum amplitude amplification and estimation

2002-01-01

Gilles Brassard , Peter Høyer , Michele Mosca +1 more

Consider a Boolean function $χ: X \to \{0,1\}$ that partitions set $X$ between its good and bad elements, where $x$ is good if $χ(x)=1$ and bad otherwise. Consider also a … Consider a Boolean function $χ: X \to \{0,1\}$ that partitions set $X$ between its good and bad elements, where $x$ is good if $χ(x)=1$ and bad otherwise. Consider also a quantum algorithm $\mathcal A$ such that $A |0\rangle= \sum_{x\in X} α_x |x\rangle$ is a quantum superposition of the elements of $X$, and let $a$ denote the probability that a good element is produced if $A |0\rangle$ is measured. If we repeat the process of running $A$, measuring the output, and using $χ$ to check the validity of the result, we shall expect to repeat $1/a$ times on the average before a solution is found. *Amplitude amplification* is a process that allows to find a good $x$ after an expected number of applications of $A$ and its inverse which is proportional to $1/\sqrt{a}$, assuming algorithm $A$ makes no measurements. This is a generalization of Grover's searching algorithm in which $A$ was restricted to producing an equal superposition of all members of $X$ and we had a promise that a single $x$ existed such that $χ(x)=1$. Our algorithm works whether or not the value of $a$ is known ahead of time. In case the value of $a$ is known, we can find a good $x$ after a number of applications of $A$ and its inverse which is proportional to $1/\sqrt{a}$ even in the worst case. We show that this quadratic speedup can also be obtained for a large family of search problems for which good classical heuristics exist. Finally, as our main result, we combine ideas from Grover's and Shor's quantum algorithms to perform amplitude estimation, a process that allows to estimate the value of $a$. We apply amplitude estimation to the problem of *approximate counting*, in which we wish to estimate the number of $x\in X$ such that $χ(x)=1$. We obtain optimal quantum algorithms in a variety of settings.

View PDF Chat

Online Independent Set Beyond the Worst-Case: Secretaries, Prophets, and Periods

2014-01-01

Oliver Göbel , Martin Hoefer , Thomas Keßelheim +2 more

View PDF Chat

Matroid prophet inequalities

2012-05-19

Robert Kleinberg , S. Matthew Weinberg

Consider a gambler who observes a sequence of independent, non-negative random numbers and is allowed to stop the sequence at any time, claiming a reward equal to the most recent … Consider a gambler who observes a sequence of independent, non-negative random numbers and is allowed to stop the sequence at any time, claiming a reward equal to the most recent observation. The famous prophet inequality of Krengel, Sucheston, and Garling asserts that a gambler who knows the distribution of each random variable can achieve at least half as much reward, in expectation, as a "prophet" who knows the sampled values of each random variable and can choose the largest one. We generalize this result to the setting in which the gambler and the prophet are allowed to make more than one selection, subject to a matroid constraint. We show that the gambler can still achieve at least half as much reward as the prophet; this result is the best possible, since it is known that the ratio cannot be improved even in the original prophet inequality, which corresponds to the special case of rank-one matroids. Generalizing the result still further, we show that under an intersection of $p$ matroid constraints, the prophet's reward exceeds the gambler's by a factor of at most $O(p)$, and this factor is also tight.

View PDF Chat

Polymatroid Prophet Inequalities

2015-01-01

Paul Dütting , Robert Kleinberg

View PDF Chat

Approximating Edit Distance in Near-Linear Time

2012-01-01

Alexandr Andoni , Krzysztof Onak

We show how to compute the edit distance between two strings of length $n$ up to a factor of $2^{\tilde{O}(\sqrt{\log n})}$ in $n^{1+o(1)}$ time. This is the first subpolynomial approximation … We show how to compute the edit distance between two strings of length $n$ up to a factor of $2^{\tilde{O}(\sqrt{\log n})}$ in $n^{1+o(1)}$ time. This is the first subpolynomial approximation algorithm for this problem that runs in near-linear time, improving on the state-of-the-art $n^{1/3+o(1)}$ approximation. Previously, approximation of $2^{\tilde{O}(\sqrt{\log n})}$ was known only for embedding edit distance into $\ell_1$, and it is not known if that embedding can be computed in less than quadratic time.

View PDF Chat

Prophet-type inequalities for multi-choice optimal stopping

1987-02-01

Douglas P. Kennedy

Comparison of optimal value and constrained maxima expectations for independent random variables

1986-06-01

Robert P. Kertz

For all uniformly bounded sequences of independent random variables X 1 , X 2, ···, a complete comparison is made between the optimal value V ( X 1 , X … For all uniformly bounded sequences of independent random variables X 1 , X 2, ···, a complete comparison is made between the optimal value V ( X 1 , X 2 , ···) = sup { EX t :t is an (a.e.) finite stop rule for X 1, X 2 , ···} and , where M i ( X 1, X 2 , ···) is the i th largest order statistic for X 1 , X 2 , ··· In particular, for k&gt; 1, the set of ordered pairs {( x , y ): x = V ( X 1 , X 2, ···) and for some independent random variables X 1 , X 2 , ··· taking values in [0, 1]} is precisely the set , where B k (0) = 0, B k (1) = 1, and for The result yields sharp, universal inequalities for independent random variables comparing two choice mechanisms, the mortal&amp;s value of the game V ( X 1 , X 2, ···) and the prophet&amp;s constrained maxima expectation of the game . Techniques of proof include probability- and convexity-based reductions; calculus-based, multivariate, extremal problem analysis; and limit theorems of Poisson-approximation type. Precise results are also given for finite sequences of independent random variables.

Polylogarithmic Approximation for Edit Distance and the Asymmetric Query Complexity

2010-10-01

Alexandr Andoni , Robert Krauthgamer , Krzysztof Onak

We present a near-linear time algorithm that approximates the edit distance between two strings within a polylogarithmic factor. For strings of length n and every fixed ε >; 0, the … We present a near-linear time algorithm that approximates the edit distance between two strings within a polylogarithmic factor. For strings of length n and every fixed ε >; 0, the algorithm computes a (log n) O(1/ε) approximation in n 1+ε time. This is an exponential improvement over the previously known approximation factor, 2 Õ (√log n) , with a comparable running time [Ostrovsky and Rabani, J. ACM 2007; Andoni and Onak, STOC 2009]. This result arises naturally in the study of a new asymmetric query model. In this model, the input consists of two strings x and y, and an algorithm can access y in an unrestricted manner, while being charged for querying every symbol of x. Indeed, we obtain our main result by designing an algorithm that makes a small number of queries in this model. We then provide a nearly-matching lower bound on the number of queries. Our lower bound is the first to expose hardness of edit distance stemming from the input strings being "repetitive", which means that many of their substrings are approximately identical. Consequently, our lower bound provides the first rigorous separation between edit distance and Ulam distance.

View PDF Chat

Bicriteria Network Design Problems

1998-07-01

Madhav Marathe , R. Ravi , Ravi Sundaram +3 more

View PDF Chat

Quantum algorithms for shortest paths problems in structured instances.

2014-10-23

Aran Nayebi , Virginia Vassilevska Williams

We consider the quantum time complexity of the all pairs shortest paths (APSP) problem and some of its variants. The trivial classical algorithm for APSP and most all pairs path … We consider the quantum time complexity of the all pairs shortest paths (APSP) problem and some of its variants. The trivial classical algorithm for APSP and most all pairs path problems runs in $O(n^3)$ time, while the trivial algorithm in the quantum setting runs in $\tilde{O}(n^{2.5})$ time, using Grover search. A major open problem in classical algorithms is to obtain a truly subcubic time algorithm for APSP, i.e. an algorithm running in $O(n^{3-\varepsilon})$ time for constant $\varepsilon>0$. To approach this problem, many truly subcubic time classical algorithms have been devised for APSP and its variants for structured inputs. Some examples of such problems are APSP in geometrically weighted graphs, graphs with small integer edge weights or a small number of weights incident to each vertex, and the all pairs earliest arrivals problem. In this paper we revisit these problems in the quantum setting and obtain the first nontrivial (i.e. $O(n^{2.5-\varepsilon})$ time) quantum algorithms for the problems.

Beating 1-1/e for ordered prophets

2017-06-15

Melika Abolhassani , Soheil Ehsani , Hossein Esfandiari +3 more

View PDF Chat

Online mixed packing and covering

2013-01-06

Yossi Azar , Umang Bhaskar , Lisa Fleischer +1 more

Recent work has shown that the classical framework of solving optimization problems by obtaining a fractional solution to a linear program (LP) and rounding it to an integer solution can … Recent work has shown that the classical framework of solving optimization problems by obtaining a fractional solution to a linear program (LP) and rounding it to an integer solution can be extended to the online setting using primal-dual techniques. The success of this new framework for online optimization can be gauged from the fact that it has led to progress in several longstanding open questions. However, to the best of our knowledge, this framework has previously been applied to LPs containing only packing or only covering constraints, or minor variants of these. We extend this framework in a fundamental way by demonstrating that it can be used to solve mixed packing and covering LPs online, where packing constraints are given offline and covering constraints are received online. The objective is to minimize the maximum multiplicative factor by which any packing constraint is violated, while satisfying the covering constraints. Our results represent the first algorithm that obtains a polylogarithmic competitive ratio for solving mixed LPs online.We then consider two canonical examples of mixed LPs: unrelated machine scheduling with startup costs, and capacity constrained facility location. We use ideas generated from our result for mixed packing and covering to obtain polylogarithmic-competitive algorithms for these problems. We also give lower bounds to show that the competitive ratios of our algorithms are nearly tight.

O(log log rank) Competitive-Ratio for the Matroid Secretary Problem

2014-03-26

Oded Lachish

In the \textit{Matroid Secretary Problem} (MSP), the elements of the ground set of a Matroid are revealed on-line one by one, each together with its value. An algorithm for the … In the \textit{Matroid Secretary Problem} (MSP), the elements of the ground set of a Matroid are revealed on-line one by one, each together with its value. An algorithm for the MSP is \textit{Matroid-Unknown} if, at every stage of its execution: (i) it only knows the elements that have been revealed so far and their values, and (ii) it has access to an oracle for testing whether or not any subset of the elements that have been revealed so far is an independent set. An algorithm is \textit{Known-Cardinality} if, in addition to (i) and (ii), it also initially knows the cardinality of the ground set of the Matroid. We present here a Known-Cardinality and \textit{Order-Oblivious} algorithm that, with constant probability, selects an independent set of elements, whose value is at least the optimal value divided by $O(\log{\log{\rho}})$, where $\rho$ is the rank of the Matroid; that is, the algorithm has a \textit{competitive-ratio} of $O(\log{\log{\rho}})$. The best previous results for a Known-Cardinality algorithm are a competitive-ratio of $O(\log{\rho})$, by Babaioff \textit{et al.} (2007), and a competitive-ratio of $O(\sqrt{\log{\rho}})$, by Chakraborty and Lachish (2012). In many non-trivial cases the algorithm we present has a competitive-ratio that is better than the $O(\log{\log{\rho}})$. The cases in which it fails to do so are easily characterized. Understanding these cases may lead to improved algorithms for the problem or, conversely, to non-trivial lower bounds.

Tight Hardness for Shortest Cycles and Paths in Sparse Graphs

2018-01-01

Andrea Lincoln , Virginia Vassilevska Williams , Ryan Williams

Fine-grained reductions have established equivalences between many core problems with Õ(n3)-time algorithms on n-node weighted graphs, such as Shortest Cycle, All-Pairs Shortest Paths (APSP), Radius, Replacement Paths, Second Shortest Paths, … Fine-grained reductions have established equivalences between many core problems with Õ(n3)-time algorithms on n-node weighted graphs, such as Shortest Cycle, All-Pairs Shortest Paths (APSP), Radius, Replacement Paths, Second Shortest Paths, and so on. These problems also have Õ(mn)-time algorithms on m-edge n-node weighted graphs, and such algorithms have wider applicability. Are these mn bounds optimal when m << n2?Starting from the hypothesis that the minimum weight (2ℓ + 1)-Clique problem in edge weighted graphs requires n2ℓ+1–o(1) time, we prove that for all sparsities of the form m = Θ(n1+1/ℓ), there is no O(n2 + mn1–ε) time algorithm for ε > 0 for any of the below problems•• Minimum Weight (2ℓ + 1)-Cycle in a directed weighted graph,•• Shortest Cycle in a directed weighted graph,•• APSP in a directed or undirected weighted graph,•• Radius (or Eccentricities) in a directed or undirected weighted graph,•• Wiener index of a directed or undirected weighted graph,•• Replacement Paths in a directed weighted graph,•• Second Shortest Path in a directed weighted graph,•• Betweenness Centrality of a given node in a directed weighted graph.That is, we prove hardness for a variety of sparse graph problems from the hardness of a dense graph problem. Our results also lead to new conditional lower bounds from several related hypothesis for unweighted sparse graph problems including k-cycle, shortest cycle, Radius, Wiener index and APSP.

View PDF Chat

If the Current Clique Algorithms are Optimal, So is Valiant's Parser

2015-10-01

Amir Abboud , Artūrs Bačkurs , Virginia Vassilevska Williams

The CFG recognition problem is: given a context-free grammar G and a string w of length n, decide if w can be obtained from G. This is the most basic … The CFG recognition problem is: given a context-free grammar G and a string w of length n, decide if w can be obtained from G. This is the most basic parsing question and is a core computer science problem. Valiant's parser from 1975 solves the problem in O(nO) time, where ? <; 2:373 is the matrix multiplication exponent. Dozens of parsing algorithms have been proposed over the years, yet Valiant's upper bound remains unbeaten. The best combinatorial algorithms have mildly subcubic O(n3= log3 n) complexity. Lee (JACM'01) provided evidence that fast matrix multiplication is needed for CFG parsing, and that very efficient and practical algorithms might be hard or even impossible to obtain. Lee showed that any algorithm for a more general parsing problem with running time O(|G| n3 -- e) can be converted into a surprising subcubic algorithm for Boolean Matrix Multiplication. Unfortunately, Lee' s hardness result required that the grammar size be |G| = O(n6). Nothing was known for the more relevant case of constant size grammars. In this work, we prove that any improvement on Valiant' s algorithm, even for constant size grammars, either in terms of runtime or by avoiding the inefficiencies of fast matrix multiplication, would imply a breakthrough algorithm for the k-Clique problem: given a graph on n nodes, decide if there are k that form a clique. Besides classifying the complexity of a fundamental problem, our reduction has led us to similar lower bounds for more modern and well-studied cubic time problems for which faster algorithms are highly desirable in practice: RNA Folding, a central problem in computational biology, and Dyck Language Edit Distance, answering an open question of Saha (FOCS'14).

View PDF Chat

Prophet Inequalities Made Easy: Stochastic Optimization by Pricing Non-Stochastic Inputs

2017-10-01

Paul Dütting , Michal Feldman , Thomas Keßelheim +1 more

We present a general framework for stochastic online maximization problems with combinatorial feasibility constraints. The framework establishes prophet inequalities by constructing price-based online approximation algorithms, a natural extension of threshold … We present a general framework for stochastic online maximization problems with combinatorial feasibility constraints. The framework establishes prophet inequalities by constructing price-based online approximation algorithms, a natural extension of threshold algorithms for settings beyond binary selection. Our analysis takes the form of an extension theorem: we derive sufficient conditions on prices when all weights are known in advance, then prove that the resulting approximation guarantees extend directly to stochastic settings. Our framework unifies and simplifies much of the existing literature on prophet inequalities and posted price mechanisms, and is used to derive new and improved results for combinatorial markets (with and without complements), multi-dimensional matroids, and sparse packing problems. Finally, we highlight a surprising connection between the smoothness framework for bounding the price of anarchy of mechanisms and our framework, and show that many smooth mechanisms can be recast as posted price mechanisms with comparable performance guarantees.

View PDF Chat

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

2018-10-01

Diptarka Chakraborty , Debarati Das , Elazar Goldenberg +2 more

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

View PDF Chat

Approximation Algorithms for LCS and LIS with Truly Improved Running Times

2019-11-01

Aviad Rubinstein , Saeed Seddighin , Zhao Song +1 more

Longest common subsequence (LCS) is a classic and central problem in combinatorial optimization. While LCS admits a quadratic time solution, recent evidence suggests that solving the problem may be impossible … Longest common subsequence (LCS) is a classic and central problem in combinatorial optimization. While LCS admits a quadratic time solution, recent evidence suggests that solving the problem may be impossible in truly subquadratic time. A special case of LCS wherein each character appears at most once in every string is equivalent to the longest increasing subsequence problem (LIS) which can be solved in quasilinear time. In this work, we present novel algorithms for approximating LCS in truly subquadratic time and LIS in truly sublinear time. Our approximation factors depend on the ratio of the optimal solution size over the input size. We denote this ratio by λ and obtain the following results for LCS and LIS without any prior knowledge of λ. • A truly subquadratic time algorithm for LCS with approximation factor O(λ^3). • A truly sublinear time algorithm for LIS with approximation factor O(λ^3). Triangle inequality was recently used by Boroujeni et al. [1] and Chakraborty et al.[2] to present new approximation algorithms for edit distance. Our techniques for LCS extend the notion of triangle inequality to non-metric settings.

View PDF Chat

Sublinear Algorithms for Gap Edit Distance

2019-11-01

Elazar Goldenberg , Robert Krauthgamer , Barna Saha

The edit distance is a way of quantifying how similar two strings are to one another by counting the minimum number of character insertions, deletions, and substitutions required to transform … The edit distance is a way of quantifying how similar two strings are to one another by counting the minimum number of character insertions, deletions, and substitutions required to transform one string into the other. A simple dynamic programming computes the edit distance between two strings of length n in O(n2) time, and a more sophisticated algorithm runs in time O(n + t2) when the edit distance is t [Landau, Myers and Schmidt, SICOMP 1998]. In pursuit of obtaining faster running time, the last couple of decades have seen a flurry of research on approximating edit distance, including polylogarithmic approximation in near-linear time [Andoni, Krauthgamer and Onak, FOCS 2010], and a constant-factor approximation in subquadratic time [Chakrabarty, Das, Goldenberg, Kouck´y and Saks, FOCS 2018]. We study sublinear-time algorithms for small edit distance, which was investigated extensively because of its numerous applications. Our main result is an algorithm for distinguishing whether the edit distance is at most t or at least t^2 (the quadratic gap problem) in time Õ(n/t+t^3). This time bound is sublinear roughly for all t in [ω(1), o(n^1/3)], which was not known before. The best previous algorithms solve this problem in sublinear time only for t=ω(n^1/3) [Andoni and Onak, STOC 2009]. Our algorithm is based on a new approach that adaptively switches between uniform sampling and reading contiguous blocks of the input strings. In contrast, all previous algorithms choose which coordinates to query non-adaptively. Moreover, it can be extended to solve the t vs t^2-ε gap problem in time Õ(n/t^1-ε+t^3).

View PDF Chat

Asymmetric Streaming Algorithms for Edit Distance and LCS

2020-02-26

Alireza Farhadi , MohammadTaghi Hajiaghayi , Aviad Rubinstein +1 more

The edit distance (ED) and longest common subsequence (LCS) are two fundamental problems which quantify how similar two strings are to one another. In this paper, we consider these problems … The edit distance (ED) and longest common subsequence (LCS) are two fundamental problems which quantify how similar two strings are to one another. In this paper, we consider these problems in the asymmetric streaming model introduced by Andoni et al. (FOCS'10) and Saks and Seshadhri (SODA'13). In this model we have random access to one string and streaming access the other string. Our main contribution is a constant factor approximation algorithm for ED with the memory of $\tilde O(n^{\delta})$ for any constant $\delta > 0$. In addition to this, we present an upper bound of $\tilde O_\epsilon(\sqrt{n})$ on the memory needed to approximate ED or LCS within a factor $1+\epsilon$. All our algorithms are deterministic and run in a single pass. For approximating ED within a constant factor, we discover yet another application of triangle inequality, this time in the context of streaming algorithms. Triangle inequality has been previously used to obtain subquadratic time approximation algorithms for ED. Our technique is novel and elegantly utilizes triangle inequality to save memory at the expense of an exponential increase in the runtime.

Constant-factor approximation of near-linear edit distance in near-linear time

2020-06-07

Joshua Brakensiek , Aviad Rubinstein

We show that the edit distance between two strings of length n can be computed via a randomized algorithm within a factor of f(є) in n 1+є time as long … We show that the edit distance between two strings of length n can be computed via a randomized algorithm within a factor of f(є) in n 1+є time as long as the edit distance is at least n 1−δ for some δ(є) > 0.

View PDF Chat

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

2020-06-06

Michal Koucký , Michael 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 … 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).

View PDF Chat

Does preprocessing help in fast sequence comparisons?

2020-06-07

Elazar Goldenberg , Aviad Rubinstein , Barna Saha

We study edit distance computation with preprocessing: the preprocessing algorithm acts on each string separately, and then the query algorithm takes as input the two preprocessed strings. This model is … We study edit distance computation with preprocessing: the preprocessing algorithm acts on each string separately, and then the query algorithm takes as input the two preprocessed strings. This model is inspired by scenarios where we would like to compute edit distance between many pairs in the same pool of strings.

View PDF Chat

Prophet Secretary

2015-07-05

Hossein Esfandiari , MohammadTaghi Hajiaghayi , Vahid Liaghat +1 more

Optimal stopping theory is a powerful tool for analyzing scenarios such as online auctions in which we generally require optimizing an objective function over the space of stopping rules for … Optimal stopping theory is a powerful tool for analyzing scenarios such as online auctions in which we generally require optimizing an objective function over the space of stopping rules for an allocation process under uncertainty. Perhaps the most classic problems of stopping theory are the prophet inequality problem and the secretary problem. The classical prophet inequality states that by choosing the same threshold OPT/2 for every step, one can achieve the tight competitive ratio of 0.5. On the other hand, for the basic secretary problem, the optimal strategy achieves the tight competitive ratio of 1/e. In this paper, we introduce Prophet Secretary, a natural combination of the prophet inequality and the secretary problems. An example motivation for our problem is as follows. Consider a seller that has an item to sell on the market to a set of arriving customers. The seller knows the types of customers that may be interested in the item and he has a price distribution for each type: the price offered by a customer of a type is anticipated to be drawn from the corresponding distribution. However, the customers arrive in a random order. Upon the arrival of a customer, the seller makes an irrevocable decision whether to sell the item at the offered price. We address the question of finding a strategy for selling the item at a high price. We show that by using a uniform threshold one cannot break the 0.5 barrier. However, we show that i) using n distinct non-adaptive thresholds one can obtain a competitive ratio that goes to (1-1/e) as n grows; and ii) no online algorithm can achieve a competitive ratio better than 0.75. Our results improve the (asymptotic) approximation guarantee of single-item sequential posted pricing mechanisms from 0.5 to (1-1/e) when the order of agents (customers) is chosen randomly.

A Simple Sublinear Algorithm for Gap Edit Distance.

2020-07-28

Joshua Brakensiek , Moses Charikar , Aviad Rubinstein

We study the problem of estimating the edit distance between two $n$-character strings. While exact computation in the worst case is believed to require near-quadratic time, previous work showed that … We study the problem of estimating the edit distance between two $n$-character strings. While exact computation in the worst case is believed to require near-quadratic time, previous work showed that in certain regimes it is possible to solve the following {\em gap edit distance} problem in sub-linear time: distinguish between inputs of distance $\le k$ and $>k^2$. Our main result is a very simple algorithm for this benchmark that runs in time $\tilde O(n/\sqrt{k})$, and in particular settles the open problem of obtaining a truly sublinear time for the entire range of relevant $k$. Building on the same framework, we also obtain a $k$-vs-$k^2$ algorithm for the one-sided preprocessing model with $\tilde O(n)$ preprocessing time and $\tilde O(n/k)$ query time (improving over a recent $\tilde O(n/k+k^2)$-query time algorithm for the same problem [GRS'20].

Approximating Edit Distance Within Constant Factor in Truly Sub-quadratic Time

2020-10-29

Diptarka Chakraborty , Debarati Das , Elazar Goldenberg +2 more

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 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 article, we provide an algorithm with running time Õ( n 2−2/7 ) that approximates the edit distance within a constant factor.

View PDF Chat

Nested Quantum Walks with Quantum Data Structures

2013-01-06

Stacey Jeffery , Robin Kothari , Frédéric Magniez

We develop a new framework that extends the quantum walk framework of Magniez, Nayak, Roland, and Santha, by utilizing the idea of quantum data structures to construct an efficient method … We develop a new framework that extends the quantum walk framework of Magniez, Nayak, Roland, and Santha, by utilizing the idea of quantum data structures to construct an efficient method of nesting quantum walks. Surprisingly, only classical data structures were considered before for searching via quantum walks. The recently proposed learning graph framework of Belovs has yielded improved upper bounds for several problems, including triangle finding and more general subgraph detection. We exhibit the power of our framework by giving a simple explicit constructions that reproduce both the $O(n^{35/27})$ and $O(n^{9/7})$ learning graph upper bounds (up to logarithmic factors) for triangle finding, and discuss how other known upper bounds in the original learning graph framework can be converted to algorithms in our framework. We hope that the ease of use of this framework will lead to the discovery of new upper bounds.

View PDF Chat

Stochastic k-Server Problem: How Should Uber Work?

2017-05-16

Sina Dehghani , Soheil Ehsani , MohammadTaghi Hajiaghayi +2 more

Near-linear time insertion-deletion codes and (1+ ε )-approximating edit distance via indexing

2019-06-20

Bernhard Haeupler , Aviad Rubinstein , Amirbehshad Shahrasbi

We introduce fast-decodable indexing schemes for edit distance which can be used to speed up edit distance computations to near-linear time if one of the strings is indexed by an … We introduce fast-decodable indexing schemes for edit distance which can be used to speed up edit distance computations to near-linear time if one of the strings is indexed by an indexing string $I$. In particular, for every length $n$ and every $\varepsilon >0$, one can in near linear time construct a string $I \in \Sigma'^n$ with $|\Sigma'| = O_{\varepsilon}(1)$, such that, indexing any string $S \in \Sigma^n$, symbol-by-symbol, with $I$ results in a string $S' \in \Sigma''^n$ where $\Sigma'' = \Sigma \times \Sigma'$ for which edit distance computations are easy, i.e., one can compute a $(1+\varepsilon)$-approximation of the edit distance between $S'$ and any other string in $O(n \text{poly}(\log n))$ time. Our indexing schemes can be used to improve the decoding complexity of state-of-the-art error correcting codes for insertions and deletions. In particular, they lead to near-linear time decoding algorithms for the insertion-deletion codes of [Haeupler, Shahrasbi; STOC `17] and faster decoding algorithms for list-decodable insertion-deletion codes of [Haeupler, Shahrasbi, Sudan; ICALP `18]. Interestingly, the latter codes are a crucial ingredient in the construction of fast-decodable indexing schemes.

View PDF Chat

Better Algorithms for Unfair Metrical Task Systems and Applications

2003-01-01

Amos Fiat , Manor Mendel

Unfair metrical task systems are a generalization of online metrical task systems. In this paper we introduce new techniques to combine algorithms for unfair metrical task systems and apply these … Unfair metrical task systems are a generalization of online metrical task systems. In this paper we introduce new techniques to combine algorithms for unfair metrical task systems and apply these techniques to obtain improved randomized online algorithms for metrical task systems on arbitrary metric spaces.

View PDF Chat

Polynomial-Time Algorithms for Prime Factorization and Discrete Logarithms on a Quantum Computer

1997-10-01

Peter W. Shor

A digital computer is generally believed to be an efficient universal computing device; that is, it is believed able to simulate any physical computing device with an increase in computation … A digital computer is generally believed to be an efficient universal computing device; that is, it is believed able to simulate any physical computing device with an increase in computation time of at most a polynomial factor. This may not be true when quantum mechanics is taken into consideration. This paper considers factoring integers and finding discrete logarithms, two problems which are generally thought to be hard on a classical computer and have been used as the basis of several proposed cryptosystems. Efficient randomized algorithms are given for these two problems on a hypothetical quantum computer. These algorithms take a number of steps polynomial in the input size, e.g., the number of digits of the integer to be factored.

View PDF Chat

Descending Price Optimally Coordinates Search

2016-07-21

Robert Kleinberg , Bo Waggoner , E. Glen Weyl

Investigating potential purchases, such as a start-up company to acquire, is often a substantial investment under uncertainty. Standard market designs, such as simultaneous or ascending price auctions, compound this with … Investigating potential purchases, such as a start-up company to acquire, is often a substantial investment under uncertainty. Standard market designs, such as simultaneous or ascending price auctions, compound this with additional uncertainty about the eventual price a bidder will have to pay in order to win. As a result they tend to confuse the process of search by leading to both wasteful information acquisition on goods that have already found a good purchaser and discouraging needed investigations of objects, potentially eliminating all gains from trade. Fully efficient procedures that avoid these problems, such as dynamic Vickrey-Clarke-Groves processes, are extremely complex and fragile. By contrast, we show that the Dutch auction preserves all of its properties from a standard setting without information costs because it guarantees, at the time of information acquisition, a price at which the good can be purchased.

View PDF Chat

Edit Distance in Near-Linear Time: it's a Constant Factor

2020-11-01

Alexandr Andoni , Negev Shekel Nosatzki

We present an algorithm for approximating the edit distance between two strings of length n in time n 1+ε , for any , up to a constant factor. … We present an algorithm for approximating the edit distance between two strings of length n in time n 1+ε , for any , up to a constant factor. Our result completes a research direction set forth in the recent breakthrough paper [1], which showed the first constant-factor approximation algorithm with a (strongly) sub-quadratic running time. The recent results [2], [3] have shown near-linear complexity only under the restriction that the edit distance is close to maximal (equivalently, there is a near-linear additive approximation). In contrast, our algorithm obtains a constant-factor approximation in near-linear running time for any input strings.

View PDF Chat

Sublinear-Time Algorithms for Computing & Embedding Gap Edit Distance

2020-11-01

Tomasz Kociumaka , Barna Saha

In this paper, we design new sublinear-time algorithms for solving the gap edit distance problem and for embedding edit distance to Hamming distance. For the gap edit distance problem, we … In this paper, we design new sublinear-time algorithms for solving the gap edit distance problem and for embedding edit distance to Hamming distance. For the gap edit distance problem, we give a greedy algorithm that distinguishes in time ~O([n/k]+k 2 ) between length-n input strings with edit distance at most k and those with edit distance more than 4k 2 . This is an improvement and a simplification upon the main result of [Goldenberg, Krauthgamer, Saha, FOCS 2019], where the k vs Θ(k 2 ) gap edit distance problem is solved in ~O([n/k]+k 3 ) time. We further generalize our result to solve the k vs αk gap edit distance problem in time ~O([n/(α)]+k 2 +[k/(α)]√{nk}), strictly improving upon the previously known bound ~O([n/(α)]+k 3 ). Finally, we show that if the input strings do not have long highly periodic substrings, then the gap edit distance problem can be solved in sublinear time within any factor . Specifically, if the strings contain no substring of length l with the shortest period of length at most 2k, then the k vs (1+ε)k gap edit distance problem can be solved in time ~O([n/(ε 2 k)]+k 2 l). We further give the first sublinear-time algorithm for the probabilistic embedding of edit distance to Hamming distance. Our ~O([n/p])-time procedure yields an embedding with distortion k 2 p, where k is the edit distance of the original strings. Specifically, the Hamming distance of the resultant strings is between [(k-p+1)/p] and k 2 with good probability. This generalizes the linear-time embedding of [Chakraborty, Goldenberg, Koucký, STOC 2016], where the resultant Hamming distance is between k and k 2 . Our algorithm is based on a random walk over samples, which we believe will find other applications in sublinear-time algorithms.

View PDF Chat

Quantum Amplitude Amplification and Estimation

2000-05-15

Gilles Brassard , Peter Høyer , Michele Mosca +1 more

Consider a Boolean function $\chi: X \to \{0,1\}$ that partitions set $X$ between its good and bad elements, where $x$ is good if $\chi(x)=1$ and bad otherwise. Consider also a … Consider a Boolean function $\chi: X \to \{0,1\}$ that partitions set $X$ between its good and bad elements, where $x$ is good if $\chi(x)=1$ and bad otherwise. Consider also a quantum algorithm $\mathcal A$ such that $A |0\rangle= \sum_{x\in X} \alpha_x |x\rangle$ is a quantum superposition of the elements of $X$, and let $a$ denote the probability that a good element is produced if $A |0\rangle$ is measured. If we repeat the process of running $A$, measuring the output, and using $\chi$ to check the validity of the result, we shall expect to repeat $1/a$ times on the average before a solution is found. *Amplitude amplification* is a process that allows to find a good $x$ after an expected number of applications of $A$ and its inverse which is proportional to $1/\sqrt{a}$, assuming algorithm $A$ makes no measurements. This is a generalization of Grover's searching algorithm in which $A$ was restricted to producing an equal superposition of all members of $X$ and we had a promise that a single $x$ existed such that $\chi(x)=1$. Our algorithm works whether or not the value of $a$ is known ahead of time. In case the value of $a$ is known, we can find a good $x$ after a number of applications of $A$ and its inverse which is proportional to $1/\sqrt{a}$ even in the worst case. We show that this quadratic speedup can also be obtained for a large family of search problems for which good classical heuristics exist. Finally, as our main result, we combine ideas from Grover's and Shor's quantum algorithms to perform amplitude estimation, a process that allows to estimate the value of $a$. We apply amplitude estimation to the problem of *approximate counting*, in which we wish to estimate the number of $x\in X$ such that $\chi(x)=1$. We obtain optimal quantum algorithms in a variety of settings.

Comparison of optimal value and constrained maxima expectations for independent random variables

1986-06-01

Robert P. Kertz

For all uniformly bounded sequences of independent random variables X 1 , X 2, ···, a complete comparison is made between the optimal value V ( X 1 , X … For all uniformly bounded sequences of independent random variables X 1 , X 2, ···, a complete comparison is made between the optimal value V ( X 1 , X 2 , ···) = sup { EX t :t is an (a.e.) finite stop rule for X 1, X 2 , ···} and , where M i ( X 1, X 2 , ···) is the i th largest order statistic for X 1 , X 2 , ··· In particular, for k> 1, the set of ordered pairs {( x , y ): x = V ( X 1 , X 2, ···) and for some independent random variables X 1 , X 2 , ··· taking values in [0, 1]} is precisely the set , where B k (0) = 0, B k (1) = 1, and for The result yields sharp, universal inequalities for independent random variables comparing two choice mechanisms, the mortal&s value of the game V ( X 1 , X 2, ···) and the prophet&s constrained maxima expectation of the game . Techniques of proof include probability- and convexity-based reductions; calculus-based, multivariate, extremal problem analysis; and limit theorems of Poisson-approximation type. Precise results are also given for finite sequences of independent random variables.