U. Faigle, W. Kern, M. Streng

We show that, for fixed dimension $n$, the approximation of

inner and outer $j$-radii of polytopes in ${\Re}^n$, endowed

with the Euclidean norm, is polynomial.

Joe Kilian, Erez Petrank

We consider noninteractive zero-knowledge proofs in the shared random

string model proposed by Blum, Feldman and Micali \cite{bfm}. Until

recently there was a sizable polynomial gap between the most

efficient noninteractive proofs for {\sf NP} based on general

complexity assumptions \cite{fls} versus those based on specific

algebraic assumptions \cite{Da}. ...
more >>>

Petr Savicky, Stanislav Zak

Branching programs (b.p.'s) or decision diagrams are a general

graph-based model of sequential computation. B.p.'s of polynomial

size are a nonuniform counterpart of LOG. Lower bounds for

different kinds of restricted b.p.'s are intensively investigated.

An important restriction are so called 1-b.p.'s, where each

computation reads each input bit at ...
more >>>

Farid Ablayev

In the manuscript F. Ablayev and M. Karpinski, On the power of

randomized branching programs (generalization of ICALP'96 paper

results for the case of pure boolean function, available at

http://www.ksu.ru/~ablayev) we exhibited a simple boolean functions

$f_n$ in $n$ variables such that:

1) $f_{n}$ can be computed ... more >>>

Alexander Barg

This is a research-expository paper. It deals with

complexity issues in the theory of linear block codes. The main

emphasis is on the theoretical performance limits of the

best known codes. Therefore, the main subject of the paper are

families of asymptotically good codes, i.e., codes whose rate and

relative ...
more >>>

Petr Savicky

For any Boolean function $f$ let $L(f)$ be its formula size

complexity in the basis $\{\land,\oplus,1\}$. For every $n$ and

every $k\le n/2$, we describe a probabilistic distribution

on formulas in the basis $\{\land,\oplus,1\}$ in some given set of

$n$ variables and of the ...
more >>>

Sanjeev Arora, Carsten Lund, Rajeev Motwani, Madhu Sudan, Mario Szegedy

We show that every language in NP has a probablistic verifier

that checks membership proofs for it using

logarithmic number of random bits and by examining a

<em> constant </em> number of bits in the proof.

If a string is in the language, then there exists a proof ...
more >>>

Venkatesan Guruswami, Daniel Lewin and Madhu Sudan, Luca Trevisan

It is known that there exists a PCP characterization of NP

where the verifier makes 3 queries and has a {\em one-sided}

error that is bounded away from 1; and also that 2 queries

do not suffice for such a characterization. Thus PCPs with

3 ...
more >>>

Madhu Sudan, Luca Trevisan

The error probability of Probabilistically Checkable Proof (PCP)

systems can be made exponentially small in the number of queries

by using sequential repetition. In this paper we are interested

in determining the precise rate at which the error goes down in

an optimal protocol, and we make substantial progress toward ...
more >>>

Eli Ben-Sasson, Avi Wigderson

The width of a Resolution proof is defined to be the maximal number of

literals in any clause of the proof. In this paper we relate proof width

to proof length (=size), in both general Resolution, and its tree-like

variant. The following consequences of these relations reveal width as ...
more >>>

Wolfgang Slany

We consider combinatorial avoidance and achievement games

based on graph Ramsey theory: The players take turns in coloring

still uncolored edges of a graph G, each player being assigned a

distinct color, choosing one edge per move. In avoidance games,

completing a monochromatic subgraph isomorphic to ...
more >>>

E.A. Okol'nishnikiva

Some operations over Boolean functions are considered. It is shown that

the operation of the geometrical projection and the operation of the

monotone extension can increase the complexity of Boolean functions for

formulas in each finite basis, for switching networks, for branching

programs, and read-$k$-times ...
more >>>

Michele Zito

We prove that, with high probability, the space complexity of refuting

a random unsatisfiable boolean formula in $k$-CNF on $n$

variables and $m = \Delta n$ clauses is

$O(n \cdot \Delta^{-\frac{1}{k-2}})$.

Andrei Bulatov

The Constraint Satisfaction Problem (CSP) provides a common framework for many combinatorial problems. The general CSP is known to be NP-complete; however, certain restrictions on a possible form of constraints may affect the complexity, and lead to tractable problem classes. There is, therefore, a fundamental research direction, aiming to separate ... more >>>

Andrei Bulatov

A wide variety of combinatorial problems can be represented in the form of the Constraint Satisfaction Problem (CSP). The general CSR is known to be NP-complete, however, some restrictions on the possible form of constraints may lead to a tractable subclass. Jeavons and coauthors have shown that the complexity of ... more >>>

Sven Baumer, Rainer Schuler

The satisfiability problem of Boolean Formulae in 3-CNF (3-SAT)

is a well known NP-complete problem and the development of faster

(moderately exponential time) algorithms has received much interest

in recent years. We show that the 3-SAT problem can be solved by a

probabilistic algorithm in expected time O(1,3290^n).

more >>>

Nayantara Bhatnagar, Parikshit Gopalan, Richard J. Lipton

We study the problem of representing symmetric Boolean functions as symmetric polynomials over Z_m. We show an equivalence between such

representations and simultaneous communication protocols. Computing a function with a polynomial of degree d modulo m=pq is equivalent to a two player protocol where one player is given the first ...
more >>>

Kazuo Iwama, Suguru Tamaki

This paper presents a new upper bound for the

$k$-satisfiability problem. For small $k$'s, especially for $k=3$,

there have been a lot of algorithms which run significantly faster

than the trivial $2^n$ bound. The following list summarizes those

algorithms where a constant $c$ means that the algorithm runs in time

more >>>

Andrei Krokhin, Peter Jonsson

In constraint satisfaction problems over finite domains, some variables

can be frozen, that is, they take the same value in all possible solutions. We study the complexity of the problem of recognizing frozen variables with restricted sets of constraint relations allowed in the

instances. We show that the complexity of ...
more >>>

Andrzej Lingas, Martin Wahlén

We consider the ``minor'' and ``homeomorphic'' analogues of the maximum clique problem, i.e., the problems of determining the largest $h$ such that the input graph has a minor isomorphic to $K_h$ or a subgraph homeomorphic to $K_h,$ respectively.We show the former to be approximable within $O(\sqrt {n} \log^{1.5} n)$ by ... more >>>

Kooshiar Azimian, Mahmoud Salmasizadeh, Javad Mohajeri

In1985, Shmuley proposed a theorem about intractability of Composite Diffie-Hellman [Sh85]. The Theorem of Shmuley may be paraphrased as saying that if there exist a probabilistic poly-time oracle machine which solves the Diffie-Hellman modulo an

RSA-number with odd-order base then there exist a probabilistic algorithm which factors the modulo. ...
more >>>

Martin Dyer, Leslie Ann Goldberg, Michael S. Paterson

We give a dichotomy theorem for the problem of counting homomorphisms to

directed acyclic graphs. $H$ is a fixed directed acyclic graph.

The problem is, given an input digraph $G$, how many homomorphisms are there

from $G$ to $H$. We give a graph-theoretic classification, showing that

for some digraphs $H$, ...
more >>>

Alan Nash, Russell Impagliazzo, Jeff Remmel

Diagonalization is a powerful technique in recursion theory and in

computational complexity \cite{For00}. The limits of this technique are

not clear. On the one hand, many people argue that conflicting

relativizations mean a complexity question cannot be resolved using only

diagonalization. On the other hand, it is not clear that ...
more >>>

Parikshit Gopalan, Phokion G. Kolaitis, Elitza Maneva, Christos H. Papadimitriou

Boolean satisfiability problems are an important benchmark for questions about complexity, algorithms, heuristics and threshold phenomena. Recent work on heuristics, and the satisfiability threshold has centered around the structure and connectivity of the solution space. Motivated by this work, we study structural and connectivity-related properties of the space of solutions ... more >>>

Oded Lachish, Ilan Newman, Asaf Shapira

Combinatorial property testing deals with the following relaxation

of decision problems: Given a fixed property and an input $x$, one

wants to decide whether $x$ satisfies the property or is ``far''

from satisfying it. The main focus of property testing is in

identifying large families of properties that can be ...
more >>>

Leslie G. Valiant

Living cells function according to complex mechanisms that operate in different ways depending on conditions. Evolutionary theory suggests that such mechanisms evolved as a result of a random search guided by selection and realized by genetic mutations. However, as some observers have noted, there has existed no theory that would ... more >>>

Lance Fortnow, Rahul Santhanam

We survey time hierarchies, with an emphasis on recent attempts to prove hierarchies for semantic classes.

more >>>Andrei A. Bulatov

The Counting Constraint Satisfaction Problem (#CSP(H)) over a finite

relational structure H can be expressed as follows: given a

relational structure G over the same vocabulary,

determine the number of homomorphisms from G to H.

In this paper we characterize relational structures H for which

#CSP(H) can be solved in ...
more >>>

Dmitriy Cherukhin

We consider bounded depth circuits over an arbitrary field $K$. If the field $K$ is finite, then we allow arbitrary gates $K^n\to K$. For instance, in the case of field $GF(2)$ we allow any Boolean gates. If the field $K$ is infinite, then we allow only polinomials.

For every fixed ... more >>>

Manoj Prabhakaran, Mike Rosulek

We develop new tools to study the relative complexities of secure

multi-party computation tasks (functionalities) in the Universal

Composition framework. When one task can be securely realized using

another task as a black-box, we interpret this as a

qualitative, complexity-theoretic reduction between the two tasks.

Virtually all previous characterizations of ...
more >>>

Arnaldo Moura, Igor Carboni Oliveira

We propose a generalization of the traditional algorithmic space and

time complexities. Using the concept introduced, we derive an

unified proof for the deterministic time and space hierarchy

theorems, now stated in a much more general setting. This opens the

possibility for the unification and generalization of other results

that ...
more >>>

Nicola Galesi, Massimo Lauria

We prove that Polynomial Calculus and Polynomial Calculus with Resolution are not automatizable, unless W[P]-hard problems are fixed parameter tractable by one-side error randomized algorithms. This extends to Polynomial Calculus the analogous result obtained for Resolution by Alekhnovich and Razborov (SIAM J. Computing, 38(4), 2008).

more >>>Dave Buchfuhrer, Chris Umans

Many commonly-used auction mechanisms are ``maximal-in-range''. We show that any maximal-in-range mechanism for $n$ bidders and $m$ items cannot both approximate the social welfare with a ratio better than $\min(n, m^\eta)$ for any constant $\eta < 1/2$ and run in polynomial time, unless $NP \subseteq P/poly$. This significantly improves upon ... more >>>

Derrick Stolee, Vinodchandran Variyam

We consider the reachability problem for a certain class of directed acyclic graphs embedded on surfaces. Let ${\cal G}(m,g)$ be the class of directed acyclic graphs with $m = m(n)$ source vertices embedded on a surface (orientable or non-orientable) of genus $g = g(n)$. We give a log-space reduction that ... more >>>

Sergei Lozhkin, Alexander Shiganov

In this paper we suggest a modification of classical Lupanov's method [Lupanov1958]

that allows building circuits over the basis $\{\&,\vee,\neg\}$ for Boolean functions of $n$ variables with size at most

$$

\frac{2^n}{n}\left(1+\frac{3\log n + O(1)}{n}\right),

$$

and with more uniform distribution of outgoing arcs by circuit gates.

For almost all ... more >>>

Stephen A. Fenner, Rohit Gurjar, Arpita Korwar, Thomas Thierauf

We consider the complexity of determining the winner of a finite, two-level poset game.

This is a natural question, as it has been shown recently that determining the winner of a finite, three-level poset game is PSPACE-complete.

We give a simple formula allowing one to compute the status ...
more >>>

Igor Sergeev

It is shown that complexity of implementation of prefix sums of $m$ variables (i.e. functions $x_1 \cdot \ldots\cdot x_i$, $1\le i \le m$) by circuits of depth $\lceil \log_2 m \rceil$ in the case $m=2^n$ is exactly $$3.5\cdot2^n - (8.5+3.5(n \bmod 2))2^{\lfloor n/2\rfloor} + n + 5.$$ As a consequence, ... more >>>

Stanislav Zak

Abstract. The old intuitive question "what does the machine think" at

different stages of its computation is examined. Our paper is based on

the formal de nitions and results which are collected in the branching

program theory around the intuitive question "what does the program

know about the contents of ...
more >>>

Bireswar Das, Patrick Scharpfenecker, Jacobo Toran

It is well known that problems encoded with circuits or formulas generally gain an exponential complexity blow-up compared to their original complexity.

We introduce a new way for encoding graph problems, based on $\textrm{CNF}$ or $\textrm{DNF}$ formulas. We show that contrary to the other existing succinct models, there are ... more >>>

Guy Kindler

The first part of this thesis strengthens the low-error PCP

characterization of NP, coming closer to the upper limit of the

conjecture of~\cite{BGLR}.

In the second part we show that a boolean function over

$n$ variables can be tested for the property of depending ...
more >>>

Moritz Gobbert

The topic of this paper is a game on graphs called Edge Hop. The game's goal is to move a marked token from a specific starting node to a specific target node. Further, there are other tokens on some nodes which can be moved by the player under suitable conditions. ... more >>>

Lieuwe Vinkhuijzen, André Deutz

In quantum computational complexity theory, the class QMA models the set of problems efficiently verifiable by a quantum computer the same way that NP models this for classical computation. Vyalyi proved that if $\text{QMA}=\text{PP}$ then $\text{PH}\subseteq \text{QMA}$. In this note, we give a simple, self-contained proof of the theorem, using ... more >>>

Igor Sergeev

We investigate the number of pairwise comparisons sufficient to sort $n$ elements chosen from a linearly ordered set. This number is shown to be $\log_2(n!) + o(n)$ thus improving over the previously known upper bounds of the form $\log_2(n!) + \Theta(n)$. The new bound is achieved by the proposed group ... more >>>

Robert Kleinberg, Daniel Mitropolsky, Christos Papadimitriou

We identify several genres of search problems beyond NP for which existence of solutions is guaranteed. One class that seems especially rich in such problems is PEPP (for "polynomial empty pigeonhole principle"), which includes problems related to existence theorems proved through the union bound, such as finding a bit string ... more >>>