Colloquiums and Public Lectures 2010

Title:	Internet Ad Auctions: Algorithms and Directions
Speaker:	Professor S. Muthukrishnan
Date:	15 September 2010
Time:	4.00pm - 5.00pm
Venue:	SPMS - LT4, SPMS-03-09
Abstract:	For over 5 years, internet companies have been selling ads via auctions and have enabled a fascinating market comprising millions of users and advertisers. This ad auctions market presents an unique opportunity to test and refine economic principles as applied to a very large number of interacting, dynamic, self-interested parties with myraid objectives; researchers in Economics, Computer Science, Game Theory, Marketing and Business Sciences are increasingly involved in defining, understanding and influencing it. This talk will be an overview of the underlying algorithmic and economic problems in internet ad auctions, and future directions. For material relevant to this talk: http://algo.research.googlepages.com/home

Title:	The Limiting Curve of Jarník's Polygons
Speaker:	Professor Greg Martin
Date:	30 July 2010
Time:	2.00pm - 3.00pm
Venue:	MAS Executive Classroom 1, SPMS-03-06
Abstract:	In 1925, Jarník defined a sequence of polygons for use in constructing strictly convex curves containing many lattice points. Properly scaled, these polygons converge to a certain limiting curve. In this talk we identify this limiting curve precisely, showing that it consists piecewise of arcs of parabolas. We describe a surprising connection between this limiting curve and a "random convex lattice polygon" theorem of Vershik. We also show that the local curvatures of Jarník's polygons fail to converge to the local curvature of the limiting curve; in fact, the manner in which the local curvatures oscillate depends on the Diophantine approximation properties of the parameter that identifies the locale. If time permits, we will discuss sequences of polygons arising from generalizations of Jarník's construction.

Title:	High Performance Computational Models of Multi-theory Multi-level Complex Networks: Epidemics in Social and Wireless Networks
Speaker:	Professor Madhav Marathe
Date:	6 April 2010
Time:	3.30pm - 4.30pm
Venue:	SPMS-Lecture Theatre 4, SPMS-03-09
Abstract:	Complex Networks are pervasive in our society. Realistic biological, information, social and technical networks share a number of unique features that distinguish them from physical networks. Examples of such features include: irregularity, time-varying structure, heterogeneity among individual components and selfish/cooperative game-like behavior by individual components. Furthermore, the network structure, the dynamical process on the network and the behavior of constituent agents co-evolve over time. The size and heterogeneity of these networks, their co-evolving nature and the technical difficulties in applying dimension reduction techniques commonly used to analyze physical systems makes reasoning, prediction and controlling of these networks even more challenging. Recent quantitative changes in high performance and wireless computing capability have created new opportunities for collecting, integrating, analyzing and accessing information related to such large complex networks. The advances in network and information science that build on this new capability provide entirely new ways for reasoning and controlling these networks. Together, they enhance our ability to formulate, analyze and realize novel public policies pertaining to these complex networks. The talk will focus on elements of network and information science required to support policy informatics as it pertains to epidemic processes in social and wireless networks. Understanding these epidemiological processes is of immense societal importance. Additionally, they serve as excellent "model organisms" for developing a theory of co-evolving complex networks. Perhaps more intriguing, recent advances in wireless communications provide compelling reasons for studying these networks together. I will discuss this possibility in my concluding remarks.

Title:	From Philosophical to Industrial Logics
Speaker:	Professor Moshe Y. Vardi
Date:	26 January 2010
Time:	10.30am - 11.30am
Venue:	SPMS-Lecture Theatre 5, SPMS-03-08
Abstract:	One of the surprising developments in the area of program verification is how several ideas introduced by logicians in the first part of the 20th century ended up yielding at the start of the 21st century industry-standard property-specification languages called PSL and SVA. This development was enabled by the equally unlikely transformation of the mathematical machinery of automata on infinite words, introduced in the early 1960s for second-order arithmetics, into effective algorithms for industrial model-checking tools. This talk attempts to trace the tangled threads of this development.

Title:	Heuristic Algorithms in Molecular Biology and Genetics
Speaker:	Professor Richard M. Karp
Date:	25 January 2010
Time:	3.30pm - 4.30pm
Venue:	SPMS-Lecture Theatre 5, SPMS-03-08
Abstract:	Advances in instrumentation and information technology have enabled the acquisition of large bodies of data about the content of genomes, the properties and functions of proteins, and the interactions among genes, RNA molecules and proteins within living cells. New algorithmic methods are required for processing these rich data sources in order to understand the regulation of fundamental life processes at the cellular level and analyze the causal relationships between genetic variation and disease. Because regulatory mechanisms are often conserved in the course of evolution, they are best studied through comparative analysis across several species. This analysis leads to combinatorial problems of aligning the genomes of several species to reveal conserved genes and regulatory regions, and aligning the protein-protein interaction networks of several species to reveal protein modules linked by pairs of functionally orthologous proteins. Such alignments can enhance the understanding of each individual organism through the lens of its relationship with other organisms. The resulting combinatorial optimization problems are NP-hard and must be attacked by heuristic algorithms. We shall present some of these algorithms and describe the methodology of constructing them.

Title:	Fast Transforms : Banded Matrices with Banded Inverses
Speaker:	Professor Gilbert Strang
Date:	20 January 2010
Time:	10.30am – 11.30am
Venue:	SPMS Lecture Theatre 2, SPMS-03-03
Abstract:	Good transforms give useful decorrelation of the data - but they must be fast too! The success of the wavelet transform depends on the property that its inverse also involves finite length filters. *So the transform and its inverse are both represented by banded matrices*. We provide a factorization for these matrices and many extensions - including time-varying filters and also recurrences that arise in the theory of orthogonal polynomials.