All reports in year 1994:

__
TR94-001
| 12th December 1994
__

Noam Nisan, Avi Wigderson#### On Rank vs. Communication Complexity

__
TR94-002
| 12th December 1994
__

Oded Goldreich, Avi Wigderson#### Tiny Families of Functions with Random Properties: A Quality--Size Trade--off for Hashing

Revisions: 2

__
TR94-003
| 12th December 1994
__

Noam Nisan, Amnon Ta-Shma#### Symmetric Logspace is Closed Under Complement

__
TR94-004
| 12th December 1994
__

Eric Allender, Martin Strauss#### Measure on Small Complexity Classes, with Applications for BPP

__
TR94-005
| 12th December 1994
__

Noga Alon, Alan Frieze, Dominic Welsh#### Polynomial time randomised approximation schemes for Tutte-Gr\"{o}thendieck invariants: the dense case

__
TR94-006
| 12th December 1994
__

Alexander Razborov#### On provably disjoint NP-pairs

__
TR94-007
| 12th December 1994
__

Oded Goldreich, Rafail Ostrovsky, Erez Petrank#### Computational Complexity and Knowledge Complexity

__
TR94-008
| 12th December 1994
__

Oded Goldreich#### Probabilistic Proof Systems (A Survey)

__
TR94-009
| 12th December 1994
__

Noga Alon, Raphael Yuster, Uri Zwick#### Color-coding

__
TR94-010
| 12th December 1994
__

Alexander Razborov, Steven Rudich#### Natural Proofs

__
TR94-011
| 12th December 1994
__

R. Beigel, W. Hurwood, N. Kahale#### Fault Diagnosis in a Flash

__
TR94-012
| 12th December 1994
__

#### Bounds for the Computational Power and Learning Complexity of Analog Neural Nets

__
TR94-013
| 12th December 1994
__

Pavel Pudlak#### Complexity Theory and Genetics

__
TR94-014
| 12th December 1994
__

Miklos Ajtai#### The Independence of the modulo p Counting Principles

__
TR94-015
| 12th December 1994
__

Miklos Ajtai#### Symmetric Systems of Linear Equations modulo $p$

__
TR94-016
| 12th December 1994
__

Jin-Yi Cai, W. H. J. Fuchs, Dexter Kozen, Zicheng Liu#### Efficient Average-Case Algorithms for the Modular Group

__
TR94-017
| 12th December 1994
__

#### Neural Nets with Superlinear VC-Dimension

__
TR94-018
| 12th December 1994
__

Jan Krajicek, Pavel Pudlak, Alan Woods#### An Exponential Lower Bound to the Size of Bounded Depth Frege Proofs of the Pigeonhole Principle

__
TR94-019
| 12th December 1994
__

#### Lower Bounds for the Computational Power of Networks of Spiking

__
TR94-020
| 12th December 1994
__

#### Agnostic PAC-Learning of Functions on Analog Neural Nets

__
TR94-021
| 12th December 1994
__

Lance Fortnow#### My Favorite Ten Complexity Theorems of the Past Decade

__
TR94-022
| 12th December 1994
__

Christoph Meinel, Stephan Waack#### The MÃ¶bius Function, Variations Ranks, and Theta(n)--Bounds on the Modular Communication Complexity of the Undirected Graph Connectivity Problem

__
TR94-023
| 12th December 1994
__

Matthias Krause, Pavel Pudlak#### On the Computational Power of Depth 2 Circuits with Threshold and Modulo Gates

__
TR94-024
| 12th December 1994
__

Marek Karpinski, Angus Macintyre#### Polynomial Bounds for VC Dimension of Sigmoidal Neural Networks

__
TR94-025
| 12th December 1994
__

David P. Dobkin, Dimitrios Gunopulos#### Computing the Maximum Bichromatic Discrepancy with applications to Computer Graphics and Machine Learning

__
TR94-026
| 12th December 1994
__

Beate Bollig, Martin Sauerhoff, Detlef Sieling, Ingo Wegener#### On the Power of Different Types of Restricted Branching Programs

__
TR94-027
| 12th December 1994
__

Stasys Jukna#### A Note on Read-k Times Branching Programs

Noam Nisan, Avi Wigderson

This paper concerns the open problem of Lovasz and

Saks regarding the relationship between the communication complexity

of a boolean function and the rank of the associated matrix.

We first give an example exhibiting the largest gap known. We then

prove two related theorems.

Oded Goldreich, Avi Wigderson

We present three explicit constructions of hash functions,

which exhibit a trade-off between the size of the family

(and hence the number of random bits needed to generate a member of the family),

and the quality (or error parameter) of the pseudo-random property it

achieves. Unlike previous constructions, ...
more >>>

Noam Nisan, Amnon Ta-Shma

We present a Logspace, many-one reduction from the undirected

st-connectivity problem to its complement. This shows that

$SL=co-SL$

Eric Allender, Martin Strauss

We present a notion of resource-bounded measure for P and other

subexponential-time classes. This generalization is based on Lutz's

notion of measure, but overcomes the limitations that cause Lutz's

definitions to apply only to classes at least as large as E. We

present many of the basic properties of this ...
more >>>

Noga Alon, Alan Frieze, Dominic Welsh

The Tutte-Gr\"othendieck polynomial $T(G;x,y)$ of a graph $G$

encodes numerous interesting combinatorial quantities associated

with the graph. Its evaluation in various points in the $(x,y)$

plane give the number of spanning forests of the graph, the number

of its strongly connected orientations, the number of its proper

$k$-colorings, the (all ...
more >>>

Alexander Razborov

In this paper we study the pairs $(U,V)$ of disjoint ${\bf NP}$-sets

representable in a theory $T$ of Bounded Arithmetic in the sense that

$T$ proves $U\cap V=\emptyset$. For a large variety of theories $T$

we exhibit a natural disjoint ${\bf NP}$-pair which is complete for the

class of disjoint ...
more >>>

Oded Goldreich, Rafail Ostrovsky, Erez Petrank

We study the computational complexity of languages which have

interactive proofs of logarithmic knowledge complexity. We show that

all such languages can be recognized in ${\cal BPP}^{\cal NP}$. Prior

to this work, for languages with greater-than-zero knowledge

complexity (and specifically, even for knowledge complexity 1) only

trivial computational complexity bounds ...
more >>>

Oded Goldreich

Various types of probabilistic proof systems have played

a central role in the development of computer science in the last decade.

In this exposition, we concentrate on three such proof systems ---

interactive proofs, zero-knowledge proofs,

and probabilistic checkable proofs --- stressing the essential

role of randomness in each ...
more >>>

Noga Alon, Raphael Yuster, Uri Zwick

We describe a novel randomized method, the method of

{\em color-coding\/} for finding simple paths and cycles of a specified

length $k$, and other small subgraphs, within a given graph $G=(V,E)$.

The randomized algorithms obtained using this method can be

derandomized using families of {\em perfect hash functions\/}. ...
more >>>

Alexander Razborov, Steven Rudich

We introduce the notion of {\em natural} proof.

We argue that the known proofs of lower bounds on the complexity of explicit

Boolean functions in non-monotone models

fall within our definition of natural.

We show based on a hardness assumption

that natural proofs can't prove superpolynomial lower bounds ...
more >>>

R. Beigel, W. Hurwood, N. Kahale

We consider the fault diagnosis problem: how to use parallel testing

rounds to identify which processors in a set are faulty. We prove

that 4 rounds suffice when 3% or less of the processors are faulty,

and 4 rounds are necessary when any nontrivial constant fraction of

the processors are ...
more >>>

It is shown that high order feedforward neural nets of constant depth with piecewise

polynomial activation functions and arbitrary real weights can be simulated for boolean

inputs and outputs by neural nets of a somewhat larger size and depth with heaviside

gates and weights ...
more >>>

Pavel Pudlak

We introduce a population genetics model in which the operators

are effectively computable -- computable in polynomial time on

Probabilistic Turing Machines. We shall show that in this model

a population can encode easily large amount of information

from enviroment into genetic code. Then it can process the

information as ...
more >>>

Miklos Ajtai

The modulo $p$ counting principle is a first-order axiom

schema saying that it is possible to count modulo $p$ the number of

elements of the first-order definable subsets of the universe (and of

the finite Cartesian products of the universe with itself) in a

consistent way. It trivially holds on ...
more >>>

Miklos Ajtai

Suppose that $p$ is a prime number $A$ is a finite set

with $n$ elements

and for each sequence $a=<a_{1},...,a_{k}>$ of length $k$ from the

elements of

$A$, $x_{a}$ is a variable. (We may think that $k$ and $p$ are fixed an

$n$ is sufficiently large.) We will ...
more >>>

Jin-Yi Cai, W. H. J. Fuchs, Dexter Kozen, Zicheng Liu

The modular group occupies a central position in many branches of

mathematical sciences. In this paper we give average polynomial-time

algorithms for the unbounded and bounded membership problems for

finitely generated subgroups of the modular group. The latter result

affirms a conjecture of Gurevich.

It has been known for quite a while that the Vapnik-Chervonenkis dimension

(VC-dimension) of a feedforward neural net with linear threshold gates is at

most O(w log w), where w is the total number of weights in the neural net.

We show in this paper that this bound is in ...
more >>>

Jan Krajicek, Pavel Pudlak, Alan Woods

We prove lower bounds of the form $exp\left(n^{\epsilon_d}\right),$

$\epsilon_d>0,$ on the length of proofs of an explicit sequence of

tautologies, based on the Pigeonhole Principle, in proof systems

using formulas of depth $d,$ for any constant $d.$ This is the

largest lower bound for the strongest proof system, for which ...
more >>>

We investigate the computational power of a formal model for networks of

spiking neurons. It is shown that simple operations on phase-differences

between spike-trains provide a very powerful computational tool that can

in principle be used to carry out highly complex computations on a small

network of spiking neurons. We ...
more >>>

We consider learning on multi-layer neural nets with piecewise polynomial

activation functions and a fixed number k of numerical inputs. We exhibit

arbitrarily large network architectures for which efficient and provably

successful learning algorithms exist in the rather realistic refinement of

Valiant's model for probably approximately correct learning ("PAC-learning")

where ...
more >>>

Lance Fortnow

We review the past ten years in computational complexity theory by

focusing on ten theorems that the author enjoyed the most. We use

each of the theorems as a springboard to discuss work done in

various areas of complexity theory.

Christoph Meinel, Stephan Waack

We prove that the modular communication complexity of the

undirected graph connectivity problem UCONN equals Theta(n),

in contrast to the well-known Theta(n*log n) bound in the

deterministic case, and to the Omega(n*loglog n) lower bound

in the nondeterministic case, recently proved by ...
more >>>

Matthias Krause, Pavel Pudlak

We investigate the computational power of depth two circuits

consisting of $MOD^r$--gates at the bottom and a threshold gate at

the top (for short, threshold--$MOD^r$ circuits) and circuits with

two levels of $MOD$ gates ($MOD^{p}$-$MOD^q$ circuits.) In particular, we

will show the following results

(i) For all prime numbers ... more >>>

Marek Karpinski, Angus Macintyre

We introduce a new method for proving explicit upper bounds on the VC

Dimension of general functional basis networks, and prove as an

application, for the first time, the VC Dimension of analog neural

networks with the sigmoid activation function $\sigma(y)=1/1+e^{-y}$

to ...
more >>>

David P. Dobkin, Dimitrios Gunopulos

Computing the maximum bichromatic discrepancy is an interesting

theoretical problem with important applications in computational

learning theory, computational geometry and computer graphics.

In this paper we give algorithms to compute the maximum

bichromatic discrepancy for simple geometric ranges, including

rectangles and halfspaces.

In addition, we give ...
more >>>

Beate Bollig, Martin Sauerhoff, Detlef Sieling, Ingo Wegener

Almost the same types of restricted branching programs (or

binary decision diagrams BDDs) are considered in complexity

theory and in applications like hardware verification. These

models are read-once branching programs (free BDDs) and certain

types of oblivious branching programs (ordered and indexed BDDs

with k layers). The complexity of ...
more >>>

Stasys Jukna

A syntactic read-k times branching program has the restriction

that no variable occurs more than k times on any path (whether or not

consistent). We exhibit an explicit Boolean function f which cannot

be computed by nondeterministic syntactic read-k times branching programs

of size less than exp(\sqrt{n}}k^{-2k}), ...
more >>>