Name
Title | ||
|---|---|---|
Building above Read-once Polynomials: Identity Testing and Hardness of Representation. |
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 $$sum ^{(2)}times prod times mathsf{ROF}$$ź(2)ן×ROF. (2) Weak hardness of representation theorems for sums of powers of constant-free ROPs and for $$mathsf{ROF}$$ROFs of the form $$sum times prod times sum $$ź×ź×ź. (3) A partial characterization of multilinear monotone constant-free ROPs. |
Year | DOI | Venue |
|---|---|---|
2014 | 10.1007/s00453-015-0101-z | Electronic Colloquium on Computational Complexity |
Keywords | Field | DocType |
Polynomial Identity Testing,Algebraic algorithms,Arithmetic circuits | Discrete mathematics,Arithmetic circuits,Polynomial identity testing,Combinatorics,Algebra,Polynomial,Identity testing,Sums of powers,Mathematics | Conference |
Volume | Issue | ISSN |
22 | 4 | 1432-0541 |
Citations | PageRank | References |
3 | 0.38 | 14 |
Authors | ||
3 | ||
Name | Order | Citations | PageRank |
|---|---|---|---|
| Meena Mahajan | 1 | 688 | 56.90 |
| B. V. Raghavendra Rao | 2 | 53 | 13.86 |
| Karteek Sreenivasaiah | 3 | 13 | 5.30 |