For a graph $G$, a $D$-diameter-reducing exact hopset is a small set of additional edges $H$ that, when added to $G$, maintains its graph metric but guarantees that all node pairs have a shortest path in $G \cup H$ using at most $D$ edges. A shortcut set is the analogous concept for reachability. These objects have been studied since the early '90s due to applications in parallel, distributed, dynamic, and streaming graph algorithms. For most of their history, the state-of-the-art construction for either object was a simple folklore algorithm, based on randomly sampling nodes to hit long paths in the graph. However, recent breakthroughs of Kogan and Parter [SODA '22] and Bernstein and Wein [SODA '23] have finally improved over the folklore diameter bound of $\widetilde{O}(n^{1/2})$ for shortcut sets and for $(1+\epsilon)$-approximate hopsets. For both objects it is now known that one can use $O(n)$ hop-edges to reduce diameter to $\widetilde{O}(n^{1/3})$. The only setting where folklore sampling remains unimproved is for exact hopsets. Can these improvements be continued? We settle this question negatively by constructing graphs on which any exact hopset of $O(n)$ edges has diameter $\widetilde{\Omega}(n^{1/2})$. This improves on the previous lower bound of $\widetilde{\Omega}(n^{1/3})$ by Kogan and Parter [FOCS '22]. Using similar ideas, we also polynomially improve the current lower bounds for shortcut sets, constructing graphs on which any shortcut set of $O(n)$ edges reduces diameter to $\widetilde{\Omega}(n^{1/4})$. This improves on the previous lower bound of $\Omega(n^{1/6})$ by Huang and Pettie [SIAM J. Disc. Math. '18]. We also extend our constructions to provide lower bounds against $O(p)$-size exact hopsets and shortcut sets for other values of $p$; in particular, we show that folklore sampling is near-optimal for exact hopsets in the entire range of $p \in [1, n^2]$.
相關內容
Interpolatory necessary optimality conditions for $\mathcal{H}_2$-optimal reduced-order modeling of unstructured linear time-invariant (LTI) systems are well-known. Based on previous work on $\mathcal{L}_2$-optimal reduced-order modeling of stationary parametric problems, in this paper we develop and investigate optimality conditions for $\mathcal{H}_2$-optimal reduced-order modeling of structured LTI systems, in particular, for second-order, port-Hamiltonian, and time-delay systems. We show that across all these different structured settings, bitangential Hermite interpolation is the common form for optimality, thus proving a unifying optimality framework for structured reduced-order modeling.
In this paper we study the orbit closure problem for a reductive group $G\subseteq GL(X)$ acting on a finite dimensional vector space $V$ over $\C$. We assume that the center of $GL(X)$ lies within $G$ and acts on $V$ through a fixed non-trivial character. We study points $y,z\in V$ where (i) $z$ is obtained as the leading term of the action of a 1-parameter subgroup $\lambda (t)\subseteq G$ on $y$, and (ii) $y$ and $z$ have large distinctive stabilizers $K,H \subseteq G$. Let $O(z)$ (resp. $O(y)$) denote the $G$-orbits of $z$ (resp. $y$), and $\overline{O(z)}$ (resp. $\overline{O(y)}$) their closures, then (i) implies that $z\in \overline{O(y)}$. We address the question: under what conditions can (i) and (ii) be simultaneously satisfied, i.e, there exists a 1-PS $\lambda \subseteq G$ for which $z$ is observed as a limit of $y$. Using $\lambda$, we develop a leading term analysis which applies to $V$ as well as to ${\cal G}= Lie(G)$ the Lie algebra of $G$ and its subalgebras ${\cal K}$ and ${\cal H}$, the Lie algebras of $K$ and $H$ respectively. Through this we construct the Lie algebra $\hat{\cal K} \subseteq {\cal H}$ which connects $y$ and $z$ through their Lie algebras. We develop the properties of $\hat{\cal K}$ and relate it to the action of ${\cal H}$ on $\overline{N}=V/T_z O(z)$, the normal slice to the orbit $O(z)$. We examine the case of {\em alignment} when a semisimple element belongs to both ${\cal H}$ and ${\cal K}$, and the conditions for the same. We illustrate some consequences of alignment. Next, we examine the possibility of {\em intermediate $G$-varieties} $W$ which lie between the orbit closures of $z$ and $y$, i.e. $\overline{O(z)} \subsetneq W \subsetneq O(y)$. These have a direct bearing on representation theoretic as well as geometric properties which connect $z$ and $y$.
A class $\mathcal F$ of graphs is $\chi$-bounded if there is a function $f$ such that $\chi(H)\le f(\omega(H))$ for all induced subgraphs $H$ of a graph in $\mathcal F$. If $f$ can be chosen to be a polynomial, we say that $\mathcal F$ is polynomially $\chi$-bounded. Esperet proposed a conjecture that every $\chi$-bounded class of graphs is polynomially $\chi$-bounded. This conjecture has been disproved; it has been shown that there are classes of graphs that are $\chi$-bounded but not polynomially $\chi$-bounded. Nevertheless, inspired by Esperet's conjecture, we introduce Pollyanna classes of graphs. A class $\mathcal C$ of graphs is Pollyanna if $\mathcal C\cap \mathcal F$ is polynomially $\chi$-bounded for every $\chi$-bounded class $\mathcal F$ of graphs. We prove that several classes of graphs are Pollyanna and also present some proper classes of graphs that are not Pollyanna.
Interpolatory necessary optimality conditions for $\mathcal{H}_2$-optimal reduced-order modeling of unstructured linear time-invariant (LTI) systems are well-known. Based on previous work on $\mathcal{L}_2$-optimal reduced-order modeling of stationary parametric problems, in this paper we develop and investigate optimality conditions for $\mathcal{H}_2$-optimal reduced-order modeling of structured LTI systems, in particular, for second-order, port-Hamiltonian, and time-delay systems. We show that across all these different structured settings, bitangential Hermite interpolation is the common form for optimality, thus proving a unifying optimality framework for structured reduced-order modeling.
We compute the weight distribution of the ${\mathcal R} (4,9)$ by combining the approach described in D. V. Sarwate's Ph.D. thesis from 1973 with knowledge on the affine equivalence classification of Boolean functions. To solve this problem posed, e.g., in the MacWilliams and Sloane book [p. 447], we apply a refined approach based on the classification of Boolean quartic forms in $8$ variables due to Ph. Langevin and G. Leander, and recent results on the classification of the quotient space ${\mathcal R} (4,7)/{\mathcal R} (2,7)$ due to V. Gillot and Ph. Langevin.
Many-to-many multimodal summarization (M$^3$S) task aims to generate summaries in any language with document inputs in any language and the corresponding image sequence, which essentially comprises multimodal monolingual summarization (MMS) and multimodal cross-lingual summarization (MXLS) tasks. Although much work has been devoted to either MMS or MXLS and has obtained increasing attention in recent years, little research pays attention to the M$^3$S task. Besides, existing studies mainly focus on 1) utilizing MMS to enhance MXLS via knowledge distillation without considering the performance of MMS or 2) improving MMS models by filtering summary-unrelated visual features with implicit learning or explicitly complex training objectives. In this paper, we first introduce a general and practical task, i.e., M$^3$S. Further, we propose a dual knowledge distillation and target-oriented vision modeling framework for the M$^3$S task. Specifically, the dual knowledge distillation method guarantees that the knowledge of MMS and MXLS can be transferred to each other and thus mutually prompt both of them. To offer target-oriented visual features, a simple yet effective target-oriented contrastive objective is designed and responsible for discarding needless visual information. Extensive experiments on the many-to-many setting show the effectiveness of the proposed approach. Additionally, we will contribute a many-to-many multimodal summarization (M$^3$Sum) dataset.
The concatenation of four Boolean bent functions $f=f_1||f_2||f_3||f_4$ is bent if and only if the dual bent condition $f_1^* + f_2^* + f_3^* + f_4^* =1$ is satisfied. However, to specify four bent functions satisfying this duality condition is in general quite a difficult task. Commonly, to simplify this problem, certain connections between $f_i$ are assumed, as well as functions $f_i$ of a special shape are considered, e.g., $f_i(x,y)=x\cdot\pi_i(y)+h_i(y)$ are Maiorana-McFarland bent functions. In the case when permutations $\pi_i$ of $\mathbb{F}_2^m$ have the $(\mathcal{A}_m)$ property and Maiorana-McFarland bent functions $f_i$ satisfy the additional condition $f_1+f_2+f_3+f_4=0$, the dual bent condition is known to have a relatively simple shape allowing to specify the functions $f_i$ explicitly. In this paper, we generalize this result for the case when Maiorana-McFarland bent functions $f_i$ satisfy the condition $f_1(x,y)+f_2(x,y)+f_3(x,y)+f_4(x,y)=s(y)$ and provide a construction of new permutations with the $(\mathcal{A}_m)$ property from the old ones. Combining these two results, we obtain a recursive construction method of bent functions satisfying the dual bent condition. Moreover, we provide a generic condition on the Maiorana-McFarland bent functions stemming from the permutations of $\mathbb{F}_2^m$ with the $(\mathcal{A}_m)$ property, such that their concatenation does not belong, up to equivalence, to the Maiorana-McFarland class. Using monomial permutations $\pi_i$ of $\mathbb{F}_{2^m}$ with the $(\mathcal{A}_m)$ property and monomial functions $h_i$ on $\mathbb{F}_{2^m}$, we provide explicit constructions of such bent functions. Finally, with our construction method, we explain how one can construct homogeneous cubic bent functions, noticing that only very few design methods of these objects are known.
We develop two "Nesterov's accelerated" variants of the well-known extragradient method to approximate a solution of a co-hypomonotone inclusion constituted by the sum of two operators, where one is Lipschitz continuous and the other is possibly multivalued. The first scheme can be viewed as an accelerated variant of Tseng's forward-backward-forward splitting (FBFS) method, while the second one is a Nesterov's accelerated variant of the "past" FBFS scheme, which requires only one evaluation of the Lipschitz operator and one resolvent of the multivalued mapping. Under appropriate conditions on the parameters, we theoretically prove that both algorithms achieve $\mathcal{O}(1/k)$ last-iterate convergence rates on the residual norm, where $k$ is the iteration counter. Our results can be viewed as alternatives of a recent class of Halpern-type methods for root-finding problems. For comparison, we also provide a new convergence analysis of the two recent extra-anchored gradient-type methods for solving co-hypomonotone inclusions.
Kalai's $3^d$-conjecture states that every centrally symmetric $d$-polytope has at least $3^d$ faces. We give short proofs for two special cases: if $P$ is unconditional (that is, invariant w.r.t. reflection in any coordinate hyperplane), and more generally, if $P$ is locally anti-blocking (that is, looks like an unconditional polytope in every orthant). In both cases we show that the minimum is attained exactly for the Hanner polytopes.
Let $P$ be a convex polygon in the plane, and let $T$ be a triangulation of $P$. An edge $e$ in $T$ is called a diagonal if it is shared by two triangles in $T$. A flip of a diagonal $e$ is the operation of removing $e$ and adding the opposite diagonal of the resulting quadrilateral to obtain a new triangulation of $P$ from $T$. The flip distance between two triangulations of $P$ is the minimum number of flips needed to transform one triangulation into the other. The Convex Flip Distance problem asks if the flip distance between two given triangulations of $P$ is at most $k$, for some given parameter $k$. We present an FPT algorithm for the Convex Flip Distance problem that runs in time $O(3.82^k)$ and uses polynomial space, where $k$ is the number of flips. This algorithm significantly improves the previous best FPT algorithms for the problem.
注冊地址： 北京市海淀區羊坊店路18號2幢3層301-191