[Colloquium] Guest Speakers @ TTI-C Next Week (2/20-2/24)

[Katherine Cumming]

**********TTI-C Guest Speakers (4) Next Week***********
                      February 20 - February 24, 2006
Presented by:  Toyota Technological Institute at Chicago
 
 
(1)
 
Speaker: Nir Ailon, Princeton University
Speaker's home page: http://www.cs.princeton.edu/~nailon/
 
Date: Tuesday, February 21, 2006 
Location: TTI-C Conference Room
Time:  10:00 am
 
Title:
 
New Algorithms for High-Dimensional, Inconsistent Datasets
 
Abstract:
 
(1) The problem of Rank Aggregation is that of combining inconsistent
rankings of some base set suggested by different voters.  This problem was
originally studied in the 18th century in the context of social choice and
has recently attracted the attention of computer scientists in surprising
new contexts.
 
I will present new algorithms improving on the previously best known.  En
route, I will discuss the related graph-theoretic problem of Minimum
Feedback Arc-Set in Tournaments.  I will also discuss related results and
follow-up work on cluster aggregation, hierarchical clustering and
phylogeny.
 
(2) Dimension reduction is one of the most important tools in algorithms for
large datasets.  The known (linear) dimension reduction techniques require
multiplying the data points by a dense matrix.  I will show the surprising
fact that using the Fourier transform it is possible to obtain a significant
speedup of this computation.  This idea is inspired by the Heisenberg
uncertainty principle from physics.
 
Time permitting; I will briefly touch upon other areas I am working in.
 
(2)
 
Speaker:  Atsushi Ohori, Research Institute of Electrical Communication,
Tohoku University
Speaker's home page:  <http://www.pllab.riec.tohoku.ac.jp/~ohori/index.html>
http://www.pllab.riec.tohoku.ac.jp/~ohori/index.html
 
Date: Wednesday, February 22, 2006 
Location:  Ryerson 251
Time:  2:30 pm
 
Title:
 
Development of the SML# Compiler
 
Abstract:
 
SML# is a new programming language in the ML family being developed at RIEC,
Tohoku University.  Its main features include the following.
 
* Interoperability.
In SML#, standard data structures including integers, floating point data,
records and arrays have their natural representations.  The bit-map
inspecting GC of SML# is compatible with that of Java.  These make SML#
highly interoperable.  An SML# code, for example, can load a C FFT function
and pass a "real array" (created in an SML# heap) to the C function as an
array of unboxed double-word floats without any data conversion. 
 
* Record polymorphism.
SML# fully support polymorphic record operations, for which the SML#
compiler generates efficient code.
 
* It is a full fledged functional language extending Standard ML.
The programmer can enjoy the above new features with the usual benefits of
SML such as interactive programming using existing collection of SML library
modules.
 
In this talk, I will outline the features of SM#, the SML# compiler and
programming tools, and describe the theory and implementation methods
underlying the compiler. 
 
This is a joint project with Sanpu-Koubou inc., and Japan Advanced Institute
of Science and Technology.  The project has been supported by the Japanese
MEXT (Ministry of Education, Culture, Sports, Science and Technologies)
e-Society project.
 
 
(3)
 
Speaker:  Elad Hazan, Princeton University
Speaker's home page:  <http://www.cs.princeton.edu/~ehazan/>
http://www.cs.princeton.edu/~ehazan/
 
Date: Thursday, February 23, 2006 
Location: TTI-C Conference Room
Time:  10:00 am
 
Title:
 
New Techniques in Online Convex Optimization and their Applications
 
 
Abstract:
 
In the first part of the talk we introduce a new algorithm and a new
analysis technique that is applicable to a variety of online optimization
scenarios, including regret minimization for Lipschitz regret functions
studied by Hannan, universal portfolios by Cover, Kalai and Vempala, online
convex optimization by Zinkevich, and others.  The algorithm extends a
method proposed by Hannan in the 1950's, called `Follow the Leader", and
shows a surprising connection to the Newton method for offline optimization.
One application from computational finance is for portfolio management, for
which our algorithm combines optimal regret with computational efficiency.
For more general settings, our algorithm is the first to achieve optimal
regret.
 
Time permitting; in the second part of the talk we survey the applications
of online game playing algorithms for obtaining efficient offline
optimization algorithms. 
 
 
(4)
 
Speaker: Santosh Vempala, MIT
Speaker's home page:  <http://www-math.mit.edu/~vempala/>
http://www-math.mit.edu/~vempala/
 
Date: Friday, February 24, 2006 
Location: TTI-C Conference Room
Time:  10:00 am
 
Title:  
 
Dispersion of Mass and the Complexity of Randomized Algorithms
 
Abstract:
 
How much can randomness help computation?  Motivated by this question, we
analyze a notion of dispersion and connect it to asymptotic convex geometry.
Two of the most appealing conjectures in the latter field are (i) slicing
(or isotropic constant) and (ii) variance.  Together they imply that for a
random point X from an isotropic convex body in n-space, the variance of
|X|^2 is O(n).  We prove a reverse inequality: for any isotropic convex
polytope with at most poly(n) facets, the variance of |X|^2 is AT LEAST n/ln
n (up to a constant).  In fact, the lower bound holds for any polytope of
unit volume with poly(n) facets contained in the ball of radius poly(n).  It
implies that in order for most of such a convex polytope to be contained
between two concentric spheres, their radii have to differ by about
1/\sqrt{\log n}; in contrast, most of a unit-volume ball lies in between two
spheres whose radii differ by only about 1/\sqrt{n}.  This geometric
dispersion leads to linear and quadratic lower bounds on the randomized
complexity of some basic algorithmic problems.
 
This is joint work with Luis Rademacher. 
 
 
----------------------------------------------------------------------------
------
If you have questions, or would like to meet the speaker, please contact
Katherine at 773-834-1994 or kcumming at tti-c.org.   
For information on future TTI-C talks and events, please go to the TTI-C
Events page:  http://www.tti-c.org/events.html.  TTI-C (1427 East 60th
Street, Chicago, IL  60637)
 
 
 
-------------- next part --------------
An HTML attachment was scrubbed...
URL: http://mailman.cs.uchicago.edu/pipermail/colloquium/attachments/20060215/e893e506/attachment.htm