Tanya Khovanova's Math Blog

I wrote a story a while ago about how a clerk at my previous job mistyped my resignation date, substituting January 2007 for my real date, January 2008. As a result, my medical insurance provider decided that I wasn’t covered in 2007, and requested that my doctor return the money he had already received.

After several phone calls my medical insurance was reinstated, but I kept receiving bills from my doctor. When I called my insurance, they assured me that everything was fine and that they had paid my doctor. However, my doctor continued to send me bills.

After half a year of phone calls back and forth, someone finally explained to me what was going on. My insurance company had initially requested the money back. The money was never returned to them, because my doctor’s office would not pay them a penny until I had paid the doctor first. In my doctor’s database, my visits were marked as unpaid.

When the problem was cleared up, the insurance company stopped requesting that the doctor pay them back. But the computer at my doctor’s office didn’t understand that stop-the-request command. It didn’t know what stopping the request meant.

The computers were talking different languages and I was caught in the middle.

My son, Alexey Radul, made his PhD thesis available to the public.

I was amazed at how much he had invested in the thesis. I assumed that the main goal for a dissertation in computer science is to write a ground-breaking code and that the accompanying text is just a formality. However, this is not the case with my son’s thesis. I am not fully qualified to appreciate the “ground-breakness” of his code, but his thesis text is just wonderful.

Alexey decided that he wanted to make his thesis accessible to a wide audience. He had to make a lot of choices and decisions while he was designing and coding his prototype, and in his thesis he devoted a lot of effort to explaining this process. He also tried to entertain: I certainly had fun trying to solve an evil sudoku puzzle on page 87, that turned out not to have a unique solution.

In addition to everything else, Alexey is an amazing writer.

I am a proud mother and as such I am biased. So I’ll let his thesis speak for itself. Below is the table of contents accompanied by some quotes:

1. Time for a Revolution
   

   “Revolution is at hand. The revolution everyone talks about is, of course, the parallel hardware revolution; less noticed but maybe more important, a paradigm shift is also brewing in the structure of programming languages. Perhaps spurred by changes in hardware architecture, we are reaching away from the old, strictly time-bound expression-evaluation paradigm that has carried us so far, and looking for new means of expressiveness not constrained by over-rigid notions of computational time.”

   1. Expression Evaluation has been Wonderful
   2. But we Want More
   3. We Want More Freedom from Time
   4. Propagation Promises Liberty
      

      “Fortunately, there is a common theme in all these efforts to escape temporal tyranny. The commonality is to organize computation as a network of interconnected machines of some kind, each of which is free to run when it pleases, propagating information around the network as proves possible. The consequence of this freedom is that the structure of the aggregate does not impose an order of time. Instead the implementation, be it a constraint solver, or a logic programming system, or a functional reactive system, or what have you is free to attend to each conceptual machine as it pleases, and allow the order of operations to be determined by the needs of the solution of the problem at hand, rather then the structure of the problem’s description.”

2. Design Principles
   1. Propagators are Asynchronous, Autonomous, and Stateless
   2. We Simulate the Network until Quiescence
   3. Cells Accumulate Information
3. Core Implementation
   1. Numbers are Easy to Propagate
   2. Propagation can Go in Any Direction
   3. We can Propagate Intervals Too
   4. Generic Operations let us Propagate Anything!
4. Dependencies
   

   “Every human harbors mutually inconsistent beliefs: an intelligent person may be committed to the scientific method, and yet have a strong attachment to some superstitious or ritual practices. A person may have a strong belief in the sanctity of all human life, yet also believe that capital punishment is sometimes justified. If we were really logicians this kind of inconsistency would be fatal, because were we to simultaneously believe both propositions P and NOT P then we would have to believe all propositions! Somehow we manage to keep inconsistent beliefs from inhibiting all useful thought. Our personal belief systems appear to be locally consistent, in that there are no contradictions apparent. If we observe inconsistencies we do not crash—we chuckle!”

   1. Dependencies Track Provenance
   2. Dependencies Support Alternate Worldviews
   3. Dependencies Explain Contradictions
   4. Dependencies Improve Search
5. Expressive Power
   1. Dependency Directed Backtracking Just Works
   2. Probabilistic Programming Tantalizes
   3. Constraint Satisfaction Comes Naturally
      

      “This is power. By generalizing propagation to deal with arbitrary partial information structures, we are able to use it with structures that encode the state of the search as well as the usual domain information. We are consequently able to invert the flow of control between search and propagation: instead of the search being on top and calling the propagation when it needs it, the propagation is on top, and bits of search happen as contradictions are discovered. Even better, the structures that track the search are independent modules that just compose with the structures that track the domain information.”

   4. Logic Programming Remains Mysterious
   5. Functional Reactive Programming Embeds Nicely
   6. Rule-based Systems Have a Special Topology
   7. Type Inference Looks Like Propagation Too
6. Towards a Programming Language
   1. Conditionals Just Work
   2. There are Many Possible Means of Abstraction
   3. What Partial Information to Keep about Compound Data?
   4. Scheduling can be Smarter
   5. Propagation Needs Better Garbage Collection
   6. Side Effects Always Cause Trouble
   7. Input is not Trivial Either
   8. What do we Need for Self-Reliance?
7. Philosophical Insights
   

   “A shift such as from evaluation to propagation is transformative. You have followed me, gentle reader, through 137 pages of discussions, examples, implementations, technicalities, consequences and open problems attendant upon that transformation; sit back now and reflect with me, amid figurative pipe smoke, upon the deepest problems of computation, and the new way they can be seen after one’s eyes have been transformed.”

   1. On Concurrency
      

      “The “concurrency problem” is a bogeyman of the field of computer science that has reached the point of being used to frighten children. The problem is usually stated equivalently to “How do we make computer languages that effectively describe concurrent systems?”, where “effectively” is taken to mean “without tripping over our own coattails”. This problem statement contains a hidden assumption. Indeed, the concurrency itself is not difficult in the least—the problem comes from trying to maintain the illusion that the events of a concurrent system occur in a particular chronological order.”

   2. Time and Space
      

      “Time is nature’s way of keeping everything from happening at once; space is nature’s way of keeping everything from happening in the same place ( with apologies to Woody Allen, Albert Einstein, and John Archibald Wheeler, to whom variations of this quote are variously attributed).”

   3. On Side Effects
8. Appendix A: Details
   

   “I’m meticulous. I like to dot every i and cross every t. The main text had glossed over a number of details in the interest of space and clarity, so those dots and cross-bars are collected here.”

You have been warned. You are allowed to read this if you are 17 or over. Otherwise, you can ask your parents to read this to you. Here is a famous old condom puzzle in the version I heard when I was a teenager myself:

A man hires three prostitutes and wants to have sex with all three of them. They all might have different sexually transmitted diseases and they all want to use condoms. Unluckily, they have only two condoms. Plus, they are in the forest and can’t buy new condoms. Can the man have sex with all three of the women without danger to any of the four?

Everyone in this problem is so health-conscious, that it might not be such a dirty problem after all. I leave you with the fun challenge of figuring this problem out.

Another fun variation of this problem is when you have two men and two women and two condoms. Every woman wants to have sex with every man. How can they do that?

If you are a teacher and want to use these great puzzles for younger students, you can follow the example of MathWorld and pretend that it’s a glove problem between doctors and patients.

Recently my younger son and his MIT friends invented another variation of this problem:

Suppose three gay men all want to have sex with each other and every pair among them wants to do two penetrative sexual acts, switching roles. They want to avoid contaminating each other, and in addition, each man also does not want to cross-contaminate himself from either region to the other. How can they do that using exactly three condoms?

Let me remind you that they plan to perform six sexual acts altogether, meaning that six condoms would be enough. On the other hand, each of them needs two condom surfaces, so they can’t do it with less than three condoms. My son showed to me his solution, but I will postpone its publication.

Of course, you can say that this is a glove problem about three surgeons operating on each other.

In addition, you can generalize it to any number of gay men. Here is my solution for four men and four condoms, where letters denote people, numbers denote condoms, and the order of people represents roles: A12D, B32D, C2D, A14C, B34C, D4C, A1B, B3A, C21B, D41B, C23A, D43A.

Can you solve the problem for five or more people?

I used to receive emails requesting link exchanges with other websites. They promised to increase my page rank by creating additional hyperlinks to my pages. I ignored them. If they thought my website was good, why did they need my reciprocity to link to me? Besides, their websites didn’t have anything to do with mathematics; they were the sites of dental services or Honda dealers.

I have resisted the temptation so far. The links that I have on my websites are to sites that I recommend. Sometimes I wonder through other people blogrolls and add good links to my blog.

At other times a blog roll exchange happens: I have Google Analytics installed on my sites. From time to time I examine my traffic. When I see a new traffic flow from a particular website, I check that site out. If I like it, I add it to my blogroll.

I wouldn’t mind people writing to inform me that they have a link to my website and asking me if I’d like to reciprocate. But this doesn’t happen. Instead, strangers write to me offering to put up a link to my website on the condition that I put a link to them. I do not like this imposition.

Recently I received a request for a blog review exchange. I went to that blog and found that all of its postings were reviews of other people’s blogs, presumably those who had agreed on this kind of exchange. I checked out several of those other blogs and I didn’t find any of them very interesting.

I missed this opportunity to receive that blog review, but on the other hand, if I start linking to random crap, I might lose the respect of my readers.

My previous paragraph reminded me of a Russian joke:

I wonder how a person whose website comes up first in a Google search for “random crap” feels.

Russians assume that such a person will be embarrassed. They do not understand Americans who welcome negative publicity, and purposefully would name their website randomcraponline.com.

I enjoyed a recent discussion on the sequences fans mailing list. David Wilson suggested an idea for hiding email addresses on webpages from bots: change your email slightly and explain how to change it back.

For example, if you want to contact me, you should reverse my login name in the following email address:

hkaynat@yahoo.com

Or, remove all the digits from the following email address:

1ta2nya3kh4@yahoo.com