Aggregating data in a database could also be called "integrating along fibers": given functions $\pi\colon E\to D$ and $s\colon E\to R$, where $(R,\circledast)$ is a commutative monoid, we want a new function $(\circledast s)_\pi$ that sends each $d\in D$ to the "sum" of all $s(e)$ for which $\pi(e)=d$. The operation lives alongside querying -- or more generally data migration -- in typical database usage: one wants to know how much Canadians spent on cell phones in 2021, for example, and such requests typically require both aggregation and querying. But whereas querying has an elegant category-theoretic treatment in terms of parametric right adjoints between copresheaf categories, a categorical formulation of aggregation -- especially one that lives alongside that for querying -- appears to be completely absent from the literature. In this paper we show how both querying and aggregation fit into the "polynomial ecosystem". Starting with the category $\mathbf{Poly}$ of polynomial functors in one variable, we review the relatively recent results of Ahman-Uustalu and Garner, which showed that the framed bicategory $\mathbb{C}\mathbf{at}^\sharp$ of comonads in $\mathbf{Poly}$ is precisely the right setting for data migration: its objects are categories and its bicomodules are parametric right adjoints between their copresheaf categories. We then develop a great deal of theory, compressed for space reasons, including local monoidal closed structures, a coclosure to bicomodule composition, and an understanding of adjoints in $\mathbb{C}\mathbf{at}^\sharp$. Doing so allows us to derive interesting mathematical results, e.g.\ that the ordinary operation of transposing a span can be decomposed into the composite of two more primitive operations, and then finally to explain how aggregation arises, alongside querying, in $\mathbb{C}\mathbf{at}^\sharp$.
相關內容
Given a graph $G$, when is it possible to reconstruct with high probability a uniformly random colouring of its vertices in $r$ colours from its $k$-deck, i.e. a set of its induced (coloured) subgraphs of size $k$? In this paper, we reconstruct random colourings of lattices and random graphs. Recently, Narayanan and Yap proved that, for $d=2$, with high probability a random colouring of vertices of a $d$-dimensional $n$-lattice ($n\times n$ grid) is reconstructibe from its deck of all $k$-subgrids ($k\times k$ grids) if $k\geq\sqrt{2\log_2 n}+\frac{3}{4}$ and is not reconstructible if $k<\sqrt{2\log_2 n}-\frac{1}{4}$. We prove that the same "two-point concentration" result for the minimum size of subgrids that determine the entire colouring holds true in any dimension $d\geq 2$. We also prove that with high probability a uniformly random $r$-colouring of the vertices of the random graph $G(n,1/2)$ is reconstructible from its full $k$-deck if $k\geq 2\log_2 n+8$ and is not reconstructible if $k\leq\sqrt{2\log_2 n}$. We further show that the colour reconstruction algorithm for random graphs can be modified and used for graph reconstruction: we prove that with high probability $G(n,1/2)$ is reconstructible from its full $k$-deck if $k\geq 2\log_2 n+11$ (while it is not reconstructible with high probability if $k\leq 2\sqrt{\log_2 n}$). This significantly improves the best known upper bound for the minimum size of subgraphs in a deck that can be used to reconstruct the random graph with high probability.
平滑
·
We analyze an algorithmic question about immersion theory: for which $m$, $n$, and $CAT=\mathbf{Diff}$ or $\mathbf{PL}$ is the question of whether an $m$-dimensional $CAT$-manifold is immersible in $\mathbb{R}^n$ decidable? As a corollary, we show that the smooth embeddability of an $m$-manifold with boundary in $\mathbb{R}^n$ is undecidable when $n-m$ is even and $11m \geq 10n+1$.
Let $G$ be a multigraph and $L\,:\,E(G) \to 2^\mathbb{N}$ be a list assignment on the edges of $G$. Suppose additionally, for every vertex $x$, the edges incident to $x$ have at least $f(x)$ colors in common. We consider a variant of local edge-colorings wherein the color received by an edge $e$ must be contained in $L(e)$. The locality appears in the function $f$, i.e., $f(x)$ is some function of the local structure of $x$ in $G$. Such a notion is a natural generalization of traditional local edge-coloring. Our main results include sufficient conditions on the function $f$ to construct such colorings. As corollaries, we obtain local analogs of Vizing and Shannon's theorems, recovering a recent result of Conley, Greb\'ik and Pikhurko.
We investigate error of the Euler scheme in the case when the right-hand side function of the underlying ODE satisfies nonstandard assumptions such as local one-sided Lipschitz condition and local H\"older continuity. Moreover, we assume two cases in regards to information availability: exact and noisy with respect to the right-hand side function. Optimality analysis of the Euler scheme is also provided. Finally, we present the results of some numerical experiments.
This paper concerns an expansion of first-order Belnap-Dunn logic which is called $\mathrm{BD}^{\supset,\mathsf{F}}$. Its connectives and quantifiers are all familiar from classical logic and its logical consequence relation is very closely connected to the one of classical logic. Results that convey this close connection are established. Fifteen classical laws of logical equivalence are used to distinguish $\mathrm{BD}^{\supset,\mathsf{F}}$ from all other four-valued logics with the same connectives and quantifiers whose logical consequence relation is as closely connected to the logical consequence relation of classical logic. It is shown that several interesting non-classical connectives added to Belnap-Dunn logic in its expansions that have been studied earlier are definable in $\mathrm{BD}^{\supset,\mathsf{F}}$. It is also established that $\mathrm{BD}^{\supset,\mathsf{F}}$ is both paraconsistent and paracomplete. Moreover, a sequent calculus proof system that is sound and complete with respect to the logical consequence relation of $\mathrm{BD}^{\supset,\mathsf{F}}$ is presented.
We investigate a linearised Calder\'on problem in a two-dimensional bounded simply connected $C^{1,\alpha}$ domain $\Omega$. After extending the linearised problem for $L^2(\Omega)$ perturbations, we orthogonally decompose $L^2(\Omega) = \oplus_{k=0}^\infty \mathcal{H}_k$ and prove Lipschitz stability on each of the infinite-dimensional $\mathcal{H}_k$ subspaces. In particular, $\mathcal{H}_0$ is the space of square-integrable harmonic perturbations. This appears to be the first Lipschitz stability result for infinite-dimensional spaces of perturbations in the context of the (linearised) Calder\'on problem. Previous optimal estimates with respect to the operator norm of the data map have been of the logarithmic-type in infinite-dimensional settings. The remarkable improvement is enabled by using the Hilbert-Schmidt norm for the Neumann-to-Dirichlet boundary map and its Fr\'echet derivative with respect to the conductivity coefficient. We also derive a direct reconstruction method that inductively yields the orthogonal projections of a general $L^2(\Omega)$ perturbation onto the $\mathcal{H}_k$ spaces, hence reconstructing any $L^2(\Omega)$ perturbation.
We prove lower bounds for the randomized approximation of the embedding $\ell_1^m \rightarrow \ell_\infty^m$ based on algorithms that use arbitrary linear (hence non-adaptive) information provided by a (randomized) measurement matrix $N \in \mathbb{R}^{n \times m}$. These lower bounds reflect the increasing difficulty of the problem for $m \to \infty$, namely, a term $\sqrt{\log m}$ in the complexity $n$. This result implies that non-compact operators between arbitrary Banach spaces are not approximable using non-adaptive Monte Carlo methods. We also compare these lower bounds for non-adaptive methods with upper bounds based on adaptive, randomized methods for recovery for which the complexity $n$ only exhibits a $(\log\log m)$-dependence. In doing so we give an example of linear problems where the error for adaptive vs. non-adaptive Monte Carlo methods shows a gap of order $n^{1/2} ( \log n)^{-1/2}$.
We consider finite element approximations to the optimal constant for the Hardy inequality with exponent $p=2$ in bounded domains of dimension $n=1$ or $n\geq 3$. For finite element spaces of piecewise linear and continuous functions on a mesh of size $h$, we prove that the approximate Hardy constant, $S_h^n$, converges to the optimal Hardy constant $S^n$ no slower than $O(1/\vert \log h \vert)$. We also show that the convergence is no faster than $O(1/\vert \log h \vert^2)$ if $n=1$ or if $n\geq 3$, the domain is the unit ball, and the finite element discretization exploits the rotational symmetry of the problem. Our estimates are compared to exact values for $S_h^n$ obtained computationally.
We present a linear-time algorithm that, given as input (i) a bipartite Pfaffian graph $G$ of minimum degree three, (ii) a Hamiltonian cycle $H$ in $G$, and (iii) an edge $e$ in $H$, outputs at least three other Hamiltonian cycles through the edge $e$ in $G$. This linear-time complexity of finding another Hamiltonian cycle given one is in sharp contrast to the problem of deciding the existence of a Hamiltonian cycle, which is NP-complete already for cubic bipartite planar graphs; such graphs are Pfaffian. Also, without the degree requirement, we show that it is NP-hard to find another Hamiltonian cycle in a bipartite Pfaffian graph. We present further improved algorithms for finding optimal traveling salesperson tours and counting Hamiltonian cycles in bipartite planar graphs with running times that are not known to hold in general planar graphs. We prove our results by a new structural technique that efficiently witnesses each Hamiltonian cycle $H$ through an arbitrary fixed anchor edge $e$ in a bipartite Pfaffian graph using a two-coloring of the vertices as advice that is unique to $H$. Previous techniques -- the Cut&Count technique of Cygan et al. [FOCS'11, TALG'22] in particular -- were able to reduce the Hamiltonian cycle problem only to essentially counting problems; our results show that counting can be avoided by leveraging properties of bipartite Pfaffian graphs. Our technique also has purely graph-theoretical consequences; for example, we show that every cubic bipartite Pfaffian graph has either zero or at least six distinct Hamiltonian cycles; the latter case is tight for the cube graph.
We provide a $O(\log^6 \log n)$-round randomized algorithm for distance-2 coloring in CONGEST with $\Delta^2+1$ colors. For $\Delta\gg\operatorname{poly}\log n$, this improves exponentially on the $O(\log\Delta+\operatorname{poly}\log\log n)$ algorithm of [Halld\'orsson, Kuhn, Maus, Nolin, DISC'20]. Our study is motivated by the ubiquity and hardness of local reductions in CONGEST. For instance, algorithms for the Local Lov\'asz Lemma [Moser, Tardos, JACM'10; Fischer, Ghaffari, DISC'17; Davies, SODA'23] usually assume communication on the conflict graph, which can be simulated in LOCAL with only constant overhead, while this may be prohibitively expensive in CONGEST. We hope our techniques help tackle in CONGEST other coloring problems defined by local relations.
注冊地址： 北京市海淀區羊坊店路18號2幢3層301-191