Constant Degree Networks for Almost-Everywhere Reliable Transmission

Dor Minzer; Mitali Bafna

REVIEW 1 major objections 5 minor 1 cited by

Constant Degree Networks for Almost-Everywhere Reliable Transmission

T0 review · 1 major / 5 minor · reviewed 2026-08-10 · deepseek-v4-flash

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

Pith's one-line read This paper constructs constant-degree networks whose routing protocols use polylogarithmic work and tolerate a constant fraction of adversarial edge corruptions, settling the main open problem of [DPPU86].

desk verdict Genuinely new composition technique that likely solves the DPPU86 open problem, but Corollary 4.5 has a real, fixable gap in the final all-pairs majority argument. read the letter →

arxiv 2501.00337 v1 pith:F2HWNKOE submitted 2024-12-31 cs.DC cs.CRcs.DS

Mitali Bafna , Dor Minzer This is my paper · ORCID

classification cs.DCcs.CRcs.DS MSC 68M1468M1568R10

keywords almost-everywherereliabletransmissionconstant-degreenetworksedgefaulttoleranceroutingprotocolsgraphcompositionbalancedreplacementproductpermutationdistributedcomputing

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

The paper claims to settle the main open problem of almost-everywhere reliable transmission: for any small constant fraction of adversarial edge corruptions, there is a network of constant degree, with routing protocols that run in polylogarithmic work and quasilinear-logarithmic rounds, such that all but a polynomially small fraction of vertices can still communicate perfectly. If true, this is the first construction to combine constant degree, polylogarithmic efficiency, and constant fault tolerance simultaneously. The key idea is a composition lemma based on the balanced replacement product: two edge-fault-tolerant networks are merged into one whose degree is essentially the degree of the smaller network, with fault tolerance and work complexity preserved up to polynomial factors. Starting from a polylogarithmic-degree construction and a constant-degree but inefficient construction, repeated composition reduces the degree to a constant while keeping protocols efficient.

What carries the argument

The balanced replacement product $G \circledast H$ (adapted from [RVW02]): each vertex of $G$ is replaced by a cloud, a copy of $H$, and each edge of $G$ is routed through a designated vertex in each cloud, connecting clouds by parallel edges. The composition lemma (Lemma 3.1) proves that if $G$ admits $(\varepsilon_1, \nu_1)$-edge-tolerant permutation routing with work $W_1$ and $H$ admits all-pairs protocols with few doomed vertices under $\varepsilon_2$-fraction edge corruptions, then the product graph admits $(\varepsilon, \nu)$-tolerant permutation routing with work $O(W_1 W_2)$ and round $O(R_1 R_2)$, where $\varepsilon \sim \min(\varepsilon_2^2, (\varepsilon_1 - O(\nu_2))^2)$ and $\nu \sim O(\sqrt{\varepsilon} + \nu_1 + \nu_2)$. The protocol decomposes any permutation on the product into $\deg(G)$ permutations on $G$, simulates the outer protocol cloud-by-cloud, and implements each cloud-to-cloud message transfer by a majority vote through the designated edge-copy, using the inner protocols of $H$ for intra-cloud propagation. This is what carries the degree reduction: $Z = G \circledast H$ has degree $2\deg(H)$, so composing a large graph with a small graph shrinks the degree.

What would settle it

Check the quoted [BMV24, Lemma D.3] directly: if its guarantee is weaker than $(\varepsilon, O(\varepsilon))$-edge-tolerance with polylog work and $O(\log n)$ rounds, or if it holds only for specially chosen permutations rather than all permutations, then the composition chain cannot reach constant degree, and the counterexample would disprove Theorem 1.1. Alternatively, brute-force Lemma 3.1 on small graphs with known optimal protocols to see whether the doomed-vertex fraction ever exceeds the lemma's bound.

Watch

Extended reading notes

Core claim

The central claim, Theorem 1.1, is that there exists an absolute constant $D$ such that for every $\varepsilon > 0$ and all sufficiently large $n$, one can construct a $D$-regular graph on $\Theta(n)$ vertices with a set of routing protocols $R(u,v)$ of polylogarithmic work and $\tilde{O}(\log n)$ rounds with the following guarantee: if an adversary corrupts at most an $\varepsilon$-fraction of edges, then at most $\mathrm{poly}(\varepsilon)$-fraction of vertices are doomed, so all other pairs communicate perfectly. The paper also proves the stronger permutation-model version (Lemma 1.2), where the same degree and complexity bounds hold for routing any permutation, with deterministic polynomial-time construction of both graph and protocols; Theorem 1.1 follows by a randomized reduction. The engine is a composition theorem (Lemma 3.1) showing that composing two edge-fault-tolerant networks via the balanced replacement product yields a network with degree reduced to that of the smaller factor, while the tolerance and work bounds degrade only polynomially.

Load-bearing premise

The load-bearing premise is Theorem 4.1, quoted from [BMV24, Lemma D.3], which asserts the existence of polylogarithmic-degree edge-tolerant permutation routing networks with polylogarithmic work and linear-in-$\varepsilon$ tolerance for every $n$; if that quoted theorem fails or has weaker parameters, the constant-degree construction collapses.

Editorial extensions

If this is right

Corollary 1.3: any distributed protocol designed for the complete network that tolerates $\varepsilon^c$ corrupted nodes can be simulated on the sparse constant-degree graph with only polylogarithmic overhead in rounds and work, and all but an $O(\varepsilon)$-fraction of nodes still output correctly.
Using known reductions (e.g., [GO08]), the network supports almost-everywhere Byzantine agreement and secure multiparty computation on a constant-degree sparse graph, a step toward practical fault-tolerant MPC on realistic network topologies.
The construction in the permutation model (Lemma 1.2) is fully deterministic and polynomial-time, so it can serve as a building block in PCP constructions that require efficient fault-tolerant routing on sparse graphs.
The composition lemma works for edge-fault-tolerant networks generally, so any future improvement in base networks (e.g., lower degree or better tolerance) automatically transfers to the final constant-degree construction.
This resolves the trade-off identified in [DPPU86]: previously one had to choose between constant degree with $o(1)$ faults, constant degree with exponential work, or polylogarithmic degree with constant fault tolerance; now all three goals are met simultaneously.

Reading between the lines

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

The composition lemma may be applicable beyond the two base constructions used here: any pair of edge-fault-tolerant networks satisfying the lemma's hypotheses can be merged, so the technique gives a general recipe for trading degree against efficiency in fault-tolerant routing.
Because the composition is proven only for edge-faults and the paper notes it is not known for vertex-faults, extending the result to the vertex-corruption model (which is the more common assumption in distributed computing) would require a new ingredient; this is an implicit open direction.
A natural stress test is whether the $\mathrm{poly}(\varepsilon)$ doomed-vertex fraction can be improved to $O(\varepsilon)$ or $\varepsilon^2$; the current proof loses a square root in the composition, so tightening Lemma 3.1 would propagate to the final parameters.
The randomized all-pairs protocol of Theorem 1.1 selects random polylog-sized vertex sets for each pair and uses majority voting; derandomizing this selection, or reducing the polylog overhead to $\log n$, would make the construction more directly usable in practice.

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.

Desk Editor's Note

read the letter

Things you should know before reading: the paper has a genuinely new composition lemma (Lemma 3.1) that, on paper, gives constant-degree networks with polylog work and constant edge-fault tolerance, resolving the main open problem of DPPU86. It deserves a serious referee. But the final amplification step in Corollary 4.5 has a real gap as written, and until that is fixed Theorem 1.1 is not proved.

The core contribution is the balanced replacement product composition. Lemma 3.1 is new, the analysis in Section 3.2 is careful, and Claim 3.3 convincingly shows that a successful protocol on G survives simulation over Z when the super-edge set is small. The parameter chain in Lemma 4.4 also checks out: the epsilon^4, epsilon^16, epsilon^32 progression is consistent, and the final degree reduction via Upfal's constant-degree expanders is sound. This is not a routine combination of prior work; the composition step is the real substance.

The soft spot is Corollary 4.5. The protocol R(u,v) sends u's message to a random set S_{u,v} via R'(u,w), then each w relays to v via R'(w,v), and v takes a majority. The proof defines D1 as vertices with many outgoing bad R', and D2/D3 using "S_{u,v} is corrupted," which is a condition on the first hop R'(u,w). Nothing bounds the number of vertices v for which a large fraction of the incoming protocols R'(w,v) are bad. A vertex v with, say, a third of all R'(w,v) bad can sit outside D, and then the second-hop failures can exceed half, breaking the majority. This is fixable: Markov gives that only O(epsilon) vertices have more than a 1/8 incoming-bad fraction, so adding D_in = {v : >1/8 of R'(w,v) are bad} to D(E) repairs the proof. But as printed, the step is incomplete.

The other caveat is the heavy reliance on Theorem 4.1 from the authors' own BMV24 preprint, which is not re-proved here. If that base has weaker tolerance or work parameters, the whole construction collapses. That is a legitimate dependency, but the referee should verify it.

Who is this for? Researchers in fault-tolerant distributed computing, sparse MPC simulation, and graph product constructions. I would cite the composition lemma even before the main theorem is fixed. Recommendation: send to peer review, require a repair to Corollary 4.5 and a careful check of the BMV24 base.

Referee Report

1 major / 5 minor

Summary. The paper studies the almost-everywhere reliable message transmission problem on sparse networks. Its main theorem (Theorem 1.1) claims a constant-degree graph on Theta(n) vertices with routing protocols of polylogarithmic work and O~(log n) round complexity that tolerate a constant fraction of adversarial edge faults, with only a poly(epsilon)-fraction of doomed vertices. The proof is modular: a new composition lemma (Lemma 3.1) combines two edge-fault-tolerant routing networks via the balanced replacement product, reducing degree while maintaining fault tolerance and efficiency; this lemma is then applied to the polylogarithmic-degree networks of [BMV24] and the constant-degree but exponentially expensive networks of [Upf92] to obtain the claimed parameters.

Significance. If the main theorem is correct, it resolves the main open problem of [DPPU86], giving the first constant-degree network with polylogarithmic-work and constant-fault-tolerant routing. The composition technique itself is a genuine conceptual contribution: the analysis of the replacement product in Section 3 is careful, with explicit bounds on bad super-edges via Markov and union bounds, and the parameter chain in Section 4.3 is consistent once the omitted specifications are filled in. The paper is also honest about its heavy reliance on the companion result [BMV24, Lemma D.3], which is cited but not proved here, and on [Upf92]; this is acceptable for a paper that is primarily a composition argument, but it means the main theorem is conditional on the correctness of those cited results. The central gap is in the final all-pairs amplification step, Corollary 4.5, which I detail below; it is local and fixable with a modest addition to the doomed-set definition.

major comments (1)

[§4.4, Corollary 4.5] The proof of the final amplification from permutation routing to all-pairs routing does not control failures of the incoming protocols R'(w,v). The sets D1, D2, and D3 are all defined in terms of failures of protocols R'(u,w) that are outgoing from u: D1 is the set of vertices with many bad outgoing protocols, and the event that Su,v is corrupted depends only on R'(u,w) for w in Su,v, not on the receiver v. Consequently, a vertex v outside D(E) can still have, for example, one third of the protocols R'(w,v) bad, and then in the majority vote of R(u,v) the second-hop transmissions can fail for more than half of the chosen w, breaking the Chernoff-majority conclusion. This gap is load-bearing for Theorem 1.1. The fix is to add D_in = {v : more than 1/8 of the protocols R'(·,v) are bad} to the doomed set D(E); Markov's inequality gives |D_in| ≤ O(epsilon n). Then for any u,v outside D1 ∪ D_in, at most 1/4 of the w in Su,v have a bad first-hop or second-hop protocol, and the majority argument goes through with the same high-probability bound. As printed, the proof of Theorem 1.1 is incomplete at this step.

minor comments (5)

[§4.3, Lemma 4.4 proof] The second composition step ('composing G3 with another graph G4') does not state the tolerance parameters of G4. To obtain epsilon_5 = Theta(epsilon^16), the reader must choose G4 to be (Theta(epsilon^8), O(epsilon^8))-tolerant before applying Proposition 4.2; please specify these parameters explicitly so the parameter chain is fully verifiable.
[§4.3, Lemma 4.4 proof] The first sentence 'We assume epsilon <= c where c is a small absolute constant, otherwise the statement is vacuously true' is not self-evident. For epsilon > c, the demanded tolerance epsilon^32 is still a small positive number (for epsilon < 1), and the claim needs a short explanation or a monotonicity argument rather than an assertion.
[Abstract and Introduction] There is a duplicated word: 'that that even if an adversary corrupts...' appears in the abstract and the introduction; please fix throughout.
[§1.3.3] The text says 'we now explain how to prove Theorem 1.2' but the result being proved is Lemma 1.2 (the permutation-model statement); there is no Theorem 1.2 in the paper. Please correct the cross-reference.
[Corollary 4.5] In the final paragraph, the statement that 'every two vertices w,w' outside D can communicate perfectly via R(w,w') and R(w',w)' is not argued in detail; in particular, the roles of D2 and D3 in ensuring both directions of communication should be spelled out, especially given the asymmetry of the protocol definitions.

Circularity Check

0 steps flagged · score 0.0 of 10

No circularity: composition lemma is self-contained and the base network is an independent prior theorem; the Corollary 4.5 orientation gap is a correctness issue, not circularity.

full rationale

I walked the claimed derivation chain. Lemma 3.1 is a new, self-contained composition argument: it assumes black-box (ε1,ν1)-tolerant permutation routing on G and (ε2,ν2)-tolerant all-pairs protocols on H and explicitly proves, via Algorithm 1 and Claims 3.2 and 3.3, that G r H inherits these properties with the stated parameter degradation. The proof never re-uses the theorem it is trying to establish, and no equation in it is definitionally equal to its inputs. Lemma 4.4 instantiates Lemma 3.1 with Theorem 4.1 (from [BMV24]) and Theorem 4.3 (from [Upf92]); Theorem 4.1 is a parameter-free existence statement from prior work by two of the same authors, but it is not the target result, its assumptions do not contain Theorem 1.1, and the present paper does not merely rename it. Section 4.4's Corollary 4.5 has a technical orientation gap: D3 is defined via corrupted sets Su,v whose corruption condition tests bad R'(u,w), i.e., outgoing failures, so a vertex with many incoming bad protocols R'(w,v) is not excluded by D1, D2, or D3; the majority over second hops is therefore not fully justified as printed. This is a correctness risk and should be repaired by defining D3 via incoming failures, but it is not a circularity: it is an omitted case, not an equation reducing to its own input. There is no fitted parameter relabeled as a prediction and no known result renamed as a new one. Accordingly, the circularity score is 0.

Assumptions & free parameters 0 free parameters · 5 assumptions · 0 invented entities

All constants in the proof are asymptotic and chosen to satisfy inequalities; none are fitted to data. The argument rests on two external theorems: Theorem 4.1 from the authors' own [BMV24] (polylog-degree edge-fault tolerant graphs) and Theorem 4.3 from [Upf92] (constant-degree, exponential-work tolerant graphs). The paper's own contribution, Lemma 3.1, is a composition theorem proved from these building blocks using the balanced replacement product. Standard probabilistic tools (Markov, Chernoff, union bound) and matching decompositions are used. No new physical or computational entities are introduced.

assumptions (5)

domain assumption Theorem 4.1 (from [BMV24]): For all n, there exists a regular graph on Theta(n) vertices with polylog degree, such that for every permutation there is an (epsilon, O(epsilon))-edge-tolerant routing protocol with round O(log n) and work polylog n, constructible in poly(n) time.
Used as the base construction G1, G2, G4 in the proof of Lemma 4.4. This is the authors' own prior work, not proved in this paper.
domain assumption Theorem 4.3 (from [Upf92]): There is a constant d such that for all n there is a d-regular graph on n vertices with all-pairs protocols of work exp(n) and round O(log n), tolerant to a constant fraction of edge corruptions with O(epsilon) doomed vertices.
Used in the final composition to reduce degree to a constant. The edge-fault version is derived by the authors from Upfal's vertex-fault result.
standard math The balanced replacement product G r H as defined in [RVW02] has the property that if at most epsilon-fraction of edges in Z are corrupted, then at most 2epsilon of the edges inside clouds and at most 2epsilon of the edges across clouds are corrupted.
Used in Section 1.3.1 and Section 3 in the error analysis of Lemma 3.1.
standard math By Markov's inequality, if at most epsilon-fraction of edges of Z are corrupted, then at most O(sqrt(epsilon))-fraction of clouds are 'bad' (contain more than sqrt(2epsilon) fraction of corrupted edges).
Used in the proof of Lemma 3.1 to bound the number of bad clouds and bad super-edges.
standard math The edges of a complete graph on an even number of vertices can be decomposed into matchings (permutations), and each vertex of a constant-degree graph has degree D such that corrupting epsilon-fraction of vertices corrupts at most O(epsilon)-fraction of edges.
Used in Proposition 4.2 and Corollary 4.5 to obtain all-pairs protocols from permutation protocols, and to translate between vertex and edge fault models.

how reviews work

0 comments

Cite this review

Pith. "Pith review of Constant Degree Networks for Almost-Everywhere Reliable Transmission." pith.science (2026). https://pith.science/paper/F2HWNKOE

@misc{pith2026250100337,
  author       = {Pith},
  title        = {Pith review of: Constant Degree Networks for Almost-Everywhere Reliable Transmission},
  year         = {2026},
  howpublished = {\url{https://pith.science/paper/F2HWNKOE}},
  note         = {Machine review of arXiv:2501.00337}
}

abstract

In the almost-everywhere reliable message transmission problem, introduced by [Dwork, Pippenger, Peleg, Upfal'86], the goal is to design a sparse communication network $G$ that supports efficient, fault-tolerant protocols for interactions between all node pairs. By fault-tolerant, we mean that that even if an adversary corrupts a small fraction of vertices in $G$, then all but a small fraction of vertices can still communicate perfectly via the constructed protocols. Being successful to do so allows one to simulate, on a sparse graph, any fault-tolerant distributed computing task and secure multi-party computation protocols built for a complete network, with only minimal overhead in efficiency. Previous works on this problem achieved either constant-degree networks tolerating $o(1)$ faults, constant-degree networks tolerating a constant fraction of faults via inefficient protocols (exponential work complexity), or poly-logarithmic degree networks tolerating a constant fraction of faults. We show a construction of constant-degree networks with efficient protocols (i.e., with polylogarithmic work complexity) that can tolerate a constant fraction of adversarial faults, thus solving the main open problem of Dwork et al.. Our main contribution is a composition technique for communication networks, based on graph products. Our technique combines two networks tolerant to adversarial edge-faults to construct a network with a smaller degree while maintaining efficiency and fault-tolerance. We apply this composition result multiple times, using the polylogarithmic-degree edge-fault tolerant networks constructed in a recent work of [Bafna, Minzer, Vyas'24] (that are based on high-dimensional expanders) with itself, and then with the constant-degree networks (albeit with inefficient protocols) of [Upfal'92].

Discussion (0). Continue with ORCID to comment.

Forward citations

Cited by 1 Pith paper

Reviewed papers in the Pith corpus that reference this work. Sorted by Pith novelty score. Full citation record

All-to-All Communication with Mobile Edge Adversary: Almost Linearly More Faults, For Free
cs.DS 2025-05 accept novelty 7.0 of 10

Error correcting codes, locally decodable codes, and a new resilient routing primitive allow O(1)-round simulation of Congested Clique rounds under per-node bounded-degree edge corruption.

Reference graph

Works this paper leans on

17 extracted references · 12 canonical work pages · cited by 1 Pith paper

[1]

Proof verification and the hardness of approximation problems

Sanjeev Arora, Carsten Lund, Rajeev Motwani, Madhu Sudan, and Mario Szegedy. Proof verification and the hardness of approximation problems. J. ACM , 45(3):501--555, 1998

1998
[2]

Probabilistic checking of proofs: A new characterization of NP

Sanjeev Arora and Shmuel Safra. Probabilistic checking of proofs: A new characterization of NP . J. ACM , 45(1):70--122, 1998

1998
[3]

Completeness theorems for non-cryptographic fault-tolerant distributed computation (extended abstract)

Michael Ben - Or, Shafi Goldwasser, and Avi Wigderson. Completeness theorems for non-cryptographic fault-tolerant distributed computation (extended abstract). In Janos Simon, editor, STOC 1988 , pages 1--10. ACM , 1988

work page 1988
[4]

Quasi-linear size pcps with small soundness from HDX

Mitali Bafna, Dor Minzer, and Nikhil Vyas. Quasi-linear size pcps with small soundness from HDX . CoRR , abs/2407.12762, 2024

arXiv 2024
[5]

Multiparty unconditionally secure protocols (extended abstract)

David Chaum, Claude Cr \' e peau, and Ivan Damg rd. Multiparty unconditionally secure protocols (extended abstract). In Janos Simon, editor, STOC 1988 , pages 11--19. ACM , 1988

work page 1988
[6]

Garay, Rafail Ostrovsky, Rutvik Patel, and Vassilis Zikas

Nishanth Chandran, Pouyan Forghani, Juan A. Garay, Rafail Ostrovsky, Rutvik Patel, and Vassilis Zikas. Universally composable almost-everywhere secure computation. In ITC 2022 , volume 230 of LIPIcs , pages 14:1--14:25. Schloss Dagstuhl - Leibniz-Zentrum f \" u r Informatik, 2022

work page 2022
[7]

Improved fault tolerance and secure computation on sparse networks

Nishanth Chandran, Juan Garay, and Rafail Ostrovsky. Improved fault tolerance and secure computation on sparse networks. In ICALP 2010 , pages 249--260. Springer, 2010

work page 2010
[8]

Edge fault tolerance on sparse networks

Nishanth Chandran, Juan Garay, and Rafail Ostrovsky. Edge fault tolerance on sparse networks. In ICALP 2012 , pages 452--463. Springer, 2012

work page 2012

Show all 17 references

[9]

Fault tolerance in networks of bounded degree

Cynthia Dwork, David Peleg, Nicholas Pippenger, and Eli Upfal. Fault tolerance in networks of bounded degree. In STOC 1986 , pages 370--379, 1986

1986
[10]

Interactive proofs and the hardness of approximating cliques

Uriel Feige, Shafi Goldwasser, L \' a szl \' o Lov \' a sz, Shmuel Safra, and Mario Szegedy. Interactive proofs and the hardness of approximating cliques. J. ACM , 43(2):268--292, 1996

1996
[11]

Garay and Rafail Ostrovsky

Juan A. Garay and Rafail Ostrovsky. Almost-everywhere secure computation. In Nigel P. Smart, editor, EUROCRYPT 2008 , volume 4965 of Lecture Notes in Computer Science , pages 307--323. Springer, 2008

2008
[12]

Efficient constructions for almost-everywhere secure computation

Siddhartha Jayanti, Srinivasan Raghuraman, and Nikhil Vyas. Efficient constructions for almost-everywhere secure computation. In EUROCRYPT 2020 , pages 159--183. Springer, 2020

2020
[13]

Shostak, and Marshall C

Leslie Lamport, Robert E. Shostak, and Marshall C. Pease. The byzantine generals problem. ACM Trans. Program. Lang. Syst. , 4(3):382--401, 1982

1982
[14]

Explicit constructions of R amanujan complexes of type A _d

Alexander Lubotzky, Beth Samuels, and Uzi Vishne. Explicit constructions of R amanujan complexes of type A _d . Eur. J. Comb. , 26(6):965--993, 2005

2005
[15]

Ramanujan complexes of type A _d

Alexander Lubotzky, Beth Samuels, and Uzi Vishne. Ramanujan complexes of type A _d . Israel journal of Mathematics , 149:267--299, 2005

2005
[16]

Entropy waves, the zig-zag graph product, and new constant-degree expanders

Omer Reingold, Salil Vadhan, and Avi Wigderson. Entropy waves, the zig-zag graph product, and new constant-degree expanders. Annals of Mathematics , pages 157--187, 2002

2002
[17]

Tolerating linear number of faults in networks of bounded degree

Eli Upfal. Tolerating linear number of faults in networks of bounded degree. In Proceedings of the eleventh annual ACM symposium on Principles of distributed computing , pages 83--89, 1992

1992

Pith tools

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

[1] [1]

Proof verification and the hardness of approximation problems

Sanjeev Arora, Carsten Lund, Rajeev Motwani, Madhu Sudan, and Mario Szegedy. Proof verification and the hardness of approximation problems. J. ACM , 45(3):501--555, 1998

1998

[2] [2]

Probabilistic checking of proofs: A new characterization of NP

Sanjeev Arora and Shmuel Safra. Probabilistic checking of proofs: A new characterization of NP . J. ACM , 45(1):70--122, 1998

1998

[3] [3]

Completeness theorems for non-cryptographic fault-tolerant distributed computation (extended abstract)

Michael Ben - Or, Shafi Goldwasser, and Avi Wigderson. Completeness theorems for non-cryptographic fault-tolerant distributed computation (extended abstract). In Janos Simon, editor, STOC 1988 , pages 1--10. ACM , 1988

work page 1988

[4] [4]

Quasi-linear size pcps with small soundness from HDX

Mitali Bafna, Dor Minzer, and Nikhil Vyas. Quasi-linear size pcps with small soundness from HDX . CoRR , abs/2407.12762, 2024

arXiv 2024

[5] [5]

Multiparty unconditionally secure protocols (extended abstract)

David Chaum, Claude Cr \' e peau, and Ivan Damg rd. Multiparty unconditionally secure protocols (extended abstract). In Janos Simon, editor, STOC 1988 , pages 11--19. ACM , 1988

work page 1988

[6] [6]

Garay, Rafail Ostrovsky, Rutvik Patel, and Vassilis Zikas

Nishanth Chandran, Pouyan Forghani, Juan A. Garay, Rafail Ostrovsky, Rutvik Patel, and Vassilis Zikas. Universally composable almost-everywhere secure computation. In ITC 2022 , volume 230 of LIPIcs , pages 14:1--14:25. Schloss Dagstuhl - Leibniz-Zentrum f \" u r Informatik, 2022

work page 2022

[7] [7]

Improved fault tolerance and secure computation on sparse networks

Nishanth Chandran, Juan Garay, and Rafail Ostrovsky. Improved fault tolerance and secure computation on sparse networks. In ICALP 2010 , pages 249--260. Springer, 2010

work page 2010

[8] [8]

Edge fault tolerance on sparse networks

Nishanth Chandran, Juan Garay, and Rafail Ostrovsky. Edge fault tolerance on sparse networks. In ICALP 2012 , pages 452--463. Springer, 2012

work page 2012