All reports by Author Dzmitry Sledneu:

__
TR13-139
| 7th October 2013
__

Peter Floderus, Andrzej Lingas, Mia Persson, Dzmitry Sledneu#### Detecting Monomials with $k$ Distinct Variables

__
TR12-176
| 14th December 2012
__

Marek Karpinski, Andrzej Lingas, Dzmitry Sledneu#### Optimal Cuts and Partitions in Tree Metrics in Polynomial Time

Peter Floderus, Andrzej Lingas, Mia Persson, Dzmitry Sledneu

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 >>>

Marek Karpinski, Andrzej Lingas, Dzmitry Sledneu

We present a polynomial time dynamic programming algorithm for optimal partitions in the shortest path metric induced by a tree. This resolves, among other things, the exact complexity status of the optimal partition problems in one dimensional geometric metric settings. Our method of solution could be also of independent interest ... more >>>