{"id":"openai-math/The-PCP-for-PPAD-conjecture-a-quasilinear-reduction","pdf":"https://github.com/openai/math/blob/main/preprints/The-PCP-for-PPAD-conjecture-a-quasilinear-reduction-September-25-2026/paper.pdf","url":"https://github.com/openai/math/tree/main/preprints/The-PCP-for-PPAD-conjecture-a-quasilinear-reduction-September-25-2026","tags":["complexity-theory","pcp","ppad"],"score":0,"title":"The PCP-for-PPAD conjecture: a quasilinear reduction","domain":"Theoretical computer science","family":"136","origin":"ai-generated","source":"openai-math","authors":["OpenAI"],"reviews":0,"subject":"cs.CC","summary":"We prove the quasilinear-size PCP-for-PPAD conjecture of Babichenko, Papadimitriou, and Rubinstein. There are fixed positive rational constants ε and δ and a deterministic polynomial-time reduction that transforms an End-of-Line instance of binary length N into a generalized circuit of total binary length $`N(\\log N)^{O(1)}`$. From any rational assignment of polynomial encoding length that ε -satisfies all but a δ fraction of the gates, a solution to the original End-of-Line instance can be recovered in polynomial time, regardless of which gates fail. Such assignments always exist, with one…","category":"research","comments":0,"disputed":false,"division":"cs","mentions":0,"discussed":0,"published":"2026-09-25","reactions":{},"formalized":false,"family_title":"A quasilinear PCP theorem for PPAD"}