{"id":"682c422b-8cf1-4701-ba05-59e12554cd9d","arxiv_id":"1908.03363","paper_version":1,"verdict":"CONDITIONAL","confidence":"MODERATE","novelty_score":7.0,"correctness_risk":"medium","formal_verification":"none","parameter_count":1,"one_line_summary":"Distributed interactive proofs admit a continuous space-communication trade-off for triangle-freeness, broad communication savings from shared randomness, and a separation between interaction-reduction and linear-size proof-labeling schemes.","lead":"This paper studies how much a network of computers can verify about itself when a powerful but untrusted helper sends short proofs to each node. It finds trade-offs between proof size, message size, number of back-and-forth rounds, and whether nodes share random coins, and shows some verification tasks become impossible if proofs are too small.","discovery_kind":"extension","skeptic_critique":{"model":"deepseek-v4-flash","headline":"Theorem 11 assumes perfect-completeness dMAM without justification; with only 2/3 completeness the constructed dAM protocol fails to meet completeness.","rationale":"The reader's weakest-assumption analysis correctly identifies the most load-bearing gap. I checked Theorem 4 carefully: the polynomial construction gives completeness 1, and soundness follows with error at most 2(n/α−1)/q ≤ 2/(cα²); the distance-2 coloring from Lemma 3 can be folded in with negligible overhead. Theorems 6, 9, and 10 also appear internally consistent at the proof-sketch level. The only place where a stated central result depends on an unproven strengthening of the model is Theorem 11, where the proof silently upgrades dMAM from two-sided to one-sided error. This is not a matter of disagreeing with common conventions: Definition 1 is explicit about the 2/3 completeness threshold, and no lemma in the paper converts that threshold into perfect completeness. The proposed concrete test settles whether the proof as written can work: with all-repetitions acceptance, two-sided completeness collapses exponentially, so the proof's central step is false for arbitrary dMAM protocols. A revised proof using majority-based amplification may succeed, which is why the verdict should remain conditional rather than reject; but the current text does not establish the advertised general reduction.","tokens_in":21399,"tokens_out":42145,"duration_ms":484863,"concrete_test":"Take any dMAM protocol with completeness exactly 2/3, e.g., a dAM protocol for a nontrivial language preceded by a dummy first Merlin message, and instantiate the proof of Theorem 11 with k = nσ. For a yes-instance, the all-repetitions rule accepts with probability (2/3)^{nσ}; for σ = 1, n = 10 this is about 0.017, not ≥ 2/3. Then check whether replacing the acceptance rule by 'majority of repetitions accept' using the certified spanning tree from Proposition 2 keeps certificate size within nσ² + O(log n) and messages within nσγ + O(log n). If it does, the theorem is salvageable by a revised proof; if it does not, the inclusion as stated needs a different formulation.","verdict_should_be":"UNCHANGED","load_bearing_attack":"Section 5.1, Theorem 11: the proof begins 'Let P be a dMAM(σ,γ) 1-sided protocol', but Definition 1 defines dMAM with completeness 2/3 and gives no one-sidedness guarantee. The constructed dAM protocol P' repeats P k = nσ times and accepts only if every repetition accepts. On a yes-instance, if P has only completeness 2/3, this acceptance rule gives probability at most (2/3)^{nσ}, which is far below the required 2/3; the proof's statement that 'all nodes will accept with probability one, since P is a 1-sided protocol' is doing essential work. Proposition 2 amplifies success probability 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 holds only if perfect completeness is either assumed, proved, or handled by a different acceptance rule.","agreement_with_reader":"agree"},"referee_report":{"model":"deepseek-v4-flash","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).","tokens_in":21596,"tokens_out":14208,"duration_ms":158537,"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":[{"comment":"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.","section":"Section 5.1, Theorem 11"},{"comment":"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.","section":"Section 4.3, Theorem 10"}],"minor_comments":[{"comment":"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.","section":"Section 5.1, proof of Theorem 11"},{"comment":"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.","section":"References"},{"comment":"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.","section":"Section 3, Theorem 4"},{"comment":"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.","section":"Section 5.2, Theorem 13"}],"recommendation":"major_revision","confidential_remarks":"The paper contains two central proofs with gaps that affect claimed main results. The Theorem 11 gap is quite plausibly repairable by replacing the all-accept rule with a majority rule plus a spanning-tree counting certificate. The Theorem 10 gap is more delicate: the reduction as written does not establish either the certificate-size or the message-size lower bound, and repairing it may require a different graph construction or a more careful treatment of cut messages. If the authors cannot repair Theorem 10, the paper would lose the claimed separation MA ⊄ AM and the shared-randomness lower bounds, though Theorems 4, 6, 9, 13, and 14 would remain. I recommend major revision with a request to address both gaps explicitly."},"author_rebuttal":null,"desk_editor":{"model":"deepseek-v4-flash","letter":"Here's my take on Crescenzi–Fraigniaud–Paz (arXiv:1908.03363). The paper is a genuine contribution. Theorem 4 gives a continuous space/communication trade-off for triangle-freeness, the first such trade-off in distributed interactive proofs. Theorem 6 shows that shared randomness gives exponential communication savings for a broad class of optimization problems that are locally checkable. Theorem 13 separates the Arthur-Merlin hierarchy from LCP with linear certificates via a counting argument. These are new, clearly stated, and the proofs of Theorem 4 and Theorem 13 are sound. I also like Theorem 9, a simple simulation of shared randomness by distributed randomness, and Proposition 2 on boosting, which fills a gap in prior work. Citations are appropriate; prior results by Kol–Oshman–Saxena and Naor–Parter–Yogev are used as black boxes rather than being repackaged.\n\nThe main soft spot is Theorem 11. The proof starts \"Let P be a dMAM(σ,γ) 1-sided protocol,\" but Definition 1 only guarantees completeness 2/3. The constructed dAM protocol repeats P a number of times and demands that all repetitions accept. On a yes-instance, if P is only 2/3-complete, the probability of all accepting is at most (2/3)^k, which is nowhere near 1. The paper does not show that dMAM can be made perfect-completeness, so the stated inclusion dMAM(σ,γ) ⊆ dAM(nσ², nσγ) is not established. This is a genuine gap in the statement of the theorem; it propagates to Corollary 12 and the applications. It is likely fixable — either prove that 1-sidedness is w.l.o.g., or state the theorem for 1-sided protocols — but the current text is not correct as a general collapse. The stress-test note got this right.\n\nTheorem 10's proof is sketchy in places, particularly the communication-complexity version where the argument is described as an adaptation. That's a minor-to-moderate concern; the intended lower bound is plausible and the reduction is standard.\n\nWho is this for? People working on distributed decision, proof-labeling schemes, and interactive proofs. The paper deserves a serious referee; with the Theorem 11 gap fixed or scoped, it would be a solid publication. I'd cite it and bring it to a reading group.","headline":"New trade-off theorems and a hierarchy separation, but Theorem 11's inclusion rests on an unproven perfect-completeness assumption.","tokens_in":22141,"tokens_out":3055,"would_cite":true,"duration_ms":30300,"reading_group":"yes","serious_thinker":"yes","would_accept_peer_review":true},"rs_alignment":null,"lean_confirmation":null,"pith_extraction":{"msc":[],"pacs":[],"model":"deepseek-v4-flash","headline":"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…","keywords":["distributed interactive proofs","distributed verification","Arthur-Merlin protocols","space-communication trade-off","shared randomness","triangle-freeness","proof-labeling schemes","interaction hierarchy"],"falsifier":"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.","tokens_in":21166,"feed_emoji":"⚖️","tokens_out":14256,"duration_ms":137990,"temperature":0.7,"pith_summary":"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.","feed_headline":"Distributed proofs trade space against communication, continuously","feed_subtitle":"Triangle-freeness is the first task where certificate size and message size can be shifted at any chosen ratio.","key_machinery":"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.","core_discovery":"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.","pith_inferences":["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."],"forward_implications":["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."],"supporting_citations":[{"why":"Introduces distributed interactive proofs and the dAM/dMAM classifications that this paper extends and compares against.","marker":"[21]"},{"why":"Gives the dAMAM protocols for graph non-isomorphism and symmetry that the interaction-reduction theorems are applied to.","marker":"[24]"},{"why":"Provides randomized proof-labeling schemes and the dMA-style O(log n)-communication protocol that Theorem 4's trade-off builds on.","marker":"[16]"},{"why":"Supplies the two-party Arthur-Merlin disjointness protocol with a communication-versus-certificate trade-off that the triangle-freeness construction adapts.","marker":"[2]"},{"why":"Underlies the multiparty disjointness lower bound used in Proposition 5 to show any proof-labeling scheme for triangle-freeness needs large certificates.","marker":"[27]"},{"why":"Defines locally checkable proofs and the certificate-size lower-bound method for proof-labeling schemes used in Proposition 5.","marker":"[19]"},{"why":"Gives the SumZero multiparty communication protocol with O(log log n) communication used in Theorem 6 to verify partial sums.","marker":"[26]"},{"why":"Provides the two-party Arthur-Merlin lower bound for equality and non-equality that Theorem 10 transfers to the symmetry problems.","marker":"[18]"},{"why":"Supplies the local-hierarchy counting argument that Theorem 13 adapts to separate the Arthur-Merlin hierarchy from linear-size proof-labeling schemes.","marker":"[11]"},{"why":"Introduces proof-labeling schemes and the O(log n)-bit spanning-tree certificates used for boosting and for simulating shared randomness with distributed randomness.","marker":"[15]"}],"fun_headline_variants":["Continuous trade-off in distributed proofs: space vs. communication","Distributed proofs: shift between certificate and message size at will","Triangle-freeness: parameterized proof size vs. message size","Dial the ratio: distributed proof size and communication trade off"],"cache_read_input_tokens":3200,"weakest_assumption_plain":"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.","fun_headline_variants_meta":{"raw":{"variants":["Continuous trade-off in distributed proofs: space vs. communication","Distributed proofs: shift between certificate and message size at will","Triangle-freeness: parameterized proof size vs. message size","Dial the ratio: distributed proof size and communication trade off"]},"model":"deepseek-v4-flash","effort":"low","cost_usd":0.001022,"raw_usage":{"total_tokens":4308,"prompt_tokens":941,"completion_tokens":3367,"prompt_tokens_details":{"cached_tokens":384},"prompt_cache_hit_tokens":384,"prompt_cache_miss_tokens":557,"completion_tokens_details":{"reasoning_tokens":3297}},"tokens_in":557,"tokens_out":3367,"duration_ms":26468,"temperature":1.0,"reasoning_tokens":3297,"cache_read_input_tokens":384,"cache_creation_input_tokens":0},"cache_creation_input_tokens":0},"created_at":"2026-08-14T14:19:03.934185+00:00","model_set":{"reader":"deepseek-v4-flash"},"falsifier":"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.","supporting_citations":[{"cited_title":"13 Pierre Fraigniaud, Mika Göös, Amos Korman, Merav Parter, an d David Peleg","cited_arxiv_id":null,"evidence_quote":"Supplies the local-hierarchy counting argument that Theorem 13 adapts to separate the Arthur-Merlin hierarchy from linear-size proof-labeling schemes."},{"cited_title":"17 John Gill","cited_arxiv_id":null,"evidence_quote":"Introduces proof-labeling schemes and the O(log n)-bit spanning-tree certificates used for boosting and for simulating shared randomness with distributed randomness."}],"review_version":1}