Christoph Meinel, Stephan Waack

We prove that the modular communication complexity of the

undirected graph connectivity problem UCONN equals Theta(n),

in contrast to the well-known Theta(n*log n) bound in the

deterministic case, and to the Omega(n*loglog n) lower bound

in the nondeterministic case, recently proved by ...
more >>>

Lance Fortnow

We review the past ten years in computational complexity theory by

focusing on ten theorems that the author enjoyed the most. We use

each of the theorems as a springboard to discuss work done in

various areas of complexity theory.

Frederic Green

We say an integer polynomial $p$, on Boolean inputs, weakly

$m$-represents a Boolean function $f$ if $p$ is non-constant and is zero (mod

$m$), whenever $f$ is zero. In this paper we prove that if a polynomial

weakly $m$-represents the Mod$_q$ function on $n$ inputs, where $q$ and $m$

more >>>

Christoph Meinel, Stephan Waack

We investigate the probabilistic communication complexity

(more exactly, the majority communication complexity,)

of the graph accessibility problem GAP and

its counting versions MOD_k-GAP, k > 1.

Due to arguments concerning matrix variation ranks

and certain projection reductions, we prove

that, for any partition of the input variables,

more >>>

Uri Zwick, Michael S. Paterson

We study the complexity of finding the values and optimal strategies of

MEAN PAYOFF GAMES on graphs, a family of perfect information games

introduced by Ehrenfeucht and Mycielski and considered by Gurvich,

Karzanov and Khachiyan. We describe a pseudo-polynomial time algorithm

for the solution of such games, the decision ...
more >>>

Hans-Joerg Burtschick, Heribert Vollmer

We show that examinations of the expressive power of logical formulae

enriched by Lindstroem quantifiers over ordered finite structures

have a well-studied complexity-theoretic counterpart: the leaf

language approach to define complexity classes. Model classes of

formulae with Lindstroem quantifiers are nothing else than leaf

language definable sets. Along the ...
more >>>

Bernd Borchert, Antoni Lozano

This note connects two topics of Complexity Theory: The

topic of succinct circuit representations initiated by

Galperin and Wigderson and the topic of leaf languages

initiated by Bovet, Crescenzi, and Silvestri. It will be

shown for any language that its succinct version is

more >>>

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

Edoardo Amaldi, Viggo Kann

We investigate the computational complexity of two classes of

combinatorial optimization problems related to linear systems

and study the relationship between their approximability properties.

In the first class (MIN ULR) one wishes, given a possibly infeasible

system of linear relations, to find ...
more >>>

Yongge Wang

We show that the class of sets which can be polynomial

time truth table reduced to some $p$-superterse sets has

$p$-measure 0. Hence, no $P$-selective set is $\le_{tt}^p$-hard

for $E$. Also we give a partial affirmative answer to

the conjecture by Beigel, Kummer and ...
more >>>

Lane A. Hemaspaandra, Ashish Naik, Mitsunori Ogihara, Alan L. Selman

Is there an NP function that, when given a satisfiable formula

as input, outputs one satisfying assignment uniquely? That is, can a

nondeterministic function cull just one satisfying assignment from a

possibly exponentially large collection of assignments? We show that if

there is such a nondeterministic function, then the polynomial ...
more >>>

The computational power of formal models for

networks of spiking neurons is compared with

that of other neural network models based on

McCulloch Pitts neurons (i.e. threshold gates)

respectively sigmoidal gates. In particular it

is shown that networks of spiking neurons are

...
more >>>

Edmund Ihler

We show that a fully polynomial time approximation scheme given

for an optimization problem can always be simply modified to a

polynomial time algorithm solving the problem optimally if the

computation model is the deterministic Turing Machine or the

logarithmic cost RAM and ...
more >>>

Bernd Borchert, Lane A. Hemaspaandra, Jörg Rothe

We study EP, the subclass of NP consisting of those

languages accepted by NP machines that when they accept always have a

number of accepting paths that is a power of two. We show that the

negation equivalence problem for OBDDs (ordered binary decision

diagrams) ...
more >>>

Sanjeev Khanna, Madhu Sudan, David P. Williamson

In this paper we study the approximability of boolean constraint

satisfaction problems. A problem in this class consists of some

collection of ``constraints'' (i.e., functions

$f:\{0,1\}^k \rightarrow \{0,1\}$); an instance of a problem is a set

of constraints applied to specified subsets of $n$ boolean

variables. Schaefer earlier ...
more >>>

Sanjeev Khanna, Madhu Sudan, Luca Trevisan

This paper continues the work initiated by Creignou [Cre95] and

Khanna, Sudan and Williamson [KSW96] who classify maximization

problems derived from boolean constraint satisfaction. Here we

study the approximability of {\em minimization} problems derived

thence. A problem in this framework is characterized by a

collection F ...
more >>>

Marco Cesati, Luca Trevisan

A polynomial time approximation scheme (PTAS) for an optimization

problem $A$ is an algorithm that on input an instance of $A$ and

$\epsilon > 0$ finds a $(1+\epsilon)$-approximate solution in time

that is polynomial for each fixed $\epsilon$. Typical running times

are $n^{O(1/\epsilon)}$ or $2^{1/\epsilon^{O(1)}} ...
more >>>

Marek Karpinski, Alexander Zelikovsky

We study dense instances of several covering problems. An instance of

the set cover problem with $m$ sets is dense if there is $\epsilon>0$

such that any element belongs to at least $\epsilon m$ sets. We show

that the dense set cover problem can be approximated with ...
more >>>

Marco Cesati, Miriam Di Ianni

We consider the framework of Parameterized Complexity, and we

investigate the issue of which problems do admit efficient fixed

parameter parallel algorithms by introducing two different

degrees of efficiently parallelizable parameterized problems, PNC

and FPP. We sketch both some FPP-algorithms solving natural

parameterized problems and ...
more >>>

Jonathan F. Buss, Gudmund Skovbjerg Frandsen, Jeffrey O. Shallit

We consider the computational complexity of some problems

dealing with matrix rank. Let E,S be subsets of a

commutative ring R. Let x_1, x_2, ..., x_t be variables.

Given a matrix M = M(x_1, x_2, ..., x_t) with entries

chosen from E union {x_1, x_2, ..., ...
more >>>

Marek Karpinski

We survey recent results on the existence of polynomial time

approximation schemes for some dense instances of NP-hard

optimization problems. We indicate further some inherent limits

for existence of such schemes for some other dense instances of

the optimization problems.

Gunter Blache, Marek Karpinski, Juergen Wirtgen

The bandwidth problem is the problem of enumerating

the vertices of a given graph $G$ such that the maximum difference

between the numbers of adjacent vertices is minimal. The problem

has a long history and a number of applications.

There was not ...
more >>>

Steffen Reith, Heribert Vollmer

We consider the problems of finding the lexicographically

minimal (or maximal) satisfying assignment of propositional

formulae for different restricted formula classes. It turns

out that for each class from our framework, the above problem

is either polynomial time solvable or complete for ...
more >>>

Piotr Berman, Marek Karpinski

We prove a number of improved inaproximability results,

including the best up to date explicit approximation

thresholds for MIS problem of bounded degree, bounded

occurrences MAX-2SAT, and bounded degree Node Cover. We

prove also for the first time inapproximability of the

problem of Sorting by ...
more >>>

Marek Karpinski

We survey some upper and lower bounds established recently on

the sizes of randomized branching programs computing explicit

boolean functions. In particular, we display boolean

functions on which randomized read-once ordered branching

programs are exponentially more powerful than deterministic

or nondeterministic read-$k$-times branching programs for ...
more >>>

H. Buhrman, Dieter van Melkebeek, K.W. Regan, Martin Strauss, D. Sivakumar

We introduce "resource-bounded betting games", and propose

a generalization of Lutz's resource-bounded measure in which the choice

of next string to bet on is fully adaptive. Lutz's martingales are

equivalent to betting games constrained to bet on strings in lexicographic

order. We show that if strong pseudo-random number generators exist,

more >>>

C. Lautemann, Pierre McKenzie, T. Schwentick, H. Vollmer

Building upon the known generalized-quantifier-based first-order

characterization of LOGCFL, we lay the groundwork for a deeper

investigation. Specifically, we examine subclasses of LOGCFL arising

from varying the arity and nesting of groupoidal quantifiers. Our

work extends the elaborate theory relating monoidal quantifiers to

NC^1 and its subclasses. In the ...
more >>>

Wenceslas Fernandez de la Vega, Marek Karpinski

We give the first polynomial time approximability characterization

of dense weighted instances of MAX-CUT, and some other dense

weighted NP-hard problems in terms of their empirical weight

distributions. This gives also the first almost sharp

characterization of inapproximability of unweighted 0,1

MAX-BISECTION instances ...
more >>>

Paul Beame

Proof complexity, the study of the lengths of proofs in

propositional logic, is an area of study that is fundamentally connected

both to major open questions of computational complexity theory and

to practical properties of automated theorem provers. In the last

decade, there have been a number of significant advances ...
more >>>

Michael Schmitt

We calculate lower bounds on the size of sigmoidal neural networks

that approximate continuous functions. In particular, we show that

for the approximation of polynomials the network size has to grow

as $\Omega((\log k)^{1/4})$ where $k$ is the degree of the polynomials.

This bound is ...
more >>>

Amitabha Roy, Christopher Wilson

A {\em supermodel} is a satisfying assignment of a boolean formula

for which any small alteration, such as a single bit flip, can be

repaired by another small alteration, yielding a nearby

satisfying assignment. We study computational problems associated

with super models and some generalizations thereof. For general

formulas, ...
more >>>

Beate Bollig

Branching programs are a well established computation model for

Boolean functions, especially read-once branching programs have

been studied intensively.

In this paper the expressive power of nondeterministic read-once

branching programs, i.e., the class of functions

representable in polynomial size, is investigated.

For that reason two restricted models of nondeterministic read-once

more >>>

Prahladh Harsha, Madhu Sudan

Most known constructions of probabilistically checkable proofs (PCPs)

either blow up the proof size by a large polynomial, or have a high

(though constant) query complexity. In this paper we give a

transformation with slightly-super-cubic blowup in proof size, with a

low query complexity. Specifically, the verifier probes the proof ...
more >>>

Andreas Klein, Martin Kutrib

Deterministic k-tape and multitape Turing machines with one-way,

two-way and without a separated input tape are considered. We

investigate the classes of languages acceptable by such devices with

time bounds of the form n+r(n) where r in o(n) is a sublinear

function. It is shown that there ...
more >>>

Shin Aida, Rainer Schuler, Tatsuie Tsukiji, Osamu Watanabe

In this paper we separate many-one reducibility from truth-table

reducibility for distributional problems in DistNP under the

hypothesis that P neq NP. As a first example we consider the

3-Satisfiability problem (3SAT) with two different distributions

on 3CNF formulas. We show that 3SAT using a version of the

standard distribution ...
more >>>

Pavol Duris, Juraj Hromkovic, Stasys Jukna, Martin Sauerhoff, Georg Schnitger

We study k-partition communication protocols, an extension

of the standard two-party best-partition model to k input partitions.

The main results are as follows.

1. A strong explicit hierarchy on the degree of

non-obliviousness is established by proving that,

using k+1 partitions instead of k may decrease

the communication complexity from ...
more >>>

Beate Bollig, Philipp Woelfel, Stephan Waack

Branching programs are a well-established computation model

for Boolean functions, especially read-once branching programs

have been studied intensively. Exponential lower bounds for

deterministic and nondeterministic read-once branching programs

are known for a long time. On the other hand, the problem of

proving superpolynomial lower bounds ...
more >>>

Robert Albin Legenstein

In this article we consider a basic problem in the layout of

VLSI-circuits, the channel-routing problem in the knock-knee mode.

We show that knock-knee channel routing with 3-terminal nets is

NP-complete and thereby settling a problem that was open for more

than a decade. In 1987, Sarrafzadeh showed that knock-knee ...
more >>>

Dima Grigoriev, Edward Hirsch, Dmitrii V. Pasechnik

It is a known approach to translate propositional formulas into

systems of polynomial inequalities and to consider proof systems

for the latter ones. The well-studied proof systems of this kind

are the Cutting Planes proof system (CP) utilizing linear

inequalities and the Lovasz-Schrijver calculi (LS) utilizing

quadratic ...
more >>>

Klaus Weihrauch

We introduce a new Turing machine based concept of time complexity for functions on computable metric spaces. It generalizes the ordinary complexity of word functions and the complexity of real functions studied by Ko \cite{Ko91} et al. Although this definition of ${\rm TIME}$ as the maximum of a generally infinite ... more >>>

Tobias Riege, Jörg Rothe

We prove that the exact versions of the domatic number problem are complete

for the levels of the boolean hierarchy over NP. The domatic number

problem, which arises in the area of computer networks, is the problem of

partitioning a given graph into a maximum number ...
more >>>

Harumichi Nishimura, Tomoyuki Yamakami

Advice is supplementary information that enhances the computational

power of an underlying computation. This paper focuses on advice that

is given in the form of a pure quantum state. The notion of advised

quantum computation has a direct connection to non-uniform quantum

circuits and tally languages. The paper examines the ...
more >>>

Ran Raz

An arithmetic formula is multi-linear if the polynomial computed

by each of its sub-formulas is multi-linear. We prove that any

multi-linear arithmetic formula for the permanent or the

determinant of an $n \times n$ matrix is of size super-polynomial

in $n$.

Matthias Homeister

We prove the first lower bound for restricted read-once parity branching

programs with unlimited parity nondeterminism where for each input the

variables may be tested according to several orderings.

Proving a superpolynomial lower bound for read-once parity branching

programs is still a challenging open problem. The following variant ...
more >>>

John Hitchcock, Maria Lopez-Valdes, Elvira Mayordomo

Scaled dimension has been introduced by Hitchcock et al (2003) in order to quantitatively distinguish among classes such as SIZE(2^{a n}) and SIZE(2^{n^{a}}) that have trivial dimension and measure in ESPACE.

more >>>Ran Raz

An arithmetic circuit or formula is multilinear if the polynomial

computed at each of its wires is multilinear.

We give an explicit example for a polynomial $f(x_1,...,x_n)$,

with coefficients in $\{0,1\}$, such that over any field:

1) $f$ can be computed by a polynomial-size multilinear circuit

of depth $O(\log^2 ...
more >>>

Xiaoyang Gu

In this paper, we use resource-bounded dimension theory to investigate polynomial size circuits. We show that for every $i\geq 0$, $\Ppoly$ has $i$th order scaled $\pthree$-strong dimension $0$. We also show that $\Ppoly^\io$ has $\pthree$-dimension $1/2$, $\pthree$-strong dimension $1$. Our results improve previous measure results of Lutz (1992) and dimension ... more >>>

Kousha Etessami, Andreas Lochbihler

Game theory has been used for a long time to study phenomena in evolutionary biology, beginning systematically with the seminal work of John Maynard Smith. A central concept in this connection has been the notion of an evolutionarily stable strategy (ESS) in a symmetric two-player strategic form game. A regular ... more >>>

Beatrice List, Markus Maucher, Uwe Schöning, Rainer Schuler

The worst-case complexity of an implementation of Quicksort depends

on the random number generator that is used to select the pivot

elements. In this paper we estimate the expected number of

comparisons of Quicksort as a function in the entropy of the random

source. We give upper and lower bounds ...
more >>>

Piotr Berman, Marek Karpinski, Alexander D. Scott, Alexander D. Scott

We prove results on the computational complexity of instances of 3SAT in which every variable occurs 3 or 4 times.

more >>>Uriel Feige, Daniel Reichman

Max-Satisfy is the problem of finding an assignment that satisfies

the maximum number of equations in a system of linear equations

over $\mathbb{Q}$. We prove that unless NP$\subseteq $BPP there is no

polynomial time algorithm for the problem achieving an

approximation ratio of $1/n^{1-\epsilon}$, where $n$ is the number

of ...
more >>>

Neeraj Kayal

Let $\mathbb{F}_q$ be a finite field and $f(x) \in \mathbb{F}_q(x)$ be a rational function over $\mathbb{F}_q$.

The decision problem {\bf PermFunction} consists of deciding whether $f(x)$ induces a permutation on

the elements of $\mathbb{F}_q$. That is, we want to decide whether the corresponding map

$f : \mathbb{F}_q ...
more >>>

Olivier Powell

We constructively prove the existence of almost complete problems under logspace manyone reduction for some small complexity classes by exhibiting a parametrizable construction which yields, when appropriately setting the parameters, an almost complete problem for PSPACE, the class of space efficiently decidable problems, and for SUBEXP, the class of problems ... more >>>

Michael Bauland, Elmar Böhler, Nadia Creignou, Steffen Reith, Henning Schnoor, Heribert Vollmer

We consider constraint satisfaction problems parameterized by the set of allowed constraint predicates. We examine the complexity of quantified constraint satisfaction problems with a bounded number of quantifier alternations and the complexity of the associated counting problems. We obtain classification results that completely solve the Boolean case, and we show ... more >>>

Bruno Codenotti, Amin Saberi, Kasturi Varadarajan, Yinyu Ye

We give a reduction from any two-player game to a special case of

the Leontief exchange economy, with the property that the Nash equilibria of the game and the

equilibria of the market are in one-to-one correspondence.

Our reduction exposes a potential hurdle inherent in solving certain

families of market ...
more >>>

Li-Sha Huang, Xiaotie Deng

We consider the computational complexity of the market equilibrium

problem by exploring the structural properties of the Leontief

exchange economy. We prove that, for economies guaranteed to have

a market equilibrium, finding one with maximum social welfare or

maximum individual welfare is NP-hard. In addition, we prove that

counting the ...
more >>>

Kooshiar Azimian, Javad Mohajeri, Mahmoud Salmasizadeh, Siamak Fayyaz

In this paper, firstly we propose two new concepts concerning the notion of key escrow encryption schemes: provable partiality and independency. Roughly speaking we say that a scheme has provable partiality if existing polynomial time algorithm for recovering the secret knowing escrowed information implies a polynomial time algorithm that can ... more >>>

Xiaoyang Gu, Jack H. Lutz, Philippe Moser

The base-$k$ {\em Copeland-Erd\"os sequence} given by an infinite

set $A$ of positive integers is the infinite

sequence $\CE_k(A)$ formed by concatenating the base-$k$

representations of the elements of $A$ in numerical

order. This paper concerns the following four

quantities.

\begin{enumerate}[$\bullet$]

\item

The {\em finite-state dimension} $\dimfs (\CE_k(A))$,

a finite-state ...
more >>>

Paul Goldberg, Christos H. Papadimitriou

We address the fundamental question of whether the Nash equilibria of

a game can be computed in polynomial time. We describe certain

efficient reductions between this problem for

normal form games with a fixed number of players

and graphical games with fixed degree. Our main result is that ...
more >>>

Bernhard Fuchs

We investigate the computational hardness of the {\sc Connectivity},

the {\sc Strong Connectivity} and the {\sc Broadcast} type of Range

Assignment Problems in $\R^2$ and $\R^3$.

We present new reductions for the {\sc Connectivity} problem, which

are easily adapted to suit the other two problems. All reductions

are considerably simpler ...
more >>>

Parikshit Gopalan

Explicit construction of Ramsey graphs or graphs with no large clique or independent set has remained a challenging open problem for a long time. While Erdos's probabilistic argument shows the existence of graphs on 2^n vertices with no clique or independent set of size 2n, the best known explicit constructions ... more >>>

Christian Glaßer, Stephen Travers

We propose the e-model for leaf languages which generalizes the known balanced and unbalanced concepts. Inspired by the neutral behavior of rejecting paths of NP machines, we allow transducers to output empty words.

The paper explains several advantages of the new model. A central aspect is that it allows us ... more >>>

Xiaoyang Gu, Jack H. Lutz

We use derandomization to show that sequences of positive $\pspace$-dimension -- in fact, even positive $\Delta^\p_k$-dimension

for suitable $k$ -- have, for many purposes, the full power of random oracles. For example, we show that, if $S$ is any binary sequence whose $\Delta^p_3$-dimension is positive, then $\BPP\subseteq \P^S$ and, moreover, ...
more >>>

Argimiro Arratia, Carlos E. Ortiz

We formulate a formal syntax of approximate formulas for the logic with counting

quantifiers, $\mathcal{SOLP}$, studied by us in \cite{aaco06}, where we showed the

following facts:

$(i)$ In the presence of a built--in (linear) order, $\mathcal{SOLP}$ can

describe {\bf NP}--complete problems and fragments of it capture classes like

{\bf P} ...
more >>>

Hermann Gruber, Markus Holzer

We investigate the following lower bound methods for regular

languages: The fooling set technique, the extended fooling set

technique, and the biclique edge cover technique. It is shown that

the maximal attainable lower bound for each of the above mentioned

techniques can be algorithmically deduced from ...
more >>>

Wenbin Chen, Jiangtao Meng

We show that the Closest Vector

Problem with Preprocessing over infty Norm

is NP-hard to approximate to within a factor of $(\log

n)^{1/2-\epsilon}$. The result is the same as Regev and Rosen' result, but our proof methods are different from theirs. Their

reductions are based on norm embeddings. However, ...
more >>>

Ran Raz, Amir Shpilka, Amir Yehudayoff

We construct an explicit polynomial $f(x_1,...,x_n)$, with

coefficients in ${0,1}$, such that the size of any syntactically

multilinear arithmetic circuit computing $f$ is at least

$\Omega( n^{4/3} / log^2(n) )$. The lower bound holds over any field.

Felix Brandt, Felix Fischer, Markus Holzer

Strategic games may exhibit symmetries in a variety of ways. A common aspect of symmetry, enabling the compact representation of games even when the number of players is unbounded, is that players cannot (or need not) distinguish between the other players. We define four classes of symmetric games by considering ... more >>>

Alex Hertel, Alasdair Urquhart

The importance of {\em width} as a resource in resolution theorem proving

has been emphasized in work of Ben-Sasson and Wigderson. Their results show that lower

bounds on the size of resolution refutations can be proved in a uniform manner by

demonstrating lower bounds on the width ...
more >>>

Michael Bauland, Thomas Schneider, Henning Schnoor, Ilka Schnoor, Heribert Vollmer

In a seminal paper from 1985, Sistla and Clarke showed

that satisfiability for Linear Temporal Logic (LTL) is either

NP-complete or PSPACE-complete, depending on the set of temporal

operators used

If, in contrast, the set of propositional operators is restricted, the

complexity may ...
more >>>

Heribert Vollmer, Michael Bauland, Elmar Böhler, Nadia Creignou, Steffen Reith, Henning Schnoor

In this paper we will look at restricted versions of the evaluation problem, the model checking problem, the equivalence problem, and the counting problem for quantified propositional formulas, both with and without bound on the number of quantifier alternations. The restrictions are such that we consider formulas in conjunctive normal-form ... more >>>

Heribert Vollmer

We study the complexity of the following algorithmic problem: Given a Boolean function $f$ and a finite set of Boolean functions $B$, decide if there is a circuit with basis $B$ that computes $f$. We show that if both $f$ and all functions in $B$ are given by their truth-table, ... more >>>

Beate Bollig, Niko Range, Ingo Wegener

Ordered binary decision diagrams (OBDDs) are nowadays the most common

dynamic data structure or representation type for Boolean functions.

Among the many areas of application are verification, model checking,

computer aided design, relational algebra, and symbolic graph algorithms.

Although many even exponential lower bounds on the OBDD size of Boolean ...
more >>>

Brendan Juba, Madhu Sudan

Is it possible for two intelligent beings to communicate meaningfully, without any common language or background? This question has interest on its own, but is especially relevant in the context of modern computational infrastructures where an increase in the diversity of computers is making the task of inter-computer interaction increasingly ... more >>>

Beate Bollig

Branching programs are computation models

measuring the space of (Turing machine) computations.

Read-once branching programs (BP1s) are the

most general model where each graph-theoretical path is the computation

path for some input. Exponential lower bounds on the size of read-once

branching programs are known since a long time. Nevertheless, there ...
more >>>

Jeffrey C. Jackson, Homin Lee, Rocco Servedio, Andrew Wan

We give an algorithm that with high probability properly learns random monotone t(n)-term

DNF under the uniform distribution on the Boolean cube {0, 1}^n. For any polynomially bounded function t(n) <= poly(n) the algorithm runs in time poly(n, 1/eps) and with high probability outputs an eps accurate monotone DNF ...
more >>>

Felix Brandt, Felix Fischer, Markus Holzer

We study graphical games where the payoff function of each player satisfies one of four types of symmetries in the actions of his neighbors. We establish that deciding the existence of a pure Nash equilibrium is NP-hard in graphical games with each of the four types of symmetry. Using a ... more >>>

Michael Bauland, Martin Mundhenk, Thomas Schneider, Henning Schnoor, Ilka Schnoor, Heribert Vollmer

In a seminal paper from 1985, Sistla and Clarke showed

that the model-checking problem for Linear Temporal Logic (LTL) is either NP-complete

or PSPACE-complete, depending on the set of temporal operators used.

If, in contrast, the set of propositional operators is restricted, the complexity may decrease.

...
more >>>

Christian Glaßer, Christian Reitwießner, Victor Selivanov

We study the shrinking and separation properties (two notions well-known in descriptive set theory) for NP and coNP and show that under reasonable complexity-theoretic assumptions, both properties do not hold for NP and the shrinking property does not hold for coNP. In particular we obtain the following results.

1. NP ... more >>>

James I. Lathrop, Jack H. Lutz, Matthew J. Patitz, Scott M. Summers

This paper explores the impact of geometry on computability =

and complexity in

Winfree's model of nanoscale self-assembly. We work in the =

two-dimensional

tile assembly model, i.e., in the discrete Euclidean plane Z x Z. Our =

first

main theorem says that there is a roughly quadratic function f ...
more >>>

Felix Brandt, Felix Fischer, Markus Holzer

We study computational problems that arise in the context of iterated dominance in anonymous games, and show that deciding whether a game can be solved by means of iterated weak dominance is NP-hard for anonymous games with three actions. For the case of two actions, this problem can be reformulated ... more >>>

Vikraman Arvind, Partha Mukhopadhyay

Motivated by the quantum algorithm in \cite{MN05} for testing

commutativity of black-box groups, we study the following problem:

Given a black-box finite ring $R=\angle{r_1,\cdots,r_k}$ where

$\{r_1,r_2,\cdots,r_k\}$ is an additive generating set for $R$ and a

multilinear polynomial $f(x_1,\cdots,x_m)$ over $R$ also accessed as

a ...
more >>>

Brendan Juba, Madhu Sudan

We continue the investigation of the task of meaningful communication among intelligent entities (players, agents) without any prior common language. Our generic thesis is that such communication is feasible provided the goals of the communicating players are verifiable and compatible. In a previous work we gave supporting evidence for this ... more >>>

Jack H. Lutz, Elvira Mayordomo

This paper investigates the existence of inseparable disjoint

pairs of NP languages and related strong hypotheses in

computational complexity. Our main theorem says that, if NP does

not have measure 0 in EXP, then there exist disjoint pairs of NP

languages that are P-inseparable, in fact TIME(2^(n^k)-inseparable.

We also relate ...
more >>>

Iftach Haitner, Omer Reingold, Salil Vadhan, Hoeteck Wee

We put forth a new computational notion of entropy, which measures the

(in)feasibility of sampling high entropy strings that are consistent

with a given protocol. Specifically, we say that the i'th round of a

protocol (A, B) has _accessible entropy_ at most k, if no

polynomial-time strategy A^* can generate ...
more >>>

Yonatan Bilu, Nathan Linial

We introduce the notion of a stable instance for a discrete

optimization problem, and argue that in many practical situations

only sufficiently stable instances are of interest. The question

then arises whether stable instances of NP--hard problems are

easier to solve. In particular, whether there exist algorithms

that solve correctly ...
more >>>

Christian Glaßer, Christian Reitwießner, Maximilian Witek

We improve and derandomize the best known approximation algorithm for the two-criteria metric traveling salesman problem (2-TSP). More precisely, we construct a deterministic 2-approximation which answers an open question by Manthey.

Moreover, we show that 2-TSP is randomized $(3/2+\epsilon ,2)$-approximable, and we give the first randomized approximations for the two-criteria ... more >>>

Chongwon Cho, Chen-Kuei Lee, Rafail Ostrovsky

It is well known that proving the security of a key agreement protocol (even in a special case where the protocol transcript looks random to an outside observer) is at least as difficult as proving $P \not = NP$. Another (seemingly unrelated) statement in cryptography is the existence of two ... more >>>

Zeev Dvir, Dan Gutfreund, Guy Rothblum, Salil Vadhan

We investigate the complexity of the following computational problem:

Polynomial Entropy Approximation (PEA):

Given a low-degree polynomial mapping

$p : F^n\rightarrow F^m$, where $F$ is a finite field, approximate the output entropy

$H(p(U_n))$, where $U_n$ is the uniform distribution on $F^n$ and $H$ may be any of several entropy measures.

Harry Buhrman, Leen Torenvliet, Falk Unger, Nikolay Vereshchagin

It is well-known that the class of sets that can be computed by polynomial size circuits is equal to the class of sets that are polynomial time reducible to a sparse set. It is widely believed, but unfortunately up to now unproven, that there are sets in $EXP^{NP}$, or even ... more >>>

Marcel R. Ackermann, Johannes Blömer, Christoph Scholz

We prove the computational hardness of three k-clustering problems using an (almost) arbitrary Bregman divergence as dissimilarity measure: (a) The Bregman k-center problem, where the objective is to find a set of centers that minimizes the maximum dissimilarity of any input point towards its closest center, and (b) the Bregman ... more >>>

Yang Li

In the paper, we introduce the concept of monotone rank, and using it as a powerful tool, we obtain several important and strong separation results in computational complexity.

\begin{itemize}

\item We show a super-exponential separation between monotone and non-monotone computation in the non-commutative model, and thus give the answer to ... more >>>

Salil Vadhan, Colin Jia Zheng

We provide a characterization of pseudoentropy in terms of hardness of sampling: Let $(X,B)$ be jointly distributed random variables such that $B$ takes values in a polynomial-sized set. We show that $B$ is computationally indistinguishable from a random variable of higher Shannon entropy given $X$ if and only if there ... more >>>

Prabhu Manyem, Julien Ugon

We survey research that studies the connection between the computational complexity

of optimization problems on the one hand, and the duality gap between the primal and

dual optimization problems on the other. To our knowledge, this is the first survey that

connects the two very important areas. We further look ...
more >>>

Xiaohui Bei, Ning Chen, Shengyu Zhang

Motivated by certain applications from physics, biochemistry, economics, and computer science in which the objects under investigation are unknown or not directly accessible because of various limitations, we propose a trial-and-error model to examine search problems with unknown inputs. Given a search problem with a hidden input, we are asked ... 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 >>>

Andrzej Dudek , Marek Karpinski, Andrzej Rucinski, Edyta Szymanska

We design a fully polynomial time approximation scheme (FPTAS) for counting the number of matchings (packings) in arbitrary 3-uniform hypergraphs of maximum degree three, referred to as $(3,3)$-hypergraphs. It is the first polynomial time approximation scheme for that problem, which includes also, as a special case, the 3D Matching counting ... more >>>

Andris Ambainis, Jevgenijs Vihrovs

We study the structure of sets $S\subseteq\{0, 1\}^n$ with small sensitivity. The well-known Simon's lemma says that any $S\subseteq\{0, 1\}^n$ of sensitivity $s$ must be of size at least $2^{n-s}$. This result has been useful for proving lower bounds on sensitivity of Boolean functions, with applications to the theory of ... more >>>

Rahul Mehta

We prove that a variant of 2048, a popular online puzzle game, is PSPACE-Complete. Our hardness result

holds for a version of the problem where the player has oracle access to the computer player's moves.

Specifically, we show that for an $n \times n$ game board $G$, computing a

more >>>

Beate Bollig

Ordered binary decision diagrams (OBDDs) are a popular data structure for Boolean functions.

Some applications work with a restricted variant called complete OBDDs

which is strongly related to nonuniform deterministic finite automata.

One of its complexity measures is the width which has been investigated

in several areas in computer science ...
more >>>

Stephen A. Fenner, Daniel Grier, Jochen Messner, Luke Schaeffer, Thomas Thierauf

A black-white combinatorial game is a two-person game in which the pieces are colored either black or white. The players alternate moving or taking elements of a specific color designated to them before the game begins. A player loses the game if there is no legal move available for his ... more >>>

Mahdi Cheraghchi, Piotr Indyk

For every fixed constant $\alpha > 0$, we design an algorithm for computing the $k$-sparse Walsh-Hadamard transform of an $N$-dimensional vector $x \in \mathbb{R}^N$ in time $k^{1+\alpha} (\log N)^{O(1)}$. Specifically, the algorithm is given query access to $x$ and computes a $k$-sparse $\tilde{x} \in \mathbb{R}^N$ satisfying $\|\tilde{x} - \hat{x}\|_1 \leq ... more >>>

Marco L. Carmosino, Jiawei Gao, Russell Impagliazzo, Ivan Mikhailin, Ramamohan Paturi, Stefan Schneider

We introduce the Nondeterministic Strong Exponential Time Hypothesis

(NSETH) as a natural extension of the Strong Exponential Time

Hypothesis (SETH). We show that both refuting and proving

NSETH would have interesting consequences.

In particular we show that disproving NSETH would ...
more >>>

Titus Dose

We study the computational complexity of constraint satisfaction problems that are based on integer expressions and algebraic circuits. On input of a finite set of variables and a finite set of constraints the question is whether the variables can be mapped onto finite subsets of natural numbers (resp., finite intervals ... more >>>

Balagopal Komarath, Jayalal Sarma, Saurabh Sawlani

The reversible pebble game is a combinatorial game played on rooted DAGs. This game was introduced by Bennett (1989) motivated by applications in designing space efficient reversible algorithms. Recently, Chan (2013) showed that the reversible pebble game number of any DAG is the same as its Dymond-Tompa pebble number and ... more >>>

Michael Rudow

This paper shows that the Discrete Logarithm Problem is in ZPP^(MCSP) (where MCSP is the Minimum Circuit Size Problem). This result improves the previous bound that the Discrete Logarithm Problem is in BPP^(MCSP) Allender et al. (2006). In doing so, this paper helps classify the relative difficulty of the Minimum ... more >>>

C Ramya, Raghavendra Rao B V

An n-variate Vandermonde polynomial is the determinant of the n × n matrix where the ith column is the vector (1, x_i , x_i^2 , . . . , x_i^{n-1})^T. Vandermonde polynomials play a crucial role in the in the theory of alternating polynomials and occur in Lagrangian polynomial interpolation ... more >>>