Under the auspices of the Computational Complexity Foundation (CCF)

REPORTS > 1999:
All reports in year 1999:
TR99-001 | 4th January 1999
Detlef Sieling

#### The Complexity of Minimizing FBDDs

Revisions: 1

Free Binary Decision Diagrams (FBDDs) are a data structure
for the representation and manipulation of Boolean functions.
Efficient algorithms for most of the important operations are known if
only FBDDs respecting a fixed graph ordering are considered. However,
the size of such an FBDD may strongly depend on the chosen ... more >>>

TR99-002 | 22nd January 1999
Oded Goldreich, Daniele Micciancio, Shmuel Safra and Jean-Pierre Seifert.

#### Approximating shortest lattice vectors is not harder than approximating closest lattice vectors.

returns approximate closest vectors in a lattice, one may find in
polynomial-time approximate shortest vectors in a lattice.
The level of approximation is maintained; that is, for any function
$f$, the following holds:
Suppose that the subroutine, on input a ... more >>>

TR99-003 | 18th December 1998
Stephen A. Fenner, Frederic Green, Steven Homer, Randall Pruim

#### Determining Acceptance Possibility for a Quantum Computation is Hard for the Polynomial Hierarchy

It is shown that determining whether a quantum computation
has a non-zero probability of accepting is at least as hard as the
polynomial time hierarchy. This hardness result also applies to
determining in general whether a given quantum basis state appears
with nonzero amplitude in a superposition, or whether a ... more >>>

TR99-004 | 3rd February 1999
Valentine Kabanets

#### Almost $k$-Wise Independence and Boolean Functions Hard for Read-Once Branching Programs

Revisions: 1

Andreev et al.~\cite{ABCR97} give constructions of Boolean
functions (computable by polynomial-size circuits) that require large
read-once branching program (1-b.p.'s): a function in P that requires
1-b.p. of size at least $2^{n-\polylog(n)}$, a function in quasipolynomial
time that requires 1-b.p. of size at least $2^{n-O(\log n)}$, and a
function in LINSPACE ... more >>>

TR99-005 | 21st December 1998
Michael Schmitt

#### On the Sample Complexity for Nonoverlapping Neural Networks

A neural network is said to be nonoverlapping if there is at most one
edge outgoing from each node. We investigate the number of examples
that a learning algorithm needs when using nonoverlapping neural
networks as hypotheses. We derive bounds for this sample complexity
in terms of the Vapnik-Chervonenkis dimension. ... more >>>

TR99-006 | 10th March 1999
Jin-Yi Cai

#### Some Recent Progress on the Complexity of Lattice Problems

We survey some recent developments in the study of
the complexity of lattice problems. After a discussion of some
problems on lattices which can be algorithmically solved
efficiently, our main focus is the recent progress on complexity
results of intractability. We will discuss Ajtai's worst-case/
average-case connections, NP-hardness and non-NP-hardness,
more >>>

TR99-007 | 10th March 1999
Juraj Hromkovic, Georg Schnitger

#### On the Power of Las Vegas II: Two-Way Finite Automata

The investigation of the computational power of randomized
computations is one of the central tasks of current complexity and
algorithm theory. This paper continues in the comparison of the computational
power of LasVegas computations with the computational power of deterministic
and nondeterministic ones. While for one-way ... more >>>

TR99-008 | 19th March 1999
Eric Allender, Vikraman Arvind, Meena Mahajan

#### Arithmetic Complexity, Kleene Closure, and Formal Power Series

The aim of this paper is to use formal power series techniques to
study the structure of small arithmetic complexity classes such as
GapNC^1 and GapL. More precisely, we apply the Kleene closure of
languages and the formal power series operations of inversion and
root ... more >>>

TR99-009 | 26th March 1999
Marek Karpinski, Rustam Mubarakzjanov

#### A Note on Las Vegas OBDDs

We prove that the error-free (Las Vegas) randomized OBDDs
are computationally equivalent to the deterministic OBDDs.
In contrast, it is known the same is not true for the

more >>>

TR99-010 | 1st April 1999
Eric Allender, Igor E. Shparlinski, Michael Saks

#### A Lower Bound for Primality

Recent work by Bernasconi, Damm and Shparlinski
proved lower bounds on the circuit complexity of the square-free
numbers, and raised as an open question if similar (or stronger)
lower bounds could be proved for the set of prime numbers. In
this short note, we answer this question ... more >>>

TR99-011 | 14th April 1999
Matthias Krause, Petr Savicky, Ingo Wegener

#### Approximations by OBDDs and the variable ordering problem

Ordered binary decision diagrams (OBDDs) and their variants
are motivated by the need to represent Boolean functions
in applications. Research concerning these applications leads
also to problems and results interesting from theoretical
point of view. In this paper, methods from communication
complexity and ... more >>>

TR99-012 | 19th April 1999
Eric Allender, Andris Ambainis, David Mix Barrington, Samir Datta, Huong LeThanh

#### Bounded Depth Arithmetic Circuits: Counting and Closure

Constant-depth arithmetic circuits have been defined and studied
in [AAD97,ABL98]; these circuits yield the function classes #AC^0
and GapAC^0. These function classes in turn provide new
characterizations of the computational power of threshold circuits,
and provide a link between the circuit classes AC^0 ... more >>>

TR99-013 | 28th May 1999
Oded Goldreich, Amit Sahai, Salil Vadhan

#### Can Statistical Zero Knowledge be made Non-Interactive? or On the Relationship of SZK and NISZK

We extend the study of non-interactive statistical zero-knowledge
proofs. Our main focus is to compare the class NISZK of problems
possessing such non-interactive proofs to the class SZK of problems
possessing interactive statistical zero-knowledge proofs. Along these
lines, we first show that if statistical zero knowledge is non-trivial
then so ... more >>>

TR99-014 | 30th May 1999
Alexander Razborov, Nikolay Vereshchagin

#### One Property of Cross-Intersecting Families

Assume that A, B are finite families of n-element sets.
We prove that there is an element that simultaneously
belongs to at least |A|/2n sets
in A and to at least |B|/2n sets in B. We use this result to prove
that for any inconsistent DNF's F,G with OR ... more >>>

TR99-015 | 25th April 1999
Irit Dinur, S. Safra

#### On the hardness of approximating label cover

The label-cover problem was introduced in \cite{ABSS} and shown
there to be quasi-NP-hard to approximate to within a factor of
$2^{\log^{1-\delta}n}$ for any {\em constant} $\delta>0$. This
combinatorial graph problem has been utilized \cite{ABSS,GM,ABMP}
for showing hardness-of-approximation of numerous problems. We
present a direct combinatorial reduction from low
error-probability PCP ... more >>>

TR99-016 | 25th April 1999
Irit Dinur

#### Approximating SVP_\infty to within Almost-Polynomial Factors is NP-hard

This paper shows SVP_\infty and CVP_\infty to be NP-hard to approximate
to within any factor up to $n^{1/\log\log n}$. This improves on the
best previous result \cite{ABSS} that showed quasi-NP-hardness for
smaller factors, namely $2^{\log^{1-\epsilon}n}$ for any constant
$\epsilon>0$. We show a direct reduction from SAT to these
problems, that ... more >>>

TR99-017 | 4th June 1999
Yevgeniy Dodis, Oded Goldreich, Eric Lehman, Sofya Raskhodnikova, Dana Ron, Alex Samorodnitsky

#### Improved Testing Algorithms for Monotonicity.

Revisions: 1

We present improved algorithms for testing monotonicity of functions.
Namely, given the ability to query an unknown function $f$, where
$\Sigma$ and $\Xi$ are finite ordered sets, the test always accepts a
monotone $f$, and rejects $f$ with high probability if it is $\e$-far
from being monotone (i.e., every ... more >>>

TR99-018 | 8th June 1999
Manindra Agrawal, Somenath Biswas

#### Reducing Randomness via Chinese Remaindering

We give new randomized algorithms for testing multivariate polynomial
identities over finite fields and rationals. The algorithms use
\lceil \sum_{i=1}^n \log(d_i+1)\rceil (plus \lceil\log\log C\rceil
in case of rationals where C is the largest coefficient)
random bits to test if a
polynomial P(x_1, ..., x_n) is zero where d_i is ... more >>>

TR99-019 | 7th June 1999
Detlef Sieling

#### Lower Bounds for Linear Transformed OBDDs and FBDDs

Linear Transformed Ordered Binary Decision Diagrams (LTOBDDs) have
been suggested as a generalization of OBDDs for the representation and
manipulation of Boolean functions. Instead of variables as in the
case of OBDDs parities of variables may be tested at the nodes of an
LTOBDD. By this extension it is ... more >>>

TR99-020 | 9th June 1999
Marek Karpinski

#### Randomized Complexity of Linear Arrangements and Polyhedra

We survey some of the recent results on the complexity of recognizing
n-dimensional linear arrangements and convex polyhedra by randomized
algebraic decision trees. We give also a number of concrete applications
of these results. In particular, we derive first nontrivial, in fact

TR99-021 | 8th April 1999
Igor E. Shparlinski

#### ON THE UNIFORMITY OF DISTRIBUTION OF A CERTAIN PSEUDO-RANDOM FUNCTION

We show that a pseudo-random number generator,
introduced recently by M. Naor and O. Reingold,
possess one more attractive and useful property.
Namely, it is proved that for almost all values of parameters it
produces a uniformly distributed sequence.
The proof is based on some recent bounds of exponential
more >>>

TR99-022 | 14th June 1999
Eli Ben-Sasson, Avi Wigderson

#### Short Proofs are Narrow - Resolution made Simple

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

TR99-023 | 16th June 1999
Amir Shpilka, Avi Wigderson

#### Depth-3 Arithmetic Formulae over Fields of Characteristic Zero

In this paper we prove near quadratic lower bounds for
depth-3 arithmetic formulae over fields of characteristic zero.
Such bounds are obtained for the elementary symmetric
functions, the (trace of) iterated matrix multiplication, and the
determinant. As corollaries we get the first nontrivial lower
bounds for ... more >>>

TR99-024 | 25th June 1999
Oded Goldreich, Silvio Micali.

#### Interleaved Zero-Knowledge in the Public-Key Model.

We introduce the notion of Interleaved Zero-Knowledge (iZK),
a new security measure for cryptographic protocols which strengthens
the classical notion of zero-knowledge, in a way suitable for multiple
concurrent executions in an asynchronous environment like the internet.
We prove that iZK protocols are robust: they are parallelizable'',
and ... more >>>

TR99-025 | 2nd July 1999

#### Linear Consistency Testing

We extend the notion of linearity testing to the task of checking
linear-consistency of multiple functions. Informally, functions
are linear'' if their graphs form straight lines on the plane.
Two such functions are consistent'' if the lines have the same
slope. We propose a variant of a test of ... more >>>

TR99-026 | 7th July 1999
Miklos Ajtai

#### A Non-linear Time Lower Bound for Boolean Branching Programs

We prove that for all positive integer $k$ and for all
sufficiently small $\epsilon >0$ if $n$ is sufficiently large
then there is no Boolean (or $2$-way) branching program of size
less than $2^{\epsilon n}$ which for all inputs
$X\subseteq \lbrace 0,1,...,n-1\rbrace$ computes in time $kn$
the parity of ... more >>>

TR99-027 | 17th July 1999
Marek Karpinski, Igor E. Shparlinski

#### On the computational hardness of testing square-freeness of sparse polynomials

We show that deciding square-freeness of a sparse univariate
polynomial over the integer and over the algebraic closure of a
finite field is NP-hard. We also discuss some related open

more >>>

TR99-028 | 30th August 1999
Stefan Edelkamp, Ingo Wegener

#### On the performance of WEAK-HEAPSORT

Dutton presents a further HEAPSORT variant called
WEAK-HEAPSORT which also contains a new data structure for
priority queues. The sorting algorithm and the underlying
data structure ara analyzed showing that WEAK-HEAPSORT is
the best HEAPSORT variant and that it has a lot of nice
more >>>

TR99-029 | 31st August 1999
Ilya Dumer, Daniele Micciancio, Madhu Sudan

#### Hardness of approximating the minimum distance of a linear code

We show that the minimum distance of a linear code (or
equivalently, the weight of the lightest codeword) is
not approximable to within any constant factor in random polynomial
time (RP), unless NP equals RP.
Under the stronger assumption that NP is not contained in RQP
(random ... more >>>

TR99-030 | 9th July 1999
Meena Mahajan, P R Subramanya, V Vinay

#### A Combinatorial Algorithm for Pfaffians

The Pfaffian of an oriented graph is closely linked to
Perfect Matching. It is also naturally related to the determinant of
an appropriately defined matrix. This relation between Pfaffian and
determinant is usually exploited to give a fast algorithm for
computing Pfaffians.

We present the first completely combinatorial algorithm for ... more >>>

TR99-031 | 2nd September 1999
Hans-Joachim Böckenhauer, Juraj Hromkovic, Ralf Klasing, Sebastian Seibert, Walter Unger

#### Towards the Notion of Stability of Approximation for Hard Optimization Tasks and the Traveling Salesman Problem

The investigation of the possibility to efficiently compute
approximations of hard optimization problems is one of the central
and most fruitful areas of current algorithm and complexity theory.
The aim of this paper is twofold. First, we introduce the notion of
stability of approximation algorithms. This notion is shown to ... more >>>

TR99-032 | 7th July 1999
Cristopher Moore

#### Quantum Circuits: Fanout, Parity, and Counting

We propose definitions of $\QAC^0$, the quantum analog of the
classical class $\AC^0$ of constant-depth circuits with AND and OR
gates of arbitrary fan-in, and $\QACC^0[q]$, the analog of the class
$\ACC^0[q]$ where $\Mod_q$ gates are also allowed. We show that it is
possible to make a cat' state on ... more >>>

TR99-033 | 19th August 1999
Vikraman Arvind, J. Köbler

#### Graph Isomorphism is Low for ZPP$^{\mbox{\rm NP}}$ and other Lowness results.

We show the following new lowness results for the probabilistic
class ZPP$^{\mbox{\rm NP}}$.

1. The class AM$\cap$coAM is low for ZPP$^{\mbox{\rm NP}}$.
As a consequence it follows that Graph Isomorphism and several
group-theoretic problems known to be in AM$\cap$coAM are low for
ZPP$^{\mbox{\rm ... 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 >>> TR99-035 | 6th July 1999 Leonard Schulman #### Clustering for Edge-Cost Minimization We address the problem of partitioning a set of$n$points into clusters, so as to minimize the sum, over all intracluster pairs of points, of the cost associated with each pair. We obtain a randomized approximation algorithm for this problem, for the cost functions$\ell_2^2,\ell_1$and$\ell_2$, as ... more >>> TR99-036 | 6th September 1999 Edward Hirsch #### A New Algorithm for MAX-2-SAT Revisions: 2 Recently there was a significant progress in proving (exponential-time) worst-case upper bounds for the propositional satisfiability problem (SAT). MAX-SAT is an important generalization of SAT. Several upper bounds were obtained for MAX-SAT and its NP-complete subproblems. In particular, Niedermeier and Rossmanith recently ... more >>> TR99-037 | 27th August 1999 Johan Håstad, Mats Näslund #### The Security of all RSA and Discrete Log Bits We study the security of individual bits in an RSA encrypted message$E_N(x)$. We show that given$E_N(x)$, predicting any single bit in$x$with only a non-negligible advantage over the trivial guessing strategy, is (through a polynomial time reduction) as hard as breaking ... more >>> TR99-038 | 27th August 1999 Peter Jonsson, Paolo Liberatore #### On the Complexity of Finding Satisfiable Subinstances in Constraint Satisfaction We study the computational complexity of an optimization version of the constraint satisfaction problem: given a set$F$of constraint functions, an instance consists of a set of variables$V$related by constraints chosen from$F$and a natural number$k$. The problem is to decide whether there exists a ... more >>> TR99-039 | 24th September 1999 Johan Håstad #### On approximating CSP-B We prove that any constraint satisfaction problem where each variable appears a bounded number of times admits a nontrivial polynomial time approximation algorithm. more >>> TR99-040 | 20th October 1999 Michael Alekhnovich, Eli Ben-Sasson, Alexander Razborov, Avi Wigderson #### Space Complexity in Propositional Calculus We study space complexity in the framework of propositional proofs. We consider a natural model analogous to Turing machines with a read-only input tape, and such popular propositional proof systems as Resolution, Polynomial Calculus and Frege systems. We propose two different space measures, corresponding to the maximal number of bits, ... more >>> TR99-041 | 22nd August 1999 Oliver Kullmann #### Investigating a general hierarchy of polynomially decidable classes of CNF's based on short tree-like resolution proofs Revisions: 2 A relativized hierarchy of conjunctive normal forms is introduced, recognizable and SAT decidable in polynomial time. The corresponding hardness parameter, the first level of inclusion in the hierarchy, is studied in detail, admitting several characterizations, e.g., using pebble games, the space complexity of (relativized) tree-like ... more >>> TR99-042 | 24th October 1999 Ran Canetti, Oded Goldreich, Silvio Micali. #### Resettable Zero-Knowledge. Revisions: 1 We introduce the notion of Resettable Zero-Knowledge (rZK), a new security measure for cryptographic protocols which strengthens the classical notion of zero-knowledge. In essence, an rZK protocol is one that remains zero knowledge even if an adeversary can interact with the prover many times, each time ... more >>> TR99-043 | 5th November 1999 Venkatesan Guruswami #### The Approximability of Set Splitting Problems and Satisfiability Problems with no Mixed Clauses We prove hardness results for approximating set splitting problems and also instances of satisfiability problems which have no `mixed'' clauses, i.e all clauses have either all their literals unnegated or all of them negated. Recent results of Hastad imply tight hardness results for set splitting when all sets ... more >>> TR99-044 | 30th September 1999 Farid Ablayev #### On Complexity of Regular$(1,+k)$-Branching Programs A regular$(1,+k)$-branching program ($(1,+k)$-ReBP) is an ordinary branching program with the following restrictions: (i) along every consistent path at most$k$variables are tested more than once, (ii) for each node$v$on all paths from the source to$v$the same set$X(v)\subseteq X\$ of variables is ... more >>>

TR99-045 | 16th November 1999
Valentine Kabanets, Jin-Yi Cai

#### Circuit Minimization Problem

We study the complexity of the circuit minimization problem:
given the truth table of a Boolean function f and a parameter s, decide
whether f can be realized by a Boolean circuit of size at most s. We argue
why this problem is unlikely to be in P (or ... more >>>

TR99-046 | 17th November 1999
Ran Raz, Omer Reingold, Salil Vadhan

#### Extracting All the Randomness and Reducing the Error in Trevisan's Extractors

We give explicit constructions of extractors which work for a source of
any min-entropy on strings of length n. These extractors can extract any
constant fraction of the min-entropy using O(log^2 n) additional random
bits, and can extract all the min-entropy using O(log^3 n) additional
random bits. Both of these ... more >>>

TR99-047 | 10th November 1999
Wolfgang Slany

#### Graph Ramsey games

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

TR99-048 | 7th December 1999
Beate Bollig, Ingo Wegener

#### Asymptotically Optimal Bounds for OBDDs and the Solution of Some Basic OBDD Problems

Ordered binary decision diagrams (OBDDs) are nowadays the
most common dynamic data structure or representation type
for Boolean functions. Among the many areas of application
are verification, model checking, and computer aided design.
For many functions it is easy to estimate the OBDD ... more >>>

ISSN 1433-8092 | Imprint