Pith. sign in

REVIEW 2 major objections 4 minor 23 references

Trade-offs in Distributed Interactive Proofs

T0 review · 2 major / 4 minor · reviewed 2026-08-14 · deepseek-v4-flash

Challenge this review Re-run · record.json Download PDF Read on arXiv ↗ Review JSON

Pith's one-line read This paper establishes the first continuous trade-off between certificate size and communication in distributed interactive proofs, and uses it—together with shared-randomness gains, lower bounds, and interaction-reduction theorems—to map…

desk verdict New trade-off theorems and a hierarchy separation, but Theorem 11's inclusion rests on an unproven perfect-completeness assumption. read the letter →

arxiv 1908.03363 v1 pith:MAWF7THL submitted 2019-08-09 cs.DC cs.CC

Pierluigi Crescenzi , Pierre Fraigniaud , Ami Paz This is my paper · ORCID
classification cs.DCcs.CC
keywords distributedinteractiveproofsverificationArthur-Merlinprotocolsspace-communicationtrade-offsharedrandomnesstriangle-freenessproof-labelingschemesinteractionhierarchy
verification ladder T0 review T1 audit T2 compute T3 formal

The pith

A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.

The reading

This paper maps the power of distributed interactive proofs, in which an untrusted prover sends certificates to the nodes of a network and the nodes verify a global property by exchanging messages with neighbors. Its central claim is that the main cost parameters can be traded against one another in ways not previously known. For triangle-freeness, the paper constructs, for every choice of $\alpha$, a Merlin-Arthur protocol whose certificates use $O((n/\alpha)\log n)$ bits and whose messages use $O(\alpha\log n)$ bits, with only $O(\log n)$ bits of shared randomness; this is the first decision task for which certificate size and communication can be traded continuously. The paper also shows that shared randomness sharply lowers communication for locally checkable optimization problems, proves lower bounds showing that symmetry remains hard even with shared randomness, and gives a general reduction collapsing three- and four-interaction protocols to two interactions at a linear blow-up in certificate size.

What carries the argument

The load-bearing device in the triangle-freeness protocol is a polynomial encoding of each node's neighborhood. Writing the identifier space $\{1,\ldots,n\}$ as $[n/\alpha]\times[\alpha]$, each node represents its neighbor set as $\alpha$ Boolean functions on $[n/\alpha]$, extends each function to a low-degree polynomial over a finite field $\mathbb{F}_q$ of size $\Theta(n\alpha)$, and forms the sum over its incident edges of the products of its own polynomials with those of its neighbors. Merlin supplies each node with the alleged sum polynomial; Arthur then uses the shared randomness to choose one field element $i_0$, broadcasts the $\alpha$ evaluations of its own polynomials to each neighbor, and accepts only if the claimed polynomial evaluates to zero at $i_0$ and matches the recomputed sum. Since two distinct polynomials of degree $d$ agree on a uniformly random field element with probability at most $d/q$, choosing $q\gg n\alpha$ makes the error probability small. The parameter $\alpha$ is the dial: certificates store $O(n/\alpha)$ coefficients while messages carry $O(\alpha)$ evaluations, so increasing $\alpha$ shrinks space and grows communication, and vice versa. The other results rest on distinct mechanisms: the SumZero multiparty protocol and equality tests give the shared-randomness savings, two-party Arthur-Merlin lower bounds for equality give the symmetry lower bounds, and a counting argument over $0/1$-labelled oriented cycles gives the hierarchy separation.

What would settle it

Run the construction from Theorem 11 on a concrete dMAM protocol whose completeness is exactly $2/3$ and whose accepting first-round certificate varies with Arthur's randomness; if the resulting dAM protocol rejects some legal instance with probability at least $2/3$, the claimed inclusion $dMAM(\sigma,\gamma)\subseteq dAM(n\sigma^2,n\sigma\gamma)$ fails as stated.

Watch

Extended reading notes

Core claim

On its own terms, the paper's central discovery is a parameterized trade-off: for the triangle-freeness language, and for every $\alpha = O(n)$, there is a distributed Merlin-Arthur protocol using $O(\log n)$ bits of shared randomness, certificates of size $O((n/\alpha)\log n)$ bits, and messages of size $O(\alpha\log n)$ bits between neighbors. At $\alpha=\sqrt{n}$, both costs become $\widetilde{O}(\sqrt{n})$, while any proof-labeling scheme requires at least $n/e^{O(\sqrt{\log n})}$ certificate bits. The paper further establishes that shared randomness is a real resource: locally checkable optimization problems, including maximum independent set, minimum dominating set, and minimum vertex cover, can be certified with $O(\log n)$-bit certificates and $O(\log\log n)$-bit messages, whereas earlier randomized verification reached the same communication only with larger certificates. Symmetry and non-symmetry, meaning whether the network has a non-trivial automorphism, are shown to require $\Omega(\log\log n)$ certificates and messages even with shared randomness. Finally, the paper proves a general interaction-reduction theorem, $dMAM(\sigma,\gamma)\subseteq dAM(n\sigma^2,n\sigma\gamma)$, and a separation: some language on cycles with an $O(n)$-bit locally checkable proof lies outside the Arthur-Merlin hierarchy with $o(n)$-bit certificates for any constant number of interactions.

Load-bearing premise

The load-bearing premise is that every dMAM protocol can be assumed to accept legal instances with probability 1; the paper's own definition only guarantees probability $2/3$, and no argument is supplied that closes this gap, so the inclusion $dMAM(\sigma,\gamma)\subseteq dAM(n\sigma^2,n\sigma\gamma)$ is proven only under that stronger assumption.

Editorial extensions

If this is right

  • Choosing $\alpha=\sqrt{n}$ in the triangle-freeness protocol yields a Merlin-Arthur protocol with $\widetilde{O}(\sqrt{n})$-bit certificates and $\widetilde{O}(\sqrt{n})$-bit messages, while any proof-labeling scheme for the same property needs at least $n/e^{O(\sqrt{\log n})}$ certificate bits.
  • For any optimization problem whose admissible solutions are locally checkable, the existence of a solution of cost at most $k$ belongs to $dMA(O(\log n),O(\log\log n))$ when nodes share $O(\log n)$ random bits; this covers maximum independent set, minimum dominating set, and minimum vertex cover, including weighted versions.
  • The symmetry and non-symmetry problems require $\Omega(\log\log n)$ bits of certificates and $\Omega(\log\log n)$ bits of messages in every Arthur-Merlin protocol, even with shared randomness, so the centralized inclusion $MA\subseteq AM$ does not transfer to the distributed setting.
  • Every language in $dMAM(\sigma,\gamma)$ belongs to $dAM(n\sigma^2,n\sigma\gamma)$, and every language in $dAMAM(\sigma,\gamma)$ belongs to $dAM(n\sigma^2,n\sigma\gamma)$; as corollaries, symmetry and graph non-isomorphism each gain one-interaction protocols with $O(n\log^2 n)$-bit certificates.
  • There exists a language on $0/1$-labelled cycles with a locally checkable proof using $O(n)$-bit certificates that lies outside the Arthur-Merlin hierarchy with $o(n)$-bit certificates, for any constant number of interactions, even with unbounded messages and shared randomness.

Reading between the lines

Editorial extensions of the paper, not claims the author makes directly.

  • Extension: the same polynomial-intersection recipe used for triangle-freeness should transfer to $K_t$-freeness, $C_t$-freeness, and other fixed-subgraph-freeness properties, yielding an $\alpha$-dial between certificate size and message size whenever the forbidden configuration can be written as a sum of products of neighborhood polynomials.
  • Extension: the shared-randomness results suggest a design principle for low-communication verifiers: nodes use one global random value as a fingerprint seed and exchange only constant-size hashes instead of local identities; a physical broadcast beacon or satellite clock could supply such a seed in practice.
  • Extension: the proof of Theorem 11 assumes the starting protocol has perfect completeness, so the first thing to test is whether every dMAM protocol can be boosted to completeness 1 without changing parameters; if not, the interaction-collapse theorem should be stated for perfect-completeness protocols.
  • Extension: the separation between the Arthur-Merlin hierarchy and linear-size proof-labeling schemes suggests the hierarchy is properly stratified, and a natural next question is whether languages with $o(n)$-bit locally checkable proofs also require $o(n)$ certificates at every interaction count.
Share X Bluesky LinkedIn Reddit HN

Signed reviews

No signed human review yet.

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, and a circularity audit.

Referee Report

2 major / 4 minor

Summary. The paper studies distributed interactive proofs, defined as Arthur-Merlin protocols in which a centralized prover interacts a constant number of times with a distributed verifier, followed by a one-round distributed verification phase. The main contributions are: (i) a Merlin-Arthur protocol for triangle-freeness trading certificate size against message size (Theorem 4), with a matching PLS lower bound (Proposition 5); (ii) protocols using shared randomness for optimization problems and for coloring/lucky-labeling problems (Theorems 6 and 8), a general simulation of shared randomness by distributed randomness (Theorem 9), and lower bounds for symmetry and non-symmetry even with shared randomness (Theorem 10); (iii) a general reduction from dMAM to dAM at the cost of larger certificates and messages (Theorem 11 and Corollary 12); and (iv) a diagonalization showing that the Arthur-Merlin hierarchy with o(n)-bit certificates cannot capture all languages admitting linear-size locally checkable proofs (Theorem 13), together with a universal linear-size LCP for regular graphs (Theorem 14).

Significance. If the results hold, the paper makes several useful contributions to the structure of distributed interactive proofs. Theorem 4 is, to my knowledge, the first continuous space-communication trade-off for a natural distributed decision problem, and its polynomial-evaluation technique is elegant. Theorem 6 gives an exponential communication saving for a broad class of optimization problems, and Theorem 13's diagonalization is a clean and sound argument separating linear-size LCP from the Arthur-Merlin hierarchy. The proof of Theorem 4 is well specified and the reduction in Theorem 9 is simple and correct. However, two load-bearing proofs currently have gaps: Theorem 11 assumes perfect completeness without justification, and Theorem 10's reduction to two-party communication complexity does not account for dependencies across the cut of the constructed graph. Both points need repair before the corresponding claims can be accepted.

major comments (2)
  1. [Section 5.1, Theorem 11] The proof begins by fixing 'a dMAM(σ,γ) 1-sided protocol', but Definition 1 defines dMAM with completeness 2/3 and gives no guarantee of one-sided (perfect-completeness) error. The constructed dAM protocol P' repeats the protocol k = nσ times and accepts only if every repetition accepts. If the original protocol P has completeness 2/3, then on a yes-instance the probability that all k repetitions accept is (2/3)^k, which is far below the required 2/3; the statement 'all nodes will accept with probability one, since P is a 1-sided protocol' is doing essential work. Proposition 2 amplifies success probability to any value below 1, but not to 1, and the paper provides no transformation from bounded-error dMAM to perfect-completeness dMAM. Consequently the claimed inclusion dMAM(σ,γ) ⊆ dAM(nσ², nσγ) is not established for arbitrary dMAM protocols as stated. The theorem may be repairable by changing the acceptance rule to a majority over repetitions and using a spanning-tree counting certificate (along the lines of Proposition 2), with parameters chosen so that both completeness and soundness are at least 2/3; however, as written the proof is incomplete.
  2. [Section 4.3, Theorem 10] The reduction from a dAM protocol for Sym/Sym to a two-party Arthur-Merlin protocol for Eq/Eq does not correctly handle the interaction across the cut of the constructed graph G_{x,y}. In the graph, the only edge between the two subgraphs GA and GB is (a,b). In a one-round verification protocol, node a's decision depends on the message sent by node b over this edge, and that message is determined by b's certificate and by the messages b receives from its neighbors in GB; symmetrically, b depends on a's message. Alice, simulating GA alone, cannot determine whether there exists a certificate assignment to GA that is consistent with some accepting assignment to GB, because the boundary message from b is not locally computable from the data she holds. Similarly, Bob cannot independently verify consistency with GA. Thus the criterion 'Alice accepts if her side can be made accepting and Bob accepts if his side can be made accepting' can produce false positives even when no global certificate assignment makes all nodes of G_{x,y} accept. The proof should specify how the boundary messages are supplied (for example, by including them in the two-party certificate) and should redo the complexity accounting for both the certificate-size lower bound and the message-size lower bound; as written, the claimed lower bounds for Sym and Sym with shared randomness are not established.
minor comments (4)
  1. [Section 5.1, proof of Theorem 11] The text states that with k = nσ the error probability is at most 1/3, but the bound obtained is 2^{nσ}/3^{nσ} = (2/3)^{nσ}, which is larger than 1/3 when nσ is 1 or 2. Since the theorem is asymptotic, this is easily fixed by choosing k = c nσ for a sufficiently large constant c, but the current statement is not pointwise correct.
  2. [References] References [15] and [16] are identical entries for the same paper ('Randomized proof-labeling schemes' by Fraigniaud, Patt-Shamir, and Perry). One duplicate should be removed and the citations renumbered.
  3. [Section 3, Theorem 4] The proof identifies the node IDs with the product space [n/α] × [α], which requires α to divide n and n/α to be an integer. The theorem is stated for every α = O(n); a sentence explaining rounding when α does not divide n would remove a small technical ambiguity.
  4. [Section 5.2, Theorem 13] In the proof, the language is constructed on 0/1-labelled oriented cycles, and the theorem statement says 'regular graphs'; cycles are 2-regular, so this is consistent, but the wording could be made uniform.

Circularity Check

0 steps flagged · score 0.0 of 10

No circularity: all central derivations are self-contained constructions using external black boxes; the Theorem 11 1-sided assumption is a correctness gap, not a circular step.

full rationale

The paper's main results are derived from direct constructions rather than from restating their own inputs. Theorem 4 builds the triangle-freeness dMA protocol from polynomial identity testing over F_q, with Merlin sending coefficients of alleged polynomials and Arthur checking evaluations at a shared random point; the complexity trade-off follows from the degree bound and the field size, with no parameter fitted to the claimed output. Theorem 6 constructs protocols from certified spanning trees and the SumZero multiparty protocol, which are cited external tools. Theorem 10 reduces (non)symmetry lower bounds to two-party Arthur-Merlin lower bounds for equality from Goos, Pitassi, and Watson, so the claimed lower bound is imported from an independent communication-complexity result, not from the paper's own framework. Theorem 11 and Corollary 12 give an interaction-reduction simulation whose counting argument is explicit and does not presuppose the inclusion it proves. The paper's self-citations, such as randomized proof-labeling schemes [16], are used as known primitives for message-complexity improvements and are not load-bearing in a circular sense. The only substantive issue found in the derivation chain is non-circular: the proof of Theorem 11 begins "Let P be a dMAM(σ,γ) 1-sided protocol," while Definition 1 guarantees only completeness 2/3, and the argument that all nodes accept with probability one on a yes-instance relies on that unproven one-sidedness. This is a missing justification or completeness gap in the theorem as stated, but it is not a reduction of the conclusion to its inputs, nor does it make the claimed inclusion equivalent to an assumption by construction. No fitted input is relabeled as a prediction, no uniqueness theorem from the authors is invoked to force a choice, and no known result is merely renamed as a contribution. Hence the circularity score is 0.

Assumptions & free parameters 1 free parameters · 4 assumptions · 0 invented entities

The central claims rest on standard communication complexity black boxes, the one-round verifier restriction, and, in Theorem 11, an unstated perfect-completeness assumption. No invented entities or data-fitted parameters appear; the only free parameter is the trade-off knob α.

free parameters (1)
  • α (trade-off parameter in Theorem 4) = arbitrary in [1, n], e.g. √n
    The theorem is parameterized by α; the protocol's certificate and message complexities depend on it. It is a genuine hand-chosen parameter of the result, not fitted to data.
assumptions (4)
  • domain assumption Verifier algorithms are restricted to a single round of communication between neighbors.
    Stated in Section 2: 'we restrict ourselves to verification algorithms v that perform in a single round.' All trade-offs are within this restriction.
  • domain assumption All distributed languages considered are Turing-decidable.
    Stated in Section 2 and used in the diagonalization argument of Theorem 13 to ensure the constructed language is a valid distributed language.
  • standard math External communication complexity results (disjointness, equality, SumZero, Arthur-Merlin communication lower bounds) hold as stated.
    Used as black boxes in Theorems 4, 6, and 10. The paper cites [1,2,18,26] for these results.
  • ad hoc to paper The dMAM protocol in Theorem 11 can be assumed to be 1-sided (perfect completeness).
    The proof says 'since P is a 1-sided protocol', but Definition 1 only guarantees completeness 2/3. The paper does not prove that every dMAM protocol can be converted to a perfect-completeness one, so this is an unstated load-bearing assumption for the interaction-reduction theorem.

how reviews work

0 comments
Cite this review

Pith. "Pith review of Trade-offs in Distributed Interactive Proofs." pith.science (2026). https://pith.science/paper/MAWF7THL

@misc{pith2026190803363,
  author       = {Pith},
  title        = {Pith review of: Trade-offs in Distributed Interactive Proofs},
  year         = {2026},
  howpublished = {\url{https://pith.science/paper/MAWF7THL}},
  note         = {Machine review of arXiv:1908.03363}
}
read the original abstract

The study of interactive proofs in the context of distributed network computing is a novel topic, recently introduced by Kol, Oshman, and Saxena [PODC 2018]. In the spirit of sequential interactive proofs theory, we study the power of distributed interactive proofs. This is achieved via a series of results establishing trade-offs between various parameters impacting the power of interactive proofs, including the number of interactions, the certificate size, the communication complexity, and the form of randomness used. Our results also connect distributed interactive proofs with the established field of distributed verification. In general, our results contribute to providing structure to the landscape of distributed interactive proofs.

Discussion (0). Continue with ORCID to comment.

Reference graph

Works this paper leans on

23 extracted references · 15 canonical work pages

  1. [6]

    7 Yi-Jun Chang, Seth Pettie, and Hengjie Zhang

    URL: https://doi.org/10.1007/978-3-319-72050-0_5 , doi:10.1007/978-3-319-72050-0\_5 . 7 Yi-Jun Chang, Seth Pettie, and Hengjie Zhang. Distributed t riangle detection via expander de- composition. In Proceedings of the Thirtieth Annual ACM-SIAM Symposium on D iscrete Algo- rithms, SODA , pages 821–840,

    work page doi:10.1007/978-3-319-72050-0_5

  2. [8]

    9 Andrew Drucker, Fabian Kuhn, and Rotem Oshman

    URL: https://doi.org/10.1016/j.ipl.2009.05.011, doi:10.1016/j.ipl.2009.05.011. 9 Andrew Drucker, Fabian Kuhn, and Rotem Oshman. On the power o f the congested clique model. In ACM Symposium on Principles of Distributed Computing, PODC , pages 367–376,

    work page doi:10.1016/j.ipl.2009.05.011 2009

  3. [10]

    12 Laurent Feuilloley, Pierre Fraigniaud, Juho Hirvonen, Ami Paz, and Mor Perry

    URL: https://doi.org/10.4230/LIPIcs.ICALP.2016.118, doi:10.4230/LIPIcs.ICALP.2016.118. 12 Laurent Feuilloley, Pierre Fraigniaud, Juho Hirvonen, Ami Paz, and Mor Perry. Redun- dancy in distributed proofs. In 32nd International Symposium on Distributed Comput- ing, DISC , pages 24:1–24:18,

    work page doi:10.4230/lipics.icalp.2016.118 2016

  4. [11]

    13 Pierre Fraigniaud, Mika Göös, Amos Korman, Merav Parter, an d David Peleg

    URL: https://doi.org/10.4230/LIPIcs.DISC.2018.24, doi:10.4230/LIPIcs.DISC.2018.24. 13 Pierre Fraigniaud, Mika Göös, Amos Korman, Merav Parter, an d David Peleg. Ran- domized distributed decision. Distributed Computing , 27(6):419–434,

    work page doi:10.4230/lipics.disc.2018.24 2018

  5. [12]

    14 Pierre Fraigniaud, Amos Korman, and David Peleg

    URL: https://doi.org/10.1007/s00446-014-0211-x, doi:10.1007/s00446-014-0211-x. 14 Pierre Fraigniaud, Amos Korman, and David Peleg. Towards a c omplexity the- ory for local distributed computing. J. ACM , 60(5):35:1–35:26,

    work page doi:10.1007/s00446-014-0211-x

  6. [13]

    15 Pierre Fraigniaud, Boaz Patt-Shamir, and Mor Perry

    URL: https://doi.org/10.1145/2499228, doi:10.1145/2499228. 15 Pierre Fraigniaud, Boaz Patt-Shamir, and Mor Perry. Random ized proof- labeling schemes. Distributed Computing , 32(3):217–234,

    doi:10.1145/2499228

  7. [15]

    17 John Gill

    URL: https://doi.org/10.1007/s00446-018-0340-8, doi:10.1007/s00446-018-0340-8. 17 John Gill. Computational complexity of probabilistic turi ng machines. SIAM J. Comput. , 6(4):675–695,

    work page doi:10.1007/s00446-018-0340-8

  8. [17]

    URL: https://doi.org/10.1007/s00453-015-0104-9, doi:10.1007/s00453-015-0104-9. P. Crescenzi, P. Fraigniaud and A. Paz 21 19 Mika Göös and Jukka Suomela. Locally checkable proofs in dis tributed computing. The- ory of Computing , 12(1):1–33,

    work page doi:10.1007/s00453-015-0104-9

Show all 23 references
  1. [18]

    20 Karthik C

    URL: https://doi.org/10.4086/toc.2016.v012a019, doi:10.4086/toc.2016.v012a019. 20 Karthik C. S., Bundit Laekhanukit, and Pasin Manurangsi. On the parameterized complexity of approximating dominating set. In Proceedings of the 50th Annual ACM SIGACT Symposium on Theory of Compu...

    2016 doi

  2. [19]

    21 Gillat Kol, Rotem Oshman, and Raghuvansh R

    URL: https://doi.org/10.1145/3188745.3188896, doi:10.1145/3188745.3188896. 21 Gillat Kol, Rotem Oshman, and Raghuvansh R. Saxena. Interac tive distributed proofs. In Proceedings of the 2018 ACM Symposium on Principles of Distr ibuted Computing, PODC , pages 255–264,

    2018

  3. [22]

    25 Moni Naor and Larry J

    URL: http://arxiv.org/abs/1812.10917, arXiv:1812.10917. 25 Moni Naor and Larry J. Stockmeyer. What can be computed local ly? SIAM J. Comput., 24(6):1259–1277,

    arXiv

  4. [1976]

    URL: https://doi.org/10.1016/0304-3975(76)90061-X, doi:10.1016/0304-3975(76)90061-X

    doi

  5. [1977]

    18 Mika Göös, Toniann Pitassi, and Thomas Watson

    URL: https://doi.org/10.1137/0206049, doi:10.1137/0206049. 18 Mika Göös, Toniann Pitassi, and Thomas Watson. Zero-inform ation protocols and un- ambiguity in arthur-merlin communication. Algorithmica, 76(3):684–719,

    doi

  6. [1995]

    26 Noam Nisan

    URL: https://doi.org/10.1137/S0097539793254571, doi:10.1137/S0097539793254571. 26 Noam Nisan. The communication complexity of threshold gate s. In Combinatorics, Paul Erdos is Eighty , volume 1, pages 301–315,

    doi

  7. [2007]

    23 Eyal Kushilevitz and Noam Nisan

    URL: https://doi.org/10.1007/s00446-007-0025-1, doi:10.1007/s00446-007-0025-1. 23 Eyal Kushilevitz and Noam Nisan. Communication complexity. Cambridge University Press,

    doi

  8. [2009]

    2 Amir Abboud, A viad Rubinstein, and R

    URL: https://doi.org/10.1145/1490270.1490272, doi:10.1145/1490270.1490272. 2 Amir Abboud, A viad Rubinstein, and R. Ryan Williams. Distri buted PCP theorems for hardness of approximation in P. In 58th IEEE Annual Symposium on Foundations of Com- puter Science, FOCS , pages 25–36,

  9. [2013]

    4 Maria Axenovich, Jochen Harant, Jakub Przybylo, Roman Sotá k, Margit Voigt, and Jenny Weidelich

    URL: https://doi.org/10.1016/j.tcs.2013.07.026, doi:10.1016/j.tcs.2013.07.026. 4 Maria Axenovich, Jochen Harant, Jakub Przybylo, Roman Sotá k, Margit Voigt, and Jenny Weidelich. A note on adjacent vertex distinguishing colori ngs of graphs. Discrete Ap- plied Mathematics , 205:1–7,

    2013 doi

  10. [2014]

    10 Laurent Feuilloley and Pierre Fraigniaud

    URL: https://doi.org/10.1145/2611462.2611493, doi:10.1145/2611462.2611493. 10 Laurent Feuilloley and Pierre Fraigniaud. Survey of distri buted decision. Bulletin of the EATCS, 119,

  11. [2015]

    28 Larry J

    URL: https://doi.org/10.4230/LIPIcs.CCC.2015.88, doi:10.4230/LIPIcs.CCC.2015.88. 28 Larry J. Stockmeyer. The polynomial-time hierarchy. Theor. Comput. Sci. , 3(1):1–22,

    2015 doi

  12. [2016]

    5 Alkida Balliu, Gianlorenzo D’Angelo, Pierre Fraigniaud, a nd Dennis Olivetti

    URL: https://doi.org/10.1016/j.dam.2015.12.005, doi:10.1016/j.dam.2015.12.005. 5 Alkida Balliu, Gianlorenzo D’Angelo, Pierre Fraigniaud, a nd Dennis Olivetti. What can be verified locally? J. Comput. Syst. Sci. , 97:106–120,

    2015 doi

  13. [2017]

    20 Trade-offs in Distributed Interactive Proofs 3 Daniel Apon, Jonathan Katz, and Alex J

    URL: https://doi.org/10.1109/FOCS.2017.12, doi:10.1109/FOCS.2017.12. 20 Trade-offs in Distributed Interactive Proofs 3 Daniel Apon, Jonathan Katz, and Alex J. Malozemoff. One-roun d multi-party communi- cation complexity of distinguishing sums. Theor. Comput. Sci. , 501:101–108,

    2017 doi

  14. [2018]

    6 Keren Censor-Hillel, Ami Paz, and Mor Perry

    URL: https://doi.org/10.1016/j.jcss.2018.05.004, doi:10.1016/j.jcss.2018.05.004. 6 Keren Censor-Hillel, Ami Paz, and Mor Perry. Approximate pr oof-labeling schemes. In Structural Information and Communication Complexity - 24t h International Colloquium, SIROCCO, pages 71–89,

    2018 doi

  15. [2019]

    8 Sebastian Czerwinski, Jaroslaw Grytczuk, and Wiktor Zelaz ny

    URL: https://doi.org/10.1137/1.9781611975482.51, doi:10.1137/1.9781611975482.51. 8 Sebastian Czerwinski, Jaroslaw Grytczuk, and Wiktor Zelaz ny. Lucky la- belings of graphs. Inf. Process. Lett. , 109(18):1078–1081,

    doi

Pith tools

Reviewed August 14, 2026 · model on record in the stance chip above.