MIDAS: A Golden Opportunity in Russia

By Rob Knies, Senior Editor, Microsoft Research

Collaboration is one of the hallmarks of Microsoft Research. Across the organization, the desire to work with world-class computer scientists takes on many forms, all with the express interest of advancing the state of the art in computer science and related fields. Such efforts present a myriad of challenges, but the rewards and the collegiality thus engendered regularly prove invaluable.

The latest example begins Aug. 8 in St. Petersburg, Russia, where Microsoft Research, in cooperation with St. Petersburg State Polytechnic University and the Academic Physics and Technology University, presents the Microsoft Data Structures and Algorithms School (MIDAS), which runs through Aug. 14.

The event comes on the heels of a successful Russian Summer School for High Performance and Parallel Computing, held in Moscow in July 2009. The popularity of that gathering provided impetus for this year’s school, as explained by the school director, Andrew V. Goldberg of Microsoft Research Silicon Valley.

“My goal as a school director,” says Goldberg, a principal researcher, “was to bring together leading scientists in the area and excellent students to provide a unique opportunity for learning and social networking. This goal has been achieved.”

The achievement is demonstrated by the level of expertise among the individuals who will be conducting the school’s classes—and by the enthusiasm displayed by the 62 students accepted for the weeklong seminar. Such factors get an approving nod from Nikolay Pryanishnikov, president of Microsoft Russia.

“When it comes to e-society development, it is important to prepare prospective professionals for the Russian IT industry,” Pryanishnikov says. “The Microsoft summer school is a unique project and provides valuable input to the market demand. It is a practical instrument for science-ecosystem development and a good opportunity for young specialists to improve their knowledge and achieve their professional goals.

“We can see a high interest in the project among students and young scientists in Russia, and that tells us that the school is highly anticipated by the audience and the market.”

A 14-person organizing committee, consisting mainly of academic and industrial officials from Russia, made the plans for this year’s school. Among the committee members, in addition to Goldberg, are Fabrizio Gagliardi, a Swiss-based director of the External Research division of Microsoft Research; Rostislav Yavorskiy, an External Research program manager headquartered in Moscow; and Ilya Mironov, a Microsoft Research Silicon Valley researcher.

“External Research is very much about outreach to the wider scientific community,” Gagliardi says, “and by organizing schools in collaboration with prestigious institutes, we address this goal. It’s also important to connect senior Microsoft Research scientists, such as Andrew Goldberg, to outside scientists and expose them to other researchers and students. This view is shared by Microsoft Research senior management, as demonstrated by the presence last year of Dan Ling [Microsoft Research vice president] and, this year, Andrew Herbert [Microsoft distinguished engineer and managing director of Microsoft Research Cambridge].”

Goldberg elaborates:

“MIDAS and other Microsoft Research-sponsored schools are a part of the External Research activities in Russia,” he says, “which also include collaborative research projects, interns from Russia, and academic exchange programs. The schools contribute to computer-science education in Russia, expose students to leading experts in the field, and help to establish new ties and collaborations.”

The school is free for the accepted applicants—a collection of advanced undergraduates, Ph.D. students, and young scientists and developers interested in data structures and algorithms.

“Due to the high quality of the lecturers and the reputation of the previous summer school, interest in the school was high as soon as it was announced,” Goldberg reports. “In spite of strict admissions criteria, we got many more applications from qualified individuals than we could accept. The acceptance ratio was almost 1-in-4. The accepted students, coming from 25 separate institutions, are advanced undergraduates, graduate students, and a few recent graduates working in industry.”

Alexander Daynyak of Moscow State University, one of the students who will be participating in this year’s school, provides a cogent view of the value of such an opportunity.

“For us, as specialists who have just begun their way into their careers, it is very important to participate in events with as high a status and as many opportunities as the Microsoft summer school,” Alexander says. “Beside the great honor of being chosen to participate in the event, it is an outstanding experience for us.

“It gives us an opportunity to get useful information from high-level, worldwide experts and to find new coworkers and friends. We have common goals and tasks with the honored scientists here: to develop our Russian scientific platform and to develop a new vision of some aspects. It is a great atmosphere here, because we are united by this great idea.”

Such a reputation was forged initially by the 2009 school, Gagliardi explains.

“It was pretty impressive,” he says. “More than 80 students worked for five days around the clock. We had an impressive list of lecturers from Microsoft Research and beyond. Moscow State University provided a prestigious site and excellent organization, and we received significant visibility with Russian authorities and scientists.”

There’s also more than a bit of fun to be had by participants. This year, for example, the students will be participating in an exercise in algorithmic design and engineering by developing and implementing an algorithm for a well-defined problem, Using Landmarks to Estimate Distances in a Graph. While the problem might be well-defined, the project is open-ended, because it has not yet been determined what the best solution is.

Teams with three or four students each will be competing in the project. The winning team will get an opportunity to present its solution on Aug. 13.

MIDAS got its inception when Goldberg heard about the first instance of the Russian summer school.

“Algorithms and data structures constitute a fundamental area of computer science that is underrepresented in Russia,” he explains. “There are many students with strong backgrounds, but there remains a need for additional faculty with expertise in this area.

“When I learned that Microsoft Research was starting a summer-school program in Russia, I felt that there would be strong interest in such a school from the prospective students—and that I could put together an outstanding team of lecturers for the school. I proposed the topic to Dan and Fabrizio, and they supported it.”

Indeed, the five courses to be taught during MIDAS will be led by a prestigious collection of educators and researchers—including a recipient of the A.M. Turing Award:

• Algorithms on Large Data Sets, by Giuseppe F. Italiano: The course, to be led by a full professor of Computer Science and chair of the Department of Information, Systems, and Production at the Universita di Roma “Tor Vergata.” He will present algorithms and data structures for efficiently solving problems on data sets of the order of terabytes, or even petabytes.
• Case Studies: The Traveling Salesman and Bin Packing Problems, by David S. Johnson: Johnson, head of the Algorithms and Optimization Department at AT&T Labs-Research, will discuss a pair of research problems that have served as key test beds for the introduction of new algorithmic approaches and modes of analysis, particularly in the area of approximation algorithms.
• Combinatorial Optimization Algorithms, by Clifford Stein: Algorithms, both exact and approximate, for several fundamental problems in combinatorial optimization, will be introduced by Stein, professor and chair of the Industrial Engineering and Operations Research Department at Columbia University.
• Data Structures, by Robert E. Tarjan: Tarjan is James S. McDonnell Distinguished University Professor of Computer Science at Princeton University, co-director of the National Science Foundation for Discrete Mathematics and Theoretical Computer Science, and senior fellow at Hewlett-Packard, where he is a member of the Office of Strategy and Technology. A winner of the Turing Award in 1986, he will instruct students on classical data structures and their recent variants, binary search trees and heaps.
• Shortest Paths and Experimental Evaluation of Algorithms, by Renato F. Werneck. A researcher with Microsoft Research Silicon Valley, Werneck will present an overview of recent algorithms for computing point-to-point shortest paths, with an emphasis on road networks.

“The lecturers are top scientists and educators from the United States and Europe, recognized by the scientific community as leaders in the area,” Goldberg says. “The list includes a U.S. National Academy of Science member and a Turing Award winner, and, in Herbert, a fellow of the U.K. Royal Academy of Engineering. There are also two university department chairs, an industrial algorithms-department director, Association for Computing Machinery fellows, winners of many other prestigious awards, and an author of the most widely used algorithms textbook. All of them are active scientists and good lecturers.”

In addition, Herbert will discuss the research areas being explored at Microsoft Research Cambridge.

“Russia is an important new area for Microsoft Research,” he says. “We have had a growing number of collaborations with Russian institutions in recent years and a steady flow of interns from Russia to Redmond and Cambridge. The summer school we run, supported by Microsoft Russia, is becoming an important annual event. I’ll be giving an overview of hot topics at Cambridge relating to cloud computing, inference, and natural user interfaces.”

Herbert’s participation, Goldberg notes, represents a sign of Microsoft’s commitment to education and basic research.

“It is important to have a high-profile Microsoft Research representative to give a talk about Microsoft Research activities,” he says. “As a director of Microsoft’s research laboratory in Europe, arguably the best industrial laboratory in Europe doing basic research in computer science, Andrew makes a great choice, and I am very glad that he agreed to give a talk.”

After an evening reception at St. Petersburg’s Angleterre Hotel, students and instructors begin work in earnest on Aug. 9, with five days chockfull of lectures, question-and-answer sessions, homework and the programming project.

Given the sheer intellectual wattage to be gathered, the school has generated interest in major, nationwide Russian media, include Mail.Ru, a popular general-interest site; CNews, a prominent tech website; and Rossiyskaya Gazeta, the daily newspaper of record for the Russian government.

Such attention has Goldberg thinking of ways to measure the success of this year’s school.

“On the objective side, the school will have homework and the programming project, so we can see how well the students learned,” he says. “We will distribute questions to gauge student satisfaction. New social connections are harder to measure objectively.

“The school will contribute to Microsoft Research visibility and highlight Microsoft’s commitment to research. We expect to see applications from the graduates for internship positions at Microsoft, and we will be able to better evaluate these applications. Contact developed during the school will help in attracting strong applicants to the next school, as well as facilitating future collaborations.”

Opens in a new tab