0368.4283
Space-Bounded Computation
CS dept, Tel-Aviv University, Spring
2018
|
Syllabus (including
links and references)
|
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. |
||
|
2 |
March 13 |
Undirected
graphs as operators and basic properties, USTCONN in RL, Universal traversal
sequences. |
|
|
|
3 |
March 20 |
The
Expander Mixing Lemma, Expanders as samplers |
|
|
|
4 |
March 27 |
Rotation
maps, tensor product, the replacement product. |
|
|
|
5 |
April 17 |
A
fully-explicit family of expander graphs. The derandomized
squaring product. USTCONN in L with the derandomized
squaring product (started). |
|
|
|
6 |
April 24 |
USTCONN
in L with the derandomized squaring product. |
|
|
|
7 |
May 1 |
Universal
traversal sequences and universal exploration sequences. USTCONN with Reingold's algorithm. Connectivity in regular directed
graphs. Extractors – an exposition. |
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). |
|
|
|
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 |
|