MSCS Seminar Calendar

Knowledge representation and reasoning (KR&R) is the branch of Artificial Intelligence (AI) devoted to the design, analysis, and implementation of inference algorithms and data structures. Traditionally, it is divided into applications of logical representations and applications of probabilistic ones. Logic is more convenient for representing relational, object-based knowledge and is well suited for combinatorial (non-convex) problems and structures. Graphical probabilistic models represent uncertain knowledge better, are more natural for learning in the presence of noise. In the last 15 years the field of KR&R has concentrated efforts on general methods for large-scale probabilistic representation and reasoning through relational probabilistic representations. Those representations use logical atoms such as partners(X,Y) as random variables parameterized by logical variables. In this talk I will present the state of the art in representation and inference with relational probabilistic models, pointing out open questions and challenges. I will also discuss ongoing work in my group on this topic, with applications to social network analysis and large models of dependencies in economics.

This talk continues from last week: The idea of "categorification" has now entered the representation theory of semisimple Lie algebras and finite groups of Lie type. Khovanov and Lauda defined certain algebras using diagrams of the kind familiar to knot theorists. These algebras now play a role in the categorification mentioned above. In this talk we will explain some of these ideas.

Recently (in joint work with Chris Laskowski) we characterized countable, weakly minimal theories $T$ such that any two (elementarily) bi-embeddable models of $T$ are isomorphic. We prove that if $T$ is countable and weakly minimal, the following are equivalent: 1. $T$ has two bi-embeddable but nonisomorphic models; 2. There is an automorphism $f$ of the monster model of $T$ and a strong type $p$ over the empty set which is almost-orthogonal to $f(p) \otimes \ldots \otimes f^n(p) $ for any n. 3. $T$ has an infinite collection of models that are pairwise bi-embeddable but pairwise nonisomorphic. The proof involves some geometric stability theory plus a Dushnik-Miller type argument to build nonisomorphic models by "killing'' every potential isomorphism at each stage of the construction.

The Dehn function is a group invariant which connects geometric and combinatorial group theory; it measures both the difficulty of the word problem and the area necessary to fill a closed curve in an associated space with a disc. The behavior of the Dehn function for high-rank lattices in high-rank symmetric spaces has long been an open question; one particularly interesting case is SL(n,Z). Thurston conjectured that SL(n,Z) has a quadratic Dehn function when n>=4. This differs from the behavior for n=2 (when the Dehn function is linear) and for n=3 (when it is exponential). I have proven that it is quadratic when n>=5, and in this talk, I will discuss some of the background of the problem and sketch a proof that it is at most quartic when n >= 5.

We introduce a new type of design, called nested Latin hypercube design, for sequential integration and multi-fidelity computer modeling. A nested Latin hypercube design is defined to be a special Latin hypercube design that contains a smaller Latin hypercube design as a subset. Such designs are constructed by exploiting nested structures in random permutations. The constructed designs are also useful for solving stochastic optimization problems, including stochastic programs, the Monte Carlo EM algorithm and chance-constraint problems.

In the 1970's, Lenstra generalized the notion of a Euclidean ring to that of a ring with a Euclidean ideal. In the context of Dedekind domains, the consequence of the existence of such an ideal is the cyclicity of the class group in much the same way that the consequence of the existence of a Euclidean algorithm is the triviality of the class group. In this talk, I'll discuss Lentra's notion in light of some recent developments of Hester Graves. In particular, I'll discuss a joint result with Graves classifying the quadratic imaginary fields (which play a rather exception role in the theory) that have a Euclidean ideal.

This talk will continue themes that were started a few weeks ago. In particular, the speaker will discuss ideas relating statistical mechanics to the Khovanov homology.

The problem that gave rise to the research to be reported in this lecture is the following: Given a (finite) group G and a finite dimensional topological space X, can G act freely on X? In the early 1980's Gunnar Carlsson, Bill Browder, Steve Halperin, and others found a number of interesting algebraic obstructions to free actions. In my talk, I will present certain aspects of recent work in commutative algebra that is motivated by, and perhaps clarifies, some of their results. This is based on joint work with Avramov, Buchweitz, and C. Miller, and reported in our paper "Homology of perfect complexes", arXiv: math/0609008.

The connection between ergodic theory and additive combinatorics dates back to the 1970's, with Furstenberg's proof of Szemeredi's Theorem via ergodic theory. Certain algebraic constraints (arising from nilsystems) play a key role in understanding objects that arise in Furstenberg's proof. More recently, nil-structures have been imported into the finite combinatorial setting, playing a role in finding patterns in the primes. I will give an overview of where nilsystems arise in ergodic theory and topological dynamics, explaining some of the connections to additive combinatorics.

We will explain how Furstenberg's correspondence principle can be used to estimate from below the upper Banach density of A+B for sets A and B in a countable infinite abelian group. New results will be discussed for the case B is a Bohr set (almost periodic set). This is joint work with M. Bjorklund (Hebrew University).

In this joint work with Hee Oh, we consider various sphere packing configurations, which happen to be invariant under actions of geometrically finite hyperbolic groups, and estimate the cardinality of spheres of curvature (with respect to euclidean, or spherical, or hyperbolic metric) at most T for some large T. This sphere counting problem is studied by formulating and proving certain ``weighted equidistribution'' results related to the geodesic flow on the unit tangent bundle of a hyperbolic $n$-manifold $H^n/\Gamma$, where $\Gamma$ is a geometrically finite discrete group of isometries of $H^n$.

In 1958, Kolmogorov defined the entropy of a probability measure preserving transformation. Entropy has since been central to the classification theory of measurable dynamics. In the 70's and 80's researchers extended entropy theory to measure preserving actions of amenable groups (Kieffer, Ornstein-Weiss). My recent work generalizes the entropy concept to actions of sofic groups; a class of groups that contains for example, all subgroups of GL(n,C). Applications include the classification of Bernoulli shifts over a free group. This answers a question of Ornstein and Weiss.

Consider larger and larger metric spheres in a group. Under nice circumstances, these converge to a definite "limit shape" as the radius goes to infinity. For instance in finitely generated nilpotent groups one may use the rescaling homothety in the ambient Lie group to shrink down large spheres, and by work of Pansu (extended by Breuillard) this gives a well-defined limit. For a simple example, in the free abelian group $Z^2$, if we take the standard generating set, the limit shape is a diamond (and the limiting metric, for which this is the unit sphere, is the $L^1$ metric on the plane). It is natural to ask whether the counting measure on the discrete spheres converges to a measure on the limit shape. I'll discuss our work on this question, and give some ergodic applications and some averaging applications for limit shapes. Parts of this project are joint work with Samuel Lelievre, Christopher Mooney, and Ralf Spatzier.

Automorphism groups of first order structures exhibit a number of interesting dynamical phenomena not easily encountered in other topological groups. We shall focus on the existence of large, i.e., dense or even comeagre, conjugacy classes in automorphism groups and see how the existence of these relates to strengthened versions of residual finiteness for countable groups. Moreover, we shall indicate how the existence of comeagre conjugacy classes strongly determines the structure of a topological group.

While it is not known whether Thompson's group $F$ is amenable, I will establish a lower bound on the F\"{o}lner function for $F$. In particular, I will demonstrate the following: For each generating set, there is a constant $C > 1$ such that if $A$ is a $C^{-n}$-F\"{o}lner set in $F$, then $A$ contains at least $H(n)$ elements, where $H(0) = 0$ and $H(n+1) = 2^{H(n)}$.

In a classical work, Yang and Lee proved that zeros of certain polynomials (partition functions of Ising models) always lie on the unit circle. Distribution of these zeros control phase transitions in the model. We study this distribution for a special ``Migdal-Kadanoff hierarchical lattice''. In this case, it can be described in terms of the dynamics of an explicit rational function in two variables. More specifically, we prove that the renormalization operator is partially hyperbolic and has a unique central foliation. The limiting distribution of Lee-Yang zeros is described by a holonomy invariant measure on this foliation. I will explain both of the above (omitting some details) and describe further questions motivated by our work. This is a joint work with Pavel Bleher and Mikhail Lyubich.

After reviewing the structure of minimal equicontinuous flows, we will discuss equicontinuity for foliated spaces and recent results with Hurder on the structure of special classes of minimal equicontinuous foliated spaces we call matchbox manifolds. These results are closely related to our topological characterization of homogeneous matchbox manifolds that we shall also discuss and relate to the characterization of minimal equicontinuous flows. These results lead to natural conjectures for a more general characterization of compact minimal equicontinuous foliated spaces.

Let $MP_d$ denote the space of affine conjugacy classes of polynomials of degree $d \geq 2$. The shift locus $S_d$, consisting of maps all of whose critical points escape under iteration, has rich topological structure. I will describe some of its features. This is joint ongoing work with Laura DeMarco.

In classification, semi-supervised learning occurs when a large amount of unlabeled data is available with only a small number of labeled data. This imposes a great challenge in that it is difficult to achieve good classification performance through labeled data alone. To leverage unlabeled data for enhancing classification, we introduce a margin based semisupervised learning method within the framework of regularization, based on an efficient margin loss for unlabeled data, which seeks efficient extraction of the information from unlabeled data for estimating the Bayes rule for classification. In particular, I will discuss three aspects: (1) the idea and methodology development; (2) computational tools; (3) a statistical learning theory. Numerical examples will be provided to demonstrate the advantage of our proposed methodology against other competitors. An application to gene function prediction will be discussed.

Understanding and using trigonometric functions is difficult for both students and secondary teachers. These difficulties range from weak understandings of topics foundational to trigonometry (e.g., angle measure and function) to incoherent conceptions of the various contexts in which trigonometry is applied (e.g., the unit circle and right triangles). As an example, students often have difficulty reasoning about trigonometric functions as functions defined on the real numbers. This talk reports results of an investigation into the understandings and reasoning abilities involved in learning ideas of trigonometry. The data was collected in the context of a teaching experiment designed to support precalculus students in developing conceptions of angle measure, images of the radian as a unit of measurement, and connections across the contexts of trigonometry. It was hypothesized that these foundational conceptions constructed by the students would support the students in developing coherent understandings of trigonometric functions. The curriculum also promoted student reasoning abilities (e.g, quantitative and covariational reasoning) and function understandings that are foundational for learning central ideas of calculus. Findings from the investigation revealed information about student understandings of angle measure that are needed to understand and use trigonometric functions. Specifically, the study gained insight to the role of student conceptions of the radian as a unit of measurement when students are asked to reason about angle measure and trigonometric functions. Analysis of the collected data also illuminated the critical role of students' conceptualization of quantities as varying, prior to formalizing an understanding of sine and cosine as functions defining the relationship between two covarying quantities.

While it is not known whether Thompson's group $F$ is amenable, I will establish a lower bound on the cardinality of its Foelner sets. In particular, I will demonstrate the following: There is a constant $C > 1$ such that if $A$ is a $C^{-n}$-Foelner set in $F$, then $A$ contains at least $H(n)$ elements, where $H(0)=0$ and $H(n+1)=2^{H(n)}$.

In this talk, we discuss the asymptotic properties of a semiparametric multiplicative hazard model when the relative risk is expressed as a first order continuously differentiable parametric function. We show that the log- the partial likelihood function of the model is locally concave for an arbitrary continuously differentiable relative risk under suitable conditions. Then we derive the existence and uniqueness of the MPLE and show consistency. Using the convexity lemma and characterization of minimizers, we demonstrate that the MPLE of the parameter is asymptotically normal. As an application, we exhibit that the MPLE of the parameter in a model in which the log- the relative risk is expressed as a free-knot spline with knots in covariates uniquely exists in a neighborhood of the true parameter value and is consistent and asymptotically normal. In particular, we derive the asymptotic normality of the MPLE of the parameter in a model in which the log- relative risk is expressed as a free-knot quadratic spline which has first order continuous derivative.

We use surgery and homotopy theoretic techniques to study the moduli space of complete nonnegatively curved metrics on an open manifold N. A starting point is that the diffeomorphism type of the soul, or more generally, the diffeomorphism type of the pair (N, soul) defines a locally constant function on the moduli space. We focus on the harder case when non-diffeomorphic souls have low codimension. One of the most delicate results is an example of a simply-connected manifold with homeomorphic non-diffeomorphic souls of codimension 2. Previously, examples of homeomorphic non-diffeomorphic closed simply-connected nonnegatively curved manifolds have been only known in dimension 7 thanks to work of Kreck-Stolz, while we construct such examples in each dimension 4r-1 > 10, and realize them as codimension two souls. This is joint work with Slawomir Kwasik and Reinhard Schultz.

We partially generalize the results of Kudla and Rallis on the poles of degenerate, Siegel-parabolic Eisenstein series to residual-data Eisenstein series. In particular, for $a,b$ integers greater than 1, we show that poles of the Eisenstein series induced from the Speh representation on the Levi component of the Siegel parabolic of $\mathrm{Sp}_{2ab}$ are located in a particular "segment" of half integers $X_{b}$ between a "right endpoint" and its negative, inclusive of endpoints. We study the automorphic forms $\Phi_{i}^{(b)}$ obtained as residues at the points $s_i^{(b)}$ (defined precisely in the paper) by calculating their cuspidal exponents in certain cases. In the case of the "endpoint" $s_0^{(b)}$ and `first interior point' $s_1^{(b)}$ in the segment of singularity points, we are able to determine a set containing \textit{all possible} cuspidal exponents of $\Phi_0^{(b)}$ and $\Phi_1^{(b)}$ precisely for all $a$ and $b$. In these cases, we use the result of the calculation to deduce that the residual automorphic forms lie in $L^2(G(k)\backslash G(\mathbf{A}))$. In a more precise sense, our result establishes a relationship between, on the one hand, the actually occurring cuspidal exponents of $\Phi_i^{(b)}$, residues at interior points which lie to the right of the origin, and, on the other hand, the "analytic properties" of the original residual-data Eisenstein series at the origin. If time permits we will discuss further analytic properties such as wave-front sets of the residual automorphic forms, and applications of our calculations.

In 1949 Lars Onsager introduced a variational model describing isotropic-nematic phase transition in liquid crystals. In this model equilibrium states of a liquid-crystalline system correspond to minimizers of a free energy functional. I will review the model and present a complete classification of all critical points of the Onsager functional with Maier-Saupe interaction. Then I will present an extension of Onsager's theory which takes into account spatial variations of nematic ordering and provide a detailed description of vortex-like patterns which appear in a two-dimensional model.

There are two seemingly unrelated classical objects associated to a simplicial complex: a hierarchical model and a Stanley-Reisner ring. A hierarchical model gives rise to a toric ideal, a relationship that is a staple of algebraic statistics. The degrees of generators of this ideal are dubbed "Markov degrees" and encode the complexity of the model. In turn, a Stanley-Reisner ideal is a monomial ideal whose algebraic properties are encoded by the combinatorial properties of the complex. Betti numbers encode ranks of free modules in a minimal free resolution of the Stanley-Reisner ring, a central object in commutative algebra. In this talk, I will introduce all of these concepts, and present a recent result which explores a first connection between Markov degrees of the model and Betti numbers of the Stanley-Reisner ideal. As an application of the main theorem, we recover a result of Froberg which classifies simplicial complexes with linear resolutions. This talk is based on joint work with Erik Stokes, preprint available at arXiv:0910.1610v1

There is a theory which computes arithmetic, is strongly minimal, and all of its models have recursive presentations. We will preview the Hrushovski construction and some ways to alter the construction to code non-recursive information. Then we will use an infinite worker argument to show that with these method we can code the most complicated set possibly coded in a recursive structure, namely the set of true statements in Arithmetic ($0^{\omega}$).

One of the great realizations of twentieth century mathematics was that there is a huge variety of problems out there whose solvability can, and should, be packaged in terms of cohomology groups. The talk will be about cohomology groups that arise when trying to solve certain fundamental analytical problems of complex analysis and geometry. After introducing the central notion of the subject: holomorphic functions, I will pass to the so called Cousin problem, and its significance. I will summarize the works of H. Cartan, Oka, and Serre on the solution of the Cousin problem in finite dimensional spaces. The solution is expressed in terms of cohomology groups. Finally, I will discuss recent developments in infinite dimensions.

Nonlinear Schrödinger equations can be used as a mean-field description of Bose-Einstein condensates. Recent experimental breakthroughs require extensions of the classical Gross-Pitaevskii model to include new physical phenomena. A particularly interesting field concerns condensates in so-called dipolar quantum gases. We review several recent mathematical results on nonlinear Schrödinger equations arising in this context, including existence of solutions, the possibility of finite time-blow-up, and dimension reduction through scaling limits.

In the 1970s S. Shelah gave the following characterization of stable theories: a theory is stable if and only if any indiscernible sequence in a model of the theory is an indiscernible set. I will present a similar characterization of NIP theories, as theories in which any random ordered graph-indiscernible in a model of the theory remains indiscernible strictly with respect to the order. In this talk I will explain what I mean by a random ordered graph-indiscernible and I will indicate how the result is proved using the Nesetril-Rodl theorem. If time permits, I will discuss an additional example of a characterization of stable theories by generalized indiscernibles that generalizes more faithfully on Shelah's.

With no doubt, Thurston's stability theorem is still the most striking rigidity result for group actions. In this talk I will concentrate on its 1-dimensional version, which establishes that the group of C^1 diffeomorphisms of the interval is locally indicable (i.e. every finitely generated subgroup surjects onto Z). I will show by an example that the converse statement does not hold. More precisely, the semidirect product SL(2,Z) \rtimes Z^2, though locally indicable (and finitely generated) does not act faithfully by C^1 diffeomorphisms of neither the real line nor the circle. Several open questions will be addresed.

A new statistical methodology is developed for analysis of spontaneous adverse event reports from post-marketing drug surveillance data. The method involves both empirical Bayes and fully-Bayes estimation of rate multipliers for each drug within a class of drugs, for a particular adverse event, based on a mixed-effects Poisson regression model. Both parametric and semi-parametric models for the random effect distribution are examined. The method is applied to data from FDA`s Adverse Event Reporting System (AERS) on the relationship between antidepressants and suicide. We obtain point estimates and 95% confidence intervals for the rate multiplier for each drug (e.g., antidepressants), which can be used to determine if a particular drug has an increased risk of association with a particular adverse event (e.g., suicide). Confidence intervals that do not include 1.0 provide evidence for either significant protective or harmful associations of the drug and the adverse effect. We also examine empirical Bayes, parametric Bayes and semi-parametric Bayes estimators of the rate multipliers and associated confidence intervals. Results of our analysis of the FDA AERS data revealed that newer antidepressants are associated with lower rates of suicide. This finding contradicts previous findings of FDA that newer antidepressants are causally related to increased suicidal thinking in children and young adults. Finally, we suggest changes in the AERS system to improve our ability to discover these adverse events.

I will talk about a certain combination of complex-analytic and arithmetic tools which can be used to study one-dimensional complex dynamical systems. In the setting of quadratic polynomials $z^2 + c$, the result is: the set of parameters $c$ for which two given complex numbers $a$ and $b$ are both preperiodic is infinite iff $a^2 = b^2$. This is a dynamical analog of recent results of Masser and Zannier concerning simultaneous torsion sections on families of elliptic curves. This is joint work with Matt Baker.