Weizmann Logo
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style

Reports tagged with complexity theory:
TR96-046 | 27th August 1996
Luca Trevisan

On the Approximability of the Multi-dimensional Euclidean TSP

Revisions: 1

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

TR99-034 | 30th August 1999
Wolfgang Merkle

The global power of additional queries to p-random oracles.

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

TR01-022 | 15th February 2001
Rahul Santhanam

On segregators, separators and time versus space

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

TR02-036 | 30th May 2002
Stephen A. Fenner

PP-lowness and a simple definition of AWPP

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

TR03-048 | 24th June 2003
Stefan Droste, Thomas Jansen, Ingo Wegener

Upper and Lower Bounds for Randomized Search Heuristics in Black-Box Optimization

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

TR04-015 | 24th February 2004
Richard Beigel, Harry Buhrman, Peter Fejer, Lance Fortnow, Piotr Grabowski, Luc Longpré, Andrej Muchnik, Frank Stephan, Leen Torenvliet

Enumerations of the Kolmogorov Function

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

TR05-099 | 9th September 2005
Leslie G. Valiant

Holographic Algorithms

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

TR05-126 | 5th November 2005
Eric Allender, Lisa Hellerstein, Paul McCabe, Michael Saks

Minimizing DNF Formulas and AC0 Circuits Given a Truth Table

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

TR07-005 | 17th January 2007
Rahul Santhanam

Circuit Lower Bounds for Merlin-Arthur Classes

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

TR07-096 | 8th October 2007
Lance Fortnow, Rahul Santhanam

Infeasibility of Instance Compression and Succinct PCPs for NP

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

TR08-021 | 3rd March 2008
Shankar Kalyanaraman, Chris Umans

The Complexity of Rationalizing Matchings

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.

... more >>>

TR09-111 | 5th November 2009
Walid Gomaa

Model-Theoretic Characterization of Complexity Classes

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

TR12-122 | 17th September 2012
Giorgio Ausiello, Francesco Cristiano, Luigi Laura

Syntactic Isomorphism of CNF Boolean Formulas is Graph Isomorphism Complete

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

TR20-078 | 21st May 2020
Eric Allender

The New Complexity Landscape around Circuit Minimization

We survey recent developments related to the Minimum Circuit Size Problem

more >>>

TR21-004 | 10th January 2021
Vishnu Iyer, Avishay Tal, Michael Whitmeyer

Junta Distance Approximation with Sub-Exponential Queries

Leveraging tools of De, Mossel, and Neeman [FOCS, 2019], we show two different results pertaining to the tolerant testing of juntas. Given black-box access to a Boolean function $f:\{\pm1\}^{n} \to \{\pm1\}$ we give a poly$(k, \frac{1}{\varepsilon})$ query algorithm that distinguishes between functions that are $\gamma$-close to $k$-juntas and $(\gamma+\varepsilon)$-far from ... more >>>

ISSN 1433-8092 | Imprint