network architects

Abstract: Expander graphs have been central objects of study for over fifty years. Ramanujan graphs attain the asymptotically optimal nontrivial adjacency-eigenvalue threshold for infinite fixed-degree families. The original arithmetic constructions by Lubotzky-Phillips-Sarnak (1988) and Margulis (1988), and the iterative $2$-lift method of Bilu-Linial (2006) provide different approaches to Ramanujan graph constructions. Motivated by work on Mealy automata, we combine both approaches to give the following new arithmetic construction. For every prime $p\equiv 1\pmod {17}$, we construct a infinite tower of $(p+1)$-regular non-bipartite Ramanujan graphs on $2^n$ vertices, with label-preserving $2$-lifts between consecutive levels. These construction is strongly explicit: for fixed $p$, a neighbor or lift sign is computable in $O_p(n^3)$ bit operations. The construction uses fixed algebraic $2$-adic transformations, specified by finite data computable in preprocessing depending only on $p$. The main number-theoretic tool is Blasius's Ramanujan-Petersson theorem for Hilbert modular forms, applied through the Jacquet-Langlands correspondence to obtain the sharp bound $|λ|\leq2\sqrt p$ for every nontrivial adjacency eigenvalue of our $(p+1)$-regular graphs. The transformations preserve $2$-adic distance, which gives the binary covers and an explicit formula for their signings.

Abstract: Autonomous agents are moving from application-layer components to active participants in networked systems. They not only generate traffic but also perceive context, express intent, invoke services, coordinate with other agents, and act under task, policy, and resource constraints. This evolution exposes a mismatch between emerging agentic interactions and conventional endpoint- and traffic-centric network abstractions. This white paper introduces Agentic Communication Networks (ACN) as a network-centric paradigm for the time when agents become first-order network entities. At its core, ACN reshapes networking around three fundamental aspects. First, agents are represented as identifiable and governable network entities with explicit identity, authority, and lifecycle. Second, agentic services are expressed through intent, capability, context, policy, and task state, allowing the network to capture what an agent seeks to accomplish and under what conditions. Third, agentic execution becomes an explicit network concern as tasks involve multiple agents, services, tools, and distributed capabilities across heterogeneous infrastructures. Based on these shifts, the paper defines the scope, principles, architecture, and research directions of ACN, positioning it as a networking foundation for autonomous agent ecosystems.

Abstract: Let $G=(V,E)$ be a $d$-uniform hypergraph with $|V|=n$ and $|E|=m$. Estimating $m$ from uniformly random hyperedge samples requires $Θ(\sqrt{m})$ samples by a birthday-paradox argument. We investigate the power of conditional sampling through a hierarchy of oracles: for an integer $1\le s\le d$, given pairwise disjoint subsets $X_1,\ldots,X_s\subseteq V$, the $s$-colorful oracle returns a hyperedge chosen uniformly at random from all hyperedges contained in $X_1\cup\cdots\cup X_s$ that intersect every $X_i$, provided one exists. For $s=1$, this samples a uniformly random hyperedge induced by $X_1$. For every $1\le s\le d$, we give a randomized algorithm that outputs $\widehat{m}\in[(1-\varepsilon)m,(1+\varepsilon)m]$ with probability at least $2/3$ using $O_{s,d}(\operatorname{poly}(1/\varepsilon,\log n))$ conditional samples, where the exponent of $\log n$ is an absolute constant independent of both $s$ and $d$. Conditional sampling thus yields an exponential separation over uniform hyperedge sampling. We also study the decision version, in which the oracle only reports whether a qualifying hyperedge exists. For every $1\le s<d$, we prove that any algorithm using the $s$-colorful decision oracle requires $\widetildeΩ_{s,d}(n^{\frac{d-s}{d-s+1}})$ queries. Hence, for $s<d$, access to uniformly random witness hyperedges (random certificates) is exponentially more powerful than existence queries. For $s=d$, decision queries alone achieve $\operatorname{poly}(1/\varepsilon,\log n)$ query complexity, but the exponent of $\log n$ is known to be $Θ(d)$. The colorful hierarchy thus exhibits a phase transition at $s=d$: for $s<d$, random certificates are essential for polylogarithmic-query estimation, whereas at $s=d$ decision queries suffice, yet random certificates still provably reduce the exponent of $\log n$ from $Θ(d)$ to an absolute constant.

Abstract: CXL Memory Module - Memory Pooling (CMM-MP) introduces a novel memory pooling architecture to meet the unique requirements of emerging memory-intensive workloads. This industry-first, purpose-built memory-pooling device combines the benefits of Compute Express Link (CXL) with the scalability and cost advantages of Ethernet. Multiple CMM-MP devices together provide a flexible, composable, and disaggregated memory expansion solution. The CMM-MP enables 100s of TB capacity for GPU/CPU applications without modifications. The memory pool is exposed as a large-capacity logical aggregate memory, with all pool discovery, composition, and backend network datapath tasks fully offloaded to the device. CMM-MP supports both memory pooling and sharing usage modes. It provides an application latency of 2.7 us and up to 23 GB/s of memory throughput. Our evaluations demonstrate that CMM-MP significantly outperforms RDMA-based solutions in latency and throughput. We also evaluated real-world use cases of Valkey+YCSB and DiskANN using CMM-MP.

Abstract: We give a new rounding technique for spreading-metric linear programs, called Greedy Region Growing, which adapts the classical technique of region growing to min-max graph layout problems and flow-expander decomposition. Using this technique, we obtain state-of-the-art approximation algorithms for several fundamental problems. (1) An $O(\log n)$-approximation for Cutwidth and Pathwidth, improving upon the previous bound of $O(\log n\exp(O(\sqrt{\log\log n})))$ due to Bansal, Katzelnick, and Schwartz (FOCS 2024). This matches the $Ω(\log n)$ integrality gap of the standard LP relaxations. (2) An $O(\log n)$-approximation for their directed analogues, Minimum Storage and Minimum Register Sufficiency on directed acyclic graphs, improving the previous bound of $O(\log^{3/2} n)$. (3) A $φ$-flow-expander decomposition that cuts at most an $O(φ\log n\log\log n)$ fraction of the edges. This improves the $O(φ\log n\exp(O(\sqrt{\log\log n})))$ bound of Bansal, Jambulapati, and Saranurak (ICALP 2026), and is within an $O(\log\log n)$ factor of the graph-theoretic lower bound. The vertex version of our algorithm also gives an $O(\log n)$-approximation for Treedepth. In particular, our results answer several open problems of Bansal, Katzelnick, and Schwartz (FOCS 2024). Technically, we also solve the conceptual question raised by their work: our technique shows how to adapt Seymour recursion to min-max objectives, and constructs $O(1)$-weak local partitions in spreading metrics.

Abstract: Let $D$ be a finite simple minimally strongly $k$-connected digraph, where $k\ge 2$, and let $n=|V(D)|$. Mader proved in 1985 that $|A(D)|\le 2k(n-k)$ for all sufficiently large $n$, with equality if and only if $D\cong \overleftrightarrow{K}_{k,n-k}$ (JCTB 1985). We prove that this bound holds whenever $n\ge 3k-1$ and that the order threshold $3k-1$ is best possible. Moreover, if $n\ge 3k$, then equality holds if and only if $D\cong \overleftrightarrow{K}_{k,n-k}$. The threshold $3k$ is also best possible. These results resolve the conjecture of Mader in (JCTB 1985).

Abstract: Chekuri, Gupta, Newman, Rabinovich, and Sinclair [SODA'03] showed that $k$-outerplanar graphs can be embedded into trees and $\ell_1$ with distortion $2^{O(k)}$. Their result is perhaps the strongest evidence supporting the still-open planar $\ell_1$-embedding conjecture: planar metrics can be embedded into $\ell_1$ with constant distortion. However, the exponential dependency on $k$ in their distortion bound remains the state of the art. Their embedding is obtained by a so-called onion-peeling approach: removing one layer of the graph at a time at the cost of incurring $O(1)$ distortion multiplicatively, and recursively embedding the resulting $(k-1)$-outerplanar graph. In this paper, we devise a new onion peeling approach that peels $k/2$ layers off the input $k$-outerplanar graph at every step. As a result, we obtain the first embedding of $k$-outerplanar graphs into trees and $\ell_1$ with distortion $\operatorname{poly}(k)$, an exponential improvement over the best-known distortion bound [SODA'03]. Our result of embeddings into trees comes closer to the distortion lower bound $Ω(k)$ for $k$-outerplanar graphs.

Abstract: Decentralized learning is highly sensitive to communication topology under non-IID data. Adaptive peer-selection methods can exploit local model information, but broader peer discovery may require increasingly large control state, whereas direct spectral optimization typically relies on graph-wide information. We study the intermediate setting of bounded local topology search and propose Local-First Heuristic Evolution (LFHE), a representation-driven rewiring framework whose candidate discovery and scoring use only ego-neighborhood and friend-of-a-friend (FoF) information. The structural score admits an exact interpretation through graph Dirichlet energy: its sum across clients equals twice the representation Dirichlet energy, which under standard linear consensus dynamics governs the instantaneous dissipation of representation disagreement. LFHE combines this state-dependent structural signal with early exploration and degree control, while algebraic connectivity remains an offline graph diagnostic. Under bounded sparse degree, its FoF candidate state remains local rather than expanding toward population-wide peer tracking. Across four image, speech, and text benchmarks, LFHE achieves competitive decentralized learning performance. Matched-protocol controls identify the structural term as the principal empirical topology-selection signal, while comparison with broader peer discovery exposes a trade-off between predictive performance and discovery-state locality. Together, these results motivate state-aware bounded local topology search between pairwise peer selection and globally informed topology optimization.

Abstract: As mobile communications cross the threshold from 5G to 6G, the 3GPP has entered a decisive phase. Following the Technical Specification Group (TSG) plenary meetings of June 2026 and the associated 6G workshop in Singapore, the Release-20 study phase is now well underway across all three TSGs: Radio Access Network (RAN), Service and System Aspects (SA), and Core Network and Terminals (CT). Concurrently, the timeline for the first normative 6G specifications in Release 21 has been established. Rather than offering another technology vision, or a chronological account of committee progress, this article asks what the first body of agreed 6G material tells us. We review service requirements, system architecture, the emerging radio interface, native AI, ISAC, non-terrestrial networks (NTN), and core-network protocols, tracing how each moves from study item toward specification. Read across the three TSGs, this material also supports seven cross-cutting lessons: AI has moved from a feature to a primitive spanning every stage, non-terrestrial access has crossed from overlay to substrate, and connectivity is now one objective among three alongside computing and sensing; the industry favors deployability over redesign, with spectrum access and site reuse, rather than waveform innovation, appearing to be the tighter constraint; and standardization targets AI workflows rather than AI models, with testability across vendors recurring as a decisive criterion for which techniques survive. Because the material spans very different stages of maturity, every item cited is tagged with its status at a single snapshot date (approved, draft, individually proposed, or vendor-demonstrated), and the lessons are offered as the authors' synthesis rather than as 3GPP positions. We close with the road toward trials and commercial launch around 2030, and with the open questions these lessons help prioritize.

Abstract: AI clusters increasingly run large language model (LLM) inference and training on the same fabric. Prefill-decode (P-D) disaggregation creates key-value (KV) cache transfers between prefill and decode groups, whereas training collectives and all-to-all traffic benefit from near-uniform global connectivity. A static sparse topology can therefore be poorly matched to one of the two traffic patterns. We present Mode-Switching Expander (MoSE), a reconfigurable expander that treats topology design as a fixed-degree edge-allocation problem. MoSE reallocates the same sparse edge budget toward direct P-D connectivity in inference-heavy modes and restores a uniform random regular expander in training-heavy modes. We evaluate MoSE using a 1024-group flow-level topology model, shortest-path routing, and two mixed workloads. Across 20 seeds, MoSE reduces average and 95th-percentile (P95) load-aware KV communication cost by 90.8\% and 91.9\% relative to Static-Training in the inference-heavy mode. In the training-heavy mode, it reduces average and P95 training communication cost by 22.7\% and 27.6\% relative to stale Static-Inference. These results show that coarse-grained topology switching can support both workload modes without additional ports or routing changes.

Abstract: Vision-Language Models (VLMs) enable edge devices like unmanned aerial vehicles (UAVs) to interpret visual observations and reason about complex environments using natural-language instructions. However, their practical deployment remains challenging as onboard inference is constrained by limited computational, memory, and energy resources, whereas cloud-based inference introduces communication latency, bandwidth overhead, and dependence on network connectivity. To address these limitations, split computing offers a promising alternative by partitioning VLM inference between the resource-constrained UAVs and more capable remote servers. However, the performance trade-offs among fully onboard, cloud-based, and split-computing architectures for lightweight VLMs have not yet been systematically profiled. This paper benchmarks these three deployment paradigms using SmolVLM-256M as a representative lightweight VLM. We quantify their inference latency, computational resource utilization, communication overhead, and energy consumption across varying image resolutions and network conditions. Our results show that no deployment strategy is universally optimal; instead, the preferred strategy depends on the interaction between network conditions and input image resolution.

Abstract: We show that isomorphism of $F$-free tournaments can be solved in FPT time $f(k) \cdot n^{O(1)}$, where $k$ denotes the size of $F$, and $n$ denotes the size of the input tournaments. Our result extends on a previous FPT isomorphism test for tournaments of bounded twin-width [Grohe, Neuen 2024], as well as XP isomorphism tests parameterized by the VC dimension or the chromatic number [Raßmann, Schweitzer 2026]. It also implies that every non-trivial hereditary class of tournaments admits a polynomial-time isomorphism test. Our algorithm builds on a novel combination of spectral, geometric, combinatorial and group-theoretic tools.

Abstract: In the 1960s, Erdős and Hajnal conjectured that every graph with sufficiently large chromatic number contains a subgraph of large girth (size of a smallest cycle) and large chromatic number. In this paper, we prove that every tournament with sufficiently large dichromatic number contains a subdigraph of large digirth (size of a smallest directed cycle) and large dichromatic number. We investigate the same statement when replacing digirth by girth (of the underlying graph). We show that it implies the conjecture of Erdős and Hajnal, and prove it for a particular family of tournaments.

Abstract: Chatterjee and Sloman proved that a bounded measurable similarity function with sufficiently small average Gromov hyperbolicity admits a tree representation with small mean approximation error. Their argument uses a weighted version of Szemerédi's regularity lemma and does not yield useful quantitative bounds. Here, we establish an explicit relation between average hyperbolicity and mean tree approximation error. For a similarity function $s:S\times S\to[0,b]$, we prove that \[ \Tree(s) \leq (63/e)^{1/3} \sqrt[3]{b^2 \Hyp(s)} \leq 2.8512 \sqrt[3]{b^2 \Hyp(s)}.\] The proof uses a simple pivoting construction inspired by \textsc{KwikCluster}. We also discuss the optimal dependence on average hyperbolicity, including a square-root lower bound, and connections with ultrametric fitting.

Abstract: At edge price $α=1$, we construct an infinite family of pure Nash equilibria of the unilateral max-distance network creation game with $\PoA\ge2^{\sqrt{\log_2 n}-O(\log\log n)}$. Together with the known upper bound, this gives $2^{Θ(\sqrt{\log n})}$ along the constructed sequence of population sizes. We subdivide every edge of the bipartite double cover of a distance-uniform graph with large diameter constructed by Lavrov, Loh and Messegué, and let each subdivision vertex buy its two incident edges. A distance calculation rules out every profitable unilateral deviation. The equilibria are not strict. We also give a short proof that the price of anarchy is constant for every polynomially vanishing edge price.

Abstract: In this paper, we introduce the problem of private information retrieval (PIR) under arbitrary privacy requirements, in a graph-based storage system. This formulation is motivated by the server storage limitations, abundance of data (messages) and heterogeneous data privacy requirements. Under the arbitrary privacy requirement, each message has to be retrieved privately from a pre-specified subset of servers, where the subset always includes the servers storing it. Thus, each server is associated with a privacy set, which pre-specifies the message indices that should be privately retrieved from it. This setting is a generalization of the classical PIR setting, where the required message index needs to be kept private from all servers, i.e., there, the privacy set of each server comprises all message indices. Our setting is also a bridge between the newly formulated local PIR (LPIR) setting and the classical PIR setting, where in the former, the privacy set is exactly the set of stored message indices. In this paper, we derive general lower and upper bounds on the PIR capacity for general graphs, under certain privacy requirements, that capture the essence of both LPIR and classical PIR. Then, we focus on path and cyclic storage graphs under these and more fine-grained settings, for which we derive capacity results for certain cases, and establish lower and upper bounds for others. Their low degree allows for a more in-depth understanding of the new privacy formulation and admits more privacy requirement settings compared to other simple graphs. Finally, we introduce a new graph structure, the pyramid storage graph, to model server storage. Although this graph has never been investigated in the literature in any PIR context, it enjoys a nice symmetric structure for message storage and replication patterns.

Abstract: Next-generation connectivity depends on data traversing multiple physical media within a single end-to-end path, yet research in optical fibre, free-space optical and radio wireless, non-terrestrial networks, and underwater communications has advanced largely in isolation. This fragmentation has a wider adverse impact on communication performance, deployment and adaption as the most demanding open problems in next-generation connectivity, cross-medium channel characterisation, transport-layer protocol design across heterogeneous latency regimes, and cross-domain orchestration, sit at the boundaries between domains and can only be addressed by bringing these challenges together in cross-domain systems. Space-air-ground integrated network research has begun to treat three domains analytically, and its recent extension to the sea surface represents the most ambitious multi-domain framework proposed to date, yet neither has produced experimental results, a deployed system, or a standards engagement. The subsurface and maritime domain remains absent from both. This paper proposes the connected heterogeneous all-medium integrated network (CHAIN), a framework that treats the undersea, maritime, terrestrial, aerial and space domains as a single design space. We identify an all-photonic network backbone as the unifying physical infrastructure, Artificial intelligence (AI)-driven orchestration as the cross-domain control layer, and the joints between domains as a unification challenge. We survey the state of the art across all domains and the existing cross-domain literature, develop the CHAIN framework and its technical pillars, characterise the five core open problems the field must resolve, and set out a research roadmap from near-term measurement campaigns and testbed validation through cross-medium field trials to global-scale deployment.

Abstract: We construct an explicit infinite family of simple two-dimensional Cayley complexes over $\mathbb{F}_2^n$ whose degree is polynomial in $n$ and whose nontrivial vertex-link eigenvalues lie in $[-λ,λ]$ for every fixed $λ>0$. For every fixed $d\ge2$, we also obtain an explicit infinite family of weighted $d$-dimensional Cayley complexes over $\mathbb{F}_2^n$ with codimension-two local spectral norm at most $1/d$ and Cayley degree $Θ_d(n)$. Our two-dimensional construction uses evaluation at rational points of algebraic curves to produce projective direction sets and many functions affine along these directions, which may be useful for further constructions and improvements.