Electronic Colloquium on Computational Complexity
Login | Register | Classic Style

REPORTS > 2000:
All reports in year 2000:
TR00-001 | 14th January 2000
Piotr Berman, Moses Charikar, Marek Karpinski

On-Line Load Balancing for Related Machines

We consider the problem of scheduling permanent jobs on related machines
in an on-line fashion. We design a new algorithm that achieves the
competitive ratio of $3+\sqrt{8}\approx 5.828$ for the deterministic
version, and $3.31/\ln 2.155 \approx 4.311$ for its randomized variant,
improving the previous competitive ratios ... more >>>

TR00-002 | 23rd December 1999
Michael Schmitt

Lower Bounds on the Complexity of Approximating Continuous Functions by Sigmoidal Neural Networks

We calculate lower bounds on the size of sigmoidal neural networks
that approximate continuous functions. In particular, we show that
for the approximation of polynomials the network size has to grow
as $\Omega((\log k)^{1/4})$ where $k$ is the degree of the polynomials.
This bound is ... more >>>

TR00-003 | 26th November 1999
Matthias Krause, Hans Ulrich Simon

Determining the Optimal Contrast for Secret Sharing Schemes in Visual Cryptography

This paper shows that the largest possible contrast C(k,n)
in a k-out-of-n secret sharing scheme is approximately
4^(-(k-1)). More precisely, we show that
4^(-(k-1)) <= C_{k,n} <= 4^(-(k-1))}n^k/(n(n-1)...(n-(k-1))).
This implies that the largest possible contrast equals
4^(-(k-1)) in the limit when n approaches ... more >>>

TR00-004 | 14th January 2000
Oded Goldreich, Salil Vadhan, Avi Wigderson

Simplified derandomization of BPP using a hitting set generator.

A hitting-set generator is a deterministic
algorithm which generates a set of strings that intersects
every dense set recognizable by a small circuit.
A polynomial time hitting-set generator readily implies $RP=P$.
Andreev \etal\/ (ICALP'96, and JACM 1998)
showed that if polynomial-time hitting-set
generator in fact implies ... more >>>

TR00-005 | 17th January 2000
Eli Ben-Sasson, Russell Impagliazzo, Avi Wigderson

Near-Optimal Separation of Treelike and General Resolution

We present the best known separation
between tree-like and general resolution, improving
on the recent $\exp(n^\epsilon)$ separation of \cite{BEGJ98}.
This is done by constructing a natural family of contradictions, of
size $n$, that have $O(n)$-size resolution
refutations, but only $\exp (\Omega(n/\log n))$-size tree-like refutations.
This result ... more >>>

TR00-006 | 26th January 2000
E.A. Okol'nishnikiva

On operations of geometrical projection and monotone extension

Some operations over Boolean functions are considered. It is shown that
the operation of the geometrical projection and the operation of the
monotone extension can increase the complexity of Boolean functions for
formulas in each finite basis, for switching networks, for branching
programs, and read-$k$-times ... more >>>

TR00-007 | 14th December 1999
Pavlos S. Efraimidis, Paul Spirakis

Randomized Approximation Schemes for Scheduling Unrelated Parallel Machines

The problem of Scheduling $n$ Independent Jobs
on $m$ Unrelated Parallel Machines, when $m$
is fixed, is considered. The standard problem
of minimizing the makespan of the schedule
(SUM) and the bicriteria problem of scheduling
with bounded makespan and cost (SUMC), are
addressed, and randomized fully linear time
more >>>

TR00-008 | 20th January 2000
Albert Atserias, Nicola Galesi, Ricard Gavaldà

Monotone Proofs of the Pigeon Hole Principle

We study the complexity of proving the Pigeon Hole
Principle (PHP) in a monotone variant of the Gentzen Calculus, also
known as Geometric Logic. We show that the standard encoding
of the PHP as a monotone sequent admits quasipolynomial-size proofs
in this system. This result is a consequence of ... more >>>

TR00-009 | 21st February 2000
Russell Impagliazzo, Ronen Shaltiel, Avi Wigderson

Extractors and pseudo-random generators with optimal seed length

We give the first construction of a pseudo-random generator with
optimal seed length that uses (essentially) arbitrary hardness.
It builds on the novel recursive use of the NW-generator in
a previous paper by the same authors, which produced many optimal
generators one of which was pseudo-random. This is achieved ... more >>>

TR00-010 | 12th January 2000
Amitabha Roy, Christopher Wilson

Supermodels and Closed Sets

A {\em supermodel} is a satisfying assignment of a boolean formula
for which any small alteration, such as a single bit flip, can be
repaired by another small alteration, yielding a nearby
satisfying assignment. We study computational problems associated
with super models and some generalizations thereof. For general
formulas, ... more >>>

TR00-011 | 27th January 2000
Sotiris Nikoletseas, Paul Spirakis

Efficient Communication Establishment in Extremely Unreliable Large Networks

We consider here a large network of $n$ nodes which supports
only the following unreliable basic communication primitive:
when a node requests communication then this request
{\em may fail}, independently of other requests, with probability
$f<1$. Even if it succeeds, the request is answered by returning
a stable link to ... more >>>

TR00-012 | 14th February 2000
Ke Yang

Integer Circuit Evaluation is PSPACE-complete

In this paper, we address the problem of evaluating the
Integer Circuit (IC), or the $\{\cup, \times, +\}$-circuit over
the set of natural numbers. The problem is a natural extension
to the integer expression by Stockmeyer and Mayer, and is also studied
by Mckenzie, Vollmer and Wagner in ... more >>>

TR00-013 | 14th February 2000
Daniel Král

Algebraic and Uniqueness Properties of Parity Ordered Binary Decision Diagrams and their Generalization

Ordered binary decision diagrams (OBDDs) and parity ordered binary
decision diagrams have proved their importance as data structures
representing Boolean functions. In addition to parity OBDDs we study
their generalization which we call parity AOBDDs, give the algebraic
characterization theorem and compare their minimal size to the size
more >>>

TR00-014 | 16th February 2000
Matthias Krause, Stefan Lucks

On Learning versus Distinguishing and the Minimal Hardware Complexity of Pseudorandom Function Generators

A set $F$ of $n$-ary Boolean functions is called a pseudorandom function generator
(PRFG) if communicating
with a randomly chosen secret function from $F$ cannot be
efficiently distinguished from communicating with a truly random function.
We ask for the minimal hardware complexity of a PRFG. This question ... more >>>

TR00-015 | 16th February 2000
Andrej Muchnik, Alexej Semenov

Multi-conditional Descriptions and Codes in Kolmogorov Complexity

TR00-016 | 29th February 2000
Mikhail V. Vyugin

Information Distance and Conditional Complexities

C.H.~Bennett, P.~G\'acs, M.~Li, P.M.B.~Vit\'anyi, and W.H.~Zurek
have defined information distance between two strings $x$, $y$
d(x,y)=\max\{ K(x|y), K(y|x) \}
where $K(x|y)$ is the conditional Kolmogorov complexity.
It is easy to see that for any string $x$ and any integer $n$
there is a string $y$ ... more >>>

TR00-017 | 3rd March 2000
Valentin E. Brimkov, Stefan S. Dantchev

On the Algebraic Complexity of Integer Programming

In the framework of the Blum-Shub-Smale real number model \cite{BSS}, we study the {\em algebraic complexity} of the integer linear programming problem
(ILP$_{\bf R}$) : Given a matrix $A \in {\bf R}^{m \times n}$ and vectors
$b \in {\bf R}^m$, $d \in {\bf R}^n$, decide if there is $x ... more >>>

TR00-018 | 16th February 2000
Oliver Kullmann

An application of matroid theory to the SAT problem

A basic property of minimally unsatisfiable clause-sets F is that
c(F) >= n(F) + 1 holds, where c(F) is the number of clauses, and
n(F) the number of variables. Let MUSAT(k) be the class of minimally
unsatisfiable clause-sets F with c(F) <= n(F) + k.

Poly-time decision algorithms are known ... more >>>

TR00-019 | 20th March 2000
Edward Hirsch

Worst-case time bounds for MAX-k-SAT w.r.t. the number of variables using local search

During the past three years there was an explosion of algorithms
solving MAX-SAT and MAX-2-SAT in worst-case time of the order
c^K, where c<2 is a constant, and K is the number of clauses
in the input formula. Such bounds w.r.t. the number of variables
instead of the number of ... more >>>

TR00-020 | 27th March 2000
Oded Goldreich, Dana Ron

On Testing Expansion in Bounded-Degree Graphs

We consider testing graph expansion in the bounded-degree graph model.
Specifically, we refer to algorithms for testing whether the graph
has a second eigenvalue bounded above by a given threshold
or is far from any graph with such (or related) property.

We present a natural algorithm aimed ... more >>>

TR00-021 | 19th April 2000
Uriel Feige, Marek Karpinski, Michael Langberg

Improved Approximation of MAX-CUT on Graphs of Bounded Degree

We analyze the addition of a simple local improvement step to various known
randomized approximation algorithms.
Let $\alpha \simeq 0.87856$ denote the best approximation ratio currently
known for the Max Cut problem on general graphs~\cite{GW95}.
We consider a semidefinite relaxation of the Max Cut problem,
round it using the ... more >>>

TR00-022 | 2nd May 2000
Rosario Gennaro, Luca Trevisan

Lower bounds on the efficiency of generic cryptographic constructions

We present lower bounds on the efficiency of
constructions for Pseudo-Random Generators (PRGs) and
Universal One-Way Hash Functions (UOWHFs) based on
black-box access to one-way permutations. Our lower bounds are tight as
they match the efficiency of known constructions.

A PRG (resp. UOWHF) construction based on black-box access is
a ... more >>>

TR00-023 | 11th May 2000
Michael Alekhnovich, Eli Ben-Sasson, Alexander Razborov, Avi Wigderson

Pseudorandom Generators in Propositional Proof Complexity

We call a pseudorandom generator $G_n:\{0,1\}^n\to \{0,1\}^m$ {\em
hard} for a propositional proof system $P$ if $P$ can not efficiently
prove the (properly encoded) statement $G_n(x_1,\ldots,x_n)\neq b$ for
{\em any} string $b\in\{0,1\}^m$. We consider a variety of
``combinatorial'' pseudorandom generators inspired by the
Nisan-Wigderson generator on the one hand, and ... more >>>

TR00-024 | 16th May 2000
Amihood Amir, Richard Beigel, William Gasarch

Some Connections between Bounded Query Classes and Non-Uniform Complexity

Let A(x) be the characteristic function of A. Consider the function
F_k^A(x_1,...,x_k) = A(x_1)...A(x_k). We show that if F_k^A can be
computed with fewer than k queries to some set X, then A can be
computed by polynomial size circuits. A generalization of this result
has applications to bounded query ... more >>>

TR00-025 | 20th May 2000
Paul Beame, Michael Saks, Xiaodong Sun, Erik Vee

Super-linear time-space tradeoff lower bounds for randomized computation

We prove the first time-space lower bound tradeoffs for randomized
computation of decision problems. The bounds hold even in the
case that the computation is allowed to have arbitrary probability
of error on a small fraction of inputs. Our techniques are an
extension of those used by Ajtai in his ... more >>>

TR00-026 | 11th April 2000
Andrei Romashchenko, Alexander Shen, Nikolay Vereshchagin

Combinatorial Interpretation of Kolmogorov Complexity

The very first Kolmogorov's paper on algorithmic
information theory was entitled `Three approaches to the
definition of the quantity of information'. These three
approaches were called combinatorial, probabilistic and
algorithmic. Trying to establish formal connections
between combinatorial and algorithmic approaches, we
prove that any ... more >>>

TR00-027 | 11th April 2000
Pavol Duris, Juraj Hromkovic, Katsushi Inoue

A Separation of Determinism, Las Vegas and Nondeterminism for Picture Recognition

The investigation of the computational power of randomized computations
is one of the central tasks of current complexity and algorithm theory.
In this paper for the first time a "strong" separation between the power
of determinism, Las Vegas randomization, and nondeterminism for a compu-
ting model is proved. The computing ... more >>>

TR00-028 | 17th April 2000
Lance Fortnow, Dieter van Melkebeek

Time-Space Tradeoffs for Nondeterministic Computation

We show new tradeoffs for satisfiability and nondeterministic
linear time. Satisfiability cannot be solved on general purpose
random-access Turing machines in time $n^{1.618}$ and space
$n^{o(1)}$. This improves recent results of Lipton and Viglas and

more >>>

TR00-029 | 30th April 2000
Ran Raz, Amir Shpilka

Lower Bounds for Matrix Product, in Bounded Depth Circuits with Arbitrary Gates

Revisions: 1

We prove super-linear lower bounds for the number of edges
in constant depth circuits with $n$ inputs and up to $n$ outputs.
Our lower bounds are proved for all types of constant depth
circuits, e.g., constant depth arithmetic circuits, constant depth
threshold circuits ... more >>>

TR00-030 | 31st May 2000

A Simple Model for Neural Computation with Firing Rates and Firing Correlations

A simple extension of standard neural network models is introduced that
provides a model for neural computations that involve both firing rates and
firing correlations. Such extension appears to be useful since it has been
shown that firing correlations play a significant computational role in
many biological neural systems. Standard ... more >>>

TR00-031 | 31st May 2000
Eduardo D. Sontag

Neural Systems as Nonlinear Filters

Experimental data show that biological synapses behave quite
differently from the symbolic synapses in all common artificial
neural network models. Biological synapses are dynamic, i.e., their
``weight'' changes on a short time scale by several hundred percent
in dependence of the past input to the synapse. ... more >>>

TR00-032 | 31st May 2000

On the Computational Power of Winner-Take-All

In this paper the computational power of a new type of gate is studied:
winner-take-all gates. This work is motivated by the fact that the cost
of implementing a winner-take-all gate in analog VLSI is about the same
as that of implementing a threshold gate.

We show that ... more >>>

TR00-033 | 22nd May 2000
Jan Krajicek

Tautologies from pseudo-random generators

Revisions: 1

We consider tautologies formed from a pseudo-random
number generator, defined in Kraj\'{\i}\v{c}ek \cite{Kra99}
and in Alekhnovich \cite{ABRW}.
We explain a strategy of proving their hardness for EF via
a conjecture about bounded arithmetic formulated
in Kraj\'{\i}\v{c}ek \cite{Kra99}. Further we give a
purely finitary statement, in a ... more >>>

TR00-034 | 5th June 2000
Valentine Kabanets, Charles Rackoff, Stephen Cook

Efficiently Approximable Real-Valued Functions

We consider a class, denoted APP, of real-valued functions
f:{0,1}^n\rightarrow [0,1] such that f can be approximated, to
within any epsilon>0, by a probabilistic Turing machine running in
time poly(n,1/epsilon). We argue that APP can be viewed as a
generalization of BPP, and show that APP contains a natural
complete ... more >>>

TR00-035 | 6th June 2000
Nikolay Vereshchagin, Mikhail V. Vyugin

Independent minimum length programs to translate between given strings

A string $p$ is called a program to compute $y$ given $x$
if $U(p,x)=y$, where $U$ denotes universal programming language.
Kolmogorov complexity $K(y|x)$ of $y$ relative to $x$
is defined as minimum length of
a program to compute $y$ given $x$.
Let $K(x)$ denote $K(x|\text{empty string})$
(Kolmogorov complexity of $x$) ... more >>>

TR00-036 | 29th May 2000
Carsten Damm, Markus Holzer, Pierre McKenzie

The Complexity of Tensor Calculus

Tensor calculus over semirings is shown relevant to complexity
theory in unexpected ways. First, evaluating well-formed tensor
formulas with explicit tensor entries is shown complete for $\olpus\P$,
for $\NP$, and for $\#\P$ as the semiring varies. Indeed the
permanent of a matrix is shown expressible as ... more >>>

TR00-037 | 26th May 2000
Jens Gramm, Edward Hirsch, Rolf Niedermeier, Peter Rossmanith

New Worst-Case Upper Bounds for MAX-2-SAT with Application to MAX-CUT

The maximum 2-satisfiability problem (MAX-2-SAT) is:
given a Boolean formula in $2$-CNF, find a truth
assignment that satisfies the maximum possible number
of its clauses. MAX-2-SAT is MAXSNP-complete.
Recently, this problem received much attention in the
contexts of approximation (polynomial-time) algorithms
... more >>>

TR00-038 | 24th May 2000

On Computation with Pulses

We explore the computational power of formal models for computation
with pulses. Such models are motivated by realistic models for
biological neurons, and by related new types of VLSI (``pulse stream

In preceding work it was shown that the computational power of formal
models for computation with pulses is ... more >>>

TR00-039 | 25th April 2000
Yevgeniy Dodis

Impossibility of Black-Box Reduction from Non-Adaptively to Adaptively Secure Coin-Flipping

Collective Coin-Flipping is a classical problem where n
computationally unbounded processors are trying to generate a random
bit in a setting where only a single broadcast channel is available
for communication. The protocol is said to be b(n)-resilient if any
adversary that can corrupt up to b(n) players, still cannot ... more >>>

TR00-040 | 19th May 2000
Maria Isabel Gonzalez Vasco, Igor E. Shparlinski

Security of the Most Significant Bits of the Shamir Message Passing Scheme

Boneh and Venkatesan have recently proposed a polynomial time
algorithm for recovering a ``hidden'' element $\alpha$ of a
finite field $\F_p$ of $p$ elements from rather short
strings of the most significant bits of the remainder
mo\-du\-lo $p$ of $\alpha t$ for several values of $t$ selected uniformly
at random ... more >>>

TR00-041 | 19th May 2000
Igor E. Shparlinski

Security of Polynomial Transformations of the Diffie--Hellman Key

D. Boneh and R. Venkatesan have recently proposed an approach to proving
that a reasonably small portions of most significant bits of the
Diffie--Hellman key modulo a prime are as secure the the whole key. Some
further improvements and generalizations have been obtained by
I. M. Gonzales Vasco ... more >>>

TR00-042 | 21st June 2000
Lars Engebretsen

Lower Bounds for non-Boolean Constraint Satisfaction

Revisions: 1

We show that the k-CSP problem over a finite Abelian group G
cannot be approximated within |G|^{k-O(sqrt{k})}-epsilon, for
any constant epsilon>0, unless P=NP. This lower bound matches
well with the best known upper bound, |G|^{k-1}, of Serna,
Trevisan and Xhafa. The proof uses a combination of PCP
techniques---most notably a ... more >>>

TR00-043 | 21st June 2000
Uriel Feige, Marek Karpinski, Michael Langberg

A Note on Approximating MAX-BISECTION on Regular Graphs

We design a $0.795$ approximation algorithm for the Max-Bisection problem
restricted to regular graphs. In the case of three regular graphs our
results imply an approximation ratio of $0.834$.

more >>>

TR00-044 | 26th June 2000
Tzvika Hartman, Ran Raz

On the Distribution of the Number of Roots of Polynomials and Explicit Logspace Extractors

Weak designs were defined by Raz, Reingold and Vadhan (1999) and are
used in constructions of extractors. Roughly speaking, a weak design
is a collection of subsets satisfying some near-disjointness
properties. Constructions of weak designs with certain parameters are
given in [RRV99]. These constructions are explicit in the sense that
more >>>

TR00-045 | 23rd June 2000
Maria Isabel Gonzalez Vasco, Igor E. Shparlinski

On the Security of Diffie--Hellman Bits

Boneh and Venkatesan have recently proposed a polynomial time
algorithm for recovering a ``hidden'' element $\alpha$ of a
finite field $\F_p$ of $p$ elements from rather short
strings of the most significant bits of the remainder
mo\-du\-lo $p$ of $\alpha t$ for several values of $t$ selected
uniformly at ... more >>>

TR00-046 | 19th June 2000
Philipp Woelfel

New Bounds on the OBDD-Size of Integer Multiplication via Universal Hashing

Ordered binary decision diagrams (OBDDs) belong to the most important
representation types for Boolean functions. Although they allow
important operations such as satisfiability test and equality test to
be performed efficiently, their limitation lies in the fact, that they
may require exponential size for important functions. Bryant ... more >>>

TR00-047 | 29th June 2000
Tobias Polzin, Siavash Vahdati Daneshmand

Primal-Dual Approaches to the Steiner Problem

We study several old and new algorithms for computing lower
and upper bounds for the Steiner problem in networks using dual-ascent
and primal-dual strategies. These strategies have been proven to be
very useful for the algorithmic treatment of the Steiner problem. We
show that none of the known algorithms ... more >>>

TR00-048 | 3rd July 2000
Beate Bollig

Restricted Nondeterministic Read-Once Branching Programs and an Exponential Lower Bound for Integer Multiplication

Branching programs are a well established computation model for
Boolean functions, especially read-once branching programs have
been studied intensively.
In this paper the expressive power of nondeterministic read-once
branching programs, i.e., the class of functions
representable in polynomial size, is investigated.
For that reason two restricted models of nondeterministic read-once
more >>>

TR00-050 | 13th July 2000
Peter Auer, Philip M. Long, Gerhard J. Woeginger

On the Complexity of Function Learning

The majority of results in computational learning theory
are concerned with concept learning, i.e. with the special
case of function learning for classes of functions
with range {0,1}. Much less is known about the theory of
learning functions with a larger range such
as N or R. In ... more >>>

TR00-051 | 14th July 2000
Marek Karpinski, Miroslaw Kowaluk, Andrzej Lingas

Approximation Algorithms for MAX-BISECTION on Low Degree Regular Graphs and Planar Graphs

The max-bisection problem is to find a partition of the vertices of a
graph into two equal size subsets that maximizes the number of edges with
endpoints in both subsets.
We obtain new improved approximation ratios for the max-bisection problem on
the low degree $k$-regular graphs for ... more >>>

TR00-052 | 3rd July 2000
Beate Bollig, Ingo Wegener

Approximability and Nonapproximability by Binary Decision Diagrams

Many BDD (binary decision diagram) models are motivated
by CAD applications and have led to complexity theoretical
problems and results. Motivated by applications in genetic
programming Krause, Savick\'y, and Wegener (1999) have shown
that for the inner product function IP$_n$ and the direct
storage access function DSA$_n$ ... more >>>

TR00-053 | 5th May 2000
Alexander E. Andreev, Andrea E. F. Clementi, Paolo Penna, Jose' D. P. Rolim

Parallel Read Operations Without Memory Contention

We address the problem of organizing a set $T$ of shared data into
the memory modules of a Distributed Memory Machine (DMM) in order
to minimize memory access conflicts (i.e. memory contention)
during read operations.
Previous solutions for this problem can be found as fundamental ... more >>>

TR00-054 | 5th May 2000
Andrea E. F. Clementi, Paolo Penna, Riccardo Silvestri

On the power assignment problem in radio networks

Given a finite set $S$ of points (i.e. the stations of a radio
network) on a $d$-dimensional Euclidean space and a positive integer
$1\le h \le |S|-1$, the \minrangeh{d} problem
consists of assigning transmission ranges to the stations so as
to minimize the total power consumption, provided ... more >>>

TR00-055 | 14th July 2000
Peter Auer, Stephen Kwek, Manfred K. Warmuth

Learning of Depth Two Neural Networks with Constant Fan-in at the Hidden Nodes

We present algorithms for learning depth two neural networks where the
hidden nodes are threshold gates with constant fan-in. The transfer
function of the output node might be more general: we have results for
the cases when the threshold function, the logistic function or the
identity function is ... more >>>

TR00-056 | 20th July 2000
Oded Goldreich, Avi Wigderson

On Pseudorandomness with respect to Deterministic Observers.

In the theory of pseudorandomness, potential (uniform) observers
are modeled as probabilistic polynomial-time machines.
In fact many of the central results in
that theory are proven via probabilistic polynomial-time reductions.
In this paper we show that analogous deterministic reductions
are unlikely to hold. We conclude that randomness ... more >>>

TR00-057 | 25th July 2000
Martin Sauerhoff

An Improved Hierarchy Result for Partitioned BDDs

One of the great challenges of complexity theory is the problem of
analyzing the dependence of the complexity of Boolean functions on the
resources nondeterminism and randomness. So far, this problem could be
solved only for very few models of computation. For so-called
partitioned binary decision diagrams, which are a ... more >>>

TR00-058 | 1st August 2000
Martin Sauerhoff

Approximation of Boolean Functions by Combinatorial Rectangles

This paper deals with the number of monochromatic combinatorial
rectangles required to approximate a Boolean function on a constant
fraction of all inputs, where each rectangle may be defined with
respect to its own partition of the input variables. The main result
of the paper is that the number of ... more >>>

TR00-059 | 11th August 2000
Omer Reingold, Ronen Shaltiel, Avi Wigderson

Extracting Randomness via Repeated Condensing

On an input probability distribution with some (min-)entropy
an {\em extractor} outputs a distribution with a (near) maximum
entropy rate (namely the uniform distribution).
A natural weakening of this concept is a condenser, whose
output distribution has a higher entropy rate than the
input distribution (without losing
much of ... more >>>

TR00-060 | 17th August 2000
Uri Zwick

All Pairs Shortest Paths using Bridging Sets and Rectangular Matrix Multiplication

We present two new algorithms for solving the {\em All
Pairs Shortest Paths\/} (APSP) problem for weighted directed
graphs. Both algorithms use fast matrix multiplication algorithms.

The first algorithm
solves the APSP problem for weighted directed graphs in which the edge
weights are integers of small absolute value in ... more >>>

TR00-061 | 14th August 2000
Prahladh Harsha, Madhu Sudan

Small PCPs with low query complexity

Most known constructions of probabilistically checkable proofs (PCPs)
either blow up the proof size by a large polynomial, or have a high
(though constant) query complexity. In this paper we give a
transformation with slightly-super-cubic blowup in proof size, with a
low query complexity. Specifically, the verifier probes the proof ... more >>>

TR00-062 | 25th August 2000
Venkatesan Guruswami, Johan Hastad, Madhu Sudan

Hardness of approximate hypergraph coloring

We introduce the notion of covering complexity of a probabilistic
verifier. The covering complexity of a verifier on a given input is
the minimum number of proofs needed to ``satisfy'' the verifier on
every random string, i.e., on every random string, at least one of the
given proofs must be ... more >>>

TR00-063 | 13th July 2000
Peter Auer

On-line Learning of Rectangles in Noisy Environments

We investigate the implications of noise in the equivalence query
model. Besides some results for general target and hypotheses
classes, we prove bounds on the learning complexity of d-dimensional
discretized rectangles in the case where only rectangles are allowed
as hypotheses.
Our noise model assumes ... more >>>

TR00-064 | 29th August 2000
Klaus Jansen, Marek Karpinski, Andrzej Lingas

A Polynomial Time Approximation Scheme for MAX-BISECTION on Planar Graphs

The Max-Bisection and Min-Bisection are the problems of finding
partitions of the vertices of a given graph into two equal size subsets so as
to maximize or minimize, respectively, the number of edges with exactly one
endpoint in each subset.
In this paper we design the first ... more >>>

TR00-065 | 7th September 2000
Eric Allender, David Mix Barrington

Uniform Circuits for Division: Consequences and Problems

Comments: 2

The essential idea in the fast parallel computation of division and
related problems is that of Chinese remainder representation
(CRR) -- storing a number in the form of its residues modulo many
small primes. Integer division provides one of the few natural
examples of problems for which ... more >>>

TR00-066 | 14th July 2000
Peter Auer

On Learning from Ambiguous Information

We investigate a variant of the Probably Almost Correct learning model
where the learner has to learn from ambiguous information. The
ambiguity is introduced by assuming that the learner does not receive
single instances with their correct labels as training data, but that
the learner receives ... more >>>

TR00-067 | 13th July 2000
Peter Auer, Philip M. Long

Simulating Access to Hidden Information while Learning

We introduce a new technique which enables a learner without access to
hidden information to learn nearly as well as a learner with access to
hidden information. We apply our technique to solve an open problem
of Maass and Turan, showing that for any concept class F the least ... more >>>

TR00-068 | 13th July 2000
Peter Auer, Nicolo Cesa-Bianchi, Yoav Freund, Robert E. Schapire

Gambling in a rigged casino: The adversarial multi-armed bandit problem

In the multi-armed bandit problem, a gambler must decide which arm
of K non-identical slot machines to play in a sequence of trials
so as to maximize his reward.
This classical problem has received much attention because of the
simple model it provides of the trade-off between
exploration ... more >>>

TR00-069 | 14th July 2000
Peter Auer

Learning Nested Differences in the Presence of Malicious Noise

We present a PAC-learning algorithm and an on-line learning algorithm
for nested differences of intersection-closed classes. Examples of
intersection-closed classes include axis-parallel rectangles,
monomials, and linear sub-spaces. Our PAC-learning algorithm uses a
pruning technique that we rigorously proof correct. As a result we
show that ... more >>>

TR00-070 | 14th July 2000
Peter Auer, Manfred K. Warmuth

Tracking the best disjunction

Littlestone developed a simple deterministic on-line learning
algorithm for learning $k$-literal disjunctions. This algorithm
(called Winnow) keeps one weight for each variable and does
multiplicative updates to its weights. We develop a randomized
version of Winnow and prove bounds for an adaptation of the
algorithm ... more >>>

TR00-071 | 14th July 2000
Peter Auer, Nicolo Cesa-Bianchi

On-line Learning with Malicious Noise and the Closure Algorithm

We investigate a variant of the on-line learning model for classes
of {0,1}-valued functions (concepts) in which the labels of a certain
amount of the input instances are corrupted by adversarial noise.
We propose an extension of a general learning strategy, known as
"Closure Algorithm", to this noise ... more >>>

TR00-072 | 14th July 2000
Peter Auer, Philip M. Long, Aravind Srinivasan

Approximating Hyper-Rectangles: Learning and Pseudo-random Sets

The PAC learning of rectangles has been studied because they have
been found experimentally to yield excellent hypotheses for several
applied learning problems. Also, pseudorandom sets for rectangles
have been actively studied recently because (i) they are a subproblem
common to the derandomization of depth-2 (DNF) ... more >>>

TR00-073 | 28th August 2000
Venkatesan Guruswami, Sanjeev Khanna

On the Hardness of 4-coloring a 3-colorable Graph

We give a new proof showing that it is NP-hard to color a 3-colorable
graph using just four colors. This result is already known (Khanna,
Linial, Safra 1992), but our proof is novel as it does not rely on
the PCP theorem, while the earlier one does. This ... more >>>

TR00-074 | 12th July 2000
Daniele Micciancio, Bogdan Warinschi

A Linear Space Algorithm for Computing the Hermite Normal Form

Computing the Hermite Normal Form
of an $n\times n$ matrix using the best current algorithms typically
requires $O(n^3\log M)$ space, where $M$ is a bound on the length of
the columns of the input matrix.
Although polynomial in the input size (which ... more >>>

TR00-075 | 7th September 2000
Andreas Klein, Martin Kutrib

Deterministic Turing Machines in the Range between Real-Time and Linear-Time

Deterministic k-tape and multitape Turing machines with one-way,
two-way and without a separated input tape are considered. We
investigate the classes of languages acceptable by such devices with
time bounds of the form n+r(n) where r in o(n) is a sublinear
function. It is shown that there ... more >>>

TR00-076 | 24th August 2000
Juraj Hromkovic, Juhani Karhumaki, Hartmut Klauck, Georg Schnitger, Sebastian Seibert

Measures of Nondeterminism in Finite Automata

While deterministic finite automata seem to be well understood, surprisingly
many important problems
concerning nondeterministic finite automata (nfa's) remain open.

One such problem area is the study of different measures of nondeterminism in
finite automata and the
estimation of the sizes of minimal nondeterministic finite automata. In this
paper the ... more >>>

TR00-077 | 24th August 2000
Till Tantau

On the Power of Extra Queries to Selective Languages

Revisions: 1

A language is \emph{selective} if there exists a
selection algorithm for it. Such an algorithm selects
from any two words one, which is an element of the
language whenever at least one of them is.
Restricting the complexity of selection algorithms
yields different \emph{selectivity classes} ... more >>>

TR00-078 | 18th July 2000
Jean-Pierre Seifert

Using fewer Qubits in Shor's Factorization Algorithm via Simultaneous Diophantine Approximation}

While quantum computers might speed up in principle
certain computations dramatically, in pratice, though
quantum computing technology is still in its infancy.
Even we cannot clearly envison at present what the
hardware of that machine will be like.
Nevertheless, we can be quite confident that it will be
more >>>

TR00-079 | 12th September 2000
Mark Jerrum, Eric Vigoda

A polynomial-time approximation algorithm for the permanent of a matrix with non-negative entries

We present a fully-polynomial randomized approximation scheme
for computing the permanent of an arbitrary matrix
with non-negative entries.

more >>>

TR00-080 | 24th July 2000
Marco Cesati

Perfect Code is W[1]-complete

We show that the parameterized problem Perfect Code belongs to W[1].
This result closes an old open question, because it was often
conjectured that Perfect Code could be a natural problem having
complexity degree intermediate between W[1] and W[2]. This result
also shows W[1]-membership of the parameterized problem Weighted
more >>>

TR00-081 | 5th September 2000
Shin Aida, Rainer Schuler, Tatsuie Tsukiji, Osamu Watanabe

On the difference between polynomial-time many-one and truth-table reducibilities on distributional problems

In this paper we separate many-one reducibility from truth-table
reducibility for distributional problems in DistNP under the
hypothesis that P neq NP. As a first example we consider the
3-Satisfiability problem (3SAT) with two different distributions
on 3CNF formulas. We show that 3SAT using a version of the
standard distribution ... more >>>

TR00-082 | 17th August 2000
Lefteris Kirousis, Phokion G. Kolaitis

The Complexity of Minimal Satisfiability Problems

Revisions: 2

A dichotomy theorem for a class of decision problems is
a result asserting that certain problems in the class
are solvable in polynomial time, while the rest are NP-complete.
The first remarkable such dichotomy theorem was proved by
T.J. Schaefer in 1978. It concerns the ... more >>>

TR00-083 | 18th September 2000
Eldar Fischer

Testing graphs for colorability properties

Revisions: 1

Let $P$ be a property of graphs. An $\epsilon$-test for $P$ is a
randomized algorithm which, given the ability to make queries whether
a desired pair of vertices of an input graph $G$ with $n$ vertices are
adjacent or not, distinguishes, with high probability, between the
case of $G$ satisfying ... more >>>

TR00-084 | 6th November 2000
Salil Vadhan, Amit Sahai

A Complete Problem for Statistical Zero Knowledge

We present the first complete problem for SZK, the class of (promise)
problems possessing statistical zero-knowledge proofs (against an
honest verifier). The problem, called STATISTICAL DIFFERENCE, is to
decide whether two efficiently samplable distributions are either
statistically close or far apart. This gives a new characterization
of SZK that makes ... more >>>

TR00-085 | 19th September 2000
Rustam Mubarakzjanov

Probabilistic OBDDs: on Bound of Width versus Bound of Error

Ordered binary decision diagrams (OBDDs) are well established tools to
represent Boolean functions. There are a lot of results concerning
different types of generalizations of OBDDs. The same time, the power
of the most general form of OBDD, namely probabilistic (without bounded
error) OBDDs, is not studied enough. In ... more >>>

TR00-086 | 26th September 2000
Michael Schmitt

On the Complexity of Computing and Learning with Multiplicative Neural Networks

In a great variety of neuron models neural inputs are
combined using the summing operation. We introduce the concept of
multiplicative neural networks which contain units that multiply
their inputs instead of summing them and, thus, allow inputs to
interact nonlinearly. The class of multiplicative networks
comprises such widely known ... more >>>

TR00-087 | 14th November 2000
Albert Atserias, Nicola Galesi, Pavel Pudlak

Monotone simulations of nonmonotone propositional proofs

We show that an LK proof of size $m$ of a monotone sequent (a sequent

that contains only formulas in the basis $\wedge,\vee$) can be turned

into a proof containing only monotone formulas of size $m^{O(\log m)}$

and with the number of proof lines polynomial in $m$. Also we show

... more >>>

TR00-088 | 28th November 2000
Meena Mahajan, V. Vinay

A note on the hardness of the characteristic polynomial

In this note, we consider the problem of computing the
coefficients of the characteristic polynomial of a given
matrix, and the related problem of verifying the

Santha and Tan [CC98] show that verifying the determinant
(the constant term in the characteristic polynomial) is
complete for the class C=L, ... more >>>

TR00-089 | 1st December 2000
Lars Engebretsen, Marek Karpinski

Approximation Hardness of TSP with Bounded Metrics

Revisions: 1

The general asymmetric (and metric) TSP is known to be approximable
only to within an O(log n) factor, and is also known to be
approximable within a constant factor as soon as the metric is
bounded. In this paper we study the asymmetric and symmetric TSP
problems with bounded metrics ... more >>>

TR00-090 | 3rd December 2000
Oded Goldreich

Candidate One-Way Functions Based on Expander Graphs

We suggest a candidate one-way function using combinatorial
constructs such as expander graphs. These graphs are used to
determine a sequence of small overlapping subsets of input bits,
to which a hard-wired random predicate is applied.
Thus, the function is extremely easy to evaluate:
all that is needed ... more >>>

TR00-091 | 21st December 2000
Cristina Bazgan, Wenceslas Fernandez de la Vega, Marek Karpinski

Approximability of Dense Instances of NEAREST CODEWORD Problem

We give a polynomial time approximation scheme (PTAS) for dense
instances of the NEAREST CODEWORD problem.

more >>>

ISSN 1433-8092 | Imprint