Friday, October 7, 2005
1:30 pm Posner Hall 151
Miguel Lejeune
Visiting Assistant Professor, Tepper School of Business
Derivation of Country Risk Rating Systems Using Logical Analysis of Data
In order to evaluate the creditworthiness of countries, a learning model is induced from Standard & Poors country risk ratings. The learning model is obtained using the combinatoriallogical technique of Logical Analysis (LAD), and allows the construction of a partially ordered set describing the relative superiority of countries on the basis of their creditworthiness. It is shown that the Condorcet linear extensions of this poset match closely S&Ps ratings. The rating system derived from the model is transparent, self-contained, provides stable country risk rating systems, and correlate highly with the ratings of other rating agencies. The model is shown to provide excellent ratings even when applied to the following years data or to the ratings of previously unrated countries. Rating changes implemented by S&P in subsequent years resolved most discrepancies between the constructed poset and S&Ps initial ratings.
Speaker: Lea Kissner
Time: Wednesday 12-1pm
Place: NSH 1507
Title: Privacy-Preserving Set Operations
Abstract:
In many important applications, a collection of mutually distrustful parties must perform private computation over multisets. Each party’s input to the function is his private input multiset. In order to protect these private sets, the players perform privacy-preserving computation; that is, no party learns more information about other parties’ private input sets than what can be deduced from the result. In this talk, we propose efficient techniques for privacy-preserving operations on multisets. By building a framework of multiset operations, employing the mathematical properties of polynomials, we design efficient, secure, and composable methods to enable privacy-preserving computation of the union, intersection, and element reduction operations. We apply these techniques to a wide range of practical problems, achieving more efficient results than those of
previous work.
Near linear time solution of elliptic PDE’s using support-graph preconditioners
Steve Vavasis, Department of Computer Science, Cornell University
October 7th 2005, 3:30PM, Wean 7220
Abstract
Support-graph preconditioners were first proposed by Vaidya in 1991. They are a graph-based method for fast solution of a certain kinds of linear equations. The basic idea was extended and generalized by various groups including Gremban, Miller and Zagha; Boman and Hendrickson; Bern et al.; and most recently Spielman and Teng. A limitation of almost all of this previous work is that provable bounds on the running time of the various methods have been available only in the case that the matrix is diagonally dominant, which is a fairly restricted class of linear systems.
We show how to extend this previous work to linear systems arising from finite element analysis of elliptic boundary value problems. Our technique, in combination with the recent results of Spielman and Teng, establishes that these linear systems can be solved in nearly linear time. Other fast methods, notably multigrid, are also available for these problems. In comparison with multigrid, our method imposes more stringent restrictions on the class of differential equations but fewer restrictions on the mesh, geometry, and variation of the coefficient fields.
This talk represents joint work with Erik Boman and Bruce Hendrickson.
TITLE: The game chromatic number of random graphs
SPEAKER: Alan Frieze
WHEN: Thursday, October 6, 4:00pm-5:30pm
WHERE: 300 PPB
ABSTACT: Two players take turns in coloring the vertices of a graph G with k colors. They are constrained so that the partial coloring is always proper, i.e., neighboring vertices get different colors. In one version of this game, the two players are called Maker and Breaker. Maker wins if all the vertices of G are eventually colored. Breaker wins if at some stage the current partial coloring cannot be extended to a complete coloring of G, i.e., if at some stage there is an uncolored vertex such that each of the k colors appears at least once in its neighbourhood.
Our results will not be sensitive to who gets first and so let us assume that Maker goes first. The Game Chromatic Number is the minimum k for which Maker has a winning strategy. This parameter was introduced by Bodlaender and we discuss its size in the context of random graphs.
This is joint work with Tom Bohman and Benny Sudakov.
