Strong-Diameter Network Decomposition

Network decomposition is a central concept in the study of distributed graph algorithms. We present the first polylogarithmic-round deterministic distributed algorithm with small messages that constructs a strong-diameter network decomposition with polylogarithmic parameters. Concretely, a ($C$, $D$) strong-diameter network decomposition is a partitioning of the nodes of the graph into disjoint clusters, colored with $C$ colors, such that neighboring clusters have different colors and the subgraph induced by each cluster has a diameter at most $D$. In the weak-diameter variant, the requirement is relaxed by measuring the diameter of each cluster in the original graph, instead of the subgraph induced by the cluster. A recent breakthrough of Rozhov{n} and Ghaffari [STOC 2020] presented the first $text{poly}(log n)$-round deterministic algorithm for constructing a weak-diameter network decomposition where $C$ and $D$ are both in $text{poly}(log n)$. Their algorithm uses small $O(log n)$-bit messages. One can transform their algorithm to a strong-diameter network decomposition algorithm with similar parameters. However, that comes at the expense of requiring unbounded messages. The key remaining qualitative question in the study of network decompositions was whether one can achieve a similar result for strong-diameter network decompositions using small messages. We resolve this question by presenting a novel technique that can transform any black-box weak-diameter network decomposition algorithm to a strong-diameter one, using small messages and with only moderate loss in the parameters.

Locally Checkable Problems in Rooted Trees

Consider any locally checkable labeling problem $Pi$ in rooted regular trees: there is a finite set of labels $Sigma$, and for each label $x in Sigma$ we specify what are permitted label combinations of the children for an internal node of label $x$ (the leaf nodes are unconstrained). This formalism is expressive enough to capture many classic problems studied in distributed computing, including vertex coloring, edge coloring, and maximal independent set. We show that the distributed computational complexity of any such problem $Pi$ falls in one of the following classes: it is $O(1)$, $Theta(log^* n)$, $Theta(log n)$, or $n^{Theta(1)}$ rounds in trees with $n$ nodes (and all of these classes are nonempty). We show that the complexity of any given problem is the same in all four standard models of distributed graph algorithms: deterministic $mathsf{LOCAL}$, randomized $mathsf{LOCAL}$, deterministic $mathsf{CONGEST}$, and randomized $mathsf{CONGEST}$ model. In particular, we show that randomness does not help in this setting, and the complexity class $Theta(log log n)$ does not exist (while it does exist in the broader setting of general trees). We also show how to systematically determine the complexity class of any such problem $Pi$, i.e., whether $Pi$ takes $O(1)$, $Theta(log^* n)$, $Theta(log n)$, or $n^{Theta(1)}$ rounds. While the algorithm may take exponential time in the size of the description of $Pi$, it is nevertheless practical: we provide a freely available implementation of the classifier algorithm, and it is fast enough to classify many problems of interest.

Constructing higher-order topological states in higher dimension

Higher-order topological phase as a generalization of Berry phase attracts an enormous amount of research. The current theoretical models supporting higher-order topological phases, however, cannot give the connection between lower and higher-order topological phases when extending the lattice from lower to higher dimensions. Here, we theoretically propose and experimentally demonstrate a topological corner state constructed from the edge states in one dimensional lattice. The two-dimensional square lattice owns independent spatial modulation of coupling in each direction, and the combination of edge states in each direction come up to the higher-order topological corner state in two-dimensional lattice, revealing the connection of topological phase in lower and higher dimensional lattices. Moreover, the topological corner states in two-dimensional lattice can also be viewed as the dimension-reduction from a four-dimensional topological phase characterized by vector Chern number, considering two modulation phases as synthetic dimensions in Aubry-Andre-Harper model discussed as example here. Our work deeps the understanding to topological phases breaking through the lattice dimension, and provides a promising tool constructing higher topological phases in higher dimensional structures.

Distributed graph problems through an automata-theoretic lens

The locality of a graph problem is the smallest distance $T$ such that each node can choose its own part of the solution based on its radius-$T$ neighborhood. In many settings, a graph problem can be solved efficiently with a distributed or parallel algorithm if and only if it has a small locality. In this work we seek to automate the study of solvability and locality: given the description of a graph problem $Pi$, we would like to determine if $Pi$ is solvable and what is the asymptotic locality of $Pi$ as a function of the size of the graph. Put otherwise, we seek to automatically synthesize efficient distributed and parallel algorithms for solving $Pi$. We focus on locally checkable graph problems; these are problems in which a solution is globally feasible if it looks feasible in all constant-radius neighborhoods. Prior work on such problems has brought primarily bad news: questions related to locality are undecidable in general, and even if we focus on the case of labeled paths and cycles, determining locality is $mathsf{PSPACE}$-hard (Balliu et al., PODC 2019). We complement prior negative results with efficient algorithms for the cases of unlabeled paths and cycles and, as an extension, for rooted trees. We introduce a new automata-theoretic perspective for studying locally checkable graph problems. We represent a locally checkable problem $Pi$ as a nondeterministic finite automaton $mathcal{M}$ over a unary alphabet. We identify polynomial-time-computable properties of the automaton $mathcal{M}$ that near-completely capture the solvability and locality of $Pi$ in cycles and paths, with the exception of one specific case that is $mbox{co-$mathsf{NP}$}$-complete.

Observing Movement of Dirac Cones from Single-Photon Dynamics

Graphene with honeycomb structure, being critically important in understanding physics of matter, exhibits exceptionally unusual half-integer quantum Hall effect and unconventional electronic spectrum with quantum relativistic phenomena. Particularly, graphene-like structure can be used for realizing topological insulator which inspires an intrinsic topological protection mechanism with strong immunity for maintaining coherence of quantum information. These various peculiar physics arise from the unique properties of Dirac cones which show high hole degeneracy, massless charge carriers and linear intersection of bands. Experimental observation of Dirac cones conventionally focuses on the energy-momentum space with bulk measurement. Recently, the wave function and band structure have been mapped into the real-space in photonic system, and made flexible control possible. Here, we demonstrate a direct observation of the movement of Dirac cones from single-photon dynamics in photonic graphene under different biaxial strains. Sharing the same spirit of wave-particle nature in quantum mechanics, we identify the movement of Dirac cones by dynamically detecting the edge modes and extracting the diffusing distance of the packets with accumulation and statistics on individual single-particle registrations. Our results of observing movement of Dirac cones from single-photon dynamics, together with the method of direct observation in real space by mapping the band structure defined in momentum space, pave the way to understand a variety of artificial structures in quantum regime.

Observation of Magic Angle and Wall State in Twisted Bilayer Photonic Graphene

Graphene, a one-layer honeycomb lattice of carbon atoms, exhibits unconventional phenomena and attracts much interest since its discovery. Recently, an unexpected Mott-like insulator state induced by moire pattern and a superconducting state are observed in magic-angle-twisted bilayer graphene, especially, without correlations between electrons, which gives more hints for the understanding and investigation of strongly correlated phenomena. The photon as boson, behaving differently with fermion, can also retrieve the unconventional phenomena of graphene, such as the bearded edge state which is even never been observed in graphene due to the unstability. Here, we present a direct observation of magic angle and wall state in twisted bilayer photonic graphene. We successfully observe the strong localization and rapid diffusion of photon at the regions with AA and AB stacking order around the magic angle, respectively. Most importantly, we find a wall state showing the photon distribution distinctly separate at the regions with AA and AB/BA stacking order in the lowest-energy band. The mechanism underlying the wall states may help to understand the existence of both Mott-like insulating state and superconducting state in magic-angle twisted bilayer graphene. The accessibility of magic angle in twisted bilayer photonic graphene adds the boson behavior into graphene superlattice and the observation of wall state will also deep the understanding of matter.

Improved Distributed Expander Decomposition and Nearly Optimal Triangle Enumeration

An $(epsilon,phi)$-expander decomposition of a graph $G=(V,E)$ is a clustering of the vertices $V=V_{1}cupcdotscup V_{x}$ such that (1) each cluster $V_{i}$ induces subgraph with conductance at least $phi$, and (2) the number of inter-cluster edges is at most $epsilon|E|$. In this paper, we give an improved distributed expander decomposition. Specifically, we construct an $(epsilon,phi)$-expander decomposition with $phi=(epsilon/log n)^{2^{O(k)}}$ in $O(n^{2/k}cdottext{poly}(1/phi,log n))$ rounds for any $epsilonin(0,1)$ and positive integer $k$. For example, a $(0.01,1/text{poly}log n)$-expander decomposition can be computed in $O(n^{gamma})$ rounds, for any arbitrarily small constant $gamma>0$. Previously, the algorithm by Chang, Pettie, and Zhang can construct a $(1/6,1/text{poly}log n)$-expander decomposition using $tilde{O}(n^{1-delta})$ rounds for any $delta>0$, with a caveat that the algorithm is allowed to throw away a set of edges into an extra part which forms a subgraph with arboricity at most $n^{delta}$. Our algorithm does not have this caveat. By slightly modifying the distributed algorithm for routing on expanders by Ghaffari, Kuhn and Su [PODC17], we obtain a triangle enumeration algorithm using $tilde{O}(n^{1/3})$ rounds. This matches the lower bound by Izumi and Le Gall [PODC17] and Pandurangan, Robinson and Scquizzato [SPAA18] of $tilde{Omega}(n^{1/3})$ which holds even in the CONGESTED CLIQUE model. This provides the first non-trivial example for a distributed problem that has essentially the same complexity (up to a polylogarithmic factor) in both CONGEST and CONGESTED CLIQUE. The key technique in our proof is the first distributed approximation algorithm for finding a low conductance cut that is as balanced as possible. Previous distributed sparse cut algorithms do not have this nearly most balanced guarantee.

The Complexity of $(Delta + 1)$Coloring inCongested Clique, Massively Parallel Computation,and Centralized Local Computation

We present new randomized algorithms that improve the complexity of the classic $(Delta+1)$-coloring problem, and its generalization $(Delta+1)$-list-coloring, in three well-studied models of distributed, parallel, and centralized computation: Distributed Congested Clique: We present an $O(1)$-round randomized algorithm for $(Delta+1)$-list coloring in the congested clique model of distributed computing. This settles the asymptotic complexity of this problem. It moreover improves upon the $O(log^ast Delta)$-round randomized algorithms of Parter and Su [DISC18] and $O((loglog Delta)cdot log^ast Delta)$-round randomized algorithm of Parter [ICALP18]. Massively Parallel Computation: We present a $(Delta+1)$-list coloring algorithm with round complexity $O(sqrt{loglog n})$ in the Massively Parallel Computation (MPC) model with strongly sublinear memory per machine. This algorithm uses a memory of $O(n^{alpha})$ per machine, for any desirable constant $alpha>0$, and a total memory of $widetilde{O}(m)$, where $m$ is the size of the graph. Notably, this is the first coloring algorithm with sublogarithmic round complexity, in the sublinear memory regime of MPC. For the quasilinear memory regime of MPC, an $O(1)$-round algorithm was given very recently by Assadi et al. [SODA19]. Centralized Local Computation: We show that $(Delta+1)$-list coloring can be solved with $Delta^{O(1)} cdot O(log n)$ query complexity, in the centralized local computation model. The previous state-of-the-art for $(Delta+1)$-list coloring in the centralized local computation model are based on simulation of known LOCAL algorithms.

Distributed Triangle Detection via Expander Decomposition

We present improved distributed algorithms for triangle detection and its variants in the CONGEST model. We show that Triangle Detection, Counting, and Enumeration can be solved in $tilde{O}(n^{1/2})$ rounds. In contrast, the previous state-of-the-art bounds for Triangle Detection and Enumeration were $tilde{O}(n^{2/3})$ and $tilde{O}(n^{3/4})$, respectively, due to Izumi and LeGall (PODC 2017). The main technical novelty in this work is a distributed graph partitioning algorithm. We show that in $tilde{O}(n^{1-delta})$ rounds we can partition the edge set of the network $G=(V,E)$ into three parts $E=E_mcup E_scup E_r$ such that (a) Each connected component induced by $E_m$ has minimum degree $Omega(n^delta)$ and conductance $Omega(1/text{poly} log(n))$. As a consequence the mixing time of a random walk within the component is $O(text{poly} log(n))$. (b) The subgraph induced by $E_s$ has arboricity at most $n^{delta}$. (c) $|E_r| leq |E|/6$. All of our algorithms are based on the following generic framework, which we believe is of interest beyond this work. Roughly, we deal with the set $E_s$ by an algorithm that is efficient for low-arboricity graphs, and deal with the set $E_r$ using recursive calls. For each connected component induced by $E_m$, we are able to simulate congested clique algorithms with small overhead by applying a routing algorithm due to Ghaffari, Kuhn, and Su (PODC 2017) for high conductance graphs.

The Energy Complexity of Broadcast

Energy is often the most constrained resource in networks of battery-powered devices, and as devices become smaller, they spend a larger fraction of their energy on communication (transceiver usage) not computation. As an imperfect proxy for true energy usage, we define energy complexity to be the number of time slots a device transmits/listens; idle time and computation are free. In this paper we investigate the energy complexity of fundamental communication primitives such as broadcast in multi-hop radio networks. We consider models with collision detection (CD) and without (No-CD), as well as both randomized and deterministic algorithms. Some take-away messages from this work include: 1. The energy complexity of broadcast in a multi-hop network is intimately connected to the time complexity of leader election in a single-hop (clique) network. Many existing lower bounds on time complexity immediately transfer to energy complexity. For example, in the CD and No-CD models, we need $Omega(log n)$ and $Omega(log^2 n)$ energy, respectively. 2. The energy lower bounds above can almost be achieved, given sufficient ($Omega(n)$) time. In the CD and No-CD models we can solve broadcast using $O(frac{log nloglog n}{logloglog n})$ energy and $O(log^3 n)$ energy, respectively. 3. The complexity measures of Energy and Time are in conflict, and it is an open problem whether both can be minimized simultaneously. We give a tradeoff showing it is possible to be nearly optimal in both measures simultaneously. For any constant $epsilon>0$, broadcast can be solved in $O(D^{1+epsilon}log^{O(1/epsilon)} n)$ time with $O(log^{O(1/epsilon)} n)$ energy, where $D$ is the diameter of the network.