Computer Science Colloquium SERIES

Prof. David Brooks

Harvard University

Flash Video

Host: Prof. Greg Morrisett

Dr. David Bacon

IBM Research and Harvard University

Flash Video

Host: Prof. Greg Morrisett

Prof. Arvind

Computer Science and Artificial Intelligence Laboratory,
M.I.T.

Flash Video

In the developing world a mobile phone is the only computer most people have.  With countries like India getting seven million new mobile phone customers per month, mobile devices and the associated services infrastructure are going to be the main drivers for both industry and research. In this new world, power and cost constraints completely determine functionality. Meeting power and cost constraints for mobile devices and sensors is much easier through dedicated chips than via software programmability. This vision is counter to the steadily decreasing new chip-starts in industry driven by rising chip development costs. A fundamental shift is needed in the current design flow of systems-on-a-chip (SoCs) to fulfill this demand in a cost-efficient manner. We will present a method of designing systems that facilitates synthesis of complex SoCs from reusable “IP” modules. The technical challenge is to provide a method for connecting modules in a parallel setting so that the functionality and the performance of the composite are predictable.

Speaker: Arvind is the Johnson Professor of Computer Science and Engineering at MIT where in the late eighties his group, in collaboration with Motorola, built the Monsoon dataflow machines and its associated software. In 2000, Arvind started Sandburst which was sold to Broadcom in 2006. In 2003, Arvind co-founded Bluespec Inc., an EDA company to produce a set of tools for high-level synthesis. In 2001, Dr. R. S. Nikhil and Arvind published the book "Implicit parallel programming in pH". Arvind's current research focus is on enabling rapid development of embedded systems. Arvind is a Fellow of IEEE and ACM, and also a member of  National Academy of Engineering. http://www.csg.csail.mit.edu/Users/arvind/

Host: Prof. David Brooks

February 26, 2009 -- JOINT CS/IIC

NOTE CHANGE OF LOCATION TO 60 Oxford St., Rm. 330

S. Muthu Muthukrishnan

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 myriad 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.

Speaker: S. Muthukrishnan (call him Muthu) finished his Ph.D. at the Courant Institute of Mathematical Sciences, NYU, in 1994. He has been a faculty member at U. Warwick, UK, a Member of Technical Staff at Bell Labs, Lucent Tech., and a Technology Consultant at AT&T Labs. He is now a Senior Research Scientist at Google Research in NY on leave from Rutgers University where he is a Professor. His research interest is in design and analysis of algorithms, databases, networking and market algorithms. His recent research is on algorithmic methods and computing systems for processing massive "streams" of data with applications to IP traffic analyses (see book at http://www.amazon.com/Data-Streams-Applications-Foundations-Theoretical/dp/193301914X), as well as algorithmic mechanism design for Internet ad auctions (See paper from ICALP Pleary Talk at http://algo.research.googlepages.com/icalp08.pdf) . His previous research interest included wireless networking (see NAE address at http://books.nap.edu/openbook.php?record_id=10494&page=68), string matching algorithms and others.

Host: Prof. Michael Mitzenmacher

Prof. Ravin Balakrishnan

University of Toronto

Flash Video

Facile interaction with displays all over the place

As computing increasingly veers away from the desktop to more mobile and "everywhere" usage scenarios, the user interface must evolve to better support such activities. In this talk I will provide a broad overview of some of the more promising research being undertaken in the area of next-generation user interfaces for future computing environments, illustrated with examples from the work being undertaken at the Department of Computer Science, University of Toronto. This will include interaction using handheld projectors, sketch and gesture based interfaces, inerfaces for very large scale but expensive displays, interfaces for very cheap "displays" all over the place, and supporting infrastructure.

Speaker: Ravin Balakrishnan is an Associate Professor of Computer Science and Canada Research Chair in Human-Centred Interfaces at the Department of Computer Science, University of Toronto, where he co-directs the Dynamic Graphics Project (DGP) laboratory and serves as the department's Associate Chair for Research and Industrial Relations. He is also a member of the Knowledge Media Design Institute (KMDI). His research interests are in Human Computer Interaction (HCI), Information and Communications Technology for Development, and Interactive Computer Graphics. He earned his Ph.D. in Computer Science from the University of Toronto in 2001, working with Bill Buxton. While doing his Ph.D., from 1997-2001 he was concurrently a part-time researcher at Alias|wavefront (now part of Autodesk). He is the recipient of an Alfred P. Sloan Research Fellowship (2007), an Ontario Premier's Research Excellence Award (2003), the Bell University Laboratories Associate Chair in HCI at the University of Toronto (2002-2006), and best paper awards and honourable mentions at the CHI 2008,CSCW 2006, UIST 2006, CHI 2005, Graphics Interface 2005 and UIST 2004 conferences. In addition to working with students and colleagues at Toronto, he collaborates with researchers at leading industrial laboratories and universities worldwide, including stints as a visiting researcher at Mitsubishi Electric Research Laboratories (MERL) (2005-2007), a visiting professor at the University of Paris & INRIA (2006), and most recently a visiting researcher at Microsoft Research's Redmond, Beijing, Bangalore and Cambridge labs while on sabbatical from the University of Toronto during the 2007-2008 academic year. He is also involved in two startups that are commercializing research conducted in his lab: Sketch2 Corp. and Bump Technologies Inc. Further information, including publications and videos demonstrating some of his research, can be obtained from www.dgp.toronto.edu/~ravin

Host: Chia Shen

Prof. Shalom Lappin

King's College London

Flash Video

Restricting Distributions for Computational Language Learning

Joint work with Alex Clark of Royal Holloway College, London

Classical computational learning models like Gold's (1967) identification in the limit paradigm and PAC learning require learning under all possible probability distributions over data samples. By modifying PAC learning to restrict the set of possible distributions,
it is possible to show that different classes of languages are learnable than in the distribution free framework. I will explore some recent work on distribution based language learning. Clark and Thollard (2004) prove that when the set of distributions is limited to those produced by Probabilistic Deterministic Finite State Automata, then the class of regular languages is PAC learnable from positive evidence only. Clark (2006) demonstrates a similar result for an interesting subclass of context free languages when the set of distributions corresponds to a specified set of Probabilistic Context Free Grammars. I will then discuss how this approach might be used to increase the range of evidence available for learning. Clark and Lappin (2009) suggest that an appropriate restriction on the set of possible distributions for PAC learning could provide the basis for a stochastic model of indirect negative evidence.

Speaker:  Shalom Lappin is Professor of Computational Linguistics. He received his BA in Philosophy at York University, Toronto Canada (1970), and his MA (1973) and PhD (1976) in Philosophy at Brandeis University. He taught philosophy at Ben Gurion University of the Negev (1974-1980), Linguistics at the University of Ottawa (1980-84), where he was Chair of the Linguistics Department (1981-84), and linguistics at the University of Haifa (1984-88) and Tel Aviv University (1988-89).

He was a Research Staff Member in the Natural Language Group of the Computer Science Department at IBM T.J. Watson Research Center (1989-93). He then took up a position in the Linguistics Department at SOAS, University of London (1993-99). He came to the Philosophy Department at King's in 1999, and then moved to the Computer Science Department, where he was head of the Natural Language Processing Group (2000-05). In September, 2005 he returned to the Philosophy Department.

His areas of research and teaching are formal and computational semantics, formal grammar, natural language processing, and logic. His current research activities include the formal foundations of semantics, type theory, machine learning, and the cognitive basis of natural language.

Host: Prof. Stuart Shieber

David Pogue

Technology Columnist, New York Times

Web 2.0 Reality Check

What do YouTube, MySpace, eBay, and Craigslist have in common? They're all part of "Web 2.0," in which a Web site's material is supplied by its visitors. In this head-spinning talk, David Pogue, the New York Times's tech columnist, helps to make sense of the explosively expanding realm of Web 2.0. He'll advise both individuals and companies on how to exploit these live-wire technologies, supply some horrifying and hilarious real-world stories, and hint at the future, the pitfalls, and the rewards of these revolutionary new channels.

Speaker: David Pogue is the personal-technology columnist for the New York Times. Each week, he contributes a print column, an online column, an online video and a popular daily blog, “Pogue’s Posts.”  David is also an Emmy award-winning tech correspondent for CBS News, and he appears each week on CNBC with his trademark comic tech videos.

With over 3 million books in print, David is one of the world’s bestselling how-to authors. He wrote or co-wrote seven books in the “for Dummies” series (including Macs, Magic, Opera, and Classical Music); in 1999, he launched his own series of complete, funny computer books called the Missing Manual series, which now includes over 100 titles.

David graduated summa cum laude from Yale in 1985, with distinction in Music, and he spent ten years conducting and arranging Broadway musicals in New York. In 2007, he was awarded an honorary doctorate in music from Shenandoah Conservatory.
He’s been profiled on both “48 Hours” and “60 Minutes.” He lives with his wife and three young children in Connecticut. His web site is www.davidpogue.com.

April 2, 2009

Prof. Victor Zue

MIT - Computer Science and Artificial Intelligence Laboratory

Flash Video

Talking with Computers

Speech is one of the most natural ways or humans to communicate. Therefore it is not surprising that pundits and Hollywood producers have been predicting for decades that natural spoken communications with computers is just around the corner. However, this promise has largely been unfulfilled. In this presentation, I want to argue a reason for this failure is that we have been working on the wrong problem. Rather than working on recognition alone, we need to focus on the issue of communication. I will reinforce my argument by demonstrating some of the research being conducted at MIT in the area of information retrieval in diverse domains such as weather, flights, restaurants, entertainment, and diverse platforms such as laptops, telephones, or mobile Internet devices. I will also touch on other applications of speech technology such as foreign language learning, speaker identification, and multimodal integration.

Speaker: Victor Zue received his ScD from MIT in 1976 and has been at MIT ever since. He is the Delta Electronics Professor of Electrical Engineering and the Director of the Computer Science and Artificial Intelligence Laboratory. In the early part of his career, Victor conducted research in acoustic-phonetic and phonological analyses of American English. Subsequently, his research interest shifted to the development of spoken language interfaces to make human-computer interactions easier and more natural. Between 1989 and 2001, he headed the Spoken Language Systems Group at the MIT Laboratory for Computer Science, which has pioneered the development of many systems that enable a user to interact with computers using spoken language.

Outside of MIT, Victor has served on many planning, advisory, and review committees for the U.S. federal government and for many multinational corporations. From 1996 to 1998, he chaired the Information Science and Technology Study Group for the Defense Advanced Research Projects Agency of the U.S. Department of Defense, helping the DoD formulate new directions for information technology research. In 1999, he received the DARPA Sustained Excellence Award. Victor is a Fellow of the Acoustical Society of America, a Fellow of the International Speech Communication Association, and a member of the U.S. National Academy of Engineering. He is also an Academician of Academia Sinica of Taiwan.

Host: Prof. H.T. Kung

April 9, 2009

Andy Wilson

Microsoft Research

Flash Video

Riffing on Surface

What started as a modest incubation effort has grown into the Surface Computing group at Microsoft. Surface, its first product, is but one example of an exciting new category of form factors and user experiences. In this talk I would like to present a number of research projects that share the Surface Computing vision but push in different directions. For example, PlayAnywhere is a compact tabletop projection-vision system which explores a number of new interactions on everyday surfaces, while TouchLight combines a transparent projection screen material with computer vision techniques, and FourBySix allows multiple designers to gather around a large-format Surface. We've even brought Surface technology to spherical displays, and, most recently, dome projection displays. In addition to new form factors, we are also examining ways to structure Surface interactions that go beyond traditional point cursor models. For example, Surface input may be embedded in a gaming physics simulation to obtain realistic manipulations based on friction and collisions. Finally, I will describe some recent work applying newly developed range-sensing cameras to enable new interactions above the surface. All of these new systems have the potential of changing the way we relate to computing, but they also pose serious challenges because they are so different from today's desktop computing systems.

Speaker: Andy Wilson is a Senior Researcher at Microsoft Research. There he has been applying sensing technologies to enable new styles of human-computer interaction. His interests include gesture-based interfaces, computer vision, inertial sensing, display technologies and machine learning. In 2002 he helped found the Surface Computing group at Microsoft. Before joining Microsoft, Andy obtained his BA at Cornell University in 1993, and PhD at the MIT Media Laboratory in 2000. Publications and videos of his work are located at http://research.microsoft.com/~awilson.

Host: Prof. Hanspeter Pfister

Prof. Robin Murphy

Texas A&M University

Flash Video

Being There

Being at disasters is the apotheosis of field robotics; hardware and software must work with real people under challenging temporal and environmental conditions.  We have shifted over the past 10 years from traditional hypothesis-driven, top-down research to a bottom-up approach where research questions are extracted from field experiences. The types of questions and ideas that arise for robotics from “being there” are illustrated through the 11 incidents where we have deployed robots, including the 9-11 World Trade Center disaster, Hurricane Katrina, the Crandall Canyon Utah mine collapse, and the Cologne, Germany, archive collapse. Three major themes have emerged.  One is that new types of mobility are needed, especially tethered robots, legs, and snake robots. A paradigmatic theme is that rescue robots, and possibly all robots, are part of joint cognitive systems. A third, unfortunate, theme is confirmation of Norman’s scathing assessment that “roboticists automate what is easy and leave the rest to the human,” leading to poor designs.  The solution to Norman’s assessment is systems-level thinking. Extensive videos will be shown to illustrate the lessons learned.

Speaker: Robin Roberson Murphy received a B.M.E. in mechanical engineering, a M.S. and Ph.D in computer science in 1980, 1989, and 1992, respectively, from Georgia Tech, where she was a Rockwell International Doctoral Fellow. She is the Raytheon Professor of Computer Science and Engineering at Texas A&M and directs the Center for Robot-Assisted Search and Rescue. Her research interests are artificial intelligence, human-robot interaction, and heterogeneous teams of robots. In 2008, she was awarded the Al Aube Outstanding Contributor award by the AUVSI Foundation, for her insertion of ground, air, and sea robots for urban search and rescue (US&R) at the 9/11 World Trade Center disaster, Hurricanes Katrina and Charley, and the Crandall Canyon Utah mine collapse.  She is an associate editor for IEEE Intelligent Systems, a Distinguished Speaker for the IEEE Robotics and Automation Society, and is currently on the Defense Science Board, and has served on numerous others, including the USAF SAB, NSF CISE Advisory Council, and DARPA ISAT.

Host: Prof. Yiling Chen

Prof. Johannes Gehrke

Cornell University

What Can Database Systems Do For Computer Games?

Databases have the stigma of an association with (boring) enterprise data management. The area of database research, however, has developed a wide set of concepts and techniques with applicability much beyond exam questions about departments and employees.

In this talk, I will show how the idea of declarative processing from databases can be applied to computer games. I will describe our journey from declarative to imperative scripting languages for computer games, and I will introduce the state-effect pattern, a design pattern that enables game developers to design games that can be programmed imperatively, but processed declaratively. I will then introduce Scalable Games Language (SGL), our scripting language for games, and I will outline how database techniques can be used to process SGL resulting in performance improvements of an order of magnitude or more compared to standard scripting languages.

Speaker: Johannes Gehrke is an Associate Professor in the Department of Computer Science at Cornell University. Johannes' research interests are in the areas of data mining, search, data privacy, complex event processing, and applications of database and data mining technology to marketing and the sciences. Johannes has received a National Science Foundation Career Award, an Arthur P. Sloan Fellowship, and IBM Faculty Award, The Cornell College of Engineering James and Mary Tien Excellence in Teaching Award, and the Cornell University Provost's Award for Distinguished Scholarship. He is the author of numerous publications on data mining and database systems, and he co-authored the undergraduate textbook Database Management Systems (McGraw Hill 2002), currently in its third edition and used at universities all over the world. Johannes is also an Adjunct Associate Professor at the University of Tromso in Norway.

Johannes was Co-Chair of the 2003 ACM SIGKDD Cup, Program Co-Chair of the 2004 ACM International Conference on Knowledge Discovery and Data Mining (KDD 2004), and Program Chair of the 33rd International Conference on Very Large Data Bases (VLDB 2007). From 2007 to 2008, he was Chief Scientist at FAST, A Microsoft Subsidiary.

Host: Prof. Greg Morrisett

April 30, 2009 -- JOINT CS/IIC

NOTE CHANGE OF LOCATION TO 60 Oxford St., Rm. 330

Jennifer Tour Chayes

Microsoft Research New England

Flash Video

Interdisciplinarity in the Age of Networks

Everywhere we turn these days, we find that networks have become increasing appropriate descriptions of relevant interactions.  In the high tech world, we see the Internet, the World Wide Web, mobile phone networks, and a variety of online social networks.  In economics, we are increasingly experiencing both the positive and negative effects of a global networked economy.  In epidemiology, we find disease spreading over our ever growing social networks, complicated by mutation of the disease agents.  In problems of world health, distribution of limited resources, such as water resources, quickly becomes a problem of finding the optimal network for resource allocation.  In biomedical research, we are beginning to understand the structure of gene regulatory networks, with the prospect of using this understanding to manage the many diseases caused by gene mis-regulation.  In this talk, I look quite generally at some of the models we are using to describe these networks, processes we are studying on the networks, algorithms we have devised for the networks, and finally, methods we are developing to indirectly infer network structure from measured data.  In particular, I will discuss models and techniques which cut across many disciplinary boundaries.

Speaker: Jennifer Chayes is Managing Director of Microsoft Research New England.  Her research areas include phase transitions in discrete mathematics and computer science, structural and dynamical properties of self-engineered networks, and algorithmic game theory.  She is the coauthor of over 100 scientific papers and the co-inventor of over 20 patents.

She serves on numerous institute boards, advisory committees and editorial boards, including the Turing Award Committee.  Chayes received her Ph.D. at Princeton, and held postdoctoral fellowships at Harvard and Cornell.  She is the recipient of the NSF Postdoctoral Fellowship, the Sloan Fellowship, and the UCLA Distinguished Teaching Award.  Chayes is a Fellow of the AAAS and the Fields Institute, and a National Associate of the National Academies.

PREVIOUS SEMESTERS

Fall 2008

September 18, 2008

Walter Bender

In 1900, the German mathematician David Hilbert posed 23 problems in mathematics that were very influential to 20th century mathematics. Subsequently, variants of this device have been used to draw attention to additional challenges in mathematics and in other disciplines. I will use his device to draw attention to a number of problems -- perhaps not as intractable as the Riemann hypothesis -- facing the intervention of technology on learning. Topics range from computer science and engineering to the social sciences, economics, and education.

Speaker: Walter Bender is the founder of Sugar Labs, a non-profit foundation that serves as a support base for the community of educators and software developers who are extending the Sugar user interface. Sugar is designed to enhance the primary educational experience by emphasizing collaboration and expression. Prior to that, Bender was president for software and content of the One Laptop per Child association. Before taking a leave of absence from MIT, Bender was executive director of the MIT Media Laboratory. Bender is currently on sabbatical from MIT, where he is a senior research scientist and director of the Electronic Publishing group. He received his BA from Harvard University in 1977 and his MS from MIT in 1980.

Host: Prof. Harry Lewis

Prof. Gerome Miklau

A network data set represents entities and the connections between them. Network data can describe a variety of domains: a social network describes individuals connected by personal relationships; an information network might describe a set of articles connected by citations; a communication network might describe Internet hosts related by traffic flows. Network data is extremely valuable to analysts seeking to understand the structure and function of networks and processes that occur in networks. Network analysts study the influence of individuals in organizations, disease transmission in communities, the operation of computer networks, and the emergent behavior of physical and biological systems. While network data can now be collected in unprecedented scale, it often describes relationships that are sensitive. Releasing the data can result in unacceptable disclosures, and privacy concerns are constraining network science.

In this talk, I will describe threats to anonymity posed by published networks, and recent work on resisting these threats. I will focus on the threat of structural re-identification, in which an individual's local relationships can be identifying even when names (and other identifiers) are removed from the network. Re-identification risk depends on the power of the adversary and also the naturally-occurring structural diversity in the graph. I will describe models of adversary knowledge and evaluate their impact on anonymity using both empirical results on real networks and the theoretical analysis of random graphs. Finally, I will describe an anonymization technique based on graph clustering which can accurately preserve global properties of networks while protecting against anonymity threats.

Speaker: Gerome Miklau is an Assistant Professor at the University of Massachusetts, Amherst. His primary research interest is secure data management: providing privacy, confidentiality, and integrity guarantees for data in relational databases and data exchanged on the World Wide Web. He received an NSF CAREER Award in 2007 and won the 2006 ACM SIGMOD Dissertation Award. He received his Ph.D. in computer science from the University of Washington in 2005. He earned bachelor's degrees in mathematics and in rhetoric from the University of California, Berkeley, in 1995.

Host: Prof. Margo Seltzer