All reports in year 1999:

__
TR99-001
| 4th January 1999
__

Detlef Sieling#### The Complexity of Minimizing FBDDs

Revisions: 1

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

__
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

__
TR99-004
| 3rd February 1999
__

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

Revisions: 1

__
TR99-005
| 21st December 1998
__

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

__
TR99-006
| 10th March 1999
__

Jin-Yi Cai#### Some Recent Progress on the Complexity of Lattice Problems

__
TR99-007
| 10th March 1999
__

Juraj Hromkovic, Georg Schnitger#### On the Power of Las Vegas II: Two-Way Finite Automata

__
TR99-008
| 19th March 1999
__

Eric Allender, Vikraman Arvind, Meena Mahajan#### Arithmetic Complexity, Kleene Closure, and Formal Power Series

Revisions: 1
,
Comments: 1

__
TR99-009
| 26th March 1999
__

Marek Karpinski, Rustam Mubarakzjanov#### A Note on Las Vegas OBDDs

__
TR99-010
| 1st April 1999
__

Eric Allender, Igor E. Shparlinski, Michael Saks#### A Lower Bound for Primality

Comments: 1

__
TR99-011
| 14th April 1999
__

Matthias Krause, Petr Savicky, Ingo Wegener#### Approximations by OBDDs and the variable ordering problem

__
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

__
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

__
TR99-014
| 30th May 1999
__

Alexander Razborov, Nikolay Vereshchagin#### One Property of Cross-Intersecting Families

__
TR99-015
| 25th April 1999
__

Irit Dinur, S. Safra#### On the hardness of approximating label cover

__
TR99-016
| 25th April 1999
__

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

__
TR99-017
| 4th June 1999
__

Yevgeniy Dodis, Oded Goldreich, Eric Lehman, Sofya Raskhodnikova, Dana Ron, Alex Samorodnitsky#### Improved Testing Algorithms for Monotonicity.

Revisions: 1

__
TR99-018
| 8th June 1999
__

Manindra Agrawal, Somenath Biswas#### Reducing Randomness via Chinese Remaindering

__
TR99-019
| 7th June 1999
__

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

__
TR99-020
| 9th June 1999
__

Marek Karpinski#### Randomized Complexity of Linear Arrangements and Polyhedra

__
TR99-021
| 8th April 1999
__

Igor E. Shparlinski#### ON THE UNIFORMITY OF DISTRIBUTION OF A CERTAIN PSEUDO-RANDOM FUNCTION

__
TR99-022
| 14th June 1999
__

Eli Ben-Sasson, Avi Wigderson#### Short Proofs are Narrow - Resolution made Simple

__
TR99-023
| 16th June 1999
__

Amir Shpilka, Avi Wigderson#### Depth-3 Arithmetic Formulae over Fields of Characteristic Zero

__
TR99-024
| 25th June 1999
__

Oded Goldreich, Silvio Micali.#### Interleaved Zero-Knowledge in the Public-Key Model.

Revisions: 1
,
Comments: 1

__
TR99-025
| 2nd July 1999
__

Yonatan Aumann, Johan Hastad, Michael O. Rabin, Madhu Sudan#### Linear Consistency Testing

__
TR99-026
| 7th July 1999
__

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

__
TR99-027
| 17th July 1999
__

Marek Karpinski, Igor E. Shparlinski#### On the computational hardness of testing square-freeness of sparse polynomials

__
TR99-028
| 30th August 1999
__

Stefan Edelkamp, Ingo Wegener#### On the performance of WEAK-HEAPSORT

__
TR99-029
| 31st August 1999
__

Ilya Dumer, Daniele Micciancio, Madhu Sudan#### Hardness of approximating the minimum distance of a linear code

__
TR99-030
| 9th July 1999
__

Meena Mahajan, P R Subramanya, V Vinay#### A Combinatorial Algorithm for Pfaffians

__
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

__
TR99-032
| 7th July 1999
__

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

__
TR99-033
| 19th August 1999
__

Vikraman Arvind, J. Köbler#### Graph Isomorphism is Low for ZPP$^{\mbox{\rm NP}}$ and other Lowness results.

__
TR99-034
| 30th August 1999
__

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

__
TR99-035
| 6th July 1999
__

Leonard Schulman#### Clustering for Edge-Cost Minimization

__
TR99-036
| 6th September 1999
__

Edward Hirsch#### A New Algorithm for MAX-2-SAT

Revisions: 2

__
TR99-037
| 27th August 1999
__

Johan Hastad, Mats Näslund#### The Security of all RSA and Discrete Log Bits

__
TR99-038
| 27th August 1999
__

Peter Jonsson, Paolo Liberatore#### On the Complexity of Finding Satisfiable Subinstances in Constraint Satisfaction

__
TR99-039
| 24th September 1999
__

Johan Hastad#### On approximating CSP-B

__
TR99-040
| 20th October 1999
__

Michael Alekhnovich, Eli Ben-Sasson, Alexander Razborov, Avi Wigderson#### Space Complexity in Propositional Calculus

__
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

__
TR99-042
| 24th October 1999
__

Ran Canetti, Oded Goldreich, Silvio Micali.#### Resettable Zero-Knowledge.

Revisions: 1

__
TR99-043
| 5th November 1999
__

Venkatesan Guruswami#### The Approximability of Set Splitting Problems and Satisfiability Problems with no Mixed Clauses

__
TR99-044
| 30th September 1999
__

Farid Ablayev#### On Complexity of Regular $(1,+k)$-Branching Programs

__
TR99-045
| 16th November 1999
__

Valentine Kabanets, Jin-Yi Cai#### Circuit Minimization Problem

__
TR99-046
| 17th November 1999
__

Ran Raz, Omer Reingold, Salil Vadhan#### Extracting All the Randomness and Reducing the Error in Trevisan's Extractors

__
TR99-047
| 10th November 1999
__

Wolfgang Slany#### Graph Ramsey games

__
TR99-048
| 7th December 1999
__

Beate Bollig, Ingo Wegener#### Asymptotically Optimal Bounds for OBDDs and the Solution of Some Basic OBDD Problems

Detlef Sieling

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

Oded Goldreich, Daniele Micciancio, Shmuel Safra and Jean-Pierre Seifert.

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

Stephen A. Fenner, Frederic Green, Steven Homer, Randall Pruim

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

Valentine Kabanets

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

Michael Schmitt

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

Jin-Yi Cai

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

Juraj Hromkovic, Georg Schnitger

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

Eric Allender, Vikraman Arvind, Meena Mahajan

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

Marek Karpinski, Rustam Mubarakzjanov

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.

Eric Allender, Igor E. Shparlinski, Michael Saks

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

Matthias Krause, Petr Savicky, Ingo Wegener

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

Eric Allender, Andris Ambainis, David Mix Barrington, Samir Datta, Huong LeThanh

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

Oded Goldreich, Amit Sahai, Salil Vadhan

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

Alexander Razborov, Nikolay Vereshchagin

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

Irit Dinur, S. Safra

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

Irit Dinur

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

Yevgeniy Dodis, Oded Goldreich, Eric Lehman, Sofya Raskhodnikova, Dana Ron, Alex Samorodnitsky

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

Manindra Agrawal, Somenath Biswas

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

Detlef Sieling

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

Marek Karpinski

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

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

Eli Ben-Sasson, Avi Wigderson

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

Amir Shpilka, Avi Wigderson

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

Oded Goldreich, Silvio Micali.

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

Yonatan Aumann, Johan Hastad, Michael O. Rabin, Madhu Sudan

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

Miklos Ajtai

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

Marek Karpinski, Igor E. Shparlinski

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.

Stefan Edelkamp, Ingo Wegener

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

Ilya Dumer, Daniele Micciancio, Madhu Sudan

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

Meena Mahajan, P R Subramanya, V Vinay

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

Hans-Joachim Böckenhauer, Juraj Hromkovic, Ralf Klasing, Sebastian Seibert, Walter Unger

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

Cristopher Moore

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

Vikraman Arvind, J. Köbler

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

Wolfgang Merkle

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

Leonard Schulman

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

Edward Hirsch

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

Johan Hastad, Mats Näslund

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

Peter Jonsson, Paolo Liberatore

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

Johan Hastad

We prove that any constraint satisfaction problem

where each variable appears a bounded number of

times admits a nontrivial polynomial time approximation

algorithm.

Michael Alekhnovich, Eli Ben-Sasson, Alexander Razborov, Avi Wigderson

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

Oliver Kullmann

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

Ran Canetti, Oded Goldreich, Silvio Micali.

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

Venkatesan Guruswami

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

Farid Ablayev

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

Valentine Kabanets, Jin-Yi Cai

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

Ran Raz, Omer Reingold, Salil Vadhan

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

Wolfgang Slany

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

Beate Bollig, Ingo Wegener

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