All reports by Author Stefan S. Dantchev:

__
TR07-001
| 19th November 2006
__

Stefan S. Dantchev, Barnaby Martin, Stefan Szeider#### Parameterized Proof Complexity: a Complexity Gap for Parameterized Tree-like Resolution

Revisions: 1

__
TR00-017
| 3rd March 2000
__

Valentin E. Brimkov, Stefan S. Dantchev#### On the Algebraic Complexity of Integer Programming

__
TR98-015
| 16th January 1998
__

Valentin E. Brimkov, Stefan S. Dantchev#### Lower Bounds, "Pseudopolynomial" and Approximation Algorithms for the Knapsack Problem with Real Coefficients

Stefan S. Dantchev, Barnaby Martin, Stefan Szeider

We propose a proof-theoretic approach for gaining evidence that certain parameterized problems are not fixed-parameter tractable. We consider proofs that witness that a given propositional formula cannot be satisfied by a truth assignment that sets at most k variables to true, considering k as the parameter. One could separate the ... more >>>

Valentin E. Brimkov, Stefan S. Dantchev

In the framework of the Blum-Shub-Smale real number model \cite{BSS}, we study the {\em algebraic complexity} of the integer linear programming problem

(ILP$_{\bf R}$) : Given a matrix $A \in {\bf R}^{m \times n}$ and vectors

$b \in {\bf R}^m$, $d \in {\bf R}^n$, decide if there is $x ...
more >>>

Valentin E. Brimkov, Stefan S. Dantchev

In this paper we study the Boolean Knapsack problem (KP$_{{\bf R}}$)

$a^Tx=1$, $x \in \{0,1\}^n$ with real coefficients, in the framework

of the Blum-Shub-Smale real number computational model \cite{BSS}.

We obtain a new lower bound

$\Omega \left( n\log n\right) \cdot f(1/a_{\min})$ for the time

complexity ...
more >>>