BZPEERPapers, people, evidence and research paths
Menu

Discover

SearchFind papers, people, topics, institutions and opportunities from one place.GraphSee how papers, authors, topics and evidence connect.

Research tools

HomeContinue from the papers, people and topics that matter now.CollectionsTurn saved papers into reading lists, evidence maps and shareable context.ResearchReconstruct the path that led you from search to paper to question.CollaborationMove from a paper, topic or expert request into a focused thread.PublishCreate full-text research articles with metadata, formulas and versions.

Network

ExpertsFind specialists whose work and reviews explain why they can help.CommunitiesJoin research groups organized around papers, topics and shared evidence.

Opportunities

ListingsBrowse roles, calls and collaborations connected to real research context.

Account

Log inReturn to your saved papers, graph views and active threads.Create accountStart saving papers, building a research trail and joining teams.
Log inCreate account

Source author record

Saeed Seddighin

Saeed Seddighin appears in the imported research catalog. Authorship, coauthor and topic links are available while profile ownership is still unclaimed.

ResearcherUnclaimed source record
Data Structures and AlgorithmsComputer Science and Game TheoryComputational ComplexityDiscrete MathematicsMachine Learning

Catalog footprint

What is connected

9works
5topics
4close collaborators

Actions

Connect this record

Log in to claim
Open graphBrowse works

Research graph

See the researcher in context

Open full explorer

Inspect adjacent papers, topics, institutions and collaborators without losing the researcher page.

Building this map preview

BZPEER is loading the nearby papers, people, topics and institutions for this page.

Published work

9 published item(s)

preprint2022arXiv

Dynamic Subset Sum with Truly Sublinear Processing Time

Subset sum is a very old and fundamental problem in theoretical computer science. In this problem, $n$ items with weights $w_1, w_2, w_3, \ldots, w_n$ are given as input and the goal is to find out if there is a subset of them whose weights sum up to a given value $t$. While the problem is NP-hard in general, when the values are non-negative integer, subset sum can be solved in pseudo-polynomial time $~\widetilde O(n+t)$. In this work, we consider the dynamic variant of subset sum. In this setting, an upper bound $\tmax$ is provided in advance to the algorithm and in each operation, either a new item is added to the problem or for a given integer value $t \leq \tmax$, the algorithm is required to output whether there is a subset of items whose sum of weights is equal to $t$. Unfortunately, none of the existing subset sum algorithms is able to process these operations in truly sublinear time\footnote{Truly sublinear means $n^{1-Ω(1)}$.} in terms of $\tmax$. Our main contribution is an algorithm whose amortized processing time\footnote{Since the runtimes are amortized, we do not use separate terms update time and query time for different operations and use processing time for all types of operations.} for each operation is truly sublinear in $\tmax$ when the number of operations is at least $\tmax^{2/3+Ω(1)}$. We also show that when both element addition and element removal are allowed, there is no algorithm that can process each operation in time $\tmax^{1-Ω(1)}$ on average unless \textsf{SETH}\footnote{The \textit{strong exponential time hypothesis} states that no algorithm can solve the satisfiability problem in time $2^{n(1-Ω(1))}$.} fails.

0 citations0 reviewsNo code linkedOpen access
preprint2021arXiv

Dynamic Longest Increasing Subsequence and the Erdös-Szekeres Partitioning Problem

In this paper, we provide new approximation algorithms for dynamic variations of the longest increasing subsequence (\textsf{LIS}) problem, and the complementary distance to monotonicity (\textsf{DTM}) problem. In this setting, operations of the following form arrive sequentially: (i) add an element, (ii) remove an element, or (iii) substitute an element for another. At every point in time, the algorithm has an approximation to the longest increasing subsequence (or distance to monotonicity). We present a $(1+ε)$-approximation algorithm for \textsf{DTM} with polylogarithmic worst-case update time and a constant factor approximation algorithm for \textsf{LIS} with worst-case update time $\tilde O(n^ε)$ for any constant $ε> 0$.% $n$ in the runtime denotes the size of the array at the time the operation arrives. Our dynamic algorithm for \textsf{LIS} leads to an almost optimal algorithm for the Erdös-Szekeres partitioning problem. Erdös-Szekeres partitioning problem was introduced by Erdös and Szekeres in 1935 and was known to be solvable in time $O(n^{1.5}\log n)$. Subsequent work improve the runtime to $O(n^{1.5})$ only in 1998. Our dynamic \textsf{LIS} algorithm leads to a solution for Erdös-Szekeres partitioning problem with runtime $\tilde O_ε(n^{1+ε})$ for any constant $ε> 0$.

0 citations0 reviewsNo code linkedOpen access
preprint2020arXiv

Approximating LCS in Linear Time: Beating the $\sqrt{n}$ Barrier

Longest common subsequence (LCS) is one of the most fundamental problems in combinatorial optimization. Apart from theoretical importance, LCS has enormous applications in bioinformatics, revision control systems, and data comparison programs. Although a simple dynamic program computes LCS in quadratic time, it has been recently proven that the problem admits a conditional lower bound and may not be solved in truly subquadratic time. In addition to this, LCS is notoriously hard with respect to approximation algorithms. Apart from a trivial sampling technique that obtains a $n^{x}$ approximation solution in time $O(n^{2-2x})$ nothing else is known for LCS. This is in sharp contrast to its dual problem edit distance for which several linear time solutions are obtained in the past two decades.

0 citations0 reviewsNo code linkedOpen access
preprint2020arXiv

Asymmetric Streaming Algorithms for Edit Distance and LCS

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^δ)$ for any constant $δ> 0$. In addition to this, we present an upper bound of $\tilde O_ε(\sqrt{n})$ on the memory needed to approximate ED or LCS within a factor $1+ε$. 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.

0 citations0 reviewsNo code linkedOpen access
preprint2020arXiv

Learning Complexity of Simulated Annealing

Simulated annealing is an effective and general means of optimization. It is in fact inspired by metallurgy, where the temperature of a material determines its behavior in thermodynamics. Likewise, in simulated annealing, the actions that the algorithm takes depend entirely on the value of a variable which captures the notion of temperature. Typically, simulated annealing starts with a high temperature, which makes the algorithm pretty unpredictable, and gradually cools the temperature down to become more stable. A key component that plays a crucial role in the performance of simulated annealing is the criteria under which the temperature changes namely, the cooling schedule. Motivated by this, we study the following question in this work: "Given enough samples to the instances of a specific class of optimization problems, can we design optimal (or approximately optimal) cooling schedules that minimize the runtime or maximize the success rate of the algorithm on average when the underlying problem is drawn uniformly at random from the same class?" We provide positive results both in terms of sample complexity and simulation complexity. For sample complexity, we show that $\tilde O(\sqrt{m})$ samples suffice to find an approximately optimal cooling schedule of length $m$. We complement this result by giving a lower bound of $\tilde Ω(m^{1/3})$ on the sample complexity of any learning algorithm that provides an almost optimal cooling schedule. These results are general and rely on no assumption. For simulation complexity, however, we make additional assumptions to measure the success rate of an algorithm. To this end, we introduce the monotone stationary graph that models the performance of simulated annealing. Based on this model, we present polynomial time algorithms with provable guarantees for the learning problem.

0 citations0 reviewsNo code linkedOpen access
preprint2016arXiv

A Tight Algorithm for Strongly Connected Steiner Subgraph On Two Terminals With Demands

Given an edge-weighted directed graph $G=(V,E)$ on $n$ vertices and a set $T=\{t_1, t_2, \ldots, t_p\}$ of $p$ terminals, the objective of the \scss ($p$-SCSS) problem is to find an edge set $H\subseteq E$ of minimum weight such that $G[H]$ contains an $t_{i}\rightarrow t_j$ path for each $1\leq i\neq j\leq p$. In this paper, we investigate the computational complexity of a variant of $2$-SCSS where we have demands for the number of paths between each terminal pair. Formally, the \sharinggeneral problem is defined as follows: given an edge-weighted directed graph $G=(V,E)$ with weight function $ω: E\rightarrow \mathbb{R}^{\geq 0}$, two terminal vertices $s, t$, and integers $k_1, k_2$ ; the objective is to find a set of $k_1$ paths $F_1, F_2, \ldots, F_{k_1}$ from $s\leadsto t$ and $k_2$ paths $B_1, B_2, \ldots, B_{k_2}$ from $t\leadsto s$ such that $\sum_{e\in E} ω(e)\cdot ϕ(e)$ is minimized, where $ϕ(e)= \max \Big\{|\{i\in [k_1] : e\in F_i\}|\ ,\ |\{j\in [k_2] : e\in B_j\}|\Big\}$. For each $k\geq 1$, we show the following: The \sharing problem can be solved in $n^{O(k)}$ time. A matching lower bound for our algorithm: the \sharing problem does not have an $f(k)\cdot n^{o(k)}$ algorithm for any computable function $f$, unless the Exponential Time Hypothesis (ETH) fails. Our algorithm for \sharing relies on a structural result regarding an optimal solution followed by using the idea of a "token game" similar to that of Feldman and Ruhl. We show with an example that the structural result does not hold for the \sharinggeneral problem if $\min\{k_1, k_2\}\geq 2$. Therefore \sharing is the most general problem one can attempt to solve with our techniques.

0 citations0 reviewsNo code linkedOpen access
preprint2016arXiv

Faster and Simpler Algorithm for Optimal Strategies of Blotto Game

In the Colonel Blotto game, which was initially introduced by Borel in 1921, two colonels simultaneously distribute their troops across different battlefields. The winner of each battlefield is determined independently by a winner-take-all rule. The ultimate payoff of each colonel is the number of battlefields he wins. This game is commonly used for analyzing a wide range of applications such as the U.S presidential election, innovative technology competitions, advertisements, etc. There have been persistent efforts for finding the optimal strategies for the Colonel Blotto game. After almost a century Ahmadinejad, Dehghani, Hajiaghayi, Lucier, Mahini, and Seddighin provided a poly-time algorithm for finding the optimal strategies. They first model the problem by a Linear Program (LP) and use Ellipsoid method to solve it. However, despite the theoretical importance of their algorithm, it is highly impractical. In general, even Simplex method (despite its exponential running-time) performs better than Ellipsoid method in practice. In this paper, we provide the first polynomial-size LP formulation of the optimal strategies for the Colonel Blotto game. We use linear extension techniques. Roughly speaking, we project the strategy space polytope to a higher dimensional space, which results in a lower number of facets for the polytope. We use this polynomial-size LP to provide a novel, simpler and significantly faster algorithm for finding the optimal strategies for the Colonel Blotto game. We further show this representation is asymptotically tight in terms of the number of constraints. We also extend our approach to multi-dimensional Colonel Blotto games, and implement our algorithm to observe interesting properties of Colonel Blotto; for example, we observe the behavior of players in the discrete model is very similar to the previously studied continuous model.

0 citations0 reviewsNo code linkedOpen access
preprint2016arXiv

Price of Competition and Dueling Games

We study competition in a general framework introduced by Immorlica et al. and answer their main open question. Immorlica et al. considered classic optimization problems in terms of competition and introduced a general class of games called dueling games. They model this competition as a zero-sum game, where two players are competing for a user's satisfaction. In their main and most natural game, the ranking duel, a user requests a webpage by submitting a query and players output an ordering over all possible webpages based on the submitted query. The user tends to choose the ordering which displays her requested webpage in a higher rank. The goal of both players is to maximize the probability that her ordering beats that of her opponent and gets the user's attention. Immorlica et al. show this game directs both players to provide suboptimal search results. However, they leave the following as their main open question: "does competition between algorithms improve or degrade expected performance?" In this paper, we resolve this question for the ranking duel and a more general class of dueling games. More precisely, we study the quality of orderings in a competition between two players. This game is a zero-sum game, and thus any Nash equilibrium of the game can be described by minimax strategies. Let the value of the user for an ordering be a function of the position of her requested item in the corresponding ordering, and the social welfare for an ordering be the expected value of the corresponding ordering for the user. We propose the price of competition which is the ratio of the social welfare for the worst minimax strategy to the social welfare obtained by a social planner. We use this criterion for analyzing the quality of orderings in the ranking duel. We prove the quality of minimax results is surprisingly close to that of the optimum solution.

0 citations0 reviewsNo code linkedOpen access
preprint2015arXiv

Revenue Maximization for Selling Multiple Correlated Items

We study the problem of selling $n$ items to a single buyer with an additive valuation function. We consider the valuation of the items to be correlated, i.e., desirabilities of the buyer for the items are not drawn independently. Ideally, the goal is to design a mechanism to maximize the revenue. However, it has been shown that a revenue optimal mechanism might be very complicated and as a result inapplicable to real-world auctions. Therefore, our focus is on designing a simple mechanism that achieves a constant fraction of the optimal revenue. Babaioff et al. propose a simple mechanism that achieves a constant fraction of the optimal revenue for independent setting with a single additive buyer. However, they leave the following problem as an open question: "Is there a simple, approximately optimal mechanism for a single additive buyer whose value for $n$ items is sampled from a common base-value distribution?" Babaioff et al. show a constant approximation factor of the optimal revenue can be achieved by either selling the items separately or as a whole bundle in the independent setting. We show a similar result for the correlated setting when the desirabilities of the buyer are drawn from a common base-value distribution. It is worth mentioning that the core decomposition lemma which is mainly the heart of the proofs for efficiency of the mechanisms does not hold for correlated settings. Therefore we propose a modified version of this lemma which is applicable to the correlated settings as well. Although we apply this technique to show the proposed mechanism can guarantee a constant fraction of the optimal revenue in a very weak correlation, this method alone can not directly show the efficiency of the mechanism in stronger correlations.

0 citations0 reviewsNo code linkedOpen access