Mahajan, Meena ; Rao, B. V. Raghavendra ; Sreenivasaiah, Karteek (2016) Building Above Read-Once Polynomials: Identity Testing and Hardness of Representation Algorithmica, 76 (4). pp. 890-909. ISSN 0178-4617
Full text not available from this repository.
Official URL: http://doi.org/10.1007/s00453-015-0101-z
Related URL: http://dx.doi.org/10.1007/s00453-015-0101-z
Abstract
Polynomial Identity Testing (PIT) algorithms have focussed on polynomials computed either by small alternation-depth arithmetic circuits, or by read-restricted formulas. Read-once polynomials (ROPs) are computed by read-once formulas (ROFs) and are the simplest of read-restricted polynomials. Building structures above these, we show the following: (1) a deterministic polynomial-time non-black-box PIT algorithm for ∑(2)×∏×ROF. (2) Weak hardness of representation theorems for sums of powers of constant-free ROPs and for ROFs of the form ∑×∏×∑. (3) A partial characterization of multilinear monotone constant-free ROPs.
| Item Type: | Article |
|---|---|
| Source: | Copyright of this article belongs to Springer Nature Switzerland AG. |
| Keywords: | Polynomial Identity Testing; Algebraic algorithms; Arithmetic circuits |
| ID Code: | 128011 |
| Deposited On: | 14 Oct 2022 11:28 |
| Last Modified: | 14 Oct 2022 11:28 |
Repository Staff Only: item control page
