{
  "$type": "site.standard.document",
  "bskyPostRef": {
    "cid": "bafyreiavp7frqbsklbr3pedxyv3sjhzuqf362ozbqrr7msf6lwpr2u4xem",
    "uri": "at://did:plc:4rgrdigiftglskeax4wvmsev/app.bsky.feed.post/3mh7zhkmuxbh2"
  },
  "coverImage": {
    "$type": "blob",
    "ref": {
      "$link": "bafkreiflo6xt7is6b2iafwghkjahlgggocme5jwjsbeuqqwcywuvjhmszm"
    },
    "mimeType": "image/png",
    "size": 24783
  },
  "path": "/abs/2603.15565v1",
  "publishedAt": "2026-03-17T00:00:00.000Z",
  "site": "https://arxiv.org",
  "tags": [
    "Lixi Ye"
  ],
  "textContent": "**Authors:** Lixi Ye\n\nWe prove two new upper bounds for depth-2 linear circuits computing the $N$th disjointness matrix $D^{\\otimes N}$. First, we obtain a circuit of size $O\\big(2^{1.24485N}\\big)$ over $\\\\{0,1\\\\}$. Second, we obtain a circuit of degree $O\\big(2^{0.3199N}\\big)$ over $\\\\{0,\\pm 1\\\\}$. These improve the previous bounds of Alman and Li, namely size $O\\big(2^{1.249424N}\\big)$ and degree $O\\big(2^{N/3}\\big)$. Our starting point is the rebalancing framework developed in a line of works by Jukna and Sergeev, Alman, Sergeev, and Alman-Guan-Padaki, culminating in Alman and Li. We sharpen that framework in two ways. First, we replace the earlier \"wild\" rebalancing process by a tame, discretized process whose geometric-average behavior is governed by the quenched top Lyapunov exponent of a random matrix product. This allows us to invoke the convex-optimization upper bound of Gharavi and Anantharam. Second, for the degree bound we work explicitly with a cost landscape on the $(p,q)$-plane and show that different circuit families are dominant on different regions, so that the global maximum remains below $0.3199$.",
  "title": "Smaller Depth-2 Linear Circuits for Disjointness Matrices"
}