{
  "$type": "site.standard.document",
  "bskyPostRef": {
    "cid": "bafyreigkykg7hmaklgbsyejlf6ho3fmkcynvecjgi7uugb3ve52z26fe4u",
    "uri": "at://did:plc:4rgrdigiftglskeax4wvmsev/app.bsky.feed.post/3mluzoi7ntrm2"
  },
  "path": "/report/2026/076",
  "publishedAt": "2026-05-15T03:36:58.000Z",
  "site": "https://eccc.weizmann.ac.il",
  "textContent": "We present the first algorithms for polynomial identity testing (PIT) of read-$4$ arithmetic formulas in the non-multilinear setting. Specifically, we give a polynomial-time PIT algorithm in the whitebox model and a quasi-polynomial-time algorithm in the blackbox model. Since our techniques are based on proving hardness of representation results, we extend our algorithms to orbits of read-$4$ formulas under the action of the affine linear group. Prior to our work, no subexponential white- or blackbox algorithms were known for this class of formulas. All our results hold over any field $\\mathbb{F}$ with $\\text{char}(\\mathbb{F}) = 0$ or $\\text{char}(\\mathbb{F}) \\ge 5$. Prior work addressed only restricted cases. Anderson, van Melkebeek, and Volkovich (Computational Complexity, 2015) studied multilinear read-$k$ formulas, giving a polynomial-time whitebox PIT algorithm and a quasi-polynomial-time blackbox algorithm. Without the multilinearity restriction, Mahajan, Rao, and Sreenivasaiah (TCS, 2014) gave polynomial-time whitebox algorithms for read-$2$ and read-$3$ formulas, Prakriya (Doctoral Thesis, 2019) obtained quasi-polynomial-time blackbox PIT algorithm for both read-$2$ and read-$3$ formulas. Independently, Shamir (Master's Thesis, 2022) obtained a quasi-polynomial-time blackbox PIT algorithm for read-$2$ formulas. For bounded-depth read-$k$ formulas, Agrawal, Saha, Saptharishi, and Saxena (SICOMP, 2016) obtained a polynomial-time blackbox algorithm in the non-multilinear case. The running time of their algorithm is $n^{k^{2^\\Delta}}$ for read-$k$, depth-$\\Delta$ formulas, and hence it is applicable only to constant depth. Partial derivatives are a central tool in the study of deterministic PIT for bounded-read formulas. However, for non-multilinear R$k$Fs, differentiation may increase the number of reads. To address this, we develop new structural results that ensure ``nice behavior'' of derivatives. Specifically, we introduce a new Fragmentation Lemma that reduces the PIT problem for general R$k$Fs to simpler models via differentiation. In addition, we define the notion of dominating degree patterns and show that, in certain cases, taking partial derivatives with respect to these patterns preserves the read count.",
  "title": "TR26-076 |  Polynomial Identity Testing for Read-4 Arithmetic Formulas | \n\n\tNimrod Kaplan, \n\n\tAmir Shpilka"
}