Monday, March 19, 2012 - 09:20 for 8 hours (full day)
Location
Klaus 1116
Speaker
Tutorial lectures by Andreas Krause, Kazuo Murota and Jan Vondrak – ETH, University of Tokyo, and IBM
Workshop Theme: Submodular functions are discrete analogues of convex functions, arising in various fields of computer science and operations research. Since the seminal work of Jack Edmonds (1970), submodularity has long been recognized as a common structure of many efficiently solvable combinatorial optimization problems. Recent algorithmic developments in the past decade include combinatorial strongly polynomial algorithm for minimization, constant factor approximation algorithms for maximization, and efficient methods for learning submodular functions. In addition, submodular functions find novel applications in combinatorial auctions, machine learning, and social networks. This workshop aims at providing a forum for researchers from a variety of backgrounds for exchanging results, ideas, and problems on submodular optimization and its applications. The workshop will be held from March 19-22, 2012. For complete details and workshop program, please see
the website.
Friday, March 16, 2012 - 15:05 for 1 hour (actually 50 minutes)
Location
Skiles 005
Speaker
Mihai Ciucu – Mathematics, Indiana University, Bloomington, IN
The correlation of gaps in dimer systems was introduced in 1963 by
Fisher and Stephenson, who looked at the interaction of two monomers
generated by the rigid exclusion of dimers on the closely packed square
lattice. In previous work we considered the analogous problem on the
hexagonal lattice, and we extended the set-up to include the correlation of
any finite number of monomer clusters. For fairly general classes of monomer
clusters we proved that the asymptotics of their correlation is given, for
large separations between the clusters, by a multiplicative version of
Coulomb's law for 2D electrostatics. However, our previous results required
that the monomer clusters consist (with possibly one exception) of an even
number of monomers. In this talk we determine the asymptotics of general
defect clusters along a lattice diagonal in the square lattice (involving an
arbitrary, even or odd number of monomers), and find that it is given by the
same Coulomb law. Of special interest is that one obtains a conceptual
interpretation for the multiplicative constant, as the product of the
correlations of the individual clusters. In addition, we present several
applications of the explicit correlation formulas that we obtain.
I present a new class of vertex cover and set cover games, with the price of anarchy bounds matching the best known
constant factor approximation guarantees for the centralized optimization problems for linear and also for submodular
costs. In particular, the price of anarchy is 2 for vertex cover. The
basic intuition is that the members of the vertex cover form a Mafia
that has to "protect" the graph, and may ask ransoms from their
neighbors in exchange for the protection. These ransoms turn out to
capture a good dual solution to the linear programming relaxation. For linear costs we also exhibit
linear time best response dynamics that converge that mimic the classical greedy approximation algorithm of Bar-Yehuda
and Even. This is a joint work with Georgios Piliouras and Tomas Valla.
Thursday, March 15, 2012 - 15:05 for 1 hour (actually 50 minutes)
Location
skyles 006
Speaker
Vygantas Paulauskas – Vilnius University, Lithuania
In
the talk we demonstrate the usefulness of the so-called Beveridge-Nelson
decomposition in asymptotic analysis of sums of values
of linear processes and fields. We consider several generalizations
of this decomposition and discuss advantages and shortcomings of this
approach which can be considered as one of possible methods to deal
with sums of dependent random variables. This decomposition is
derived for linear processes and fields with the continuous time
(space) argument. The talk is based on several papers, among them [V.
Paulauskas, J. Multivar. Anal. 101,
(2010), 621-639] and [Yu. Davydov and V. Paulauskas, Teor. Verojat.
Primenen., (2012), to appear]
Thursday, March 15, 2012 - 12:05 for 1 hour (actually 50 minutes)
Location
Skiles 005
Speaker
Po-Shen Loh – Carnegie Mellon University
Erd\H{o}s and Rothschild asked to estimate the maximum number, denotedby $h(n,c)$, such that every $n$-vertex graph with at least $cn^2$edges, each of which is contained in at least one triangle, mustcontain an edge that is in at least $h(n,c)$ triangles. In particular,Erd\H{o}s asked in 1987 to determine whether for every $c>0$ there is$\epsilon>0$ such that $h(n,c)>n^{\epsilon}$ for all sufficientlylarge $n$. We prove that $h(n,c)=n^{O(1/\log \log n)}$ for every fixed$c<1/4$. This gives a negative answer to the question of Erd\H{o}s,and is best possible in terms of the range for $c$, as it is knownthat every $n$-vertex graph with more than $n^2/4$ edges contains anedge that is in at least $n/6$ triangles.Joint work with Jacob Fox.
Wednesday, March 14, 2012 - 14:00 for 1 hour (actually 50 minutes)
Location
Skiles 006
Speaker
Vygantas Paulauskas – Vilnius University
In the talk some problems related with the famous Chernoff square root of
n - lemma in the theory of approximation of some semi-groups of operators will
be discussed. We present some optimal bounds in these approximations
(one of them is Euler approximation) and two new classes of operators,
generalizing sectorial and quasi-sectorial operators will be introduced.
The talk is based on two papers [V. Bentkus and V. Paulauskas, Letters
in Math. Physics, 68, (2004), 131-138] and [V. Paulauskas, J. Functional
Anal., 262, (2012), 2074-2099]
Amanda Pascoe Streib – School of Mathematics, Georgia Tech
The fields of statistical physics, discrete probability, combinatorics, and theoretical computer science have converged around efforts to understand random structures and algorithms. Recent activity in the interface of these fields has enabled tremendous breakthroughs in each domain and has supplied a new set of techniques for researchers approaching related problems. This thesis makes progress on several problems in this interface whose solutions all build on insights from multiple disciplinary perspectives.
First, we consider a dynamic growth process arising in the context of DNA-based self-assembly. The assembly process can be modeled as a simple Markov chain. We prove that the chain is rapidly mixing for large enough bias in regions of Z^d. The proof uses a geometric distance function and a variant of path coupling in order to handle distances that can be exponentially large. We also provide the first results in the case of fluctuating bias, where the bias can vary depending on the location of the tile, which arises in the nanotechnology application. Moreover, we use intuition from statistical physics to construct a choice of the biases for which the Markov chain M_{mon} requires exponential time to converge.
Second, we consider a related problem regarding the convergence rate of biased permutations that arises in the context of self-organizing lists. The Markov chain M_{nn} in this case is a nearest-neighbor chain that allows adjacent transpositions, and the rate of these exchanges is governed by various input parameters. It was conjectured that the chain is always rapidly mixing when the inversion probabilities are positively biased, i.e., we put nearest neighbor pair x < y in order with bias 1/2 <= p_{xy} <=
1 and out of order with bias 1-p_{xy}. The Markov chain M_{mon} was known to have connections to a simplified version of this biased card-shuffling. We provide new connections between M_{nn} and M_{mon} by using simple combinatorial bijections, and we prove that M_{nn} is always rapidly mixing for two general classes of positively biased {p_{xy}}. More significantly,
we also prove that the general conjecture is false by exhibiting values for the p_{xy}, with 1/2 <= p_{xy} <= 1 for all x < y, but for which the transposition chain will require exponential time to converge.
Finally, we consider a model of colloids, which are binary mixtures of molecules with one type of molecule suspended in another. It is believed that at low density typical configurations will be well-mixed throughout, while at high density they will separate into clusters. This clustering has proved elusive to verify, since all local sampling algorithms are known to be inefficient at high density, and in fact a new nonlocal algorithm was recently shown to require exponential time in some cases. We characterize the high and low density phases for a general family of discrete interfering binary mixtures by showing that they exhibit a "clustering property" at high density and not at low density. The clustering property states that there will be a region that has very high area, very small perimeter, and high density of one type of molecule. Special cases of interfering binary mixtures include the Ising model at fixed magnetization and independent sets.
Wednesday, March 14, 2012 - 11:00 for 1 hour (actually 50 minutes)
Location
Skiles 006
Speaker
Boris Kalinin – Univ. of Southern Alabama
Hyperbolic actions of Z^k and R^k arise naturally in algebraic
and geometric context. Algebraic examples include actions by
commuting automorphisms of tori or nilmanifolds and, more generally,
affine and homogeneous actions on cosets of Lie groups. In contrast
to hyperbolic actions of Z and R, i.e. Anosov diffeomorphisms and
flows, higher rank actions exhibit remarkable rigidity properties,
such as scarcity of invariant measures and smooth conjugacy to
a small perturbation. I will give an overview of results in this area
and discuss recent progress.
Tuesday, March 13, 2012 - 15:05 for 1 hour (actually 50 minutes)
Location
Skiles 005
Speaker
John McCuan – Georgia Tech
The stability of a liquid drop of prescribed volume hanging from a circular cylindrical tube in a gravity field has been a problem of continuing interest. This problem was treated variationally in the late '70s by Henry Wente who showed there was a continuous family indexed by increasing volume which terminated in a final unstable equilibrium due to one or the other of two specific geometric mechanisms. I will describe a similar problem arising in mathematical biology for drops at the bottom of a rectangular tube and explain, among other things, how the associated instability occurs through exactly three physical mechanisms.