BUCAN Newsletter for Summer 2003

In this issue...

Congratulations and Welcome BUCS Class of 2003!

In my remarks to the 2003 graduating class, I noted that:

The class of 2003 will always hold a special place in our Department’s collective memory. The class of 2003 is the first to graduate in this third decade of our department history. The class of 2003 represents the largest graduating class in our department history (116 BA graduates, 24 MA graduates, and 6 PhD graduates). The class of 2003 has been a catalyst of growth for the department: almost one half of today’s CS faculty joined our department after most of you declared CS to be your major! And, when this class of 2003 comes back for its fifth reunion, each and every one of you will be welcomed in a brand new Computer Science Department building at the heart of the Charles River Campus.

What I did not mention is that this class is also one that will go in our books as one with the best academic achievements yet! Of the 116 students who graduated with a BA degree, 4 graduated Summa Cum Laude, 17 graduated Magna Cum Laude, 29 graduated Cum Laude, and 7 were elected as members in Phi Beta Kappa. These achievements are a testament not only to the individual hard work of the students who earned them, but also to the level of excellence that our department has reached in its short twenty year history.

The 2003 CS Convocation ceremonies reflected the special status of the class of 2003. The ceremonies were held at the brand new Trustees Hall and featured a reflective student speech by Ryan Mahon CAS'03, and an inspiring speech by Microsoft VP J Allard, CAS'91. Pictures from these ceremonies are available from http://www.cs.bu.edu/misc/Graduation2003.

As I welcome the Class of 2003 to the Computing Alumni Network of Boston University, I wish to emphasize how important it is to stay in touch with your department. As you begin a new journey in life, remember that you are carrying the hopes and dreams of many people---friends, family, and yes CS faculty members. We are proud of you and we hope that you will always remember with pride your Alma Mater and your department for many years to come.

Sincerely,

Azer Bestavros

Associate Professor and Chairman
CS Department, Boston University

J Allard (BA'91) of Microsoft receives CAS Distinguished Alumni Award

In his induction of J Allard (CAS'91) into the Arts and Sciences Collegium and Academy of Distinguished Alumni, John W. Connery (CAS'69) noted that

Hired at Microsoft in 1991, straight out of Boston University’s Computer Science Department, Allard soon got the attention of Bill Gates by advocating a stronger Internet presence for Microsoft, and he has been a major influence on the company’s Internet strategies ever since. In a 1993 memo to top executives, "Windows: The Killer Application for the Internet," Allard outlined the challenge facing Microsoft: to develop products that would make the Internet as seamless and easy to use as the company’s Windows operating system made desktop computing.

J Allard (pictured above with his wife Rebecca Norlander, also CS Class of 1991) has earned the reputation of “Microsoft’s Father of the Internet” because of his major influence on the company’s online strategy during his 11 years with the company. Allard and his team developed an FTP and Web server for Windows NT and created and managed ftp.microsoft.com and www.microsoft.com for close to a year before transitioning it to a more "official" home. He also started the company's web server initiative -- Internet Information Server -- which has become the most widely adopted commercial Internet server product today, running some of the largest businesses on the Internet. Allard helped establish the strategy for the Next Generation Windows Services.

After leading the company in its successful Web initiatives for most of the 1990s, he turned his attention back to his computing roots—videogames, which he sees as the beginning of, and model for, a whole range of new, software-driven entertainment products coming over the horizon. Today, as Vice President of the Xbox Platform, Allard oversees operating systems, hardware, and online strategies, assuring the best game play over the Internet will be incorporated into the game console.

As he told Bostonia magazine recently, “I firmly believe that in twenty years, entertainment will become a software business.” And J Allard will no doubt be right in the middle of it.

Congratulations to J for being the first Computer Science graduate to be inducted in the CAS Collegium of Distinguished Alumni!

20th Anniversary Colloquia debuts with Dick Karp's talk on Sensor Networks

On Wednesday, April 30, the department was host to an all-day (and all evening) visit by Richard M. Karp, one of the world's pre-eminent computer scientists. Dick is University Professor at the University of California at Berkeley, and is a member of both the National Academy of Sciences and the National Academy of Engineering. In 1985 Dick Karp was awarded Computer Science's highest award, the ACM Turing Award, for his seminal work on reductions between NP-complete problems. In 1996 he received the National Medal of Science, the nation's highest scientific award bestowed annually by the President of the United States.

Dick spent the day visiting with old acquaintances, including his former Ph.D. student, John Byers (now on our faculty), and making new acquaintances. The highlight of the day, and the primary reason for his visit, was his technical talk, which kicked off the year-long Colloquium Series celebrating the 20th Anniversary of Computer Science at Boston University (check http://www.cs.bu.edu/lectures for details of this series). Dick spoke about the algorithmic challenges in addressing a central problem in sensor networks, namely clock synchronization, and described a solution drawing on a diverse set of techniques from network flow theory, electric circuit theory and optimization. The highlight of the evening was a wonderful dinner at the Top of the Hub with Professors Bestavros, Byers, Gacs, Levin and Teng.

The purpose of the BUCS 20th Anniversary Colloquium Series is to bring to campus some of the most prominent computer scientists in order to introduce them (and in many cases to re-introduce them) to the department so that they may see first-hand how far the department has come along, and in order for the department to hear of their impressions and feedback on the department's ambitions for the coming years.

On that score, at the end of his visit, Dick Karp commented that "[his] appreciation of the exceptional qualities of [our] department now eclipses what [he] knew of it only 8 hours ago!"

Future speakers in this special 20th Anniversary Colloquium include Michael Rabin of Harvard University, Jon Crowcroft of Cambridge University, Albert Meyer of Massachusetts Institute of Technology, Margaret Wright of New York University,  Rohit Parikh of City University of New York, and   Christos Faloutsos and Takeo Kanade of Carnegie Mellon University.

Leonid Levin receives prestigious SIAM Outstanding Paper Award

Professor Leonid Levin and co-authors will share the 2003 "Outstanding Paper Prize" of the Society for Industrial and Applied Mathematics awarded at the SIAM Annual Meeting in Montreal, June 16-20, 2003. These prizes, awarded annually since 1999, are given for the most influential papers published in the 13 SIAM journals during the four years prior to the year of the award. More information on SIAM's Outstanding Paper Award is available from http://siam.org/prizes/outstanding.htm. The prize-winning paper was published in SIAM J. on Computing in 1999. It proves the equivalence between two fundamental problems in Computing Theory.

The first problem is the existence of one-way functions. One-way functions are those that are easy to compute but very hard to invert. In the words of Professor Levin, while everybody who deals with kids (or politics :-) knows that many things are much easier to do than to undo, no hard proof exists of this seemingly obvious fact in computing theory.

The second problem is the possibility of (seemingly paradoxical) deterministic generation of perfectly random data that are indistinguishable, even in theory, from those obtained by coin flips. In the words of Professor Levin, while many magical algorithms in computer theory and practice (e.g., in cryptography and security) rely on our ability to come up with such seemingly perfect pseudo-random generators, again no hard proof exists about whether this is possible or not.

The equivalence of the two problems is important because it implies that we can trust the magic of deterministic randomness and all of the practical applications it enables, unless all transformations can be undone as easily as done (which would be quite shocking).

Shanghua Teng's collaboration with Spielman featured in MIT Technology Review

Cited in 2001 by the National Science Foundation for his influential research shedding light on the Simplex method "which defied complete understanding for over 50 years", Shanghua Teng and his collaborator Dan Spielman of MIT  were featured on the pages of MIT Technology Review's most recent issue (available on the web at http://www.technologyreview.com/articles/vandre0603.asp).

In an article entitled "The Simplex Solution: The mission to improve the widely used simplex-method algorithm showed instead why it works so well", Teng and Spielman (pictured on the right) share with readers how they managed to stumble on why the simplex method (widely used in many computational applications) works so well in practice, when classical approaches to analyzing its performance predict otherwise. They did it by developing a new way to analyze the algorithm. Until their discovery, the efficiency of an algorithm was measured by quantifying worst-case behaviors, in which an algorithm is given the most difficult data and then judged on how well it can calculate with it.

The MIT Technology Review explains this as follows:

It would be as if someone handed you the worst possible long-division problem you could imagine and then tested to see whether you could solve it and how long it would take. But this just didn’t work with the simplex method. So Spielman and Teng found a new approach. They introduced some variability into worst-case analysis. Instead of using exact numbers as inputs to test the algorithm, they allowed imprecision. For example, if the input was 1.31, they allowed a random input between 1.29 and 1.33. They discovered that by allowing for imprecision, the simplex algorithm always efficiently solved the problem, and that is why it has been so successful.

Shanghua Teng teaches algorithms and computational geometry courses to at Boston University. His research is supported by multiple grants from the National Science Foundation.

Leo Reyzin pushes the envelop of security by making cryptography go physical

Leonid Reyzin Photo by Vernon DoucetteYour internet browser is probably equipped with the some of the latest cryptographic technology available, so that no eavesdropper along the way can read the secrets you send. You may think you are safe: after all, today's cryptography provides mathematical assurances that communications will be protected against all kinds of attackers: ones that intercept and substitute messages, perform sophisticated computations, and even send maliciously constructed junk to unsuspecting computers.

How would you feel then if, all the sophisticated math notwithstanding, someone with a radio receiver could pick up your secret key from 40 feet away?

An emerging class of attacks on security systems bypasses mathematical security by physically observing the computation being performed. For example, people have been able to successfully recover secret keys by measuring the power consumption of smart cards or radio signals emitted by circuits.

Today's cryptography can provide rigorous mathematical assurances that communications will be protected . However, one class of attacks that gained strength recently has defied mathematical modeling: namely, attacks that observe the physical characteristics of a computation (as opposed to merely its input/output behavior). For example, people have been able to successfully recover secret keys by observing the power consumption of smart cards or by measuring electromagnetic radiation emitted by servers.

The surprising power of these physical attacks threatens to undermine the relevance of today's cryptography. To address them, Leo Reyzin, jointly with Silvio Micali of MIT, has proposed "Physically Observable Cryptography": a way to incorporate physical observations performed by the adversary into mathematical models of cryptography. Now that a sound framework has been created, work can commence on building protection against such physical attacks. Indeed, some preliminary results on pseudorandom generation and digital signatures have already been obtained under this framework.

A joint $4M proposal from Boston University and MIT to pursue research on Physically Observable Cryptography is currently under consideration by the National Science Foundation's Information Technology Research (ITR) program.

Undergraduate student group launches the Video Game Creators' Consortium

Late afternoon, on a freezing Tuesday in January, walking back from a classroom in the GCB building with Professor Bestavros after a CS-350 lecture on how interrupts are used to coordinate I/O events and inter-process communication, Ben Waber a Computer Science sophomore asked if it would be possible for the department to subsidize a weekly "Pizza and Pop" meeting of undergraduate students who share a common interest in creating video games. Ben managed not only to get an approval for funding his student group meeting, but also to recruit Professor Bestavros as the group's faculty advisor.

The "Video Game Creator Consortium" (VGCC) meetings went on for the entire semester, sometimes lasting till late into the night, with occasional cheers of excitement heard a few rooms down the hall when a cool feature "works"! And, by the end of the semester, VGCC had already made their mark in the department, by organizing a couple of workshops: one on "Multithreading" and another one on "Artificial Intelligence", by developing a game called "Bouncer" for Professor Margrit Betke to help with her work in Human Computer Interfaces, by getting engaged in testing HCI software for the Image and Video Computing group, and by holding a number of social events, including of course some video game tournaments :-)

For more information, please visit the group's web page at http://cs-people.bu.edu/dhirsh/VGCC

Contributions Solicited to the BUCS Alumni Hall of Fame!

On many occasions--for example in meetings with prospective students and their parents and in trying to establish ties with industrial partners--it is handy to highlight successes and achievements of our alumni body. While we know of many examples, we are certain that there are many more success stories that we are not fully aware of and which would be beneficial to highlight. To that end, we are seeking your help!

Please send us (self) nominations for BUCS Alumni to be included in our "BUCAN Hall of Fame". A few examples are already available at http://www.cs.bu.edu/CAN/profiles.

Please send your contribution to this effort to bucan-admin@cs.bu.edu and thanks in advance!

Note: You are receiving this quarterly newsletter because you are a registered member of BUCAN and/or you have been identified as somebody who may be interested in staying in touch with the Computer Science Department at Boston University. If you prefer not to receive such a newsletter, please let us know by contacting us at <bucan-admin@cs.bu.edu>