YPNG seminars

Fall 2018: Fridays from 11-1 in the main classroom of 24 Hillhouse.

During 2014 we switched to the Yale mailman system for seminar announcements.

September 14, 2018 TBA
September 7, 2018 Chris will continue his presentation from a few weeks ago (see Aug 17.)

END of Summer 2018
August 24, 2018 Derek Feng will talk about "Testing for Balance in Social Networks"
August 17, 2018 Chris Harshaw will talk about "Submodularity Beyond Lattices: Matrices, Polynomials, Arbitrary Real Vector Spaces - Oh My!"
July 27, 2018 Mingrui Zhang will talk about: Online optimization for non-convex functions has been receiving increasing attention in the research field of machine learning. One important class of these non-convex functions is the submodular function, which has both interesting theoretical properties and wide practical applications. In this talk, we will briefly review the basic properties of submodular function and the classic optimization algorithm in the offline case. Then our new online algorithms for continuous submodular maximization will be presented with detailed analysis.

END of Spring 2018
April 20, 2018 Yihong will continue his talk about recovering a hidden Hamiltonian cycle via linear programming.
April 6, 2018 Yihong will talk about recovering a hidden Hamiltonian cycle via linear programming.
March 2, 2018 This week David is hoping to discuss some of the ideas left unexplained in the seminar on Monday 26 Feb by Ramdas.
February 16, 2018 Sekhar will talk about how to avoid saddlepoints when optimizing nonconvex functions.
February 09, 2018 Elena and David will continue the talk begun on 26 Jan, regarding a concentration inequality for time reversible Markov chains. This week they will get into some of the details of the method for bounding the operator norm of the perturbed transition matrix.
January 26, 2018 Elena and David have been trying to understand some papers of Lezaud (1998 Ann. Appl. Prob) and Paulin (2015 Elect. J Prob) on concentration for sums f(X_1)+ \dots + f(X_n), where X_0,X_1,\dots is a time-reversible Markov chain with a finite state space. Their method involves a lot of fancy perturbation theory, a la Kato. On the assumption that many in the audience will have forgotten any complex analysis that they might have known, David will try to explain everything, including the basics of spectral theory for Markov chains. The talk will be very boring for anyone who already knows a lot about spectral theory and eigengaps. It is intended to provide a gentle introduction for those who have never experienced a YPNG talk.

END of Fall 2017
November 10, 2017 Cheng Mao (MIT) will talk about permutation-based models for ranking from pairwise comparisons.
October 27, 2017 Anderson will give the second part of his talk the convergence of the iterative algorithm of mean field variational inference method. He will explain why the iterative algorithm (Batch Coordinate Ascent Variational Inference) has linear convergence and reaches the minimax optimal rate within log n iterations.
October 6, 2017 Anderson will talk about theoretical and computational gaurentees on mean-field variational Bayes method for community detection.
September 29, 2017 David will continue with some more path arguments for gaussian processes. John will get his wish for a coupling. David will wonder what makes a path smart.
September 22, 2017 David will will describe a beautiful argument of Chatterjee to prove the Fernique inequality: if $(X_1,\dots, X_n)$ and $(Y_1,\dots, Y_n)$ are both distributed multivariate normal with $\PP X_i = \PP Y_i$ for each $i$ and $ \var (X_I-X_j) \le \var(Y_i-Y_j) $ for all $i$ and $j$ then $\mathbb P \max_i X_i \le \mathbb P \max_i Y_i $. Motivation, background, and intuition included. All you need to know is some elementary facts about the multivariate normal

END of Summer 2017
August 11, 2017 Sekhar will talk about sparse regression codes.
July 28, 2017 Jiantao Jiao (Stanford) will talk about minimax estimation of the total variance distance.
July 21, 2017 Rasmus will talk about "Approximate Gaussian Elimination for Laplacians."
June 16, 2017 Yihong will talk about "Gaussian mixtures and denoised method of moments." He will describe some recent results on the optimal parameter estimation for mixtures of k-Gaussians. The algorithm (and lower bound) relies the theory of moments, polynomial interpolation and majorization.

END of Spring 2017
April 21, 2017 John Hartigan will discuss some of his recent work on k-means clustering -- namely when is there a mode in each of the k-means clusters?
February 10, 2017 Winston Lin will talk about: Agnostic Notes on Regression Adjustments to Experimental Data: Reexamining Freedman's Critique.

END of Fall 2016
December 9, 2016 Roman Vershynin, from Michigan, will talk about: Title: How to discover a hidden structure of a complex network.
November 11, 2016 Yu Lu will continue his talk from a few weeks ago.
November 4, 2016 Donald Lee will talk on: Sparse interpretable estimators for cyclic arrival rates
October 14, 2016 Tengyu Ma (Princeton) will talk on: Matrix Completion has No Spurious Local Minimum
October 7, 2016 Yu Lu will talk on: Statistical and Computational Guarantees of Lloyd's Algorithm and its variants.
September 30, 2016 Yining Wang (CMU) will talk on: Computational aspects of subset selection in regression models.

END of Summer 2016
July 22, 2016 Sabyasachi will talk on: On Estimation in Tournaments and Graphs under monotonicity constraints.
July 1, 2016 David is seizing the YPNG time slot for an informal discussion of the techniques used in a paper of Latala: Some estimates of norms of random matrices.
June 10, 2016 David will kickoff the first YPNG of the summer this Friday. He will discuss his interpretation of the main result by Van Vu in (2007 Combinatorica) his paper "Spectral norm of random matrices." The paper gives a probabilistic upper bound for for the spectral norm of a random symmetric matrix.

END of Spring 2016
May 6, 2016 Yuchen Zhang from Berkeley will talk about: Communication complexity of statistical estimation and linear algebraic computation
April 15, 2016 Yu Lu will talk about: Exact Exponent in Optimal Rates for Crowdsourcing
April 8, 2016 Ani Adhikari from Berkeley will be discussing the new data science course at Berkeley: STAT 94 / CS 94 "Foundations of Data Science".
April 1, 2016 Randolf Altmeyer will talk about: Estimating the spectrum of a covariance matrix using random matrix theory
February 26, 2016 Anderson will continue from last week.
February 19, 2016 Anderson will speak on: Polynomial-time and Rate-optimal Algorithm for Community Detection in Stochastic Block Model
February 12, 2016 John will speak on the likelihood ratio test for k-means. He promises there will be some good asymptotics and the tracy widom distribution.
January 29, 2016 Pierre Bellec will talk about: Title: Almost parametric rates and adaptive confidence sets in shape constrained problems

END of Fall 2015
November 13, 2015 Ahmad Beirami (Duke and MIT) will talk about: Guesswork, computational security, and information theory
November 6, 2015 Open discussion of "data science."
October 30, 2015 David will talk about the growth of the giant component in the Erdos-Renyi graph.
October 16, 2015 Chao Gao will present: Network analysis: Community Detection and Graphon Estimation
October 9, 2015 Chao Gao will present: Robust covariance matrix estimation
September 25, 2015 Zhimei Ren will talk about: Spectral Clustering Using Graph Distance.
September 18, 2015 Patrick will talk about: Killed random walks and graph Laplacians: local sensitivity in network flow problems.

END of Summer 2015
August 28, 2015 John has some incomplete thoughts about the number of k-means clusters that are justified. Come along tomorrow at 11:00 to attack him viciously for his lack of completeness.
August 21, 2015 Lizhong Peng, from Peking University, will talk about: Tensor Eigenvalue and Its Applications.
August 7, 2015 David will talk about Zorn's lemma, ultrafilters, and compactness.
July 10, 2015 Sekhar will discuss the Marcenko-Pastur distribution for random sample covariance matrices. And depending on time I will show how this can be used to analyze the loss of identifiability in high dimensional spiked covariance models.
July 3, 2015 David will continue from last time.
June 26, 2015 David will talk about the Hoover-Aldous characterization of doubly exchangeable infinite arrays.
June 19, 2015 David will attempt to explain some ideas on minimaxity contained in a paper by Tsybakov and others.
June 5, 2015 Sekhar will continue from last time.
May 29, 2015 Sekhar will go over some basic random matrix theory relevant for high dimensional statistics.
May 22, 2015 Summer 2015 organizational meeting

END of Spring 2015
April 17, 2015 Patrick Rebeschini will give a talk titled: On the role of the Hessian of submodular functions.
April 3, 2015 This week we will learn about the mysteries of the Bernstein-von Mises theorem for normal approximation of posterior distributions. Dana and Natalie will explain the key ideas. Along the way we will learn about LAN, contiguity, and some interesting facts about the effect on posteriors of changes in the prior.
March 27, 2015 Jae Oh Woo will talk about Rearrangements, Majorization and Their applications
March 6, 2015 Alp Kucukelbir will talk about Population Empirical Bayes.
February 6, 2015 Derek Feng will talk about something involving real networks.
January 23, 2015 Thierry Emonet, from MCDB and Physics, who will give us an informal introduction to what his lab works on. From the website: "We study how live cells and animals process information, interact, and make decisions using wet lab experiments and computational modeling."

END of Fall 2014
December 12, 2014 John Hartigan will present: "Bad maximum likelihood ratio tests in change point problems."
December 5, 2014 Cindy Rush will present: In this talk, I'll propose an approximate message passing (AMP) decoder for sparse superposition codes which are low-complexity, capacity-achieving codes for the memoryless additive white Gaussian noise channel. I'll analyze its performance and give a proof that the probability of decoding error goes to zero as the number of channel uses tends to infinity for all fixed rates R < C.
November 21, 2014 Sushant will present: Chebyshev approximations and the Conjugate Gradient method
November 14, 2014 Sahand will discuss: We analyze an upper-bound for the expected value of an empirical process that arises from a ranking problem. We will go through the steps that lead us to that process and discuss steps to bound it. We will then discuss.
November 7, 2014 Too many people away at conferences.
October 31, 2014 DeWen will finish up his discussion of faithfulness in Gaussian graphical models.
October 24, 2014 Yale holiday.
October 17, 2014 Chao Gao will talk about his recent work on minimax rates for network analysis.
October 10, 2014 Patrick will continue his presentation on high dimensional particle filtering.
October 3, 2014 DeWen will continue his discussion of faithful relation in Gaussian graphical models.
September 26, 2014 DeWen will discuss the notion of faithful relation for Gaussian graphical models.
September 19, 2014 Patrick will continue his presentation from last week.
September 12, 2014 Patrick Rebeschini will talk about how to tweak classical sequential Monte Carlo algorithms (particle filters) to overcome the curse of dimensionality in high dimensional problems. He will review the classical theory (bootstrap particle filter), analyze the curse of dimensionality, and discuss what ideas are needed to address the core of the problem and to make tangible progress in applications.
September 5, 2014 David P will try to defend his assertion that Chen-Stein works for any log-concave distribution on the nonnegative integers.

END of Summer 2014
August 15, 2014 David will discuss an interesting example of a Gaussian process that illustrates nicely the difference between two techniques for controlling the expected supremum of a Gaussian process. The example is an improved version of an classical example that took over a YPNG seminar in January 2013. The audience suggestions have subsequently proved most helpful.
August 1, 2014 This week our special guest, Guanyang from USTC, will tell us about the use of Chen-Stein in proving the Erdos-Kac theorem, a CLT for something to do with prime numbers.
July 25, 2014 Sekhar will continue the discussion of Stein methods.
July 18, 2014 David Brinda will continue his discussion of the Chen-Stein method.
July 11, 2014 This week David Brinda will talk about the Chen-Stein method.
June 20, 2014 David will talk about the exchangeable pairs approach to Stein's method for normal approximation.
June 13, 2014 Sekhar will continue the discussion from last week on the Onsager correction term.
June 6, 2014 An important step in the analysis of Montanari's AMP algorithm is the use of the so-called Onsager (reaction or correction) term. The Onsager term was first developed by physicists to understand mean-field behavior in spin glasses. Sekhar will give a gentle introduction to the Onsager term.
May 23, 2014 Sabyasachi will tell us something about "Information Theory of Penalized Likelihoods and its Statistical Implications", based on work for his dissertation.

END of Spring 2014
May 16, 2014 The SDD* coalition will be holding an informal discussion about fat shattering.
April 25, 2014 Sahand will talk about fast rates of convergence for stochastic optimization.
April 18, 2014 Dana and Soeren will describe a simplified argument for obtaining an oracle inequality from the paper by Kneip "Ordered linear smoothers" (AnnStat 1994). Obstreperous audience members should note that the speakers might have hired thugs in attendance.
April 11, 2014 Pierre Bellec will talk about the aggregation of density estimators and sharp oracle inequality in deviations.
March 28, 2014 Sasha Tsybakov will talk about: "Adaptive estimation by Goldenshluger-Lepski method". He will give a simple proof of their main oracle inequality and discuss some examples.
February 28, 2014 Patrick Rebeschini, from Princeton, will talk about: New phenomena in nonlinear filtering.
February 21, 2014 Gilles Stoltz, from CNRS and HEC Paris, will discuss a Bayesian version of the Cramér-Rao bound known as the van Trees inequality. The latter will be revisited it in the spirit of Hajék and Le Cam.
February 7, 2014 David will give an overview of some of the ideas behind Talagrand's inductive method for concentration.
January 24, 2014 David will describe Bobkov's (Ann. Probab. 1997; J. Funct. An. 1996) functional approach to the Gaussian Isoperimetric inequality, with simplifications due to Ledoux (Progress in Prob. 1998) and Barthe and Maurey (Ann. Inst. H. Poincare, 2000). No previous acquaintance with isoperimetric bounds assumed.

END of Fall 2013
December 6, 2013 Daniel Fresen will conclude his heroic discussion of convex bodies. Audience excited that his new results might be related to the lasso. [Editorial comment: There is a lot of fancy mathematical theory out there that high-dimensional statisticians need to be aware of. Much applause for Daniel.]
November 22, 2013 DeWen Soh will talk about "Learning Latent Graphical Models": We consider the problem of graphical model reconstruction in the partially observed regime. Some nodes are observable while the rest are hidden, and we want to recover the hidden nodes and their structure based on the observable nodes. We will look at some recovery results for latent tree graphs and locally-tree like graphs. While there are algorithms to reconstruct the model in these kinds of graphs, these algorithms fail in the presence of small cycles, especially triangles. However, many real world networks have triangles in them. Thus, more general latent graphical models are a challenge to reconstruct. We will discuss some of the difficulties in dealing with small cycles and research directions to overcome these difficulties.
November 15, 2013 Daniel Fresen will continue his discussion of convex bodies. [Editorial comment: So far he has persuaded us that a high dimensional cube is like a ball with a few little mountains on its surface.]
November 8, 2013 Zhao Ren will talk about "Asymptotic Normality in Estimation of High-Dimensional Ising Models"
November 1, 2013 Daniel Fresen will talk about Euclidean structures in high dimensional normed spaces: We discuss the general theory surrounding Dvoretzky's theorem on ellipsoidal cross-sections of convex bodies (equivalently, Hilbertian subspaces of normed spaces). Particular topics include the volume ratio theorem, Kashin splitting, type/cotype (growth rate of random walks in normed spaces), and the Maurey-Pisier-Krivine theorem. Most of the material is classical and well known, but we present a few new results too, including connections with the restricted isometry property for random matrices and the Johnson-Lindenstrauss lemma for sparse vectors in general normed spaces.
October 18, 2013 [OCTOBER RECESS]
October 11, 2013 Uri will discuss some characteristics and challenges of machine learning work at PayPal, as he was facing during his years there.
September 27, 2013 John will discuss some new results on the maximum of dependent normal random variables.
September 20, 2013 David will discuss some applications of convexity in statistics. The ideas come mostly from unpublished joint work with Nils Hjort and joint work with Wei Dou and Harry Zhou
September 13, 2013 Sabyasachi will talk about his work on "Improved Risk Bounds in Isotonic Regression": We consider the problem of estimating an unknown non decreasing function in 1 dimension from finitely many noisy samples. We give an improved global risk bound for the isotonic least squares estimator in this problem. The obtained risk bound behaves differently depending on the true function f0, one gets a whole range of rates from logn/n when f0 is constant to n^-(2/3) when the function is strictly increasing in some sense. In particular, when f0 has k constant pieces the risk bound becomes (k/n) log(en/k). As a consequence, we illustrate the automatic adaptation properties of the LSE. We also prove analogous results for model misspecification. We also derive local minimax lower bounds for this problem which show that our risk bounds are optimal upto log factors. All our results are non asymptotic.
September 6, 2013 Organizational meeting for Fall semester.

END of Summer 2013
August 16 2013 Harry will discuss an ongoing research project of Mengjie Chen (from Computatnl Bio & Bioinformatcs), Chao Gao and Zhao Ren on Canonical Correlation Analysis.
August 9 2013 Zhao Ren will continue his discussion from the last two weeks.
August 2 2013 Zhao Ren will continue his discussion from last week.
July 26 2013 Zhao Ren will discuss the paper "Reconstruction From Anisotropic Random Measurements" by Rudelson and Zhou (IEEE TRANSACTIONS ON INFORMATION THEORY, VOL. 59, NO. 6, JUNE 2013).
July 19 2013 David will talk about the humble Poisson-Binomial distribution (sums of independent {0,1}-valued random variables) and some interesting calculations by Daskalakis & Papadimitriou ("Sparse Covers for Sums of Indicators", arXiv:1306.1265 [stat.CO]).
July 12 2013 Sekhar will discuss some problems in spin glasses.
June 28 2013 Sekhar will continue discussing the problem of local search on graphs.
June 21 2013 Sekhar will discuss the problem of local search on graphs primarily focusing on Kleinberg's paper: "The small-world phenomenon: An algorithmic perspective" in Proc. 32nd ACM Symposium on Theory of Computing, 2000.
June 14 2013 David will continnue his discussion of the entropy method for proving concentration inequalities.
June 7 2013 David will give a self-contained introduction to the entropy method for proving concentration inequalities.
May 31 2013 Harry will attempt to give a statistical story for the results Van presented last week on a random extension of the Davis-Kahan theorem.
May 24 2013 Van Vu will present the Davis-Kahan theorem for random perturbation and matrix recovery
May 17 2013 Daniel Fresen will continue his discussion of a multivariate Gnedenko Law of Large Numbers
May 10 2013 Daniel Fresen will discuss a multivariate Gnedenko Law of Large Numbers

END of Spring 2013
April 19 2013 Yuan Yao (from PKU) will be telling us about "The Landscape of Complex Networks".
April 12 2013 Chao will discuss: I will motivate the sparse PCA in high-dimensional setting. With the single/multi-spike model, infer the principal components with a sparse prior is natural. I will propose two priors for sparse signals. The first prior leads to optimal posterior convergence rate, but leaves computational challenges. The second prior leads to efficient Gibbs sampling, but its theoretical property is still in the progress of my work.
March 29 2013 Chao continues from last time.
March 8 2013 Chao Gao will talk about: I will show intuition why the choice of prior is important in nonparametric, semiparametric and high dimensional setting, in contrast to the phenomenon that the prior influence will be washed away by data in the classical parametric setting. Then I will give introduction to the results in Ghosal, Ghosh and van der Vaart (2000) and van der Vaart and van Zanten (2008) for posterior convergence rate and Gaussian process.
February 22 2013 Zhao Ren will discuss his research.
February 1 2013 David continues from last week.
January 25 2013 David will try to explain some of the clever ideas in Talagrand's majorizing measure result for Gaussian processes.

END of Fall 2012
November 30 2012 Xiaosheng Mu will discuss some results related to the following problem: Suppose n players compete in a round robin tournament. The outcome of each match is determined by the toss of a fair coin. Each player can choose to be one of two types throughout the tournament, type A (aggressive) or type N (not aggressive). In a match between two A's, the winner scores +2, the loser -2. In a match between an A and an N, the winner scores +1, the loser -1. For N versus N both players score 0. The problem: For a tournament with both A and N players, show that the probability that a particular type A person has the highest score is strictly greater than the probability that a particular type N person has the highest score.
November 9 2012 Peter Orbanz (Columbia) will be speaking about nonparametric priors for exchangeable graphs and arrays.
October 19 2012 Le-Minh will be telling us why he and Harry are interested in the paper "Exact Recovery of Sparsely-Used Dictionaries" by Spielman, Wang, and Wright.
October 12 2012 David will talk about ``fat shattering."
October 5 2012 Partha Dey, from the Courant Institute, will talk about Stein's method and its applications to concentration.
September 28 2012 Nick Ruozzi is back in town and will talk about: "Log-supermodular Functions and Counting Problems"
21 September 2012 David will talk about the concentration of chromatic numbers for sparse Erdos-Renyi graphs.
14 September 2012 Taylor will discuss the ADMM (Alternating Direction Method of Multipliers) technique that has found use in many statistical optimization problems such as LASSO.

END of Summer 2012
24 August 2012 Aryeh Kontorovich will talk about: "Convergence of the empirical distribution -- an old story with new twists."
17 August 2012 Mike Kane will tell us about the use of libraries in R: what, why, and how.
3 August 2012 David will continue his discussion of Van Vu's concentration inequality.
27 July 2012 David will discuss Van Vu's concentration inequality.
20 July 2012 John Hartigan will discuss his approach to understanding critical behavior in random graphs.
6 July 2012 Sabyasachi will continue his discussion of a recent result of Krivelevich and Sudakov.
29 June 2012 Sabyasachi will discuss a recent result of Krivelevich and Sudakov.
22 June 2012 Sekhar will give a gentle introduction to random graphs.
15 June 2012 David Pollard will talk about: "How I learned some neat things about Hermitian matrices"
8 June 2012 Ramji will discuss a greedy technique for solving a sparse linear regression problem with applications to data compression.

END of Spring 2012
20 April 2012 Ankur Sharma will discuss the identification of pedigrees (family trees) from genetic data, essentially an identifiability question on a certain complex probability model on specific kinds of graphs.
13 April 2012 Roy Lederman will talk about a nearest neighbors algorithm for strings. See you at 11 in the Stat's classroom.
23 March 2012 Arlene will discuss some results in her thesis on minimax lower bounds.
17 February 2012 Mike will continue his discussion of epidemic models based on random graphs.
10 February 2012 Mike Kane will talk about epidemic models based on random graphs.
3 February 2012 Arlene will talk about minimax bounds for estimation of normal location mixtures.
27 January 2012 Roy Lederman will give an overview of multi-scale analysis, parameterization and visualization using diffusion embedding.

END of Fall 2011
2 December 2011 Sabyasachi will discuss some papers he has been reading on the topic of sampling, denoising and compression of matrices by coherent matrix organization.
18 November 2011 Ramji continues his discussion Suen's correlation inequality.
11 November 2011 Ramji Venkataramanan will discuss Suen's correlation inequality.
28 October 2011 Harry Zhou will discuss the following paper: "Dimension-free tail inequalities for sums of random matrices" by Daniel Hsu, Sham M. Kakade, Tong Zhang which can be found at: http://arxiv.org/abs/1104.1672
21 October 2011 Zhao Ren will talk about dictionary learning.
14 October 2011 Mokhsay will continue his presentation from last week.
7 October 2011 Mokhsay Madiman will talk about "random polytopes and floating bodies."
30 September 2011 Lie Wang, from MIT, will present his square-root lasso method.
23 September 2011 Antony Joseph will discuss some of theory behind lasso.
16 September 2011 Taylor will continue his presentation from last week.
9 September 2011 Taylor Arnold will discuss some issues in sparse regression.
2 September 2011 DP will talk about an elegant little lemma (due to Fremlin, and much admired by Talagrand) that proves the existence of evil sets under suitably evil circumstances. The talk will be self-contained as long as you have heard of the Holder inequality and Fubini.

END of Summer 2011
16 June 2011 Behrouz Touri, from UIUC, will be talking about: "On the product of random stochastic matrices".
9 June 2011 Sekhar will describe Blackwell's unique ergodicity problem for hidden Markov chains. The problem was recently resolved by Chigansky and van Handel.
2 June 2011 David Pollard will talk about a simple problem involving a statistic which is not sufficient but for which there is no loss of Fisher information if only that statistic is observed. (The problem is a simplified version of a counterexample due to Kagan and Shepp 2005.)
26 May 2011 John Hartigan will discuss: "Admissible normal location estimators are Bayes"
19 May 2011 This week Harry Zhou will present the paper "User-friendly tail bounds for sums of random matrices" by Tropp, http://arxiv.org/abs/1004.4389

END of Spring 2011
11 May 2011 Lav Varshney from the IBM Watson Research Center will talk about decision making with quantized priors.
4 May 2011 Laurent Cavalier from the Centre de Mathimatiques et Informatique at the Universiti Aix-Marseille will talk on "Risk hull method for inverse problems."
27 April 2011 Martin Wainwright from UC Berkeley will be talking on "Statistical inference in high-dimensions: A unified framework for decomposable regularizers."
20 April 2011 Harry Zhou will discuss some open problems that have him stumped.
13 April 2011 David will speak about chaining and bracketing arguments.
6 April 2011 Sanghee Cho will discuss a paper by Leeb: "Evaluation and selection of models for out-of-sample prediction when the sample size is small relative to the complexity of the data-generating process." Bernoulli, 14(3):661-690, 2008.
30 March 2011 Seminar cancelled
23 March 2011 Taylor will talk about "Applied Theory of Learning Graphical Models", including some of the ideas in his prospectus.
16 March 2011 Spring break
9 March 2011 Spring break
2 March 2011 No seminar this week.
23 February 2011 David Pollard will discuss the concept of fat shattering. This is either a combinatorial technique for bounding the covering number of a class of functions or a revolutionary new diet and exercise program. Come this week to find out which one it is!
16 February 2011 Sekhar will discuss a general method called the multiplicative weights update method that is useful in many contexts including approximating solutions to zero-sum games, fractional packing and covering, approximating multicommodity flows, and others.
9 February 2011 John Hartigan will discuss admissible estimators and a normal location problem.
2 February 2011 Second snow day! Seminar rescheduled
26 January 2011 Yihong Wu from Princeton will be discussing his work on: "Finite-constellation capacity and approximation by Gaussian location mixtures".
19 January 2011 Aditya Guntuboyina will talk about convex body reconstruction from support plane measurements.
12 January 2011 Snow day -- seminar rescheduled

END of Fall 2010
30 November 2010 David will talk about the LARS paper of Efron et al (Ann. Stat. 2004). He will present a small modification developed for his Linear Models course. [handout]
23 November 2010 Turkey break
16 November 2010 cancelled
9 November 2010 Ramji Venkataramanan will making his YPNG debut tomorrow. He will discuss the problem of communicating over a deletion channel. What is a deletion channel you ask? Come tomorrow and find out.
2 November 2010 Emmanuel Abbe will be talking about polar codes. He will go into more detail than was possible at the Departmental seminar yesterday.
26 October 2010 Nick will discuss his latest research on the max-product algorithm.
19 October 2010 Antony will present Wainwright's paper: "Sharp thresholds for high-dimensional and noisy sparsity recovery using 1-constrained quadratic programming (Lasso)"
12 October 2010 Harry will discuss his lower bounds for inverse covariance estimation.
5 October 2010 Taylor will discuss Lasso regression and connections to graph learning.
28 September 2010 Taylor will discuss some issues with learning graphs from data.
23 September 2010 Aditya G. will continue his discussion from last week.
16 September 2010 Aditya G. will talk about the problem of reconstructing convex bodies from finitely many noisy support function measurements. He'll present at least one reconstruction technique and an estimation lower bound.
9 September 2010 Organizational meeting

END of summer 2010
29 June 2010 Aditya M will discuss Witsenhausen's counter-example. This is a classic hard problem in decision/control theory.
22 June 2010 Antony will discussion connections between coding and regression.
15 June 2010 David will try out more Le Cam theory: square roots of Poissons.
8 June 2010 Sekhar will talk about Szemeredi's regularity lemma, drawing on the following sources:
  1. http://en.wikipedia.org/wiki/Szemerédi_regularity_lemma
  2. Komlós, János; Shokoufandeh, Ali; Simonovits, Miklós; Szemerédi, Endre (2002), "The regularity lemma and its applications in graph theory", Theoretical aspects of computer science (Tehran, 2000), Lecture Notes in Comput. Sci., 2292, Berlin, New York: Springer-Verlag, pp. 84–112,
  3. Tao, Terence (2006), "A variant of the hypergraph removal lemma", Journal of Combinatorial Theory. Series A 113 (7): 1257–1280,
  4. Section 7.4 of the 2005 edition of Diestel's "Graph Theory."
1 June 2010 Aditya G. will discuss Choquet theory and some applications.
25 May 2010 David will try out a few bits and pieces about Le Cam theory, in preparation for some lectures in Beijing.
18 May 2010 Cancelled. Baby imminent.

END of spring 2010
7 May 2010 Mark Low, from UPenn, will talk about "Optimal estimation of a Nonsmooth Functional."
30 April 2010 Reading week. Go read!
23 April 2010 Anima Anandkumar, from MIT, will discuss her new work on learning tree structures from partial observations.
16 April 2010 Nikhil Srivastava will discuss the results in his PhD thesis titled: "Spectral Sparsification and Restricted Invertibility."
9 April 2010 Mokshay will discuss his new extension of the Shannon-McMillan-Breiman theorem.
2 April 2010 Teemu Roos, from University of Helsinki, will talk about learning tree structures from data.
26 March 2010 Antony will discuss the use of Fano's inequality to find limits on recovery in the regression setting.
19 March 2010 Spring break
12 March 2010 Spring break
5 March 2010 David will continue his discussion of minimax lower bounds.
26 February 2010 Cancelled due to speaker illness.
19 February 2010 David will discuss minimax lower bounds.
12 February 2010 Taylor and Sekhar will discuss how to learn graphical models from data. In particular they will be discussing lower bounds on sample complexity to ensure learning.
5 February 2010 Theo Weber, from MIT, will talk about correlation decay and average-case optimization for graphical models and combinatorial optimization.
29 January 2010 Tony Jebara from Columbia, will talk about MAP Estimation, Message Passing and Perfect Graphs.
22 January 2010 Nick Ruozzi will discuss some of his recent work on distributed optimization via local message passing rules.

END of fall 2009
11 December 2009 Reading week. Go read!
4 December 2009 Cancelled. Everyone busy.
28 November 2009 Thanksgiving break.
21 November 2009 John Hartigan has agreed to talk. I am not sure of the title but almost surely the following phrases will almost surely be heard during the talk: "scaled diagonal dominance," "counting," "graphs," and "this should only take 10 minutes."
14 November 2009 Cancelled because of the ``Simplicity and Likelihood" conference at Cowles.
7 November 2009 Sekhar will talk about some issues in learning graphical models from data.
30 October 2009 Aditya G. will tell us about a clever new way to derive inequalities between f-divergences.
23 October 2009 Mokshay will discuss entropy in convex geometry.
16 October 2009 Sekhar will discuss Bethe states (useful structures that occur in MRFs defined on sparse graphs).
9 October 2009 Mokshay continued.
2 October 2009 Mokshay will speak about large-time behavior (in the sense of forgetting of the initial state) of inhomogeneous Markov chains on finite state spaces.
25 September 2009 Aditya M will continue his discussion of the multi-armed bandit problem.
18 September 2009 Aditya M. will discuss "Multi-armed bandits, Gittins index, and their extensions.
11 September 2009 To kick off the semester, Sekhar will discuss replica symmetry breaking in combinatorial optimization problems. He will present a toy example that illustrates some of the predictions made by physicists.

END of summer 2009
26 August 2009 Harry will end out the summer for us with an explanation of how to get minimax lower bounds for the problem he has been describing during the past month.
26 August 2009 Harry will continue his discussion of minimax rates of convergence for estimation of of really big covariance matrices.
19 August 2009 Aditya M will discuss a training based scheme for universal communication over unknown channels.   This involves what appears to be a new adaptive hypothesis testing problem.
12 August 2009 Harry will discuss some recent problems in minimax estimation of large covariance matrices.
5 August 2009 Sekhar will continue his discussion from last week.
29 July 2009 Sekhar will discuss some connections between statistical physics and signal estimation.
22 July 2009 David will continue the discussion of the assignment problem. He will explain and criticise the arguments in an amazing paper, An easy proof of the ζ(2) limit in the random assignment problem, Elect. Comm. in Probab. 14 (2009), 261–269, by Johan Wästlund.
15 July 2009 David will start the discussion of the constant bound on expected minimum matching in a bipartite graph with exponential weights. He will work from Steele's exposition [Chapter 4 of Probability Theory and Combinatorial Optimization] of the Walkup result [SIAM J. Computing 8 (1979), 440-442; and Discrete Math. 31 (1981), 59-64], with a few modifications.
8 July 2009 Nick Ruozzi will continue with some of the hard details left out last week.
1 July 2009 Nick Ruozzi will discuss some of his recent work on BP and Gauss-Markov measures.
24 June 2009 Sekhar will continue with his review of Gibbs measures: existence, non-uniqueness, clustering, and applications in combinatorial optimization.
17 June 2009 Sekhar will talk about a clustering phenomena that occurs in Gibbs measures defined on large graphs.
10 June 2009 Cancelled. Nearly everyone out of town.
3 June 2009 David: In Sekhar's absence, I thought I would try my hand at at explaining (yet again) some of the ideas behind message passing algorithms.  If things get too confused we can always implore Sekhar to explain again at some future date.
27 May 2009 Aditya G will wrap-up his discussion on Wigner's semicircle law.  
20 May 2009 Aditya G. will talk about Wigner's  semicircle law, which describes the limiting behavior of the set of eigenvalues of random symmetric matrices.
13 May 2009 David will speak about optimal stopping and the Snell envelope.

END of spring 2009
5 May 2009 Sekhar will talk about the cavity method.
28 April 2009 The YPNG seminar will not meet tomorrow so that we can go out and enjoy some sun.
21 April 2009 John Hartigan will tell us about maximum entropy Edgeworth approximation of the "the number of graphs with a given property".
14 April 2009 Aditya G will present some simple convexity arguments that have interesting consequences for minimax estimation problems.  Along the way, inequalities of Fano and Pinsker will fall out.
7 April 2009 Steven will continue his discussion of results in his thesis.
31 March 2009 Adam will continue the presentation on entropy inequalities started by Mokshay before Spring Break.
24 March 2009 Steven Jaslar will discuss some aspects of his PhD thesis.

Spring break
3 March 2009 Mokshay will talk about entropy inequalities.
24 February 2009 This week in the YPNG seminar we have a special speaker: Prof. Charles Johnson from W&M College will speak on matrix completion problems.
17 February 2009 In the YPNG seminar Sekhar will talk about something. He hasn't decided yet.
10 February 2009 Over the last few weeks we have heard a bit about Blackwell's dynamic programming contributions. This week DP will tell us about another Blackwell idea, the canonical measure for an experiment indexed by a finite parameter set. Connections with Le Cam's distance will be explained.  The talk will be accessible to anyone who knows what sufficiency means.
3 February 2009 Aditya will discuss some examples of sequential decomposition in decentralized control.
27 January 2009 Aditya will continue discussing sequential decision making in decentralized systems.
20 January 2009 Aditya Mahajan will talk about "sequential decision making in decentralized systems".
13 January 2009 David will discuss concentration inequalities via Marton's method.
17 December 2008 Sekhar will tell us more about the Hilbert metric, Birkhoff's contraction coefficient, and their use in determining mixing properties of nonhomogeneous Markov chains and filtering rates in HMMs.

END of fall 2008
23 December 2008 Sekhar will continue his talk from last week.
17 December 2008 Sekhar will tell us more about the Hilbert metric, Birkhoff's contraction coefficient, and their use in determining mixing properties of nonhomogeneous Markov chains and filtering rates in HMMs.
10 December 2008 Govind Menon will continue his talk on cube root asymptotics and Brownian motion with quadratic drift. This week: the details for the pde stuff.
3 December 2008 John Hartigan will talk on "Gaussian Estimates of Volumes."
26 November 2008 Thanksgiving break.
19 November 2008 Much exhaustion; seminar cancelled.
12 November 2008 ``Govind Menon, works on PDE's in mathematical physics at Brown. Some of his recent work is apparently connected to the Pollard-Kim cube root asymptotics paper and to related work of Groeneboom. Govind approached the subject from a PDE point of view but is interested in exploring further the statistical aspects of his work.''
5 November 2008 Nick will talk about max product.
29 October 2008 John Hartigan will enlighten us further on the topic of uniform distributions over contingency tables with fixed marginals. His thoughts on the subject were inspired by the recent talk by Alexander Barvinok in the Stats Monday seminar. For those who are interested, a copy of Barvinok's paper is attached. John has promised to make his talk self-contained; attendance at the Barvinok talk is not a prerequisite for YPNG.
22 October 2008 Nikhil Srivastava will talk on: Twice-Ramanujan Sparsifiers
We prove that for every d>1 and every undirected, weighted graph G(V,E) on n vertices, there exists a weighted subgraph H of G with at most dn edges which preserves the Laplacian quadratic form of G upto a multiplicative error of d+1 \pm 2\sqrt{d}. Thus, H approximates G spectrally at least as well as Ramanujan expanders approximate the complete graph, with at most twice as many edges. We give a deterministic polynomial time algorithm for constructing H. Joint work with Josh Batson and Dan Spielman.
15 October 2008 Antony Joseph will present a simplification of the conceptual proof of the kesten-stigum branching process theorem.
8 October 2008 Ou Zhao will discuss some refined tools to analyze stationary processes. Two particular results will be highlighted:
(1) characterization of the existence of martingale approximations for ``Markov random walks''.
(2) Martingale approximations with approximation rates, which lead to a good understanding of the fluctuation behavior of stationary processes. A ``quenched'' CLT follows easily.
1 October 2008 John Hartigan will discuss percolation on grids
24 September 2008 David Pollard will be discussing branching processes
17 September 2008 Steven Jaslar will continue his discussion of graph coloring on trees.
10 September 2008 Steven Jaslar will discuss his recent work.

END of summer 2008
26 August 2008 Sekhar will speak about mixing in HMMs. In particular he will talk about Birkhoff's contraction coefficient and the Hilbert metric approach.
19 August 2008 David will continue his discussion of majorizing measures.
12 August 2008 David will be speaking about majorizing measures.
5 August 2008 Sekhar will talk about estimating an unknown probability distribution when the size of the alphabet is unknown. In particular he will discuss the paper: "Universal Compression of Memoryless Sources Over Unknown Alphabets" by Orlitsky, et.al. (This won the IEEE-IT best paper award a few years ago.)
29 July 2008 John will speak about the EM algorithm.
22 July 2008 holiday
15 July 2008 Nick will continue his presentation from last week. Specifically he will talk about the minimum s-t path problem and the max-product algorithm.
8 July 2008 Nick will present some of his findings relating the s-t path and minimum cut problems and the max-product algorithm.
1 July 2008 Steven will discuss connections between the relaxed linear program on a graph and its associated computation tree
24 June 2008 Steven will continue his presentation from the last 2 weeks.
17 June 2008 Steven will continue his presentation from last week.
10 June 2008 Steven will discuss independent sets and matchings, the max-product algorithm, and connections with relaxed linear programs.
3 June 2008 Sekhar will discuss matchings, Edmond's blossom algorithm, and the Edmonds-Gallai graph decomposition.
20 May 2008 Since a few of us are working on issues of optimal matchings in random graphs it seems appropriate to discuss the basic facts about matchings in graphs. To that end Sekhar will motivate why the problem is important; discuss Edmond's algorithm for finding optimal matchings; review enough LP to talk about integer LP relaxations and total unimodularity; and discuss distributed algorithms based on the max-product algorithm for finding matchings in random graphs.
15 May 2008 Edmund Yeh will talk about geometric graphs and the like.

END of spring 2008
23 April 2008 Arlene Kim will combine the ideas from the last few talks to get a maximal inequality for an empirical process indexed by a collection of functions.
16 April 2008 David will continue his discussion of the connections between VC dimension and entropy.
9 April 2008 David will discuss connections between VC dimension and entropy.
2 April 2008 Mike Kane will discuss an important lemma in VC theory.
26 March 2008 Sekhar will talk about phase transitions in error-correcting codes.
5 March 2008 John will discuss some connections between the beta distribution and the Hoeffding decomposition.
27 February 2008 Armand Makowski from the University of Maryland will discuss critical thresholds in random geometric graphs under non-uniform node placement.
20 February 2008 Mokshay will continue his discussion of the connections between exchangeability and the Hoeffding decomposition.
13 February 2008 Mokshay will discuss some connections between exchangeability and the Hoeffding decomposition.
6 February 2008 David will discuss the de Finetti proof of exchangeability.
30 January 2008 Aditya will revisit the localization lemma of Lovasz and Simonovits.
23 January 2008 Sekhar will discuss exchangeability, finite exchangeability, and Markov exchangeability. Note these concepts are not exchangeable.
16 January 2008 Aditya will discuss the localization lemma of Lovasz and Simonovits.

END of fall 2007
12 December 2007 David will discuss conditional Poissons and their use in determining chromatic numbers of random graphs.
5 December 2007 We'll tackle some of the results Mokshay didn't have time to cover in the seminar last week.
28 November 2007 Mokshay will finish discussing the Bertsimas-Vempala optimization algorithm.
21 November 2007 Turkey break. No seminar.
14 November 2007 Sekhar will discuss cluster expansions.
7 November 2007 David will discuss the Prekopa-Leindler Inequality.
31 October 2007 Mokshay will scare us by discussing stochastic optimization.
24 October 2007 Sekhar will discuss Wick decompositions and cluster expansions.
17 October 2007 Aditya will continue his discussion of mixing in Markov chains. He will talk about canonical paths and the Poincare inequality.
10 October 2007 Aditya will continue his discussion of conductance and mixing in Markov chains.
3 October 2007 Aditya will discuss graphs and chains and mixing...
26 September 2007 John will talk about partial orders, probabilities on them, probabilities to the right of them, probabilities to the left of them, on and on rode the 600.
19 September 2007 Sekhar will continue his discussion of Markov chains, reversibility, entropy....
12 September 2007 Sekhar will present a hodgepodge of ideas connecting Markov chains, reversibility, electrical networks, second law of thermodynamics, Dirichlet forms, and trees in a coherent manner. We'll see how that goes.
5 September 2007 David will try to summarize some of what we have learned about harmonic functions and the solution of the Dirichlet problem using Markov chains. He will explain why harmonic functions minimize energy and how this fact relates to the relaxation method for solving the Dirichlet problem.

END of summer 2007
29 August 2007 Sekhar will continue his progress towards the Markov chain tree theorem.
22 August 2007 Sekhar will give us a gentle introduction to random walks and electrical networks. He will head towards the Markov chain tree theorem.
15 August 2007 Nikhil will be presenting his recent joint work (with Dan S.) on "Fast Graph Sparsification by Random Sampling".
8 August 2007 Steven will continue his discussion of bonuses and his take on Gamarnik.
1 August 2007 [Everyone away at JSM.]
24 July 2007 Steven will talk about Gamarnik's work and his own extensions.
18 July 2007 This week we have a collection of bits and pieces for the seminar. Dimiter could take us through yet another of Friedgut's Lemmas. Perhaps more interesting to most of you would be his argument using Bourgain's criterion to establish a sharp threshold for connectedness.
If we run out of things to do, David could talk about another way to get the Fourier coefficients for the functional that recognizes the presence of a triangle. I have hopes that my modification of Dimiter's method might make it easier to do similar calculations for functionals that recognize the presence of copies of other graphs.
11 July 2007 [everyone is out of town]
4 July 2007 Dimiter will explain Friedgut's reasoning for the Lemma that confused DP and HZ.
27 June 2007 Dimiter will calculate the coefficients for the monotone functional ``graph contains a triangle". If time permits, we will also learn how Bourgain's criterion gives a sharp threshold for connectedness.
20 June 2007 Sekhar will continue with the discussion of thresholds for geometric random graphs.
13 June 2007 Sekhar will discuss thresholds for monotone properties in geometric random graphs. An interesting question to mull over: is there a coarse/sharp dichotomy?
6 June 2007 Harry will take us into the mysterious core of the Bourgain proof.
30 May 2007 Harry will continue, explaining the key steps in the Bourgain argument.
23 May 2007 Harry Zhou will present background material needed to understand the Bourgain appendix to Friedgut (1999) JAMS, "Sharp thresholds of graph properties, and the K-sat problem".
16 May 2007 John Hartigan will talk about connected components in random graphs. [DP will add comments on the role of the series \sum_{n=1}^\infty n^{n-1}\lambda^n \exp(-n\lambda)/n! and related ideas.]
9 May 2007 David Pollard will talk about generalized Polya urn models and the limiting occupancy distribution. He will talk some more about the ideas introduced last week by Pemantle. "As I suspect that some of you were not familiar with all the probability that he was using, I'll fill in some background (exchangeability, reverse martingales, De Finetti, ...). I hope to explain why the limit for the Polya urn has a beta distribution (easy once you know about De Finetti) and give an exposition of some of the results in the paper: A Strong Law for Some Generalized Urn Processes Bruce M. Hill; David Lane; William Sudderth The Annals of Probability Vol. 8, No. 2 (Apr., 1980), pp. 214-226"
2 May 2007 Robin Pemantle will talk about random processes with reinforcement. He has written a survey on this topic, here: http://www.math.upenn.edu/~pemantle/papers/reinforce.pdf

END of spring 2007
25 April 2007 David Pollard will discuss some aspects of Le Cam theory -- on the asymptotic equivalence of different statistical questions.
18 April 2007 Steven Jaslar will continue his discussion of sharp thresholds in the context of graph coloring.
11 April 2007 Steven Jaslar will continue his discussion of sharp thresholds in the context of graph coloring.
4 April 2007 Steven Jaslar will discuss sharp thresholds in the context of graph coloring.
28 March 2007 Sekhar Tatikonda will review "what I learned at the DIMACS workshop."
7 March 2007 Steven Jaslar will continue his discussion of Wormald's paper.
28 February 2007 Steven Jaslar will discuss Wormald's ODE to martingale analysis. Prereq for the talk: an appreciation for birdsong recommended but not required.
21 February 2007 Giacomo Como will present the paper "Tracking Stopping Times" by A. Tchamkerten, U. Niesen and G. Wornell.
14 February 2007 David Pollard will discuss Wormald's ODE method.
7 February 2007 Sekhar Tatikonda will present Dror Weitz new approach for computing exact marginals on loopy graphs. This involves a variation of the computation tree that involves only self-avoiding walks of the graph and a clever initialization of the messages.
31 January 2007 John Hartigan will speak on minimum spanning trees, nearest neighbor density estimation, single linkage clusters, and percolation.
24 January 2007 Giacomo Como will talk about sequential hypothesis testing in random environments.
17 January 2007 Sekhar Tatikonda will discuss Gibbs measures on trees, the differences between Markov random fields and Markov chains, and, if time, discuss alternative approaches to proving uniqueness (i.e. beyond Dobrushin's contraction argument.)

END of fall 2006
19 December 2006 Stephan Winkler will discuss techniques for proving uniqueness of Gibbs measures.
13 December 2006 Steven Jaslar will discuss graph coloring.
5 December 2006 Sekhar Tatikonda will present "Counting good truth assignments of random k-SAT formulae" by A. Montanari and D. Shah. http://arxiv.org/abs/cs.DM/0607073
28 November 2006 This week David will talk about the evolution of clusters in Erdos-Renyi graphs.
14 November 2006 Mokshay Madiman will discuss entropy power inequalities for sums, including applications to the central limit theorem. Along the way, there will be some rather interesting excursions into classical tools from statistical theory.
7 November 2006 In honor of our participatory democracy Mokshay Madiman will participate by presenting "entropy inequalities and applications, including to counting". I'll get the talk started: 1, 2, 3, 4,...
31 October 2006 Boo! Ravi Montenegro will talk about: A canonical path approach to bounding collision time for Pollard's Rho algorithm.
24 October 2006 Yet another attempt at the variance bound for the Achlioptas and Naor paper: David will present his latest thoughts on conditional Poissons and its relation to moment calculations. [Success at last.]
17 October 2006 Stephan Winkler will continue his discussion of Bayati and Nair's paper "A rigorous proof of the cavity method for counting matchings".
10 October 2006 Stephan Winkler will discuss "A rigorous proof of the cavity method for counting matchings" by Bayati and Nair.
3 October 2006 John Hartigan will build on David's approach to multinomial expectations. [One more shot at Achlioptas and Naor.]
26 September 2006 David Pollard will present his learned opinion on the matter of expectations with respect to multinomials. [Yet another attempt to understand Achlioptas and Naor.]
19 September 2006 Sekhar Tatikonda will continue with the discussion of large deviations with applications to moment calculations.
12 September 2006 Sekhar Tatikonda will give a tutorial on large deviations with an emphasis on applications to moment calculations. [Another attempt to understand Achlioptas and Naor.]

END of summer 2006
29 August 2006 Come one, come all, to the last seminar of the summer. The finale of our summer symphony will be orchestrated by Maestro Mokshay Madiman. Come watch him hum a few bars on the topic of monotonicity properties of information measures.
22 August 2006 Nikhil Srivastava will discuss the 'evolving sets method' for bounding the mixing time of a Markov chain, and an application of the method in a new proof of Cheeger's inequality. The talk is loosely based on the following papers: Evolving sets, mixing and heat kernel bounds by Ben Morris and Yuval Peres http://arxiv.org/abs/math.PR/0305349 Generalized Cheeger inequalities for eigenvalues of non-reversible Markov Chains http://www.ravimontenegro.com/research/cheeger.pdf
15 August 2006 Sekhar Tatikonda will continue discussing "The Two Possible Values of the Chromatic Number of a Random Graph" by Achlioptas and Naor
8 August 2006 Sekhar Tatikonda will discuss "The Two Possible Values of the Chromatic Number of a Random Graph" by Achlioptas and Naor.
1 August 2006 Stephan Winkler will continue his discussion of the properties of the max-product fixed point equations in the seminar tomorrow.
25 July 2006 Stephan Winkler will discuss properties of the max-product fixed point equations in the seminar tomorrow.
18 July 2006 Steven Jaslar will discuss connections between graph coloring and belief propagation.
27 June 2006 Yo yo yo, Harry Zhou in the hooouuuusssseeeee. Come to the stat. 'hood tomorrow at 1 and give him your props as he discusses his CAREER proposal on asymptotic equivalence of inference problems.
20 June 2006 Sekhar Taitkonda will discuss dynamic programming on infinite trees.
6 June 2006 Sekhar Tatikonda will continue his discussion of Gamarnik's work on max-weight independent set and max-weight matching for random graphs.
16 May 2006 Sekhar Taitkonda will continue discussion of the Garmarnik paper on max weight independent sets and max weight matchings on random graphs using the max-product algorithm.
4 May 2006 Sekhar Tatikonda will be presenting the Gamarnik paper on max independent sets.

END of spring 2006
27 April 2006 Here's the story of Steven Jaslar; who was reading three very tough papers; all of them used max-product, and beliefs; the last one had bonuses.
20 April 2006 Steven Jaslar will present more work on the max-weight matching problem, connections between bonuses and beliefs, and the like.
6 April 2006 Sekhar Tatikonda will talk about the clustering of solutions for combinatorial optimization problems in the non-unique measure case.
30 March 2006 Steven Jaslar will continue talking about the max-weight matching problem.
23 March 2006 Steven Jaslar will talk about the max-weight matching problem.
2 March 2006 Steven Jaslar will continue his discussion of the objective method.
23 February 2006 Mokshay Madiman says: "Tighten your seatbelts for a ride through the world of functional inequalities and hypercontractivity!"
16 February 2006 Sekhar Tatikonda will discuss "Monotone properties of random geometric graphs have sharp thresholn inequalities.
2 February 2006 Steven Jaslar will continue his discussion of the objective method.

END of fall 2005
13 December 2005 Mokshay Madiman will discuss "Boolean Functions with Low Average Sensitivity Depend on Few coordinates." Combinatorica Vol 18 (1) 1998
16 November 2005 David Pollard and Harry Zhou will discuss Friedgut's threshold paper.
9 November 2005 David Pollard and Harry Zhou will discuss Friedgut's threshold paper.
2 November 2005 David Pollard and Harry Zhou will discuss Friedgut's threshold paper.
26 October 2005 Sekhar Tatikonda will discuss the connection between Gibbs measures and the loopy sum-product algorithm.
19 October 2005 Jian Ni will introduce an application of factor graphs and the sum-product algorithm on analyzing loss networks.
12 October 2005 Steven Jaslar will discuss the "objective method."
5 October 2005 Sekhar Tatikonda will discuss connections between Glauber dynamics and infinite site Gibbs measures.
28 September 2005 Stephan Winkler will discuss the survey propagation algorithm.
21 September 2005 David Pollard will discuss the "objective method."

END of summer 2005
19 August 2005 Sekhar Tatikonda will continue his discussion of last week.
22 July 2005 Sekhar Tatikonda will first present an alternative proof of Talagrand's convex distance exponential bound based on the "entropy method" introduced by Ledoux and Massart. Then we will present another concentration result useful for proving the self-averaging property of spin glasses. The proof of this result is based on the "smart path method." Finally, if there is time, he will introduce the notion of overlaps and the role they play in spin glasses.
15 July 2005 Stephan Winkler will motivate (using a bin packing problem) and prove Talagrand's "convex hull concentration inequality", which improves on the bound derived last week.
8 July 2005 David Pollard will be speak about some of the motivation for one of Talagrand's concentration inequalities (multi-point control).
1 July 2005 John Hartigan will discuss "How to win the Tour De France."
24 June 2005 David Pollard will discuss concentration inequalities.
17 June 2005 Sekhar Tatikonda will continue his discussion of "Free Energy: What is it Good For? - Part 3"
10 June 2005 Sekhar Tatikonda will continue his discussion of "Free Energy: What is it Good For? - Part 2"
3 June 2005 Sekhar Tatikonda will discuss: "Free Energy: What is it Good For?" Physicists have developed many techniques for determining equilibrium properties of statistical mechanical systems. These techniques have also found use in combinatorial optimization problems. Some of these techniques include: the mean field approximation, the cavity method, and the replica method. These techniques have made remarkable predictions but at present there does not exist a rigorous mathematical basis for them. Talagrand and others have started on a program to make these techniques rigorous. These techniques are based on tools from convexity and concentration of measure. This summer we hope to understand these techniques as well.