Meena Mahajan, Venkatesh Raman

In this paper we investigate the parametrized

complexity of the problems MaxSat and MaxCut using the

framework developed by Downey and Fellows.

Let $G$ be an arbitrary graph having $n$ vertices and $m$

edges, and let $f$ be an arbitrary CNF formula with $m$

clauses on $n$ variables. We improve ...
more >>>

Chiranjit Chakraborty, Rahul Santhanam

We define instance compressibility for parametric problems in PH and PSPACE. We observe that

the problem \Sigma_{i}CircuitSAT of deciding satisfiability of a quantified Boolean circuit with i-1 alternations of quantifiers starting with an existential uantifier is complete for parametric problems in \Sigma_{i}^{p} with respect to W-reductions, and that analogously ... more >>>

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