1127 Seminar Series

The goal of the 1127 Seminar Series is to present weekly talks by top researchers outside of the Computing Sciences Research Center, aka 1127, on topics that would be of interest to the members of 1127. Although this is a new series, it is envisioned to become a staple of life in 1127, similar to Show&Tell (weekly informal talks by researchers inside the center for others inside the center) and Cookie Time (a weekly social gathering for the center).

If you have a speaker in mind for the series, contact Chandra Chekuri to schedule a time slot. In general, the talks will be Friday afternoons at 2pm, just before Cookie Time, but if that is not convenient for your speaker, then other days/times are possible. Remember that we would like speakers to talk on topics of interest to a general 1127 audience. This will probably lie somewhere in between the type of talks at the Bell Labs General Research Colloquium, and the type of talks at some specific seminar series (like the Math Seminar). If you are not in 1127 and would like receive seminar announcements, send email to (chekuri att lucent dott com) to be added to the mailing list.

Upcoming:

Friday, August 5, 2PM : MH 2D-500D

Speaker: Hadas Shachnai, Technion
Host: Lisa Zhang
Title: Improved Results for Data Migration and Open Shop Scheduling
Abstract: The data migration problem is to compute an efficient plan for
moving data stored on devices in a network from one configuration to
another. It is modeled by a transfer graph, where vertices represent
the storage devices, and the edges indicate the data transfers
required between pairs of devices. Each vertex has a non-negative
weight, and each edge has a release time and a processing time. A
vertex completes when all the edges incident on it complete, under the
constraint that two edges incident on the same vertex cannot be
processed simultaneously. The objective is to minimize the sum of
weighted completion times of all vertices. Kim (in SODA 2003) gave a
9-approximation algorithm when edges have arbitrary processing times
and are released at time 0. We improve Kim's result by giving a
5.06-approximation algorithm.

We also address the open shop scheduling problem and show that it is a
special case of the data migration problem. Queyranne and Sviridenko
(J. of Scheduling, 2002) gave a 5.83-approximation algorithm for the
non-preemptive version of the open shop problem. They state as an
obvious open question whether there exists an algorithm for open shop
scheduling that gives a performance guarantee better than 5.83. Our
5.06 algorithm for data migration proves the existence of such an
algorithm. Crucial to our improved result is a property of the linear
programming relaxation for the problem. Similar linear programs have
been used for various other scheduling problems. Our technique may be
useful in obtaining improved results for these problems as well.

(Joint work with Rajiv Gandhi, Magn\'{u}s Halld\'{o}rsson and Guy
Kortsarz)

Past Seminars:

Friday, June 24, 2PM : MH 2A-435

Speaker: Leendert van Doorn, IBM
Host: Peter Bosch
Title: Trusted Computing (an IBM Research view)
Abstract: It is still too early to say, but it wouldn't surprise me if the phrase
Trusted Computing ends up among the top 10 hype phrases of this decade.
While seemingly intuitive, everyone knows what trusted computing means
to them, it is hard to develop set of common features and guarantees
that have a clear value proposition. In this talk I will present an IBM
research view of trusted computing which is obviously server, service
and open source centric. I will explain the technical details of the work
we are doing at IBM research around Trusted Computing Group (TCG) standards
(attestion, virtual TPMs) and secure virtualization (sHype and Xen).
I will also discuss some of the inherent TCG limitations and promising
new directions that resulted from collaboration with Adrian Perrig
(CMU) and his students.

Speaker bio:

Leendert van Doorn is a Research Staff Member at IBM T.J. Watson
Research Center where he is the senior manager of the secure systems and
tools departments. He received his Ph.D. from the Vrije Universiteit in
Amsterdam where he worked on the distributed operating system Amoeba and
designed and implemented an extensible operating system called Paramecium.
Nowadays his main interest is in system security. Currently he is working on
on secure hypervisors and trusted computing. His role is mainly that
of chief architect but he also likes to get his hands dirty and work on
the Intel VMX port for Xen. Occasionally he still works on his former
projects such as physically secure coprocessors and wireless security
auditing tools. He spends most of his time at Watson but is known to
occasionally find refuge in his office at CMU.

http://www.ece.cmu.edu/~leendert
http://www.research.ibm.com/people/l/leendert/

Tuesday, May 31, 2PM : MH 2A-435

Speaker: Rohit Khandekar, UC Berkeley
Host: Chandra Chekuri
Title: Approximating separators using single commodity flows
Abstract: Partitioning a graph into two large pieces while minimizing
the size of the "interface" between them is a fundamental
combinatorial problem. We show that such separators can be
approximated within a poly-logarithmic factor in time O*(n^{3/2}) using
single commodity max-flows. Previous algorithms are based on
multi-commodity flows which take time O*(n^2). Our algorithm
iteratively employs eigenvector and max-flow computations to embed an
expander flow, thus providing a certificate of expansion. We use as a
subroutine a balanced cut procedure of Spielman and Teng.

This is joint work with Satish Rao and Umesh Vazirani.

Friday, April 29, 2pm : MH 2D-500D

Speaker: Moses Charikar, Princeton University
Host: Chandra Chekuri
Title: Aggregating Inconsistent Information: Ranking and Clustering
Abstract: A ranking of n web pages is to be chosen from outputs of k search
engines. How do we choose one ranking minimizing the "disagreement" with
the k rankings ?

A clustering of n genes is to be chosen from outputs of k clustering
algorithms. How do we choose one clustering minimizing the
"disagreement" with the k clusterings?

These information aggregation problems date back to 1785, when the
French philosopher Condorcet considered voting systems where each voter
chooses a full ranking of a set of candidates. Recently, their
algorithmic and complexity aspects have been studied.

I will show that for both these problems, we can obtain improved
algorithms using essentially the same, remarkably simple principle.
Furthermore, this also applies to and yields improvements for
related graph theoretic optimization problems, known as the minimum
feedback arc set in tournaments and the correlation clustering in
complete graphs. Additionally, I will show that the problem of finding a
minimum feedback arc set in tournaments has no poly-time algorithm,
assuming NP is not contained in BPP. This almost settles a long-standing
conjecture of Bang-Jensen and Thomassen, that the problem is NP-hard.

This is joint work with Nir Ailon and Alantha Newman.

Friday, February 18, 2pm : MH 2D-500D

Speaker: Li (Erran) Li, Networking Research Lab, Bell Labs
Host: Chandra Chekuri
Title: Wireless Networking with Selfish Agents
Abstract: Traditionally wireless network protocols and architectures have been
designed under the assumption that end users and network entities are
cooperative. However, as wireless networks get more decentralized and
pervasive, efficient networking solutions must include and cope with
entities who want to optimize their own utilities.

In this talk, I will show how we can greatly improve on current approaches
to spectrum access in 3G wireless networks and WiFi networks, taking
selfish agents into account. First, I present an architecture and protocol
framework that allows 3G service providers to offload popular content to
ad hoc networks composed of 3G subscribers with 802.11 radios, thereby
reducing demand for 3G wireless spectrum. I then consider the problem of
assigning channels in WiFi networks. In WiFi networks, channels are shared
among the acess points (APs) of independent entities. I show that, by
allowing players to bargain, channel assignment can be made much more
efficient than the current approach which allocates channels in an ad hoc
manner. In both contexts, I present game-theoretic analysis on the impact
of of the selfish behavior of players.

This talk is based on two papers (joint work), one in MobiHoc'04, the
other in PODC'04.

Thursday, January 27, 10.30am : MH 2D-500D

Speaker: Dave Naumann, Stevens Institute of Technology.
Host: Kedar Namjoshi
Title: Reasoning locally about global invariants in object-oriented programs
Abstract: Imperative and object-oriented programs make ubiquitous use of heap
objects. Type-based ways of enforcing encapsulation, e.g., modules and
private fields in classes, are often transgressed by unexpected aliasing.
Common design patterns like Subscribe/Publish involve reentrant callbacks
which violate layered structure. Such encapsulation violations make it
difficult to achieve sound, modular reasoning about program behavior.
Type systems for alias control have addressed the problem but impose
awkward restrictions. In this talk I describe the use of auxiliary
fields, used for reasoning and validation but not present in production
code, to express encapsulation using assertions. A tool based on these
ideas is being developed at Microsoft Research.

Based on joint work with Mike Barnett and with Anindya Banerjee.

2004:

Friday, December 10, 2-3pm: MH 2D-500D

Speaker: Prof Badrinath, Rutgers.
Host: Girija Narlikar

Monday, December 6, 3pm: MH 2A-435

Speaker: Dr. Burton Kaliski, Jr., RSA Laboratories.
Host: Eric Grosse
Title: Cryptography and Data Security: Long-Term Challenges
Abstract: In this talk, I'll highlight some of the challenges the
cryptographic research community needs to address to prepare effectively for
the next 30 years. Current research provides initial but perhaps temporary
answers; I'll also suggest some areas of investigation that may yield more
permanent solutions.

Dr. Burt Kaliski is chief scientist and director of RSA Laboratories, the
research center of RSA Security, where he works to transform promising
technologies into competitive advantages for the company and its customers.

Friday, September 10, 2pm: MH 2D-500D

Speaker: Randy Wang, Princeton Univ.
Host: Girija Narlikar
Title: Networking Going Postal
Abstract: Making high-bandwidth Internet access pervasively available to a large world-wide audience is a difficult challenge, especially in many developing regions. As we wait for the uncertain takeoff of technologies that promise to improve the situation, we propose to explore an approach that is potentially more easily realizable: the use of digital storage media transported by the postal system as a general digital communication mechanism. We shall call such a system a Postmanet. Compared to more conventional wide-area connectivity options, the Postmanet has several important advantages, including wide global reach, great bandwidth potential, low cost, and ease of incremental adoption. While the idea of sending digital content via the postal system is not a new one, none of the existing attempts have turned the postal system into a generic and transparent communication channel that not only can cater to a wide array of applications, but also effectively manage the many idiosyncrasies associated with using the postal system. In the proposed Postmanet, we see two recurring themes at many different levels of the system. One is the simultaneous exploitation of the Internet and the postal system so we can combine their latency and bandwidth advantages. The other is the exploitation of the abundant capacity and bandwidth of the Postmanet to improve its latency, cost, and reliability.

Friday, August 20, 2pm: MH 2D-500D

Speaker: Trevor Jim, AT&T Research
Host: Nils Klarlund
Title: Secure programming in Cyclone
Abstract: Many security breaches today are caused by buffer overflows in server programs written in the C programming language. Cyclone is a dialect of C that prevents buffer overflows and related bugs. Cyclone retains C's syntax, types, and low-level control over data representations and memory management, while ensuring safety through combination of compile-time analysis and runtime checks. The combination of safety and C compatibility make Cyclone a good language for writing servers and other security-critical software.

I will review common causes of security breaches in C programs, and show how Cyclone would prevent the vulnerabilities, focusing on Cyclone's treatment of pointers and memory management. I will show by example that programming in Cyclone is very similar to programming in C, as well as illustrate a few omissions which remain to be addressed.

The Cyclone implementation is available at http://www.research.att.com/projects/cyclone/.

(Cyclone is a joint project of AT&T Labs Research, Harvard University, the University of Maryland, and the University of Washington.)

Tuesday, August 17, 2pm: MH 2D-500D

Speaker: George Karakostas, McMaster Univ.
Host: Gordon Wilfong
Title: The Good, the Bad, and the Rich: Routing selfish, class-conscious, and malicious users on traffic networks
Abstract: Recently the study of traffic networks has drawn much attention in the CS community, due to possible applications to the Internet or other computer networks. Yet the model of selfish routing studied so far by our community has been studied by OR experts for many decades now. In this talk we will use the classic formulation of Wardrop's principle by Aashtiani and Magnanti[AM81], to show how a certain type of malicious behavior can be incorporated in the traffic model. Surprisingly, although this malicious user is quite powerful, we show that he cannot affect the network performance by too much. Taxation can also be used in order to lure the selfish users into adopting a flow pattern that optimizes the total network latency. We will present some partial results that show this taxation not to be too harsh compared with the latency cost of the routing.

This is joint work with Anastasios Viglas and Stavros Kolliopoulos.

Monday, August 16, 3pm: MH 2D-500D

Speaker: Hana Chockler, Northeastern/ MIT
Host: Kedar Namjoshi
Title: Coverage Metrics in Formal Verification
Abstract: In formal verification, we verify that a system is correct with respect to a specification. Even when the system is proven to be correct, there is still a question of how complete the specification is, and whether it really covers all the behaviors of the system. The challenge of making the verification process as exhaustive as possible is even more crucial in {\em simulation-based\/} verification, where the infeasible task of checking all input sequences is replaced by checking a test suite consisting of a finite subset of them. It is very important to measure the exhaustiveness of the test suite, and indeed, there has been an extensive research in the simulation-based verification community on {\em coverage metrics}, which provide such a measure. It turns out that no single measure can be absolute, leading to the development of numerous coverage metrics whose usage is determined by industrial verification methodologies. On the other hand, prior research of coverage in formal verification has focused solely on state-based coverage.

I will introduce other coverage metrics that seem more suitable for temporal logic model checking. Some of the metrics are an adaptation of the work done on coverage in simulation-based verification to the formal-verification setting. For each metric I will briefly describe an efficient algorithm for computing it.

I will also discuss possible applications of the study of causality and responsibility to coverage. I will show that it gives significant insight into unresolved issues regarding the definition of coverage and leads to potentially useful extensions of coverage.

Joint work with J.Y. Halpern, O. Kupferman, R. Kurshan, and M. Y. Vardi

Friday, August 13, 2pm: MH 2D-500D

Speaker: Aravind Krishnamurthy, Yale Univ.
Host: Girija Narlikar
Title: Construction of Structured and Unstructured Overlays
Abstract: Distributed hash tables use hashing schemes to map machines and keys to a single, modular ID space. This results in a setting where the objects are (probabilistically) uniformly distributed over the ID space, but the hash function destroys the logical integrity of the keyspace, making it difficult to efficiently support complex similarity searches and range queries, and to distribute complex data structures without loss of performance. In this work, we propose a structured overlay based on Skip Graphs that can be used to efficiently distribute arbitrary hierarchical tree-like data structures and support interesting applications such as multi-dimensional indexing, distributed directory systems, and content-based publish-subscribe systems.

We also consider the problem of constructing unstructured overlays for medium-scale systems, a setting where unstructured overlays outperform their structured counterparts. We propose the use of interleaved spanning trees to compose a resilient, high performance overlay mesh. Though spanning trees of arbitrary type could be used to construct an overlay mesh, we focus on a distributed algorithm that computes k minimum spanning trees on an arbitrary graph. We elaborate details of k-MST and analyze its performance using a variety of metrics with simulation as well as a functional PlanetLab implementation. We then consider the problem of computing a set of paths for supporting multi-path data streams, and introduce a novel framework adapted from the world of finance - the mean-variance model. We demonstrate that the adaptation of this model to the context of overlay networks has a sound empirical basis.

Bio:

Arvind Krishnamurthy received his PhD from UC, Berkeley in 1999 for his dissertation research on parallel computing. He joined Yale faculty in 1999 and his current research interests include distributed systems, overlay networks, storage systems, network security, and mechanism design.

Friday, August 6, 2pm: MH 2D-500D

Speaker: Kasturi Varadarajan, Univ. of Iowa
Host: Chandra Chekuri
Title: Market Equilibrium for Exchange Economies
Abstract: We consider the problem of efficiently computing a competitive equilibrium for a given exchange economy. When an exchange economy satisfies a property known as weak gross substitutability, classical results from mathematical economics characterize the set of equilibria as a convex set. We show that under some fairly mild assumptions, we can build on the proofs of these characterizations to obtain poly-time algorithms to compute an equilibrium.

We then consider exchange economies where the utility functions are drawn from an important class known as CES functions. We show that for a range of these functions the equilibria can be characterized as the solutions to a finite convex program. This range contains all the CES functions that satisfy weak gross substitutability and some CES functions that do not enjoy this property.

Friday, July 23, 2004, 2pm: MH 2D-500D

Speaker: Michael Codish, Ben Gurion Univ. (Israel)
Host: Dennis Dams
Title: Semantic Based Termination Analysis (One Loop at a Time)
Abstract: This talk presents a semantic based approach to termination analysis. The focus is on termination of logic programs; however, the approach is of general interest and provides a different perspective on proving termination than that which we learn (or teach) in "Computer Science 101".

Classic techniques for proving termination require the identification of a measure that maps program states to the elements of a well-founded domain. Termination is guaranteed if this measure is shown to decrease with each iteration of a loop in the program. This is a \emph{global} termination condition --- there exists a measure which is shown to decrease over all of the loops in the program.

In recent years, systems based on \emph{local} termination conditions are emerging. Here, termination is guaranteed if for every loop there exists a measure which decreases as execution follows through that loop. Local termination conditions are simpler and easier to verify automatically. However, for correctness, loops are required to be closed under a composition operation. In theory, this may increase their number exponentially, although this rarely happens in practice.

The talk will present the local approach to proving termination and illustrate its formal justification.

Friday, June 11, 10am: MH 2D-500D

Speaker: Huaiyu "Kitty" Liu,University of Texas Austin
Host: Eric Grosse
Title: Failure Recovery for Structured P2P Networks: Protocol Design and Performance Evaluation
Abstract:Measurement studies indicate a high rate of node dynamics in p2p systems. In this paper, we address the question of how high a rate of node dynamics can be supported by structured p2p networks. We confine our study to the hypercube routing scheme used by several structured p2p systems. To improve system robustness and facilitate failure recovery, we introduce the property of K-consistency, K>=1, which generalizes consistency defined previously. (Consistency guarantees connectivity from any node to any other node.) We design and evaluate a failure recovery protocol based upon local information for K-consistent networks. The failure recovery protocol is then integrated with a join protocol that has been proved to construct K-consistent neighbor tables for concurrent joins. The integrated protocols were evaluated by a set of simulation experiments in which nodes joined a 2000-node network and nodes (both old and new) were randomly selected to fail concurrently over 10,000 seconds. In each such ``churn'' experiment, we took a ``snapshot'' of neighbor tables in the network once every 50 seconds and evaluated connectivity and consistency measures over time as a function of the churn rate, timeout value in failure recovery, and K. Storage and communication overheads were also evaluated. We found our protocols to be effective, efficient, and stable for an average node lifetime as low as 16.7 minutes (the median lifetime measured for Napster and Gnutella was 60 minutes).

Friday, Feb 27, 1:30pm: MH 2D-500D

Speaker: Jon Giffin, University of Wisconsin
Host: Eric Grosse
Title: Efficient Context-Sensitive Intrusion Detection
Abstract: Model-based intrusion detection compares a process's execution against a program model to detect intrusion attempts. Models constructed from static program analysis have historically traded precision for efficiency. In particular, precise models based upon pushdown automata (PDA) are very inefficient to operate due to non-determinism in stack activity. In this talk, I will describe a technique for determinizing PDA models. I will introduce the concept of a stack-deterministic PDA and will present the Dyck model, an implementation of such a PDA. The Dyck model is the first efficient statically-constructed context-sensitive model. Experiments demonstrate that it is an order of magnitude more precise than a context-insensitive finite state machine model. With null call squelching, a dynamic technique to bound cost, the Dyck model operates in time similar to the context-insensitive model. I will also present new static data-flow analyses, branch analysis and argument dependency recovery, that manipulate data values known only at run-time. Combined with a monitor that observes datavalues, these techniques limit model exploration and system call arguments to further thwart potential attacks.

Friday, Mar 12, 2pm: MH 2A-435

Speaker: Henry S. Baird, Lehigh University
Host: Tin-Kam Ho
Title: Image Understanding & Web Security
Abstract: Internet services offered for human use are suffering abuse by programs ('bots, spiders, scrapers, spammers, etc). We mount a defense against such attacks with CAPTCHAs, `completely automatic public Turing tests to tell computers and humans apart.' These are special cases of `human interactive proofs' (HIPs), a class of security protocols allowing people easily to identify themselves over networks as members of given groups. I will review the five years of evolution of HIP R&D, highlights of the first NSF HIP workshop, and applications of HIPs now in use and on the horizon. One of the best ways to build a CAPTCHA is to exploit the gap in ability between humans and machines when they attempt to read images of text. I will describe two such reading-based CAPTCHAs, developed in collaborations between PARC and UC Berkeley:

PessimalPrint, motivated by studies of physics-based image degradations, uses images synthesized pseudo-randomly over certain words, typefaces, and image qualities; and
BaffleText, motivated by the psychophysics of human reading, uses image-masking degradations that seem to require Gestalt perception skills that people are especially good at.

Both of these CAPTCHAs have been validated by experiments on human subjects and commercial OCR machines, and both have successfully resisted attack by advanced computer-vision techniques (so far) . I'll offer proposals for an image understanding research agenda to advance further the state of the art of web security.
[This work was carried out while the speaker was at the Palo Alto Research Center; it was joint with Richard Fateman, Allison Coates, Kris Popat, Monica Chew, Tom Breuel, & Mark Luk.]
Dr. Baird is a Professor of Computer Science & Engineering at Lehigh University. He's a Fellow of the IEEE and of the IAPR. He has published three books and sixty-nine technical articles, and holds seven patents. With Manuel Blum of CMU, he organized the 1st NSF Int'l HIP Workshop, held at PARC in January 2002.

Friday, Mar 26, 2pm: MH 2A-435

Speaker: Cliff Stein, Columbia University

Host: Lisa Zhang

Title:Scheduling an Industrial Production Facility: Applying theory in practice

Abstract: Managing an industrial production facility requires carefully allocating limited resources, and gives rise to large, potentially complicated scheduling problems. In this talk we consider a specific instance of such a problem: planning efficient utilization of the facilities and technicians that maintain the United States nuclear stockpile. A detailed study of this problem yields a complicated mixed-integer programming (MIP) model with upward of hundreds of thousands of variables and even more constraints. Consistently and quickly solving such a model exactly is impossible using today's algorithms and computers, and thus, in addition to using branch-and-bound, we must use good heuristics and approximation algorithms. This talk studies several different methods of generating good solutions, given the solution to the IP relaxation. We design a suite of sample data and test the algorithms. The goals of this project are twofold. First, we want to develop a program that could efficiently and accurately help with the planning problem. Second, we want to experimentally test various ideas, designed originally for ``cleaner'' problems, in this more challenging context. This talk wil focus on the second goal. In summary, we demonstrate the value of using alpha-points as a way to quickly and cheaply generate, from one solution of an LP relaxation, many feasible solutions to an integer program. In this particular envivonment, the use of alpha-points, combined with other clever heurstics outperforms local search. We also see the value of finding combinatorially-structured subproblems as opposed to using simple greedy approaches.
Joint work with: E. Asgiersson (Columbia University), J. Berry (Lafayette College), C. Phillips (Sandia National Labs), D. Phillips (Columbia University), J. Wein (Polytechnic University)

Friday, Apr 9, 2pm: MH 2A-435

Speaker: Peter Patel-Schneider, Bell Labs
Host: Eric Grosse
Title:What is OWL (and why should I care)?
Abstract:OWL is the new ontology language produced by the W3C Web Ontology Working Group. OWL is thus poised to be a major formalism for the design and dissemination of ontology information, particularly in the Semantic Web. OWL has influences from several communities, including the RDF community, the Description Logic community, and the frame community. These influences resulted in a wide variety of requirements on OWL, some of which appear to be conflicting. OWL contains innovative solutions to several of these apparent conflicts, but it has not been possible to completely satisfy all the desired requirements for OWL. In this talk I will describe the development and design of OWL, concentrating on what makes OWL important, the relationship of OWL to other formalisms, the place of OWL in the Semantic Web, the innovative solutions that were required in its design, and the impact of the conflicting requirements on OWL. I will also propose a different foundation for the Semantic Web, one that I think would allow for easier and better development of new formalisms for the Semantic Web.

http://www-db.research.bell-labs.com/user/pfps

Friday, Apr 16, 2pm: MH 2A-435

Speaker: Christian Scheideler, Johns Hopkins
Host: Lisa Zhang
Title: Distributed data structures
Abstract: In this talk I will give a survey of recent results in the area of distributed data structures, concentrating on data structures that are useful for distributed applications such as peer-to-peer systems. Peer-to-peer systems have recently attracted a great deal of attention both inside and outside the research community. Unfortunately, due to the lack of clean and well-accepted models, theoretical research on data structures useful for peer-to-peer systems has rarely made it into top theory conferences. I will first discuss problems in previous models for distributed and concurrent data structures and then suggest alternative models, opening up interesting, new research directions for distributed data structures as well as platforms that allow to run distributed data structures over the Internet.

Thursday, May 20, 2pm: MH 2A-435

Speaker: Sanjeev Arora, Princeton
Host: Chandra Chekuri
Title: Expander Flows, Geometric Embeddings, and Graph Partitioning
Abstract: Partitioning a graph into two (or more) large pieces while minimizing the size of the ``interface'' between them is a fundamental combinatorial problem. Graph partitions or separators are central objects of study in the theory of Markov chains, geometric embeddings and are a natural algorithmic primitive in numerous settings, including clustering, divide and conquer approaches, PRAM emulation, VLSI layout, and packet routing in distributed networks. We describe a new O(\sqrt{log n})-approximation algorithm for many graph partitioning problems, including SPARSEST CUT. This improves the classical algorithms based upon flows (Leighton Rao; O(log n)-approximation) and those based upon spectral methods. The algorithm relies on semidefinite relaxations that use the triangle inequality constraints. Analysing these relaxations had been an important open problem as well. We also introduce the notion of {\em expander flows}, which constitute an interesting ``certificate'' of a graph's expansion. At the end I also mention a more recent algorithm obtained with students Elad Hazan and Satyen Kale that shows how to achieve the above approximations in O(n²) time without using semidefinite programming. Our techniques are an interesting mix of graph theory and high-dimensional geometry, including the use of "measure concentration." (Joint work with Satish Rao and Umesh Vazirani; to appear at ACM STOC 2004)

Friday, May 21, 10:30am: MH 2A-435

Speaker: Florian Jarre,University of Duesseldorf (on sabbatical at Rice University)
Host: Roland Freund
Title: Semidefinite Programming
Abstract: We give a brief introduction to semidefinite programming and its applications. We then present a simple sensitivity result for solutions of linear semidefinite programs under small arbitrary perturbations of the data. The result is used to derive an elementary and self-contained analysis of local quadratic convergence of a sequential semidefinite programming (SSP) method. Some numerical examples conclude the talk.

Friday, June 11, 10am: MH 2D-500D

Speaker: Huaiyu "Kitty" Liu,University of Texas Austin
Host: Eric Grosse
Title: Failure Recovery for Structured P2P Networks: Protocol Design and Performance Evaluation
Abstract:Measurement studies indicate a high rate of node dynamics in p2p systems. In this paper, we address the question of how high a rate of node dynamics can be supported by structured p2p networks. We confine our study to the hypercube routing scheme used by several structured p2p systems. To improve system robustness and facilitate failure recovery, we introduce the property of K-consistency, K>=1, which generalizes consistency defined previously. (Consistency guarantees connectivity from any node to any other node.) We design and evaluate a failure recovery protocol based upon local information for K-consistent networks. The failure recovery protocol is then integrated with a join protocol that has been proved to construct K-consistent neighbor tables for concurrent joins. The integrated protocols were evaluated by a set of simulation experiments in which nodes joined a 2000-node network and nodes (both old and new) were randomly selected to fail concurrently over 10,000 seconds. In each such ``churn'' experiment, we took a ``snapshot'' of neighbor tables in the network once every 50 seconds and evaluated connectivity and consistency measures over time as a function of the churn rate, timeout value in failure recovery, and K. Storage and communication overheads were also evaluated. We found our protocols to be effective, efficient, and stable for an average node lifetime as low as 16.7 minutes (the median lifetime measured for Napster and Gnutella was 60 minutes).

2003:

Friday, Mar 14, 2003, 2pm: MH 2A-435

Speaker: Manish Parashar, Rutgers University

Host: Wonsuck Lee

Title: Towards Autonomic Simulations on the Grid

Abstract: Dynamically adaptive simulations, such as those based on SAMR, have the potential for enabling physically realistic modeling of complex phenomenon. However their efficient implementation on distributed, heterogeneous and dynamic execution environments such as the Grid presents significant challenges. In this talk I will present computational solutions that can enable efficient implementations of these applications. Specifically, I will address distributed and dynamic data management, autonomic runtime management, interactive monitoring and control of SAMR applications.

Friday, Mar 21, 2003, 2pm: MH 2D-500D

Speaker: Suresh Venkat, AT&T Labs

Host: Chandra Chekuri

Title: Streaming Algorithms in Graphics Hardware

Abstract: The computing industry is seeing the emergence of a powerful subsystem: the graphics accelerator card. This subsystem, capable of rendering millions of objects per second, demonstrates parallelism in pixel-level rendering and is based on a architecture designed for processing data streams. Moreover, it is now undergoing powerful augmentation with the introduction of programmability in its traditionally fixed pipeline architecture. These graphics accelerator cards are inexpensive and ubiquitous (most off-the-shelf PCs have them, as do all video game consoles), and essentially provide an alternative computational platform for the interactive visualization of streams. Graphics hardware has been already used to accelerate computation of general interest in data analysis, GIS, geometry and graphics, These algorithms provide proof-of-concept; however, they have only used a small subset of the capabilities that current hardware provides, and exclude all of the programmable aspects. What is the extent of the capabilities of the graphics pipeline? To answer this question, we need to understand the computational power that it provides. As a model of computing, the pipeline draws together ideas from streaming algorithms, parallel computing, and approximation algorithms. A formal investigation of this will both tell us what we can do with graphics cards, and how we can improve them in the future. In this talk, I will survey the streaming computing capabilities of the graphics pipeline, and present some examples of problems that can currently be solved using the graphics pipeline.

Friday, Apr 25, 2003, 2pm: MH 2A-435
- Speaker: Steve Bellovin, AT&T Labs
- Host: Phil MacKenzie
- Title: Realistic Security
- Abstract: Many security systems fail, not for technical reasons but because they fail to take into account the way people really use computers. A realistic security policy may not be the theoretical best; in the real work, though, it's likely to do far better. We present some examples of things that have been done wrong in the past, along with suggestions for improvement.

Friday, May 2, 2003, 2pm: <open>

Friday, May 9, 2003, 2pm: MH 2A-435

Speaker: Dragan Samardzija, Bell Labs Wireless Research Labs
Host: Sape Mullender
Title: Packet Based 3G Wireless Systems: A Modem Design
Abstract: In this talk we will address the basic features of the latest, third generation (3G), wireless systems dedicated to data transmissions. In order to optimize wireless cellular networks, the voice-centric circuit-switched 2G wireless systems have evolved. As a major step, implementing a packet-based access directly on the physical layer greatly increases spectral efficiency of 3G systems, optimizing them for data transmission. The talk will focus on the cellular wireless environment, physical and MAC layer. As a case study, High Speed Downlink Packet Access (HSDPA) will be presented. The basic building blocks of the physical layer (scrambling, spreading, modulation, channel coding) and the MAC layer (fast retransmissions, incremental redundancy, Chase combining and scheduling/resource controller) will be described.

Friday, May 16, 2003, 2pm: <open>

Friday, May 23, 2003, 2pm: MH 2A-435

Speaker: Pankaj Agarwal, Duke University
Host: Steve Fortune
Title: Geometric Approximation Using Core Sets
Abstract: We present a general technique for approximating the `extent'' of a set of points in d-dimensional space. Extent is an abstraction that includes as special cases the diameter, width, and smallest bounding box, ball, or cylinder. For a given tolerance epsilon>0, the technique computes a ``core'' subset of the input points that approximates the extent of the whole set. The size of the core-set depends upon epsilon but is independent of the size of the input set, and for any fixed epsilon, the core-set can be computed in linear time. The technique extends to maintaining an approximation of the extent of a moving points and to points given online in the streaming model. The technique also allows fitting various shapes, including spheres and cylinders, through a point set. Joint work with Sariel Har-Peled and Kasturi Varadarjan.

Friday, May 30, 2003, 2pm: <open>

Friday, Sep 12, 2003, 2pm: MH 2A-435

Speaker: Hugo Krawczyk, Technion and IBM Research
Host: Juan Garay
Title: The Design of the SIGMA and IPSec's Key-Exchange (IKE) Protocol
Abstract: SIGMA is a family of authenticated Diffie-Hellman protocols that forms the cryptographic core of the main key-exchange mechanisms in IPSec (IKE versions 1 and 2). In this talk we describe the rationale behind the SIGMA design, its security and privacy guarantees, and its applications to IKE. The presentation is intended for a broad audience of crypto-protocol designers and security engineers, and emphasizes many subtleties surrounding the design of secure key-exchange protocols. In particular, we point to several shortcomings found in previous authenticated Diffie-Hellman protocols. The talk is based on the invited lecture delivered at Crypto'03, and a detailed paper on the SIGMA design can be found in its proceedings. For an on-line version see http://www.ee.technion.ac.il/~hugo/sigma.html.

Friday, Oct 17, 2003, 2pm: MH 2A-435

Speaker:Nils Klarlund, Clairgrove LLC
Host:Dennis Dams & Kedar Namjoshi
Title: TheShortTalk editing language --- and its relevance to the roleof language in human computer interfaces
Abstract: The idea is old that human languages should be constructed accordingto systematic phonetic principles that make them succint. In addition to 19th-century Volapük (Vola="world" pük="speak") [infamously known in some countries where it means "nonsense"!], two other reasons for their existence were conceived in the 1940s. (1) The machine reason by Vannevar Bush, Director of the Office of Scientific Research and Development: "It is strange that the inventors of universal languages have not seized upon the idea of producing one which better fitted the technique for transmitting and recording speech." (2) The cognitive reason by Robert A. Heinlein: "...it was possible to establish any one-to-one relationship with Basic English so that one phonetic symbol was equivalent to an entire word in a 'normal' language, one Speedtalk word was equal to an entire sentence. ShortTalk is an editing language meant to make spoken operation of a text editor efficient and enjoyable. Although not a universal language by any means, ShortTalk is powered by cognitive abilities of humans similar to (2) and known from human mastery of commandlanguages expressed through keys; it is also affected by user interface issues anticipated by (1) and known as mode problems. I will provide cognitive and analytical arguments why a ShortTalk-like language is the only solution to the problem of manipulating a computer efficiently by voice. Preliminary experimental results support the conclusion that speech offers a very significant advantage to editing efficiency over traditional means. Of course, doing intrinsically repetitive work by speech is not a feasible approach. So, I round off the talk by mentioning an anotheralternative to using your hands: use your feet. A recent invention allows virtually any keyboard command to be issued by feet.