0368.4159
Randomized algorithms and de-randomization
CS dept, Tel-Aviv University, Fall 2015
|
Ben Lee Volk
|
|
The White-Box case is from a paper by Ran and Amir: Deterministic
Polynomial Identity Testing in Non Commutative Models But there's a two-page explanation of
this in section 4.5 of the arithmetic circuits survey by Shpilka
and Yehudayoff, which already appears on the
website, so maybe it's better to refer people to there. The Black-Box case is from a paper by Agrawal
et al. Hitting-sets for
ROABP and Sum of Set-Multilinear circuits The paper is a bit long but we will only be interested in
(a subset of the) things that appear on pages 1-11. |
Gonen Krak
|
|
Pseudorandom Walks on Regular Digraphs and the RL vs. L Problem éù ùí 3 ð÷åãåú, ëàùø àú 2 äð÷åãåú
äøàùåðåú òùéðå áëéúä åáúøâéìéí, àæ ääøöàä úéäéä
áòé÷ø òì äð÷åãä äùìéùéú(ùäéà âí òé÷ø äîàîø) |
|
|
|
|
|
|
|
|
|
|
|
|
|
Lectures Instructor Open to |
Monday,
10:10-13:00, Kaplun 319 Amnon Ta-Shma | Schreiber 127 | 5364 Undergrad
and grad students. |
|
Textbooks |
·
[V] Salil
Vadhan : Pseudorandomness ·
[LD]
Laskshmivarahan,
Dhall : Analysis and Design of Parallel Algorithms ·
[SY]
Amir Shpilka,
Amir Yehudayoff
: Arithmetic
Circuits: a survey of recent results and open questions. · [MR] Rajeev Motwani, Prabhakar Raghavan Randomized Algorithms |
|
Grading policy |
Homework
50%, Paper presentation 50% |
Links
|
·
L. Lovasz Random
walks on graphs: A Survey ·
M. Luby, A. Wigderson Pairwise Independence and Derandomization Foundation and Trends in
Theoretical Computer Science, vol. 1, no. 4, pp. 237-301, 2005. ·
A. Wigderson Derandomizing BPP - A survey (lecture notes) Scribe: Irit
Dinur, 2002. ·
A. Wigderson Derandomizing
BPP - Lecture notes of a Hebrew University course) Scribe: Ronen Shaltiel,
1998. |
|
Date |
Class Topic |
Lercture notes (in Hebrew) |
References and notes |
|
1. Oct 27 |
A
randomized algorithm for Perfect matching (PM). The Schwartz-Zippel lemma.
Some complexity classes. The PRAM model. NC^k and NC. RNC. Arithmetic
circuits. DET is in SAC^1. |
[S] 2.1,2.2 [LD] 7.2 [MR] 12.4 deals with graphs
(rather than bipartite graphs) and with the problem of finding a matching
(rather than just recognizing its existence) |
|
|
2. Nov 3 |
PIT in coRP. STCON. USTCON in RL. |
||
|
3. Nov 10 |
Completing USTCON in RL. |
|
|
|
4.
Nov 17 |
Finding a maximal independent set
in NC. Pair-wise and K-wise independence.
A construction of a k-wise independent space. De-randomizing the small space
maximal-IS algorithm. Markov, Chebychev,
chernoff. |
|
|
|
5. Nov 24 |
Tail inequalities for k-wise
independence. Estimating the second moment with a streaming algorithm. Deterministic amplification:
complete independence, pair-wise independendce,
k-wise independence, walks on an undirected graphs (to be continued). |
|
N. Alon, Y. Matias
and M. Szegedy. The space complexity of
Approximating the frequency moments. |
|
6. Dec 1 |
Deterministic amplification of
one-sided by walking over an expander. Two-sided amplification, the Chernoff bound for expander walks (no proof). Powering, tensoring,
replacement product. |
|
Alexander
Healy, Randomness-Efficient
Sampling within NC^1 (see section 5). |
|
7. Dec 8 |
Constructing fully explicit
expanders with the zig-zag product. |
Entropy Waves, the Zig-Zag Graph Product, and New Constant-Degree Expanders and Extractors by Omer Reingold, Salil P. Vadhan, and Avi Wigderson |
|
|
8. Dec 15 |
Undirected connectivity in L. UTS
for consistently labeled graphs. |
Undirected
connectivity in log-space by Omer Reingold |
|
|
9. Dec 22 |
Dispersers. Definition,
non-explicit construction and lower bounds. Extractors. Parameters of
non-explicit and optimal extractors. Deterministic amplification
revisited. The privacy amplification problem. |
||
|
10. Dec 29 |
Branching programs. PRG for
space-bounded computation. INW: A PRG for RL with log^2n seed length. |
Pseudorandomness for Network Algorithms by R. Impagliazzo, N. Nisan, and A. Wigderson. Randomness is Linear in Space by N. Nisan
and D. Zuckerman. |
|
|
11. Jan 5 |
Nisan’s
generator. RL in Timespace(poly(n),log^2n). |
RL is contained in SC by N. Nisan. |
|
|
12. Jan 12 |
RL in Space(log^1.5n) Error correcting codes. A
non-explicit construction and some lower bounds. |
BPHSPACE⊆DPSACE(S3/2) by Michael Saks and Shiyu Zhou |
|
|
13. Feb 4 |
1-bit strong extractors and error
correcting codes. Designs. Trevisan’s
extractor. |
Extractors
and Pseudorandom Generators by
Luca Trevisan |
|
|
14. Feb 11 |
NW generator: Hardness ve. Randomness. A PRG for BPP under average-case
assumptions. |
Hardness vs. Randomness by N.
Nisan and A. Wigderson |
|
|
Not this year |
Average-case vs. worst-case
hardness assumptions. Hardness amplification. Error correcting codes. Local
decoding. Local decoding and hardness amplification. Local decoding RD codes.
Local decoding RM codes. Conditional PRG for BPP under worst-case
assumptions. The reverse direction: Derandomization implies some kind of non-uniform hardness
for a uniform function. |
|