The 3MIN threshold conjecture for reliable noisy computation

Let δ3MIN\delta^*_{\operatorname{3MIN}} denote the threshold for reliable computation with noisy circuits of 3MIN gates, and let δ(3)\delta^*(3) denote the threshold for reliable computation with noisy circuits of fan-in 33. 3MIN threshold conjecture. The thresholds are equal:

δ3MIN=δ(3).\delta^*_{\operatorname{3MIN}}=\delta^*(3).

This conjecture asserts that restricting noisy circuits of fan-in three to the single functionally complete 3MIN gate does not change the reliable-computation threshold, analogously to the equality of the thresholds for NAND formulas and fan-in-two formulas. The paper presents it as a conjecture motivated by the known fan-in-two result; no resolution is given here.

Sources & referencesView supporting material

Primary source

Andrew K. Yang, “Strong Data Processing Inequalities and their Applications to Reliable Computation”, arXiv:2408.08239 (2024).

Progress summary

Never refreshed

Nothing recorded yet. Refresh searches the literature and the public web for attempts on this problem, and writes the first summary here.

Solutions 0

No solutions have been posted yet.