{
  "$type": "site.standard.document",
  "bskyPostRef": {
    "cid": "bafyreignzcfagbexfzy22mphm5sbmzqfokj62t47epy7efo2emijiqfg4a",
    "uri": "at://did:plc:3fychdutjjusoqeq24ljch6q/app.bsky.feed.post/3mis73c33vtz2"
  },
  "path": "/report/2026/048",
  "publishedAt": "2026-04-05T09:56:22.000Z",
  "site": "https://eccc.weizmann.ac.il",
  "textContent": "The linear problem specified by an $n \\times n$ matrix $M$ over a finite field is the problem of computing the product of $M$ and a given vector $x$. We present optimal error-tolerant random self-reductions (also known as worst-case to average-case reductions) for all linear problems: Given a linear-size circuit that computes $M x$ on an $\\varepsilon$-fraction of inputs $x$ for a positive constant $\\varepsilon$, we construct a randomized linear-size circuit that computes $M x$ for all inputs $x$ with high probability. This resolves the open problem posed by Asadi, Golovnev, Gur, Shinkar, and Subramanian (SODA'24), who presented quantum $n^{1.5}$-time random self-reductions for all linear problems. Somewhat surprisingly, we also demonstrate the quantum advantage of their quantum reduction over classical uniform algorithms, by proving that any classical subquadratic-time random self-reduction requires the advice complexity of $\\Omega(\\log(1/\\varepsilon) \\cdot \\log n)$, as long as the field size is at most $1/\\varepsilon$. We complement this advice complexity lower bound by presenting (1) a random self-reduction with the optimal advice complexity of $O(\\log(1/\\varepsilon) \\cdot \\log n)$ and (2) a uniform random self-reduction over a large finite field.",
  "title": "TR26-048 |  Optimal Random Self-Reductions for All Linear Problems | \n\n\tShuichi Hirahara, \n\n\tNobutaka Shimizu"
}