Weizmann Logo
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style

Reports tagged with Parametrized Complexity:
TR97-033 | 1st August 1997
Meena Mahajan, Venkatesh Raman

Parametrizing Above Guaranteed Values: MaxSat and MaxCut

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

TR12-077 | 10th June 2012
Chiranjit Chakraborty, Rahul Santhanam

Instance Compression for the Polynomial Hierarchy and Beyond

Comments: 2

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

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