Tanya Khovanova's Math Blog

I started my life wanting to be a mathematician. At some point I had to quit academia in order to feed my children. And so I went to work in industry for ten years. Now that my children have grown, I am trying to get back to academia. So I am the right person to compare the experience of working in the two sectors. Just remember:

• This is my personal experience.
• I am not a professor, so I never experienced the best part of academia.
• My academic experience was at Princeton and MIT: a very selective set.

Money. The pay is much better in industry. About twice as high as academia.

Time. I almost never had to work overtime while working in industry. That might not be true for programmers and testers. As a designer, I worked at the beginning of the project stage. Programmers and testers are closer to deadlines, so they have more pressure on them. The industrial job was more practical than conceptual, so I didn’t think about it at home. My evenings and weekends were free, so I could relax with my children. In academia I work 24/7. There are 20 mathematical papers that I have started and want to finish. This is a never-ending effort because I need those papers to find my next job. Plus, I want to be a creative teacher, so I spend a lot of time preparing for classes. I do not have time to breath.

Respect. When I was working in industry, some of my co-workers would tell me that I was the smartest person they ever met. In any case, I always felt that my intelligence and my skills were greatly appreciated. In academia, I am surrounded by first-class mathematicians who rarely express respect and mostly to those who supersede them in their own fields.

Social Life. Mathematics is a lonely endeavor. Everyone is engrossed in their own thoughts. There is no urge to chat at the coffee machine. In industry we were working in teams. I knew everyone in my group. I was closer to my co-workers when I worked in industry.

Freedom. In both industry and academia there are bosses who tell you what to do. But while building my university career, a big part of my life is devoted to writing papers. It is not a formal part of my job, but it is a part of the academic life style. And in my papers I have my freedom.

Motivation. In academia, one must be self-motivated.

Rejection. The output of an academic job is published papers. Most journals have high rejection rates. For me, it’s not a big problem because from time to time I get fantastic reviews and I usually have multiple papers awaiting review. I have enough self-confidence that if my paper is rejected, I don’t blink. I revise it and send it to a different journal. But this is a huge problem for my high school students who submit their first paper and get rejected. It is very discouraging.

Perfectionism. In industry I was working on deadlines. The goal was to deliver by the deadline a project that more or less worked. Time was more important than quality. My inner perfectionist suffered. When I write papers, I decide myself when they are ready for publication.

Impact. When I was working at Telcordia I felt that I was doing something useful. For example, we were building a local number portability feature, the mechanism allowing people to take their phone numbers with them when they moved. I wish Verizon had bought our product. Just a couple of months ago I had to change my phone number when I moved five blocks from Belmont to Watertown. Bad Verizon. But I digress. When I was working at Alphatech/BAE Systems, I was designing proofs of concepts for future combat systems. I oppose war and the implementation was sub-standard. I felt I was wasting my time. Now that I am teaching and writing papers, I feel that I am building a better world. My goal is to help people structure their minds and make better decisions.

Fame. All the documents I wrote in industry were secret. The world would never know about them. Plus, industry owns the copyright and takes all the credit. There is no trace of what I have done; there is no way to show off. People in academia are much more visible and famous.

Happiness. I am much happier now. I do what I love.

I gave the following puzzle from Raymond Smullyan’s book What is the Name of this Book? to my AMSA students.

What happens if an irresistible cannonball hits an immovable post?

This puzzle is known as the Irresistible Force Paradox. The standard answer is that the given conditions are contradictory and the two objects cannot exist at the same time.

My AMSA student gave me a much cuter answer: The post falls in love with the cannonball as it is so irresistible.

It has been a while since I wrote my last essay and my readers have started to worry. Sorry for being out of touch, but let me tell you what is going on in my life.

In September I received an offer from MIT that changes my status there. In exchange for a slight increase in pay, I am now conducting recitations (supplemental seminars) in linear algebra In addition to my previous responsibilities.

My readers will know that just a slight increase in money in exchange for significant demands on my time would not appeal to me. But this offer comes with perks. First, my position at MIT changes from an affiliate to a lecturer, which looks so much better on my CV. Second, it includes benefits, the most important of which is medical insurance.

I lived without insurance for three years. On the bright side, lack of insurance made me conscious of my health. I developed many healthy habits. I read a lot about the treatments for colds and other minor problems that I had. On the other hand, it is a bit scary to be without insurance.

Many people are surprised to hear that I didn’t have any insurance: Doesn’t Massachusetts require medical insurance for everyone?

The Commonwealth levies a fine on those who do not have insurance. But I was in this middle bracket in which my income was too high for a subsidized plan, and too low to be fined. You see, the fine is dependent on one’s income and is pro-rated. So I didn’t have to pay it at all.

I got my insurance from MIT in October, but ironically my doctor’s waiting list is so long, that my first check-up will not be until January.

Anyway, I sort of have four jobs now. I am coaching students for math competitions at the AMSA charter school six hours a week. I am the head mentor at the RSI summer program where I supervise the math research projects of a dozen high school students. I do the same thing for the PRIMES program, in which I have the additional responsibility of mentoring my own students. And as I mentioned, I am also teaching two recitation groups in linear algebra at MIT.

Teaching linear algebra turned out to be more difficult than I expected. I love linear algebra, but I had to learn the parts of it that are related to applications and engineering. Plus, I didn’t know linear algebra in English. And my personality as a perfectionist didn’t help because to teach linear algebra up to my standards would have taken more time than I really had.

This semester I barely had time to breathe, and I certainly couldn’t concentrate on essay pieces. Now that this semester is almost over, my as yet unwritten essays are popping up in my head. It’s nice to be back.

Hooray! My weight is down to two digits in kilograms: below 100. This is a big deal for me. I reached the desired number of digits. In pounds it means I weigh less than 220 and I’ve lost 25 pounds.

My friends have started to notice. The chubbier ones ask me to tell them about my Yellow Road. And I don’t actually know what to reply, because the Yellow Road is not a solution. I took many steps before I approached the Yellow Road. The Yellow Road is, I hope, the end of the road.

The idea of the Yellow Road is simple. If I weigh more than I want, I decrease food. All my skinny friends have always lived that way. The problem is that the rest of us do not know how exactly to reduce food intake and then how to sustain that reduction.

So today, I would like to explain to my friends and my readers what I really think helped me to lose weight.

1. I got desperate. I was ready to do whatever it takes. I was prepared not to ever eat again. If I had to extract my calories from the air, I was prepared to do that. I was ready to be hungry and restrain myself for the rest of my life. In short, I was totally motivated.

2. I fought my sugar addiction. I used to crave sugar. I used to think that sugar helps my brain. But once I looked into it, I realized that I might be wrong. I decided to experiment and cut off my carbohydrates intake significantly. That was the most painful thing I had to do. But after a week of withdrawal symptoms, I felt better and stopped craving foods and sugars as much.

3. I wrote my weight down everyday. Having numbers staring me in the face reminded me what I ate the day before. This moment of reflection allowed me to understand what causes the increase or decrease in my weight. Now I know that some foods provoke my appetite: carbohydrates, dairy, mayonnaise. I eat them in small portions, but I do not start my day with them. It’s better to have an increased appetite for a couple of hours in the evening, than for the whole day.

4. I had already changed some bad habits. I tried to build new healthy habits before I started my Yellow Road. These alone didn’t help me lose weight, but I think they contribute to my weight loss. I still do the following:

• I get organic fruits and vegetables delivered weekly from Boston Organics.
• I buy no more than one item of desert when I shop.
• At a restaurant, I divide my portion in half. I eat one half and wait for a minute. More often than not, I take the other half home.
• I talk to myself. Currently, I am persuading myself that at a party, I don’t have to try every dish: I can try half of them, hoping that the other half will be at the next party.

I feel that an internal switch was turned off. I don’t feel that hungry anymore. My son thinks that I’m in my hibernating state. I wonder if he is right and I will awake one day as hungry as ever.

My son, Alexey Radul, is gainfully unemployed. While looking for a new job he wrote several essays about his programming ideas. I am a proud and happy mother. While I can’t understand his code, I understand his cutting-edge essays. Below are links to the four essays he has posted so far. He is also a superb writer. You do not need to take my word for it. Each link is accompanied by the beginning of the essay.

• Digital FoxesThe successful fox must know more than the sum of what the hedgehogs know, for it must know the connections from one thing to another. This fact is key to the design of computer systems for solving certain kinds of problems. Read more
• Introduction to Automatic DifferentiationAutomatic differentiation may be one of the best scientific computing techniques you’ve never heard of. If you work with computers and real numbers at the same time, I think you stand to benefit from at least a basic understanding of AD, which I hope this article will provide; Read more
• On the Cleverness of CompilersThe “Sufficiently Clever Compiler” has become something of a trope in the Lisp community: the mythical beast that promises language and interface designers near-unlimited freedom, and leaves their output in a performance lurch by its non-appearance. A few years ago, I was young enough to join a research project to build one of these things. Neglecting a raft of asterisks, footnotes, and caveats, we ended up making something whose essence is pretty impressive: you pay for abstraction boundaries in compile-time resources, but they end up free at runtime. One prototype was just open-sourced recently, so that makes now a good time to talk about it. Read more
• Cleverness of Compilers 2: HowThe Cleverness of Compilers essay described the name of the hyperaggressive compilation game in broad, philosophical strokes. Here, I would like to walk through the Mandelbrot example in some detail, so that the interested reader may see one particular way to actually accomplish that level of optimization. Read more

I submitted four papers to the arXiv this Spring. Since then I wrote four more papers:

• (with Leigh Marie Braswell) Cookie Monster Devours Naccis. History and Overview arXiv: arXiv 1305.4305.

  In 2002, Cookie Monster appeared in The Inquisitive Problem Solver. The hungry monster wants to empty a set of jars filled with various numbers of cookies. On each of his moves, he may choose any subset of jars and take the same number of cookies from each of those jars. The Cookie Monster number is the minimum number of moves Cookie Monster must use to empty all of the jars. This number depends on the initial distribution of cookies in the jars. We discuss bounds of the Cookie Monster number and explicitly find the Cookie Monster number for Fibonacci, Tribonacci and other nacci sequences.

• A Line of Sages.
  • PDF.

  A new variation of an old hat puzzle, where sages are standing in line one behind the other.

• (Jesse Geneson and Jonathan Tidor) Convex geometric (k+2)-quasiplanar representations of semi-bar k-visibility graphs. Combinatorics arXiv: arXiv 1307.1169.

  We examine semi-bar visibility graphs in the plane and on a cylinder in which sightlines can pass through k objects. We show every semi-bar k-visibility graph has a (k+2)-quasiplanar representation in the plane with vertices drawn as points in convex position and edges drawn as segments. We also show that the graphs having cylindrical semi-bar k-visibility representations with semi-bars of different lengths are the same as the (2k+2)-degenerate graphs having edge-maximal (k+2)-quasiplanar representations in the plane with vertices drawn as points in convex position and edges drawn as segments.

• (with Leigh Marie Braswell) On the Cookie Monster Problem. History and Overview arXiv: arXiv 1309.5985.

  The Cookie Monster Problem supposes that the Cookie Monster wants to empty a set of jars filled with various numbers of cookies. On each of his moves, he may choose any subset of jars and take the same number of cookies from each of those jars. The Cookie Monster number of a set is the minimum number of moves the Cookie Monster must use to empty all of the jars. This number depends on the initial distribution of cookies in the jars. We discuss bounds of the Cookie Monster number and explicitly find the Cookie Monster number for jars containing cookies in the Fibonacci, Tribonacci, n-nacci, and Super-n-nacci sequences. We also construct sequences of k jars such that their Cookie Monster numbers are asymptotically rk, where r is any real number between 0 and 1 inclusive.

This is my toast at the Gelfand’s Centennial Conference:

I moved to the US twenty years ago, right after I got my Ph.D in mathematics under the supervision of Israel Gelfand. My first conversation with an American mathematician went like this:

The guy asks me, “What do you do?”

I say, “Mathematics.”

“No, I mean what is your field?”

I can’t understand what he wants, and repeat “Mathematics.”

He says, “No, no, I mean, I do differential geometry. What do you do?”

I do not know how to answer him. My teacher, Israel Gelfand, never mentioned that mathematicians divide mathematics into pieces. So I had to repeat, “My field is mathematics.”

I got asked this question many times and I couldn’t figure out how to give a satisfactory answer, so I quit academia. Well, I quit it not because of the question, but for many other reasons… But answering the question became so much easier when I worked for industry.

A guy asks me, “What do you do?”

I say, “Battle management.”

He says, “What?”

I say, “Battle management. I manage battles, in case there is a war.” And this is it, he doesn’t ask any more questions … ever.

I always knew that industry was not the right place for me. Five years ago, when my children grew up, I realized that it was time to take some risks. So I resigned from my job, and came back to mathematics. But now I know how to answer the question. When someone asks me, What is your field in mathematics? I say, … brag, “I am a student of Israel Gelfand, I just do mathematics.”

I would like to drink to the Unity of Mathematics.

Now that my weight loss is under way, I want to build an exercise program.

I already exercise. I am a member of the MIT ballroom dance team and I go to the gym, where I use the machines, swim, and take gentle yoga and Zumba classes.

Doesn’t sound bad, right? But the reality is that I went to Zumba class a total of three times last year. I skipped half the dance classes I signed up for because I was too tired to attend. I had sincerely planned to go to them, but they’re held in the evenings, when I’m already drooping.

The yoga situation is the worst. I’m scheduled to go to yoga twice a week, but just as it is time to leave for yoga, I get very hungry and cannot resist having a snack. Then I remember that they do not recommend practicing yoga after eating a meal, and voilà—I have found my excuse. I am all set up to exercise five hours a week, but in reality most weeks I do not exercise at all.

How can I motivate myself? I know that with food, if I have gained weight one day, I eat less the next. So if I’ve missed my goal of exercising one week, do I add those hours to the next week? That’s unlikely to actually help, since the problem is that I’m not meeting my exercise goal, period.

Many people suggested that I punish myself. For example, if I do not meet my goal, I should donate money to a cause I do not support. This feels wrong. If I fail, I’ll feel doubly guilty. I’ll go broke paying for psychotherapy.

I can try to reward myself. But what should the reward be? Should I reward myself with a piece of tiramisu? Since I am trying to persuade myself that sugar is bad, I shouldn’t create a situation that makes sugar desirable. So rewarding with food won’t work. Should I buy myself something? If I really want it, I will buy it anyway.

I’ve been thinking about a plan for a long time. Finally I realized that I should find other people to reward me. I do have a lot of friends, and I came up with an idea of how they could help.

The next time I saw my friend Hillary I asked her if she wanted to sponsor my new exercise plan. She said, “I’m in,” without even hearing the plan. Hillary is a true friend. This is what she blindly signed up for.

I decided to push myself to exercise five hours a week. Because of weather and health fluctuations, I pledged to spread 20 hours of exercise over four weeks. I will sent Hillary weekly reports of what I do. This is in itself a huge motivating factor. After the four weeks, we will go to lunch together, which is a great reward for me to look forward to. If I succeed with my plan, she pays for lunch. If I fail, I pay.

Once I saw how enthusiastic Hillary was, I lined up four other friends for the next four-week periods. I hope that after several months of exercise, I will learn to enjoy it. Or at least, I will start feeling the benefits and that itself will be a motivating factor.

Hillary liked my plan so much that she designed a similar exercise plan for herself. Now I am looking forward to two lunches with Hillary.

I was driving on Mass Pike, when the cars in front of me stopped abruptly. I hit the brakes and was lucky to escape the situation without a scratch.

Actually, it wasn’t just luck. First of all, I always keep a safe distance from the other cars. Second, if I see the brake lights of the car in front of me, I automatically remove my foot from the gas pedal and hold it over the brake pedal until I know what the situation is.

On a highway, if the car in front of me has its brake lights on, usually that means that the driver is adjusting their speed a little bit. So, most of the time I don’t have to do anything. Seeing that the car in front of me has its brake lights on is not a good predictor of what will happen next. Only after I see that the distance between me and the car in front of me is decreasing rapidly, do I know to hit my brakes. That means that brake lights alone are not enough information. Differentiating between insignificant speed adjustments and serious braking requires time and can cost lives.

I have a suggestion. Why not create smart brake lights. The car’s computer system can recognize the difference in the strength with which the brakes are hit and the lights themselves can reflect that. They can be brighter or a different color or pulsing, depending on the strength of the pressure.

The drivers behind will notice these things before they will notice the decrease in the distance. This idea could save lives.

I recently posted the following coin weighing puzzle invented by Konstantin Knop:

We have N indistinguishable coins. One of them is fake and it is not known whether it is heavier or lighter than all the genuine coins, which weigh the same. There are two balance scales that can be used in parallel. Each weighing lasts one minute. What is the largest number of coins N for which it is possible to find the fake coin in five minutes?

The author’s solution in Russian is available at his blog. Also, two of my readers, David Reynolds and devjoe, solved it correctly.

Here I want to explain the solution for any number of required weighings.

It is easy to see that for n weighings the information theoretical bound is 5ⁿ. Indeed, each weighing divides coins into five groups: four pans and the leftover pile. To distinguish between coins, there can’t be two coins in the same pile at every weighing.

Suppose we know the faking potential of every coin, that is, each coin is assigned a value: potentially light or potentially heavy. If a potentially light coin is ever determined to be fake, then it must be lighter than a real coin. The same story holds for potentially heavy coins. How many coins with known potential can we process in n weighings?

If all the coins are potentially light then we can find the fake coin out of 5ⁿ coins in n weighings. What if there is a mixture of coins? Can we expect the same answer? How much more complicated could it be? Suppose we have five coins: two of them are potentially light and three are potentially heavy. Then on the first scale we compare one potentially light coin with the other such coin. On the other scale we compare one potentially heavy coin against another potentially heavy coin. The fake coin can be determined in one weighing.

The discussion above shows that there is a hope that any mixture of coins with different potential can be resolved. After each weighing, we want the number of coins that are not determined to be real to be reduced by a factor of 5. If one of the weighings on one scale is unbalanced, the potentially light coins on the lighter pan, plus the potentially heavy coins on the heavier pan would contain the fake coin. We do not want this number to be bigger than one-fifth of the total number of coins we are processing. So we divide coins in pairs with the same potential, and from each pair we put the coins on different pans of the same scale. So in one weighing we can divide the group into five equal groups. If there is an odd number of coins with the same potential, then the extra coin doesn’t go on the scales.

The only thing that we is left to check is what happens if the number of coins is small. Namely, we need to check what happens when the number of potentially light coins is odd and the number of potentially heavy coins is odd, and the total number of coins is not more than five. In this case the algorithm requires us to put aside the extra coin in each group, but the put-aside pile can’t have more than one coin.

After checking small cases, we see that we can’t resolve the problem in one weighing when there are 2 coins of different potential, or when the 4 coins are distributed as 1 and 3.

On the other hand, if we have extra coins that are known to be real, then the above cases can be resolved. Hence, any number of coins with known potential greater than four can be resolved in ⌈log₅n⌉ weighings.

Now let’s go back to the original problem in which we do not know the coins’ potential at the start. After a weighing, if both scales balance, then all the coins on the scale are real and the fake coin is in the leftover pile and we do not know its potential. If a scale doesn’t balance then the fake coin is in one of its two pans: the lighter pan has coins that are potentially light and the heavier pan has coins that are potentially heavy.

Let’s add an additional assumption to the original problem. Suppose we have an unlimited supply of coins that we know to be real. Let u(n) be the maximum number of coins we can process in n weighings if we do not know their potential.

What would be the first weighing? Both scales might be balanced, meaning that the fake coin is in the leftover pile of coins with unknown potential. So we have to leave out not more than u(n−1) coins. On the other hand, exactly one scale might be unbalanced. In this case, all the coins on this scale will get their potential known. The number of these coins can’t be more than 5^n-1. But this is an odd number, so we can use one extra real coin to make this number even, in order to put the same number of coins in each pan on this scale.

So u(n) = 2 · 5^n-1 + u(n−1), and u(1) = 3. This gives the answer of (5ⁿ+1)/2. Now we need to go back and remember that we got this bound using an additional assumption that we have an unlimited supply of real coins. Looking closer, we do not need our additional supply of real coins to be unlimited; we just need not more than two real coins. The good news is that we will have these extra real coins after the first weighing. The bad news is that for the first weighing we do not have extra real coins at all. So in the first weighing we should put unknown coins against unknown coins, not more than 5^n-1 on each scale, and as the number on each scale must be even, the best we can do is put 5^n-1−1 coins on each scale.

Thus the answer is (5ⁿ−3)/2 for n more than 1.

We can generalize this problem to any number of scales used in parallel. Suppose the number of scales is k. Suppose the number of weighings is more than 1, then the following problems can be solved in n weighings:

• If all the coins have known potential, then the maximum number of coins that can be resolved is (2k+1)ⁿ.
• If we do not know the potential of any coin and there is an unlimited supply of real coins, the maximum number of coins that can be solved is defined by a recursion: u(n) = k (2k+1)^n-1 + u(n−1) and u(1)=k + 1. So the answer is: ((2k+1)ⁿ+1)/2.
• If we do not know the potential of any coin and there is no extra real coins, then the answer is u(n) − k = ((2k+1)ⁿ+1)/2 − k.

The methods I described can be used to answer another common question in the same setting: Find the fake coin and say whether it is heavier or lighter. Let us denote by U(n) the number of coins that can be resolved in n weighings when there is an unlimited supply of extra real coins. Then the recurrence for U(n) is the same as the recurrence for u(n): U(n) = 2·5^n-1 + U(n−1). The only difference is in the initial conditions: U(1) = k. This means that U(n) = ((2k+1)ⁿ−1)/2. If we don’t have extra real coins then the answer is: U(n) = ((2k+1)ⁿ−1)/2 − k.

When we don’t need to say whether the fake coin is heavier or lighter, we can add one extra coin to the mix: the coin that doesn’t participate in any weighing and is fake if the scales always balance.