distributed system designers

Abstract: The inefficiency of decentralized resource allocation is classically measured by the Price of Anarchy (PoA) and the Price of Stability (PoS). The most widely studied and foundational class of these models are atomic and non-atomic congestion games, for which a robust theory quantifying the inefficiency of equilibria is well-established. To mitigate the effects of selfish behavior, we employ Coordination Mechanisms, which modify resource costs to incentivize socially improved equilibria. However, standard Coordination Mechanisms assume unknown, adversarial demand, restricting positive results mainly to specialized networks such as parallel links. We address this limitation by studying learning-augmented coordination mechanisms, where the mechanism is endowed with a potentially inaccurate prediction of the demand. We study general atomic and non-atomic congestion games with polynomial latency functions of degree $d$. Our main positive result is a learning-augmented coordination mechanism tuned by a confidence parameter $β$ which achieves a "best of both worlds" type of result: approximately optimal performance for an accurate prediction without sacrificing the worst-case guarantee of a good equilibrium (PoS). We further establish bounds on PoA-Robustness (worst equilibrium performance under cost modification). Our construction relies on transforming approximate equilibria of the original game into exact equilibria of the modified game using an approximate potential function. We complement our positive results with impossibility results. We first show that requiring all equilibria to have optimal social cost under an accurate prediction precludes bounded robustness. We also show a strong error tolerance limit in non-atomic games: even infinitesimal prediction errors can cause the performance of a mechanism with optimal consistency to revert to the original PoA.

Abstract: We present the directed simplicial complex: this is an extension of a simplicial complex with a direction on its faces. This enables us to model a local notion of belief in a three-valued semantics, in which formulas may be true, false, or undefined. Of particular interest is a class of directed simplicial complexes called cups, in which any maximal set of vertices of different colors is a facet. Cups permit a more concise relational representation. We give examples and applications of our logical semantics. We then provide a sound and complete axiomatization for the class of directed simplicial complexes and extend it to an axiomatization for the class of cups. We include a detailed technical comparison with other works on belief on complexes. Our work generalizes a prior axiomatization for knowledge on (undirected) impure simplicial complexes.

Abstract: Alice and Bob hold complementary halves of the columns of an $n\times n$ matrix of $k$-bit integers and decide whether it is singular over $\mathbb Q$. Up to constant-factor dimension growth, this partitioned problem is equivalent to additive singularity, where Alice and Bob hold $n\times n$ matrices $A,B$ of $k$-bit integers and test the singularity of $A+B$ over $\mathbb Q$. We prove a bounded-error quantum lower bound $Ω(\min\{n^{3/2}\sqrt{k\log n},n^2\log(nk)\})$ and a randomized upper bound $O(n^2\min\{k,\log(k+\log n)\})$. The bounds match at $Θ(n^2\log(nk))$ for $k\ge n\log n$. The lower bound holds even under the promise of rank $n-1$ versus $n$. Its proof combines an integer witness with a local digit encoding, while the upper-bound protocol lifts modular kernel relations using short messages. Bitwise sharing changes how the communication complexity depends on the entry bit length $k$. If Alice and Bob instead hold $n\times n$ matrices $A,B$ of $k$-bit integers and test whether their entrywise bitwise XOR $A\oplus B$ is singular over $\mathbb Q$, we prove a quantum lower bound $Ω(n^2k)$, matching the trivial upper bound. This lower bound holds even under the promise of rank $n-1$ versus $n$. Our proof uses a dense weighted equation and a signed Fourier witness whose exceptional dyadic frequencies can be removed at small variation cost.

Abstract: Multi-agent systems can differ under identical agents and communication budgets when they support different forms of joint interaction. We introduce Topological Sheaves of Irreducibility (TSI), a sheaf-theoretic framework separating task-level compatibility obstructions from system capability. A task is represented by an interaction complex $K$ and a capacity sheaf $\mathcal{F}$; nonzero $H^n(K;\mathcal{F})$ defines a structural signature, while registered interventions test capability. For cocycle data, cochain realization is solvable exactly when the represented cohomology class vanishes. Examples show that the signature is sheaf-relative, and the degree-1 reduction yields cycle-space witnesses and observation requirements. We evaluate two finite one-round models. Across 15,625 degree-1 inputs, an all-agent additive primitive solves decision and repair exactly; the optimal pairwise system reaches 88.80% on decision, one input above the 88.79% majority-class baseline, and 26.63% on repair. On a degree-2 tetrahedral-boundary task over 531,441 inputs, the same-2-skeleton system retains all four three-agent primitives yet matches the pairwise-only optimum throughout the registered separation window, whereas adding the class-filling four-agent primitive makes both tasks exact. Status-preserving robustness checks retain exact performance but are not cost-matched to the class-restoring ablation. Conditional on the registered primitives and cost models, TSI provides task-relative, falsifiable tests of higher-order interaction.

Abstract: On ranked directed acyclic graphs coupled by vertex conflicts we study exact-arrival multi-agent path finding (departure and arrival pinned in place and time) posed as a distributed output task: every cell must emit its own bit of a valid joint path-support mask. The machines are cellular: one automaton per cell, state factored over cells, communication only along a fixed local fabric, synchronous rounds, a query-independent output round, no central decoder, and a per-topology transition code. "Necessary" here means: on an explicit hard topology, over all its feasible queries, no universally correct local-only architecture can renounce either temporal orientation; with global flags, impossibility becomes a bandwidth-round trade-off. The class is not vacuous: a flooding machine solves every instance in as many rounds as the diameter of the local fabric. The bound survives two concessions: we supply every agent's exact individual cavity, which alone solves the single-agent problem in zero rounds and makes the single-agent direction theorem vacuous; and we allow $k$ one-bit global aggregate flags. On a twelve-cell, two-agent, depth-three topology no forward-only machine with $k=0$ is correct on two feasible queries, for any number of rounds; the time-reversed topology does the same to backward-only machines. Placing $p$ copies side by side gives, for forward-only machines, $J_R+kR\ge p$ at constant depth, where $J_R$ measures how much of the query reaches the targets' cones and is $0$ here. A backward-only machine solves that family in constant rounds and a flag-streaming one in $\lceil p/k\rceil+O(1)$, so the bound is tight in order; on the composite family neither orientation can be renounced. The finite lemmas of the gadget and the pair-invariance contradictions are checked in Lean 4; the semantic bridge, the cone lemma and the counting are paper proofs. We report no benchmarks.

Abstract: We consider the metric distortion framework for voting, where $n$ voters and $m$ candidates are embedded in an unknown metric space. A voting rule selects a candidate using only voters' ordinal preferences, and its distortion is the worst-case ratio between the social cost of the selected candidate and the minimum social cost. We study how round complexity trades off against total communication in deterministic voting protocols with low distortion. Deterministic rules can achieve the optimal distortion of $3$ in one round by eliciting complete rankings using $Θ(nm\log m)$ bits, while a direct sequential implementation of PluralityVeto achieves the same distortion using only $O(n\log m)$ bits but requires $Θ(n)$ rounds. Our main result is TreePluralityVeto, a deterministic voting protocol that, for every $r\ge 2$, achieves distortion at most $2r-1$ using at most $r$ rounds and $O(n\log m+n s^{1/(r-1)}\log s)$ bits of total communication, where $s = \min\{n, m\}$. The protocol runs PluralityVeto on a hierarchical partition of the voters, collecting restricted rankings in parallel at each level. The branching factor controls the tradeoff between rounds and communication, and a matching-based analysis shows that each level increases the distortion bound by at most $2$.

Abstract: Recent work of Sawettamalya and Yu (FOCS 2026) initiated the study of \emph{gap-majority} composition in randomized communication. They showed that if computing a $\{\pm 1\}$-valued function $f$ in $r$ rounds requires $I$ bits of information, then distinguishing $\sum_{i=1}^n f(X_i,Y_i)\geq 0.01\sqrt{n}$ from $\sum_{i=1}^n f(X_i,Y_i)\leq -0.01\sqrt{n}$ in $r$ rounds requires $n \cdot (I-O(\log n))$ bits of information. They also conjectured that the $O(\log n)$-additive ``loss'' can be further reduced to $O(1)$. In this note, we record that a minor adaptation to their approach combining with a finer analysis achieves the conjectured $O(1)$ loss, establishing a gap-majority lemma for bounded-round communication that is optimal up to constant factors.

Abstract: This paper studies the complexity of model checking strategic abilities in multiagent systems under imperfect information, in particular systems represented succinctly. Such a representation can describe systems that are exponentially larger than their input and is particularly relevant to practical implementations of model checkers such as MCMAS. The logics we consider include epistemic strategy logic supporting partial binding $SLK_{P}$, and its syntactic fragments: epistemic strategy logic $SLK$ and variants of Alternating Time Temporal logics. We show that succinct model checking for $SLK_P$ and $SLK$ is $AEXP(poly)$-complete, while objective ATL and ATL$^{*}$ are $P^{NEXP}$-complete. The latter corrects a previous NEXP-completeness result for model checking succinct imperfect-information systems. Under subjective semantics, $P^{NEXP}$-completeness already holds for one-step Coalition Logic, and therefore also for ATL and ATL$^{*}$.

Abstract: We provide a $\operatorname{poly}(\log\log n)$-round randomized LOCAL algorithm for the constructive Lovász Local Lemma with polynomial criterion $pd^{c} < 1$, for a sufficiently large constant $c$. The best previous general round complexity was $\widetilde O(\log n)$. The key ingredient is a local reduction that amplifies the LLL probability exponent quadratically, while increasing the dependency radius only by a constant factor.

Abstract: We study the two-player communication complexity of the \textsf{Coin} problem. Here, two players, denoted Alice and Bob, are given up to $n$ individual i.i.d. random coins, and asked to output whether there are more heads or tails. An immediate approach is for Alice to send Bob her exact numbers of heads and tails, yielding a deterministic protocol with one-way communication cost $O(\log n)$ bits. Indeed, this is provably optimal in the related multi-player and streaming settings [Braverman, Garg, Woodruff, FOCS'20]. Our contribution is to show that this is not the right answer in the one-way two-player setting. Instead, we prove a $Ω(\log\log n)$ bit lower bound for the constant error-rate regime, and a $Ω(\log(1/δ))$ bit lower bound for arbitrarily small error rates, $δ\geq n^{-0.1}$. We also complement these with a tight one-way protocol using $O(\log\log n + \log(1/δ))$ bits of communication. Unlike the previous works, our lower bounds avoid intricate direct information-theoretic arguments. Instead, our $Ω(\log(1/δ))$ bound is via a standard fooling-set style argument, whilst our $Ω(\log\log n)$ bound is via a novel yet simple reduction from the \textsf{Gap-Greater-Than} problem. This reduction is our main technical contribution, and can be seen as loosely inspired by the \emph{Robust Communication Complexity} arguments of [Chakrabarti, Cormode, McGregor, STOC'08]. Finally, we also show that our constant-error lower bound and protocol can be adapted to the multi-round setting: up to polynomial factors in $r$, the $r$-round communication complexity of the coin problem is $Θ\left((\log\log n)^{1/r}\right)$ bits.

Abstract: In this work, we prove that computing the edge ranking of a tree in parallel is P-Complete. An optimal tree edge ranking assigns positive integer ranks to the edges such that any two edges with the same rank are separated by an edge of higher rank, while minimizing the highest rank. Tree edge ranking abstracts several classical problems such as parallel assembly in manufacturing, minimum-height dendrograms, reversible pebble game and edge-query binary search on trees. Its parallel complexity remained open for over thirty years, since the seminal work of de la Torre, Greenlaw, and Sch{ä}ffer [SODA'93], and was listed as an open problem in the book Limits to Parallel Computation by Greenlaw, Hoover, and Ruzzo [1995]. We prove that deciding whether a tree has edge ranking at most $K$ is P-Complete, already for trees of diameter six. Our reduction is from NOR-CVP and simulates a greedy procedure underlying known sequential approaches. Despite ruling out NC algorithms, we prove that this hardness barrier can be bypassed in the well-known model of Massively Parallel Computation (MPC) with strongly sublinear local memory, showing that $O(\log n)$ MPC rounds suffice to solve the hard tree-edge ranking instances used to prove P-Completeness. Specifically, we present a deterministic MPC algorithm that computes an optimal edge ranking of an $n$-vertex tree of diameter $D$ in $O(\log D+\log\log n)$ rounds with $O(n^{3/4}D^{1/4})$ local memory. Our algorithm circumvents the linear-memory barrier by compressing the information required to produce a lexicographically minimal ranking from subtree merges. Overall, this result reinforces the strict separation between NC and what can be computed efficiently in MPC.

Abstract: This work studies the multidimensional asymptotic agreement problem in dynamic networks. We assume that nodes have $d$-dimensional inputs and need to converge arbitrarily close to each other's inputs while their vectors stay inside the convex hull of all inputs. We present a new upper bound of $\sqrt{2d/(3d+1)}$ on the contraction rate of asymptotic agreement in the non-split network model, where $d$ is the dimension of the input and $\sqrt{2d/(3d+1)}\rightarrow \sqrt{2/3}\approx 0.816$ for $d\rightarrow\infty$. To this end, we adapt the BallMidpoint algorithm (Melnyk, 2026) recently introduced for the all-to-all communication model. This algorithm lets the nodes choose the midpoint of the smallest enclosing ball of the received vectors. This bound is strictly worse than the $\sqrt{1/2}\approx 0.707$ contraction rate for fault-tolerant approximate agreement in all-to-all communication networks because the convex hulls of the nodes do not have a common intersection, and only intersect pairwise. Our bound improves over the previously best-known contraction rate of $\sqrt{7/8}\approx 0.935$ for dynamic networks via the MidExtremes algorithm (Függer and Nowak, 2018). We present the first multi-dimensional lower bound of $2/3$ for the contraction of coordinate-free memoryless anonymous deterministic algorithms in non-split networks, for $d\ge 8$. This result shows that the previously best-known lower bound of $1/2$ on the contraction rate for $n\ge 3$ and $d=1$ is not tight in higher dimensions. If $n$ is infinite, we extend this lower bound to $\sqrt{1/2\cdot d/(d+1)}$, which converges to $\sqrt{1/2}$ for $d\rightarrow \infty$. We further show that for a single round, the one-round contraction is at least $\sqrt{\frac{2d-2}{3d+7}}$, which converges to $\sqrt{2/3}$ for $d\rightarrow\infty$, showing that the BallMidpoint strategy is asymptotically optimal for one round.

Abstract: For four finite discrete random variables, we prove that the negative of the Ingleton expression, divided by the joint entropy, is at most $19/124 \approx 0.15323$, improving the previously reported upper bound $3/19$ by $11/2356$. The proof uses a copy program with four copy steps and six auxiliary variables, certified by exact rational linear-programming certificates. We also show that two published information inequalities, due to Dougherty-Freiling-Zeger and Csirmaz, imply the bound $5/32$ by an explicit nonnegative combination with Shannon inequalities, and that $5/32$ is the exact optimum both of the union of the three published inequality catalogues considered here and of the full copy-lemma extensions of all 213 distinct copy programs occurring in them. The new program is not among these programs, and the bound $19/124$ remains optimal when all of them and all catalogue inequalities are added. Ancillary files provide the parsed catalogues, exact primal and dual certificates, exact extension certificates, and verifiers that use only the Python standard library.

Abstract: Agents competing against a common opponent can often gain an edge by forming alliances, but deciding whether to do so is difficult when they lack precise knowledge about their opponent or ally. We study how uncertainty affects opportunities for alliance formation in the coalitional General Lotto game, in which two players compete aganist a shared adversary by allocating their resource budgets over separate sets of valued contests. When all agents know one another's budgets, it is known that a budget transfer from one player to the other can benefit both players. We ask whether such alliances survive when the players know the relevant budgets only up to a multiplicative factor. Under two models, one in which the players are uncertain about the adversary's budget and one in which they are uncertain about each other's budgets, we characterize exactly which games admit a transfer that benefits both players in every game consistent with what they conjecture to be possible. In both models, we show that such robust transfers exist in a set of games of positive measure for every level of uncertainty. These results suggest that alliances can remain worthwhile even when allies are largely in the dark.

Abstract: We give the first exponential quantum advantage in the general interactive three-party Numbers-on-Forehead (NOF) model for a decision problem. Previous separations hold only for restricted protocols like one-way communication for a relation. We construct an explicit partial Boolean function, the Interleaved Unitary Product problem, that requires only $O(\log n)$ NOF quantum communication but $\widetildeΩ(n^{1/32})$ randomized communication. This function builds on the two-party unitary product problem of Arunachalam, Girish, and Lifshitz (TQC 2024). The main technical obstacle is that discrepancy, the standard lower-bound method for NOF, also lower-bounds quantum communication. We instead develop a regularity-based argument for randomized NOF lower bounds, building on the approach of Kelley, Lovett, and Meka and adapting the regularity decomposition of Abboud, Fischer, Kelley, Lovett, and Meka (STOC 2024) to cylinder intersections. Combined with matrix-product estimates of Arunachalam, Girish, and Lifshitz, this yields our randomized lower bound.

Abstract: We study truthful-in-expectation (TIE) mechanisms for allocating indivisible chores alongside ex-post maximin share (MMS) guarantees. For goods, Bu and Tao (FOCS 2025) established a (1/n)-approximation for TIE mechanisms, and this was substantially improved by Babaioff, Feige, and Manaker Morag (FOCS 2026), who established an Ω(1/\log n) approximation, where n is the number of agents. The corresponding problem for chores has received less attention. The best-known result is due to Aziz, Li, and Wu (MAPR 2024), who gave a TIE mechanism with an O(\sqrt{\log n}) MMS approximation guarantee that holds only in expectation. They also established a 6/5 lower bound for TIE mechanisms for two agents. In this paper, we present the first TIE mechanism for chores that achieves a constant ex-post MMS approximation guarantee. Specifically, our mechanism guarantees an ex-post ratio of 1.97 for any number of agents n, which improves to 4/3 for n=2 and 3/2 for n=3. On the hardness side, we tighten the two-agent lower bound to 4/3, showing that our mechanism is optimal for n=2. More generally, we establish a lower bound of 13/12 on the ex-post MMS approximation ratio achievable by TIE mechanisms for every n\ge 3.

Abstract: We prove a lifting theorem from two-party public-coin one-way communication to multiparty public-coin one-way number-on-forehead (NOF) communication. For every fixed $k\ge2$ and prime $q>2k$, there is a generalized inner product gadget $\GIP_{q,r}^k:(\F_q^r)^k\to\F_q$ with $r=O_k(q/\log q)$ such that, for every partial Boolean function $f:D\to\bits$, where $D\subseteq\F_q\times\F_q$, \[ R_{1/3}^1(f)-O(1) \le R_{1/6}^{1,\NOF}\bigl(f\circ\GIP_{q,r}^k\bigr) \le R_{1/6}^1(f). \] Thus, composition with the gadget preserves one-way randomized communication complexity up to an additive constant and a change in the error parameter. The lower bound holds in the general one-way NOF model, where the last player sees the entire gadget input. This extends the deterministic one-way NOF lifting theorem of Yang and Zhang to randomized protocols, and extends the randomized lifting result of Wang and Wu from the conservative model to the general one-way NOF model. Our proof introduces a one-way cylinder partition bound that lower bounds public-coin one-way NOF communication complexity. We show that, for the lifted function, this bound is at least half the one-way partition bound of the outer function. The main technical step transfers a dual solution between the two bounds, using Möbius inversion and a discrepancy estimate for generalized inner product to control the loss. Combining this transfer with the characterization of two-party one-way randomized communication complexity by the one-way partition bound yields the lifting theorem.

Abstract: Decentralised federated learning removes the aggregation server but makes collaboration dependent on transient peer availability. In mobile and intermittently connected systems, evaluating a promising peer consumes contact time and may cause the exchange opportunity itself to vanish, so that the evidence a learner gathers about a peer is perishable: it decays because links expire and because peer models drift while old measurements age. This paper develops a self-contained theory of optimal stopping for the resulting peer-selection problem. We formalise a receiver's within-contact decision as a finite-horizon Markov optimal-stopping problem with costly information acquisition and a future-arrival outside option, and prove that it admits an optimal policy characterised by a reservation value (Snell-envelope structure). Around this formulation we prove: (i) stage-uniform, drift-aware concentration and a maximin certification rule that is correct with high probability together with a finite-sample identification bound; (ii) a mobility-aware value of-information stopping rule and comparative statics showing that higher link hazard lowers the value of continued probing and enlarges the stopping region; (iii) a closed-form value of waiting under marked-Poisson contact arrivals, together with a search-theoretic reservation value whose comparative statics we characterise; and (iv) a myopic-optimality theorem establishing that, in sufficiently volatile (monotone) mobility regimes, the one-step confidence-safe rule is a sound surrogate for the optimal policy and never stops prematurely. We instantiate the theory as PROSE (Perishable-evidence Reservation-value Optimal Stopping for Exchange), a lightweight, fully local policy, and delineate the static contact and drift-free limits in which classical sequential decision problems are recovered. The development is entirely analytical.

Abstract: In this paper, we construct a total Boolean function with $\widetilde{O}(\log n)$ randomized communication protocol, while any monochromatic rectangle has density at most $O(2^{-\mathrm{poly}(n)})$. As a corollary, it gives the first total function separation for $\mathrm{BPP}\not\subseteq\mathrm{P}^{\mathrm{NP}}$ in the communication world. Inspired by Gavinsky's recent work (arXiv:2608.18784), our construction combines the cheat-sheet framework with fully linear PCPs.

Abstract: We study deterministic strategyproof aggregation in finite-dimensional Euclidean spaces. For every odd number $n\ge3$ of agents and every finite dimension, we prove that the coordinate-wise median minimizes the worst-case approximation ratio for total Euclidean distance among all continuous, anonymous, deterministic strategyproof mechanisms. The same optimality result holds for every even $n\ge4$ when each coordinate uses a fixed choice of the lower or upper middle rank. The proof combines a rigidity theorem with a normalization that does not increase the approximation ratio: any hypothetical mechanism outperforming the median has a normalized representative that is a fixed coordinate-wise order-statistic rule in a single orthonormal frame. A reflection argument then shows that no such rule improves on the median.

Abstract: Symmetric rendezvous on the line is a search problem in which two agents, initially placed at distance $2d$, must follow the same randomized strategy to meet as quickly as possible. In the standard model, agents may condition their actions on the entire execution history, and both the known- and unknown-distance variants admit expected rendezvous time $Θ(d)$. We study the role of memory by introducing oblivious self-distance strategies, in which an agent's decision depends only on her position relative to her own starting location. For an initial separation of $2d$, let $R_d$ denote the optimal oblivious expected rendezvous time in the known-distance setting. We develop two finite-state frameworks based on absorbing Markov chains. Truncated chains give computable upper bounds through finite-support strategies, while weak-peek chains give lower bounds through a revealed-information relaxation. Together, they provide a mechanism for certifying optimality. Using that mechanism, we determine $R_1$ exactly and prove that it is attained by a finite-support strategy. For $d=2,\ldots,6$, numerical optimization gives the same truncation structure and objective values, yielding rigorous upper bounds below $7.83d^2$. We do not prove that the computed weak-peek minimizers are global, but the stability of the computations leads us to conjecture that they are, in which case the corresponding truncated strategies are optimal. We also prove that $R_d=Θ(d^2)$. In the unknown-distance setting, we construct a universal strategy, independent of $d$, with expected rendezvous time $O(d^{2+η})$ for every fixed $η>0$. Thus, under the memory restriction, the known-distance rendezvous time becomes quadratic, while near-quadratic performance remains possible even without knowing $d$. The asymptotic analysis uses birth-death Markov chains and their electrical-network interpretation.

Abstract: The Simultaneous Message Passing (SMP) model provides a fundamental framework for comparing classical and quantum communication. For two players, Gavinsky et al. (STOC 2006) established a separation underlying the incomparability of shared randomness and quantum communication: \textsc{Index Coordination} needs $O(\log n)$ public-coin bits but $Ω(n^{1/3})$ bounded-error qubits. In this work, we establish a multiparty exponential separation through $\operatorname{IC}_{k,n}$, a natural $k$-party generalization of \textsc{Index Coordination}. Public-coin protocols solve it unambiguously with maximum message length $O(\log n)$ bits. In contrast, quantum SMP protocols without shared entanglement or public coins require maximum message length $Ω(n^{1-1/k})$ qubits in the unambiguous regime and $Ω(n^{(k-1)/(k+1)})$ qubits in the bounded-error regime. A classical private-coin protocol matches the unambiguous bound, so quantum communication provides no asymptotic advantage over private randomness in this regime. For fixed error parameters, all constants are independent of $k$, establishing the exponential separation for every integer-valued function $k=k(n)\ge2$, without restricting its growth. Both quantum lower bounds become $Ω(n)$ when $k\ge c\log n$ for any fixed $c>0$, matching the full-input protocol and yielding tight linear complexity in both regimes. Our results demonstrate that quantum superposition cannot efficiently simulate the coordination afforded by public randomness, extending this separation to arbitrary $k$. To bound success probabilities for multiparty product states, we prove an exact factorization theorem for unambiguous quantum state identification, which may be of independent mathematical interest.

Abstract: We propose a variable and behavior-based node-specific proof-of-work (PoW) model for a directed acyclic graph (DAG)-based distributed ledger technology (DLT) network to mitigate decentralized network congestion control. Network congestion control for centralized communication systems is an established field of study, with detailed and continuous research being done on the subject. However, attention to congestion control in decentralized networks is relatively recent and underexplored, especially with DLT, such as blockchain and DAG-based networks. For the DLT networks, the network congestion is caused by factors such as transaction spamming, an increase in the user base, and the launch of new tokens. We focus on the congestion caused by the spamming of transactions within the blockchain and DAG-based DLT network. Based on the network throughput of transactions per second and consensus procedure, the DAG-based DLT needs to control network spamming more than the blockchain network. The PoW model within the DLT consensus framework is a limited deterrent against spamming. Our model provides equal opportunities for all stakeholders regardless of their computational resources. It prevents and penalizes any node that attempts to spam or dominate the network with more than the prescribed number of transactions. Since the system nodes compete to issue transactions with finite network resources, we display the system behavior through a non-cooperative game. Further, we show that our model enforces prescribed behavior amongst the nodes through the proof of the existence of Nash equilibrium in the game.

Abstract: We show that one-way one-round quantum LOCAL algorithms cannot $4$-color directed cycles with high probability, even with unbounded local computation and quantum message length. This is the first lower bound in the high-probability quantum LOCAL setting that goes beyond the non-signaling and bounded-dependence models, exploiting the structure of distributed quantum algorithms. Our proof connects distributed quantum computing with noncommutative extremal combinatorics by identifying local collision probabilities with the weighted multiplicative energy of matrix-space decompositions. We obtain our lower bound by proving a dimension-independent weighted stability theorem for a directed noncommutative analogue of Mantel's theorem.