Luca Trevisan

We consider the Traveling Salesperson Problem (TSP) restricted

to Euclidean spaces of dimension at most k(n), where n is the number of

cities. We are interested in the relation between the asymptotic growth of

k(n) and the approximability of the problem. We show that the problem is ...
more >>>

Wolfgang Merkle

We consider separations of reducibilities in the context of

resource-bounded measure theory. First, we show a result on

polynomial-time bounded reducibilities: for every p-random set R,

there is a set which is reducible to R with k+1 non-adaptive

queries, but is not reducible to any other p-random set with ...
more >>>

Rahul Santhanam

We give the first extension of the result due to Paul, Pippenger,

Szemeredi and Trotter that deterministic linear time is distinct from

nondeterministic linear time. We show that DTIME(n \sqrt(log^{*}(n)))

\neq NTIME(n \sqrt(log^{*}(n))). We show that atleast one of the

following statements holds: (1) P \neq L ...
more >>>

Stephen A. Fenner

We show that the counting classes AWPP and APP [Li 1993] are more robust

than previously thought. Our results identify asufficient condition for

a language to be low for PP, and we show that this condition is at least

as weak as other previously studied criteria. Our results imply that

more >>>

Stefan Droste, Thomas Jansen, Ingo Wegener

Randomized search heuristics like local search, simulated annealing or all kinds of evolutionary algorithms have many applications. However, for most problems the best worst-case expected run times are achieved by more problem-specific algorithms. This raises the question about the limits of general randomized search heuristics.

Here a framework called black-box ... more >>>

Richard Beigel, Harry Buhrman, Peter Fejer, Lance Fortnow, Piotr Grabowski, Luc Longpré, Andrej Muchnik, Frank Stephan, Leen Torenvliet

A recursive enumerator for a function $h$ is an algorithm $f$ which

enumerates for an input $x$ finitely many elements including $h(x)$.

$f$ is an $k(n)$-enumerator if for every input $x$ of length $n$, $h(x)$

is among the first $k(n)$ elements enumerated by $f$.

If there is a $k(n)$-enumerator for ...
more >>>

Leslie G. Valiant

Complexity theory is built fundamentally on the notion of efficient

reduction among computational problems. Classical

reductions involve gadgets that map solution fragments of one problem to

solution fragments of another in one-to-one, or

possibly one-to-many, fashion. In this paper we propose a new kind of

reduction that allows for gadgets ...
more >>>

Eric Allender, Lisa Hellerstein, Paul McCabe, Michael Saks

For circuit classes R, the fundamental computational problem, Min-R,

asks for the minimum R-size of a boolean function presented as a truth

table. Prominent examples of this problem include Min-DNF, and

Min-Circuit (also called MCSP). We begin by presenting a new reduction

proving that Min-DNF is NP-complete. It is significantly ...
more >>>

Rahul Santhanam

We show that for each k > 0, MA/1 (MA with 1 bit of advice) does not have circuits of size n^k. This implies the first superlinear circuit lower bounds for the promise versions of the classes MA, AM and ZPP_{||}^{NP}.

We extend our main result in several ways. For ... more >>>

Lance Fortnow, Rahul Santhanam

We study the notion of "instance compressibility" of NP problems [Harnik-Naor06], closely related to the notion of kernelization in parameterized complexity theory [Downey-Fellows99, Flum-Grohe06, Niedermeier06]. A language $L$ in NP is instance compressible if there

is a polynomial-time computable function $f$ and a set $A$ such that

for each instance ...
more >>>

Shankar Kalyanaraman, Chris Umans

Given a set of observed economic choices, can one infer

preferences and/or utility functions for the players that are

consistent with the data? Questions of this type are called {\em

rationalization} or {\em revealed preference} problems in the

economic literature, and are the subject of a rich body of work.

Walid Gomaa

Model theory is a branch of mathematical logic that investigates the

logical properties of mathematical structures. It has been quite

successfully applied to computational complexity resulting in an

area of research called descriptive complexity theory. Descriptive

complexity is essentially a syntactical characterization of

complexity classes using logical formalisms. However, there ...
more >>>

Giorgio Ausiello, Francesco Cristiano, Luigi Laura

We investigate the complexity of the syntactic isomorphism problem of CNF Boolean Formulas (CSFI): given two CNF Boolean formulas $\varphi(a_{1},\ldots,a_{n})$ and $\varphi(b_{1},\ldots,b_{n})$ decide whether there exists a permutation of clauses, a permutation of literals and a bijection between their variables such that $\varphi(a_{1},\ldots,a_{n})$ and $\varphi(b_{1},\ldots,b_{n})$ become syntactically identical. We first ... more >>>