CS Paper Radar

On the Power of Alternating Local Certification with Constant-Size Certificates

Pedro Montealegre, Martín Ríos-Wilson, Jukka Suomela, Guillaume Theyssier

cs.DC ·submitted 2026-10-16 16:21 UTC · v1

Abstract

We study alternation hierarchies for distributed decision in anonymous networks with constant-size certificates. A prover and a disprover alternately assign certificates to nodes over a constant number of rounds, after which each node decides whether to accept based on its own input and the certificates observed in its neighborhood. An instance is accepted if all nodes accept. Unlike previous work on distributed alternation hierarchies, which considered restricted local computation (Reiter, PODC 2024) or logarithmic-size certificates (Feuilloley et al., ICALP 2016), we focus on constant-size certificates and the role of neighborhood information in determining expressive power. We consider three models: SET, where nodes observe only the set of certificate sequences of their neighbors; MULTISET, where multiplicities are also visible; and PORTS, where neighbors can additionally be distinguished by local port numbers. We establish that SET is strictly weaker than MULTISET, which is in turn strictly weaker than PORTS, and that all three alternation hierarchies are strict at every level. Despite their severe restrictions, these models are remarkably expressive: LEADER belongs to the third level of SET. Our main characterization shows that, over finite input alphabets, SET coincides exactly with monadic second-order logic (MSO$_1$). Moreover, every language definable in counting monadic second-order logic (CMSO$_1$) belongs to PORTS, while MULTISET already contains languages that are not CMSO$_1$-definable. Nevertheless, this expressive power has fundamental limitations. PORTS does not capture MSO$_2$: neither Hamiltonicity nor the existence of a perfect matching belongs to PORTS. Furthermore, over unbounded input alphabets, PORTS cannot verify that every node has been given the correct network size.

Closest papers

Nearest neighbours by meaning across the whole index.

Tight Bounds for Anonymous Parity Certification

cs.DC ·2026-10-28 ·Pedro Montealegre, Jorge Valenzuela
theory similarity 0.74
Abstract · 23 pages, 5 figures

Local certification is the task of verifying graph properties using certificates assigned to vertices and checked using only local information. A central question is which properties admit constant-size certificates, independently of network size. A fundamental test case is the parity of the network order. Bousquet, Feuilloley, Valenzuela, and Zeitoun (DISC 2026) showed that the complexity of certifying even order depends dramatically on the verification model. On arbitrary graphs, three bits per vertex suffice with unique identifiers and verification radius two. In the anonymous radius-one model, they established an $Ω(\log\log^* n)$ lower bound and an $O(\log n)$ upper bound. They also showed that constant-size certificates suffice in this model on bounded-expansion classes. In this paper, we settle the complexity of anonymous parity certification on general graphs and further investigate the role of graph sparsity. Our main contributions are: * We close the gap left by Bousquet et al., proving that the local complexity of certifying even order in the anonymous radius-one model is $Θ(\log\log n)$ bits. * We show that on graphs of degeneracy at most $d$, parity can be certified with $O(\log d)$ bits, while $Ω(\log\log d)$ bits are necessary. In particular, every class of bounded degeneracy admits constant-size certificates, strictly generalizing the result for bounded-expansion classes. * We show that constant-size certification cannot be guaranteed on nowhere-dense classes, a broader notion of sparsity that includes bounded expansion. We construct a fixed, subgraph-closed nowhere-dense class on which parity certification requires $Θ(\log\log n)$ bits. Together, our results provide a more complete picture of anonymous parity certification on sparse graph classes, showing that its complexity depends on the particular structural notion of sparsity.

0.13

Reducing Provers in Distributed Quantum Verification

cs.DC quant-ph ·2026-11-09 ·Alex Della Schiava, Atsuya Hasegawa, François Le Gall, Harumichi Nishimura
similarity 0.64
Abstract · 22 pages (including references), 4 figures. Submitted to SIROCCO 2027

In the distributed quantum Merlin-Arthur ($\mathsf{dQMA}$) model introduced by Fraigniaud, Le Gall, Nishimura, and Paz (ITCS 2021), a network of quantum computers verifies a global property with the aid of a quantum proof supplied by an untrusted prover. While the nodes are computationally unbounded, the challenge is to limit proof size and the communication required for verification. In this paper, we consider the model of Hasegawa, Kundu, and Nishimura (PODC 2024), where the proof must be unentangled across nodes, and define its extension to $k$ unentangled provers, denoted by $\mathsf{dQMAS}(k)$. In this setting, we investigate the proof size per node and the communication costs of reducing the number of provers. Our first result reduces the number of provers from $k$ to two, doubling the proof size without additional communication. Moreover, with four additional rounds, we can reduce the number of provers from $k$ to one, using at most three times the original local proof size plus a logarithmic term in the number of nodes. Finally, we establish amplification for perfectly complete protocols. In this regime, a single prover suffices with a constant-factor overhead in our reductions, yielding $\mathsf{dQMAS} = \mathsf{dQMAS}(k)$.

0.21

Quantum Advantage in Local Certification of Graph Properties

cs.DC ·2026-11-05 ·Benjamín Jáuregui, Masayuki Miyamoto
theoryhot direction similarity 0.64
Abstract · Shortened abstract for arXiv

Local certification allows network vertices to verify global properties using certificates from an untrusted prover and communication with their neighbors. Its complexity is the maximum certificate size at any vertex. Fraigniaud et al. (ITCS 2021) introduced the distributed quantum Merlin-Arthur (dQMA) model and proved an exponential quantum advantage for distributed equality, measured in input-string length. We resolve a question of Hasegawa, Kundu, and Nishimura (PODC 2024) by establishing unconditional exponential and polynomial quantum advantages for graph properties, which depend only on network topology, with complexity measured in the number $n$ of vertices. For every fixed integer $μ\ge 1$, we construct a graph property admitting a one-round dQMA protocol with $O(μ\log n)$-qubit certificates and messages, whereas every $μ$-round distributed Merlin-Arthur (dMA) protocol requires $Ω(n/(μ\log^2 n))$-bit certificates. We also give a one-round dQMA protocol for graph symmetry, the existence of a nontrivial automorphism, with $\widetilde{O}(n^{5/3})$-qubit certificates. This yields a polynomial advantage over one-round dMA protocols, for which an $Ω(n^2)$-bit certificate lower bound is known.

0.29

Linear Certificates for Membership Comparability, Quadratic Barriers for Selectors

cs.CC ·2026-09-25 ·Sebastian Ben Daniel
similarity 0.63
Abstract

Selectors and comparators supply only partial information about membership: a selector names a member of any pair that meets the language, while a binary membership comparator merely excludes one of the four membership vectors of a pair. We ask how much nonuniform advice turns such information into exact recognition. Our main result extends the optimal nondeterministic advice bound for P-selective sets to every binary membership-comparable language: $2-mc \subseteq NP /(3n+5)\cap\mathrm{coNP}/(3n+5)$, with common fixed advice and certificates of at most $5n+12$ bits. The class is strictly larger; some 2-mc sets are not truth-table reducible to any P-selective set. The proof replaces the tournament king by an independent two-step cover of true signed literals, together with a short-forcing-or-exact-majority dichotomy, and it relativizes. Via an advice-preserving isolation transfer, a deterministic polynomial-time algorithm for promise Unique-Circuit-SAT gives $2-mc \subseteq P/O(n)$. For selectors we determine tight orders of ordinary advice: $Θ(n)$ for errorless average-case computation and $Θ(n^2)$ for worst-case bounded-error computation, the latter independent of the interpreter's coin bound. One oracle realizes both orders on a single language and separates ordinary from coin-dependent advice. The quadratic and linear lower bounds hold for tournament-query procedures and relativized languages, not unconditionally for unrelativized P-selective sets.

0.38

Witness-Certified Fair Division with Comparison Queries

cs.GT cs.DS ·2026-08-17 ·Tatsuhito Yamagata, Hanna Sumita
theory similarity 0.61
Abstract

We study fair division of indivisible goods when agents' valuations are accessed only through ordinal comparisons between bundles, with arbitrary tie-breaking. In this model, even deciding whether a given allocation is envy-free up to one good (EF1) can be impossible. This suggests explicit fairness certificates as a natural algorithmic object. Our main contribution is a certificate-preserving scaling framework, which recursively contracts goods, solves a smaller instance, and expands the solution while repairing an explicit envy-eliminating witness certificate. For arbitrary identical monotone valuations, this yields a certified EF1 allocation for $n$ agents and $m$ goods using $O(n \log n \log(m/n))$ comparison queries, within an $O(\log n)$ factor of the $Ω(n \log (m/n))$ communication lower bound. For identical additive valuations, we additionally obtain a $1/2$-MMS guarantee within the same query complexity. For non-identical additive valuations, exploiting our EF1+$1/2$-MMS algorithm, we accelerate the existing matching-based PROP1+$1/2$-MMS framework, improving the query complexity from $O(n^4\log m)$ to $O(n^3\log m)$. Finally, we study the structure of such certificates through $k$-witness EF1, a hierarchy between EF1 and EFX.

0.21

Certifying Hidden Paths: Scalable Topology Assurance for QKD Networks

cs.CR quant-ph ·2026-10-08 ·Alessandro Colombo, Margherita Cozzolino, Stephan Krenn, Thomas Lorünser
similarity 0.60
Abstract

Large-scale Quantum Key Distribution (QKD) networks rely on trusted repeaters, making the security properties of the selected communication path an essential part of end-to-end assurance. At the same time, network operators may be unwilling to disclose their internal topology. We present a topology-certification mechanism that lets a provider prove in zero knowledge that policy-compliant routes between two endpoints exist, without disclosing the routes in an individual presentation. Our main idea is to certify nodes and edges independently using multi-message signatures, rather than signing the complete graph as one object. For a route chosen in advance, proof size and cryptographic proving and verification work depend on its positions and attributes, independently of the overall network size, whereas route discovery and certification have separate graph-dependent costs. The construction hides the actual route length up to a public bound and sketches extensions to node-disjoint routes and monotonic additions within a graph epoch. We give a formal security model and conditional proofs of unforgeability and graph hiding for a generic construction. For a BBS-based construction, presentation-size estimates remain below $300$\,KiB at $\ell=m=n=50$, and measured generation and verification times remain below $400$\,ms at $\ell=64$ and $m=n=8$.

0.17

Differential Trust: Dynamic Multi-Authority Anonymous Credentials with Epoch-Weighted Updates

cs.CR ·2026-09-16 ·Chen Li, Jianting Ning, Xiulong Liu, Yulin Liu
top venue similarity 0.58
Abstract · 34 pages. Full version of the paper published at the 35th USENIX Security Symposium (USENIX Security '26)

Anonymous credentials (ACs) are fundamental to privacy-preserving authentication, allowing users to prove possession of attributes without revealing their identities. State-of-the-art ACs distribute credential issuance across multiple authorities, typically employing techniques such as Shamir's secret sharing or aggregate signatures. While this approach enhances system robustness and eliminates a single point of failure, it treats all authorities equally in the credential issuance phase. This uniform treatment disregards the varying levels of trustworthiness or stake held by different authorities. Such a limitation has become particularly problematic in modern decentralized systems like Proof-of-Stake networks, where the inherent trust differentiation among nodes cannot be leveraged in the credential issuance process. To address this limitation, we propose the notion of Multi-Authority Anonymous Credentials with Epoch-Based Weights (MA-ACEW), the first Multi-Authority Anonymous Credential (MA-AC) model that considers authorities' weight distribution in credential issuance. Crucially, MA-ACEW enables efficient credential updates when authority weight distributions change across epochs. The core of MA-ACEW is our novel Epoch-Bound Pointcheval-Sanders Signature (EB-PS) primitive, which binds signatures to specific time epochs. This temporal binding enables both weight-based credential issuance within epochs and efficient non-interactive credential updates across epochs. We formalize the EUF-eCMA unforgeability requirement for EB-PS and prove our construction satisfies it under a novel STB-GPS assumption. We then prove that our MA-ACEW construction achieves unforgeability, anonymity, and blindness. Finally, we present benchmarks demonstrating the efficiency of EB-PS and MA-ACEW. Remarkably, presenting a credential aggregated from 128 partial ones takes only 10.68 ms on average.

0.56

Subgraph Counting with Local Node Differential Privacy

cs.DS cs.CR ·2026-10-15 ·Sofya Raskhodnikova, Adam Smith, Connor Wagaman, Anatoly Zavyalov
top venuetheory similarity 0.58
Abstract · To appear at the ACM-SIAM Symposium on Discrete Algorithms (SODA) 2027

We study the problem of approximately counting subgraphs under local node differential privacy (LNDP), a recently introduced model that enforces strong privacy guarantees in analyses of distributed social networks. We design a noninteractive $(\varepsilon,0)$-LNDP algorithm that, given any public $k$-node template graph $H$, counts occurrences of $H$ in a sensitive undirected $n$-node graph with additive error $O(n^{k-\frac{1}{2}}/\varepsilon^{k-1})$, for any constant $k$. We complement this algorithm with a lower bound showing that every noninteractive $(\varepsilon,δ)$-LNDP algorithm for counting copies of any $k$-node template graph with maximum degree greater than $1$ must have error $Ω(n^{k - \frac{1}{2}})$. Thus, our algorithm achieves optimal error for counting constant-size subgraphs, up to $\mathrm{poly}(1/\varepsilon)$ factors. Our results substantially expand the types of network statistics known to be approximable under LNDP: prior work considered only functions of the degree distribution. In addition, our lower bound yields the first known $\mathrm{poly}(n)$ gap between central and local node differential privacy when accuracy is required for all input graphs. Previous separations either only involved $\mathrm{poly}(1/\varepsilon)$ factors or only applied to promise problems.

0.32