All reports in year 1995:

__
TR95-001
| 1st January 1995
__

Amos Beimel, Anna Gal, Michael S. Paterson#### Lower Bounds for Monotone Span Programs

__
TR95-002
| 1st January 1995
__

Detlef Sieling#### New Lower Bounds and Hierarchy Results for Restricted Branching Programs

__
TR95-003
| 1st January 1995
__

Marek Karpinski, Alexander Zelikovsky#### 1.757 and 1.267-Approximation Algorithms for the Network and and Rectilinear Steiner Tree Problems

__
TR95-004
| 1st January 1995
__

Martin Dietzfelbinger, Miroslaw Kutylowski, Rüdiger Reischuk#### Feasible Time-Optimal Algorithms for Boolean Functions on Exclusive-Write PRAMs

__
TR95-005
| 1st January 1995
__

Maciej Liskiewicz, Rüdiger Reischuk#### The Sublogarithmic Alternating Space World

__
TR95-006
| 1st January 1995
__

Kenneth W. Regan, D. Sivakumar, Jin-Yi Cai#### Pseudorandom Generators, Measure Theory, and Natural Proofs

__
TR95-007
| 1st January 1995
__

U. Faigle, S.P. Fekete, W. Hochstättler, W. Kern#### THE NUCLEON OF COOPERATIVE GAMES AND AN ALGORITHM FOR MATCHING GAMES

__
TR95-008
| 27th January 1995
__

Nader H. Bshouty#### Exact Learning Boolean Functions via the Monotone Theory

__
TR95-009
| 2nd February 1995
__

Matthias Krause#### A note on realizing iterated multiplication by small depth threshold circuits

__
TR95-010
| 16th February 1995
__

Pavel Pudlak, Jiri Sgall#### An Upper Bound for a Communication Game Related to Time-Space Tradeoffs

__
TR95-011
| 15th February 1995
__

Roman Bacik, Sanjeev Mahajan#### Semidefinite Programming and its Applications to NP Problems

__
TR95-013
| 24th February 1995
__

Oleg Verbitsky#### The Parallel Repetition Conjecture for Trees is True

__
TR95-014
| 27th January 1995
__

U. Faigle, W. Kern, M. Streng#### Note On the Computational Complexity of $j$-Radii of Polytopes in ${\Re}^n$

__
TR95-015
| 6th February 1995
__

Bshouty, Cleve, Gavalda, Kannan, Tamon.#### Oracles and queries that are sufficient for exact learning

__
TR95-016
| 2nd February 1995
__

U. Faigle, S.P. Fekete, W. Hochstättler, W. Kern#### On approximately fair cost allocation in Euclidean TSP games

__
TR95-017
| 27th March 1995
__

Claudia Bertram, Thomas Hofmeister#### Multiple Product Modulo Arbitrary Numbers

__
TR95-018
| 27th March 1995
__

Jay Belanger, Jie Wang#### Rankable Distributions Do Not Provide Harder Instances Than Uniform Distributions

__
TR95-020
| 8th March 1995
__

William Hurwood#### Dynamic Fault Diagnosis

__
TR95-021
| 20th April 1995
__

Marek Karpinski, Rutger Verbeek#### On Randomized Versus Deterministic Computation

__
TR95-022
| 2nd May 1995
__

Marek Karpinski, Wojciech Rytter, Ayumi Shinohara#### Pattern-Matching for Strings with Short Descriptions

__
TR95-023
| 16th May 1995
__

Sanjeev Khanna, Rajeev Motwani, Madhu Sudan, Umesh Vazirani#### On Syntactic versus Computational views of Approximability

__
TR95-024
| 23rd May 1995
__

Mihir Bellare, Oded Goldreich, Madhu Sudan#### Free bits, PCP and Non-Approximability - Towards tight results

Revisions: 4

__
TR95-025
| 8th May 1995
__

Günter Hotz, Gero Vierke, Bjoern Schieffer#### Analytic Machines

Comments: 1

__
TR95-026
| 7th June 1995
__

Claus-Peter Schnorr, Horst Helmut Hoerner#### Attacking the Chor-Rivest Cryptosystem by Improved Lattice Reduction

__
TR95-027
| 30th May 1995
__

Frederic Green#### Lower Bounds for Circuits with Mod Gates and One Exact Threshold Gate

__
TR95-028
| 9th June 1995
__

Eric Allender, Martin Strauss#### Measure on P: Robustness of the Notion

__
TR95-029
| 15th June 1995
__

Oded Goldreich, Leonid Levin, Noam Nisan#### On Constructing 1-1 One-Way Functions

__
TR95-030
| 20th June 1995
__

Marek Karpinski, Alexander Zelikovsky#### New Approximation Algorithms for the Steiner Tree Problems

__
TR95-031
| 25th June 1995
__

Dorit Dor, Uri Zwick#### Selecting the median

__
TR95-032
| 6th April 1995
__

Nader Bshouty, Christino Tamon#### On the Fourier spectrum of monotone functions

__
TR95-033
| 29th June 1995
__

Richard Beigel, David Eppstein#### 3-Coloring in time O(1.3446^n): a no-MIS algorithm

__
TR95-034
| 30th June 1995
__

Christoph Meinel, Stephan Waack#### Lower Bounds for the Majority Communication Complexity of Various Graph Accessibility Problems

__
TR95-035
| 30th June 1995
__

Richard Beigel#### Closure Properties of GapP and #P

__
TR95-036
| 5th July 1995
__

Richard Beigel, William Gasarch, Efim Kinber#### Frequency Computation and Bounded Queries

__
TR95-037
| 2nd July 1995
__

Richard Beigel, Howard Straubing#### The Power of Local Self-Reductions

__
TR95-038
| 2nd July 1995
__

Joe Kilian, Erez Petrank#### An Efficient Non-Interactive Zero-Knowledge Proof System for NP with General Assumptions

__
TR95-039
| 11th July 1995
__

Tomoyuki Yamakami#### Polynomial Time Samplable Distributions

Revisions: 2

__
TR95-040
| 26th July 1995
__

Uri Zwick, Michael S. Paterson#### The complexity of mean payoff games on graphs

__
TR95-041
| 28th June 1995
__

Alexander E. Andreev, Andrea E. F. Clementi, Jose Rolim#### Optimal Bounds for the Approximation of Boolean Functions and Some Applications

__
TR95-042
| 14th September 1995
__

Beate Bollig, Ingo Wegener#### Read-once Projections and Formal Circuit Verification with Binary Decision Diagrams

__
TR95-043
| 14th September 1995
__

Eric Allender, Jia Jiao, Meena Mahajan, V. Vinay#### Non-Commutative Arithmetic Circuits: Depth Reduction and Size Lower Bounds

__
TR95-044
| 18th September 1995
__

Carsten Damm, Stasys Jukna, Jiri Sgall#### Some Bounds on Multiparty Communication Complexity of Pointer Jumping

__
TR95-045
| 4th September 1995
__

Moni Naor, Omer Reingold#### Synthesizers and Their Application to the Parallel Construction of Pseudo-random Functions

__
TR95-046
| 4th August 1995
__

Vince Grolmusz#### On the Power of Circuits with Gates of Low L_1 Norms

__
TR95-047
| 5th October 1995
__

Martin Loebbing, Ingo Wegener#### The Number of Knight's Tours Equals 33,439,123,484,294 -- Counting with Binary Decision Diagrams

__
TR95-048
| 5th October 1995
__

Helmut Veith#### Succinct Representation and Leaf Languages

__
TR95-049
| 19th October 1995
__

Anna Gal, Avi Wigderson#### Boolean complexity classes vs. their arithmetic analogs

__
TR95-050
| 15th October 1995
__

Oded Goldreich, Noam Nisan, Avi Wigderson#### On Yao's XOR-Lemma

Revisions: 2
,
Comments: 1

__
TR95-051
| 16th October 1995
__

Pascal Koiran#### VC Dimension in Circuit Complexity

__
TR95-052
| 4th October 1995
__

Douglas R. Stinson#### On the Connections Between Universal Hashing, Combinatorial Designs and Error-Correcting Codes

__
TR95-053
| 15th October 1995
__

Petr Slavik#### Improved Performance of the Greedy Algorithm for the Minimum Set Cover and Minimum Partial Cover Problems

__
TR95-054
| 24th November 1995
__

Farid Ablayev, Marek Karpinski#### On the Power of Randomized Branching Programs

__
TR95-055
| 24th November 1995
__

Marek Karpinski, Angus Macintyre#### VC Dimension of Sigmoidal and General Pfaffian Networks

__
TR95-056
| 26th November 1995
__

Oded Goldreich#### Three XOR-Lemmas -- An Exposition

__
TR95-057
| 24th November 1995
__

Dima Grigoriev, Marek Karpinski, A. C. Yao#### An Exponential Lower Bound on the Size of Algebraic Decision Trees for MAX

__
TR95-058
| 20th November 1995
__

Amnon Ta-Shma#### On Extracting Randomness From Weak Random Sources

__
TR95-059
| 21st November 1995
__

Nader H. Bshouty#### The Monotone Theory for the PAC-Model

__
TR95-060
| 21st November 1995
__

Nader H. Bshouty#### A Subexponential Exact Learning Algorithm for DNF Using Equivalence Queries

__
TR95-061
| 27th November 1995
__

Alexander E. Andreev, Andrea E. F. Clementi, Jose' D. P. Rolim#### Hitting sets derandomize BPP

Revisions: 1

__
TR95-062
| 14th December 1995
__

Amir M. Ben-Amram, Zvi Galil#### On Data Structure Tradeoffs and an Application to Union-Find

Comments: 1

__
TR95-063
| 19th December 1995
__

Dima Grigoriev, Marek Karpinski, Friedhelm Meyer auf der Heide, Roman Smolensky#### A Lower Bound for Randomized Algebraic Decision Trees

Amos Beimel, Anna Gal, Michael S. Paterson

The model of span programs is a linear algebraic model of

computation. Lower bounds for span programs imply lower bounds for

contact schemes, symmetric branching programs and for formula size.

Monotone span programs correspond also to linear secret-sharing schemes.

We present a new technique for proving lower bounds for ...
more >>>

Detlef Sieling

In unrestricted branching programs all variables may be tested

arbitrarily often on each path. But exponential lower bounds are only

known, if on each path the number of tests of each variable is bounded

(Borodin, Razborov and Smolensky (1993)). We examine branching programs

in which for each path the ...
more >>>

Marek Karpinski, Alexander Zelikovsky

The Steiner tree problem requires to find a shortest tree connection

a given set of terminal points in a metric space. We suggest a better

and fast heuristic for the Steiner problem in graphs and in

rectilinear plane. This heuristic finds a Steiner tree at ...
more >>>

Martin Dietzfelbinger, Miroslaw Kutylowski, Rüdiger Reischuk

It was shown some years ago that the computation time for many important

Boolean functions of n arguments on concurrent-read exclusive-write

parallel random-access machines

(CREW PRAMs) of unlimited size is at least f(n) = 0.72 log n.

On the other hand, it ...
more >>>

Maciej Liskiewicz, Rüdiger Reischuk

This paper tries to fully characterize the properties and relationships

of space classes defined by Turing machines that use less than

logarithmic space - may they be deterministic,

nondeterministic or alternating (DTM, NTM or ATM).

We provide several examples of specific languages ...
more >>>

Kenneth W. Regan, D. Sivakumar, Jin-Yi Cai

This paper proves that if strong pseudorandom number generators or

one-way functions exist, then the class of languages that have

polynomial-sized circuits is not small within exponential

time, in terms of the resource-bounded measure theory of Lutz.

More precisely, if for some \epsilon > 0 there exist nonuniformly

2^{n^{\epsilon}}-hard ...
more >>>

U. Faigle, S.P. Fekete, W. Hochstättler, W. Kern

The {\it nucleon} is introduced as a new allocation concept for

non-negative cooperative n-person transferable utility games.

The nucleon may be viewed as the multiplicative analogue of

Schmeidler's nucleolus.

It is shown that the nucleon of (not necessarily bipartite) matching

games ...
more >>>

Nader H. Bshouty

Matthias Krause

It is shown that decomposition via Chinise Remainder does not

yield polynomial size depth 3 threshold circuits for iterated

multiplication of n-bit numbers. This result is achieved by

proving that, in contrast to multiplication of two n-bit

numbers, powering, division, and other related problems, the

...
more >>>

Pavel Pudlak, Jiri Sgall

We prove an unexpected upper bound on a communication game proposed

by Jeff Edmonds and Russell Impagliazzo as an approach for

proving lower bounds for time-space tradeoffs for branching programs.

Our result is based on a generalization of a construction of Erdos,

Frankl and Rodl of a large 3-hypergraph ...
more >>>

Roman Bacik, Sanjeev Mahajan

The graph homomorphism problem is a canonical $NP$-complete problem.

It generalizes various other well-studied problems such as graph

coloring and finding cliques. To get a better insight into a

combinatorial problem, one often studies relaxations of the problem.

We define fractional homomorphisms and pseudo-homomorphisms ...
more >>>

Oleg Verbitsky

The parallel repetition conjecture (PRC) of Feige and Lovasz says that the

error probability of a two prover one round interactive protocol repeated $n$

times in parallel is exponentially small in $n$.

We show that the PRC is true in the case when

the bipartite graph of dependence between ...
more >>>

U. Faigle, W. Kern, M. Streng

We show that, for fixed dimension $n$, the approximation of

inner and outer $j$-radii of polytopes in ${\Re}^n$, endowed

with the Euclidean norm, is polynomial.

Bshouty, Cleve, Gavalda, Kannan, Tamon.

We show what happen to learning if the learner can use NP-oracle.

A consequence of our results we show that

If NP\subset P/poly then the polynomial Hierarchy collapses to ZPP^NP

END_OF_DESCRIPTION

Contact: bshouty@cpsc.ucalgary.ca (Nader Bshouty)

U. Faigle, S.P. Fekete, W. Hochstättler, W. Kern

We consider the problem of fair cost allocation for traveling

salesman games for which the triangle inequality holds. We

give examples showing that the core of such games may be

empty, even for the case of Euclidean distances. On the

positive side, we develop an LP-based ...
more >>>

Claudia Bertram, Thomas Hofmeister

We consider the threshold circuit complexity of computing

the multiple product modulo m in threshold circuits.

Jay Belanger, Jie Wang

We show that polynomially rankable distributions

do not provide harder instances than uniform distributions

for NP problems. In particular, we show that if Levin's

randomized tiling problem is solvable in polynomial time on

average, then every NP problem under any p-rankable

...
more >>>

William Hurwood

We consider a dynamic fault diagnosis problem: There are n

processors, to be tested in a series of rounds. In every

testing round we use a directed matching to have some

processors report on the status (good or faulty) of other

processors. Also in each round ...
more >>>

Marek Karpinski, Rutger Verbeek

In contrast to deterministic or nondeterministic computation, it is

a fundamental open problem in randomized computation how to separate

different randomized time classes (at this point we do not even know

how to separate linear randomized time from ${\mathcal O}(n^{\log n})$

randomized time) or how to ...
more >>>

Marek Karpinski, Wojciech Rytter, Ayumi Shinohara

We consider strings which are succinctly described. The description

is in terms of straight-line programs in which the constants are

symbols and the only operation is the concatenation. Such

descriptions correspond to the systems of recurrences or to

context-free grammars generating single words. The descriptive ...
more >>>

Sanjeev Khanna, Rajeev Motwani, Madhu Sudan, Umesh Vazirani

We attempt to reconcile the two distinct views of approximation

classes: syntactic and computational.

Syntactic classes such as MAX SNP allow for clean complexity-theoretic

results and natural complete problems, while computational classes such

as APX allow us to work with problems whose approximability is

well-understood. Our results give a computational ...
more >>>

Mihir Bellare, Oded Goldreich, Madhu Sudan

This paper continues the investigation of the connection between proof

systems and approximation. The emphasis is on proving ``tight''

non-approximability results via consideration of measures like the

``free bit complexity'' and the ``amortized free bit complexity'' of

proof systems.

The first part of the paper presents a collection of new ... more >>>

Günter Hotz, Gero Vierke, Bjoern Schieffer

In this paper the $R$-machines defined by Blum, Shub and Smale

are generalized by allowing infinite convergent computations.

The description of real numbers is infinite.

Therefore, considering arithmetic operations on real numbers should

also imply infinite computations on {\em analytic machines}.

We prove that $\R$-computable functions are $\Q$-analytic.

We show ...
more >>>

Claus-Peter Schnorr, Horst Helmut Hoerner

We introduce new algorithms for lattice basis reduction that are

improvements of the LLL-algorithm. We demonstrate the power of

these algorithms by solving random subset sum problems of

arbitrary density with 74 and 82 many weights, by breaking the

Chor-Rivest cryptoscheme in dimensions 103 and 151 ...
more >>>

Frederic Green

We say an integer polynomial $p$, on Boolean inputs, weakly

$m$-represents a Boolean function $f$ if $p$ is non-constant and is zero (mod

$m$), whenever $f$ is zero. In this paper we prove that if a polynomial

weakly $m$-represents the Mod$_q$ function on $n$ inputs, where $q$ and $m$

more >>>

Eric Allender, Martin Strauss

In (Allender and Strauss, FOCS '95), we defined a notion of

measure on the complexity class P (in the spirit of the work of (Lutz,

JCSS '92) that provides a notion of measure on complexity classes at least

as large as E, and the work of (Mayordomo, Phd. ...
more >>>

Oded Goldreich, Leonid Levin, Noam Nisan

We show how to construct length-preserving 1-1 one-way

functions based on popular intractability assumptions (e.g., RSA, DLP).

Such 1-1 functions should not

be confused with (infinite) families of (finite) one-way permutations.

What we want and obtain is a single (infinite) 1-1 one-way function.

Marek Karpinski, Alexander Zelikovsky

The Steiner tree problem asks for the shortest tree connecting

a given set of terminal points in a metric space. We design

new approximation algorithms for the Steiner tree problems

using a novel technique of choosing Steiner points in dependence

on the possible deviation from ...
more >>>

Dorit Dor, Uri Zwick

Improving a long standing result of Sch\"{o}nhage, Paterson

and Pippenger we show that the MEDIAN of a set containing n

elements can always be found using at most 2.95n comparisons.

This is the full version of the paper. An extended abstract

version ...
more >>>

Nader Bshouty, Christino Tamon

Richard Beigel, David Eppstein

We consider worst case time bounds for NP-complete problems

including 3-SAT, 3-coloring, 3-edge-coloring, and 3-list-coloring.

Our algorithms are based on a common generalization of these problems,

called symbol-system satisfiability or, briefly, SSS [R. Floyd &

R. Beigel, The Language of Machines]. 3-SAT is equivalent to

(2,3)-SSS while the other problems ...
more >>>

Christoph Meinel, Stephan Waack

We investigate the probabilistic communication complexity

(more exactly, the majority communication complexity,)

of the graph accessibility problem GAP and

its counting versions MOD_k-GAP, k > 1.

Due to arguments concerning matrix variation ranks

and certain projection reductions, we prove

that, for any partition of the input variables,

more >>>

Richard Beigel

We classify the univariate functions that are relativizable

closure properties of GapP, solving a problem posed by Hertrampf,

Vollmer, and Wagner (Structures '95). We also give a simple proof of

their classification of univariate functions that are relativizable

closure properties of #P.

Richard Beigel, William Gasarch, Efim Kinber

For a set A and a number n let F_n^A(x_1,...,x_n) =

A(x_1)\cdots A(x_n). We study how hard it is to approximate this

function in terms of the number of queries required. For a general

set A we have exact bounds that depend on functions from coding

theory. These are applied ...
more >>>

Richard Beigel, Howard Straubing

Identify a string x over {0,1} with the positive integer

whose binary representation is 1x. We say that a self-reduction is

k-local if on input x all queries belong to {x-1,...,x-k}. We show

that all k-locally self-reducible sets belong to PSPACE. However, the

power of k-local self-reductions changes drastically between ...
more >>>

Joe Kilian, Erez Petrank

We consider noninteractive zero-knowledge proofs in the shared random

string model proposed by Blum, Feldman and Micali \cite{bfm}. Until

recently there was a sizable polynomial gap between the most

efficient noninteractive proofs for {\sf NP} based on general

complexity assumptions \cite{fls} versus those based on specific

algebraic assumptions \cite{Da}. ...
more >>>

Tomoyuki Yamakami

This paper studies distributions which

can be ``approximated'' by sampling algorithms in time polynomial in

the length of their outputs. First, it is known that if

polynomial-time samplable distributions are polynomial-time

computable, then NP collapses to P. This paper shows by a simple

...
more >>>

Uri Zwick, Michael S. Paterson

We study the complexity of finding the values and optimal strategies of

MEAN PAYOFF GAMES on graphs, a family of perfect information games

introduced by Ehrenfeucht and Mycielski and considered by Gurvich,

Karzanov and Khachiyan. We describe a pseudo-polynomial time algorithm

for the solution of such games, the decision ...
more >>>

Alexander E. Andreev, Andrea E. F. Clementi, Jose Rolim

We prove an optimal bound on the Shannon function

$L(n,m,\epsilon)$ which describes the trade-off between the

circuit-size complexity and the degree of approximation; that is

$$L(n,m,\epsilon)\ =\

\Theta\left(\frac{m\epsilon^2}{\log(2 + m\epsilon^2)}\right)+O(n).$$

Our bound applies to any partial boolean function

and any ...
more >>>

Beate Bollig, Ingo Wegener

Computational complexity is concerned with the complexity of solving

problems and computing functions and not with the complexity of verifying

circuit designs.

The importance of formal circuit verification is evident.

Therefore, a framework of a complexity theory for formal circuit

verification with binary decision diagrams ...
more >>>

Eric Allender, Jia Jiao, Meena Mahajan, V. Vinay

We investigate the phenomenon of depth-reduction in commutative

and non-commutative arithmetic circuits. We prove that in the

commutative setting, uniform semi-unbounded arithmetic circuits of

logarithmic depth are as powerful as uniform arithmetic circuits of

polynomial degree; earlier proofs did not work in the ...
more >>>

Carsten Damm, Stasys Jukna, Jiri Sgall

We introduce the model of conservative one-way multiparty complexity

and prove lower and upper bounds on the complexity of pointer jumping.

The pointer jumping function takes as its input a directed layered

graph with a starting node and layers of nodes, and a single edge ...
more >>>

Moni Naor, Omer Reingold

A pseudo-random function is a fundamental cryptographic primitive

that is essential for encryption, identification and authentication.

We present a new cryptographic primitive called pseudo-random

synthesizer and show how to use it in order to get a

parallel construction of a pseudo-random function.

We show an $NC^1$ implementation of synthesizers ...
more >>>

Vince Grolmusz

We examine the power of Boolean functions with low L_1 norms in several

settings. In large part of the recent literature, the degree of a polynomial

which represents a Boolean function in some way was chosen to be the measure of the complexity of the Boolean function.

However, some functions ...
more >>>

Martin Loebbing, Ingo Wegener

An increasing number of results in graph theory, combinatorics and

theoretical computer science is obtained with the help of computers,

e.g. the proof of the Four Colours Theorem or the computation of

certain Ramsey numbers. Binary decision diagrams, known as tools in

hardware verification ...
more >>>

Helmut Veith

In this paper, we present stronger results in the theory of succinct

problem representation by boolean circuits, and establish a close

relationship between succinct problems and leaf languages. As

a major tool, we use quantifierfree projection reductions

from descriptive complexity theory.

In particular, we show that the succinct upgrading ... more >>>

Anna Gal, Avi Wigderson

This paper provides logspace and small circuit depth analogs

of the result of Valiant-Vazirani, which is a randomized (or

nonuniform) reduction from NP to its arithmetic analog ParityP.

We show a similar randomized reduction between the

Boolean classes NL and semi-unbounded fan-in Boolean circuits and

their arithmetic counterparts. These ...
more >>>

Oded Goldreich, Noam Nisan, Avi Wigderson

Pascal Koiran

The main result of this paper is a Omega(n^{1/4}) lower bound

on the size of a sigmoidal circuit computing a specific AC^0_2 function.

This is the first lower bound for the computation model of sigmoidal

circuits with unbounded weights. We also give upper and lower bounds for

the ...
more >>>

Douglas R. Stinson

In this primarily expository

paper, we discuss the connections between two popular and useful

tools in theoretical computer science, namely,

universal hashing and pairwise

independent random variables; and classical combinatorial stuctures

such as error-correcting codes, balanced incomplete block designs,

difference matrices

...
more >>>

Petr Slavik

We establish significantly improved bounds on the performance of the greedy

algorithm for approximating MINIMUM SET COVER and MINIMUM PARTIAL COVER. Our

improvements result from a new approach to both problems. In particular,

(a) we improve the known bound on the performance ratio of the greedy ...
more >>>

Farid Ablayev, Marek Karpinski

We define the notion of a randomized branching program in

the natural way similar to the definition of a randomized

circuit. We exhibit an explicit function $f_{n}$ for which

we prove that:

1) $f_{n}$ can be computed by polynomial size randomized

...
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, that the

VC Dimension of analog neural networks with the sigmoidal

activation function $\sigma(y)=1/1+e^{-y}$ ...
more >>>

Oded Goldreich

We provide an exposition of three Lemmas which relate

general properties of distributions

with the exclusive-or of certain bit locations.

The first XOR-Lemma, commonly attributed to U.V. Vazirani,

relates the statistical distance of a distribution from uniform

to the maximum bias of the xor of certain bit positions.

more >>>

Dima Grigoriev, Marek Karpinski, A. C. Yao

We prove an exponential lower bound on the size of any

fixed-degree algebraic decision tree for solving MAX, the

problem of finding the maximum of $n$ real numbers. This

complements the $n-1$ lower bound of Rabin \cite{R72} on

the depth of ...
more >>>

Amnon Ta-Shma

We deal with the problem of extracting as much randomness as possible

from a defective random source.

We devise a new tool, a ``merger'', which is a function that accepts

d strings, one of which is uniformly distributed,

and outputs a single string that is guaranteed ...
more >>>

Nader H. Bshouty

We show that a DNF formula that has a CNF representation that contains

at least one ``$1/poly$-heavy''

clause with respect to a distribution $D$ is weakly learnable

under this distribution. So DNF that are not weakly

learnable under the distribution $D$ do not have

any ``$1/poly$-heavy'' clauses in any of ...
more >>>

Nader H. Bshouty

We present a $2^{\tilde O(\sqrt{n})}$ time exact learning

algorithm for polynomial size

DNF using equivalence queries only. In particular, DNF

is PAC-learnable in subexponential time under any distribution.

This is the first subexponential time

PAC-learning algorithm for DNF under any distribution.

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

We show that hitting sets can derandomize any BPP-algorithm.

This gives a positive answer to a fundamental open question in

probabilistic algorithms. More precisely, we present a polynomial

time deterministic algorithm which uses any given hitting set

to approximate the fractions of 1's in the ...
more >>>

Amir M. Ben-Amram, Zvi Galil

Consider a problem involving updates and queries of a data structure.

Assume that there exists a family of algorithms which exhibit a

tradeoff between query and update time. We demonstrate a general

technique of constructing from such a family

a single algorithm with best amortized time. We indicate some ...
more >>>

Dima Grigoriev, Marek Karpinski, Friedhelm Meyer auf der Heide, Roman Smolensky

We extend the lower bounds on the depth of algebraic decision trees

to the case of {\em randomized} algebraic decision trees (with

two-sided error) for languages being finite unions of hyperplanes

and the intersections of halfspaces, solving a long standing open

problem. As an application, among ...
more >>>