Microsoft Research Blog

The Microsoft Research blog provides in-depth views and perspectives from our researchers, scientists and engineers, plus information about noteworthy events and conferences, scholarships, and fellowships designed for academic and scientific communities.

Maximum Overhang, Optimum Reward

March 3, 2011 | By Microsoft blog editor

By Janie Chang, Writer, Microsoft Research

Yuval Peres, principal researcher at Microsoft Research Redmond and manager of the Theory Group, always advocates both healthy skepticism and an open mind when it comes to problem solving. Even so, Peres was pleasantly surprised when a paper he co-authored won the prestigious David P. Robbins Prize from the Mathematical Association of America (MAA) for taking a completely new approach to a problem mathematicians had considered solved for decades.

Yuval Peres

Yuval Peres during the MAA’s 2011 Joint Mathematics Meetings. Photo courtesy of Laura McHugh, Mathematical Association of America.

Maximum Overhang—by Mike Paterson of the University of Warwick, Peres, Mikkel Thorup of AT&T Labs, Peter Winkler of Dartmouth College, and Uri Zwick of Tel Aviv University—builds on a paper titled Overhang, by Paterson and Zwick, the other paper cited in the prize. Together, the papers revisit a classic problem in mathematics: how to stack blocks on a table to achieve the maximum possible overhang—the farthest horizontal distance from the edge of the table.

“Like most people,” Peres recalls, “I had thought it seemed sensible to stack just one block at each level, which leads to the classical solution. I did not think of other possibilities. It’s good to retain some healthy skepticism of accepted wisdom.”

harmonic series

The key to the classic problem uses the harmonic series of 1 + 1/ 2 + 1/ 3 + 1/ 4 … sums logarithmically to infinity to create a “harmonic” stack of n bricks which extend out approximately 1/2 log n.

The David P. Robbins Prize is awarded for novel research in algebra, combinatorics, or discrete mathematics. The winning paper must be on a topic that is broadly accessible, written in a way that provides a simple statement of the problem and with clear exposition of the work. It certainly helped that the maximum-overhang problem has been a source of fascination for more than 150 years.

“Initially, it’s surprising,” Peres says, “that it is possible at all to get farther than one block of overhang away from the edge of the table without any glue. Once one finds the classical solution, related to the harmonic series, it seems so beautiful and satisfying. It seems counterintuitive that one could do much better—that’s one source of fascination.”

The topic fits into a general theme of crucial importance at Microsoft Research: constrained optimization.

“Optimization problems occur repeatedly in applications,” Peres says. “Scheduling jobs to different machines to minimize waiting times, deciding how frequently to crawl different websites when refreshing a search-engine index, setting up a network that will connect a set of processors at minimal cost—these can all be recast as optimization problems. Thus, developing new tools and insights pertinent to optimization is a key concern in the Theory Group at Microsoft Research.”

The prize-winning papers offer a different approach, first, by stacking blocks to resemble a badly built wall, with holes, jagged edges, and a solid stack that acts as a counterweight. This extends the overhang beyond what the classic stack can achieve using the same number of blocks.

30 blocks stacked

A classic stack of 30 blocks (in orange) compared to the same number of blocks configured as a jagged wall (in gray) held stable by counterweights (in blue).

Then, to push results even farther out, the team sought a solution that optimized for a large number of blocks and devised a radical shape that yielded exponentially better results than the classic approach.

It was Zwick who then noticed a connection between the block-stacking problem and “random walk,” a fundamental tool used in areas of computer science such as web algorithms, distributed networks, and theory.

“Since I have worked on many problems involving random walks,” Peres says, “he approached me to help expand on the work. The principles of statics allowed us, together with our co-authors, to relate the overhang problem to the following, seemingly unrelated problem: Starting with a unit of mass at the origin, how many moves does it take to move half the mass to distance n, where in each move a node k between -n and n is chosen and the mass at k is split evenly between k-1 and k+1. It is easy to see that order n3 moves suffice, and a key step of the Maximum Overhang paper was to show that this number of moves is also necessary.”

oil lamp stacked

An “oil lamp” stack, whose results astonished even the researchers.

In its citation, the MAA applauds the researchers for presenting both problem and arguments in a manner accessible even to math undergraduates, despite the inherently complex mathematics of the solution. For Peres, this criterion for the award is significant.

“It’s always great to get recognition,” he says. “But this award, besides being about mathematics, is also about exposition. As mathematicians, I think it is very important that we think more often about outreach and connecting to other people with different interests and motivations, to share our excitement and love of mathematics.”

The papers’ many illustrations are effective in communicating the work, a strategy familiar to Peres, whose webpage features beautiful, computer-generated images of mathematical constructs, courtesy of talented colleagues.

random walks

The proof in Maximum Overhang uses ideas from random walks: Start with mass 1 at the origin. How many mass-balanced splits are needed to get half the mass to distance d?

“I think images and simulations can play a major role in motivating mathematical research,” he says. “Those images hold an intrinsic beauty for both mathematicians and outsiders. You often hear about the beauty of mathematics, and, for me, some of that beauty is due to the unexpected patterns you find. Their mechanism gives no indication of why these patterns happen, so a lot of the math we do tries to explain the patterns. So far, the patterns are winning, because we can only explain a small part of what we see in the images. We are still very much challenged by them.”

The ongoing challenge of his research is one of the things Peres relishes most in his life.

“I enjoy cracking a hard problem,” he says, “preferably by bringing in perspectives from unexpected areas. I also love mentoring talented students, helping them become mathematicians. Best of all is when I can combine both these endeavors.”

He admits that he enjoys work so much he doesn’t spend enough time on hobbies such as hiking and swimming. Rather ruefully, he recalls overhearing his son, 6 at the time, asking a friend: “Do you have a religion? You know, a religion, like Jewish, or Christian, or Mathematics?”

“My wife would take our sons to synagogue on Saturday mornings,” he explains. “I used the time to go to the office and think about math. So he must have figured that whatever you choose to do on your Saturday mornings, that’s your religion.”

Peres has regarded the world through the lens of mathematics from a young age. His paternal grandfather, Julius Posener, was a physicist, educator, and violinist who took the time to discuss with Peres the mathematics of music and how mathematicians of the Renaissance solved cubic and quartic equations.

“I was 12,” Peres recalls, “when he explained to me the geometry of complex numbers. I remember emerging into the sunlight and thinking that now I had a new way to understand the world—and it would never look the same again. At 13, I inherited my grandfather’s scientific books, many of them probability books, and by 14, I was pretty sure I wanted to be a mathematician.”

Equally crucial to the way Peres regards his work has been the influence of his maternal grandmother.

“Though not formally educated in math,” Peres says, “she was a calculating whiz. Her favorite saying was, ‘Why should I be surprised when I can simply disbelieve?’ She taught me the virtues of skepticism—and also of keeping an open mind.”

The work on the maximum-overhang problem epitomizes a situation in which skepticism and an open mind have challenged conventional wisdom and have delivered new results.

“The point is that we need to be willing to re-examine some natural assumptions,” Peres says. “It seems so natural to stack each block one level above the other. Why would you place several blocks at the same level? If you follow that natural assumption, then yes, the classic solution is the best one.

“But if you think outside the box, you can obtain unexpected insights. I think the lesson, the whole philosophical point, is about the nature of problem solving. It’s about finding and re-examining the hidden assumptions we make before we even start to think seriously about a problem.”

Up Next

Algorithms, Artificial intelligence, Mathematics, Security, privacy, and cryptography

Tales from the Crypt(ography) Lab with Dr. Kristin Lauter

Episode 19, April 11, 2018 - Dr. Lauter tells us why she feels lucky to do math for a living, explains the singular beauty of elliptic curves and the singular difficulty of supersingular isogeny graphs, talks about how homomorphic encryption allows us to operate on, while still protecting, our most sensitive data, and shares her dream of one day, seeing a Grace Hopper-like conference to celebrate women in mathematics.

Microsoft blog editor

Algorithms, Artificial intelligence, Mathematics, Security, privacy, and cryptography

Second homomorphic encryption standardization workshop delivers the goods

What an exciting two days at the Second Homomorphic Encryption Standardization Workshop at Massachusetts Institute of Technology. More than 70 participants from 10 countries gathered together for two intense days of panels, discussions and planning and walked away with a significant milestone: the first draft standard for homomorphic encryption, Homomorphic Encryption Standard Section 1.0 and […]

Kristin Lauter

Principal Researcher, Research Manager

Artificial intelligence, Data visualization, analytics, and platform, Ecology and environment, Economics, Human-computer interaction, Mathematics, Medical, health and genomics, Social sciences

I Chose STEM – Event Recap

Earlier this week Microsoft Research Montreal celebrated the International Day of Women and Girls in STEM (science, technology, engineering and mathematics) with a one-day symposium: I Chose STEM. More than 200 Canadian STEM students and research community stakeholders joined Microsoft Research for inspirational keynotes, workshops and dynamic conversations that explored careers in research and the […]

Jessica Mastronardi