Under the auspices of the Computational Complexity Foundation (CCF)

REPORTS > 1995:
All reports in year 1995:
TR95-001 | 1st January 1995
Amos Beimel, Anna Gal, Michael S. Paterson

#### Lower Bounds for Monotone Span Programs

The model of span programs is a linear algebraic model of
computation. Lower bounds for span programs imply lower bounds for
contact schemes, symmetric branching programs and for formula size.
Monotone span programs correspond also to linear secret-sharing schemes.
We present a new technique for proving lower bounds for ... more >>>

TR95-002 | 1st January 1995
Detlef Sieling

#### New Lower Bounds and Hierarchy Results for Restricted Branching Programs

In unrestricted branching programs all variables may be tested
arbitrarily often on each path. But exponential lower bounds are only
known, if on each path the number of tests of each variable is bounded
(Borodin, Razborov and Smolensky (1993)). We examine branching programs
in which for each path the ... more >>>

TR95-003 | 1st January 1995
Marek Karpinski, Alexander Zelikovsky

#### 1.757 and 1.267-Approximation Algorithms for the Network and and Rectilinear Steiner Tree Problems

The Steiner tree problem requires to find a shortest tree connection
a given set of terminal points in a metric space. We suggest a better
and fast heuristic for the Steiner problem in graphs and in
rectilinear plane. This heuristic finds a Steiner tree at ... more >>>

TR95-004 | 1st January 1995
Martin Dietzfelbinger, Miroslaw Kutylowski, Rüdiger Reischuk

#### Feasible Time-Optimal Algorithms for Boolean Functions on Exclusive-Write PRAMs

It was shown some years ago that the computation time for many important
Boolean functions of n arguments on concurrent-read exclusive-write
parallel random-access machines
(CREW PRAMs) of unlimited size is at least f(n) = 0.72 log n.
On the other hand, it ... more >>>

TR95-005 | 1st January 1995
Maciej Liskiewicz, Rüdiger Reischuk

#### The Sublogarithmic Alternating Space World

This paper tries to fully characterize the properties and relationships
of space classes defined by Turing machines that use less than
logarithmic space - may they be deterministic,
nondeterministic or alternating (DTM, NTM or ATM).

We provide several examples of specific languages ... more >>>

TR95-006 | 1st January 1995
Kenneth W. Regan, D. Sivakumar, Jin-Yi Cai

#### Pseudorandom Generators, Measure Theory, and Natural Proofs

This paper proves that if strong pseudorandom number generators or
one-way functions exist, then the class of languages that have
polynomial-sized circuits is not small within exponential
time, in terms of the resource-bounded measure theory of Lutz.
More precisely, if for some \epsilon > 0 there exist nonuniformly
2^{n^{\epsilon}}-hard ... more >>>

TR95-007 | 1st January 1995
U. Faigle, S.P. Fekete, W. Hochstättler, W. Kern

#### THE NUCLEON OF COOPERATIVE GAMES AND AN ALGORITHM FOR MATCHING GAMES

The {\it nucleon} is introduced as a new allocation concept for
non-negative cooperative n-person transferable utility games.
The nucleon may be viewed as the multiplicative analogue of
Schmeidler's nucleolus.
It is shown that the nucleon of (not necessarily bipartite) matching
games ... more >>>

TR95-009 | 2nd February 1995
Matthias Krause

#### A note on realizing iterated multiplication by small depth threshold circuits

It is shown that decomposition via Chinise Remainder does not
yield polynomial size depth 3 threshold circuits for iterated
multiplication of n-bit numbers. This result is achieved by
proving that, in contrast to multiplication of two n-bit
numbers, powering, division, and other related problems, the
... more >>>

TR95-010 | 16th February 1995
Pavel Pudlak, Jiri Sgall

#### An Upper Bound for a Communication Game Related to Time-Space Tradeoffs

We prove an unexpected upper bound on a communication game proposed
by Jeff Edmonds and Russell Impagliazzo as an approach for
proving lower bounds for time-space tradeoffs for branching programs.
Our result is based on a generalization of a construction of Erdos,
Frankl and Rodl of a large 3-hypergraph ... more >>>

TR95-011 | 15th February 1995
Roman Bacik, Sanjeev Mahajan

#### Semidefinite Programming and its Applications to NP Problems

The graph homomorphism problem is a canonical $NP$-complete problem.
It generalizes various other well-studied problems such as graph
coloring and finding cliques. To get a better insight into a
combinatorial problem, one often studies relaxations of the problem.
We define fractional homomorphisms and pseudo-homomorphisms ... more >>>

TR95-013 | 24th February 1995
Oleg Verbitsky

#### The Parallel Repetition Conjecture for Trees is True

The parallel repetition conjecture (PRC) of Feige and Lovasz says that the
error probability of a two prover one round interactive protocol repeated $n$
times in parallel is exponentially small in $n$.
We show that the PRC is true in the case when
the bipartite graph of dependence between ... more >>>

TR95-014 | 27th January 1995
U. Faigle, W. Kern, M. Streng

#### Note On the Computational Complexity of $j$-Radii of Polytopes in ${\Re}^n$

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.

more >>>

TR95-015 | 6th February 1995
Bshouty, Cleve, Gavalda, Kannan, Tamon.

#### Oracles and queries that are sufficient for exact learning

We show what happen to learning if the learner can use NP-oracle.
A consequence of our results we show that
If NP\subset P/poly then the polynomial Hierarchy collapses to ZPP^NP

END_OF_DESCRIPTION

more >>>

TR95-016 | 2nd February 1995
U. Faigle, S.P. Fekete, W. Hochstättler, W. Kern

#### On approximately fair cost allocation in Euclidean TSP games

We consider the problem of fair cost allocation for traveling
salesman games for which the triangle inequality holds. We
give examples showing that the core of such games may be
empty, even for the case of Euclidean distances. On the
positive side, we develop an LP-based ... more >>>

TR95-017 | 27th March 1995
Claudia Bertram, Thomas Hofmeister

#### Multiple Product Modulo Arbitrary Numbers

We consider the threshold circuit complexity of computing
the multiple product modulo m in threshold circuits.

more >>>

TR95-018 | 27th March 1995
Jay Belanger, Jie Wang

#### Rankable Distributions Do Not Provide Harder Instances Than Uniform Distributions

We show that polynomially rankable distributions
do not provide harder instances than uniform distributions
for NP problems. In particular, we show that if Levin's
randomized tiling problem is solvable in polynomial time on
average, then every NP problem under any p-rankable
... more >>>

TR95-019 | 14th April 1995
Jin-Yi Cai, Alan L. Selman

#### Average time complexity classes

TR95-020 | 8th March 1995
William Hurwood

#### Dynamic Fault Diagnosis

We consider a dynamic fault diagnosis problem: There are n
processors, to be tested in a series of rounds. In every
testing round we use a directed matching to have some
processors report on the status (good or faulty) of other
processors. Also in each round ... more >>>

TR95-021 | 20th April 1995
Marek Karpinski, Rutger Verbeek

#### On Randomized Versus Deterministic Computation

In contrast to deterministic or nondeterministic computation, it is
a fundamental open problem in randomized computation how to separate
different randomized time classes (at this point we do not even know
how to separate linear randomized time from ${\mathcal O}(n^{\log n})$
randomized time) or how to ... more >>>

TR95-022 | 2nd May 1995
Marek Karpinski, Wojciech Rytter, Ayumi Shinohara

#### Pattern-Matching for Strings with Short Descriptions

We consider strings which are succinctly described. The description
is in terms of straight-line programs in which the constants are
symbols and the only operation is the concatenation. Such
descriptions correspond to the systems of recurrences or to
context-free grammars generating single words. The descriptive ... more >>>

TR95-023 | 16th May 1995
Sanjeev Khanna, Rajeev Motwani, Madhu Sudan, Umesh Vazirani

#### On Syntactic versus Computational views of Approximability

We attempt to reconcile the two distinct views of approximation
classes: syntactic and computational.
Syntactic classes such as MAX SNP allow for clean complexity-theoretic
results and natural complete problems, while computational classes such
as APX allow us to work with problems whose approximability is
well-understood. Our results give a computational ... more >>>

TR95-024 | 23rd May 1995
Mihir Bellare, Oded Goldreich, Madhu Sudan

#### Free bits, PCP and Non-Approximability - Towards tight results

Revisions: 4

This paper continues the investigation of the connection between proof
systems and approximation. The emphasis is on proving tight''
non-approximability results via consideration of measures like the
free bit complexity'' and the amortized free bit complexity'' of
proof systems.

The first part of the paper presents a collection of new ... more >>>

TR95-025 | 8th May 1995
Günter Hotz, Gero Vierke, Bjoern Schieffer

#### Analytic Machines

In this paper the $R$-machines defined by Blum, Shub and Smale
are generalized by allowing infinite convergent computations.
The description of real numbers is infinite.
Therefore, considering arithmetic operations on real numbers should
also imply infinite computations on {\em analytic machines}.
We prove that $\R$-computable functions are $\Q$-analytic.
We show ... more >>>

TR95-026 | 7th June 1995
Claus-Peter Schnorr, Horst Helmut Hoerner

#### Attacking the Chor-Rivest Cryptosystem by Improved Lattice Reduction

We introduce new algorithms for lattice basis reduction that are
improvements of the LLL-algorithm. We demonstrate the power of
these algorithms by solving random subset sum problems of
arbitrary density with 74 and 82 many weights, by breaking the
Chor-Rivest cryptoscheme in dimensions 103 and 151 ... more >>>

TR95-027 | 30th May 1995
Frederic Green

#### Lower Bounds for Circuits with Mod Gates and One Exact Threshold Gate

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

TR95-028 | 9th June 1995
Eric Allender, Martin Strauss

#### Measure on P: Robustness of the Notion

In (Allender and Strauss, FOCS '95), we defined a notion of
measure on the complexity class P (in the spirit of the work of (Lutz,
JCSS '92) that provides a notion of measure on complexity classes at least
as large as E, and the work of (Mayordomo, Phd. ... more >>>

TR95-029 | 15th June 1995
Oded Goldreich, Leonid Levin, Noam Nisan

#### On Constructing 1-1 One-Way Functions

We show how to construct length-preserving 1-1 one-way
functions based on popular intractability assumptions (e.g., RSA, DLP).
Such 1-1 functions should not
be confused with (infinite) families of (finite) one-way permutations.
What we want and obtain is a single (infinite) 1-1 one-way function.

more >>>

TR95-030 | 20th June 1995
Marek Karpinski, Alexander Zelikovsky

#### New Approximation Algorithms for the Steiner Tree Problems

The Steiner tree problem asks for the shortest tree connecting
a given set of terminal points in a metric space. We design
new approximation algorithms for the Steiner tree problems
using a novel technique of choosing Steiner points in dependence
on the possible deviation from ... more >>>

TR95-031 | 25th June 1995
Dorit Dor, Uri Zwick

#### Selecting the median

Improving a long standing result of Sch\"{o}nhage, Paterson
and Pippenger we show that the MEDIAN of a set containing n
elements can always be found using at most 2.95n comparisons.

This is the full version of the paper. An extended abstract
version ... more >>>

TR95-032 | 6th April 1995

#### On the Fourier spectrum of monotone functions

TR95-033 | 29th June 1995
Richard Beigel, David Eppstein

#### 3-Coloring in time O(1.3446^n): a no-MIS algorithm

We consider worst case time bounds for NP-complete problems
including 3-SAT, 3-coloring, 3-edge-coloring, and 3-list-coloring.
Our algorithms are based on a common generalization of these problems,
called symbol-system satisfiability or, briefly, SSS [R. Floyd &
R. Beigel, The Language of Machines]. 3-SAT is equivalent to
(2,3)-SSS while the other problems ... more >>>

TR95-034 | 30th June 1995
Christoph Meinel, Stephan Waack

#### Lower Bounds for the Majority Communication Complexity of Various Graph Accessibility Problems

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

TR95-035 | 30th June 1995
Richard Beigel

#### Closure Properties of GapP and #P

We classify the univariate functions that are relativizable
closure properties of GapP, solving a problem posed by Hertrampf,
Vollmer, and Wagner (Structures '95). We also give a simple proof of
their classification of univariate functions that are relativizable
closure properties of #P.

more >>>

TR95-036 | 5th July 1995
Richard Beigel, William Gasarch, Efim Kinber

#### Frequency Computation and Bounded Queries

For a set A and a number n let F_n^A(x_1,...,x_n) =
A(x_1)\cdots A(x_n). We study how hard it is to approximate this
function in terms of the number of queries required. For a general
set A we have exact bounds that depend on functions from coding
theory. These are applied ... more >>>

TR95-037 | 2nd July 1995
Richard Beigel, Howard Straubing

#### The Power of Local Self-Reductions

Identify a string x over {0,1} with the positive integer
whose binary representation is 1x. We say that a self-reduction is
k-local if on input x all queries belong to {x-1,...,x-k}. We show
that all k-locally self-reducible sets belong to PSPACE. However, the
power of k-local self-reductions changes drastically between ... more >>>

TR95-038 | 2nd July 1995
Joe Kilian, Erez Petrank

#### An Efficient Non-Interactive Zero-Knowledge Proof System for NP with General Assumptions

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

TR95-039 | 11th July 1995
Tomoyuki Yamakami

#### Polynomial Time Samplable Distributions

Revisions: 2

This paper studies distributions which
can be approximated'' by sampling algorithms in time polynomial in
the length of their outputs. First, it is known that if
polynomial-time samplable distributions are polynomial-time
computable, then NP collapses to P. This paper shows by a simple
... more >>>

TR95-040 | 26th July 1995
Uri Zwick, Michael S. Paterson

#### The complexity of mean payoff games on graphs

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

TR95-041 | 28th June 1995
Alexander E. Andreev, Andrea E. F. Clementi, Jose Rolim

#### Optimal Bounds for the Approximation of Boolean Functions and Some Applications

We prove an optimal bound on the Shannon function
$L(n,m,\epsilon)$ which describes the trade-off between the
circuit-size complexity and the degree of approximation; that is
$$L(n,m,\epsilon)\ =\ \Theta\left(\frac{m\epsilon^2}{\log(2 + m\epsilon^2)}\right)+O(n).$$
Our bound applies to any partial boolean function
and any ... more >>>

TR95-042 | 14th September 1995
Beate Bollig, Ingo Wegener

#### Read-once Projections and Formal Circuit Verification with Binary Decision Diagrams

Computational complexity is concerned with the complexity of solving
problems and computing functions and not with the complexity of verifying
circuit designs.
The importance of formal circuit verification is evident.
Therefore, a framework of a complexity theory for formal circuit
verification with binary decision diagrams ... more >>>

TR95-043 | 14th September 1995
Eric Allender, Jia Jiao, Meena Mahajan, V Vinay

#### Non-Commutative Arithmetic Circuits: Depth Reduction and Size Lower Bounds

We investigate the phenomenon of depth-reduction in commutative
and non-commutative arithmetic circuits. We prove that in the
commutative setting, uniform semi-unbounded arithmetic circuits of
logarithmic depth are as powerful as uniform arithmetic circuits of
polynomial degree; earlier proofs did not work in the ... more >>>

TR95-044 | 18th September 1995
Carsten Damm, Stasys Jukna, Jiri Sgall

#### Some Bounds on Multiparty Communication Complexity of Pointer Jumping

We introduce the model of conservative one-way multiparty complexity
and prove lower and upper bounds on the complexity of pointer jumping.

The pointer jumping function takes as its input a directed layered
graph with a starting node and layers of nodes, and a single edge ... more >>>

TR95-045 | 4th September 1995
Moni Naor, Omer Reingold

#### Synthesizers and Their Application to the Parallel Construction of Pseudo-random Functions

A pseudo-random function is a fundamental cryptographic primitive
that is essential for encryption, identification and authentication.
We present a new cryptographic primitive called pseudo-random
synthesizer and show how to use it in order to get a
parallel construction of a pseudo-random function.
We show an $NC^1$ implementation of synthesizers ... more >>>

TR95-046 | 4th August 1995
Vince Grolmusz

#### On the Power of Circuits with Gates of Low L_1 Norms

We examine the power of Boolean functions with low L_1 norms in several
settings. In large part of the recent literature, the degree of a polynomial
which represents a Boolean function in some way was chosen to be the measure of the complexity of the Boolean function.
However, some functions ... more >>>

TR95-047 | 5th October 1995
Martin Loebbing, Ingo Wegener

#### The Number of Knight's Tours Equals 33,439,123,484,294 -- Counting with Binary Decision Diagrams

An increasing number of results in graph theory, combinatorics and
theoretical computer science is obtained with the help of computers,
e.g. the proof of the Four Colours Theorem or the computation of
certain Ramsey numbers. Binary decision diagrams, known as tools in
hardware verification ... more >>>

TR95-048 | 5th October 1995
Helmut Veith

#### Succinct Representation and Leaf Languages

In this paper, we present stronger results in the theory of succinct
problem representation by boolean circuits, and establish a close
relationship between succinct problems and leaf languages. As
a major tool, we use quantifierfree projection reductions
from descriptive complexity theory.

In particular, we show that the succinct upgrading ... more >>>

TR95-049 | 19th October 1995
Anna Gal, Avi Wigderson

#### Boolean complexity classes vs. their arithmetic analogs

This paper provides logspace and small circuit depth analogs
of the result of Valiant-Vazirani, which is a randomized (or
nonuniform) reduction from NP to its arithmetic analog ParityP.
We show a similar randomized reduction between the
Boolean classes NL and semi-unbounded fan-in Boolean circuits and
their arithmetic counterparts. These ... more >>>

TR95-050 | 15th October 1995
Oded Goldreich, Noam Nisan, Avi Wigderson

#### On Yao's XOR-Lemma

TR95-051 | 16th October 1995
Pascal Koiran

#### VC Dimension in Circuit Complexity

The main result of this paper is a Omega(n^{1/4}) lower bound
on the size of a sigmoidal circuit computing a specific AC^0_2 function.
This is the first lower bound for the computation model of sigmoidal
circuits with unbounded weights. We also give upper and lower bounds for
the ... more >>>

TR95-052 | 4th October 1995
Douglas R. Stinson

#### On the Connections Between Universal Hashing, Combinatorial Designs and Error-Correcting Codes

In this primarily expository
paper, we discuss the connections between two popular and useful
tools in theoretical computer science, namely,
universal hashing and pairwise
independent random variables; and classical combinatorial stuctures
such as error-correcting codes, balanced incomplete block designs,
difference matrices
... more >>>

TR95-053 | 15th October 1995
Petr Slavik

#### Improved Performance of the Greedy Algorithm for the Minimum Set Cover and Minimum Partial Cover Problems

We establish significantly improved bounds on the performance of the greedy
algorithm for approximating MINIMUM SET COVER and MINIMUM PARTIAL COVER. Our
improvements result from a new approach to both problems. In particular,
(a) we improve the known bound on the performance ratio of the greedy ... more >>>

TR95-054 | 24th November 1995
Farid Ablayev, Marek Karpinski

#### On the Power of Randomized Branching Programs

We define the notion of a randomized branching program in
the natural way similar to the definition of a randomized
circuit. We exhibit an explicit function $f_{n}$ for which
we prove that:
1) $f_{n}$ can be computed by polynomial size randomized
... more >>>

TR95-055 | 24th November 1995
Marek Karpinski, Angus Macintyre

#### VC Dimension of Sigmoidal and General Pfaffian Networks

We introduce a new method for proving explicit upper bounds
on the VC Dimension of general functional basis networks,
and prove as an application, for the first time, that the
VC Dimension of analog neural networks with the sigmoidal
activation function $\sigma(y)=1/1+e^{-y}$ ... more >>>

TR95-056 | 26th November 1995
Oded Goldreich

#### Three XOR-Lemmas -- An Exposition

We provide an exposition of three Lemmas which relate
general properties of distributions
with the exclusive-or of certain bit locations.

The first XOR-Lemma, commonly attributed to U.V. Vazirani,
relates the statistical distance of a distribution from uniform
to the maximum bias of the xor of certain bit positions.
more >>>

TR95-057 | 24th November 1995
Dima Grigoriev, Marek Karpinski, A. C. Yao

#### An Exponential Lower Bound on the Size of Algebraic Decision Trees for MAX

We prove an exponential lower bound on the size of any
fixed-degree algebraic decision tree for solving MAX, the
problem of finding the maximum of $n$ real numbers. This
complements the $n-1$ lower bound of Rabin \cite{R72} on
the depth of ... more >>>

TR95-058 | 20th November 1995
Amnon Ta-Shma

#### On Extracting Randomness From Weak Random Sources

We deal with the problem of extracting as much randomness as possible
from a defective random source.
We devise a new tool, a merger'', which is a function that accepts
d strings, one of which is uniformly distributed,
and outputs a single string that is guaranteed ... more >>>

TR95-059 | 21st November 1995

#### The Monotone Theory for the PAC-Model

We show that a DNF formula that has a CNF representation that contains
at least one $1/poly$-heavy''
clause with respect to a distribution $D$ is weakly learnable
under this distribution. So DNF that are not weakly
learnable under the distribution $D$ do not have
any $1/poly$-heavy'' clauses in any of ... more >>>

TR95-060 | 21st November 1995

#### A Subexponential Exact Learning Algorithm for DNF Using Equivalence Queries

We present a $2^{\tilde O(\sqrt{n})}$ time exact learning
algorithm for polynomial size
DNF using equivalence queries only. In particular, DNF
is PAC-learnable in subexponential time under any distribution.
This is the first subexponential time
PAC-learning algorithm for DNF under any distribution.

more >>>

TR95-061 | 27th November 1995
Alexander E. Andreev, Andrea E. F. Clementi, Jose' D. P. Rolim

#### Hitting sets derandomize BPP

Revisions: 1

We show that hitting sets can derandomize any BPP-algorithm.
This gives a positive answer to a fundamental open question in
probabilistic algorithms. More precisely, we present a polynomial
time deterministic algorithm which uses any given hitting set
to approximate the fractions of 1's in the ... more >>>

TR95-062 | 14th December 1995
Amir M. Ben-Amram, Zvi Galil

#### On Data Structure Tradeoffs and an Application to Union-Find

Consider a problem involving updates and queries of a data structure.
Assume that there exists a family of algorithms which exhibit a
tradeoff between query and update time. We demonstrate a general
technique of constructing from such a family
a single algorithm with best amortized time. We indicate some ... more >>>

TR95-063 | 19th December 1995
Dima Grigoriev, Marek Karpinski, Friedhelm Meyer auf der Heide, Roman Smolensky

#### A Lower Bound for Randomized Algebraic Decision Trees

We extend the lower bounds on the depth of algebraic decision trees
to the case of {\em randomized} algebraic decision trees (with
two-sided error) for languages being finite unions of hyperplanes
and the intersections of halfspaces, solving a long standing open
problem. As an application, among ... more >>>

ISSN 1433-8092 | Imprint