[Lowerbounds, Upperbounds]

The following new ECCC reports have been published:
===================================================

TR05-074
Li-Sha HUANG, Xiaotie DENG:

On Complexity of Market Equilibria with Maximum Social Welfare

Abstract:
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 number of equilibrium prices is #P-hard.

Keywords: Computational Complexity,
NP-hardness,
Market Equilibrium,
Leontief Economy

TR05-073
Oded Goldreich and Dana Ron.:

Approximating Average Parameters of Graphs.

Abstract:
Inspired by Feige ({em 36th STOC}, 2004), we initiate a study of
sublinear randomized algorithms for approximating average parameters
of a graph. Specifically, we consider the average degree of a graph
and the average distance between pairs of vertices in a graph.
Since our focus is on sublinear algorithms, these algorithms
access the input graph via queries to an adequate oracle.
We consider two types of queries. The first type is standard
neighborhood queries (i.e., {em what is the $i^xth$ neighbor of
vertex $v$?}), whereas the second type are queries regarding the
quantities that we need to find the average of (i.e., {em what is
the degree of vertex $v$?}/ and {em what is the distance between $u$
and $v$?}, respectively).
Loosely speaking, our results indicate a difference between the
two problems: For approximating the average degree,
the standard neighbor queries suffice and in fact are preferable
to degree queries. In contrast, for approximating average distances,
the standard neighbor queries are of little help whereas distance
queries are crucial.

Keywords: Sublinear-time,
randomness,
approximation.

TR05-072
Christian Glasser, Alan L. Selman, Liyu Zhang:

Survey of Disjoint NP-Pairs and Relations to Propositional
Proof Systems

Abstract:
We survey recent results on disjoint NP-pairs. In particular, we
survey the relationship of disjoint NP-pairs to the theory of proof
systems for propositional calculus.

TR05-071
Marius Zimand:

Simple extractors via constructions of cryptographic pseudo-random
generators

Abstract:
Trevisan has shown that constructions of pseudo-random generators from
hard functions (the Nisan-Wigderson approach) also produce extractors.
We show that constructions of pseudo-random generators from one-way
permutations (the Blum-Micali-Yao approach) can be used for building
extractors as well. Using this new technique we build extractors that
do not use designs or polynomial-based error-correcting codes and
that are very simple and efficient. For example, one extractor
produces each output bit separately in $O(log2 n)$ time.
These extractors work for weak sources with min entropy $lambda n$,
for arbitrary constant $lambda > 0$, have seed length $O(log2 n)$,
and their output length is $approx n^{lambda/3}$.

Keywords: extractor,
pseudo-random generator,
one-way permutation

TR05-070
Mahdi Cheraghchi:

On Matrix Rigidity and the Complexity of Linear Forms

Abstract:
The rigidity function of a matrix is defined as the minimum number of
its entries that need to be changed in order to reduce the rank of
the matrix to below a given parameter. Proving a strong enough lower
bound on the rigidity of a matrix implies a nontrivial lower bound on
the complexity of any linear circuit computing the set of linear
forms associated with it. However, although it is shown that most
matrices are rigid enough, no explicit construction of a rigid family
of matrices is known.
In this survey report we review the concept of rigidity and some of
its interesting variations as well as several notable results related
to that. We also show the existence of highly rigid matrices
constructed by evaluation of bivariate polynomials over finite fields.

Keywords: Matrix Rigidity,
Low Level Complexity,
Circuit Complexity,
Linear Forms

TR05-069
Piotr Berman, Marek Karpinski:

8/7-Approximation Algorithm for (1,2)-TSP

Abstract:
We design a polynomial time 8/7-approximation algorithm for the
Traveling Salesman Problem in which all distances are either one or
two. This improves over the best known approximation factor of 7/6
for that problem. As a direct application we get a 7/6-approximation
algorithm for the Maximum Path Cover Problem, similarily improving
upon the best known approximation factor for that problem. The result
depends on a new method of consecutive path cover improvements and
on a new analysis of certain related color alternating paths. This
method could be of independent interest.

Keywords: Approximation Algorithms,
Approximations Factors,
Metric TSP,
Path Cover Problems,
Alternating Paths,
Justification Points,
Consistency,
Small Step Improvements

TR05-068
Christian Glasser, A. Pavan, Alan L. Selman, Liyu Zhang:

Redundancy in Complete Sets

Abstract:
We show that a set is m-autoreducible if and only if it is m-mitotic.
This solves a long standing open question in a surprising way. As a
consequence of this unconditional result and recent work by Glasser
et al., complete sets for all of the following complexity classes are
m-mitotic: NP, coNP, ParityP, PSPACE, and NEXP, as well as all
levels of PH, MODPH, and the Boolean hierarchy over NP. In the cases
of NP, PSPACE, NEXP, and PH, this at once answers several
well-studied open questions. These results tell us that complete
sets share a redundancy that was not known before.
We disprove the equivalence between autoreducibility and mitoticity
for all polynomial-time-bounded reducibilities between
3-tt-reducibility and Turing- reducibility: There exists a sparse set
in EXP that is polynomial-time 3-tt- autoreducible, but not weakly
polynomial-time T-mitotic. In particular, polynomial-time
T-autoreducibility does not imply polynomial-time weak T- mitoticity,
which solves an open question by Buhrman and Torenvliet.
We generalize autoreducibility to define poly-autoreducibility and
give evidence that NP-complete sets are poly-autoreducible.

TR05-067
Zeev Dvir, Amir Shpilka:

An Improved Analysis of Mergers

Abstract:
Mergers are functions that transform k (possibly dependent) random
sources into a single random source, in a way that ensures that if
one of the input sources has min-entropy rate $delta$ then the
output has min-entropy rate close to $delta$. Mergers have proven to
be a very useful tool in explicit constructions of extractors and
condensers, and are also interesting objects in their own right. In
this work we present a new analysis of the merger construction of
[LRVW03]. Our analysis shows that the min-entropy rate of this
merger’s output is actually $0.52*delta$ instead of $0.5*delta$,
where $delta$ is the min-entropy rate of one of the inputs. To obtain
this result we deviate from the usual linear algebra methods that
were used by [LRVW03] and introduce a new technique that involves
results from additive number theory.

Keywords: extractors,
mergers,
randomness

TR05-066
Jakob Nordstroem:

Narrow Proofs May Be Spacious: Separating Space and Width in Resolution

Abstract:
The width of a resolution proof is the maximal number of literals in
any clause of the proof. The space of a proof is the maximal number
of memory cells used if the proof is only allowed to resolve on
clauses kept in memory. Both of these measures have previously been
studied and related to the refutation size of unsatisfiable CNF
formulas. Also, the resolution refutation space of a formula has been
proven to be at least as large as the refutation width, but it has
remained unknown whether space can be separated from width or the
two measures coincide asymptotically. We prove that there is a family
of k-CNF formulas for which the refutation width in resolution is
constant but the refutation space is non-constant, thus solving an
open problem mentioned in several previous papers.

Keywords: proof complexity,
resolution,
width, space,
separation,
lower bound,
pebble game

TR05-065
Alexander Barvinok, Alex Samorodnitsky:

Random Weighting, Asymptotic Counting, and Inverse Isoperimetry

Abstract:
For a family X of k-subsets of the set 1…n, let |X| be the
cardinality of X and let Gamma(X, mu) be the expected maximum weight
of a subset from X when the weights of 1…n are chosen independently
at random from a symmetric probability distribution mu on R. We
consider the inverse isoperimetric problem of finding mu for which
Gamma(X, mu) gives the best estimate of ln |X|.
We prove that the optimal choice of mu is the logistic distribution,
in which case Gamma(X, mu) provides an asymptotically tight estimate
of ln |X| as k^{-1} ln |X| grows. Since in many important cases
Gamma(X, mu) can be easily computed, we obtain computationally
efficient approximation algorithms for a variety of counting problems.
Given mu, we describe families X of a given cardinality with the
minimum value of Gamma(X, mu), thus extending and sharpening various
isoperimetric inequalities in the Boolean cube.

TR05-064
Howard Karloff, Subhash Khot, Aranyak Mehta, Yuval Rabani:

On earthmover distance, metric labeling, and 0-extension

Abstract:
We study the classification problem {sc Metric Labeling} and its
special case {sc 0-Extension} in the context of earthmover metrics.
Researchers recently proposed using earthmover metrics to get a
polynomial time-solvable relaxation of {sc Metric Labeling}; until
now, however, no one knew if the integrality ratio was constant or
not, for either {sc Metric Labeling} or {sc 0-Extension}. We prove
* that the integrality ratio of the earthmover relaxation for
{sc Metric Labeling} is $Omega(log k)$, $k$ being the number of
labels (this bound is tight), whereas the best previous lower bound
on the integrality ratio was constant;
* that the integrality ratio of the earthmover relaxation for
{sc 0-Extension} is $Omega(sqrt{log k})$, $k$ being the number of
terminals (the integrality ratio was known to be
$O((log k)/loglog k)$), whereas the best previous lower bound was
constant;
* that for no $epsilon>0$ is there a polynomial-time
$O((log n)^{1/4-eps})$-approximation algorithm for
{sc 0-Extension}, $n$ being the number of vertices, unless
NP$subseteq$DTIME$(n^{poly(log n)})$, whereas the strongest
inapproximability result known before was MAX SNP-hardness; and
* that there is a polynomial-time approximation algorithm for
{sc 0-Extension} with performance ratio $O(sqrt{diam(d)})$, where
$diam(d)$ is the ratio of largest distance to smallest nonzero
distance in the terminal metric.

TR05-063
Bodo Manthey, Ruediger Reischuk:

Smoothed Analysis of the Height of Binary Search Tress

Abstract:
Binary search trees are one of the most fundamental data structures.
While the height of such a tree may be linear in the worst case, the
average height with respect to the uniform distribution is only
logarithmic. The exact value is one of the best studied problems in
average case complexity.

Keywords: Smoothed Analysis,
Binary Search Trees,
Discrete Perturbations,
Permutations

TR05-062
A. Pavan, N. V. Vinodchandran:

2-Local Random Reductions to 3-Valued Functions

Abstract:
Yao (in a lecture at DIMACS Workshop on structural complexity and
cryptography) showed that if a language L is 2-locally-random
reducible to a Boolean functio, then L is in PSPACE/poly.
Fortnow and Szegedy quantitatively improved Yao’s result to show that
such languages are in fact in NP/poly (Information Processing Letters,
1992).
In this paper we extend Yao’s result to show that if a language L
is 2-locally-random reducible to a target function which takes values
in {0,1,2}, then L is in PSPACE/poly.

Keywords: local random reductions

TR05-061
Ronen Gradwohl, Guy Kindler, Omer Reingold, Amnon Ta-Shma:

On the Error Parameter of Dispersers

Abstract:
Optimal dispersers have better dependence on the error than
optimal extractors. In this paper we give explicit disperser
constructions that beat the best possible extractors in some
parameters. Our constructions are not strong, but we show that
having such explicit strong constructions implies a solution
to the Ramsey graph construction problem.

Keywords: Dispersers,
Extractors,
Expander Graphs,
Ramsey Graphs

=======================================================================

Online access to ECCC is available via the following network services: