0368.4283 Space-Bounded Computation

CS dept, Tel-Aviv University, Spring 2018

 

We meet at Holtzblat 07.


 

Syllabus (including links and references)

 

The exercise pool (HW5 is due June 12)

The Take-Home exam (due July 12)


 

 

Lecture Tuesday, 16:00-19:00, Holtzblat 07

Instructor Amnon Ta-Shma | Schreiber 127 | 5364

Open for Undergrad and grad students.

Grading policy 50% take-home exam, the rest is exercises and based on participation in class.

 

Textbooks and links

 

See the syllabus.

 

 

 

 

Date

Class Topic

Lecture notes

References

1

March 6

Introduction. Basic problems.
Expanders.

2

March 13

Undirected graphs as operators and basic properties, USTCONN in RL, Universal traversal sequences.

Lecture 2

 

3

March 20

The Expander Mixing Lemma, Expanders as samplers

Lecture 3

 

4

March 27

Rotation maps, tensor product, the replacement product.

Lecture 4

 

5

April 17

A fully-explicit family of expander graphs. The derandomized squaring product. USTCONN in L with the derandomized squaring product (started).

Lecture 5

 

6

April 24

USTCONN in L with the derandomized squaring product.

Lecture 6

 

7

May 1

Universal traversal sequences and universal exploration sequences. USTCONN with Reingold's algorithm. Connectivity in regular directed graphs. Extractors an exposition.

Lecture 7a, Lecture 7b

Salil Vadhan Pseudorandomness (for extractors)

8

May 8

Extractors. Affine extractors (existence). Seeded extractors. Extractors and samplers. Seeded extractors from random walks over an expander. The GUV condenser (without proof).

Lecture 8

 

9

May 15

Pseudorandomness. PRGs. Uniformity vs. non-uniformity. Branching-programs (BPs) and PRGs against BPs. The INW generator.

Lecture 9-10

 

10

May 22

Strong extractors, extractors from 2UFOHFs. Nisan's generator.

Lecture 9-10

 

11

May 29

BPL in SC, The Hoza-Zuckerman HSG.

Lecture 11

 

12

June 5

Zaks-Zhou's BPL in L^(3/2).

 

 

13

June 12

Solving Laplacian systems space-efficiently (due to MRSV).

Lecture 13