Weekly lecture slides and other materials are published here.
For Part 1, supporting reading material includes:
- J. von zur Gathen, J. Gerhard, Modern Computer Algebra, 3rd ed., Cambrige University Press, 2013.
- S. Gao, A new algorithm for decoding Reed-Solomon codes, Communications, Information and Network Security, The Springer International Series in Engineering and Computer Science, Vol. 712, Springer, 2003, pp. 55–68.
- M. L. Carmosino, J. Gao, R. Impagliazzo, I. Mihajlin, R. Paturi, S. Schneider, Nondeterministic extensions of the strong exponential time hypothesis and consequences for non-reducibility, ITCS'16 Proceedings of the 2016 ACM Conference on Innovations in Theoretical Computer Science, ACM, 2016, pp. 261–270.
- R. R. Williams, Strong ETH breaks with Merlin and Arthur: short non-interactive proofs of batch evaluation, 31st Conference on Computational Complexity (CCC 2016), Leibniz International Proceedings in Informatics (LIPIcs), Vol. 50, Schloss Dagstuhl – Leibniz-Zentrum für Informatik, Dagstuhl Publishing, Article No. 2, pp. 2:1–2:17. (arxiv)
- A. Björklund, P. Kaski, How proofs are prepared at Camelot, PODC'16 Proceedings of the 2016 ACM Symposium on Principles of Distributed Computing, ACM, 2016, pp. 391–400. (arxiv)
For part 2, we will not follow any specific materials. However, the instructor provides two lecture notes which summarize the content discussed in the lectures. I
Part 2.A: Competitive analysis
Extra reading:1. Online algorithms' survey, by Susanne Albers,
2. The Primal-Dual approach by Buchbinder and Naor [pdf]. Please read Chapter 1 to 4.
Part 2.B: Online prediction and applications
- A survey by Arora et al.