CSCI 670, Fall 2019


In Spring 2015, CS department has decided to make CSCI 670 a required class for all its Ph.D. students. While I personally never prefer to make any class that I teach a required class  computer science has evolved so rapidly for me or maybe anyone to determine what each successful student should take  this requirement has inspired me to modernize this class. In the age of Big Data, efficient algorithms are now in higher demand more than ever before. While Big Data takes computing into the asymptotic world envisioned by our pioneers, it also challenges the classical notion of efficient algorithms: Algorithms that used to be considered efficient, according to polynomialtime characterization, may no longer be adequate for solving today's problems. It is not just desirable, but essential, that efficient algorithms should be scalable. In other words, their complexity should be nearly linear or sublinear with respect to the problem size. Thus, scalability, not just polynomialtime computability, should be elevated as the central complexity notion for characterizing efficient computation. This revision  an evolving project  has shifted the focus of this class towards "modern" algorithm design and analysis, both in techniques/methodologies and example problems. While the class materials cover mostly known and wellestablished results in the literature, I will also cover topics of potential research interests. I hope each student will be able to learn something to benefit his/her research. Students in the class are expected to have a reasonable degree of mathematical sophistication, and to be familiar with the basic notions of algorithms and data structures, discrete mathematics, probability, and complexity theory. Specifically, the following will be assumed:
This is a theory class. Students will be required and tested not just to design algorithms but also to rigorously characterize their performance. This is also a fastpaced class. If a student does not do the reading assignments and homeworks in a timely fashion, then they will experience limited benefit from the class. 

Professor ShangHua Teng 
Hrayr Harutyunyan 

Textbook 

Lectures 

Grades 

Homeworks 

Integrity 
Plagiarism and other antiintellectual behavior will be dealt with severely. This includes the possibility of failing the course or being expelled from the University. 
Lec# 
Date

Topics and/or Events  Required Reading  "Fun" Research Reading 
1

08/26

General Topics:
Class Organization: Theoretical Computer Science
Specific Subjects:
***************************************
Type of Computational Problems
Type of Algorithms
Complexity Theory and Algorithm Analysis
*************************************** 
Book 1: Chapters 13 Search on the Web. For example: "google P NP" "google linear programming" "google graph partitioning" "google clustering" "google nearest neighbors" "google Nash Equilibrium" "google Page Rank" "google network flow" "google scalable algorithms 
Lipton's brilliant blog: "Goedel's Lost Letter and P=NP" 
2

08/28

General Topics:
Algorithms and Heuristics Specific Subjects: merging files, merging lists, Huffman codes, mergesort revisit clustering and minimum spanning trees Algorithmic Techniques: greedy algorithms Mathematical Concepts: prefixfree codes minmum spanning trees lowstretch spanning trees  Book 1: Chapter 4 
Noga Alon, Richard M. Karp, David Peleg, and Douglas West,
A GraphTheoretic Game and Its Application to the kServer Problem
Michael Elkin, Yuval Emek, Daniel A. Spielman, ShangHua Teng LowerStretch Spanning Trees 
3

09/02

Labor Day (No Class)  
4

09/04

General Topics:
Graph Algorithms Specific Subjects: shortest paths in a graph Algorithmic Techniques: greedy algorithms Mathematical Concepts: shortest path graph metrics network routing  Book 1: Chapter 4  Thorup and Zwick: Approximate distance oracles, ournal of the ACM (JACM), Volume 52 Issue 1, January 2005 
5

09/09

General Topics:
Network Analysis Specific Subjects: social influence Algorithmic Techniques: greedy algorithms submodular function maximization Mathematical Concepts: network process triggering models submodular functions 
David Kempe, Jon Kleinberg, and Eva Tardos,
Maximizing the Spread of Influence through a Social Network
George Nemhauser, Laurence Wolsey, and Marshall Fisher: An analysis of the approximations for maximizing submodular set functions I. Mathematical Programming, 14(1), 265294, 1978
Andreas Krause,
Submodular Function Maximization

Christian Borgs, Michael Brautbar, Jennifer Chayes, Brendan Lucier,
Maximizing Social Influence in Nearly Optimal Time
Y. Tang, X. Xiao, and Y. Shi. Influence maximization: nearoptimal time complexity meets practical efficiency. In Proceedings of the ACM SIGMOD International Conference on Management of Data, SIGMOD, pages 7586, 2014 Y. Tang, Y. Shi, and X. Xiao. Influence maximization in nearlinear time: A martingale approach. In Proceedings of the ACM SIGMOD International Conference on Management of Data, SIGMOD, pages 15391554, 2015 
6

09/11

General Topics:
Optimization and Approximation Specific Subjects: set cover Algorithmic Techniques: greedy algorithms Mathematical Concepts: potential analysis  Book 1: Chapter 11 (11.1  11.5, 11.8)  
7

09/16

General Topics:
Geometric Data Specific Subjects: clustering dimension reduction Algorithmic Techniques: iterative algorithms local search; potential games Mathematical Concepts: Voronoi diagrams wellseparated clusters outliers clustering stability singular value decomposition 
S. Lloyd. Least squares quantization in PCM. IEEE Transactions on Information Theory, 28(2), 129137, 2006
Search on the Web. For example:

D. Arthur, B. Manthey, and H. RoLlin. Smoothed analysis of the k means method. Journal of the ACM, 58(5), 19:119:31, 2011
Balcan, Blum, and Gupta: Approximate clustering without the approximation 
8

09/18

2:003:00pm: Quiz 1
3:003:50pm: Discussion: network centrality 

9

09/23

General Topics:
Geometric Data Specific Subjects: robust statistics median and extensions Algorithmic Techniques: sampling and randomization local data analysis evolutionary algorithms Mathematical Concepts: centerpoints VC dimensions tail analysis convex geometry: the theorems of Radon and Helly  Book 2: Chapter 5 
V. N. Vapnik and A. Y. Chervonenkis. On the uniform convergence of relative frequencies of events to their probabilities. Theory of Probability and Its Applications, 16, 264280, 1971
M. Hubert and P. J. Rousseeuw. The catline for deep regression. J. Multivariate Analysis, 66:270296, 1998 N. Amenta, M. Bern, D. Eppstein, and S.H. Teng. Regression depth and center points. Discrete & Computational Geometry, 23(3), 305323, 2000 
10

09/25

General Topics:
Geometric Data Specific Subjects: geometric divide and conquer Algorithmic Techniques: divide and conquer generalized binary search Mathematical Concepts: NNG point location data structures  Book 2: Chapter 5
Miller, Teng, Thurston, Vavasis: Separators for spherepackings and nearest neighbor graphs, Journal of the ACM, Volume 44 Issue 1, Jan. 1997 
Bentley: Multidimensional divideandconquer, Communications of the ACM, Volume 23 Issue 4, April 1980
Lipton, Rose, and Tarjan: Generalized nested dissection, SIAM Journal on Numerical Analysis 16 (2): 346358 Gilbert and Tarjan: The analysis of a nested dissection algorithm, Numerische Mathematik 50 (4): 377404. 
11

09/30

General Topics:
Geometric Data Specific Subjects: geometric separators and clustering geometric graphs: grids, nearest neighbor graphs (NNG), planar graphs, and meshes Algorithmic Techniques: sampling and randomization divide and conquer Mathematical Concepts: planar and geometric separator theorems geometric duality Koebe embedding and the lake problem geometric duality Delaunay triangulations  Book 2: Chapter 5
Lipton and Tarjan: "A Separator Theorem for Planar Graphs," SIAM J. Appl. Math. 36, 177189 (1979) Miller, Teng, Thurston, Vavasis: Separators for spherepackings and nearest neighbor graphs, Journal of the ACM, Volume 44 Issue 1, Jan. 1997 
Spielman and Teng, "Spectral partitioning works: Planar graphs and finite element meshes", Linear Algebra and its Applications Volume 421, Issues 23, 1 March 2007, Pages 284305 (Special Issue in honor of Miroslav Fiedler) 
12

10/02

General Topics:
FFT Specific Subjects: machine learning perspectives of FFT Discrete Fourier Transform inverse DFT Algorithmic Techniques: divide and conquer algorithmic view of proof by induction Mathematical Concepts: complex numbers Fundamental Theorem of Algebra  Book 1: Chapter 5
Search on the Web. For example: "google FFT" "google Discrete Fourier Transform" "google Fourier Transform" "google Fourier Analysis" 

13

10/07

General Topics:
FFT Specific Subjects: integer multiplication Algorithmic Techniques: divide and conquer Mathematical Concepts: linear algebra: review polynomials representations evaluation interpolation convolution and polynomial multiplication  Book 1: Chapter 5
Search on the Web. For example: "google FFT" "google Discrete Fourier Transform" "google Fourier Transform" "google Fourier Analysis" 

14

10/09

General Topics:
Binary Search in Graphs 
Ehsan EmamjomehZadeh, David Kempe, Vikrant Singhal: Deterministic and Probabilistic Binary Search in Graphs. In Proc. of STOC 2016.  
15

10/14

General Topics:
Interactive Learning 
Ehsan EmamjomehZadeh, David Kempe: A General Framework for Robust Interactive Learning. In Proc. of NIPS 2017.  
16

10/16

Midterm: good luck  
17

10/21

General Topics:
Graph Algorithms Specific Subjects: maximum flow and minimum cuts in a network Algorithmic Techniques: iterative algorithms Mathematical Concepts: linear programming duality  Book 1: Chapter 7  Tom Leighton and Satish Rao: Multicommodity maxflow mincut theorems and their use in designing approximation algorithms, Journal of the ACM, Volume 46 Issue 6, Nov. 1999 
18

10/23

General Topics:
Network Analysis Specific Subjects: network centrality PageRank; personalized PageRank Algorithmic Techniques: sampling and randomization local network exploration simulated annealing Mathematical Concepts: Markov chain matrix powers randomwalk matrix polynomials  Book 2: Chapter 3  S. Brin and L. Page. The anatomy of a largescale hypertextual Web search engine. Computer Networks, 30(17), 107117, 1998 
19

10/28

General Topics:
Network Analysis Specific Subjects: significant PageRank identification Algorithmic Techniques: sampling and randomization local network exploration simulated annealing Mathematical Concepts: personalized PageRank matrix centrality conforming Markov chain  Book 2: Chapter 3  
20

10/30

General Topics:
Spectral Graph Theory Specific Subjects: Laplacian matrices Algorithmic Techniques: spectral method Mathematical Concepts: clusterability conductance spectral embeddings Rayleigh quotient 
Book 2: Chapter 4 
M. Fiedler. Algebraic connectivity of graphs. Czechoslovak Mathemat ical Journal, 23(2):298  305, 1973 F. R. K. Chung. Spectral Graph Theory (CBMS Regional Conference Series in Mathematics, No. 92). American Mathematical Society, Feb. 1997.

21

11/04

General Topics:
Spectral Graph Theory Specific Subjects: graph partitioning Algorithmic Techniques: sweep and spectral partitioning local clustering algorithms Mathematical Concepts: Cheeger's inequality 
Book 2: Chapter 4 
Spielman and Teng, "Spectral partitioning works: Planar graphs and finite element meshes", Linear Algebra and its Applications
Volume 421, Issues 23, 1 March 2007, Pages 284305 (Special Issue in honor of Miroslav Fiedler)
Frank McSherry, Spectral Partitioning of Random Graphs, FOCS '01 
22

11/06

General Topics:
Spectral Graph Theory Specific Subjects: scalable Laplacian paradigm Algorithmic Techniques: SDD solvers Mathematical Concepts: spectral approximation learning on graphs 
Book 2: Chapter 7 
J. Batson, D. A. Spielman, N. Srivastava, and S.H. Teng. Spectral sparsification of graphs: Theory and algorithms. Communications of the ACM, 56(8):8794, Aug. 2013.
Ioannis Koutis, Gary L. Miller, Richard Peng, A fast solver for a class of linear systems, Communications of the ACM CACM, Volume 55 Issue 10, October 2012 Pages 99107 N. K. Vishnoi. Lx = b. Foundations and TrendsbR in Theoretical Com puter Science, 8(12):1141, 2013. 
23

11/11

Quiz 2  
24

11/13

General Topics:
Advanced Sampling Specific Subjects: graph and metric embedding spectral sparsification Algorithmic Techniques: sampling and projection Mathematical Concepts: JohnsonLindenstrauss lowdistortion embeddings  W. B. Johnson and J. Lindenstrauss. Extensions of Lipschitz mappings into a Hilbert space. Contemporary Mathematics, 26, 189206, 1984  
25

11/18

General Topics:
Advanced Sampling Specific Subjects: spectral sparsification Algorithmic Techniques: effective resistance based sampling Mathematical Concepts: spectral similarity effective resistances 
Book 2: Chapter 6 
D. A. Spielman and N. Srivastava. Graph sparsification by effective resistances. In Proceedings of the 40th ACM Symposium on the Theory of Computing, pages 563568, 2008. 
26

11/20

General Topics:
Optimization and Approximation Specific Subjects: mathematical programming Algorithmic Techniques: linear programming Mathematical Concepts: convex optimization linear programming basics 
Book 1: Chapter 11.6 Michel Goemans's note on Linear Programming and Polyhedral combinatorics 
Raghavan and Thompson, "Randomized rounding: A technique for provably good algorithms and algorithmic proofs", Combinatorica 7 (4): 365374
Goemans and Williamson, "Improved approximation algorithms for maximum cut and satisfiability problems using semidefinite programming", Journal of the ACM (JACM), 11151145, 1995. 
27

11/25

General Topics:
Optimization and Approximation Specific Subjects: mathematical programming Algorithmic Techniques: multiplicative weight updates Mathematical Concepts: convex optimization linear programming basics 
Book 1: Chapter 11.6 The Multiplicative Weights Update Method: a Meta Algorithm and Applications Sanjeev Arora, Elad Hazan, and Satyen Kale 

28

11/27

Thanksgiving (No Class)  
29

12/02

2:003:00pm: Quiz 3
3:003:50pm: Discussion

Book 2: Chapter 5  
30

12/04

General Topics:
algorithm analysis Specific Subjects: beyond worst case analysis Algorithmic Techniques: input and solution characterizations Mathematical Concepts: instancebased complexity outputsensitive algorithm smoothed analysis algorithmic condition numbers 
Book 2: Chapter 8 
Daniel A. Spielman, ShangHua Teng, Smoothed Analysis: An Attempt to Explain the Behavior of Algorithms in Practice Communications of the ACM, Vol. 52 No. 10, Pages 7684 
31

12/13

Final, Friday, December 13, 2019 24 p.m.  Good Luck 