4810-1163 Advanced Algorithms 先端アルゴリズム論 (Summer 2014)

Thursday 2:50–4:20 pm, Science Building 7, Room 007 (despite what the printed timetable says)

Lecturers: H. Imai, A. Kawamura, F. Le Gall, T. Shibuya

Schedule

Introduction (Imai) April 3, 10

• Introduction [MR, Chapter 1]

Part 1: Algebraic and number-theoretic algorithms (Le Gall)

• Freivalds' algorithm for matrix product verification, polynomial identity testing [MR, Sections 7.1, 7.2, 7.3] (April 17)
• Universal hashing [MR, Section 8.4] (April 24)
• Primality testing 1: preliminaries, modular arithmetic, Fermat’s little theorem, application (overview of the RSA cryptosystem) [MR, Chapter 14] (May 8)
• Primality testing 2: quadratic residues, Euler’s criterion, Solovay-Strassen primality testing algorithm [MR, Chapter 14] (May 15)
• Assignment 1 (link outdated)

Part 2: Probabilistic methods, random walks, and derandomization (Kawamura) May 22, 29, June 5, 12

• Probabilistic methods, maximum satisfiability [MR, Section 5.2] (May 22)
• The Lovász Local Lemma [MR, Section 5.5] and its algorithmic version [MT10] (May 29)
• Random walks [MR, Sections 6.3, 6.5 and 6.6] (June 5)
• Expanders [MR, Sections 5.3, 6.7 and 6.8] (June 12)
• Assignment 2: English, Japanese (link outdated)

Part 3: String algorithms (Shibuya) June 19, 26, July 3, 10

• Slides are here (under “先端アルゴリズム論”)
• Assignment 3 is at the end of the slides for July 10

Grades

Submit two of the three assignments (in English or Japanese) by Thursday, July 24, 2014 to the “assignments” box (and not the postboxes of the lecturers) in front of the department office 103 on the ground floor of Science Building 7 (note that the building closes at 6 pm). Please prepare your two submissions separately and indicate the name of the corresponding lecturer on the front pages.

References

[MR]

R. Motwani and P. Raghavan, Randomized Algorithms, Cambridge University Press, 1995.

[MT10]

R. Moser and G. Tardos, A constructive proof of the general Lovász Local Lemma, Journal of the ACM 57(2), Article 11, 2010.