No Better Time Page 5

  At the age of fifteen, Tom Leighton set out to solve the conjecture for his junior year science project. He didn’t succeed, but learned a lot of math in the process. He also landed a spot in the National Science Fair. In 1974, Leighton was selected as a finalist in the Westinghouse Science Talent Search (now the Intel Science Talent Search), for which he earned a scholarship to college. As the valedictorian of his class, Leighton had many colleges to choose from. He settled on Princeton University, beginning his freshman year in 1975. Leighton wanted to major in math, but his father, a practical man, steered him toward engineering, which he felt would offer his son much more lucrative career prospects. But Leighton’s love for math couldn’t be tempered, so he compromised by majoring in both electrical engineering and computer science and by taking courses mostly centered on math.

  When Leighton arrived at Princeton, he had no experience with computers and only a cursory knowledge of their history at the university, which dates back to the 1930s and the work of several great, mathematically inclined computer scientists, including Oswald Veblen, John von Neumann, and Alan Turing. Their combined efforts led to the construction of the world’s third computer at Princeton’s Institute for Advanced Study. With separate units for input and output, the colossal machine was used for everything from weather predictions and evolution studies to the modeling of freeway traffic patterns.{17}

  During Leighton’s time at Princeton, the Chairman of the university’s Electrical Engineering and Computer Science Department edited the results of a six-year research study into one of the most important publications in the field of theoretical computer science. In What Can Be Automated? the authors argued that computer science is mainly concerned with fundamental questions in math for two reasons. First, computers and programs are inherently mathematical objects—they manipulate formal symbols, and their input-output can be described by mathematical functions. Second, computer programs are often filled with massive amounts of data, making the number of possible inputs infinite. There is no better way to understand infinite cases, they wrote, than math.{18}

  The work at Princeton inspired Leighton’s early interest in theoretical computer science, the intersection between math and computing. At the time, very few universities even had departments of computer science, and even fewer offered the study of computer theory. So when Leighton graduated from Princeton, hoping to pursue a higher degree in topics like graph theory and parallel algorithms, his next step was clear. In 1978, he arrived at MIT at the very same time LCS was busy creating ARPANET, the forerunner to the Internet. But Leighton had other interests. “Honestly, I didn’t even know what ARPANET was at the time,” he said. “I came to MIT for one reason: great theoretical computer science.”

  In his spare time, Leighton said he and his classmates perpetuated the stereotype of math nerds by staying up all night to play one of the first distributed videogames, Spacewar.{19} Leighton learned to code programs, but never mastered the skill or joined the hackers who spent hours glued to computer screens. Instead, he remained squarely focused on an emerging field in theory: parallel distributed algorithms.

  By this time, it seemed Leighton’s father had been correct—math, even in computer science, was not a ticket to fortune or fame. But Leighton didn’t care. “MIT was the most wonderful place to be and to research,” he said.

  Two decades later in the late 1990s, Leighton was more than comfortably entrenched at MIT, where he’d risen to the head of the theory group at LCS, then the algorithms group. In these positions, Leighton worked closely with young scientists from all corners of the globe, and they were nothing but the best. In 1996, LCS accepted just one hundred students out of a pool of more than two thousand applicants. Of those, only five joined Leighton’s theory group, including Lewin himself. Even by the exacting standards of MIT, it was an exceptional year.

  In addition to Lewin, the theory group’s cast of characters included the following: Yevgeniy Dodis of Moldova, who immigrated to America with his parents in the 1970s to attend college at New York University (back in Moldova, Dodis was a celebrity, the three-time winner of the tiny country’s high school math championship); Eric Lehman, a whiz kid from North Dakota who studied computer science in college at MIT; Salil Vadhan, a Harvard graduate with a passion for complexity theory; and Amit Sahai, a Berkeley computer genius and winner of the Association for Computing Machinery’s World Programming Championship. They were joined the following year by Ukrainian cryptographer Anna Lysyanskaya, one of just two female students at LCS, and Venkat Gurwasami from India, whom everyone agreed was the smartest of them all.

  They were young, serious, and, for the first time in their adult lives, surrounded by people with similar skills and ambition. While some students at LCS felt the tug of the dot-com craze—which was already creating a new generation of millionaires out of university dropouts with dazzling ideas—the theory group members were generally content to stay put. “At that time, the startup rush was in the air,” said Amit Sahai, now a tenured professor at UCLA. “But we came to MIT thinking, ‘We are the serious math types, we will not get caught up in the gold rush.’”

  Central command for the theory group was Building NE43, a homely structure in a cluster of MIT buildings known as Tech Square. Located between Broadway and Main Street, Tech Square was architecturally unremarkable, constructed in the 1960s to resemble a bland government agency and already bearing signs of old age. It featured fraying carpets, hissing radiators, and windowless offices. What the building lacked in character, however, it made up for in soul. As the home of both MIT’s LCS and Artificial Intelligence (AI) Lab, the walls of Tech Square seemed to emanate a spirit of imagination and innovation. Although it had been scheduled for demolition by the mid-1990s, Tech Square remained home to the class of 1996. And it was a comfortable one, littered with relics of years past in the form of unfinished papers, whiteboards covered in bursts of brilliance, and piles of coffee-stained textbooks. “Graduate students would rotate through, and you could literally dig around and find debris—notes, half-written papers, whatever—from students many, many years before,” recalled Eric Lehman, now an engineer at Google.

  The theory group occupied the third floor, where both Tom Leighton and World Wide Web founder Tim Berners-Lee had offices. Be Blackburn, the lab secretary, was affectionately called the “den mother” of LCS. Blackburn was known for offering emotional support to students cracking under pressure and for organizing annual social gatherings. One such gathering was a “corn fest,” which Blackburn started because so many of the school’s international students had never dined on buttery cobs of corn. When they weren’t buried in research, students gathered in the third floor “Theory Lounge” to play timed chess or Scrabble, read the newspaper, or warm up their lunch using the only microwave in the nine-story building. Holiday parties were fun but without frills—fruit, crackers, and overly damp blocks of cheese on toothpicks. Occasionally, someone would introduce a case of beer or box of wine, but the parties almost always ended in a return, en masse, to the lab. Late at night, the windows of LCS would often glow with the deep, fluorescent blue of computing terminals. And in the mornings, the lab was littered with the evidence of all-nighters: cardboard pizza boxes, empty soda cans, and the occasional hooded sweatshirt hanging over a chair.

  The atmosphere at LCS was genial, but at times intensely competitive. Like any discipline at a world-class university, there was a push—unspoken but ever present—to publish papers. “There’s a lot of subconscious pressure,” confirmed Yevgeniy Dodis. “You are surrounded by incredibly smart people, and you are searching for a needle in a haystack—one that will make you famous.” And Lewin, said Dodis, possessed a somewhat superhuman drive to find that proverbial needle: “Danny would not even sleep, and he had the drive of a complete madman.”

  If there was one professor the theory group collectively worked to impress, it was Tom Leighton. To the select few who understood the complexity and beauty of his work, Leighton wa
s a star. In addition to Lewin, a few other students had come to MIT, in part, to work with Leighton. One of them was Amit Sahai. “I remember clearly this period of being awe-struck,” Sahai said. “I remember the feeling of ‘I have this meeting with Tom, and I better have something clever to say.’ We were all pretty amazed by him.” Of all those in their small group, Sahai noted, “Danny really worked hard to prove himself to Tom.”

  Despite the competition, the members of the 1996 theory group formed fast friendships and collaborated on much of their work during that first year. Lewin wasn’t the first to publish anything of great importance, a fact that frustrated him. But he still managed to impress his brilliance on his classmates in unexpected ways. Salil Vadhan recalled the time he was working in the lab when Lewin excitedly appeared and announced: “I got it!” Vadhan asked what, and Lewin went on to explain that he’d spent some time thinking about Remco Van der Hofstad, head of the Mathematics Genealogy Project in Stockholm, and his theory of inapproximability. It was late, sometime after 9:00 p.m., yet Lewin insisted that Vadhan follow him to a conference room so he could sketch some ideas out on a whiteboard. Before he knew it, Vadhan realized he’d been sitting there for close to three hours listening to Lewin explain his results with a kind of energy and clarity Vadhan said he’ll never forget. “It was a brilliant, extremely lucid presentation for someone who had just read and understood that paper,” remarked Vadhan, now a professor at Harvard. “To this day, I can still reproduce the results of Hofstad, thanks to Danny.”

  As self-professed math geeks, some even socially awkward, the theory students were somewhat awed, and a bit mystified, by Lewin. He was the only student with a family of his own, and he delighted in letting Eitan and Itamar tag along with him to Tech Square, where they’d enliven the musty halls with their tiny voices and laughter. In addition to his experience as a parent, Lewin had a military background, which was almost unheard of in the contemporary ranks of LCS. Occasionally he would thrill his classmates with Hollywood-sounding stories of his time as a soldier or his proposal to Anne on a desert cliff. They didn’t know much about Lewin’s army service besides the various snippets he shared, but they figured he was likely the first computer scientist at MIT to have fought face-to-face with terrorists. Now and then, he shared some fact that left everyone wide-eyed, like how much C4 you need to blow up a van (start with a lot, then scale back).

  It was no surprise, then, that almost as soon as the theory students formed friendships, Lewin became their ringleader. And despite the pressures of the program, they had fun. For them, fun equaled hours spent challenging each other with math puzzles. These intellectual jousting matches inspired Lewin and Eric Lehman to organize a game they called Theory Jeopardy, a weekly competition housed in the third floor lounge of Tech Square. Lewin put himself in charge of rallying his classmates to the games in widely circulated e-mails:

  FROM: dlewin@mit.lcs.edu

  TO: LCS

  Theory Jeopardy is an opportunity for Theory graduate students to sharpen their wits, heap ridicule on one another, and avoid work on Thursday night…

  The goal is to solve problems in specified Theory categories while simultaneously inventing new problems to challenge the other players. Your score is raised if you solve a problem or if you falsely claim you can (and are not caught). Your score can drop if you falsely claim that you can solve a problem (and are caught) or if you give a problem which appears to be too hard. Your score can also vary if you violate or exploit an Arbitrary Scoring Rule.

  The theory students didn’t exactly party, so Theory Jeopardy became their pressure release valve, an opportunity to achieve victory in something concrete at a time when most of them were in the throes of open-ended research projects. “It was about as nerdy as you could get,” said Lehman. Another stress reliever, and perhaps the most comical, was the department’s softball team. The team leader was Leighton, who loved the opportunity to break free from the barrels of LCS and socialize informally with his students. Lewin took charge of the team’s practices and game schedule, and, despite an abysmal record, he rallied everyone to the field with the battle cry of a commanding officer. In his softball e-mails, Lewin goaded his classmates to abandon their studies for the sake of the “lean, green, losing machine.”

  FROM: dlewin@mit.lcs.edu

  TO: LCS listserve

  Summer Softball has arrived!

  Softball is that competitive team game of seven innings closely resembling baseball but played on a smaller diamond with a ball that is larger and softer than a baseball and that is pitched underhand. Ok, that was from “Webster’,” and we probably should redefine [it] as: LCS Softball, A team game during which huge quantities of beer and iced tea are consumed, players regularly don’t show up, balls are more often dropped than caught, and balls are pitched so slow that even YOU can hit them!

  The first practice will be held TOMORROW on one of the MIT fields (start walking from West to East looking for people discussing permutation routing, batting averages, and compiler technologies).

  Lewin appointed Yevgeniy Dodis team captain, despite his protestations. As a native of Moldova, Dodis had never watched a game of softball and had no understanding of the rules. Lewin was so convincing, however, that he reluctantly agreed. The games themselves were a spectacle. “We were horrible,” recalled Lehman. “Someone would hit a ball, and we’d all run the wrong way trying to catch it. Eventually, it would just bounce on the ground.”

  The intellectual energy of MIT excited both Danny and Anne; their neighbors were studying to be molecular biologists, biomedical engineers, architects, and so on. In a neighborhood with students from all over the world, the married couple often spent long evenings engaged in heated political or academic debates by the playground in the courtyard of their student housing.

  The family’s weekends were never spent lounging around the apartment or watching television. Instead, after a long, often grueling week of school, Lewin would greet the boys and Anne first thing Saturday morning with a plan: the zoo, a national park, a campout, or a museum. They took day trips to Newport, Rhode Island, sailed on the Charles River in Massachusetts, and skied in Vermont. When the boys complained of nothing to do, Lewin often replied: “Life is too short to be bored. Only boring people are bored.” As if to prove himself, he then typically disappeared into the kitchen, rummaged the cupboards and returned with a haphazard collection of items. As the boys sat captivated, he feverishly whipped up a warrior costume, fashioning a sword out of a spoon wrapped in foil and armor out of bowls and baking sheets.

  Fatherhood was something Lewin approached with his characteristic, unbridled enthusiasm. In many ways, Lewin was childlike; he had a sophomoric sense of humor, unrestrained energy, and had an easier time playing with his kids than making small talk at cocktail parties. Although Lewin was a strict disciplinarian, Eitan and Itamar were smitten with him. Lewin always made time for them, skipping out of class in the middle of the day to surprise them at the playground. He built forts, wrestled, and instigated pillow fights with them. Greenberg remembered seeing Lewin changing diapers with a smile on his face, using his large hands to fasten the tiny tabs with military-like precision.

  In an interview for a documentary tribute to Danny, Anne recalled the thrill the boys got out of Lewin’s “word games.” Every week he would comb the dictionary for the quirkiest, strangest-sounding word he could find, write its definition on an index card, and pin it to the fridge “Obstreperous” became one of his favorite words, an ironic choice considering it is used to describe someone who is stubborn, resistant to control, and noisy. Tongue-in-cheek, Lewin used it to describe others, not himself, namely anyone who got in his way. Later, he transformed it into a catch phrase among his co-workers when referring to competitors or naysayers.

  That first year in Cambridge wasn’t easy for Danny and Anne. They were both in graduate school; Anne was accepted to Boston College, where she decided to pursue a Master’s in French Literature. They
were both working as Teaching Assistants, and needed help with care for Eitan and Itamar. Fortunately, they found an at-home daycare run by a family from India—Preetish and Shirin Nijhawan. Preetish was a graduate student at MIT’s Sloan School of Business, and to make ends meet, Shirin was caring for a small group of children out of their apartment, which was located nearby the Lewins in student housing. The two couples became fast friends.

  Despite the financial stress Danny and Anne faced, Anne never lost confidence in Danny’s potential for success. She didn’t know anything about algorithms or computer science, but she did know her husband was brilliant and determined. In a documentary tribute to Danny, Anne recalled a conversation she once had with him in their apartment in Haifa, where Danny kept a big, bulky personal computer that he loved to program. At the time, the World Wide Web had just made its debut, and it was unclear to most people what the impact of this newfangled technology would be. But Anne said Danny had a clear idea of its potential, explaining excitedly that the Internet would allow her to use a computer in Israel to access information from a library at Harvard University. Anne said she expressed her amazement, but added that it sounded complicated. Danny replied: “It is complicated. But can you imagine the possibilities? Can you imagine what we’ll be able to do if someone makes it easy?”

  Publish or perish. It’s a well-known saying at the nation’s best universities, one that sums up the fear among research-oriented graduate students that failure to publish in scholarly journals means academic doom.

  By late fall, Lewin was beginning to feel the pressure. Salil Vadhan and Amit Sahai had already produced and published an impressive paper. But Lewin and his three writing partners—Eric Lehman, Rina Panigrahy, and Matthew Levine—were stuck. “We didn’t feel like we were having much success,” recalled Lehman.