The problems of determining the minimum-sized \emph{identifying}, \emph{locating-dominating} and \emph{open locating-dominating codes} of an input graph are special search problems that are challenging from both theoretical and computational viewpoints. In these problems, one selects a dominating set $C$ of a graph $G$ such that the vertices of a chosen subset of $V(G)$ (i.e. either $V(G)\setminus C$ or $V(G)$ itself) are uniquely determined by their neighborhoods in $C$. A typical line of attack for these problems is to determine tight bounds for the minimum codes in various graphs classes. In this work, we present tight lower and upper bounds for all three types of codes for \emph{block graphs} (i.e. diamond-free chordal graphs). Our bounds are in terms of the number of maximal cliques (or \emph{blocks}) of a block graph and the order of the graph. Two of our upper bounds verify conjectures from the literature - with one of them being now proven for block graphs in this article. As for the lower bounds, we prove them to be linear in terms of both the number of blocks and the order of the block graph. We provide examples of families of block graphs whose minimum codes attain these bounds, thus showing each bound to be tight.
相關內容
Text prompts are crucial for generalizing pre-trained open-set object detection models to new categories. However, current methods for text prompts are limited as they require manual feedback when generalizing to new categories, which restricts their ability to model complex scenes, often leading to incorrect detection results. To address this limitation, we propose a novel visual prompt method that learns new category knowledge from a few labeled images, which generalizes the pre-trained detection model to the new category. To allow visual prompts to represent new categories adequately, we propose a statistical-based prompt construction module that is not limited by predefined vocabulary lengths, thus allowing more vectors to be used when representing categories. We further utilize the category dictionaries in the pre-training dataset to design task-specific similarity dictionaries, which make visual prompts more discriminative. We evaluate the method on the ODinW dataset and show that it outperforms existing prompt learning methods and performs more consistently in combinatorial inference.
By approximating posterior distributions with weighted samples, particle filters (PFs) provide an efficient mechanism for solving non-linear sequential state estimation problems. While the effectiveness of particle filters has been recognised in various applications, their performance relies on the knowledge of dynamic models and measurement models, as well as the construction of effective proposal distributions. An emerging trend involves constructing components of particle filters using neural networks and optimising them by gradient descent, and such data-adaptive particle filtering approaches are often called differentiable particle filters. Due to the expressiveness of neural networks, differentiable particle filters are a promising computational tool for performing inference on sequential data in complex, high-dimensional tasks, such as vision-based robot localisation. In this paper, we review recent advances in differentiable particle filters and their applications. We place special emphasis on different design choices for key components of differentiable particle filters, including dynamic models, measurement models, proposal distributions, optimisation objectives, and differentiable resampling techniques.
We develop $(\epsilon,\delta)$-differentially private projection-depth-based medians using the propose-test-release (PTR) and exponential mechanisms. Under general conditions on the input parameters and the population measure, (e.g. we do not assume any moment bounds), we quantify the probability the test in PTR fails, as well as the cost of privacy via finite sample deviation bounds. We demonstrate our main result on the canonical projection-depth-based median. In the Gaussian setting, we show that the resulting deviation bound matches the known lower bound for private Gaussian mean estimation, up to a polynomial function of the condition number of the covariance matrix. In the Cauchy setting, we show that the ``outlier error amplification'' effect resulting from the heavy tails outweighs the cost of privacy. This result is then verified via numerical simulations. Additionally, we present results on general PTR mechanisms and a uniform concentration result on the projected spacings of order statistics.
The Laguerre functions $l_{n,\tau}^\alpha$, $n=0,1,\dots$, are constructed from generalized Laguerre polynomials. The functions $l_{n,\tau}^\alpha$ depend on two parameters: scale $\tau>0$ and order of generalization $\alpha>-1$, and form an orthogonal basis in $L_2[0,\infty)$. Let the spectrum of a square matrix $A$ lie in the open left half-plane. Then the matrix exponential $H_A(t)=e^{At}$, $t>0$, belongs to $L_2[0,\infty)$. Hence the matrix exponential $H_A$ can be expanded in a series $H_A=\sum_{n=0}^\infty S_{n,\tau,\alpha,A}\,l_{n,\tau}^\alpha$. An estimate of the norm $\Bigl\lVert H_A-\sum_{n=0}^N S_{n,\tau,\alpha,A}\,l_{n,\tau}^\alpha\Bigr\rVert_{L_2[0,\infty)}$ is proposed. Finding the minimum of this estimate over $\tau$ and $\alpha$ is discussed. Numerical examples show that the optimal $\alpha$ is often almost 0, which essentially simplifies the problem.
We provide two families of algorithms to compute characteristic polynomials of endomorphisms and norms of isogenies of Drinfeld modules. Our algorithms work for Drinfeld modules of any rank, defined over any base curve. When the base curve is $\mathbb P^1_{\mathbb F_q}$, we do a thorough study of the complexity, demonstrating that our algorithms are, in many cases, the most asymptotically performant. The first family of algorithms relies on the correspondence between Drinfeld modules and Anderson motives, reducing the computation to linear algebra over a polynomial ring. The second family, available only for the Frobenius endomorphism, is based on a formula expressing the characteristic polynomial of the Frobenius as a reduced norm in a central simple algebra.
We present a family of non-CSS quantum stabilizer codes using the structure of duadic constacyclic codes over $\mathbb{F}_4$. Within this family, quantum codes can possess varying dimensions, and their minimum distances are bounded by a square root bound. For each fixed dimension, this allows us to construct an infinite sequence of binary quantum codes with a growing minimum distance. Additionally, we demonstrate that this quantum family includes an infinite subclass of degenerate codes with the mentioned properties. We also introduce a technique for extending splittings of duadic constacyclic codes, providing new insights into the minimum distance and minimum odd-like weight of specific duadic constacyclic codes. Finally, we establish that many best-known quantum codes belong to this family and provide numerical examples of quantum codes with short lengths within this family.
We consider non-ergodic class of stationary real harmonizable symmetric $\alpha$-stable processes $X=\left\{X(t):t\in\mathbb{R}\right\}$ with a finite symmetric and absolutely continuous control measure. We refer to its density function as the spectral density of $X$. These processes admit a LePage series representation and are conditionally Gaussian, which allows us to derive the non-ergodic limit of sample functions on $X$. In particular, we give an explicit expression for the non-ergodic limits of the empirical characteristic function of $X$ and the lag process $\left\{X(t+h)-X(t):t\in\mathbb{R}\right\}$ with $h>0$, respectively. The process admits an equivalent representation as a series of sinusoidal waves with random frequencies which are i.i.d. with the (normalized) spectral density of $X$ as their probability density function. Based on strongly consistent frequency estimation using the periodogram we present a strongly consistent estimator of the spectral density. The periodogram's computation is fast and efficient, and our method is not affected by the non-ergodicity of $X$.
The dichromatic number of a digraph is the minimum size of a partition of its vertices into acyclic induced subgraphs. Given a class of digraphs $\mathcal C$, a digraph $H$ is a hero in $\mc C$ if $H$-free digraphs of $\mathcal C$ have bounded dichromatic number. In a seminal paper, Berger at al. give a simple characterization of all heroes in tournaments. In this paper, we give a simple proof that heroes in quasi-transitive oriented graphs are the same as heroes in tournaments. We also prove that it is not the case in the class of oriented multipartite graphs, disproving a conjecture of Aboulker, Charbit and Naserasr. We also give a full characterisation of heroes in oriented complete multipartite graphs up to the status of a single tournament on $6$ vertices.
Spatial statistics is traditionally based on stationary models on $\mathbb{R^d}$ like Mat\'ern fields. The adaptation of traditional spatial statistical methods, originally designed for stationary models in Euclidean spaces, to effectively model phenomena on linear networks such as stream systems and urban road networks is challenging. The current study aims to analyze the incidence of traffic accidents on road networks using three different methodologies and compare the model performance for each methodology. Initially, we analyzed the application of spatial triangulation precisely on road networks instead of traditional continuous regions. However, this approach posed challenges in areas with complex boundaries, leading to the emergence of artificial spatial dependencies. To address this, we applied an alternative computational method to construct nonstationary barrier models. Finally, we explored a recently proposed class of Gaussian processes on compact metric graphs, the Whittle-Mat\'ern fields, defined by a fractional SPDE on the metric graph. The latter fields are a natural extension of Gaussian fields with Mat\'ern covariance functions on Euclidean domains to non-Euclidean metric graph settings. A ten-year period (2010-2019) of daily traffic-accident records from Barcelona, Spain have been used to evaluate the three models referred above. While comparing model performance we observed that the Whittle-Mat\'ern fields defined directly on the network outperformed the network triangulation and barrier models. Due to their flexibility, the Whittle-Mat\'ern fields can be applied to a wide range of environmental problems on linear networks such as spatio-temporal modeling of water contamination in stream networks or modeling air quality or accidents on urban road networks.
Finite-dimensional truncations are routinely used to approximate partial differential equations (PDEs), either to obtain numerical solutions or to derive reduced-order models. The resulting discretized equations are known to violate certain physical properties of the system. In particular, first integrals of the PDE may not remain invariant after discretization. Here, we use the method of reduced-order nonlinear solutions (RONS) to ensure that the conserved quantities of the PDE survive its finite-dimensional truncation. In particular, we develop two methods: Galerkin RONS and finite volume RONS. Galerkin RONS ensures the conservation of first integrals in Galerkin-type truncations, whether used for direct numerical simulations or reduced-order modeling. Similarly, finite volume RONS conserves any number of first integrals of the system, including its total energy, after finite volume discretization. Both methods are applicable to general time-dependent PDEs and can be easily incorporated in existing Galerkin-type or finite volume code. We demonstrate the efficacy of our methods on two examples: direct numerical simulations of the shallow water equation and a reduced-order model of the nonlinear Schrodinger equation. As a byproduct, we also generalize RONS to phenomena described by a system of PDEs.
注冊地址： 北京市海淀區羊坊店路18號2幢3層301-191