Seminars and Colloquia by Series

Liar Games, Optimal Codes, and Deterministic Simulation of Random Walks

Series
Combinatorics Seminar
Time
Thursday, May 21, 2009 - 11:00 for 1 hour (actually 50 minutes)
Location
Skiles 255
Speaker
Joshua CooperDepartment of Mathematics, University of South Carolina
We consider the Ulam "liar" and "pathological liar" games, natural and well-studied variants of "20 questions" in which the adversarial respondent is permitted to lie some fraction of the time. We give an improved upper bound for the optimal strategy (aka minimum-size covering code), coming within a triply iterated log factor of the so-called "sphere covering" lower bound. The approach is twofold: (1) use a greedy-type strategy until the game is nearly over, then (2) switch to applying the "liar machine" to the remaining Berlekamp position vector. The liar machine is a deterministic (countable) automaton which we show to be very close in behavior to a simple random walk, and this resemblance translates into a nearly optimal strategy for the pathological liar game.

Nonlinear 4th order diffusion equations by optimal transport

Series
PDE Seminar
Time
Tuesday, May 5, 2009 - 15:00 for 1 hour (actually 50 minutes)
Location
Skiles 255
Speaker
Giuseppe SavareUniversità degli Studi di Pavia, Italy
Some interesting nonlinear fourth-order parabolic equations, including the "thin-film" equation with linear mobility and the quantum drift-diffusion equation, can be seen as gradient flows of first-order integral functionals in the Wasserstein space of probability measures. We will present some general tools of the metric-variational approach to gradient flows which are useful to study this kind of equations and their asymptotic behavior. (Joint works in collaboration with U.Gianazza, R.J. McCann, D. Matthes, G. Toscani)

Laguerre-Sobolev type orthogonal polynomials. Algebraic and analytic properties

Series
Analysis Seminar
Time
Wednesday, April 29, 2009 - 14:00 for 1 hour (actually 50 minutes)
Location
Skiles 255
Speaker
Francisco MarcellanUniversidad Carlos III de Madrid

In this contribution we study the asymptotic behaviour of polynomials orthogonal with respect to a Sobolev-Type inner product
\langle p, q\rangle_S = \int^\infty_0 p(x)q(x)x^\alpha e^{-x} dx + IP(0)^t AQ(0), \alpha > -1,
where p and q are polynomials with real coefficients,
A = \pmatrix{M_0 & \lambda\\ \lambda & M_1}, IP(0) = \pmatrix{p(0)\\ p'(0)}, Q(0) = \pmatrix{q(0)\\ q'(0)},
and A is a positive semidefinite matrix.

First, we analyze some algebraic properties of these polynomials. More precisely, the connection relations between the polynomials orthogonal with respect to the above inner product and the standard Laguerre polynomials are deduced. On the other hand, the symmetry of the multiplication operator by x^2 yields a five term recurrence relation that such polynomials satisfy.

Second, we focus the attention on their outer relative asymptotics with respect to the standard Laguerre polynomials as well as on an analog of the Mehler-Heine formula for the rescaled polynomials.

Third, we find the raising and lowering operators associated with these orthogonal polynomials. As a consequence, we deduce the holonomic equation that they satisfy. Finally, some open problems will be considered.

Optimal Query Complexity Bounds for Finding Graphs

Series
ACO Seminar
Time
Wednesday, April 29, 2009 - 11:00 for 1 hour (actually 50 minutes)
Location
Skiles 255
Speaker
Jeong Han KimYonsei University and NIMS, South Korea
We consider the problem of finding an unknown graph by using two types of queries with an additive property. Given a graph, an additive query asks the number of edges in a set of vertices while a cross-additive query asks the number of edges crossing between two disjoint sets of vertices. The queries ask sum of weights for the weighted graphs. These types of queries were partially motivated in DNA shotgun sequencing and linkage discovery problem of artificial intelligence. For a given unknown weighted graph G with n vertices, m edges, and a certain mild condition on weights, we prove that there exists a non-adaptive algorithm to find the edges of G using O\left(\frac{m\log n }{\log m}\right) queries of both types provided that m \geq n^{\epsilon} for any constant \epsilon> 0. For a graph, it is shown that the same bound holds for all range of m. This settles a conjecture of Grebinski for finding an unweighted graph using additive queries. We also consider the problem of finding the Fourier coefficients of a certain class of pseudo-Boolean functions. A similar coin weighing problem is also considered. (This is joint work with S. Choi)

Aluthge iteration of an operator

Series
Analysis Seminar
Time
Monday, April 27, 2009 - 15:00 for 1 hour (actually 50 minutes)
Location
Skiles 255
Speaker
Tin Yau TamDepartment of Mathematics, Auburn University
Let A be a Hilbert space operator. If A = UP is the polar decomposition of A, and 0 < \lambda < 1, the \lambda-Aluthge transform of A is defined to be the operator \Delta_\lambda = P^\lambda UP^{1-\lambda}. We will discuss the recent progress on the convergence of the iteration. Infinite and finite dimensional cases will be discussed.

A New Look at the Compound Poisson Distribution and Compound Poisson Approximation

Series
Combinatorics Seminar
Time
Friday, April 24, 2009 - 15:00 for 1 hour (actually 50 minutes)
Location
Skiles 255
Speaker
Mokshay MadimanDepartment of Statistics, Yale University
We develop an information-theoretic foundation for compound Poisson approximation and limit theorems (analogous to the corresponding developments for the central limit theorem and for simple Poisson approximation). First, sufficient conditions are given under which the compound Poisson distribution has maximal entropy within a natural class of probability measures on the nonnegative integers. In particular, it is shown that a maximum entropy property is valid if the measures under consideration are log-concave, but that it fails in general. Second, approximation bounds in the (strong) relative entropy sense are given for distributional approximation of sums of independent nonnegative integer valued random variables by compound Poisson distributions. The proof techniques involve the use of a notion of local information quantities that generalize the classical Fisher information used for normal approximation, as well as the use of ingredients from Stein's method for compound Poisson approximation. This work is joint with Andrew Barbour (Zurich), Oliver Johnson (Bristol) and Ioannis Kontoyiannis (AUEB).

The Jones polynomial and quantum invariants

Series
Geometry Topology Working Seminar
Time
Friday, April 24, 2009 - 15:00 for 2 hours
Location
Skiles 269
Speaker
Thang LeSchool of Mathematics, Georgia Tech

Please Note: These are two hour lectures.

We will develop general theory of quantum invariants based on sl_2 (the simplest Lie algebra): The Jones polynomials, the colored Jones polynomials, quantum sl_2 groups, operator invariants of tangles, and relations with the Alexander polynomial and the A-polynomials. Optional: Finite type invariants and the Kontsevich integral.

Omnibus Tests for Comparison of Competing Risks under the Additive Risk Model

Series
Stochastics Seminar
Time
Thursday, April 23, 2009 - 15:00 for 1 hour (actually 50 minutes)
Location
Skiles 269
Speaker
Yichuan ZhaoDepartment of Mathematics, Georgia State University
It is of interest that researchers study competing risks in which subjects may fail from any one of k causes. Comparing any two competing risks with covariate effects is very important in medical studies. In this talk, we develop omnibus tests for comparing cause-specific hazard rates and cumulative incidence functions at specified covariate levels. The omnibus tests are derived under the additive risk model by a weighted difference of estimates of cumulative cause-specific hazard rates. Simultaneous confidence bands for the difference of two conditional cumulative incidence functions are also constructed. A simulation procedure is used to sample from the null distribution of the test process in which the graphical and numerical techniques are used to detect the significant difference in the risks. In addition, we conduct a simulation study, and the simulation result shows that the proposed procedure has a good finite sample performance. A melanoma data set in clinical trial is used for the purpose of illustration.

Pages