All reports in year 2000:

__
TR00-001
| 14th January 2000
__

Piotr Berman, Moses Charikar, Marek Karpinski#### On-Line Load Balancing for Related Machines

__
TR00-002
| 23rd December 1999
__

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

__
TR00-003
| 26th November 1999
__

Matthias Krause, Hans Ulrich Simon#### Determining the Optimal Contrast for Secret Sharing Schemes in Visual Cryptography

__
TR00-004
| 14th January 2000
__

Oded Goldreich, Salil Vadhan, Avi Wigderson#### Simplified derandomization of BPP using a hitting set generator.

__
TR00-005
| 17th January 2000
__

Eli Ben-Sasson, Russell Impagliazzo, Avi Wigderson#### Near-Optimal Separation of Treelike and General Resolution

__
TR00-006
| 26th January 2000
__

E.A. Okol'nishnikiva#### On operations of geometrical projection and monotone extension

__
TR00-007
| 14th December 1999
__

Pavlos S. Efraimidis, Paul Spirakis#### Randomized Approximation Schemes for Scheduling Unrelated Parallel Machines

__
TR00-008
| 20th January 2000
__

Albert Atserias, Nicola Galesi, Ricard Gavaldà#### Monotone Proofs of the Pigeon Hole Principle

__
TR00-009
| 21st February 2000
__

Russell Impagliazzo, Ronen Shaltiel, Avi Wigderson#### Extractors and pseudo-random generators with optimal seed length

__
TR00-010
| 12th January 2000
__

Amitabha Roy, Christopher Wilson#### Supermodels and Closed Sets

__
TR00-011
| 27th January 2000
__

Sotiris Nikoletseas, Paul Spirakis#### Efficient Communication Establishment in Extremely Unreliable Large Networks

__
TR00-012
| 14th February 2000
__

Ke Yang#### Integer Circuit Evaluation is PSPACE-complete

__
TR00-013
| 14th February 2000
__

Daniel Král#### Algebraic and Uniqueness Properties of Parity Ordered Binary Decision Diagrams and their Generalization

__
TR00-014
| 16th February 2000
__

Matthias Krause, Stefan Lucks#### On Learning versus Distinguishing and the Minimal Hardware Complexity of Pseudorandom Function Generators

__
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

__
TR00-017
| 3rd March 2000
__

Valentin E. Brimkov, Stefan S. Dantchev#### On the Algebraic Complexity of Integer Programming

__
TR00-018
| 16th February 2000
__

Oliver Kullmann#### An application of matroid theory to the SAT problem

__
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

__
TR00-020
| 27th March 2000
__

Oded Goldreich, Dana Ron#### On Testing Expansion in Bounded-Degree Graphs

__
TR00-021
| 19th April 2000
__

Uriel Feige, Marek Karpinski, Michael Langberg#### Improved Approximation of MAX-CUT on Graphs of Bounded Degree

__
TR00-022
| 2nd May 2000
__

Rosario Gennaro, Luca Trevisan#### Lower bounds on the efficiency of generic cryptographic constructions

__
TR00-023
| 11th May 2000
__

Michael Alekhnovich, Eli Ben-Sasson, Alexander Razborov, Avi Wigderson#### Pseudorandom Generators in Propositional Proof Complexity

__
TR00-024
| 16th May 2000
__

Amihood Amir, Richard Beigel, William Gasarch#### Some Connections between Bounded Query Classes and Non-Uniform Complexity

__
TR00-025
| 20th May 2000
__

Paul Beame, Michael Saks, Xiaodong Sun, Erik Vee#### Super-linear time-space tradeoff lower bounds for randomized computation

__
TR00-026
| 11th April 2000
__

Andrei Romashchenko, Alexander Shen, Nikolay Vereshchagin#### Combinatorial Interpretation of Kolmogorov Complexity

__
TR00-027
| 11th April 2000
__

Pavol Duris, Juraj Hromkovic, Katsushi Inoue#### A Separation of Determinism, Las Vegas and Nondeterminism for Picture Recognition

__
TR00-028
| 17th April 2000
__

Lance Fortnow, Dieter van Melkebeek#### Time-Space Tradeoffs for Nondeterministic Computation

__
TR00-029
| 30th April 2000
__

Ran Raz, Amir Shpilka#### Lower Bounds for Matrix Product, in Bounded Depth Circuits with Arbitrary Gates

Revisions: 1

__
TR00-030
| 31st May 2000
__

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

__
TR00-031
| 31st May 2000
__

Eduardo D. Sontag#### Neural Systems as Nonlinear Filters

__
TR00-032
| 31st May 2000
__

#### On the Computational Power of Winner-Take-All

__
TR00-033
| 22nd May 2000
__

Jan Krajicek#### Tautologies from pseudo-random generators

Revisions: 1

__
TR00-034
| 5th June 2000
__

Valentine Kabanets, Charles Rackoff, Stephen Cook#### Efficiently Approximable Real-Valued Functions

__
TR00-035
| 6th June 2000
__

Nikolay Vereshchagin, Mikhail V. Vyugin#### Independent minimum length programs to translate between given strings

__
TR00-036
| 29th May 2000
__

Carsten Damm, Markus Holzer, Pierre McKenzie#### The Complexity of Tensor Calculus

__
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

__
TR00-038
| 24th May 2000
__

#### On Computation with Pulses

__
TR00-039
| 25th April 2000
__

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

__
TR00-040
| 19th May 2000
__

Maria Isabel Gonzalez Vasco, Igor E. Shparlinski#### Security of the Most Significant Bits of the Shamir Message Passing Scheme

__
TR00-041
| 19th May 2000
__

Igor E. Shparlinski#### Security of Polynomial Transformations of the Diffie--Hellman Key

__
TR00-042
| 21st June 2000
__

Lars Engebretsen#### Lower Bounds for non-Boolean Constraint Satisfaction

Revisions: 1

__
TR00-043
| 21st June 2000
__

Uriel Feige, Marek Karpinski, Michael Langberg#### A Note on Approximating MAX-BISECTION on Regular Graphs

__
TR00-044
| 26th June 2000
__

Tzvika Hartman, Ran Raz#### On the Distribution of the Number of Roots of Polynomials and Explicit Logspace Extractors

__
TR00-045
| 23rd June 2000
__

Maria Isabel Gonzalez Vasco, Igor E. Shparlinski#### On the Security of Diffie--Hellman Bits

__
TR00-046
| 19th June 2000
__

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

__
TR00-047
| 29th June 2000
__

Tobias Polzin, Siavash Vahdati Daneshmand#### Primal-Dual Approaches to the Steiner Problem

__
TR00-048
| 3rd July 2000
__

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

__
TR00-049
| 2nd May 2000
__

Herbert Fleischner, Stefan Szeider#### Polynomial-Time Recognition of Minimal Unsatisfiable Formulas with Fixed Clause-Variable Difference

__
TR00-050
| 13th July 2000
__

Peter Auer, Philip M. Long, Gerhard J. Woeginger#### On the Complexity of Function Learning

__
TR00-051
| 14th July 2000
__

Marek Karpinski, Miroslaw Kowaluk, Andrzej Lingas#### Approximation Algorithms for MAX-BISECTION on Low Degree Regular Graphs and Planar Graphs

__
TR00-052
| 3rd July 2000
__

Beate Bollig, Ingo Wegener#### Approximability and Nonapproximability by Binary Decision Diagrams

__
TR00-053
| 5th May 2000
__

Alexander E. Andreev, Andrea E. F. Clementi, Paolo Penna, Jose' D. P. Rolim#### Parallel Read Operations Without Memory Contention

__
TR00-054
| 5th May 2000
__

Andrea E. F. Clementi, Paolo Penna, Riccardo Silvestri#### On the power assignment problem in radio networks

__
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

__
TR00-056
| 20th July 2000
__

Oded Goldreich, Avi Wigderson#### On Pseudorandomness with respect to Deterministic Observers.

__
TR00-057
| 25th July 2000
__

Martin Sauerhoff#### An Improved Hierarchy Result for Partitioned BDDs

__
TR00-058
| 1st August 2000
__

Martin Sauerhoff#### Approximation of Boolean Functions by Combinatorial Rectangles

__
TR00-059
| 11th August 2000
__

Omer Reingold, Ronen Shaltiel, Avi Wigderson#### Extracting Randomness via Repeated Condensing

__
TR00-060
| 17th August 2000
__

Uri Zwick#### All Pairs Shortest Paths using Bridging Sets and Rectangular Matrix Multiplication

__
TR00-061
| 14th August 2000
__

Prahladh Harsha, Madhu Sudan#### Small PCPs with low query complexity

__
TR00-062
| 25th August 2000
__

Venkatesan Guruswami, Johan Håstad, Madhu Sudan#### Hardness of approximate hypergraph coloring

__
TR00-063
| 13th July 2000
__

Peter Auer#### On-line Learning of Rectangles in Noisy Environments

__
TR00-064
| 29th August 2000
__

Klaus Jansen, Marek Karpinski, Andrzej Lingas#### A Polynomial Time Approximation Scheme for MAX-BISECTION on Planar Graphs

__
TR00-065
| 7th September 2000
__

Eric Allender, David Mix Barrington#### Uniform Circuits for Division: Consequences and Problems

Comments: 2

__
TR00-066
| 14th July 2000
__

Peter Auer#### On Learning from Ambiguous Information

__
TR00-067
| 13th July 2000
__

Peter Auer, Philip M. Long#### Simulating Access to Hidden Information while Learning

__
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

__
TR00-069
| 14th July 2000
__

Peter Auer#### Learning Nested Differences in the Presence of Malicious Noise

__
TR00-070
| 14th July 2000
__

Peter Auer, Manfred K. Warmuth#### Tracking the best disjunction

__
TR00-071
| 14th July 2000
__

Peter Auer, Nicolo Cesa-Bianchi#### On-line Learning with Malicious Noise and the Closure Algorithm

__
TR00-072
| 14th July 2000
__

Peter Auer, Philip M. Long, Aravind Srinivasan#### Approximating Hyper-Rectangles: Learning and Pseudo-random Sets

__
TR00-073
| 28th August 2000
__

Venkatesan Guruswami, Sanjeev Khanna#### On the Hardness of 4-coloring a 3-colorable Graph

__
TR00-074
| 12th July 2000
__

Daniele Micciancio, Bogdan Warinschi#### A Linear Space Algorithm for Computing the Hermite Normal Form

__
TR00-075
| 7th September 2000
__

Andreas Klein, Martin Kutrib#### Deterministic Turing Machines in the Range between Real-Time and Linear-Time

__
TR00-076
| 24th August 2000
__

Juraj Hromkovic, Juhani Karhumaki, Hartmut Klauck, Georg Schnitger, Sebastian Seibert#### Measures of Nondeterminism in Finite Automata

__
TR00-077
| 24th August 2000
__

Till Tantau#### On the Power of Extra Queries to Selective Languages

Revisions: 1

__
TR00-078
| 18th July 2000
__

Jean-Pierre Seifert#### Using fewer Qubits in Shor's Factorization Algorithm via Simultaneous Diophantine Approximation}

__
TR00-079
| 12th September 2000
__

Mark Jerrum, Eric Vigoda#### A polynomial-time approximation algorithm for the permanent of a matrix with non-negative entries

__
TR00-080
| 24th July 2000
__

Marco Cesati#### Perfect Code is W[1]-complete

__
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

__
TR00-082
| 17th August 2000
__

Lefteris Kirousis, Phokion G. Kolaitis#### The Complexity of Minimal Satisfiability Problems

Revisions: 2

__
TR00-083
| 18th September 2000
__

Eldar Fischer#### Testing graphs for colorability properties

Revisions: 1

__
TR00-084
| 6th November 2000
__

Salil Vadhan, Amit Sahai#### A Complete Problem for Statistical Zero Knowledge

__
TR00-085
| 19th September 2000
__

Rustam Mubarakzjanov#### Probabilistic OBDDs: on Bound of Width versus Bound of Error

__
TR00-086
| 26th September 2000
__

Michael Schmitt#### On the Complexity of Computing and Learning with Multiplicative Neural Networks

__
TR00-087
| 14th November 2000
__

Albert Atserias, Nicola Galesi, Pavel Pudlak#### Monotone simulations of nonmonotone propositional proofs

__
TR00-088
| 28th November 2000
__

Meena Mahajan, V Vinay#### A note on the hardness of the characteristic polynomial

__
TR00-089
| 1st December 2000
__

Lars Engebretsen, Marek Karpinski#### Approximation Hardness of TSP with Bounded Metrics

Revisions: 1

__
TR00-090
| 3rd December 2000
__

Oded Goldreich#### Candidate One-Way Functions Based on Expander Graphs

__
TR00-091
| 21st December 2000
__

Cristina Bazgan, Wenceslas Fernandez de la Vega, Marek Karpinski#### Approximability of Dense Instances of NEAREST CODEWORD Problem

Piotr Berman, Moses Charikar, Marek Karpinski

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

Michael Schmitt

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

Matthias Krause, Hans Ulrich Simon

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

Oded Goldreich, Salil Vadhan, Avi Wigderson

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

Eli Ben-Sasson, Russell Impagliazzo, Avi Wigderson

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

E.A. Okol'nishnikiva

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

Pavlos S. Efraimidis, Paul Spirakis

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

Albert Atserias, Nicola Galesi, Ricard Gavaldà

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

Russell Impagliazzo, Ronen Shaltiel, Avi Wigderson

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

Amitabha Roy, Christopher Wilson

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

Sotiris Nikoletseas, Paul Spirakis

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

Ke Yang

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

Daniel Král

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

Matthias Krause, Stefan Lucks

\begin{abstract}

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

Andrej Muchnik, Alexej Semenov

Mikhail V. Vyugin

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$

as

$$

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

Valentin E. Brimkov, Stefan S. Dantchev

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

Oliver Kullmann

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

Edward Hirsch

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

Oded Goldreich, Dana Ron

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

Uriel Feige, Marek Karpinski, Michael Langberg

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

Rosario Gennaro, Luca Trevisan

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

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

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

Amihood Amir, Richard Beigel, William Gasarch

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

Paul Beame, Michael Saks, Xiaodong Sun, Erik Vee

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

Andrei Romashchenko, Alexander Shen, Nikolay Vereshchagin

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

Pavol Duris, Juraj Hromkovic, Katsushi Inoue

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

Lance Fortnow, Dieter van Melkebeek

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

Fortnow.

Ran Raz, Amir Shpilka

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

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

Eduardo D. Sontag

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

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

Jan Krajicek

We consider tautologies formed from a pseudo-random

number generator, defined in Kraj\'{\i}\v{c}ek \cite{Kra99}

and in Alekhnovich et.al. \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 >>>

Valentine Kabanets, Charles Rackoff, Stephen Cook

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

Nikolay Vereshchagin, Mikhail V. Vyugin

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

Carsten Damm, Markus Holzer, Pierre McKenzie

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

Jens Gramm, Edward Hirsch, Rolf Niedermeier, Peter Rossmanith

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

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

VLSI'').

In preceding work it was shown that the computational power of formal

models for computation with pulses is ...
more >>>

Yevgeniy Dodis

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

Maria Isabel Gonzalez Vasco, Igor E. Shparlinski

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

Igor E. Shparlinski

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

Lars Engebretsen

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

Uriel Feige, Marek Karpinski, Michael Langberg

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

Tzvika Hartman, Ran Raz

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

Maria Isabel Gonzalez Vasco, Igor E. Shparlinski

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

Philipp Woelfel

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

Tobias Polzin, Siavash Vahdati Daneshmand

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

Beate Bollig

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

Herbert Fleischner, Stefan Szeider

Peter Auer, Philip M. Long, Gerhard J. Woeginger

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

Marek Karpinski, Miroslaw Kowaluk, Andrzej Lingas

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

Beate Bollig, Ingo Wegener

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

Alexander E. Andreev, Andrea E. F. Clementi, Paolo Penna, Jose' D. P. Rolim

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

Andrea E. F. Clementi, Paolo Penna, Riccardo Silvestri

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

Peter Auer, Stephen Kwek, Manfred K. Warmuth

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

Oded Goldreich, Avi Wigderson

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

Martin Sauerhoff

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

Martin Sauerhoff

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

Omer Reingold, Ronen Shaltiel, Avi Wigderson

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

Uri Zwick

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

Prahladh Harsha, Madhu Sudan

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

Venkatesan Guruswami, Johan Håstad, Madhu Sudan

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

Peter Auer

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

Klaus Jansen, Marek Karpinski, Andrzej Lingas

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

Eric Allender, David Mix Barrington

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

Peter Auer

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

Peter Auer, Philip M. Long

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

Peter Auer, Nicolo Cesa-Bianchi, Yoav Freund, Robert E. Schapire

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

Peter Auer

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

Peter Auer, Manfred K. Warmuth

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

Peter Auer, Nicolo Cesa-Bianchi

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

Peter Auer, Philip M. Long, Aravind Srinivasan

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

Venkatesan Guruswami, Sanjeev Khanna

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

Daniele Micciancio, Bogdan Warinschi

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

Andreas Klein, Martin Kutrib

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

Juraj Hromkovic, Juhani Karhumaki, Hartmut Klauck, Georg Schnitger, Sebastian Seibert

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

Till Tantau

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

Jean-Pierre Seifert

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

Mark Jerrum, Eric Vigoda

We present a fully-polynomial randomized approximation scheme

for computing the permanent of an arbitrary matrix

with non-negative entries.

Marco Cesati

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

Shin Aida, Rainer Schuler, Tatsuie Tsukiji, Osamu Watanabe

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

Lefteris Kirousis, Phokion G. Kolaitis

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

Eldar Fischer

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

Salil Vadhan, Amit Sahai

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

Rustam Mubarakzjanov

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

Michael Schmitt

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

Albert Atserias, Nicola Galesi, Pavel Pudlak

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 >>>Meena Mahajan, V Vinay

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

coefficents.

Santha and Tan [CC98] show that verifying the determinant

(the constant term in the characteristic polynomial) is

complete for the class C=L, ...
more >>>

Lars Engebretsen, Marek Karpinski

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

Oded Goldreich

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

Cristina Bazgan, Wenceslas Fernandez de la Vega, Marek Karpinski

We give a polynomial time approximation scheme (PTAS) for dense

instances of the NEAREST CODEWORD problem.