ALBERT — All Library Books, journals and Electronic Records Telegrafenberg

Hits per page

hit 1 - 1 | 1 hit

Select All Export

Unknown

Building Above Read-Once Polynomials: Identity Testing and Hardness of Representation (2015)

Springer

In: Algorithmica

add to mindlist on the mindlist

Details

Publication Date: 2015-12-25

Description: 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) Weak hardness of representation theorems for sums of powers of constant-free ROP s and for \(\mathsf{ROF}\) s of the form \(\sum \times \prod \times \sum \) . (3) A partial characterization of multilinear monotone constant-free ROPs.

Print ISSN: 0178-4617

Electronic ISSN: 1432-0541

Topics: Computer Science , Mathematics

Published by Springer

	Location	Call Number	Expected	Availability

Others were also interested in ...

PAPER CURRENT

S·F·X

Fulltext

hit 1 - 1 | 1 hit