Class Venue and Time: CSI 3118, 9:30-10:45AM Tue, Thu

The following is an outline of the main topics discussed in each class of CMSC858E, Spring 2011. This is an approximate summary, but gives an idea of the primary issues covered. Thanks to student Karla Saur for her help with this! Please let Aravind know if there are any major omissions or errors.

- Administrative details, how the fact that we live in a networked world leads to fundamentally new problems and to unexpected variants of classical problems.
- Key methodological ingredients: graph theory, probability & statistics, (distributed) algorithms for now (game theory to come later).
- The expectation: definition, interpretations (laws of large numbers
and the
*probabilistic method*viewpoint of "weighted average"), linearity of expectation, comparison to the median, alternative formula, examples. - Random walks on graphs, coupon collector, Markov's inequality.
- The Second Moment Method and Chebyshev's inequality.

- MAX CUT and large cuts (to be seen again later in pricing problems).
- The union bound.
- Contention resolution and distributed algorithms.
- Distributed scheduling, graph coloring, probabilistic recurrence relations, and a full analysis of Luby's coloring algorithm (along with discussions of symmetry-breaking via distributed random permutations).

- The
*k*th moment inequality. - The variance-covariance formula, negative correlation, and sampling with/without replacement.
- Sampling using
*k*-wise independence; brief discussion of data-streams and Alon-Matias-Szegedy. - Start discussion of sparse cuts; separator theorems for planar and fixed-minor-free graphs.

- (The first few among Luca Trevisan's lectures provide excellent background for the lectures of Feb 8 and Feb 15.)
- Vertex- and edge-expansion, sparsest cut, Ramanujan graphs, and the resilience of expanders.
- Basic properties of eigenvalues and eigenvectors.
- A sneak peek at homophily and the strength of weak ties.

- Graph density and its applications to networks.
- Max-flow-based exact algorithm for computing maximum-density subgraph and a linear-time greedy approximation algorithm.
- The densest
*k*-subgraph problem: algorithms and hardness.

- Eigenvalues and expansion for regular graphs: Trevisan's notes on Linear Algebra review and Cheeger's inequality.

- Bounds on binomial coefficients and binomial sums.
- Random graphs
*G(n,p)*: regions with the double jump, connectivity, and expansion: heuristic proofs. - Poisson and Normal approximations, power-law degree distributions, and "long tails".
- (See this Wikipedia article for the positive, perhaps less-known, role played by Edgar Gilbert in developing random graphs.)

- Random graphs
*G(n,p)*: examining their expansion. - Tail bounds under negative correlation; positive correlation and cascades.
- Long-range links in social and peer-to-peer networks.
- Long-range links yield expansion: Theorem 1 in Abie Flaxman's paper; discussion of why a direct plugging-in of the Chernoff lower-tail bounds will not work for small-set expansion.

- Very large deviations above the mean; finish discussion of Flaxman's work.
- Milgram's experiments,
*small-world*phenomena, and Kleinberg's work on*distributed*navigability in small-world networks. - Rank-based friendship and some of the findings of Liben-Nowell, Novak, Kumar, Raghavan & Tomkins and Backstrom, Sun & Marlow; the work of Sandberg in brief.

- Discussion of mid-term class evaluation.
- Complete the discussion of small-world routing.

- Link-based search: Kleinberg's work on hubs and authorities.
- A brief introduction to PageRank.

- Finish hubs-and-authorities and PageRank.
- General discussion of the role of bootstrapping & modeling, and examination of three examples of bootstrapping in Web search: starting with an approximately-good ranking, repeated improvement in hubs-and-authorities, and search engines/machine learning improving from user-clicks.
- Recap of basic probabilistic tools.
- Introduction to basic game theory, mostly from Chapter 6 of Easley-Kleinberg: motivation, games in normal form, examination and critique of modeling strategic interaction/games in this manner, best responses, dominant strategies, and strategy elimination.
- (This video of Dan Ariely is worth watching.)

- Continuation of game theory from Chapter 6 of Easley-Kleinberg: Nash equilibria, multiple equilibria, zero-sum games, mixed strategies, Pareto- and social- optimality, dynamic- and multi-player- games.
- Zero-sum games and linear programming.

- Exact and approximate computation of Nash equlilibria.
- Aumann's correlated equilibria and linear programming.

- Network Traffic and Game Theory (largely following Chapter 8 of Easley-Kleinberg).
- Pricing problems: the Balcan-Blum model.
- (Check out this video and a similar one that give physical demonstrations of Braess' paradox.)

- Pricing when the market is known: the approximation algorithms of Balcan-Blum for graphs and hypergraphs; see also Avrim Blum's talk slides.
- Pricing digital goods when the market is not known: the RSOP auction.
- A brief classification of single-item auctions.

- Incentive-compatibility of the second-price auction; optimal bidding strategies under randomly-chosen valuations (largely from Chapter 9 of Easley-Kleinberg).
- Start matching-markets.

- Matching markets (largely following Chapter 10 of Easley-Kleinberg): bipartite graphs, perfect matchings and Hall's Theorem, valuations and weighted matchings, market-clearing using prices (social-optimality and construction using Egervary's approach), and relation to single-item auctions.

- Algorithmic proof of Hall's Theorem.
- Algebraic approaches to matching: the Isolating Lemma and the Mulmuley-Vazirani-Vazirani algorithm.
- Whirlwind coverage of Chapter 11 of Easley-Kleinberg.
- (See these CMU lecture notes for more on probabilistic approaches to basic algebraic problems.)

- Stable marriages and stable rommmates/matchings: algorithm and proof of correctness for stable marriage, quick coverage of stable roommates, NP-hard variants, and college admissions (hospital/resident allocation).
- Bargaining and power in networks, largely from Chapter 12 of Easley-Kleinberg: basic models for power and social exchange, network-exchange experiments, interpretation of the Ultimatum Game, Nash Bargaining for two players, and stable outcomes.

- Balanced outcomes in bargaining.
- Game-theoretic reasoning in bargaining.
- (Watch this video and related ones on bargaining by William Spaniel.)

- Network dynamics: information cascades and very brief coverage of direct-benefit effects.
- A quick introduction to submodular functions, the properties they share with concave and convex functions, and the performance of the associated greedy algorithm.
- (See Jan Vondrak's Charles University thesis for an excellent modern study of submodularity.)

- Network effects on dynamics: examples from medicine & agricultural practices, and lessons learned.
- Networked coordination game with binary options: cascades, clustering & weak ties, and the cascade capacity.
- Epidemics: contact networks and branching processes, the basic reproductive number, SIR and SIS models, wireless worms.
- A basic "bipartite influence-maximization" problem (motivated, e.g.,
by banner advertising): two
*(1 - 1/e)*-approximation algorithms based on submodularity and rounding an LP relaxation.