Subscribe to the gold package and get unlimited access to Shamra Academy
Register a new userApproximating the Largest Root and Applications to Interlacing Families
103
0
0.0
(
0
)
Added by
Nikhil Srivastava
Publication date
2017
fields
Informatics Engineering
and research's language is
English
Ask ChatGPT about the research
No Arabic abstract
We study the problem of approximating the largest root of a real-rooted polynomial of degree $n$ using its top $k$ coefficients and give nearly matching upper and lower bounds. We present algorithms with running time polynomial in $k$ that use the top $k$ coefficients to approximate the maximum root within a factor of $n^{1/k}$ and $1+O(tfrac{log n}{k})^2$ when $kleq log n$ and $k>log n$ respectively. We also prove corresponding information-theoretic lower bounds of $n^{Omega(1/k)}$ and $1+Omegaleft(frac{log frac{2n}{k}}{k}right)^2$, and show strong lower bounds for noisy version of the problem in which one is given access to approximate coefficients. This problem has applications in the context of the method of interlacing families of polynomials, which was used for proving the existence of Ramanujan graphs of all degrees, the solution of the Kadison-Singer problem, and bounding the integrality gap of the asymmetric traveling salesman problem. All of these involve computing the maximum root of certain real-rooted polynomials for which the top few coefficients are accessible in subexponential time. Our results yield an algorithm with the running time of $2^{tilde O(sqrt[3]n)}$ for all of them.
rate research
Read More
We show algorithms for computing representative families for matroid intersections and use them in fixed-parameter algorithms for set packing, set covering, and facility location problems with multiple matroid constraints. We complement our tractability results by hardness results.
We revisit a fundamental problem in string matching: given a pattern of length m and a text of length n, both over an alphabet of size $sigma$, compute the Hamming distance between the pattern and the text at every location. Several $(1+epsilon)$-approximation algorithms have been proposed in the literature, with running time of the form $O(epsilon^{-O(1)}nlog nlog m)$, all using fast Fourier transform (FFT). We describe a simple $(1+epsilon)$-approximation algorithm that is faster and does not need FFT. Combining our approach with additional ideas leads to numerous new results: - We obtain the first linear-time approximation algorithm; the running time is $O(epsilon^{-2}n)$. - We obtain a faster exact algorithm computing all Hamming distances up to a given threshold k; its running time improves previous results by logarithmic factors and is linear if $klesqrt m$. - We obtain approximation algorithms with better $epsilon$-dependence using rectangular matrix multiplication. The time-bound is $~O(n)$ when the pattern is sufficiently long: $mge epsilon^{-28}$. Previous algorithms require $~O(epsilon^{-1}n)$ time. - When k is not too small, we obtain a truly sublinear-time algorithm to find all locations with Hamming distance approximately (up to a constant factor) less than k, in $O((n/k^{Omega(1)}+occ)n^{o(1)})$ time, where occ is the output size. The algorithm leads to a property tester, returning true if an exact match exists and false if the Hamming distance is more than $delta m$ at every location, running in $~O(delta^{-1/3}n^{2/3}+delta^{-1}n/m)$ time. - We obtain a streaming algorithm to report all locations with Hamming distance approximately less than k, using $~O(epsilon^{-2}sqrt k)$ space. Previously, streaming algorithms were known for the exact problem with ~O(k) space or for the approximate problem with $~O(epsilon^{-O(1)}sqrt m)$ space.
We study approximation algorithms for variants of the emph{median string} problem, which asks for a string that minimizes the sum of edit distances from a given set of $m$ strings of length $n$. Only the straightforward $2$-approximation is known for this NP-hard problem. This problem is motivated e.g.~by computational biology, and belongs to the class of median problems (over different metric spaces), which are fundamental tasks in data analysis. Our main result is for the Ulam metric, where all strings are permutations over $[n]$ and each edit operation moves a symbol (deletion plus insertion). We devise for this problem an algorithms that breaks the $2$-approximation barrier, i.e., computes a $(2-delta)$-approximate median permutation for some constant $delta>0$ in time $tilde{O}(nm^2+n^3)$. We further use these techniques to achieve a $(2-delta)$ approximation for the median string problem in the special case where the median is restricted to length $n$ and the optimal objective is large $Omega(mn)$. We also design an approximation algorithm for the following probabilistic model of the Ulam median: the input consists of $m$ perturbations of an (unknown) permutation $x$, each generated by moving every symbol to a random position with probability (a parameter) $epsilon>0$. Our algorithm computes with high probability a $(1+o(1/epsilon))$-approximate median permutation in time $O(mn^2+n^3)$.
A bond of a graph $G$ is an inclusion-wise minimal disconnecting set of $G$, i.e., bonds are cut-sets that determine cuts $[S,Vsetminus S]$ of $G$ such that $G[S]$ and $G[Vsetminus S]$ are both connected. Given $s,tin V(G)$, an $st$-bond of $G$ is a bond whose removal disconnects $s$ and $t$. Contrasting with the large number of studies related to maximum cuts, there are very few results regarding the largest bond of general graphs. In this paper, we aim to reduce this gap on the complexity of computing the largest bond and the largest $st$-bond of a graph. Although cuts and bonds are similar, we remark that computing the largest bond of a graph tends to be harder than computing its maximum cut. We show that {sc Largest Bond} remains NP-hard even for planar bipartite graphs, and it does not admit a constant-factor approximation algorithm, unless $P = NP$. We also show that {sc Largest Bond} and {sc Largest $st$-Bond} on graphs of clique-width $w$ cannot be solved in time $f(w)times n^{o(w)}$ unless the Exponential Time Hypothesis fails, but they can be solved in time $f(w)times n^{O(w)}$. In addition, we show that both problems are fixed-parameter tractable when parameterized by the size of the solution, but they do not admit polynomial kernels unless NP $subseteq$ coNP/poly.
We present a randomized approximation scheme for the permanent of a matrix with nonnegative entries. Our scheme extends a recursive rejection sampling method of Huber and Law (SODA 2008) by replacing the upper bound for the permanent with a linear combination of the subproblem bounds at a moderately large depth of the recursion tree. This method, we call deep rejection sampling, is empirically shown to outperform the basic, depth-zero variant, as well as a related method by Kuck et al. (NeurIPS 2019). We analyze the expected running time of the scheme on random $(0, 1)$-matrices where each entry is independently $1$ with probability $p$. Our bound is superior to a previous one for $p$ less than $1/5$, matching another bound that was known to hold when every row and column has density exactly $p$.
Log in to be able to interact and post comments
comments
Fetching comments
Sign in to be able to follow your search criteria
