Given a target distribution $\pi$ and an arbitrary Markov infinitesimal generator $L$ on a finite state space $\mathcal{X}$, we develop three structured and inter-related approaches to generate new reversiblizations from $L$. The first approach hinges on a geometric perspective, in which we view reversiblizations as projections onto the space of $\pi$-reversible generators under suitable information divergences such as $f$-divergences. With different choices of functions $f$, we not only recover nearly all established reversiblizations but also unravel and generate new reversiblizations. Along the way, we unveil interesting geometric results such as bisection properties, Pythagorean identities, parallelogram laws and a Markov chain counterpart of the arithmetic-geometric-harmonic mean inequality governing these reversiblizations. This further serves as motivation for introducing the notion of information centroids of a sequence of Markov chains and to give conditions for their existence and uniqueness. Building upon the first approach, we view reversiblizations as generalized means. In this second approach, we construct new reversiblizations via different natural notions of generalized means such as the Cauchy mean or the dual mean. In the third approach, we combine the recently introduced locally-balanced Markov processes framework and the notion of convex $*$-conjugate in the study of $f$-divergence. The latter offers a rich source of balancing functions to generate new reversiblizations.
相關內容
The reconfiguration graph $\mathcal{C}_k(G)$ for the $k$-colourings of a graph $G$ has a vertex for each proper $k$-colouring of $G$, and two vertices of $\mathcal{C}_k(G)$ are adjacent precisely when those $k$-colourings differ on a single vertex of $G$. Much work has focused on bounding the maximum value of ${\rm{diam}}~\mathcal{C}_k(G)$ over all $n$-vertex graphs $G$. We consider the analogous problems for list colourings and for correspondence colourings. We conjecture that if $L$ is a list-assignment for a graph $G$ with $|L(v)|\ge d(v)+2$ for all $v\in V(G)$, then ${\rm{diam}}~\mathcal{C}_L(G)\le n(G)+\mu(G)$. We also conjecture that if $(L,H)$ is a correspondence cover for a graph $G$ with $|L(v)|\ge d(v)+2$ for all $v\in V(G)$, then ${\rm{diam}}~\mathcal{C}_{(L,H)}(G)\le n(G)+\tau(G)$. (Here $\mu(G)$ and $\tau(G)$ denote the matching number and vertex cover number of $G$.) For every graph $G$, we give constructions showing that both conjectures are best possible. Our first main result proves the upper bounds (for the list and correspondence versions, respectively) ${\rm{diam}}~\mathcal{C}_L(G)\le n(G)+2\mu(G)$ and ${\rm{diam}}~\mathcal{C}_{(L,H)}(G)\le n(G)+2\tau(G)$. Our second main result proves that both conjectured bounds hold, whenever all $v$ satisfy $|L(v)|\ge 2d(v)+1$. We conclude by proving one or both conjectures for various classes of graphs such as complete bipartite graphs, subcubic graphs, cactuses, and graphs with bounded maximum average degree.
The dichromatic number of a digraph is the minimum integer $k$ such that it admits a $k$-dicolouring, i.e. a partition of its vertices into $k$ acyclic subdigraphs. We say that a digraph $D$ is a super-orientation of an undirected graph $G$ if $G$ is the underlying graph of $D$. If $D$ does not contain any pair of symmetric arcs, we just say that $D$ is an orientation of $G$. In this work, we give both lower and upper bounds on the dichromatic number of super-orientations of chordal graphs. We also show a family of orientations of cographs for which the dichromatic number is equal to the clique number of the underlying graph.
The grounded Laplacian matrix $\LL_{-S}$ of a graph $\calG=(V,E)$ with $n=|V|$ nodes and $m=|E|$ edges is a $(n-s)\times (n-s)$ submatrix of its Laplacian matrix $\LL$, obtained from $\LL$ by deleting rows and columns corresponding to $s=|S| \ll n $ ground nodes forming set $S\subset V$. The smallest eigenvalue of $\LL_{-S}$ plays an important role in various practical scenarios, such as characterizing the convergence rate of leader-follower opinion dynamics, with a larger eigenvalue indicating faster convergence of opinion. In this paper, we study the problem of adding $k \ll n$ edges among all the nonexistent edges forming the candidate edge set $Q = (V\times V)\backslash E$, in order to maximize the smallest eigenvalue of the grounded Laplacian matrix. We show that the objective function of the combinatorial optimization problem is monotone but non-submodular. To solve the problem, we first simplify the problem by restricting the candidate edge set $Q$ to be $(S\times (V\backslash S))\backslash E$, and prove that it has the same optimal solution as the original problem, although the size of set $Q$ is reduced from $O(n^2)$ to $O(n)$. Then, we propose two greedy approximation algorithms. One is a simple greedy algorithm with an approximation ratio $(1-e^{-\alpha\gamma})/\alpha$ and time complexity $O(kn^4)$, where $\gamma$ and $\alpha$ are, respectively, submodularity ratio and curvature, whose bounds are provided for some particular cases. The other is a fast greedy algorithm without approximation guarantee, which has a running time $\tilde{O}(km)$, where $\tilde{O}(\cdot)$ suppresses the ${\rm poly} (\log n)$ factors. Numerous experiments on various real networks are performed to validate the superiority of our algorithms, in terms of effectiveness and efficiency.
Given an undirected graph $G$ and a multiset of $k$ terminal pairs $\mathcal{X}$, the Vertex-Disjoint Paths (\VDP) and Edge-Disjoint Paths (\EDP) problems ask whether $G$ has $k$ pairwise internally vertex-disjoint paths and $k$ pairwise edge-disjoint paths, respectively, connecting every terminal pair in~$\mathcal{X}$. In this paper, we study the kernelization complexity of \VDP~and~\EDP~on subclasses of chordal graphs. For \VDP, we design a $4k$ vertex kernel on split graphs and an $\mathcal{O}(k^2)$ vertex kernel on well-partitioned chordal graphs. We also show that the problem becomes polynomial-time solvable on threshold graphs. For \textsc{EDP}, we first prove that the problem is $\mathsf{NP}$-complete on complete graphs. Then, we design an $\mathcal{O}(k^{2.75})$ vertex kernel for \EDP~on split graphs, and improve it to a $7k+1$ vertex kernel on threshold graphs. Lastly, we provide an $\mathcal{O}(k^2)$ vertex kernel for \EDP~on block graphs and a $2k+1$ vertex kernel for clique paths. Our contributions improve upon several results in the literature, as well as resolve an open question by Heggernes et al.~[Theory Comput. Syst., 2015].
We consider the two-pronged fork frame $F$ and the variety $\mathbf{Eq}(B_F)$ generated by its dual closure algebra $B_F$. We describe the finite projective algebras in $\mathbf{Eq}(B_F)$ and give a purely semantic proof that unification in $\mathbf{Eq}(B_F)$ is finitary and not unitary.
Given a hypergraph $\mathcal{H}$, the dual hypergraph of $\mathcal{H}$ is the hypergraph of all minimal transversals of $\mathcal{H}$. The dual hypergraph is always Sperner, that is, no hyperedge contains another. A special case of Sperner hypergraphs are the conformal Sperner hypergraphs, which correspond to the families of maximal cliques of graphs. All these notions play an important role in many fields of mathematics and computer science, including combinatorics, algebra, database theory, etc. In this paper we study conformality of dual hypergraphs. While we do not settle the computational complexity status of recognizing this property, we show that the problem is in co-NP and can be solved in polynomial time for hypergraphs of bounded dimension. In the special case of dimension $3$, we reduce the problem to $2$-Satisfiability. Our approach has an implication in algorithmic graph theory: we obtain a polynomial-time algorithm for recognizing graphs in which all minimal transversals of maximal cliques have size at most $k$, for any fixed $k$.
The complexity class Quantum Statistical Zero-Knowledge ($\mathsf{QSZK}$) captures computational difficulties of the time-bounded quantum state testing problem with respect to the trace distance, known as the Quantum State Distinguishability Problem (QSDP) introduced by Watrous (FOCS 2002). However, QSDP is in $\mathsf{QSZK}$ merely within the constant polarizing regime, similar to its classical counterpart shown by Sahai and Vadhan (JACM 2003) due to the polarization lemma (error reduction for SDP). Recently, Berman, Degwekar, Rothblum, and Vasudevan (TCC 2019) extended the $\mathsf{SZK}$ containment for SDP beyond the polarizing regime via the time-bounded distribution testing problems with respect to the triangular discrimination and the Jensen-Shannon divergence. Our work introduces proper quantum analogs for these problems by defining quantum counterparts for triangular discrimination. We investigate whether the quantum analogs behave similarly to their classical counterparts and examine the limitations of existing approaches to polarization regarding quantum distances. These new $\mathsf{QSZK}$-complete problems improve $\mathsf{QSZK}$ containments for QSDP beyond the polarizing regime and establish a simple $\mathsf{QSZK}$-hardness for the quantum entropy difference problem (QEDP) defined by Ben-Aroya, Schwartz, and Ta-Shma (ToC 2010). Furthermore, we prove that QSDP with some exponentially small errors is in $\mathsf{PP}$, while the same problem without error is in $\mathsf{NQP}$.
In this work we show that given a connectivity graph $G$ of a $[[n,k,d]]$ quantum code, there exists $\{K_i\}_i, K_i \subset G$, such that $\sum_i |K_i|\in \Omega(k), \ |K_i| \in \Omega(d)$, and the $K_i$'s are $\tilde{\Omega}( \sqrt{{k}/{n}})$-expander. If the codes are classical we show instead that the $K_i$'s are $\tilde{\Omega}\left({{k}/{n}}\right)$-expander. We also show converses to these bounds. In particular, we show that the BPT bound for classical codes is tight in all Euclidean dimensions. Finally, we prove structural theorems for graphs with no "dense" subgraphs which might be of independent interest.
In this paper, we study the smallest non-zero eigenvalue of the sample covariance matrices $\mathcal{S}(Y)=YY^*$, where $Y=(y_{ij})$ is an $M\times N$ matrix with iid mean $0$ variance $N^{-1}$ entries. We prove a phase transition for its distribution, induced by the fatness of the tail of $y_{ij}$'s. More specifically, we assume that $y_{ij}$ is symmetrically distributed with tail probability $\mathbb{P}(|\sqrt{N}y_{ij}|\geq x)\sim x^{-\alpha}$ when $x\to \infty$, for some $\alpha\in (2,4)$. We show the following conclusions: (i). When $\alpha>\frac83$, the smallest eigenvalue follows the Tracy-Widom law on scale $N^{-\frac23}$; (ii). When $2<\alpha<\frac83$, the smallest eigenvalue follows the Gaussian law on scale $N^{-\frac{\alpha}{4}}$; (iii). When $\alpha=\frac83$, the distribution is given by an interpolation between Tracy-Widom and Gaussian; (iv). In case $\alpha\leq \frac{10}{3}$, in addition to the left edge of the MP law, a deterministic shift of order $N^{1-\frac{\alpha}{2}}$ shall be subtracted from the smallest eigenvalue, in both the Tracy-Widom law and the Gaussian law. Overall speaking, our proof strategy is inspired by \cite{ALY} which is originally done for the bulk regime of the L\'{e}vy Wigner matrices. In addition to various technical complications arising from the bulk-to-edge extension, two ingredients are needed for our derivation: an intermediate left edge local law based on a simple but effective matrix minor argument, and a mesoscopic CLT for the linear spectral statistic with asymptotic expansion for its expectation.
Given a set of points $P = (P^+ \sqcup P^-) \subset \mathbb{R}^d$ for some constant $d$ and a supply function $\mu:P\to \mathbb{R}$ such that $\mu(p) > 0~\forall p \in P^+$, $\mu(p) < 0~\forall p \in P^-$, and $\sum_{p\in P}{\mu(p)} = 0$, the geometric transportation problem asks one to find a transportation map $\tau: P^+\times P^-\to \mathbb{R}_{\ge 0}$ such that $\sum_{q\in P^-}{\tau(p, q)} = \mu(p)~\forall p \in P^+$, $\sum_{p\in P^+}{\tau(p, q)} = -\mu(q)~ \forall q \in P^-$, and the weighted sum of Euclidean distances for the pairs $\sum_{(p,q)\in P^+\times P^-}\tau(p, q)\cdot ||q-p||_2$ is minimized. We present the first deterministic algorithm that computes, in near-linear time, a transportation map whose cost is within a $(1 + \varepsilon)$ factor of optimal. More precisely, our algorithm runs in $O(n\varepsilon^{-(d+2)}\log^5{n}\log{\log{n}})$ time for any constant $\varepsilon > 0$. Surprisingly, our result is not only a generalization of a bipartite matching one to arbitrary instances of geometric transportation, but it also reduces the running time for all previously known $(1 + \varepsilon)$-approximation algorithms, randomized or deterministic, even for geometric bipartite matching. In particular, we give the first $(1 + \varepsilon)$-approximate deterministic algorithm for geometric bipartite matching and the first $(1 + \varepsilon)$-approximate deterministic or randomized algorithm for geometric transportation with no dependence on $d$ in the exponent of the running time's polylog. As an additional application of our main ideas, we also give the first randomized near-linear $O(\varepsilon^{-2} m \log^{O(1)} n)$ time $(1 + \varepsilon)$-approximation algorithm for the uncapacitated minimum cost flow (transshipment) problem in undirected graphs with arbitrary real edge costs.
注冊地址： 北京市海淀區羊坊店路18號2幢3層301-191