{
  "$type": "site.standard.document",
  "bskyPostRef": {
    "cid": "bafyreicajnov6r3ypms75aerpcfi6ekbxuveyhk3mxrfriqhatwjwdzqya",
    "uri": "at://did:plc:4rgrdigiftglskeax4wvmsev/app.bsky.feed.post/3mh37j63oelz2"
  },
  "path": "/report/2026/039",
  "publishedAt": "2026-03-14T22:50:01.000Z",
  "site": "https://eccc.weizmann.ac.il",
  "textContent": "Proving lower bounds against depth-$2$ linear threshold circuits (a.k.a. $THR \\circ THR$) is one of the frontier questions in complexity theory. Despite tremendous effort, our best lower bounds for $THR \\circ THR$ only hold for sub-quadratic number of gates, which was proven a decade ago by Tamaki (ECCC TR16) and Alman, Chan, and Williams (FOCS 2016) for a hard function in $E^{NP}$. In this work, we prove that there is a function $f \\in E^{NP}$ that requires $n^{2.5-\\varepsilon}$-size $THR \\circ THR$ circuits for any $\\varepsilon > 0$. We obtain our new results by designing a new $2^{n - n^{\\Omega(\\varepsilon)}}$-time algorithm for estimating the acceptance probability of an XOR of two $n^{2.5-\\varepsilon}$-size $THR \\circ THR$ circuits, and apply Williams' algorithmic method to obtain the desired lower bound.",
  "title": "TR26-039 |  Super-quadratic Lower Bounds for Depth-2 Linear Threshold Circuits | \n\n\tLijie Chen, \n\n\tAvishay Tal, \n\n\tYichuan Wang"
}