The 3MIN threshold conjecture for reliable noisy computation
The 3MIN threshold conjecture for reliable noisy computation
Let denote the threshold for reliable computation with noisy circuits of 3MIN gates, and let denote the threshold for reliable computation with noisy circuits of fan-in . 3MIN threshold conjecture. The thresholds are equal:
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
Nothing recorded yet. Refresh searches the literature and the public web for attempts on this problem, and writes the first summary here.
Solutions 0
Sign in to submit a solution.
No solutions have been posted yet.