Computer chips have stopped getting faster: The regular performance improvements we’ve come to expect are now the result of chipmakers’ adding more cores, or processing units, to their chips, rather than increasing their clock speed.

In theory, doubling the number of cores doubles the chip’s efficiency, but splitting up computations so that they run efficiently in parallel isn’t easy. On the other hand, say a trio of computer scientists from MIT, Israel’s Technion, and Microsoft Research, neither is it as hard as had been feared.

Commercial software developers writing programs for multicore chips frequently use so-called “lock-free” parallel algorithms, which are relatively easy to generate from standard sequential code. In fact, in many cases the conversion can be done automatically.

Yet lock-free algorithms don’t come with very satisfying theoretical guarantees: All they promise is that at least one core will make progress on its computational task in a fixed span of time. But if they don’t exceed that standard, they squander all the additional computational power that multiple cores provide.

In recent years, theoretical computer scientists have demonstrated ingenious alternatives called “wait-free” algorithms, which guarantee that all cores will make progress in a fixed span of time. But deriving them from sequential code is extremely complicated, and commercial developers have largely neglected them.

In a paper to be presented at the Association for Computing Machinery’s Annual Symposium on the Theory of Computing in May, Nir Shavit, a professor in MIT’s Department of Electrical Engineering and Computer Science; his former student Dan Alistarh, who’s now at Microsoft Research; and Keren Censor-Hillel of the Technion demonstrate a new analytic technique suggesting that, in a wide range of real-world cases, lock-free algorithms actually give wait-free performance.

“In practice, programmers program as if everything is wait-free,” Shavit says. “This is a kind of mystery. What we are exposing in the paper is this little-talked-about intuition that programmers have about how [chip] schedulers work, that they are actually benevolent.”

The researchers’ key insight was that the chip’s performance as a whole could be characterized more simply than the performance of the individual cores. That’s because the allocation of different “threads,” or chunks of code executed in parallel, is symmetric. “It doesn’t matter whether thread 1 is in state A and thread 2 is in state B or if you just swap the states around,” says Alistarh, who contributed to the work while at MIT. “What we noticed is that by coalescing symmetric states, you can simplify this a lot.”

In a real chip, the allocation of threads to cores is “a complex interplay of latencies and scheduling policies,” Alistarh says. In practice, however, the decisions arrived at through that complex interplay end up looking a lot like randomness. So the researchers modeled the scheduling of threads as a process that has at least a little randomness in it: At any time, there’s some probability that a new thread will be initiated on any given core.

The researchers found that even with a random scheduler, a wide range of lock-free algorithms offered performance guarantees that were as good as those offered by wait-free algorithms.

That analysis held, no matter how the probability of thread assignment varied from core to core. But the researchers also performed a more specific analysis, asking what would happen when multiple cores were trying to write data to the same location in memory and one of them kept getting there ahead of the others. That’s the situation that results in a lock-free algorithm’s worst performance, when only one core is making progress.

For that case, they considered a particular set of probabilities, in which every core had the same chance of being assigned a thread at any given time. “This is kind of a worst-case random scheduler,” Alistarh says. Even then, however, the number of cores that made progress never dipped below the square root of the number of cores assigned threads, which is still better than the minimum performance guarantee of lock-free algorithms.

By Larry Hardesty, MIT News Office

MIT’s graduate program in engineering has been ranked No. 1 in the country in U.S. News & World Report’s annual rankings — a spot the Institute has held since 1990, when the magazine first ranked graduate programs in engineering.

U.S. News awarded MIT a score of 100 among graduate programs in engineering, followed by No. 2 Stanford University (93), No. 3 University of California at Berkeley (87), and No. 4 California Institute of Technology (80).

As was the case last year, MIT’s graduate programs led U.S. News lists in seven engineering disciplines. Top-ranked at MIT this year are programs in aerospace engineering; chemical engineering; materials engineering; computer engineering; electrical engineering (tied with Stanford and Berkeley); mechanical engineering (tied with Stanford); and nuclear engineering (tied with the University of Michigan). MIT’s graduate program in biomedical engineering was also a top-five finisher, tying for third with the University of California at San Diego.

In U.S. News’ first evaluation of PhD programs in the sciences since 2010, five MIT programs earned a No. 1 ranking: biological sciences (tied with Harvard University and Stanford); chemistry (tied with Caltech and Berkeley, and with a No. 1 ranking in the specialty of inorganic chemistry); computer science (tied with Carnegie Mellon University, Stanford, and Berkeley); mathematics (tied with Princeton University, and with a No. 1 ranking in the specialty of discrete mathematics and combinations); and physics. MIT’s graduate program in earth sciences was ranked No. 2.

The MIT Sloan School of Management ranked fifth this year among the nation’s top business schools, behind Harvard Business School, Stanford’s Graduate School of Business, the Wharton School at the University of Pennsylvania, and the Booth School of Business at the University of Chicago.

Sloan’s graduate programs in information systems, production/operations, and supply chain/logistics were again ranked first this year; the Institute’s graduate offerings in entrepreneurship (No. 3) and finance (No. 5) also ranked among top-five programs.

U.S. News does not issue annual rankings for all doctoral programs, but revisits many every few years. In the magazine’s 2013 evaluation of graduate programs in economics, MIT tied for first place with Harvard, Princeton, and Chicago.

U.S. News bases its rankings of graduate schools of engineering and business on two types of data: reputational surveys of deans and other academic officials, and statistical indicators that measure the quality of a school’s faculty, research, and students. The magazine’s less-frequent rankings of programs in the sciences, social sciences, and humanities are based solely on reputational surveys.

By News Office

Every time you open your eyes, visual information flows into your brain, which interprets what you’re seeing. Now, for the first time, MIT neuroscientists have noninvasively mapped this flow of information in the human brain with unique accuracy, using a novel brain-scanning technique.

This technique, which combines two existing technologies, allows researchers to identify precisely both the location and timing of human brain activity. Using this new approach, the MIT researchers scanned individuals’ brains as they looked at different images and were able to pinpoint, to the millisecond, when the brain recognizes and categorizes an object, and where these processes occur.

“This method gives you a visualization of ‘when’ and ‘where’ at the same time. It’s a window into processes happening at the millisecond and millimeter scale,” says Aude Oliva, a principal research scientist in MIT’s Computer Science and Artificial Intelligence Laboratory (CSAIL).

Oliva is the senior author of a paper describing the findings in the Jan. 26 issue of Nature Neuroscience. Lead author of the paper is CSAIL postdoc Radoslaw Cichy. Dimitrios Pantazis, a research scientist at MIT’s McGovern Institute for Brain Research, is also an author of the paper.

When and where

Until now, scientists have been able to observe the location or timing of human brain activity at high resolution, but not both, because different imaging techniques are not easily combined. The most commonly used type of brain scan, functional magnetic resonance imaging (fMRI), measures changes in blood flow, revealing which parts of the brain are involved in a particular task. However, it works too slowly to keep up with the brain’s millisecond-by-millisecond dynamics.

Another imaging technique, known as magnetoencephalography (MEG), uses an array of hundreds of sensors encircling the head to measure magnetic fields produced by neuronal activity in the brain. These sensors offer a dynamic portrait of brain activity over time, down to the millisecond, but do not tell the precise location of the signals.

To combine the time and location information generated by these two scanners, the researchers used a computational technique called representational similarity analysis, which relies on the fact that two similar objects (such as two human faces) that provoke similar signals in fMRI will also produce similar signals in MEG. This method has been used before to link fMRI with recordings of neuronal electrical activity in monkeys, but the MIT researchers are the first to use it to link fMRI and MEG data from human subjects.

In the study, the researchers scanned 16 human volunteers as they looked at a series of 92 images, including faces, animals, and natural and manmade objects. Each image was shown for half a second.

“We wanted to measure how visual information flows through the brain. It’s just pure automatic machinery that starts every time you open your eyes, and it’s incredibly fast,” Cichy says. “This is a very complex process, and we have not yet looked at higher cognitive processes that come later, such as recalling thoughts and memories when you are watching objects.”

Each subject underwent the test multiple times — twice in an fMRI scanner and twice in an MEG scanner — giving the researchers a huge set of data on the timing and location of brain activity. All of the scanning was done at the Athinoula A. Martinos Imaging Center at the McGovern Institute.

Millisecond by millisecond

By analyzing this data, the researchers produced a timeline of the brain’s object-recognition pathway that is very similar to results previously obtained by recording electrical signals in the visual cortex of monkeys, a technique that is extremely accurate but too invasive to use in humans.

About 50 milliseconds after subjects saw an image, visual information entered a part of the brain called the primary visual cortex, or V1, which recognizes basic elements of a shape, such as whether it is round or elongated. The information then flowed to the inferotemporal cortex, where the brain identified the object as early as 120 milliseconds. Within 160 milliseconds, all objects had been classified into categories such as plant or animal.

The MIT team’s strategy “provides a rich new source of evidence on this highly dynamic process,” says Nikolaus Kriegeskorte, a principal investigator in cognition and brain sciences at Cambridge University.

“The combination of MEG and fMRI in humans is no surrogate for invasive animal studies with techniques that simultaneously have high spatial and temporal precision, but Cichy et al. come closer to characterizing the dynamic emergence of representational geometries across stages of processing in humans than any previous work. The approach will be useful for future studies elucidating other perceptual and cognitive processes,” says Kriegeskorte, who was not part of the research team.

The MIT researchers are now using representational similarity analysis to study the accuracy of computer models of vision by comparing brain scan data with the models’ predictions of how vision works.

Using this approach, scientists should also be able to study how the human brain analyzes other types of information such as motor, verbal, or sensory signals, the researchers say. It could also shed light on processes that underlie conditions such as memory disorders or dyslexia, and could benefit patients suffering from paralysis or neurodegenerative diseases.

“This is the first time that MEG and fMRI have been connected in this way, giving us a unique perspective,” Pantazis says. “We now have the tools to precisely map brain function both in space and time, opening up tremendous possibilities to study the human brain.”

The research was funded by the National Eye Institute, the National Science Foundation, and a Feodor Lynen Research Fellowship from the Humboldt Foundation.
By Anne Trafton, MIT News Office

For years Dr. Stephanie Seneff has been known throughout the computer science world for her work in natural language processing. A computer scientist with a background in biology, Seneff received her undergraduate degree in biophysics before moving to electrical engineering and computer science for her MS and PhD degrees. For over 30 years, she worked on developing new computational systems aimed at providing insight on biological challenges, including the human auditory system, gene prediction and human language with the goal of improving human-computer interaction.

When her husband was diagnosed with heart disease six years ago and subsequently placed on statin drugs, they were both alarmed when side effects appeared immediately. Seneff vowed to learn more about statin drugs to ensure her husband was receiving the best medical treatment possible. Using the same analytical computer science skills she had developed over the years through her research, Seneff decided to take a similar approach to the study of medicine.

“Drawing on my background in biology, I started reading anything I could find about statin drugs and related research explaining their effects. I also found clinical data about their impact on humans, and was shocked by the adverse effects statin drugs have,” Seneff says. “Being a computer scientist, I started gathering all these drug side effect reports that I found online. I then took all of this information — the research literature and the drugs side effect reports — and applied my computer science programs to decipher the content.”

Using standard computer science techniques, Seneff compared the side effects of statin drugs to other drugs taken by humans within the same age distribution. She found many adverse side effects stemming from the usage of statin drugs, and through this work saw a new path for her research: Using computer science techniques to understand human biology, in particular the relationship between nutrition and health.

Based on her experience developing natural language processing algorithms that could parse phrases and locate key words, Seneff developed a way to exploit computer science methods to help her understand how drugs and environmental toxins impacted human health. To study the interaction between health and environmental factors like drugs and toxic chemicals, Seneff found that it was a natural choice to simply modify the natural language processing algorithm she and her colleagues had already developed to analyze and build summaries of restaurant reviews.

Seneff describes her method as a traditional, systems-level computer science approach to biological problems. The technique works by analyzing specific sections of research papers and testimonials documenting drug side effects for unusual statistical frequencies of key symptom-related words like fatigue or nausea, but also for biological terms like homocysteine and glutathione. Seneff then looks at the correlation statistics to see which keywords tend to appear together in the same paragraph or the same drug side effect report. Based on the statistical data, Seneff applies her findings to the research literature to see if she can draw a connection between any of the symptoms documented in the side effect reports, the biologically related words in the research literature, and environmental toxins or medications being used by the selected population.

“My approach is a systems-level biology approach using simple computer science techniques to help organize the facts. The underlying theme is collecting data from people who are experiencing problems and who live in a particular environment. You examine the data using our computer science techniques, and then you can link specific environments with specific problems. When you go back to the research literature, you can examine what certain materials like glyphosate do to human biology,” says Seneff. “You can then build a hypothesis by studying the research literature and the web-based documentation of symptoms.”

Seneff has applied her technique to understanding everything from Alzheimer’s disease and autism to studying the impact of nutritional deficiencies and environmental toxins like herbicides. Since, 2011 she has published 10 papers in various medical and health-related journals. Her findings have shocked the medical world, as she has shown connections between herbicides like glyphosate and the disruption of the human body’s gut bacteria, depletion of essential amino acids and interference with necessary enzymes, possibly leading to Alzheimer’s, autism, obesity and more.

While Seneff’s approach and findings are unconventional to some, she believes her approach to using computer science to better understand the interaction between human health and environmental toxins provides a new viewpoint that could prove insightful.

“In my work I am using a combination of simple but potent computer science tools to understand biology. I think it’s really important to use computer science as a tool to understand biology and to think of biology at a systems level,” Seneff says. “I am trying to look at the whole system and understand all of the interactions between different parts, which may be a product of my training as a computer scientist. I think computer scientists view the problem differently than biologists.”
By Abby Abazorius | CSAIL

The birth of artificial-intelligence research as an autonomous discipline is generally thought to have been the monthlong Dartmouth Summer Research Project on Artificial Intelligence in 1956, which convened 10 leading electrical engineers — including MIT’s Marvin Minsky and Claude Shannon — to discuss “how to make machines use language” and “form abstractions and concepts.” A decade later, impressed by rapid advances in the design of digital computers, Minsky was emboldened to declare that “within a generation … the problem of creating ‘artificial intelligence’ will substantially be solved.”

The problem, of course, turned out to be much more difficult than AI’s pioneers had imagined. In recent years, by exploiting machine learning — in which computers learn to perform tasks from sets of training examples — artificial-intelligence researchers have built special-purpose systems that can do things like interpret spoken language or play Jeopardy with great success. But according to Tomaso Poggio, the Eugene McDermott Professor of Brain Sciences and Human Behavior at MIT, “These recent achievements have, ironically, underscored the limitations of computer science and artificial intelligence. We do not yet understand how the brain gives rise to intelligence, nor do we know how to build machines that are as broadly intelligent as we are.”

Poggio thinks that AI research needs to revive its early ambitions. “It’s time to try again,” he says. “We know much more than we did before about biological brains and how they produce intelligent behavior. We’re now at the point where we can start applying that understanding from neuroscience, cognitive science and computer science to the design of intelligent machines.”

The National Science Foundation (NSF) appears to agree: Today, it announced that one of three new research centers funded through its Science and Technology Centers Integrative Partnerships program will be the Center for Brains, Minds and Machines (CBMM), based at MIT and headed by Poggio. Like all the centers funded through the program, CBMM will initially receive $25 million over five years.

Homegrown initiative

CBMM grew out of the MIT Intelligence Initiative, an interdisciplinary program aimed at understanding how intelligence arises in the human brain and how it could be replicated in machines.

“[MIT President] Rafael Reif, when he was provost, came to speak to the faculty and challenged us to come up with new visions, new ideas,” Poggio says. He and MIT’s Joshua Tenenbaum, also a professor in the Department of Brain and Cognitive Sciences (BCS) and a principal investigator in the Computer Science and Artificial Intelligence Laboratory, responded by proposing a program that would integrate research at BCS and the Department of Electrical Engineering and Computer Science. “With a system as complicated as the brain, there is a point where you need to get people to work together across different disciplines and techniques,” Poggio says. Funded by MIT’s School of Science, the initiative was formally launched, in 2011, at a symposium during MIT’s 150th anniversary.

Headquartered at MIT, CBMM will be, like all the NSF centers, a multi-institution collaboration. Of the 20 faculty members currently affiliated with the center, 10 are from MIT, five are from Harvard University, and the rest are from Cornell University, Rockefeller University, the University of California at Los Angeles, Stanford University and the Allen Institute for Brain Science. The center’s international partners are the Italian Institute of Technology; the Max Planck Institute in Germany; City University of Hong Kong; the National Centre for Biological Sciences in India; and Israel’s Weizmann Institute and Hebrew University. Its industrial partners are Google, Microsoft, IBM, Mobileye, Orcam, Boston Dynamics, Willow Garage, DeepMind and Rethink Robotics. Also affiliated with center are Howard University; Hunter College; Universidad Central del Caribe, Puerto Rico; the University of Puerto Rico, Río Piedras; and Wellesley College.

CBMM aims to foster collaboration not just between institutions but also across disciplinary boundaries. Graduate students and postdocs funded through the center will have joint advisors, preferably drawn from different research areas.

Research themes

The center’s four main research themes are also intrinsically interdisciplinary. They are the integration of intelligence, including vision, language and motor skills; circuits for intelligence, which will span research in neurobiology and electrical engineering; the development of intelligence in children; and social intelligence. Poggio will also lead the development of a theoretical platform intended to undergird the work in all four areas.

“Those four thrusts really do fit together, in the sense that they cover what we think are the biggest challenges facing us when we try to develop a computational understanding of what intelligence is all about,” says Patrick Winston, the Ford Foundation Professor of Engineering at MIT and research coordinator for CBMM.

For instance, he explains, in human cognition, vision, language and motor skills are inextricably linked, even though they’ve been treated as separate problems in most recent AI research. One of Winston’s favorite examples is that of image labeling: A human subject will identify an image of a man holding a glass to his lips as that of a man drinking. If the man is holding the glass a few inches further forward, it’s an instance of a different activity — toasting. But a human will also identify an image of a cat turning its head up to catch a few drops of water from a faucet as an instance of drinking. “You have to be thinking about what you see there as a story,” Winston says. “They get the same label because it’s the same story, not because it looks the same.”

Similarly, Winston explains, development is its own research thrust because intelligence is fundamentally shaped through interaction with the environment. There’s evidence, Winston says, that mammals that receive inadequate visual stimulation in the first few weeks of life never develop functional eyesight, even though their eyes are otherwise unimpaired. “You need to stimulate the neural mechanisms in order for them to assemble themselves into a functioning system,” Winston says. “We think that that’s true generally, of our entire spectrum of capabilities. You need to have language, you need to see things, you need to have language and vision work together from the beginning to ensure that the parts develop properly to form a working whole.”
By Larry Hardesty, MIT News Office

With recent advances in three-dimensional (3-D) printing technology, it is now possible to produce a wide variety of 3-D objects, utilizing computer graphics models and simulations. But while the hardware exists to reproduce complex, multi-material objects, the software behind the printing process is cumbersome, slow and difficult to use, and needs to improve substantially if 3-D technology is to become more mainstream.

On July 25, a team of researchers from the MIT Computer Science and Artificial Intelligence Lab (CSAIL) will present two papers at the SIGGRAPH computer graphics conference in Anaheim, California, which propose new methods for streamlining and simplifying the 3-D printing process, utilizing more efficient, intuitive and accessible technologies.

“Our goal is to make 3-D printing much easier and less computationally complex,” said Associate Professor Wojciech Matusik, co-author of the papers and a leader of the Computer Graphics Group at CSAIL. “Ours is the first work that unifies design, development and implementation into one seamless process, making it possible to easily translate an object from a set of specifications into a fully operational 3-D print.”

3-D printing poses enormous computational challenges to existing software. For starters, in order to fabricate complex surfaces containing bumps, color gradations and other intricacies, printing software must produce an extremely high-resolution model of the object, with detailed information on each surface that is to be replicated. Such models often amount to petabytes of data, which current programs have difficulty processing and storing.

To address these challenges, Matusik and his team developed OpenFab, a programmable “pipeline” architecture. Inspired by RenderMan, the software used to design computer-generated imagery commonly seen in movies, OpenFab allows for the production of complex structures with varying material properties. To specify intricate surface details and the composition of a 3-D object, OpenFab uses “fablets”, programs written in a new programming language that allow users to modify the look and feel of an object easily and efficiently.

“Our software pipeline makes it easier to design and print new materials and to continuously vary the properties of the object you are designing,” said Kiril Vidimče, lead author of one of the two papers and a PhD student at CSAIL. “In traditional manufacturing most objects are composed of multiple parts made out of the same material. With OpenFab, the user can change the material consistency of an object, for example designing the object to transition from stiff at one end to flexible and compressible at the other end.”

Thanks to OpenFab’s streaming architecture, data about the design of the 3-D object is computed on demand and sent to the printer as it becomes available, with little start-up delay. So far, Matusik’s research team has been able to replicate a wide array of objects using OpenFab, including an insect embedded in amber, a marble table and a squishy teddy bear.

In order to create lifelike objects that are hard, soft, reflect light and conform to touch, users must currently specify the material composition of the object they wish to replicate. This is no easy task, as it’s often easier to define the desired end-state of an object — for example, saying that an object needs to be soft — than to determine which materials should be used in its production.

To simplify this process, Matusik and his colleagues developed a new methodology called Spec2Fab. Instead of requiring explicit design specifications for each region of a print, and testing every possible combination, Spec2Fab employs a “reducer tree”, which breaks the object down into more manageable chunks. Spec2Fab’s “tuner network” then uses the reducer tree to automatically determine the material composition of an object.

By combining existing computer graphics algorithms, Matusik’s team has used Spec2Fab to create a multitude of 3-D prints, creating optical effects like caustic images and objects with specific deformation and textural properties.

“Spec2Fab is a small but powerful toolbox for building algorithms that can produce an endless array of complex, printable objects,” said Desai Chen, a PhD student at CSAIL and lead author of one of the papers presented at SIGGRAPH.

The two papers to be presented at SIGGRAPH are “OpenFab: A Programmable Pipeline for Multi-Material Fabrication,” authored by Kiril Vidimče, Szu-Po Wang, Jonathan Ragan-Kelley and Wojciech Matusik; and “Spec2Fab: A Reducer-Tuner Model for Translating Specifications to 3-D Prints,” authored by Desai Chen, David I. W. Levin, Piotr Didyk, Pitchaya Sitthi-Amorn and Wojciech Matusik.

For more information on OpenFab, please visit: For more information on Spec2Fab, please visit:

By Abby Abazorius | CSAIL

TCP, the transmission control protocol, is one of the core protocols governing the Internet: If counted as a computer program, it’s the most widely used program in the world.

One of TCP’s main functions is to prevent network congestion by regulating the rate at which computers send data. In the last 25 years, engineers have made steady improvements to TCP’s congestion-control algorithms, resulting in several competing versions of the protocol: Many Windows computers, for instance, run a version called Compound TCP, while Linux machines run a version called TCP Cubic.

At the annual conference of the Association for Computing Machinery’s Special Interest Group on Data Communication this summer, researchers from MIT’s Computer Science and Artificial Intelligence Laboratory and Center for Wireless Networks and Mobile Computing will present a computer system, dubbed Remy, that automatically generates TCP congestion-control algorithms. In the researchers’ simulations, algorithms produced by Remy significantly outperformed algorithms devised by human engineers.

“I think people can think about what happens to one or two connections in a network and design around that,” says Hari Balakrishnan, the Fujitsu Professor in Electrical Engineering and Computer Science, who co-authored the new paper with graduate student Keith Winstein. “When you have even a handful of connections, or more, and a slightly more complicated network, where the workload is not a constant — a single file being sent, or 10 files being sent — that’s very hard for human beings to reason about. And computers seem to be a lot better about navigating that search space.”

Lay of the land

Remy is a machine-learning system, meaning that it arrives at its output by trying lots of different possibilities, and exploring further variations on those that seem to work best. Users specify certain characteristics of the network, such as whether the bandwidth across links fluctuates or the number of users changes, and by how much. They also provide a “traffic profile” that might describe, say, the percentage of users who are browsing static Web pages or using high-bandwidth applications like videoconferencing.

Finally, the user also specifies the metrics to be used to evaluate network performance. Standard metrics include throughput, which indicates the total amount of data that can be moved through the network in a fixed amount of time, and delay, which indicates the average amount of time it takes one packet of information to travel from sender to receiver. The user can also assign metrics different weights — say, reducing delay is important, but only one-third as important as increasing throughput.

Remy needs to test each candidate algorithm’s performance under a wide range of network conditions, which could have been a prohibitively time-consuming task. But Winstein and Balakrishnan developed a clever algorithm that can concentrate Remy’s analyses on cases in which small variations in network conditions produce large variations in performance, while spending much less time on cases where network behavior is more predictable.

They also designed Remy to evaluate possible indicators of network congestion that human engineers have not considered. Typically, TCP congestion-control algorithms look at two main factors: whether individual data packets arrive at their intended destination and, if they do, how long it takes for acknowledgments to arrive. But as it turns out, the ratio between the rates at which packets are sent and received is a rich signal that can dictate a wide range of different behaviors on the sending computer’s end.

Down to cases

Indeed, where a typical TCP congestion-control algorithm might consist of a handful of rules — if the percentage of dropped packets crosses some threshold, cut the transmission rate in half — the algorithms that Remy produces can have more than 150 distinct rules.

“It doesn’t resemble anything in the 30-year history of TCP,” Winstein says. “Traditionally, TCP has relatively simple endpoint rules but complex behavior when you actually use it. With Remy, the opposite is true. We think that’s better, because computers are good at dealing with complexity. It’s the behavior you want to be simple.” Why the algorithms Remy produces work as well as they do is one of the topics the researchers hope to explore going forward.

In the meantime, however, there’s little arguing with the results. Balakrishnan and Winstein tested Remy’s algorithms on a simulation system called the ns-2, which is standard in the field.

In tests that simulated a high-speed, wired network with consistent transmission rates across physical links, Remy’s algorithms roughly doubled network throughput when compared to Compound TCP and TCP Cubic, while reducing delay by two-thirds. In another set of tests, which simulated Verizon’s cellular data network, the gains were smaller but still significant: a 20 to 30 percent improvement in throughput, and a 25 to 40 percent reduction in delay.

“I am thrilled by the approach,” says Victor Bahl, research manager of the Mobility and Networking Group at Microsoft Research. “When you can constrain the problem domain and define precisely what you want out of the protocol, I can believe that their system is better than a human.”

Bahl cautions that “when the protocol has to do many things for many people or many devices, then it’s not clear whether this is the optimal method.” But he adds that it could very well be that, in the future, networked computers will adopt different congestion-control policies depending on the types of applications they’re running. “I could see that that’s where this thing would excel,” he says.
By Larry Hardesty, MIT News Office

In a pair of recent papers, researchers at MIT’s Computer Science and Artificial Intelligence Laboratory have demonstrated that, for a few specific tasks, it’s possible to write computer programs using ordinary language rather than special-purpose programming languages.

The work may be of some help to programmers, and it could let nonprogrammers manipulate common types of files — like word-processing documents and spreadsheets — in ways that previously required familiarity with programming languages. But the researchers’ methods could also prove applicable to other programming tasks, expanding the range of contexts in which programmers can specify functions using ordinary language.

“I don’t think that we will be able to do this for everything in programming, but there are areas where there are a lot of examples of how humans have done translation,” says Regina Barzilay, an associate professor of computer science and electrical engineering and a co-author on both papers. “If the information is available, you may be able to learn how to translate this language to code.”

In other cases, Barzilay says, programmers may already be in the practice of writing specifications that describe computational tasks in precise and formal language. “Even though they’re written in natural language, and they do exhibit some variability, they’re not exactly Shakespeare,” Barzilay says. “So again, you can translate them.”

The researchers’ recent papers demonstrate both approaches. In work presented in June at the annual Conference of the North American Chapter of the Association for Computational Linguistics, Barzilay and graduate student Nate Kushman used examples harvested from the Web to train a computer system to convert natural-language descriptions into so-called “regular expressions”: combinations of symbols that enable file searches that are far more flexible than the standard search functions available in desktop software.

In a paper being presented at the Association for Computational Linguistics’ annual conference in August, Barzilay and another of her graduate students, Tao Lei, team up with professor of electrical engineering and computer science Martin Rinard and his graduate student Fan Long to describe a system that automatically learned how to handle data stored in different file formats, based on specifications prepared for a popular programming competition.

Regular irregularities

As Kushman explains, computer science researchers have had some success with systems that translate questions written in natural language into special-purpose formal languages — languages used to specify database searches, for instance. “Usually, the way those techniques work is that they’re finding some fairly direct mapping between the natural language and this formal representation,” Kushman says. “In general, the logical forms are handwritten so that they have this nice mapping.”

Unfortunately, Kushman says, that approach doesn’t work with regular expressions, strings of symbols that can describe the data contained in a file with great specificity. A regular expression could indicate, say, just those numerical entries in a spreadsheet that are three columns over from a cell containing a word of any length whose final three letters are “BOS.”

But regular expressions, as ordinarily written, don’t map well onto natural language. For example, Kushman explains, the regular expression used to search for a three-letter word starting with “a” would contain a symbol indicating the start of a word, another indicating the letter “a,” a set of symbols indicating the identification of a letter, and a set of symbols indicating that the previous operation should be repeated twice. “If I’m trying to do the same syntactic mapping that I would normally do,” Kushman says, “I can’t pull out any sub-chunk of this that means ‘three-letter.’”

What Kushman and Barzilay determined, however, is that any regular expression has an equivalent that does map nicely to natural language — although it may not be very succinct or, for a programmer, very intuitive. Moreover, using a mathematical construct known as a graph, it’s possible to represent all equivalent versions of a regular expression at once. Kushman and Barzilay’s system thus has to learn only one straightforward way of mapping natural language to symbols; then it can use the graph to find a more succinct version of the same expression.

When Kushman presented the paper he co-authored with Barzilay, he asked the roomful of computer scientists to write down the regular expression corresponding to a fairly simple text search. When he revealed the answer and asked how many had gotten it right, only a few hands went up. So the system could be of use to accomplished programmers, but it could also allow casual users of, say, spreadsheet and word-processing programs to specify elaborate searches using natural language.

Opening gambit

The system that Barzilay, Rinard, Lei and Long developed is one that can automatically write what are called input-parsing programs, essential components of all software applications. Every application has an associated file type — .doc for Word programs, .pdf for document viewers, .mp3 for music players, and so on. And every file type organizes data differently. An image file, for instance, might begin with a few bits indicating the file type, a few more indicating the width and height of the image, and a few more indicating the number of bits assigned to each pixel, before proceeding to the bits that actually represent pixel colors.

Input parsers figure out which parts of a file contain which types of data: Without an input parser, a file is just a random string of zeroes and ones.

The MIT researchers’ system can write an input parser based on specifications written in natural language. They tested it on more than 100 examples culled from the Association for Computing Machinery’s International Collegiate Programming Contest, which includes file specifications for every programming challenge it poses. The system was able to produce working input parsers for about 80 percent of the specifications. And in the remaining cases, changing just a word or two of the specification usually yielded a working parser.

“This could be used as an interactive tool for the developer,” Long says. “The developer could look at those cases and see what kind of changes they need to make to the natural language — maybe some word is hard for the system to figure out.”

The system begins with minimal information about how written specifications might correspond to parser programs. It knows a handful of words that should consistently refer to particular data types — the word “integer,” for instance — and it knows that the specification will probably describe some data structures that are nested in others: An image file, for instance, could consist of multiple chunks, and each chunk would be headed by a few bytes indicating how big it is.

Otherwise, the system just tries lots of different interpretations of the specification on a few sample files; in the researchers’ experiments, the samples, too, were provided on the competition website. If the resulting parser doesn’t seem to work on some of the samples, the system varies its interpretation of the specification slightly. Moreover, as it builds more and more working parsers, it becomes more adept at recognizing regularities in the way that parsers are specified. It took only about 10 minutes of calculation on an ordinary laptop for the system to produce its candidate parsers for all 100-odd specifications.

“This is a big first step toward allowing everyday users to program their computers without requiring any knowledge of programming language,” says Luke Zettlemoyer, an assistant professor of computer science and engineering at the University of Washington. “The techniques they have developed should definitely generalize to other related programming tasks.”
By Larry Hardesty, MIT News Office

Optical computing — using light rather than electricity to perform calculations — could pay dividends for both conventional computers and quantum computers, largely hypothetical devices that could perform some types of computations exponentially faster than classical computers.

But optical computing requires light particles — photons — to modify each other’s behavior, something they’re naturally averse to doing: Two photons that collide in a vacuum simply pass through each other.

In the latest issue of the journal Science, researchers at MIT’s Research Laboratory of Electronics — together with colleagues at Harvard University and the Vienna University of Technology — describe the experimental realization of an optical switch that’s controlled by a single photon, allowing light to govern the transmission of light. As such, it’s the optical analog of a transistor, the fundamental component of a computing circuit.

Moreover, since the weird, counterintuitive effects of quantum physics are easier to see in individual particles than in clusters of particles, the ability to use a single photon to flip the switch could make it useful for quantum computing.

The heart of the switch is a pair of highly reflective mirrors. When the switch is on, an optical signal — a beam of light — can pass through both mirrors. When the switch is off, only about 20 percent of the light in the signal can get through.

The paired mirrors constitute what’s known as an optical resonator. “If you had just one mirror, all the light would come back,” explains Vladan Vuletić, the Lester Wolfe Professor of Physics at MIT, who led the new work. “When you have two mirrors, something very strange happens.”

Light can be thought of as particles — photons — but it can also be thought of as a wave — an electromagnetic field. Even though, on the particle description, photons are stopped by the first mirror, on the wave description, the electromagnetic field laps into the space between the mirrors. If the distance between the mirrors is precisely calibrated to the wavelength of the light, Vuletić explains, “Basically, a very large field builds up inside the cavity that cancels the field coming back and goes in the forward direction.” In other words, the mirrors become transparent to light of the right wavelength.

Clouding over

In the RLE researchers’ experiment, the cavity between the mirrors is filled with a gas of supercooled cesium atoms. Ordinarily, these atoms don’t interfere with the light passing through the mirrors. But if a single “gate photon” is fired into their midst at a different angle, kicking just one electron of one atom into a higher energy state, it changes the physics of the cavity enough that light can no longer pass through it.

Joining Vuletić on the paper are lead author Wenlan Chen and Kristin M. Beck, both PhD students in his group; Robert Bücker of the Vienna University of Technology; and Michael Gullans, Mikhail D. Lukin and Haruka Tanji-Suzuki of Harvard.

For conventional computers, the chief advantage of optical computing would be in power management: As computer chips have more and more transistors crammed onto them, they draw more power and run hotter. Computing with light instead of electricity would address both problems.

Of course, clouds of supercooled atoms are not a practical design for the transistors in, say, a Web server. “For the classical implementation, this is more of a proof-of-principle experiment showing how it could be done,” Vuletić says. “One could imagine implementing a similar device in solid state — for example, using impurity atoms inside an optical fiber or piece of solid.”

Going quantum

Quantum-computing applications may be more compelling. Bizarrely, tiny particles of matter can be in mutually exclusive states simultaneously, something known as superposition. Where a bit in a classical computer can be either on or off, representing 0 or 1, bits built from particles in superposition can represent 0 and 1 at the same time. As a consequence, they could, in principle, evaluate many possible solutions to a computational problem in parallel, rather than considering them one by one.

Primitive quantum computers have been built using laser-trapped ions and nuclear magnetic resonance, but it’s hard to keep their bits — or “qubits,” for quantum bits — in superposition. Superposition is much easier to preserve in photons, for exactly the same reason that it’s hard to get photons to interact.

The ability to switch an optical gate with a single photon opens the possibility of arrays of optical circuits, all of which are in superposition. “If the gate photon is there, the light gets reflected; if the gate photon is not there, the light gets transmitted,” Vuletić explains. “So if you were to put in a superposition state of the photon being there and not being there, then you would end up with a macroscopic superposition state of the light being transmitted and reflected.”

A photon-switched transistor has other implications for quantum computing. For instance, Vuletić says, one of the first applications of a conventional transistor was to filter noise out of an electrical signal by feeding the transistor’s output back into it. “Quantum feedback can cancel — to the extent allowed by quantum mechanics — quantum noise,” Vuletić says. “You can make quantum states that you wouldn’t otherwise get.”

The switch could also be used as a photon detector: If a photon has struck the atoms, light won’t pass through the cavity. “That means you have a device that can detect a photon without destroying it,” Vuletić says. “That doesn’t exist today. It would have many applications in quantum information processing.”

“Energy consumption in computing devices is a big issue,” says Jelena Vuckovic, a professor of electrical engineering at Stanford University. “The beauty of this approach is that it can really do switching at the single-photon level, so your losses are much smaller. You don’t have to spend a lot of energy for each bit. Your bit is essentially included in a single photon.”

Vuckovic believes that it should be possible to reproduce the MIT researchers’ results in physical systems that are easier to integrate into computer chips. “It’s exactly the same story, except that instead of using these ultracold atoms in the cavity, you use a microscopic cavity on a semiconductor chip on a semiconductor and you use a quantum dot grown inside of the semiconductor as an artificial atom,” she says. “There would be extra steps that people would have to take in order to implement the right energy-level structure. But in principle, the physics could be translated to a platform that could be cascaded and more easily integrated.”

By Larry Hardesty, MIT News Office

Securing the cloud

April 21, 2014

Homomorphic encryption is one of the most exciting new research topics in cryptography, which promises to make cloud computing perfectly secure. With it, a Web user would send encrypted data to a server in the cloud, which would process it without decrypting it and send back a still-encrypted result.

Sometimes, however, the server needs to know something about the data it’s handling. Otherwise, some computational tasks become prohibitively time consuming — if not outright impossible.

Suppose, for instance, that the task you’ve outsourced to the cloud is to search a huge encrypted database for the handful of records that match an encrypted search term. Homomorphic encryption ensures that the server has no idea what the search term is or which records match it. As a consequence, however, it has no choice but to send back information on every record in the database. The user’s computer can decrypt that information to see which records matched and which didn’t, but then it’s assuming much of the computational burden that it was trying to offload to the cloud in the first place.

Last week, at the Association for Computing Machinery’s 45th Symposium on the Theory of Computing — the premier conference in theoretical computer science — researchers from MIT’s Computer Science and Artificial Intelligence Laboratory, together with colleagues at the University of Toronto and Microsoft Research, presented a new encryption scheme that solves this problem. Known as a functional-encryption scheme, it allows the cloud server to run a single, specified computation on the homomorphically encrypted result — asking, say, “Is this record a match?” or “Is this email spam?” — without being able to extract any other information about it.

“This is a very, very general paradigm,” says Shafi Goldwasser, the RSA Professor of Electrical Engineering and Computer Science, one of the paper’s co-authors and, together with her fellow MIT professor Silvio Micali, the most recent recipient of the Turing Award, the highest award in computer science. “Say we’re talking about the surveillance cameras of the future, which come up with encrypted images. Why would we want to do that? It’s a question of liberty versus safety. If you’re looking for a suspect, you might be interested in doing some computations on an encrypted image, to match to the subject. Another possibility would be a medical database, where all the information is encrypted and … someone [runs] a drug study on those blood samples — but just that drug study, nothing else. Our result is in some sense the first result showing that you can do this very generally.”

Joining Goldwasser on the paper are Raluca Ada Popa, a graduate student in the Department of Electrical Engineering and Computer Science, her advisor, associate professor Nickolai Zeldovich, and Yael Kalai of Microsoft Research and Vinod Vaikuntanathan of the University of Toronto, both of whom did their graduate work at MIT with Goldwasser.

Near misses

The researchers built their functional-encryption scheme by fitting together several existing schemes, each of which has vital attributes of functional encryption, but none of which is entirely sufficient in itself. The first of those is homomorphic encryption.

Another is what’s known as a garbled circuit, a technique developed in the mid-1980s and widely used in cryptography. A garbled circuit lets a user decrypt the result of one cryptographically protected operation on one cryptographically protected data item — say, “Is this record a match?” The problem is that, if the garbled circuit is used on a second data item — “How about this record?” — the security breaks.

Moreover, a garbled circuit is a so-called private-key system, in which only the holder of a secret cryptographic key can encrypt data. Homomorphic encryption, by contrast, is intended as a public-key system — like most of the encryption schemes used to protect financial transactions on the Web. With public-key encryption, anyone can encrypt a message using a key that’s published online, but only the holder of the secret key can decrypt it.

The final component technique is called attribute-based encryption. Attribute-based encryption is a public-key system, and it’s reusable. But unlike garbled circuits and homomorphic encryption, it can’t reveal the output of a function without revealing the input, too.

The new system begins with homomorphic encryption and embeds the decryption algorithm in a garbled circuit. The key to the garbled circuit, in turn, is protected by attribute-based encryption. In some sense, the garbled circuit can, like all garbled circuits, be used only once. But the encryption schemes are layered in such a way that one use grants the server access to a general function rather than a single value. It can thus ask, of every record in a database, “Is this a match?”

Zeldovich points out that since the scheme relies on homomorphic encryption, it shares the major drawback of existing homomorphic schemes: They’re still too computationally intensive to be practical. On the other hand, he says, “It’s so new, there are so many things that haven’t been explored — like, ‘How do you really implement this correctly?’ ‘What are the right mathematical constructions?’ ‘What are the right parameter settings?’” And, Popa adds, in the four years since the invention of the first fully homomorphic encryption scheme, “People have been shaving off many orders of magnitude in performance improvements.”

Besides, even a currently impractical functional-encryption scheme is still a breakthrough. “Before, we didn’t even know if this was possible,” Popa says.

Ran Canetti, a professor of computer science at Boston University, corroborates that assessment. “It’s an extremely surprising result,” he says. “I myself worked on this problem for a while, and I had no idea how to do it. So I was wowed. And it really opens up the door to many other applications.”

One of those applications, Canetti says, is what’s known as program obfuscation, or disguising the operational details of a computer program so that it can’t be reverse-engineered. “Not obfuscating the way that people are doing it now, which is just scrambling up programs and hoping nobody will understand, and eventually, these are broken,” Canetti says, “but really obfuscating so that it’s cryptographically secure.”

Canetti acknowledges that the researchers’ scheme won’t be deployed tomorrow. But “I’m sure it’s going to lead to more stuff,” he says. “It’s an enabler, and people will be building on it.”
By Larry Hardesty, MIT News Office