{
  "$type": "site.standard.document",
  "bskyPostRef": {
    "cid": "bafyreigfjhr57wcpkr3tq3ocnvm37r2vbhijtfahoq5va3hq6x32ogtngq",
    "uri": "at://did:plc:4rgrdigiftglskeax4wvmsev/app.bsky.feed.post/3moksjlrfcif2"
  },
  "coverImage": {
    "$type": "blob",
    "ref": {
      "$link": "bafkreiflo6xt7is6b2iafwghkjahlgggocme5jwjsbeuqqwcywuvjhmszm"
    },
    "mimeType": "image/png",
    "size": 24783
  },
  "path": "/abs/2606.18540v1",
  "publishedAt": "2026-06-18T00:00:00.000Z",
  "site": "https://arxiv.org",
  "tags": [
    "Neil Krishnan",
    "Elchanan Mossel"
  ],
  "textContent": "**Authors:** Neil Krishnan, Elchanan Mossel\n\nWe study the role of depth in ReLU networks with discrete (Boolean) inputs and real-valued outputs, complementing two established lines of work. For Boolean inputs, striking depth separation results were proven for $\\mathsf{AC}^0$ but with threshold ($\\mathsf{TC}^0$) or ReLU gates depth separation is only established for depth two vs. three. On the other hand, for {\\em real-valued} functions and ReLU networks, Telgarsky's (2016) constructed a simple one variable class of functions which establishes separation at higher depths. In this paper we are interested to establish an all-depths depth separation for ReLU networks on $\\\\{0,1\\\\}^n$. We do so by exhibiting an explicit family of functions computable exactly by a ReLU network of depth $n+1$ and constant width, such that any ReLU network of depth $d$ and width $w$ computing the function exactly must satisfy $w^d = Ω(2^n)$; in particular, no network of depth $d = o(n/\\log n)$ can compute it with width polynomial in $n$. We note that our lower bound relies on \\emph{exact, infinite-accuracy} computation as an exponential precision truncation of the output is computable by a polynomial-size $\\mathsf{TC}^0$ circuit.",
  "title": "Depth Lower Bounds for ReLU Networks with Binary Inputs"
}