Windows On Theory

Some memories have staying power, and feel vivid and fresh like they happened yesterday. In this post I want to reminisce about the first problem I remember solving and give some context to it, which hopefully would be more interesting than the problem itself.

I was truly fortunate to begin my mathematical education in the unique environment of St. Petersburg in the late 80s (the city was called Leningrad back then, but I’ll stick with the current name). The basic unit of extracurricular math instruction was a circle—an entity consisting of motivated and self-selected kids of the same grade level led by several adults, typically young mathematicians or PhD students. A circle was a living and breathing organism that grew, thrived, matured and then withered away over the course of several years.

To call attending these circles a rite of passage is an understatement—it has been defining experience for several generations of St. Petersburg mathematicians. Both recent Fields medalist from St. Petersburg—Grisha Perelman and Stas Smirnov—progressed through all stages of this system from fifth-graders to lecturers.

This “system of math circles” as it is commonly known is documented in the excellent book by Masha Gessen “Perfect Rigor” in the chapters on early education of Grisha Perelman. Without attempting to give a comprehensive picture of how these circles operated, I mention here three core principles that sustained the system for more than 30 years.

The first was casting a wide net, bringing in all interested middle schoolers (11–13-year-olds). The attendance in the first year could easily exceed a hundred kids, split into several groups of about 30. The number of students naturally diminished over time, with only a handful making it to the last year of high school. Upon graduation, alumni were often co-opted into the mentoring ranks, and this practice of training its own instructors proved surprisingly resilient even in the face of mass exodus of Russian mathematicians in the late 80s and early 90s.

The second principle was emphasis on hearing students out on every one of their solutions. A typical meeting of a circle began with students explaining their solutions to homework problems in one-on-ones with the instructors. It was followed by presentation of complete solutions on the blackboard by an instructor and a lecture that could be part of a longer course (such as introduction to graph theory or complex analysis).

The third principle was what now would be called gamification of mathematical instruction. The math circles were integrated with the system of mathematical Olympiads, and essential component of their formula was practicing on competitive math problems. The connection ran deeper: competitiveness was encouraged by keeping track of the students’ individual accomplishments, and math Olympiads were important milestones of the circle’s annual cycle. Even more significantly, much of the standard math curriculum, roughly corresponding to the requirements of a typical math major in the US, was taught through a series of small, tractable problems rather than lengthy lectures. There was a place for lectures too but they were mainly used to introduce definitions and discuss examples (the appropriate buzz word du jour is “flipped classroom”). Two outstanding books, translated from Russian, exemplify this approach to mathematical instruction: “Elementary Topology” by Viro et al. and “Abel’s Theorem in Problems and Solutions” by Alekseev. This really conveyed a sense of mathematics as something to be discovered (and discoverable!) rather than passively imparted or handed down from on high.

That was the backdrop (to which I was blissfully oblivious) to the first session of the math circle I attended in March of 1988 at twelve years of age. A set of problems was distributed, and we were asked to report solutions at the next meeting. One problem, which many readers will recognized as an old classic, read as follows:

A standard chessboard has two opposite corners removed. Each of the 62 remaining squares is occupied by an ant. On cue, all ants crawl to adjacent squares (sharing a side with the square they have come from). Prove that two ants will end up in the same square.

At the next meeting I began explaining my “solution” to a student volunteer, who had to endure some inarticulate nonsense along the lines of “I tried arranging the ants every each way, and it didn’t work”. He gently offered a few hints, and finally asked whether I could think of some characteristic specific to the chessboard and suggested that I drew it in my notebook. That was the moment when the light bulb went off: “The squares are black and white, and there are 30 blacks and 32 whites!” Indeed, each ant has to move to a square of the opposite color, and there are more white squares than black. Even writing this, I get choked up, recalling the sensation of suddenly seeing a crisp and elegant solution instead of a swarm of ants crawling all over the place. This is how the pigeonhole (Dirichlet) principle was introduced, and I got hooked and stayed with the circle.

Trying to convince E. Abakoumov. Will he or will he not? 1989, by Simon Bliudze.

Twice-weekly sessions of the math circle led to a summer camp, with three weeks of several hours of math per day. This became an annual ritual until I graduated from the high school, which recruited from the same math circle, and then came back as an instructor. Intellectually it was a fairly cloistered environment but it did lead to many wonderful things in my life, and it was more than balanced by seismic shifts happening in the world outside (the country ceased to exist, for one).

All math circles reflected personalities of their leaders. The hallmarks of mine was a high number of girls, due to Anna Bogomolnaia’s efforts, and its bias towards mathematical analysis, fueled by professional interests of other instructors—Evgueni Abakoumov, Lev Parnes (who tragically died in 1993), Evgeny Dubtsov, and Fedor Nazarov. They all shared passion for teaching, learning, and practicing mathematics, which proved to be infectious for many of my fellow members.

I fell under the spell of computers and CS while still attending the math circle, but that’s a different story.

Update: This post would be incomplete without referencing two books: one very recent, “Mathematical Circle Diaries, Year 1: Complete Curriculum for Grades 5 to 7″ by Anna Burago, and one slightly older, aptly titled “Mathematical Circles: Russian Experience” by Dmitri Fomin, Sergey Genkin (my math-circle grandfather and a fellow Microsoftie) and Ilia Itenberg.

Next story on our project from Russell Impagliazzo

———————

It was my first semester at Wesleyan University. I was shuffling down the path crossing the main lawn in front of the administrative building in a jacket that was not warm enough. I had decided to astound my German professor by actually putting in a half hour or so in the language lab before class, but I was thinking about a math problem and not really paying attention to my surroundings.  My forward progress got slower and slower, until I stopped completely and took out a notebook and pen.

Peripherally, I saw someone approaching across the grass, a bearded student like myself, but with a more energetic pace. I didn’t really pay attention to him, lost in my own thoughts. I was surprised when he addressed me by name, asking “Are you Russell?”.

I looked around to see if there was another Russell on the path, but I was alone.  “Yes” I answered hesitantly.

“I’ve been wanting to meet you. ” the stranger said, “The word in the Math lounge is that you can prove anything by transfinite induction.”

I don’t know what shocked me more: that faculty gossipped about me, or that this guy was in on their gossip.  He was too young to be a grad student, let alone a prof. But the mention of transfinite induction put me on surer ground.  He used the words in an everyday tone, like he knew what they meant, and was not just parrotting something he heard.  So I decided to plunge right in.

“Well, uh,  I guess it’s kind of a lazy habit.  I, um,  just like to be able to well-order every set in sight.  It makes the arguments more concrete.”

“More algorithmic,” the strange student agreed, with an air that he had just made a subtle point. “So I take it that you’re a true believer in the Axiom of Choice?”

“Well, the Xorn’s Lemma version is counter-intuitive, but I can’t see how the product of non-empty sets could be empty”, I replied with a chuckle.  “The way I see it, if any logically equivalent formulation of an axiom  is self-evident, then we should accept it, even if other formulations are less clear.”

“Plus, it’s relatively consistent, so if set theory is consistent, so is set theory with Choice.” Here, he was showing himself to have knowledge beyond my level.

“Really?  How do you prove that?”  This came across as a challenge, but I was really just excited to think that this kind of statement was actually formally provable.

“I’m not sure.  But Kevin should cover it in logic next semester.  I assume you’re taking that class.” He said this as if someone  would have to be crazy not to.

“I haven’t really looked at the course catalog yet, but that sounds great.  Who’s Kevin?”  Not only didn’t I address faculty by their first names, I was only dimly aware they had them.

“Kevin Compton is the closest we have to a theoretical computer scientist in the department.   He’s really a logician, but he also works on recursion theory and computational complexity.  You know, P = NP .”

“I did see P=NP mentioned in some class’s syllabus, but it didn’t make sense to me.  I take it P and N aren’t just variables, because that equation isn’t really worth discussing.”

“No, P vs. NP is the most important problem in mathematics, because it captures the essential difficulty of doing mathematics.   Working on the P vs. NP problem is what brought me back into computer science. That, and the FFT.”

Somewhat disappointed because I’d hoped that he was a mathematician like myself, I replied, “Um, I’m taking CS right now, and I have to say I really hate it.  It’s so subjective.  I have to tell my roommate how to solve every problem, but he still gets better grades than me, because they say I have poor “style” and don’t  “document”.”

“You just have a bad teacher.  I’ve never met someone mathematically competent who wasn’t also a talented programmer.  Anyway, you looked deep in thought when I approached you just now.  What were you thinking about?”

“Geometry, but it’s sort of related to logic.   I was thinking about what we would need to add to the definition of metric space to get an actual geometry, and that got me thinking about how  our concepts of numbers and geometry are related. Euclid gave us the idea of proving theorems from axioms, but to make sense of his axioms, you need to already know what a number is.  But we’ve also gotten our idea of number from geometry, with our idea of real number being a consequence of distances like the hypoteneuse of a right triangle with equal sides being irrational.  So there’s kind of a circularity, and maybe we’re jumping to conclusions both about possible geometries and possilbe kinds of numbers.  So what I want to do is make axioms for both geometry and the concept of number that can be used for stuff like distances, areas, and so on, and see what other types of `numbers’ could be used in a geometry.” I illustrated my comments by pointing to the diagrams and equations I had been writing in my notebook when he approached.

The stranger seemed able to absorb my ideas even if they came out of my mouth in a kind of incoherent jumble. It had started to snow lightly, and a dusting of fresh snow covered the path we stood on.  The computer science student  didn’t have a jacket, and was keeping warm by doing some kind of dance move exercise that involved shifting balance in complex ways. I had been standing stock still while talking,  and sprinkles of snow covered  my hair and coat.

“Anyway,” I continued, “ I was thinking that “numbers”, whatever they are, should have an ordering, so we can talk about greatest or smallest distances, and an operation, so we can talk about the sum of distances.”

My new friend said, “Like a group operation?”

“I think so.  It should be commutative and associative.  Is that what a group is?  I haven’t taken Abstract Algebra yet, so my only knowledge is from this book I skimmed for a high school math project.”

“What was the project?”

“It turned out to have nothing to do with Abstract Algebra.  I was just looking at the way we define addition as repeated adding one, and multiplicaction as repeated addition, exponentiation as repeated multiplication, and generalizing.”

“Oh, you mean the Ackerman functions.  Yes, I’ve been thinking about what happens if you extend the Ackerman functions to the cardinal numbers.”

“Oh, someone’s looked at them already?  And don’t you mean extend them to the {\em ordinals} , not the {\em cardinals}?”

The stranger took mild offense at this suggestion.  “I’m like Alice.  I say what I mean.  I think it would be interesting to extend them to the {\em infinite cardinals}. ”

“But the successor operation for ordinals is so simple and for cardinals, it’s not really understood.”

The argument continued for a  while.  When I looked at my watch, German class was almost over. I was also getting very cold.  So I suggested we continue the conversation back at my dorm. As we neared the top floor, his nose crinkled. The bottom three floors of Harriman Hall had been converted to classrooms, but the top floor, where I lived, had been spared largely because my room had a great view of the playing field.  Whenever there was a football or baseball game, my room, the room opposite, and the corridor in between, were unofficially converted to extra stadium seating for the alumni.  We didn’t charge admission, but we did sell them booze at a mark-up, and the dorm still stank of cheap booze from the last game, especially my room.  My roommate Kimo was playing pop songs on his new electronic keyboard and singing along in his cracked voice at full volume. When I thought to introduce Kimo to the new student, I realized I hadn’t asked his name.  It would be embarrassing to ask now.  Bringing my new friend here was a serious mistake, and we wouldn’t even be able to continue our conversation.

Then Taco, the Japanese economics student next door, walked in. He looked up at the computer science student and exclaimed, “Digit!”  It turned out that they had gone to the same prep school, and began reminiscing happily.    So I had a name to call my new friend, even if it was a nerdy nickname even I was somewhat embarrassed to use.  (Of course, Takeshi was OK with calling himself “Taco”, and he called me “Scruffy”, so his standards for nicknames were pretty low.)

Taco had come by to challenge me to a game of Othello.  The whole dorm had undergone a fad for this strategy game, and Taco was the reigning champ. “Digit” encouraged us to play (in Taco’s room), and kibitzed during our game, that “Othello is an OK game, but it’s really just a simplification of go.” Taco agreed with this assesment, but claimed not to be smart enough to handle go.  “What’s go?” I asked, shocking Digit completely. “Go is mathematics and computer science put into a boardgame.  It’s boardgame complete! I’ll have to teach you; I know you’re going to be crazy about it. I learned it as part of a plan to seduce my  now-girlfriend Julia, but she quit go after I beat her in our third game. Fortunately, the seduction worked anyway.    Since then, I’ve ordered a complete set of go textbooks from Japan. They read like math books- Lemma! Pow! Theorem! Pow! QED! ” This reminded Digit that Julia was expecting him for dinner, so he left while we were still playing.

I think of that meeting as the time I became a mathematician.  Of course, I was interested in math before then, and even starting to have my own ideas.  But until then, I was just learning and thinking about mathematics for myself. After that, I had someone to share my ideas with.   The extent to which they would interest “Digit” (who was now known as “Steven Rudich” to all but high school friends) became my standard for judging my mathematical ideas. Before, every idea was equal.  Now, I had to be able to explain and justify my interests to Steven.  Before, novelty was judged by solely by whether I knew it already.  After, I had to be prepared to deal with anything Steven might know, and Steven knew a lot already. Mathematics moved from a purely intellectual activity to how mathematicians actually do mathematics, as a social activity.  Steven and I are still frequent collaborators.  He’s my intended audience whenever I’m thinking of new mathematical ideas.

Thanks to Steven Rudich and Beth Dugan for suggestions on an earlier version.

Our project continues with Bobby Kleinberg.

————————————————————

As an undergraduate I majored in mathematics and took only one computer science course. In fact quite a few of the mathematicians who influenced me were openly dismissive of computer science. Of course, throughout this period my brother Jon would continually talk to me about TCS — a subject he had chosen to pursue a couple of years earlier — so I was well aware of some of the mathematical gems the field contained. But I fell in love with topology and went to graduate school with my heart set on becoming a topologist.

Early in my first year of grad school, at one of the innumerable dinners in Central Square with officemates, we started debating the question, “What are the greatest mathematical discoveries of the 20th century?” My own candidate, Gödel’s Incompleteness Theorem, didn’t get much traction with this group. A common thread among the suggested alternatives was that a great deal of specialized knowledge was required even to understand the statement of the theorem, much less apprehend its significance. This struck me as a very sad state of affairs, and it still does. My favorite pieces of mathematics are those that apply deep methods to derive elementary consequences. I acknowledge the value of the more specialized papers that often enable those discoveries, but when a subfield of mathematics turns so far inward that its greatest discoveries are impenetrable to non-specialists, it is a loss for the mathematics community as a whole. My feelings on this subject were reinforced in 2010 when experts tried in vain to explain the work of Fields Medalist Ngô Bảu Châu to the mathematical public.

Though I didn’t know it at the time, this incident prefigured two years of growing disillusionment with the state of contemporary research on geometry and topology, which was increasingly focused on questions that I found to be excessively distant from geometric intuition. By the spring of my second year of graduate school, I was devoting my creative energy to an esoteric topic in algebraic topology whose importance I couldn’t explain even to myself; if the research were to succeed, I couldn’t point to a single mathematical consequence that might turn out to be of interest to me. It was obvious that a change was needed. (Aside: in hindsight, there were — and still are — plenty of wonderful topics of active research in geometry and topology that probably would have satisfied my intellectual cravings at the time. For example, I bet that if I had known more about Gromov’s work at the time, I would have been hooked on it.)

To “reboot” my search for a research topic, I discovered that I needed to give myself a break from grad school, and thus I started looking for a summer job. At the time this felt to me like an act of desperation, but it turned out to be the most pivotal decision of my career. I took a job at Akamai Technologies, which was then a start-up with just under 100 employees. Shifting from the algebraic topology group at MIT to the Mapping Group at Akamai felt, to me, almost as abrupt and disorienting as Dorothy’s arrival in the Land of Oz. After nearly two years of working painfully slowly, in near-isolation, on problems whose importance I couldn’t justify even to myself, I found myself, literally overnight, embedded in a team of people rushing at top speed to solve problems with a startlingly direct impact on reality: influencing, for example, the length of time it took for different users worldwide to load Yahoo’s home page. The sense of shared purpose, and the pride in working on a system used by billions of people, were intoxicating to me. Instead of spending one summer at Akamai, I ended up staying there for three years. This was one of the most productive and fulfilling periods in my career so far. While the work didn’t involve proving theorems, I was pleased to find that it exercised some of the same problem-solving skills that I enjoyed using when working on mathematics. And Akamai at that time was loaded with world-class theoreticians. Working alongside those people made it much easier, later on, for me to feel integrated into the theory research community when it became my intellectual home.

In 2002 I was still loving my job at Akamai, but I could tell that my future lay in more mathematical pursuits, so I returned to graduate school. I still faced a choice between theoretical computer science and topology; my industry experience had whet my appetite for TCS, but my love for topology had remained with me. Reflecting on the many factors that pushed me toward TCS over the course of the next year, three things stand out in my mind. The first is the extreme awesomeness of Santosh Vempala’s course on random walks and convex geometry and Madhu Sudan’s course on essential coding theory, the two most interesting courses I took that year. The second is my brother’s inspired decision to give me Motwani and Raghavan’s textbook “Randomized Algorithms” for Hanukkah the winter before my return to grad school. I’ve never asked him if he intended the gift as a form of gentle persuasion (at the time, all he said is that he thought I would enjoy reading it) but it certainly had that effect.

The third, and most important, thing that pushed me towards TCS was the experience of starting to do research with Tom Leighton. Having worked together quite closely at Akamai, Tom and I already had an easy, familiar relationship with each other. (How many grad students have had the experience of staying up all night working with their advisor, before they ever started collaborating on research?) Tom’s instincts as an advisor, I now realize, were miraculous. He knew how to bring out the best in me, using his fierce intelligence to inspire rather than demoralize me. In situations where I might say to my student, “I bet that X is true, and if so then Y seems to follow, but you should try to prove it,” Tom instead says, “Suppose for a second that X were true; then do you think we could prove Y?” (And, when questioned about why he believes X, he insists with a self-deprecating smile that he’s just speculating and would be excited to see a proof.) When I would give an overly sophisticated proof of some step and Tom came up with an elementary argument on the spot, instead of “Here’s an easy proof you missed,” he would say, “You’re so good at proving things that way. I’ll never get the hang of it, which is why this other proof is more natural for me.” And for any result that I could present to him, he could identify an extension that seemed even cooler, and potentially within reach.

My second paper with Tom introduced me to two topics (multi-armed bandits and algorithmic pricing) that became mainstays of my research in subsequent years. More importantly for me at the time, the paper “put me on the map.” To my surprise, people whom I venerated heard about the result and sought me out: Baruch Awerbuch called out of the blue to see if I wanted to help with a problem he had been thinking about; Éva Tardos approached me at a conference and said, “I hear you have a result I should find out about.” From that moment onward, my research became self-sustaining: each project I worked on generated more ideas for other projects, and more opportunities to meet new people and try absorbing their ideas.

About a year later, my wife Miranda asked me to describe my research over brunch at the Town Diner. (If you ever go to Watertown, Massachusetts, eat there! And order the sweet potato pancakes.) This was the first time I had tried to summarize all of my papers at once, and in the course of explaining the research to her it dawned on me that I had a Ph.D. thesis. After spending so many years worrying how I would choose a thesis topic, I marveled at how the topic had instead materialized through the (largely unplanned) accumulation of inter-related projects.

Reflecting on my transformation from a frustrated aspiring topologist to a fulfilled theoretical computer scientist, I am torn between two contrasting narratives that account for the pattern of events. In one narrative, I was adrift intellectually until I worked for Akamai. That experience guided me to a set of topics (routing, learning, pricing) that were both a natural outgrowth of the work and a firm basis for my Ph.D. thesis. In the other narrative, the process was unplanned and serendipitous. I joined Akamai to escape from grad school, not to gain a new viewpoint on research. I stumbled upon multi-armed bandits and algorithmic pricing, not because I perceived their potential as a research theme, but because Tom and I wanted to solve a cute problem he had heard about while visiting Ticketmaster. Instead of choosing a thesis topic, I decided to stop worrying about The Big Choice and work on individual problems that struck me as interesting, only to discover afterward that they could be presented as a unified contribution. Order or chaos? It’s impossible to choose between the two explanations. My research-life story, like everyone else’s, can only be explained with a healthy dose of both.