{"ID":2852458,"CreatedAt":"2026-06-01T04:54:23.091178241Z","UpdatedAt":"2026-06-01T04:54:23.091178241Z","DeletedAt":null,"paper_url":"https://arxiv.org/abs/2510.19075","arxiv_id":"2510.19075","title":"Efficiently Batching Unambiguous Interactive Proofs","abstract":"We show that if a language $L$ admits a public-coin unambiguous interactive proof (UIP) with round complexity $\\ell$, where $a$ bits are communicated per round, then the batch language $L^{\\otimes k}$, i.e. the set of $k$-tuples of statements all belonging to $L$, has an unambiguous interactive proof with round complexity $\\ell\\cdot\\mathsf{polylog}(k)$, per-round communication of $a\\cdot \\ell\\cdot\\mathsf{polylog}(k) + \\mathsf{poly}(\\ell)$ bits, assuming the verifier in the $\\mathsf{UIP}$ has depth bounded by $\\mathsf{polylog}(k)$. Prior to this work, the best known batch $\\mathsf{UIP}$ for $L^{\\otimes{k}}$ required communication complexity at least $(\\mathsf{poly}(a)\\cdot k^ε + k) \\cdot \\ell^{1/ε}$ for any arbitrarily small constant $ε\u003e0$ (Reingold-Rothblum-Rothblum, STOC 2016). As a corollary of our result, we obtain a doubly efficient proof system, that is, a proof system whose proving overhead is polynomial in the time of the underlying computation, for any language computable in polynomial space and in time at most $n^{O\\left(\\sqrt{\\frac{\\log n}{\\log\\log n}}\\right)}$. This expands the state of the art of doubly efficient proof systems: prior to our work, such systems were known for languages computable in polynomial space and in time $n^{({\\log n})^δ}$ for a small $δ\u003e0$ significantly smaller than $1/2$ (Reingold-Rothblum-Rothblum, STOC 2016).","short_abstract":"We show that if a language $L$ admits a public-coin unambiguous interactive proof (UIP) with round complexity $\\ell$, where $a$ bits are communicated per round, then the batch language $L^{\\otimes k}$, i.e. the set of $k$-tuples of statements all belonging to $L$, has an unambiguous interactive proof with round complex...","url_abs":"https://arxiv.org/abs/2510.19075","url_pdf":"https://arxiv.org/pdf/2510.19075v1","authors":"[\"Bonnie Berger\",\"Rohan Goyal\",\"Matthew M. Hong\",\"Yael Tauman Kalai\"]","published":"2025-10-21T21:04:10Z","proceeding":"cs.CC","tasks":"[\"cs.CC\",\"cs.CR\"]","methods":"[]","has_code":false}