Date

Speaker

Title

 

 

No meeting first week.

 

1

2-Mar-05

Amnon Ta-Shma

Introduction

2

9-Mar-05

Eyal Kaplan

BP H SPACE (S) DSPACE (S 3/2)

 

 

See also:

Time-Space Tradeoff In Derandomizing Probabilistic Logspace.

 

3

16-Mar-05

Oded Schwartz

An NC Algorithm for Minimum Cuts by David R. Karger, Rajeev Motwani

4

23-Mar-05

 

 

5

30-Mar-05

Maya Ben-Ari

Undiercted Connectivity in log^1.5(n) space

6

6-Apr-05

Moran Levi

A nearly optimal time-space lower bound for directed st- connectivity on the NNJAG model

7

13-Apr-05

Avi Ben-Aroya

Using Nondeterminism to Amplify Hardness.

 

 

Pesach Vacation

 

8

4-May-05

Liam Roditty

A SUBLINEAR SPACE, POLYNOMIAL TIME ALGORITHM FOR DIRECTED s t connectivity.

 

 

Memorial Day

 

9

18-May-05

Daniel Deutch

Derandomization that is rarely wrong from short advice that is typically good

10

25-May-05

Eran rom

The two Zig-zag papers:

 

Entropy Waves, The Zig-Zag Graph Product, and New Constant-Degree Expanders and Extractors.

Randomness Conductors and Constant-Degree Lossless Expanders.

11

1-Jun-05

?