For fixed nonnegative integers $k$ and $\ell$, the $(P_k, P_\ell)$-Arrowing problem asks whether a given graph, $G$, has a red/blue coloring of $E(G)$ such that there are no red copies of $P_k$ and no blue copies of $P_\ell$. The problem is trivial when $\max(k,\ell) \leq 3$, but has been shown to be coNP-complete when $k = \ell = 4$. In this work, we show that the problem remains coNP-complete for all pairs of $k$ and $\ell$, except $(3,4)$, and when $\max(k,\ell) \leq 3$. Our result is only the second hardness result for $(F,H)$-Arrowing for an infinite family of graphs and the first for 1-connected graphs. Previous hardness results for $(F, H)$-Arrowing depended on constructing graphs that avoided the creation of too many copies of $F$ and $H$, allowing easier analysis of the reduction. This is clearly unavoidable with paths and thus requires a more careful approach. We define and prove the existence of special graphs that we refer to as ``transmitters.'' Using transmitters, we construct gadgets for three distinct cases: 1) $k = 3$ and $\ell \geq 5$, 2) $\ell > k \geq 4$, and 3) $\ell = k \geq 4$. For $(P_3, P_4)$-Arrowing we show a polynomial-time algorithm by reducing the problem to 2SAT, thus successfully categorizing the complexity of all $(P_k, P_\ell)$-Arrowing problems.
相關內容
We present a computationally efficient algorithm that is suitable for GPU implementation. This algorithm enables the identification of all weak pseudo-manifolds that meet specific facet conditions, drawn from a given input set. We employ this approach to enumerate toric colorable seed PL-spheres. Consequently, we achieve a comprehensive characterization of PL-spheres of dimension n-1 with n+4 vertices that possess a maximal Buchstaber number. A primary focus of this research is the fundamental categorization of non-singular complete toric varieties of Picard number 4. This classification serves as a valuable tool for addressing questions related to toric manifolds with a Picard number of 4. Notably, we have determined which of these manifolds satisfy equality within an inequality regarding the number of minimal components in their rational curve space. This addresses a question posed by Chen-Fu-Hwang in 2014 for this specific case.
Given a positive integer $d$, the class $d$-DIR is defined as all those intersection graphs formed from a finite collection of line segments in ${\mathbb R}^2$ having at most $d$ slopes. Since each slope induces an interval graph, it easily follows for every $G$ in $d$-DIR with clique number at most $\omega$ that the chromatic number $\chi(G)$ of $G$ is at most $d\omega$. We show for every even value of $\omega$ how to construct a graph in $d$-DIR that meets this bound exactly. This partially confirms a conjecture of Bhattacharya, Dvo\v{r}\'ak and Noorizadeh. Furthermore, we show that the $\chi$-binding function of $d$-DIR is $\omega \mapsto d\omega$ for $\omega$ even and $\omega \mapsto d(\omega-1)+1$ for $\omega$ odd. This refutes said conjecture of Bhattacharya, Dvo\v{r}\'ak and Noorizadeh.
In this note, we give sufficient conditions for the almost sure and the convergence in $\mathbb{L}^p$ of a $U$-statistic of order $m$ built on a strictly stationary but not necessarily ergodic sequence.
We investigate a more generalized form of submodular maximization, referred to as $k$-submodular maximization, with applications across social networks and machine learning domains. In this work, we propose the multilinear extension of $k$-submodular functions and unified Frank-Wolfe-type frameworks based on that. Our frameworks accomodate 1) monotone or non-monotone functions, and 2) various constraint types including matroid constraints, knapsack constraints, and their combinations. Notably, we attain an asymptotically optimal $1/2$-approximation for monotone $k$-submodular maximization problems with knapsack constraints, surpassing the previous $1/3$-approximation. The foundation for our analysis stems from new insights into specific linear and monotone properties pertaining to the multilinear extension.
We study the problem of solving semidefinite programs (SDP) in the streaming model. Specifically, $m$ constraint matrices and a target matrix $C$, all of size $n\times n$ together with a vector $b\in \mathbb{R}^m$ are streamed to us one-by-one. The goal is to find a matrix $X\in \mathbb{R}^{n\times n}$ such that $\langle C, X\rangle$ is maximized, subject to $\langle A_i, X\rangle=b_i$ for all $i\in [m]$ and $X\succeq 0$. Previous algorithmic studies of SDP primarily focus on \emph{time-efficiency}, and all of them require a prohibitively large $\Omega(mn^2)$ space in order to store \emph{all the constraints}. Such space consumption is necessary for fast algorithms as it is the size of the input. In this work, we design an interior point method (IPM) that uses $\widetilde O(m^2+n^2)$ space, which is strictly sublinear in the regime $n\gg m$. Our algorithm takes $O(\sqrt n\log(1/\epsilon))$ passes, which is standard for IPM. Moreover, when $m$ is much smaller than $n$, our algorithm also matches the time complexity of the state-of-the-art SDP solvers. To achieve such a sublinear space bound, we design a novel sketching method that enables one to compute a spectral approximation to the Hessian matrix in $O(m^2)$ space. To the best of our knowledge, this is the first method that successfully applies sketching technique to improve SDP algorithm in terms of space (also time).
We provide estimates on the fat-shattering dimension of aggregation rules of real-valued function classes. The latter consists of all ways of choosing $k$ functions, one from each of the $k$ classes, and computing a pointwise function of them, such as the median, mean, and maximum. The bound is stated in terms of the fat-shattering dimensions of the component classes. For linear and affine function classes, we provide a considerably sharper upper bound and a matching lower bound, achieving, in particular, an optimal dependence on $k$. Along the way, we improve several known results in addition to pointing out and correcting a number of erroneous claims in the literature.
We solve the comparison problem for generalized $\psi$-estimators introduced in Barczy and P\'ales (2022). Namely, we derive several necessary and sufficient conditions under which a generalized $\psi$-estimator less than or equal to another $\psi$-estimator for any sample. We also solve the corresponding equality problem for generalized $\psi$-estimators. For applications, we solve the two problems in question for Bajraktarevi\'c-type- and quasi-arithmetic-type estimators. We also apply our results for some known statistical estimators such as for empirical expectiles and Mathieu-type estimators and for solving likelihood equations in case of normal, a Beta-type, Gamma, Lomax (Pareto type II), lognormal and Laplace distributions.
We consider particle systems described by moments of a phase-space density and propose a realizability-preserving numerical method to evolve a spectral two-moment model for particles interacting with a background fluid moving with nonrelativistic velocities. The system of nonlinear moment equations, with special relativistic corrections to $\mathcal{O}(v/c)$, expresses a balance between phase-space advection and collisions and includes velocity-dependent terms that account for spatial advection, Doppler shift, and angular aberration. This model is closely related to the one promoted by Lowrie et al. (2001; JQSRT, 69, 291-304) and similar to models currently used to study transport phenomena in large-scale simulations of astrophysical environments. The method is designed to preserve moment realizability, which guarantees that the moments correspond to a nonnegative phase-space density. The realizability-preserving scheme consists of the following key components: (i) a strong stability-preserving implicit-explicit (IMEX) time-integration method; (ii) a discontinuous Galerkin (DG) phase-space discretization with carefully constructed numerical fluxes; (iii) a realizability-preserving implicit collision update; and (iv) a realizability-enforcing limiter. In time integration, nonlinearity of the moment model necessitates solution of nonlinear equations, which we formulate as fixed-point problems and solve with tailored iterative solvers that preserve moment realizability with guaranteed convergence. We also analyze the simultaneous Eulerian-frame number and energy conservation properties of the semi-discrete DG scheme and propose an "energy limiter" that promotes Eulerian-frame energy conservation. Through numerical experiments, we demonstrate the accuracy and robustness of this DG-IMEX method and investigate its Eulerian-frame energy conservation properties.
Elastic geophysical properties (such as P- and S-wave velocities) are of great importance to various subsurface applications like CO$_2$ sequestration and energy exploration (e.g., hydrogen and geothermal). Elastic full waveform inversion (FWI) is widely applied for characterizing reservoir properties. In this paper, we introduce $\mathbf{\mathbb{E}^{FWI}}$, a comprehensive benchmark dataset that is specifically designed for elastic FWI. $\mathbf{\mathbb{E}^{FWI}}$ encompasses 8 distinct datasets that cover diverse subsurface geologic structures (flat, curve, faults, etc). The benchmark results produced by three different deep learning methods are provided. In contrast to our previously presented dataset (pressure recordings) for acoustic FWI (referred to as OpenFWI), the seismic dataset in $\mathbf{\mathbb{E}^{FWI}}$ has both vertical and horizontal components. Moreover, the velocity maps in $\mathbf{\mathbb{E}^{FWI}}$ incorporate both P- and S-wave velocities. While the multicomponent data and the added S-wave velocity make the data more realistic, more challenges are introduced regarding the convergence and computational cost of the inversion. We conduct comprehensive numerical experiments to explore the relationship between P-wave and S-wave velocities in seismic data. The relation between P- and S-wave velocities provides crucial insights into the subsurface properties such as lithology, porosity, fluid content, etc. We anticipate that $\mathbf{\mathbb{E}^{FWI}}$ will facilitate future research on multiparameter inversions and stimulate endeavors in several critical research topics of carbon-zero and new energy exploration. All datasets, codes and relevant information can be accessed through our website at //efwi-lanl.github.io/
We consider the problem of computing a function of $n$ variables using noisy queries, where each query is incorrect with some fixed and known probability $p \in (0,1/2)$. Specifically, we consider the computation of the $\mathsf{OR}$ function of $n$ bits (where queries correspond to noisy readings of the bits) and the $\mathsf{MAX}$ function of $n$ real numbers (where queries correspond to noisy pairwise comparisons). We show that an expected number of queries of \[ (1 \pm o(1)) \frac{n\log \frac{1}{\delta}}{D_{\mathsf{KL}}(p \| 1-p)} \] is both sufficient and necessary to compute both functions with a vanishing error probability $\delta = o(1)$, where $D_{\mathsf{KL}}(p \| 1-p)$ denotes the Kullback-Leibler divergence between $\mathsf{Bern}(p)$ and $\mathsf{Bern}(1-p)$ distributions. Compared to previous work, our results tighten the dependence on $p$ in both the upper and lower bounds for the two functions.
小貼士
登錄享
相關主題
注冊地址： 北京市海淀區羊坊店路18號2幢3層301-191