In this paper we investigate the parameterized complexity of the task of counting and detecting occurrences of small patterns in unit disk graphs: Given an $n$-vertex unit disk graph $G$ with an embedding of ply $p$ (that is, the graph is represented as intersection graph with closed disks of unit size, and each point is contained in at most $p$ disks) and a $k$-vertex unit disk graph $P$, count the number of (induced) copies of $P$ in $G$. For general patterns $P$, we give an $2^{O(p k /\log k)}n^{O(1)}$ time algorithm for counting pattern occurrences. We show this is tight, even for ply $p=2$ and $k=n$: any $2^{o(n/\log n)}n^{O(1)}$ time algorithm violates the Exponential Time Hypothesis (ETH). For most natural classes of patterns, such as connected graphs and independent sets we present the following results: First, we give an $(pk)^{O(\sqrt{pk})}n^{O(1)}$ time algorithm, which is nearly tight under the ETH for bounded ply and many patterns. Second, for $p= k^{O(1)}$ we provide a Turing kernelization (i.e. we give a polynomial time preprocessing algorithm to reduce the instance size to $k^{O(1)}$). Our approach combines previous tools developed for planar subgraph isomorphism such as `efficient inclusion-exclusion' from [Nederlof STOC'20], and `isomorphisms checks' from [Bodlaender et al. ICALP'16] with a different separator hierarchy and a new bound on the number of non-isomorphic separations of small order tailored for unit disk graphs.
相關內容
In this paper we investigate the interplay between isolated suborders and closures. Isolated suborders are a special kind of suborders and can be used to diminish the number of elements of an ordered set by means of a quotient construction. The decisive point is that there are simple formulae establishing relationships between the number of closures in the original ordered set and the quotient thereof induced by isolated suborders. We show how these connections can be used to derive a recursive algorithm for counting closures, provided the ordered set under consideration contains suitable isolated suborders.
In this paper, we propose an advancement to Tarskian model-theoretic semantics, leading to a unified quantitative theory of semantic information and communication. We start with description of inductive logic and probabilities, which serve as notable tools in development of the proposed theory. Then, we identify two disparate kinds of uncertainty in semantic communication, that of physical and content, present refined interpretations of semantic information measures, and conclude with proposing a new measure for semantic content-information and entropy. Our proposition standardizes semantic information across different universes and systems, hence bringing measurability and comparability into semantic communication. We then proceed with introducing conditional and mutual semantic cont-information measures and point out to their utility in formulating practical and optimizable lossless and lossy semantic compression objectives. Finally, we experimentally demonstrate the value of our theoretical propositions.
In this paper, we establish novel data-dependent upper bounds on the generalization error through the lens of a "variable-size compressibility" framework that we introduce newly here. In this framework, the generalization error of an algorithm is linked to a variable-size 'compression rate' of its input data. This is shown to yield bounds that depend on the empirical measure of the given input data at hand, rather than its unknown distribution. Our new generalization bounds that we establish are tail bounds, tail bounds on the expectation, and in-expectations bounds. Moreover, it is shown that our framework also allows to derive general bounds on any function of the input data and output hypothesis random variables. In particular, these general bounds are shown to subsume and possibly improve over several existing PAC-Bayes and data-dependent intrinsic dimension-based bounds that are recovered as special cases, thus unveiling a unifying character of our approach. For instance, a new data-dependent intrinsic dimension-based bound is established, which connects the generalization error to the optimization trajectories and reveals various interesting connections with the rate-distortion dimension of a process, the R\'enyi information dimension of a process, and the metric mean dimension.
In this paper, we focus on the design of binary constant-weight codes that admit low-complexity encoding and decoding algorithms, and that have size as a power of $2$. We construct a family of $(n=2^\ell, M=2^k, d=2)$ constant-weight codes ${\cal C}[\ell, r]$ parameterized by integers $\ell \geq 3$ and $1 \leq r \leq \lfloor \frac{\ell+3}{4} \rfloor$, by encoding information in the gaps between successive $1$'s of a vector. The code has weight $w = \ell$ and combinatorial dimension $k$ that scales quadratically with $\ell$. The encoding time is linear in the input size $k$, and the decoding time is poly-logarithmic in the input size $n$, discounting the linear time spent on parsing the input. Encoding and decoding algorithms of similar codes known in either information-theoretic or combinatorial literature require computation of large number of binomial coefficients. Our algorithms fully eliminate the need to evaluate binomial coefficients. While the code has a natural price to pay in $k$, it performs fairly well against the information-theoretic upper bound $\lfloor \log_2 {n \choose w} \rfloor$. When $\ell =3$, the code is optimal achieving the upper bound; when $\ell=4$, it is one bit away from the upper bound, and as $\ell$ grows it is order-optimal in the sense that the ratio of $k$ with its upper bound becomes a constant $\frac{11}{16}$ when $r=\lfloor \frac{\ell+3}{4} \rfloor$. With the same or even lower complexity, we derive new codes permitting a wider range of parameters by modifying ${\cal C}[\ell, r]$ in two different ways. The code derived using the first approach has the same blocklength $n=2^\ell$, but weight $w$ is allowed to vary from $\ell-1$ to $1$. In the second approach, the weight remains fixed as $w = \ell$, but the blocklength is reduced to $n=2^\ell - 2^r +1$. For certain selected values of parameters, these modified codes have an optimal $k$.
We consider channel coding for discrete memoryless channels (DMCs) with a novel cost constraint that constrains both the mean and the variance of the cost of the codewords. We show that the maximum (asymptotically) achievable rate under the new cost formulation is equal to the capacity-cost function; in particular, the strong converse holds. We further characterize the optimal second-order coding rate of these cost-constrained codes; in particular, the optimal second-order coding rate is finite. We then show that the second-order coding performance is strictly improved with feedback using a new variation of timid/bold coding, significantly broadening the applicability of timid/bold coding schemes from unconstrained compound-dispersion channels to all cost-constrained channels. Equivalent results on the minimum average probability of error are also given.
In this paper, we concentrate on solving second-order singularly perturbed Fredholm integro-differential equations (SPFIDEs). It is well known that solving these equations analytically is a challenging endeavor because of the presence of boundary and interior layers within the domain. To overcome these challenges, we develop a fitted second-order difference scheme that can capture the layer behavior of the solution accurately and efficiently, which is again, based on the integral identities with exponential basis functions, the composite trapezoidal rule, and an appropriate interpolating quadrature rules with the remainder terms in the integral form on a piecewise uniform mesh. Hence, our numerical method acts as a superior alternative to the existing methods in the literature. Further, using appropriate techniques in error analysis the scheme's convergence and stability have been studied in the discrete max norm. We have provided necessary experimental evidence that corroborates the theoretical results with a high degree of accuracy.
In this paper, we provide a theoretical analysis for a preconditioned steepest descent (PSD) iterative solver that improves the computational time of a finite difference numerical scheme for the Cahn-Hilliard equation with Flory-Huggins energy potential. In the numerical design, a convex splitting approach is applied to the chemical potential such that the logarithmic and the surface diffusion terms are treated implicitly while the expansive concave term is treated with an explicit update. The nonlinear and singular nature of the logarithmic energy potential makes the numerical implementation very challenging. However, the positivity-preserving property for the logarithmic arguments, unconditional energy stability, and optimal rate error estimates have been established in a recent work and it has been shown that successful solvers ensure a similar positivity-preserving property at each iteration stage. Therefore, in this work, we will show that the PSD solver ensures a positivity-preserving property at each iteration stage. The PSD solver consists of first computing a search direction (involved with solving a Poisson-like equation) and then takes a one-parameter optimization step over the search direction in which the Newton iteration becomes very powerful. A theoretical analysis is applied to the PSD iteration solver and a geometric convergence rate is proved for the iteration. In particular, the strict separation property of the numerical solution, which indicates a uniform distance between the numerical solution and the singular limit values of $\pm 1$ for the phase variable, plays an essential role in the iteration convergence analysis. A few numerical results are presented to demonstrate the robustness and efficiency of the PSD solver.
In this paper, we study the asymptotic nonnegative rank of matrices, which characterizes the asymptotic growth of the nonnegative rank of fixed nonnegative matrices under the Kronecker product. This quantity is important since it governs several notions in information theory such as the so-called exact R\'enyi common information and the amortized communication complexity. By using the theory of asymptotic spectra of V. Strassen (J. Reine Angew. Math. 1988), we define formally the asymptotic spectrum of nonnegative matrices and give a dual characterization of the asymptotic nonnegative rank. As a complementary of the nonnegative rank, we introduce the notion of the subrank of a nonnegative matrix and show that it is exactly equal to the size of the maximum induced matching of the bipartite graph defined on the support of the matrix (therefore, independent of the value of entries). Finally, we show that two matrix parameters, namely rank and fractional cover number, belong to the asymptotic spectrum of nonnegative matrices.
Graph Neural Networks (GNNs) and Transformer have been increasingly adopted to learn the complex vector representations of spatio-temporal graphs, capturing intricate spatio-temporal dependencies crucial for applications such as traffic datasets. Although many existing methods utilize multi-head attention mechanisms and message-passing neural networks (MPNNs) to capture both spatial and temporal relations, these approaches encode temporal and spatial relations independently, and reflect the graph's topological characteristics in a limited manner. In this work, we introduce the Cycle to Mixer (Cy2Mixer), a novel spatio-temporal GNN based on topological non-trivial invariants of spatio-temporal graphs with gated multi-layer perceptrons (gMLP). The Cy2Mixer is composed of three blocks based on MLPs: A message-passing block for encapsulating spatial information, a cycle message-passing block for enriching topological information through cyclic subgraphs, and a temporal block for capturing temporal properties. We bolster the effectiveness of Cy2Mixer with mathematical evidence emphasizing that our cycle message-passing block is capable of offering differentiated information to the deep learning model compared to the message-passing block. Furthermore, empirical evaluations substantiate the efficacy of the Cy2Mixer, demonstrating state-of-the-art performances across various traffic benchmark datasets.
In this paper we study the expectation maximization (EM) technique for one-bit MIMO-OFDM detection (OMOD). Arising from the recent interest in massive MIMO with one-bit analog-to-digital converters, OMOD is a massive-scale problem. EM is an iterative method that can exploit the OFDM structure to process the problem in a per-iteration efficient fashion. In this study we analyze the convergence rate of EM for a class of approximate maximum-likelihood OMOD formulations, or, in a broader sense, a class of problems involving regression from quantized data. We show how the SNR and channel conditions can have an impact on the convergence rate. We do so by making a connection between the EM and the proximal gradient methods in the context of OMOD. This connection also gives us insight to build new accelerated and/or inexact EM schemes. The accelerated scheme has faster convergence in theory, and the inexact scheme provides us with the flexibility to implement EM more efficiently, with convergence guarantee. Furthermore we develop a deep EM algorithm, wherein we take the structure of our inexact EM algorithm and apply deep unfolding to train an efficient structured deep net. Simulation results show that our accelerated exact/inexact EM algorithms run much faster than their standard EM counterparts, and that the deep EM algorithm gives promising detection and runtime performances.
小貼士
登錄享
相關主題
注冊地址： 北京市海淀區羊坊店路18號2幢3層301-191