Thursday, December 1, 3:00PM
NSH 1507
Benoit Hudson
How to mesh when the ground is moving
Traditionally, finite element simulations have assumed the geometry of the domain is fixed — after all, in a weather simulation, the mountains do not move. However, in many problems the geometry does, in fact, change — very notably so in solid deformation problems (bending a steel bar, for instance) and in fluid-solid interaction problems (blood cells flowing through a capillary). Even when the geometry is fixed, it can be helpful to write the equations in a Lagrangian frame of reference, which requires that we allow mesh elements to move and deform over time. I will survey various methods to deal with moving boundaries and moving mesh elements. As a geometer, I will naturally bias towards techniques that leave the mathematics quite simple at the cost of making the geometry difficult. We will see that while the state of the art has progressed to the point of making pretty pictures, the field is still wide open.
Speaker: Virginia Vassilevska
Time: Wednesday 12-1pm
Location: NSH 1507
Title: Models of Greedy Algorithms
Abstract:
In an attempt to define an abstract model that captures what we call greedy algorithms, Borodin et al. define so called priority algorithms, in the context of scheduling problems. Davis and Impagliazzo further apply the framework to graph problems. A lot of approximation lower bounds have been proven in this model. For example, weighted vertex cover cannot be approximated by a better factor than 2 using an algorithm fitting the framework. Furthermore, most greedy algorithms seem to fit the framework – e.g. the greedy weighted vertex cover algorithm.
The goal of the talk is to provide a brief survey on the research done on priority algorithms.
TITLE:Stopping Rules and Time Reversal for Random Walks on Graphs
SPEAKER: Andrew Beveridge
WHEN: December 1, 4-5:30pm
WHERE: PPB 300
ABSTRACT: Consider a directed graph $G$ and a random walk on it. Looking at such a walk in reverse gives a random walk on a related directed graph $\hat{G}$. When $G$ is an undirected graph, we have $G=\hat{G}$. One can use and intelligent stopping rule that “looks where it is going” to halt a random walk so that the distribution of the final state is a desired distribution $\tau$. This leads to a number of exact mixing measures that are related to the classical mixing measures (such as the relaxation time). We discuss the effect of time reversal on stopping rules by considering families of rules from singletons to a specified target distribution. We describe a duality between stopping rules on $G$ and stopping rules on $\hat{G}$. In particular, we give a natural proof that the “average mixing time” of a random walk on $G$ is equal to the time it takes for a random walk on $\hat{G}$ to “forget where it started,” which was originally proved by Lovasz and Winkler via linear programming.
Joint work with Laszlo Lovasz.
Friday, December 2, 2005
1:30 p.m. Posner Hall 152
Bill Cunningham
Professor, Department of of Combinatorics & Optimization
University of Waterloo
3-Terminal Cuts and Linear Programming
Given an undirected graph having non-negative weights on the edges, and three specified terminal nodes, the optimal 3-cut problem is to find a minimum weight set of edges whose deletion disconnects the terminals from each other. The corresponding problem with only two terminals is well known to be efficiently solvable, but this problem is hard to solve, even to solve approximately.
I will outline some background on the 3-cut problem, and will describe an attractive geometric relaxation introduced by Calinescu, Karloff, and Rabani, which they used to derive an approximation of provable accuracy. Then I will explain an approach leading to a tight bound on the accuracy of their relaxation, and to an approximation algorithm having a better performance guarantee.
I will emphasize the role of linear programming, both in the solution of the relaxation, and in its analysis.
This talk is based on joint work with Kevin Cheung and Lawrence Tang.
Thursday, November 17th, 2005
4:00pm
Scaife Hall Auditorium Room 125
Steganography: Art or Science?
Pierre Moulin, UIUC
Steganography is the art of embedding secret messages into cover data sets (such as images, video, audio files, text, and computer programs). The presence of hidden information should be undetectable to everyone except the intended recipient of the message. Conversely, steganalysis is the art of discovering the presence of hidden data.
Steganography has been used by revolutionaries, spies, the military, and perhaps terrorists. Recently sophisticated methods have been developed for steganalysis, aiming at identifying small changes in statistics in cover data. This has led to a new generation of steganographic techniques that can resist steganalysis. Where does the cat and mouse game stop?
In this talk we’ll present some fundamental limits for steganography, by defining ground rules and maximizing rate of reliable transmission subject to a statistical undetectability constraint (analogous to Shannon’s notion of perfect secrecy). The applicability of this theory to practical steganographic problems will be discussed.
Bio: Pierre Moulin received his doctoral degree in 1990, after which her worked for Bell Communications Research for years. He joined the University of Illinois at Urbana-Champaign in 1996. He is currently Professor in the Department of Electrical and Computer Engineering and Affiliate Professor in the Department of Statistics. His fields of professional interest are information theory, image and video processing, statistical signal processing, compression, and information hiding. He has served on the editorial boards of the IEEE Transactions on Information Theory and the Transactions on Image Processing and is the editor in chief of the upcoming IEEE Transactions on Information Forensics and Security. He is an IEEE fellow, recipient of 1997 and 2002 best paper awards from the IEEE Signal Processing Society, 2003 Associate of the UIUC Center for Advanced Study, and 2005 Sony Faculty Scholar.
Title: Matching Algorithms are Fast in Sparse Random Graphs
Speaker: Guido Schaefer, Technische Universitaet Berlin
When: Thursday, November 17, 4pm-5pm
Where: PPB 300
Abstract:
We present an improved average case analysis of the maximum cardinality matching problem. We show that in a bipartite or general random graph on $n$ vertices, with high probability every non-maximum matching has an augmenting path of length $O(\log n)$. This implies that augmenting path algorithms like the Hopcroft–Karp algorithm for bipartite graphs and the Micali–Vazirani algorithm for general graphs, which have a worst case running time of $O(m\sqrt{n})$, run in time $O(m \log n)$ with high probability, where $m$ is the number of edges in the graph. Motwani proved these results for random graphs when the average degree is at least $\ln (n)$ [\emph{Average Case Analysis of Algorithms for Matchings and Related Problems}, Journal of the ACM, \textbf{41}(6), 1994]. Our results hold, if only the average degree is a large enough constant. At the same time we simplify the analysis of Motwani.
Joint work with Holger Bast, Kurt Mehlhorn and Hisao Tamaki
When: 4:30pm TODAY, 11/14/05 (Refreshments will be served at 4:15p outside
of A53 Baker Hall.)
Where: A53 Baker Hall
Speaker: Ann Lee
Title: Geometric tools for high-dimensional data analysis
Abstract:
In high-dimensional data analysis, one is often faced with the problem that real data is noisy and in many cases given in coordinates that are not informative for understanding the data structure itself or for performing later tasks, such as clustering, classification and regression. The combination of noise and very high dimensions (such as >1000) presents challenges for data analysis and calls for efficient dimensionality reduction tools that take the inherent geometry of natural data into account. In this talk, I will first describe a data-driven multi-scale basis that can be used for feature extraction of smooth data as well as data where the coordinates may be randomly ordered. I will then, in the second half of my talk, describe a general framework for dimensionality reduction, data set parameterization and clustering that combines many ideas from eigenmaps, spectral graph theory and harmonic analysis. Our construction is based on a Markov random walk on the data, and allows one to define a system of coordinates that is robust to noise, and that reflects the intrinsic geometry or connectivity of the data points in a diffusion process. Examples will be taken from image analysis, word-document clustering and spectroscopy. (Part of this work is joint with R.R. Coifman and S. Lafon)
Friday, November 18, 2005
1:30 pm Posner Hall 259
Pierre Bonami
Post Doctoral Fellow in OPS Research
Tepper School of Business, Carnegie Mellon
An Algorithmic Framework for Convex Mixed Integer Nonlinear Programs
We present our work in an on-going project with the Chemical Engineering Department and IBM to build new open source software for solving Mixed Integer Non Linear Programs.
We address the general problem of minimizing a twice differentiable convex function in a region described by convex constraints with integrality requirements on some of the variables.
In particular we present an hybrid algorithm that combines non-linear and linear relaxations of MINLPs in a branch-and-cut framework. This flexible algorithm is implemented in the COIN-OR framework using Cbc (a branch-and-cut algorithm), Ipopt (an interior point solver for nonlinear programming) and Clp (a linear programming solver) as building blocks. We present computational results comparing this hybrid algorithm to commercial solvers, and our implementations of branch-and-bound, and outer approximation algorithms. The algorithms are compared on a new publicly available library of convex mixed integer nonlinear programs that we have put together.
Title: New Streaming Algorithms for Fast Detection of Superspreaders
Speaker: Shobha Venkataraman, CSD
Location: NSH 1507
Time: 12-1 pm
Date: Friday, November 11th, 2005
Abstract:
High-speed monitoring of Internet traffic is an important and challenging problem, with applications to real-time attack detection and mitigation, traffic engineering, etc. However, packet-level monitoring requires fast streaming algorithms that use very little memory and little communication among collaborating network monitoring points. In this paper, we consider the problem of detecting superspreaders, which are sources that connect to a large number of distinct destinations. We propose new streaming algorithms for detecting superspreaders and prove guarantees on their accuracy and memory requirements. We also show experimental results on real network traces. Our algorithms are substantially more efficient (both theoretically and experimentally) than previous approaches. We also extend our algorithms to identify superspreaders in a distributed setting, with sliding windows, and when deletions are allowed in the stream. More generally, our algorithms are applicable to any problem that can be formulated as follows: given a stream of $(x,y)$ pairs, find all the $x$’s that are paired with a large number of distinct $y$’s. This paper discusses the applications of this general problem and, for concreteness, focuses on the superspreader problem. Joint work with Dawn Song, Phillip Gibbons and Avrim Blum.
Speaker: Andrew Gilpin
Time: Wednesday 12-1pm
Place: NSH 1507
Title: Finding equilibria in large sequential games of imperfect information
Abstract:
Computing an equilibrium of an extensive form game of imperfect information is a fundamental problem in computational game theory, but current techniques do not scale to large games. To address this, we introduce the ordered game isomorphism and the related ordered game isomorphic abstraction transformation. For an n-player sequential game of imperfect information with observable actions and an ordered signal space, we prove that any Nash equilibrium in an abstracted smaller game, obtained by one or more applications of the transformation, can be easily converted into a Nash equilibrium in the original game. We present an efficient algorithm, GameShrink, which automatically and exhaustively abstracts the game. Using GameShrink, we find an equilibrium to a poker game that is over four orders of magnitude larger than the largest poker game solved previously. To address even larger games, we introduce approximation methods that do not preserve equilibrium, but nevertheless yield (ex post) provably close-to-optimal strategies.
Every since I started giving talks, I wanted to know how my talks really were. But then, it seems difficult to collect the real opinions because of various reasons. (Diplomacy, friends, countrymen, comrades, etc.) For a start, I want to be able to conduct a thumbs-up/down vote as publicly as possible, but also preserves the secrecy of the votes.
Being at CMU actually makes this problem very easy to “solve”. All I did was to walk into a real crypto person in the corridor the very next morning. And before I finish telling my story, I am already presented with a proposal that is actually executable by real human beings. The trick is to have a way to distribute secret random bits.
Here is how one system may work to ask each person “Is this a good talk?”. At the door, each person is dealt with a card from a shuffled deck. Half of the cards in the deck have “This is a good talk” written underneath it, and the other half have “This is a bad talk”. That’s the secret bit for each person.
Two bins are placed at the door: “I agree” and “I disagree”. At the end of the talk, you just put the card (faced down, of course) into the appropriate bin. As long as your secret bit is not revealed, no one could be sure what your vote really was from observing which bin you used.
I can think of a number of ways to extend the number of questions asked in various ways, all involving secret initialization bits and XOR’ing with the answer bits.
So what questions do I want to ask? After asking around, it seems that the following questions are more interesting:
- Do you understand the problem statement?
- Do you think the problem is interesting?
- Do you understand the proposed solution in the high level?
This works better than pure thumbs-up/down because we may want to distinguish YNN from YYN.
I guess I will use it in my next talk and see how it goes.
Tuesday, November 1
3:00 p.m.
3305 Newell-Simon Hall
“Thoughts on Introductory Computer Science Education”
Peter Lee, Professor, School of Computer Science, Carnegie Mellon University
Computer scientists and computer science educators are constantly reassessing the introductory curriculum. The intensity of this reassessment has increased, in large part because it is seen as relevant to the recent concerns about declining enrollments and interest in the field.
For the most part, introductory computer science has emphasized hands-on experiences and the development of programming skills. While hands-on skills development has been a mainstay of almost all introductory laboratory-science courses in, for example, biology and chemistry, introductory CS has been unusual, both in its heavy use of “industrial-strength” tools, such as the C++ programming language and commercial web-development systems, as well as the extent to which skills are emphasized over other aspects of the field, such as its history and scientific (or mathematical) underpinnings. In a sense, intro CS has attempted to serve not only as an introduction to the field but also as a valuable form of vocational training.
In this talk, I will give my thoughts on the introductory curriculum. I will argue that the use of industrial-strength tools is often inappropriate, just as it would be in, say, a high-school chemistry course. Instead, I believe that a more well-rounded curriculum that provides a balance of skills development, mathematical foundations, and historical context would be both more appropriate and more effective in inspiring young people to enter the field and understand its scope.
