Topic 1: Markov Decision Processes and Bandit Problems

• Main papers:
  • J. N. Tsitsiklis, "A Short Proof of the Gittins Index Theorem", Annals of Applied Probability, Vol. 4, No. 1, 1994, pp. 194-199.
  • T.L. Lai and Herbert Robbins, Asymptotically Efficient Adaptive Allocation Rules, Advances In Applied Mathemattcs 6,4-22
  • Tze Leung Lai, Adaptive Treatment Allocation and the Multi-Armed Bandit Problem, The Annals of Statistics, Vol. 15, No. 3. (Sep., 1987), pp. 1091-1114.
  • Abraham D. Flaxman, Adam Tauman Kalai, H. Brendan McMahan, Online convex optimization in the bandit setting: gradient descent without a gradient,
  • Peter Auer, Nicol O Cesa-bianchi, Yoav Freund, Robert E. Schapire, The Nonstochastic Multiarmed Bandit Problem, SIAM Journal on Computing, Vol 32 (2002)

   

Topic 2: Optimization Relaxation Methods

• Main papers:
  • Monique Laurent, A comparison of the Sherali-Adams, Lovasz-Schrijver and Lasserre relaxations for 0-1 programming, 2002
  • L. Lovasz and A. Schrijver, Cones of matrices and set-functions and 0-1 optimization, SIAM J. Optim. 1 (1991), 166--190.
  • M. Grotschel, L. Lovasz, and A. Schrijver, Polynomial algorithms for perfect graphs, Topics on perfect graphs, North-Holland Math. Stud., 88, North-Holland, Amsterdam-New York, 1984, pp. 325--356.
 

Topic 3: Good-Turing estimator

• Main papers:
  • Alon Orlitsky, Narayana P. Santhanam, Junan Zhang, Always Good Turing: Asymptotically Optimal Probability Estimation, FOCS 2003
  • McAllester, D. A. and Schapire, R. E. 2000. On the Convergence Rate of Good-Turing Estimators In Proceedings of the Thirteenth Annual Conference on Computational Learning theory (June 28 - July 01, 2000).
 

Topic 4: Graph convergence

• Main papers:
  • L. Lovasz and B. Szegedy: Limits of dense graph sequences, J. Comb. Theory 96 (2006), 933-957.
  • L. Lovasz and B. Szegedy: Szemeredi's Lemma for the analyst, J. Geom. and Func. Anal. 17 (2007), 252-270.
  • L. Lovasz and B. Szegedy: Testing properties of graphs and functions,
  • C. Borgs, J. Chayes, L. Lovasz, V.T. Sos and K. Vesztergombi: Convergent Sequences of Dense Graphs I: Subgraph Frequencies, Metric Properties and Testing,
  • C. Borgs, J. Chayes, L. Lovasz, V.T. Sos and K. Vesztergombi: Convergent Sequences of Dense Graphs II: Multiway Cuts and Statistical Physics
 

Topic 5: Information-theoretic security and Cryptography

• Main papers: