Electronic Colloquium on Computational Complexity
Login | Register | Classic Style

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.

We show that given oracle access to a subroutine which
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

Revisions: 1 , Comments: 1

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
Las Vegas read-once branching programs.

more >>>

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

A Lower Bound for Primality

Comments: 1

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

Comments: 1

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
quadratic, ... more >>>

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


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.

Revisions: 1 , Comments: 1

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
Yonatan Aumann, Johan Hastad, Michael O. Rabin, Madhu Sudan

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
problems about sparse polynomials.

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 J. 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 Hastad, 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 Hastad

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

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