Weizmann Logo
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style

Reports tagged with group algebra:
TR13-139 | 7th October 2013
Peter Floderus, Andrzej Lingas, Mia Persson, Dzmitry Sledneu

Detecting Monomials with $k$ Distinct Variables

We study the complexity of detecting monomials
with special properties in the sum-product
expansion of a polynomial represented by an arithmetic
circuit of size polynomial in the number of input
variables and using only multiplication and addition.
We focus on monomial properties expressed in terms
of the number of distinct ... more >>>

ISSN 1433-8092 | Imprint