Colloquiums and Public Lectures 2011

The Internet bubble and 2008-2009 economic crash exposed severe limitations of traditional portfolio models, especially the dependence on a static framework, e.g., a constant covariance matrix. This paper develops a novel dynamic optimization model for constructing a long-short equity portfolio. Asset returns are characterized by a set of eight economic factors that follow a regime-switching autoregressive model.

 

In the empirical analysis, we employ exchange traded funds to test the approach. Common factors include: changes in the S&P 500 price index, treasury bond index, the U.S. dollar index, implied volatility, aggregate dividend yield, short term interest rate, treasury yield spread, and credit spread. The optimal portfolio is subject to the various policy constraints on leverage, individual positions, and Value at Risk. The portfolio exposure to each of the risk factors is controlled by the level of risk aversion. The empirical tests show that the developed investment portfolio provides much higher returns with very limited risk, in contrast with alternative investment approaches, for the period of January 1999 to November 2010.

We consider a framework for full-duplex communication in ad-hoc wireless networks recently proposed by Dongning Guo. An individual node in the wireless network either transmits or it listens to transmissions from other nodes but it cannot to both at the same time. There might be as many nodes as there are 48 bit MAC addresses but we assume that only a small subset of nodes contribute to the superposition received at any given node in the network.

We use ideas from compressed sensing to show that simultaneous communication is possible across the entire network. Our approach is to manage interference through configuration rather than to eliminate or align it through extensive exchange of fine-grained Channel State Information.
Our approach to configuration makes use of old fashioned coding theory.

A graph G is covered by a set of its subgraphs if each edge of G is contained in at least one of the subgraphs. An equivalent version of the Four-Color-Theorem is that every bridgeless planar graph can be covered by two even subgraphs (even graph: union of edge-disjoint circuits). The 8-Flow Theorem is equivalent to the covering of three even subgraphs. In this talk, we mainly consider the cases where the subgraphs are matchings, paths, or circuits.

Given an infinite binary string, how do we measure the computational content of the string? The two popular approaches are computability theory and algorithmic randomness. Computability theory is devoted to measuring the complexity of an infinite string by using formalized models of computation. Effective randomness calibrates complexity by defining when an infinite binary string can occur by chance. I will talk about the different ways in which one can take to measure computability and randomness, and discuss some of the recent development in this area. This talk will be accessible to the general audience.

In the past decade, there has been remarkable progress in a field known as "derandomization" - leading to a situation where most experts  now believe that any probabilistic algorithm can be replaced by a deterministic algorithm with comparable complexity.  The tools and techniques of derandomization have also opened new connections between two fields that had previously seemed to have little connection to each other: 1. the field of circuit complexity (in which we try to find the most efficient circuitry to compute a given Boolean function), and 2. the field of algorithmic information theory (aka "Kolmogorov Complexity"), which provides a mathematical definition of "randomness".
This lecture will introduce the listeners to these two fields, and show how the study of derandomization has opened links that have enriched each field.

Built on the theory of Newton's method and the notion of analytical centres, the modern interior-point method is a class of wildly successful algorithms for solving linear optimization problems; and it played an instrumental part in the flourish of semidefinite optimization. While most of the interior-point theory for linear optimization has been extended to deal with semidefinite optimization, and a significant portion of it to convex optimization in general, there remain various segments of the theory that do not have satisfactory extensions beyond linear optimization. One of them is the concept of target following, which is closely related to the notion of weighted analytic centres. In this talk, I will give a concise introduction to this concept of target following, and present recent findings towards the extension of this concept to semidefinite programming.

We review some of the history of tilings of space by translations, and generalize this theory to include the problem of covering by overlapping translates of a convex body , such that almost every point of is covered exactly times, for a fixed integer . Such a covering of Euclidean space by translations is called a -tiling. The traditional investigation of tilings (i.e. 1-tilings in this context) by translations began with the work of Fedorov and Minkowski. Here we extend the investigations of Fedorov and Minkowski to tilings by proving that if a convex body -tiles by translations, then it is centrally symmetric, and its facets are also centrally symmetric. The methods are very new, and they allow us to prove analogues of Minkowski’s conditions for 1-tiling polytopes. Conversely, in the case that is a rational polytope, we also prove that if is centrally symmetric and has centrally symmetric facets, then  must -tile for some positive integer .

This is joint work with Nick Gravin and Dmitry Shiryaev.

This talk will survey mathematical methods used for addressing the analysis of emergent collective behaviors in swarms comprised of many simple, mobile, myopic (i.e. locally sensing), mute (i.e. implicitly communicating) and senile (i.e. memoryless) ant-like agents.

This talk discusses two problems in planar geometry, involving cutting a planar shape into two parts. The first problem is related to the popular “Slice-It” AppGame available for smart phones, while the second led to the recent development of a very cute and challenging AppGame called “Magic-Cuts”.

The idea of games is central to many branches of computer science. In this talk, I will survey two flavours of games in computation which have been influenced by the long tradition of games in logic. In semantics of computation, games form a highly-structured mathematical universe; they give rise to accurate, compositional models for a wide range of programming languages. In verification, games provide an algorithmic foundation for the design, verification and synthesis of reactive systems.

The construction of error-correcting codes that achieve the best possible trade-off between information rate and the amount of errors that can be corrected has been a long sought-after goal. In this talk, I will survey some of our work on list decoding, culminating in the construction of codes with the optimal rate for any  desired error-correction  radius.  I  will  describe  these  codes  (called  folded  Reed-  Solomon  codes),  and  give  a  peek  into  the ideas  underlying  their  error-correction.  These  list  decoding  algorithms  correct  a  factor  of  two  more  errors compared  to  the  conventional  algorithms  currently  used  in  several  storage  and  communication  applications.

 

List  decodable  codes  have  also  found  several  applications  extraneous  to  coding  theory,  in  algorithms, complexity theory, and cryptography. Time permitting, I will mention some of these, highlighting a construction of graphs with good expansion properties.

We will discuss the role of algorithms and probabilistic methods in combinatorial optimization and public health, with an emphasis on networked phenomena. This includes recent and ongoing research on the Lovasz Local Lemma, the role of networked phenomena in public-health preparedness, and algorithmic issues in wireless networking. Our goal is to articulate the power of algorithms, probabilistic methods, and networked phenomena in scientific, technological, and societal applications.

In the protein-protein interaction (PPI) network of a species, thevertices are the proteins of the species and two proteins are joined by an edge if there is evidence of physical interaction between them. A set of proteins that interact strongly among themselves and weakly with other proteins is called a module. The proteins that are involved in a common cellular function often comprise a module. Proteins in two species are orthologous if they hav evolved from a common ancestral protein.

 

Modules in two species are conserved if the proteins in each module are orthologous to proteins in the other. Conserved modules often correspond to functioning cellular machinery that has survived in evolution. We present algorithms and software devised by Luqman Hodgkinson and the speaker for finding conserved modules.

 

We then introduce the following Colorful Subgraph Problem, which arises in the search for conserved protein modules: given a graph in which each vertex is assigned a color from a set S, find the smallest connected subgraph containing at least one vertex of each color in S. Here the vertices correspond to proteins, and the colors to types of proteins. We present a succesful algorithm for this problem devised by Shao Li and the speaker. In passing, we note that the Colorful Subgraph Problem is a source of entertaining combinatorial puzzles.

In many practical situations heuristic algorithms reliably give satisfactory solutions to real-life instances of optimization problems, despite evidence from computational complexity theory that the problems are intractable in general. Our long-term goal is to contribute to an understanding of this seeming contradiction, and to put the construction of heuristic algorithms on a firmer footing.

 

As a step in this direction we describe the evolution of a successful heuristic algorithm by Erick Moreno Centeno and the speaker for the following Global Genome Alignment problem: given the genomes of several species, an anchor pair is a pair of substrings from two different genomes which appear to be descended from a common ancestral sequence. Given a collection of anchor pairs, construct a multiple alignment maximizing the number of anchor pairs that are aligned against each other. Such an alignment exhibits the common evolutionary ancestry of the set of species.

 

We then use the Global Genome Alignment problem to illustrate a general approach for tuning the parameters and design choices within a given heuristic algorithmic strategy, assuming the availability of a training set of typical problem instances.

Finally, as time allows, we sketch successful heuristic algorithms for further problems arising in systems biology and statistical genetics

**Note: This is a Distinguished Lecture, hosted by NTU-Rice Institute for Sustainable and Applied Infodynamics and School of Physical Mathematical Sciences in cooperation with the College of Engineering.

We introduce the environment of map-reduce systems like Hadoop, including distributed file systems and SQL-like systems built on top of Hadoop. There is a simple algorithm for implementing the usual 2-way join in map-reduce, which we shall review. Then we consider the problem of joining more than two relations in one map-reduce round. We see that there is a nonlinear optimization problem that must be solved to do the task most efficiently. Sometimes the multiway join is in fact more efficient than a cascade of 2-way joins, although in many cases it is not. We then concentrate on one important case where the multiway join, properly implemented, is always a win: the case of star joins (analytic queries).

Consider the following two questions: 

(1) Let L be a link consisting of n rubber rings such that any nonempty sublink of L is NOT splittable, namely that cannot be separated by a plane. Question 1:  Determine the extra loops (extra rope) l going around L such that l is linked with L but l becomes unlinked from L if any one of the rubber rings is removed.

(2) Hold two separate trivial metal rings on a tree. Let L be any (n+2)-link by adding n link components rubber rings with each of them going around the both rings on the tree. Question 2: Determine the extra loops (extra rope) going around the link L which would drop down to the ground by removing any one of the rubber rings.

In this talk, we will reformulate the above two questions into mathematical questions. Then we will give a surprising answer to these questions given in terms of homotopy groups. The talk aims to general audience and so we will explain relevant concepts such as link groups and homotopy groups.

Let K = Q((d)^(1/2)) with d<0 and squarefree. Let C(K) be its corresponding class group.  It is known via the Artin map that there is a maximal unramified abelian extension H (called the Hilbert class field of K) with the property that the galois group Gal(H|K) is isomorphic to C(K). It is well known that the modular j-invariant evaluated at w where w= d^(1/2) or (3+d^(1/2))/2 can be used to generate H over K. Besides these values, there are other special values of modular functions (for example, the Weber functions) that serve the same purpose. We define a class invariant to be a special value of  modular function (not necessarily j-invariant) that generates H over K.

In this talk, we will discuss some properties and applications of these class invariants.

In this talk, I will first review some basics of automatic sequences, and then introduce the transcendence properties of automatic sequences. Especially, I will introduce Cobham Theorem and Mahler's work.

Weighted voting games are a simple, but expressive class of coalitional games that can be used to model decision-making in political bodies as well as collaboration in multi-agent systems. In such settings, stability of the grand coalition is an important consideration: the gains from the collaboration should be distributed in such a way that the agents' incentives to deviate from the grand coalition are minimized. In this talk, we will discuss the computational complexity of several stability-related solution concepts in weighted voting games, such as the epsilon-core, the least core and the nucleolus. While computing many of these solution concepts appears to be hard, we will describe recent pseudopolynomial and approximation algorithms that mitigate the hardness results. The algorithms rely on constructing separation oracles for a sequence of linear programs; we hope that they will be applicable to other classes of cooperative games.

Based on joint work with Leslie Ann Goldberg, Paul Goldberg, Michael Wooldridge (U of Liverpool) and Dmitrii Pasechnik.

To optimize means to search for the best. But what is best? Is it the highest prize or the lowest prize? The next question is: Best of what? That is to say: Which are the possible values or states that can appear? And here there is a great difference with respect to results as well as to methods depending upon whether we work with real variables or integer variables. This difference is something that I will describe.

Three important properties in convexity theory of real variables are:
· A local minimum of a convex function is global;
· The marginal function of a convex function is convex;
· Between two disjoint convex sets there exists a separating hyperplane.

All three fail in a spectacular way when we pass to integer variables and try to use a natural (naive) definition of convexity. So it is of interest to find new classes of functions for which these properties hold.

In the spring of 1976, while searching through papers of the late G. N. Watson at Trinity College, Cambridge, George Andrews found a sheaf of 138 pages in the handwriting of Srinivasa Ramanujan, generally regarded as India's greatest mathematician. In view of the fame of Ramanujan's earlier notebooks, Andrews naturally called these papers Ramanujan's "lost notebook." This work, comprising about 650 results with no proofs, arises from the last year of Ramanujan's life and represents some of his deepest work.

First, we provide a history of the lost notebook. Second, a general description of the topics found in the lost notebook will be provided. For some of the topics, in particular, q-series, theta functions, mock theta functions, continued fractions, partitions, and infinite series, we offer some details. In the time remaining, the third portion of the lecture will be devoted to a more detailed discussion of one of the topics prominently addressed in the lost notebook, namely continued fractions.

The HOMFLY polynomial is an important invariant of knots and links in 3-space invented in late 1980's. It is defined recursively, and no closed form expression for it is known in case of an arbitrary knot or link. Rational (or 2-bridge) links constitute an important class of links (in particular, knots) which is well studied from varius viewpoints. In this talk, we will give an explicit formula for the HOMFLY polynomial of a rational link in terms of a special continued fraction for the rational number that defines the given link. The talk is based on a joint paper of the speaker and M.Shkolnikov (arXiv:1000.1800).

We introduce some basic concepts of polyhedral geometry, the combinatorics of polytopes, and their solid angles.  We find new relations between the vertex solid angles of any rational polytope.  These relations involve some elementary d-dimensional finite Gauss sums, and they generalize the well-known geometric relations between solid angles of the faces of a polytope, known as the Gram relations.

We motivate the theory by noting that the Gram relations are a d-dimensional generalization of the familiar geometry theorem for triangles, namely that the angles of a triangle add up to 180 degrees.  We introduce new methods here, which involve certain polyhedral theta functions, also defined from scratch and motivated by the relevant geometry.