YPNG seminars

Spring 2012: x-days from y-z in the main classroom of 24 Hillhouse.

date	topic
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: http://en.wikipedia.org/wiki/Szemerédi_regularity_lemma 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, Tao, Terence (2006), "A variant of the hypergraph removal lemma", Journal of Combinatorial Theory. Series A 113 (7): 1257–1280, 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 Abstract: 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 Talagrands 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.