Title: Algorithms for covering multiple submodular constraints and applications

Abstract

We consider the problem of covering multiple submodular constraints. Given a finite ground setN, a weight function$$w: N \rightarrow \mathbb {R}_+$$$w:N\to {R}_{+}$,rmonotone submodular functions$$f_1,f_2,\ldots ,f_r$$${f}_{1},{f}_{2},\dots ,{f}_{r}$overNand requirements$$k_1,k_2,\ldots ,k_r$$${k}_{1},{k}_{2},\dots ,{k}_{r}$the goal is to find a minimum weight subset$$S \subseteq N$$$S\subseteq N$such that$$f_i(S) \ge k_i$$${f}_{i}\left(S\right)\ge {k}_{i}$for$$1 \le i \le r$$$1\le i\le r$. We refer to this problem asMulti-Submod-Coverand it was recently considered by Har-Peled and Jones (Few cuts meet many point sets. CoRR.arxiv:abs1808.03260Har-Peled and Jones 2018) who were motivated by an application in geometry. Even with$$r=1$$$r=1$Multi-Submod-Covergeneralizes the well-known Submodular Set Cover problem (Submod-SC), and it can also be easily reduced toSubmod-SC. A simple greedy algorithm gives an$$O(\log (kr))$$$O(log(kr\left)\right)$approximation where$$k = \sum _i k_i$$$k={\sum}_{i}{k}_{i}$and this ratio cannot be improved in the general case. In this paper, motivated by several concrete applications, we consider two ways to improve upon the approximation given by the greedy algorithm. First, we give a bicriteria approximation algorithm forMulti-Submod-Coverthat covers each constraint to within a factor of$$(1-1/e-\varepsilon )$$$(1-1/e-\epsilon )$while incurring an approximation of$$O(\frac{1}{\epsilon }\log r)$$$O(\frac{1}{\u03f5}logr)$in the cost. Second, we consider the special case when each$$f_i$$${f}_{i}$is a obtained from a truncated coverage function and obtain an algorithm that generalizes previous work on partial set cover (Partial-SC), covering integer programs (CIPs) and multiple vertex cover constraints Bera et al. (Theoret Comput Sci 555:2–8 Bera et al. 2014). Both these algorithms are based on mathematical programming relaxations that avoid the limitations of the greedy algorithm. We demonstrate the implications of our algorithms and related ideas to several applications ranging from geometric covering problems to clustering with outliers. Our work highlights the utility of the high-level model and the lens of submodularity in addressing this class of covering problems.

Vyas, Nikhil; Williams, R. Ryan(
, Theory of Computing Systems)

Abstract

We continue the program of proving circuit lower bounds via circuit satisfiability algorithms. So far, this program has yielded several concrete results, proving that functions in$\mathsf {Quasi}\text {-}\mathsf {NP} = \mathsf {NTIME}[n^{(\log n)^{O(1)}}]$$\mathrm{Quasi}-\mathrm{NP}=\mathrm{NTIME}\left[{n}^{{\left(\mathrm{log}n\right)}^{O\left(1\right)}}\right]$and other complexity classes do not have small circuits (in the worst case and/or on average) from various circuit classes$\mathcal { C}$$C$, by showing that$\mathcal { C}$$C$admits non-trivial satisfiability and/or#SAT algorithms which beat exhaustive search by a minor amount. In this paper, we present a new strong lower bound consequence of having a non-trivial#SAT algorithm for a circuit class${\mathcal C}$$C$. Say that a symmetric Boolean functionf(x_{1},…,x_{n}) issparseif it outputs 1 onO(1) values of${\sum }_{i} x_{i}$${\sum}_{i}{x}_{i}$. We show that for every sparsef, and for all “typical”$\mathcal { C}$$C$, faster#SAT algorithms for$\mathcal { C}$$C$circuits imply lower bounds against the circuit class$f \circ \mathcal { C}$$f\circ C$, which may bestrongerthan$\mathcal { C}$$C$itself. In particular:

#SAT algorithms forn^{k}-size$\mathcal { C}$$C$-circuits running in 2^{n}/n^{k}time (for allk) implyNEXPdoes not have$(f \circ \mathcal { C})$$(f\circ C)$-circuits of polynomial size.

Applying#SAT algorithms from the literature, one immediate corollary of our results is thatQuasi-NPdoes not haveEMAJ∘ACC^{0}∘THRcircuits of polynomial size, whereEMAJis the “exact majority” function, improving previous lower bounds againstACC^{0}[Williams JACM’14] andACC^{0}∘THR[Williams STOC’14], [Murray-Williams STOC’18]. This is the first nontrivial lower bound against such a circuit class.

Approximate integer programming is the following: For a given convex body$$K \subseteq {\mathbb {R}}^n$$$K\subseteq {R}^{n}$, either determine whether$$K \cap {\mathbb {Z}}^n$$$K\cap {Z}^{n}$is empty, or find an integer point in the convex body$$2\cdot (K - c) +c$$$2\xb7(K-c)+c$which isK, scaled by 2 from its center of gravityc. Approximate integer programming can be solved in time$$2^{O(n)}$$${2}^{O\left(n\right)}$while the fastest known methods for exact integer programming run in time$$2^{O(n)} \cdot n^n$$${2}^{O\left(n\right)}\xb7{n}^{n}$. So far, there are no efficient methods for integer programming known that are based on approximate integer programming. Our main contribution are two such methods, each yielding novel complexity results. First, we show that an integer point$$x^* \in (K \cap {\mathbb {Z}}^n)$$${x}^{\ast}\in (K\cap {Z}^{n})$can be found in time$$2^{O(n)}$$${2}^{O\left(n\right)}$, provided that theremaindersof each component$$x_i^* \mod \ell $$${x}_{i}^{\ast}\phantom{\rule{0ex}{0ex}}mod\phantom{\rule{0ex}{0ex}}\ell $for some arbitrarily fixed$$\ell \ge 5(n+1)$$$\ell \ge 5(n+1)$of$$x^*$$${x}^{\ast}$are given. The algorithm is based on acutting-plane technique, iteratively halving the volume of the feasible set. The cutting planes are determined via approximate integer programming. Enumeration of the possible remainders gives a$$2^{O(n)}n^n$$${2}^{O\left(n\right)}{n}^{n}$algorithm for general integer programming. This matches the current best bound of an algorithm by Dadush (Integer programming, lattice algorithms, and deterministic, vol. Estimation. Georgia Institute of Technology, Atlanta, 2012) that is considerably more involved. Our algorithm also relies on a newasymmetric approximate Carathéodory theoremthat might be of interest on its own. Our second method concerns integer programming problems in equation-standard form$$Ax = b, 0 \le x \le u, \, x \in {\mathbb {Z}}^n$$$Ax=b,0\le x\le u,\phantom{\rule{0ex}{0ex}}x\in {Z}^{n}$. Such a problem can be reduced to the solution of$$\prod _i O(\log u_i +1)$$${\prod}_{i}O(log{u}_{i}+1)$approximate integer programming problems. This implies, for example thatknapsackorsubset-sumproblems withpolynomial variable range$$0 \le x_i \le p(n)$$$0\le {x}_{i}\le p\left(n\right)$can be solved in time$$(\log n)^{O(n)}$$${(logn)}^{O\left(n\right)}$. For these problems, the best running time so far was$$n^n \cdot 2^{O(n)}$$${n}^{n}\xb7{2}^{O\left(n\right)}$.

Dalzell, Alexander M.; Hunter-Jones, Nicholas; Brandão, Fernando G. S. L.(
, Communications in Mathematical Physics)

Abstract

We study the distribution over measurement outcomes of noisy random quantum circuits in the regime of low fidelity, which corresponds to the setting where the computation experiences at least one gate-level error with probability close to one. We model noise by adding a pair of weak, unital, single-qubit noise channels after each two-qubit gate, and we show that for typical random circuit instances, correlations between the noisy output distribution$$p_{\text {noisy}}$$${p}_{\text{noisy}}$and the corresponding noiseless output distribution$$p_{\text {ideal}}$$${p}_{\text{ideal}}$shrink exponentially with the expected number of gate-level errors. Specifically, the linear cross-entropy benchmarkFthat measures this correlation behaves as$$F=\text {exp}(-2s\epsilon \pm O(s\epsilon ^2))$$$F=\text{exp}(-2s\u03f5\pm O\left(s{\u03f5}^{2}\right))$, where$$\epsilon $$$\u03f5$is the probability of error per circuit location andsis the number of two-qubit gates. Furthermore, if the noise is incoherent—for example, depolarizing or dephasing noise—the total variation distance between the noisy output distribution$$p_{\text {noisy}}$$${p}_{\text{noisy}}$and the uniform distribution$$p_{\text {unif}}$$${p}_{\text{unif}}$decays at precisely the same rate. Consequently, the noisy output distribution can be approximated as$$p_{\text {noisy}}\approx Fp_{\text {ideal}}+ (1-F)p_{\text {unif}}$$${p}_{\text{noisy}}\approx F{p}_{\text{ideal}}+(1-F){p}_{\text{unif}}$. In other words, although at least one local error occurs with probability$$1-F$$$1-F$, the errors are scrambled by the random quantum circuit and can be treated as global white noise, contributing completely uniform output. Importantly, we upper bound the average total variation error in this approximation by$$O(F\epsilon \sqrt{s})$$$O\left(F\u03f5\sqrt{s}\right)$. Thus, the “white-noise approximation” is meaningful when$$\epsilon \sqrt{s} \ll 1$$$\u03f5\sqrt{s}\ll 1$, a quadratically weaker condition than the$$\epsilon s\ll 1$$$\u03f5s\ll 1$requirement to maintain high fidelity. The bound applies if the circuit size satisfies$$s \ge \Omega (n\log (n))$$$s\ge \Omega (nlog(n\left)\right)$, which corresponds to onlylogarithmic depthcircuits, and if, additionally, the inverse error rate satisfies$$\epsilon ^{-1} \ge {\tilde{\Omega }}(n)$$${\u03f5}^{-1}\ge \stackrel{~}{\Omega}\left(n\right)$, which is needed to ensure errors are scrambled faster thanFdecays. The white-noise approximation is useful for salvaging the signal from a noisy quantum computation; for example, it was an underlying assumption in complexity-theoretic arguments that noisy random quantum circuits cannot be efficiently sampled classically, even when the fidelity is low. Our method is based on a map from second-moment quantities in random quantum circuits to expectation values of certain stochastic processes for which we compute upper and lower bounds.

Urbano Stawinski, Stephanie M.; Rubin, Kate H. R.; Prochaska, J. Xavier; Hennawi, Joseph F.; Tejos, Nicolas; Fumagalli, Michele; Rafelski, Marc; Kirby, Evan N.; Lusso, Elisabeta; Hafen, Zachary(
, The Astrophysical Journal)

Abstract

We use medium- and high-resolution spectroscopy of close pairs of quasars to analyze the circumgalactic medium (CGM) surrounding 32 damped Lyαabsorption systems (DLAs). The primary quasar sightline in each pair probes an intervening DLA in the redshift range 1.6 <z_{abs}< 3.5, such that the secondary sightline probes absorption from Lyαand a large suite of metal-line transitions (including Oi, Cii, Civ, Siii, and Siiv) in the DLA host galaxy’s CGM at transverse distances 24 kpc ≤R_{⊥}≤ 284 kpc. Analysis of Lyαin the CGM sightlines shows an anticorrelation betweenR_{⊥}and Hicolumn density (N_{HI}) with 99.8% confidence, similar to that observed around luminous galaxies. The incidences of Ciiand SiiiwithN> 10^{13}cm^{−2}within 100 kpc of DLAs are larger by 2σthan those measured in the CGM of Lyman break galaxies (C_{f}(N_{CII}) > 0.89 and${\mathrm{C}}_{f}({N}_{\mathrm{Si}\mathrm{II}})={0.75}_{-0.17}^{+0.12}$). Metallicity constraints derived from ionic ratios for nine CGM systems with negligible ionization corrections andN_{HI}> 10^{18.5}cm^{−2}show a significant degree of scatter (with metallicities/limits across the range$-2.06\lesssim \mathrm{log}Z/{Z}_{\odot}\lesssim -0.75$), suggesting inhomogeneity in the metal distribution in these environments. Velocity widths of Civλ1548 and low-ionization metal species in the DLA versus CGM sightlines are strongly (>2σ) correlated, suggesting that they trace the potential well of the host halo overR_{⊥}≲ 300 kpc scales. At the same time, velocity centroids for Civλ1548 differ in DLA versus CGM sightlines by >100 km s^{−1}for ∼50% of velocity components, but few components have velocities that would exceed the escape velocity assuming dark matter host halos of ≥10^{12}M_{⊙}.

Sequence mappability is an important task in genome resequencing. In the (k, m)-mappability problem, for a given sequenceTof lengthn, the goal is to compute a table whoseith entry is the number of indices$$j \ne i$$$j\ne i$such that the length-msubstrings ofTstarting at positionsiandjhave at mostkmismatches. Previous works on this problem focused on heuristics computing a rough approximation of the result or on the case of$$k=1$$$k=1$. We present several efficient algorithms for the general case of the problem. Our main result is an algorithm that, for$$k=O(1)$$$k=O\left(1\right)$, works in$$O(n)$$$O\left(n\right)$space and, with high probability, in$$O(n \cdot \min \{m^k,\log ^k n\})$$$O(n\xb7min\{{m}^{k},{log}^{k}n\})$time. Our algorithm requires a careful adaptation of thek-errata trees of Cole et al. [STOC 2004] to avoid multiple counting of pairs of substrings. Our technique can also be applied to solve the all-pairs Hamming distance problem introduced by Crochemore et al. [WABI 2017]. We further develop$$O(n^2)$$$O\left({n}^{2}\right)$-time algorithms to computeall(k, m)-mappability tables for a fixedmand all$$k\in \{0,\ldots ,m\}$$$k\in \{0,\dots ,m\}$or a fixedkand all$$m\in \{k,\ldots ,n\}$$$m\in \{k,\dots ,n\}$. Finally, we show that, for$$k,m = \Theta (\log n)$$$k,m=\Theta (logn)$, the (k, m)-mappability problem cannot be solved in strongly subquadratic time unless the Strong Exponential Time Hypothesis fails. This is an improved and extended version of a paper presented at SPIRE 2018.

Chekuri, Chandra, Inamdar, Tanmay, Quanrud, Kent, Varadarajan, Kasturi, and Zhang, Zhao.
"Algorithms for covering multiple submodular constraints and applications". Journal of Combinatorial Optimization 44 (2). Country unknown/Code not available: Springer Science + Business Media. https://doi.org/10.1007/s10878-022-00874-x.https://par.nsf.gov/biblio/10369572.

@article{osti_10369572,
place = {Country unknown/Code not available},
title = {Algorithms for covering multiple submodular constraints and applications},
url = {https://par.nsf.gov/biblio/10369572},
DOI = {10.1007/s10878-022-00874-x},
abstractNote = {Abstract We consider the problem of covering multiple submodular constraints. Given a finite ground setN, a weight function$$w: N \rightarrow \mathbb {R}_+$$w:N→R+,rmonotone submodular functions$$f_1,f_2,\ldots ,f_r$$f1,f2,…,froverNand requirements$$k_1,k_2,\ldots ,k_r$$k1,k2,…,krthe goal is to find a minimum weight subset$$S \subseteq N$$S⊆Nsuch that$$f_i(S) \ge k_i$$fi(S)≥kifor$$1 \le i \le r$$1≤i≤r. We refer to this problem asMulti-Submod-Coverand it was recently considered by Har-Peled and Jones (Few cuts meet many point sets. CoRR.arxiv:abs1808.03260Har-Peled and Jones 2018) who were motivated by an application in geometry. Even with$$r=1$$r=1Multi-Submod-Covergeneralizes the well-known Submodular Set Cover problem (Submod-SC), and it can also be easily reduced toSubmod-SC. A simple greedy algorithm gives an$$O(\log (kr))$$O(log(kr))approximation where$$k = \sum _i k_i$$k=∑ikiand this ratio cannot be improved in the general case. In this paper, motivated by several concrete applications, we consider two ways to improve upon the approximation given by the greedy algorithm. First, we give a bicriteria approximation algorithm forMulti-Submod-Coverthat covers each constraint to within a factor of$$(1-1/e-\varepsilon )$$(1-1/e-ε)while incurring an approximation of$$O(\frac{1}{\epsilon }\log r)$$O(1ϵlogr)in the cost. Second, we consider the special case when each$$f_i$$fiis a obtained from a truncated coverage function and obtain an algorithm that generalizes previous work on partial set cover (Partial-SC), covering integer programs (CIPs) and multiple vertex cover constraints Bera et al. (Theoret Comput Sci 555:2–8 Bera et al. 2014). Both these algorithms are based on mathematical programming relaxations that avoid the limitations of the greedy algorithm. We demonstrate the implications of our algorithms and related ideas to several applications ranging from geometric covering problems to clustering with outliers. Our work highlights the utility of the high-level model and the lens of submodularity in addressing this class of covering problems.},
journal = {Journal of Combinatorial Optimization},
volume = {44},
number = {2},
publisher = {Springer Science + Business Media},
author = {Chekuri, Chandra and Inamdar, Tanmay and Quanrud, Kent and Varadarajan, Kasturi and Zhang, Zhao},
}

Warning: Leaving National Science Foundation Website

You are now leaving the National Science Foundation website to go to a non-government website.

Website:

NSF takes no responsibility for and exercises no control over the views expressed or the accuracy of
the information contained on this site. Also be aware that NSF's privacy policy does not apply to this site.