Vizing's theorem states that any $n$-vertex $m$-edge graph of maximum degree $\Delta$ can be {\em edge colored} using at most $\Delta + 1$ different colors [Diskret.~Analiz, '64]. Vizing's original proof is algorithmic and shows that such an edge coloring can be found in $\tilde{O}(mn)$ time. This was subsequently improved to $\tilde O(m\sqrt{n})$, independently by Arjomandi [1982] and by Gabow et al.~[1985]. In this paper we present an algorithm that computes such an edge coloring in $\tilde O(mn^{1/3})$ time, giving the first polynomial improvement for this fundamental problem in over 40 years.
相關內容
In this class notes students can learn how B specifications can be translated into $\{log$\}$ forgrams, how these forgrams can be executed and how they can be proved to verify some properties.
The $\ell_p$ subspace approximation problem is an NP-hard low rank approximation problem that generalizes the median hyperplane problem ($p = 1$), principal component analysis ($p = 2$), and the center hyperplane problem ($p = \infty$). A popular approach to cope with the NP-hardness of this problem is to compute a strong coreset, which is a small weighted subset of the input points which simultaneously approximates the cost of every $k$-dimensional subspace, typically to $(1+\varepsilon)$ relative error for a small constant $\varepsilon$. We obtain the first algorithm for constructing a strong coreset for $\ell_p$ subspace approximation with a nearly optimal dependence on the rank parameter $k$, obtaining a nearly linear bound of $\tilde O(k)\mathrm{poly}(\varepsilon^{-1})$ for $p<2$ and $\tilde O(k^{p/2})\mathrm{poly}(\varepsilon^{-1})$ for $p>2$. Prior constructions either achieved a similar size bound but produced a coreset with a modification of the original points [SW18, FKW21], or produced a coreset of the original points but lost $\mathrm{poly}(k)$ factors in the coreset size [HV20, WY23]. Our techniques also lead to the first nearly optimal online strong coresets for $\ell_p$ subspace approximation with similar bounds as the offline setting, resolving a problem of [WY23]. All prior approaches lose $\mathrm{poly}(k)$ factors in this setting, even when allowed to modify the original points.
Estimating parameters of functional ARMA, GARCH and invertible processes requires estimating lagged covariance and cross-covariance operators of Cartesian product Hilbert space-valued processes. Asymptotic results have been derived in recent years, either less generally or under a strict condition. This article derives upper bounds of the estimation errors for such operators based on the mild condition Lp-m-approximability for each lag, Cartesian power(s) and sample size, where the two processes can take values in different spaces in the context of lagged cross-covariance operators. Implications of our results on eigenelements, parameters in functional AR(MA) models and other general situations are also discussed.
For $\tilde{f}(t) = \exp(\frac{\alpha-1}{\alpha}t)$, this paper proposes a $\tilde{f}$-mean information gain measure. R\'{e}nyi divergence is shown to be the maximum $\tilde{f}$-mean information gain incurred at each elementary event $y$ of channel output $Y$ and Sibson mutual information is the $\tilde{f}$-mean of this $Y$-elementary information gain. Both are proposed as $\alpha$-leakage measures, indicating the most information an adversary can obtain on sensitive data. It is shown that the existing $\alpha$-leakage by Arimoto mutual information can be expressed as $\tilde{f}$-mean measures by a scaled probability. Further, Sibson mutual information is interpreted as the maximum $\tilde{f}$-mean information gain over all estimation decisions applied to channel output.
A graph $G=(V,E)$ is a $k$-leaf power if there is a tree $T$ whose leaves are the vertices of $G$ with the property that a pair of leaves $u$ and $v$ induce an edge in $G$ if and only if they are distance at most $k$ apart in $T$. For $k\le 4$, it is known that there exists a finite set $F_k$ of graphs such that the class $L(k)$ of $k$-leaf power graphs is characterized as the set of strongly chordal graphs that do not contain any graph in $F_k$ as an induced subgraph. We prove no such characterization holds for $k\ge 5$. That is, for any $k\ge 5$, there is no finite set $F_k$ of graphs such that $L(k)$ is equivalent to the set of strongly chordal graphs that do not contain as an induced subgraph any graph in $F_k$.
We present fully abstract encodings of the call-by-name and call-by-value $\lambda$-calculus into HOcore, a minimal higher-order process calculus with no name restriction. We consider several equivalences on the $\lambda$-calculus side -- normal-form bisimilarity, applicative bisimilarity, and contextual equivalence -- that we internalize into abstract machines in order to prove full abstraction of the encodings. We also demonstrate that this technique scales to the $\lambda\mu$-calculus, i.e., a standard extension of the $\lambda$-calculus with control operators.
In this paper we give a polynomial time algorithm to compute $\varphi(N)$ for an RSA module $N$ using as input the order modulo $N$ of a randomly chosen integer. The algorithm consists only on a computation of a greatest common divisor, two multiplications and a division. The algorithm works with a probability of at least $1-\frac{C}{N^{1/2}}$.
A separating system of a graph $G$ is a family $\mathcal{S}$ of subgraphs of $G$ for which the following holds: for all distinct edges $e$ and $f$ of $G$, there exists an element in $\mathcal{S}$ that contains $e$ but not $f$. Recently, it has been shown that every graph of order $n$ admits a separating system consisting of $19n$ paths [Bonamy, Botler, Dross, Naia, Skokan, Separating the Edges of a Graph by a Linear Number of Paths, Adv. Comb., October 2023], improving the previous almost linear bound of $\mathrm{O}(n\log^\star n)$ [S. Letzter, Separating paths systems of almost linear size, Trans. Amer. Math. Soc., to appear], and settling conjectures posed by Balogh, Csaba, Martin, and Pluh\'ar and by Falgas-Ravry, Kittipassorn, Kor\'andi, Letzter, and Narayanan. We investigate a natural generalization of these results to subdivisions of cliques, showing that every graph admits both a separating system consisting of $41n$ edges and cycles, and a separating system consisting of $82 n$ edges and subdivisions of $K_4$.
We provide numerical evidence for a potential finite-time self-similar singularity of the 3D axisymmetric Euler equations with no swirl and with $C^\alpha$ initial vorticity for a large range of $\alpha$. We employ a highly effective adaptive mesh method to resolve the potential singularity sufficiently close to the potential blow-up time. Resolution study shows that our numerical method is at least second-order accurate. Scaling analysis and the dynamic rescaling method are presented to quantitatively study the scaling properties of the potential singularity. We demonstrate that this potential blow-up is stable with respect to the perturbation of initial data. Our numerical study shows that the 3D axisymmetric Euler equations with our initial data develop finite-time blow-up when the H\"older exponent $\alpha$ is smaller than some critical value $\alpha^*$, which has the potential to be $1/3$. We also study the $n$-dimensional axisymmetric Euler equations with no swirl, and observe that the critical H\"older exponent $\alpha^*$ is close to $1-\frac{2}{n}$. Compared with Elgindi's blow-up result in a similar setting \cite{elgindi2021finite}, our potential blow-up scenario has a different H\"older continuity property in the initial data and the scaling properties of the two initial data are also quite different. We also propose a relatively simple one-dimensional model and numerically verify its approximation to the $n$-dimensional axisymmetric Euler equations. This one-dimensional model sheds useful light to our understanding of the blow-up mechanism for the $n$-dimensional Euler equations.
The conditions for cubic equations, to have 3 real roots and 2 of the roots lie in the closed interval $[-1, 1]$ are given. These conditions are visualized. This question arises in physics in e.g. the theory of tops.
注冊地址： 北京市海淀區羊坊店路18號2幢3層301-191