Stephen A. Bloch, Jonathan F. Buss, Judy Goldsmith

We define the sharply bounded hierarchy, SBHQL, a hierarchy of

classes within P, using quasilinear-time computation and

quantification over values of length log n. It generalizes the

limited nondeterminism hierarchy introduced by Buss and Goldsmith,

while retaining the invariance properties. The new hierarchy has

several alternative characterizations.

We define ... more >>>

Richard Beigel

<html>

Prior results show that most bounded query hierarchies cannot

contain finite gaps. For example, it is known that

<center>

P<sub>(<i>m</i>+1)-tt</sub><sup>SAT</sup> = P<sub><i>m</i>-tt</sub><sup>SAT</sup> implies P<sub>btt</sub><sup>SAT</sup> = P<sub><i>m</i>-tt</sub><sup>SAT</sup>

</center>

and for all sets <i>A</i>

<ul>

<li> FP<sub>(<i>m</i>+1)-tt</sub><sup><i>A</i></sup> = FP<sub><i>m</i>-tt</sub><sup><i>A</i></sup> implies FP<sub>btt</sub><sup><i>A</i></sup> = FP<sub><i>m</i>-tt</sub><sup><i>A</i></sup>

</li>

<li> P<sub>(<i>m</i>+1)-T</sub><sup><i>A</i></sup> = P<sub><i>m</i>-T</sub><sup><i>A</i></sup> implies P<sub>bT</sub><sup><i>A</i></sup> = ...
more >>>

Oliver Kullmann

A relativized hierarchy of conjunctive normal forms

is introduced, recognizable and SAT decidable in polynomial

time. The corresponding hardness parameter, the first level

of inclusion in the hierarchy, is studied in detail, admitting

several characterizations, e.g., using pebble games, the space

complexity of (relativized) tree-like ...
more >>>

Oliver Kullmann

A basic property of minimally unsatisfiable clause-sets F is that

c(F) >= n(F) + 1 holds, where c(F) is the number of clauses, and

n(F) the number of variables. Let MUSAT(k) be the class of minimally

unsatisfiable clause-sets F with c(F) <= n(F) + k.

Poly-time decision algorithms are known ... more >>>

Piotr Berman, Marek Karpinski

We give improved trade-off results on approximating general

minimum cost scheduling problems.

Paul Spirakis, haralampos tsaknakis

In this paper we propose a methodology for determining approximate Nash equilibria of non-cooperative bimatrix games and, based on that, we provide a polynomial time algorithm that computes $\frac{1}{3} + \frac{1}{p(n)} $ -approximate equilibria, where $p(n)$ is a polynomial controlled by our algorithm and proportional to its running time. The ... more >>>

Vikraman Arvind, Partha Mukhopadhyay

\begin{abstract}

Given a monomial ideal $I=\angle{m_1,m_2,\cdots,m_k}$ where $m_i$

are monomials and a polynomial $f$ as an arithmetic circuit the

\emph{Ideal Membership Problem } is to test if $f\in I$. We study

this problem and show the following results.

\begin{itemize}

\item[(a)] If the ideal $I=\angle{m_1,m_2,\cdots,m_k}$ for a

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

Vishwas Bhargava, GĂˇbor Ivanyos, Rajat Mittal, Nitin Saxena

Constructing $r$-th nonresidue over a finite field is a fundamental computational problem. A related problem is to construct an irreducible polynomial of degree $r^e$ (where $r$ is a prime) over a given finite field $\F_q$ of characteristic $p$ (equivalently, constructing the bigger field $\F_{q^{r^e}}$). Both these problems have famous randomized ... more >>>