Tanya Khovanova's Math Blog

My son Alexey Radul defended his PhD thesis on Propagation Networks on August 4. Here is the abstract.

I propose a shift in the foundations of computation. Modern programming systems are not expressive enough. The traditional image of a single computer that has global effects on a large memory is too restrictive. The propagation paradigm replaces this with computing by networks of local, independent, stateless machines interconnected with stateful storage cells. It offers great flexibility and expressive power, and has therefore been much studied, but has not yet been tamed for general-purpose computation. The novel insight that should finally permit computing with general-purpose propagation is that a cell should not be seen as storing a value, but as accumulating information about a value.

Various forms of the general idea of propagation have been used with great success for various special purposes; perhaps the most immediate example is constraint propagation in constraint satisfaction systems. This success is evidence both that traditional linear computation is not expressive enough, and that propagation is more expressive. These special-purpose systems, however, are all complex and all different, and neither compose well, nor interoperate well, nor generalize well. A foundational layer is missing.

I present the design of a general-purpose propagation system. I illustrate on several examples how the resulting prototype supports arbitrary computation; recovers the expressivity benefits that have been derived from special-purpose propagation systems in a single general-purpose framework, allowing them to compose and interoperate; and offers further expressive power beyond what we have known in the past.

Langton’s ant travels on the infinite square grid, colored black and white. At each time step the ant moves one cell forward. The ant’s direction changes according to the color of the cell he moves onto. The ant turns 90 degrees left if the cell is white, and 90 degrees right if the cell is black. After that, the cell he is on changes its color to the opposite color.

There is a symmetry of time and space for this ant. If at any point of the ant’s travel, someone interferes and reverses the ant’s direction in between the cells, the ant and the grid will traverse the steps and stages back to the starting point.

Let’s give this ant a life. I mean, let’s place him inside the Game of Life invented by John H. Conway. In addition to the Langton’s ant’s rules, I want the cells to change colors according to the rules of the Game of Life.

Let me remind you of the rules of Conway’s Game of Life. We call black cells live cells and white cells dead cells. Black is life and white is death. The cell has eight neighbors — horizontal, vertical, diagonal. At each time step:

• A cell dies of agoraphobia, if it has more than three neighbors.
• A cell dies of boredom, if it has less than two neighbors.
• A dead cell can be born again, if it has exactly three neighbors.
• Otherwise, the cell’s status doesn’t change.

So, our ant will be traveling in this dying and reproducing population and correcting nature’s mistakes. He revives dead cells and kills live cells.

There is an ambiguity in this ant’s life description. The life can happen at two different moments. In the first ant’s world, the ant jumps from one cell to the next, and while he is in the air, the cells have time to copulate, give birth and die. Upon landing, the ant changes direction and uses his magic wand to change the life status of its landing cell. In the second ant’s world, the ant moves to the destination cell, changes its own direction and the status of the cell and then takes a smoke. All the fun, sex and death happen while he is enjoying his cigarette.

The ant’s life has symmetry in a way that is similar to the symmetry of the ant without life. If we reverse the ant’s direction back and also switch his life-style from the first to the second or vice versa, then the ant and the grid will go backwards in their states.

The parameters for the Langton’s ant were chosen to make the ant’s behavior interesting. The parameters of the Game of Life were chosen to make the Game of Life’s behavior interesting. To make the ant’s life fascinating, we might want to modify the ant’s behavior or the Life’s rules. The synergy of the ant and the Life might be intriguing only if the ant changes its behavior and the Life changes its rules.

Let’s experiment and discover how we need to change the rules in order to make the ant’s life interesting.

John H. Conway is teaching me his doomsday algorithm to calculate the day of the week for any day. The first lesson was devoted to 2009. “The 2009’s Doomsday is Saturday” is a magic phrase I need to remember.

The doomsday of a particular year is the day of the week on which the last day of February falls. February 28 of 2009 is Saturday, thus 2009’s doomsday is Saturday. For leap years it is the day of the week of February 29. We can combine the rules for leap years and non-leap years into one common rule: that the doomsday of a particular year is the day of the week of March 0.

If you know the day of the week of one of the days in 2009, you can theoretically calculate the day of the week of any other day that year. To save yourself time, you can learn by heart all the days of the year that fall on doomsday. That is actually what Conway does, and that is why he is so fast with calculations. The beauty of the algorithm is that the days of the doomsday are almost the same each year. They are the same for all months other than January and February; and in January and February you need to make a small adjustment for a leap year. That gives me hope that after I learn how to calculate days in 2009 I can easily move to any year.

To get us going we do not need to remember all the doomsday days in 2009. It is enough to remember one day for each month. We already know one for February, which works for March too. As there are 28 days in February, January 31 happens on a doomsday. Or January 32 for leap years.

Now we need to choose days for other months that are on doomsday and at the same time are easy to remember. Here is a nice set: 4/4, 6/6, 8/8. 10/10. For even months the days that are the same as the month will work. The reason it works so nicely is that two consecutive months starting with an even-numbered month, excluding February and December, have the sum of days equaling 61. Hence, those two months plus two days are 63, which is divisible by 7.

Remembering one of the doomsdays for every other month might be enough to significantly simplify calculations. But if you want a day for every month, there are additional doomsday days to remember on odd numbered months: 5/9, 9/5, 7/11 and 11/7. These days can be memorized as a mnemonic “9-5 job at 7-11,” or, if you prefer, “I do not want to have a 9-5 job at 7-11.”

If you throw in March 7, then the rule will fit into a poem John recited to me:

The last of Feb., or of Jan. will do
(Except that in leap years it’s Jan. 32).
Then for even months use the month’s own day,
And for odd ones add 4, or take it away*.

*According to length or simply remember,
you only subtract for September or November.

Let’s see how I calculate the day of the week for my friend’s birthday, July 29. The 11th of July falls on the doomsday, hence July 25 must be a doomsday. So we can see that my friend will celebrate on Wednesday this year.

You might ask why I described this trivial example in such detail. The reason is that you might be tempted to subtract 11 from 29, getting 18 and saying that you need to add four days to Saturday. In the method I described the calculation is equivalent, but as a bonus you calculate another day for the doomsday and consequently, you are getting closer to John Conway who remembers all doomsdays.

My homework is the same as your homework: practice calculating the days of the week for 2009.

More than a year ago, when I had my employment benefits with BAE Systems, I called my benefits center with a general question. The customer service representative refused to answer until I gave her my password. I didn’t have a password, so she told me that they would mail my new password to me.

But I needed an answer, so I tried the website, only to be informed that my new password is in the mail and I should wait for its arrival.

In a week, a letter with a password arrived and I called the benefits center again. I happily told them my new password and opened my mouth to ask my question. However, they didn’t accept my password. Obviously, they had changed my password twice, first when I called and then again when I tried their website. Since only ten minutes passed between these two events, both passwords should have arrived on the same day. But that didn’t happen. So my valid password was still in the mail.

In the second it took me to recover from this news, the customer representative told me that they would be sending me a new password and hung up before I could tell her not to.

A new password arrived the next day. I knew that they had already reset that password, and that I’d have to wait a week for the third password to arrive.

I was tempted to call them again and try to create an infinite password resetting loop, but I actually needed to ask my question. So I threw away my freshly arrived, but no-longer-valid password and waited for a week for the next one.

I was lucky to figure it out so quickly, for otherwise my problem could have spiraled out forever. As a professional specifications writer, here are my suggestions to all benefits centers that have that kind of software on what they should do:

• Don’t send an extra password if a password was sent not long ago, for example, in the last two days.
• If two passwords are mailed to a client in the same week, make both of them valid.
• Use email rather than mail.
• Don’t request passwords for general questions.

I had to wait two weeks to ask a simple question. Now I am writing and complaining about it in the hopes that someone who can fix the problem will read this. Maybe it would have been more productive to write a program that clicks on the “I forgot my password” button every second. This would have daily generated thousands of letters with new passwords to me. Maybe then this problem would have drawn attention sooner.

I ran an experiment. I copied multiple choices from the 2007 AMC 8 into a file and asked my son Sergei to try to guess the answers, looking only at the choices. I allowed him to keep several choices. The score I assigned depended on the number of leftover choices. If the leftover choices didn’t contain the right answer, the score for the problem was zero. Otherwise, it was scaled according to the number of choices he left. For example, if he had four choices left and the right answer was among them he got 1/4 of a point. Here are the choices:

1. 9, 10, 11, 12, 13.
2. 2/5, 1/2, 5/4, 5/3, 5/2.
3. 2, 5, 7, 10, 12.
4. 12, 15, 18, 30, 36.
5. 24, 25, 26, 27, 28.
6. 7, 17, 34, 41, 80.
7. 25, 26, 29, 33, 36.
8. 3, 4.5, 6, 9, 18.
9. 1, 2, 3, 4, cannot be determined.
10. 13, 20, 24, 28, 30.
11. Choose picture: I, II, III, IV, cannot be determined.
12. 1:1, 6:5, 3:2, 2:1, 3:1.
13. 503, 1006, 1504, 1507, 1510.
14. 5, 8, 13, 14, 18.
15. a+c < b, ab < c, a+b < c, ac < b, b/c = a.
16. Choose picture: 1, 2, 3, 4, 5.
17. 25, 35, 40, 45, 50.
18. 2, 5, 6, 8, 10.
19. 2, 64, 79, 96, 131.
20. 48, 50, 53, 54, 60.
21. 2/7, 3/8, 1/2, 4/7, 5/8.
22. 2, 4.5, 5, 6.2, 7.
23. 4, 6, 8, 10, 12.
24. 1/4, 1/3, 1/2, 2/3, 3/4.
25. 17/36, 35/72, 1/2, 37/72, 19/36.

It is clear that if you keep all choices, your score will be 5, which is the expected score for AMC if you are randomly guessing the answers. Sergei’s total score was 7.77, which is noticeably better than the expected 5.

There were two questions where Sergei felt that he knew the answer exactly. First was question number two with choices: 2/5, 1/2, 5/4, 5/3, 5/2. All but one of the choices has a 5 in it, so 1/2 must be wrong. Numbers 2/5 and 5/2 are inverses of each other, so if organizers expect you to make a mistake by inverting the right answer, then one of these choices must be the right answer. But 5/4 and 5/3 are better suited as a miscalculation of 5/2, than of 2/5. His choice was 5/2, and it was correct. The second question for which he was sure of the answer was question 19, with his answer 79. I still do not have a clue why.

Sergei’s result wasn’t too much better than just guessing. That means that AMC 8 organizers do a reasonably good job of hiding the real answer. You can try it at home and see if you can improve on Sergei’s result. I will publish the right answers as a comment to this essay in a week or so.

David Bernstein gave me this puzzle. He says that the puzzle was given at a Moscow math Olympiad a long time ago. At that time there were no computer science olympiads yet. I do not know why this puzzle feels to me like computer science. Maybe because the trivial solution is of order N, the easy solution is of order square root of N and the requested solution is of order logarithm of N:

Can you cut a square into N convex pieces minimizing the number of possible intersections of any straight line with your pieces?

It is easy to maximize the number of intersections. If you cut your square with N-1 parallel cuts into N equal thin rectangles, then there exists a line with N intersections.

It is easy to cut a square to guarantee no more than 2√N intersections. Can you cut your square so that any line makes no more than 2log₂N intersections?

For his Master’s thesis, my son Alexey Radul wrote the Symmetriad — a computer program to compute and display highly symmetric objects.

The objects the Symmetriad is after are the 4D generalizations of Platonic and Archimedean solids. His thesis contains a picture gallery made with the Symmetriad, and these are my three favorite pictures.

The pictures have cute titles. The problem is that I still haven’t installed the WordPress plugin that allows me to put captions under the pictures. That is why you have to guess which title matches which picture. The titles are: “The Planets are Aligned,” “Great Jaws,” and “Diamonds are Forever.”

If you are wondering why one of the pictures shows a non-connected object, in fact the object is connected, but some of the edges are white, so that you can better see 3D cells of the object.

Subsequent to the publication of this thesis, Alexey enhanced his software to make even more dramatic pictures. The following pictures have no titles, so feel free to suggest some:

I think it would be nice to publish a book with all these pictures. As a book on symmetries should be published on a symmetric date, the next opportunity would be 01.02.2010.

Start is the STate of the ART question-answering system. You can ask Start any question in plain English — for example, “What is the population of Moscow?” — and instead of producing millions of pages like Google, it provides one exact answer: “The population of Moscow, Russia, is 8,746,700.” I am not sure where this number comes from, as Russian sites suggest that the population of Moscow is more than 10 million people. But anyway, back to my challenge.

I have my email address in plain sight on my webpage. As a result, I get a lot of spam. So, I am thinking about a way to present my address so that humans can easily deduce it, but computers can’t. Here it is: my email server is Yahoo and my user name consists of 7 lower case letters. Each letter answers one of the questions below, in the right order. As of today, Start can’t answer any of these questions.

1. What is the first letter of the word 3?
2. What is the first letter of the alphabet?
3. What is the only common letter in the words “knowledge” and “triamphant”?
4. What is the last letter of all the days of the week?
5. What is the first letter of almost all the continents?
6. What is the first letter of the word “knight”?
7. What is the most frequent letter in the word “although”?

The advantage of presenting my user name in this manner is that I will restrict my new correspondence to people who are sufficiently eager to write to me that they can spare ten seconds figuring out my email address. The main advantage is that Start can’t answer these questions, giving me hope that spamming software can’t do it either.

I do think that the state of the art question-answering system should know the first letter of the alphabet. Start: these questions are a challenge for you. How much time will it take you to do it?

Watch out. Maybe Google can do it faster.

Recently I published my ideas for a Flexible Zipcar Algorithm that allows customers to rent Zipcars one-way. I had a dream the night after I published it: the Zipcar research lab invited me to give a presentation about my algorithm and they asked me a lot of questions. I would like to answer these questions now, but first let me give you a short description of the algorithm:

Some locations are flexible. The number of cars assigned at a flexible location is not fixed, but rather a range between the minimum and the maximum. A Zipster would be allowed to use a car one-way from one flexible location to another, as long the number of assigned cars doesn’t move outside the range.

Question. Zipsters expect to pick up the exact vehicle they reserved. With vehicles changing locations you will break this system. I am operating on the assumption that Zipsters will continue to pick up the exact vehicle they reserved.

Question. What about people who get attached to the cars at their location? You can divide your pool of cars at a flexible location into two groups: fixed Zipcars and floating Zipcars. Only floating cars will be allowed to move. You should advise Zipsters who get attached to their cars to choose fixed cars as the object of their affection. This solution is less flexible, but it resolves your problem.

Question. You designed your algorithm using the min and max number of cars at a flexible location. Where is the desirable number of cars coming from? We need the desirable number of cars to calculate the financial incentives. For example, you can take the absolute value of the difference between the current number of cars at a flexible location and the desirable number of cars. Then sum it up over all locations. We can call this total the distance between the current state and the optimal state. If a one-way trip increases this distance, that Zipster pays extra and vice versa. You can also add a surcharge for all one-way trips to cover the extra expense for parking spaces.

Question. What if cars get stuck? For example, what if we always have the maximum number of cars at Harvard Square and the minimum number of cars at Coolidge Corner? You can always offer free rides from Harvard Square to Coolidge Corner. If every Zipster knows that you have a discount program which is easy to find, your cars will be in the right place in no time. For example, you can color code overstaffed and understaffed locations on your map; or you can add RSS feeds for people who are interested when cheap rides from Harvard Square to Coolidge Corner are available.

Question. Are you saying that instead of hiring drivers to move our cars around we find a much cheaper Zipster who needs to go in the same direction? Yes. If you go even further and offer a token payment or some Zipcar credits, you can have Zipsters driving your cars to oil changes and car washes for you.

Question. Why do you always talk about a small number of flexible locations? I would limit the number of flexible locations for your initial stage, so that for a small investment you get something new, you can experiment, you can observe and study trends in how cars are migrating, you can tune your financial incentives system and you can design and test your web support for this algorithm.

Question. What if someone reserves a car for a one-way trip one month in advance? What happens with the car during this month? If your car – let’s name it “Comfy” — is reserved from the Harvard Square location for a month from now, you need to lock this car into the Harvard Square location for a month. That means, no one can take Comfy for a one-way trip during this month. This looks like a bad case of inflexibility. To resolve it you can have a time-limit for one-way reservations. For example, you might limit one-way reservations to not more than three days in advance.

Question. Suppose we have four cars at the Harvard Square location and the desirable number is three. Then four people reserve four different cars at this location for round-trips on Labor Day. Are these four cars stuck at Harvard Square for a month until Labor Day? I can offer one solution using the earlier idea of fixed and floating cars. You can allow very advanced reservations for fixed cars, but floating cars can only be reserved three days in advance. Another possible solution is that you do the same without dividing your cars into fixed and floating. For example, you allow people to have very advanced reservations for any car which is currently assigned to the Harvard Square location. As soon as three cars are reserved for more than three days in advance, the fourth car is no longer available for very advanced reservations. The fourth car temporarily starts behaving like a floating car, without that being its permanent designation.

Question. Suppose today is Monday and Jack reserves Comfy one-way from Harvard Square to Coolidge Corner for Thursday. To which location is Comfy assigned for three days between Monday and Thursday? On one hand it should be assigned to Harvard Square as it takes a parking space there and we can’t allow another car to take up that space. Also, Comfy is available for reservations before Thursday at Harvard Square. At the same time, Comfy can’t be counted as an extra car anymore as we know that it is guaranteed to be moved. That means that even though Harvard Square actually houses an extra car for these three days, it shouldn’t be flagged as a location with extra cars that need to be reassigned. On the other hand, Comfy will take a spot at Coolidge Corner soon, so we can’t allow other cars to move into that spot. Even though Coolidge Corner doesn’t yet have the complete set of cars, we can’t allow other cars to take up Comfy’s future spot.

Question. It sounds complicated. Can we make it simpler? You can simplify this design for the first implementation. For example, you can only allow immediate one-way reservations. That eliminates any problem with conflicting reservations or an extra car holding up a space for three days. Also, keep in mind that the user doesn’t need to see all this complicated stuff. They are only interested in knowing whether or not they can reserve a car.

Question. What if someone reserves the car one-way then cancels the reservation? This only becomes a problem if someone else reserves the same car for a later time at the destination. In this case, you might institute a very big fee for cancellations of one-way reservations, so that you can either hire a driver or offer a super deal to other Zipsters. Of course, if you allow only immediate reservations for one-way cars this problem will be minimized.

Question. Suppose Jack reserves Comfy for two hours; his starting point is Harvard Square and his end point is Coolidge Corner. Where is Comfy assigned during these two hours? This is a great question. For round-trip Zipcars, you do not care if a person starts a half-hour late or returns the car one hour early. With a one-way car, you need to know when Comfy’s parking space will be available to other cars. To allow Jack to pick up his car as late as he wants or return it as early as he wants, the simplest solution is to assign Comfy for two hours to both locations. That is, no other car is allowed to move into Comfy’s parking spot at Harvard Square until the end of Jack’s rental period and the spot for Comfy should be ready at Coolidge Corner from the start of Jack’s rental period.

Question. You were talking about the simplest solution. Do you mean you have other solutions? I have many ideas, but I prefer to get some feedback from the car-sharing research community before continuing.

Hey, Zipcar! Let’s do it!

I am now a proud owner of a Zipcard. My old car died a horrible, screaming death recently and I decided to try to go carless as an experiment, hoping to save some money or to lose weight.

Zipcar is the modern way to rent a car. You reserve a car by the hour or by the day through the web, arrive at the site, swipe your card and drive away.

My biggest problem with being a Zipster is that the closest Zipcar location to my home is about one mile away. On second thought, I am losing weight.

But for other Zipsters, the biggest problem is that you have to return the car at the exact location where you picked it up. Obviously, if you allow renters to return their car to a different location the Zipcar company might run out of paid parking spaces in a particular location or, even worse, the cars might migrate to certain places, leaving other locations without any car.

I would like to propose an algorithm that will add some flexibility to where you can return a car, without overwhelming the system.

Here’s how it would work. Suppose we have three cars currently assigned to the Mt Auburn/Homer Ave location. I suggest we name three as a desirable number, but actually allow from three to four cars to be assigned to this location at any particular time.

Now suppose I want to pick up a car at the Mt Auburn/Homer Ave location and to return it to the Somerville Ave/Beacon location. If the number of currently assigned cars to Mt Auburn/Homer Ave location is three (at the lower limit), the Zipcar reservation webpage tells me, “Sorry, you can’t use this location unless you return your car back here,” and shows me the closest location with extra cars. The same goes if the number of assigned cars at the Somerville Ave/Beacon location is at its upper limit. If my starting point has more cars assigned to it than its lowest limit and my destination point has fewer cars assigned to it than its upper limit, then I am allowed to take a car from my starting location and return it to my destination. Zipcar can throw in some financial incentives. If my choice disrupts the most desirable balance of car assignments, I have to pay a fee. If my choice restores the balance, I get a bonus discount.

It would be so cool if zipcars were flexible. I understand that the average cost to the company of parking each car might go up with my flexible algorithm as Zipcar will need more parking spaces than cars. But Zipcar can start implementing this flexibility with a small number of flexible locations. It would be a great feature.

Hey, Zipcar algorithm designers! Can I get a bonus if you implement my algorithm? I can also design a financial incentives formula for you.