{
  "$type": "site.standard.document",
  "bskyPostRef": {
    "cid": "bafyreidujfa36n2z6elouomxsqdmg4ccyfj2vwreuxjjbe3otkhgmt476m",
    "uri": "at://did:plc:3fychdutjjusoqeq24ljch6q/app.bsky.feed.post/3mq2bwmobx4e2"
  },
  "path": "/report/2026/115",
  "publishedAt": "2026-07-07T07:21:13.000Z",
  "site": "https://eccc.weizmann.ac.il",
  "textContent": "We prove an $\\tilde{\\Omega}(n^2)$ lower bound for read-once parity branching programs computing an explicit boolean function on $n$ variables. The previous best lower bound was $\\tilde{\\Omega}(n^{1.5})$. Our lower bound is proved by reducing the problem to a lower bound in algebraic circuit complexity.",
  "title": "TR26-115 |  A Lower Bound for Read-Once Parity Branching Programs | \n\n\tBen Lee Volk"
}