Colloquiums and Public Lectures 2011
Title: | An Investment Model via Regime-Switching Economic Indicators |
Speaker: | Professor Yonggan Zhao |
Date: | 15 December 2011 |
Time: | 4.30pm - 5.30pm |
Venue: | SPMS LT3 (SPMS-03-02) |
Abstract: | 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. |
Title: | Managing Interference |
Speaker: | Professor Robert Calderbank |
Date: | 1 December 2011 |
Time: | 11.00am - 12.00pm |
Venue: | SPMS LT3 (SPMS-03-02) |
Abstract: | 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. |
Title: | Covering a Graph by Subgraphs |
Speaker: | Professor Fan Genghua |
Date: | 28 October 2011 |
Time: | 11.00am - 12.00pm |
Venue: | SPMS LT3 (SPMS-03-02) |
Abstract: | 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. |
Title: | Visualizing R^n and some new dualities |
Speaker: | Professor Alfred Inselberg |
Date: | 27 October 2011 |
Time: | 4.30pm - 5.30pm |
Venue: | SPMS LT2 (SPMS-03-03) |
Abstract: | With parallel coordinates the perceptual barrier imposed by our 3-dimensional habitation is breached enabling the visualization of multidimensional problems. The highlights, interlaced with interactive demonstrations, are intuitively developed showing how M-dimensional objects are recognized recursively from their (M − 1)-dimensional subsets. It emerges that a hyperplane in N-dimensions is represented by (N − 1) indexed points. Points representing lines have two indices, those representing planes in R ^{3} have three indices and so on. In turn, this yields powerful geometrical algorithms (e.g. for intersections, containment, proximities) and applications including classification. A smooth surface in 3-D is the envelope of its tangent planes each represented by 2 planar points. As a result it is represented by two planar regions, and a hypersurface in N-dimensions by (N − 1) regions. This is equivalent to representing a surface by its normal vectors. Developable surfaces are represented by curves revealing the surface characteristics. Convex surfaces in any dimension are recognized by hyperbola-like regions. Non-orientable surfaces yield stunning patterns unlocking new geometrical insights. Non-convexities like folds, bumps, concavities are visible. The patterns persist in the presence of errors. Intuition gained from the R^{ 3} representations leads to generalizations for R ^{N} with beautiful new dualities like cusp in R^{ N} ↔ (N −1) “swirls” in R ^{2} , “twist” in R ^{N} ↔ (N −1) cusps in R ^{2} . The methodology extends to spaces of dimension ℵ0 and ℵ1. |
Title: | Applied computability theory and effective randomness |
Speaker: | Professor Ng Keng Meng |
Date: | 20 October 2011 |
Time: | 4.30pm - 5.30pm |
Venue: | SPMS LT3 (SPMS-03-02) |
Abstract: | 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. |
Title: | Circuit Complexity meets the Theory of Randomness |
Speaker: | Professor Eric Allender |
Date: | 6 October 2011 |
Time: | 4.30pm - 5.30pm |
Venue: | SPMS LT3 (SPMS-03-02) |
Abstract: | 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. |
Title: | Weighing In On Interior-Point Method |
Speaker: | Professor Chua Chek Beng |
Date: | 22 September 2011 |
Time: | 4.30pm - 5.30pm |
Venue: | SPMS LT3 (SPMS-03-02) |
Abstract: | 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. |
Title: | Tiling Space by Translates of a Convex Body, with Multiplicity |
Speaker: | Professor Sinai Robins |
Date: | 15 September 2011 |
Time: | 4.30pm - 5.30pm |
Venue: | SPMS LT3 (SPMS-03-02) |
Abstract: | 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. |
Title: | The Mathematics of Multi-A(ge)nt Interactions |
Speaker: | Professor Alfred M. Bruckstein |
Date: | 8 September 2011 |
Time: | 4.30pm - 5.30pm |
Venue: | SPMS LT3 (SPMS-03-02) |
Abstract: | 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. |
Title: | From Short Cuts to Crazy Cuts |
Speaker: | Professor Alfred M. Bruckstein |
Date: | 25 August 2011 |
Time: | 4.30pm - 5.30pm |
Venue: | SPMS LT3 (SPMS-03-02) |
Abstract: | 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”. |
Title: | Some Flavours of Games in Computation |
Speaker: | Professor Luke Ong |
Date: | 24 August 2011 |
Time: | 4.30pm - 5.30pm |
Venue: | SPMS LT4 (SPMS-03-09) |
Abstract: | 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. |
Title: | List Error-Correction Algorithms: A Survey |
Speaker: | Professor Venkatesan Guruswami |
Date: | 18 August 2011 |
Time: | 4.30pm - 5.30pm |
Venue: | SPMS LT3 (SPMS-03-02) |
Abstract: | 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. |
Title: | Algorithms, Randomness and Networks: Confluence and Applications |
Speaker: | Professor Aravind Srinivasan |
Date: | 17 August 2011 |
Time: | 3.30pm - 4.30pm |
Venue: | SPMS LT4 (SPMS-03-09) |
Abstract: | 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. |
Title: | Modularity in Protein Networks |
Speaker: | Professor Richard M. Karp |
Date: | 11 August 2011 |
Time: | 4.30pm - 5.30pm |
Venue: | SPMS LT3 (SPMS-03-02) |
Abstract: | 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. |
Title: | Effective Heuristics for NP-Hard Problems |
Speaker: | Professor Richard M. Karp |
Date: | 5 August 2011 |
Time: | 3.00pm - 4.00pm |
Venue: | SPMS LT1 (SPMS-04-07) |
Abstract: | 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. |
Title: | Relational Join Using Map-Reduce |
Speaker: | Professor Jeffrey Ullman |
Date: | 19 May 2011 |
Time: | 4.30pm - 5.30pm |
Venue: | SPMS LT5 (SPMS-03-08) |
Abstract: | 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). |
Title: | Links and Homotopy Groups |
Speaker: | Professor Jie Wu |
Date: | 28 April 2011 |
Time: | 4.30pm - 5.30pm |
Venue: | SPMS LT5 (SPMS-03-08) |
Abstract: | 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. |
Title: | Class Invariants |
Speaker: | Professor Chan Heng Huat |
Date: | 21 April 2011 |
Time: | 4.30pm - 5.30pm |
Venue: | SPMS LT5 (SPMS-03-08) |
Abstract: | 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. |
Title: | Automatic Sequences and Transcendence of Real Numbers |
Speaker: | Associate Professor Wu Guohua |
Date: | 14 April 2011 |
Time: | 4.30pm - 5.30pm |
Venue: | SPMS LT5 (SPMS-03-08) |
Abstract: | 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. |
Title: | Bases in a Vector Space, Information sets for a Linear Code and the Reed-Solomon Codes |
Speaker: | Professor Aiden A. Bruen |
Date: | 24 March 2011 |
Time: | 4.30pm - 5.30pm |
Venue: | SPMS LT5 (SPMS-03-08) |
Abstract: | Undergraduates in science and engineering devote considerable effort
to algorithms for various reductions of matrices such as row reduction of a
matrix G, Gaussian reduction and so on. Suppose G has rank k and is of size
k ×n. Then, necessarily, n is at least k. This is because of the fundamental fact
that, for all matrices, row rank equals column rank. It follows that there exists
at least one set of n linearly independent columns in G. Essentially, reduction
works because of this.
More abstractly, suppose we have a spanning set S of n vectors in a k-dimensional
vector space V = V (n, F) - such as the columns of G. Here, F is any field
whatsoever, finite or infinite. By definition S contains at least one basis. One
suspects that the bigger that n is, the larger the number of bases contained in
S. • Can this be quantified? • Does the number of bases depend on F? • Can it happen that EACH of the n k subsets of S form a basis of V ? In the event that G is the generator matrix for a linear [n, k] code C over some finite field F, the bases of the column space correspond precisely to the information sets in C. The answer to the third question above then relates to the main block codes used in industry, i.e., the Reed-Solomon codes. In this lecture the answer to each of the questions above will be revealed and discussed. It appears that some of the methods in the proof can be generalized to matroids, thereby yielding analogous results for graphs and other structures. This research is being pursued with Peter Cameron. |
Title: | Algorithmic Aspects of Stability in Weighted Voting Games |
Speaker: | Assistant Professor Edith Elkind |
Date: | 11 March 2011 |
Time: | 4.30pm - 5.30pm |
Venue: | SPMS LT5 (SPMS-03-08) |
Abstract: | 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. |
Title: | To Search for the best. Optimization in Real and Discrete Variables |
Speaker: | Professor Christer Kiselman |
Date: | 24 February 2011 |
Time: | 4.30pm - 5.30pm |
Venue: | SPMS LT4 (SPMS-03-09) |
Abstract: | 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. |
Title: | Ramanujan's Lost Notebook |
Speaker: | Professor Bruce Berndt |
Date: | 24 February 2011 |
Time: | 3.30pm - 4.30pm |
Venue: | SPMS LT5 (SPMS-03-08) |
Abstract: | 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. |
Title: | A Formula for the HOMFLY Polynomial of Rational Links |
Speaker: | Professor Sergei Duzhin |
Date: | 17 February 2011 |
Time: | 4.30pm - 5.30pm |
Venue: | SPMS LT5 (SPMS-03-08) |
Abstract: | 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). |
Title: | Polyhedral Cones, their Theta Functions, and their Solid Angles |
Speaker: | Professor Sinai Robins |
Date: | 10 February 2011 |
Time: | 4.30pm - 5.30pm |
Venue: | SPMS LT5 (SPMS-03-08) |
Abstract: | 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. |