OK, consider me dazzled. This afternoon, I got to spend a few minutes with Yuval Peres, principal researcher within Microsoft Research Redmond's Theory Group. In viewing the Theory Group's TechFest demos over the past few years, it has occurred to me that computational theory occupies a space where computer science intersects with philosophy. Maybe that's why that team always seems produce posters and animations that approach the nature of art.

Peres is an amiable, bespectacled man who speaks in the precise, clipped diction of one for whom mental meanderings would represent nothing so much as a waste of time and energy. He speaks in well-formed sentences woven into crystalline paragraphs of model clarity, This afternoon, he discussed his two TechFest 2008 demos--one entitled Algorithms and E-Commerce, the other Probability and Networks. But those mundane descriptions don't do justice to his irresistable, effortless elocutionary logic.

I warned Peres that he'd have to speak simply for me to have a chance to grasp the gist of his work, and he graciously complied. Instead of inserting my comments and interrupting the flow, I present his comments virtually verbatim. In the course of a few minutes, he managed to touch upon the techniques credit-card companies use to make money, college basketball's March Madness, and the complexity of fairness:

"The main two themes of our demonstrations this year are optimization and network formation. In optimization, we're emphasizing the difference between global optimization, when you're trying to optimize the social welfare for everyone, and local optimization, in which you have lots of individuals participating in the system and each one is maximizing their self-interest. You get very different solutions when these two mechanisms are in play, and we have some pictures that demonstrate the different solutions.

"This theme of local versus global optimization is also present in a classical problem we call the overhang problem, how far you can get a sequence of blocks to extend over a table, where the classical solution, which is obtained by recursive local optimization, is much weaker than the optimal solution you get by global optimization. We have a demonstration and even a game where people can try out the difference for themselves.

"The other thing we have is network formation, and that's very basic to a lot of what Microsoft does. It's understanding networks, from the Internet to distribution networks to social networks to telephone networks. They all have different structures. We're analyzing the basic structures of how networks form.

"If you look at a picture of a network, it often looks like a big disarray, but we now understand there are three key ingredients in the formation of a network. If you want to move away from the details and understand the basic themes, they are: underlying geometry, and that's very important in, say, a road network and less important in the Internet, though it still plays a role there. There is optimization, either by some network administrator or central authority, or optimization by individuals joining the network or taking part in the network. And the third ingredient is just randomness, or luck. These ingredients come in different doses, and they yield very different-looking networks. We have some striking examples of that in our booth.

"On the application side, besides understanding networks, we have several applications. One is monetizing social networks where, when you have a network, it's not a huge one, but it's already complicated, and it's changing very fast. The challenge is for the platform owner to monetize the network, to get the return on the investment in building the network, and to do that is more tricky than it seems at first, because if you do it the wrong way, you discourage users from joining your network. You need to understand where funding flows into the network, where it flows out of the network--and both things happen at many places--and make sure, as the platform owner, you only tax where money comes out--from people who sell stuff on the network, from developers--and not from users, not from people who bring money into the network.

"That's one basic insight that's common to many networks. A credit-card company will always put the charge to the seller and not to the buyer. They'll even sometimes reimburse the buyer. It's the same principle: You take money into the system from somebody who makes money from the system. Once you understand that principle, you still have to locate where money is going out of the system, and for complicated networks which evolve all the time, this is itself a challenge where understanding the structure of networks plays a role.

"Another application we have is a joint project with the VIBE group: fantasy-sports prediction. It's designed to help groups that participate in office pools. They make predictions on something like March Madness or other sports contests--or it can also be other competitions, even political contests, where people make predictions--and after you have their predictions in, you want to know what's the chance for each participant to win the pool.

"You could just go over all possibilities if it's a small pool, but in March Madness, with 63 games, you can't go over 2⁶³ possibilities. You have to do a Monte Carlo algorithm. There are many algorithms you could use, and the initial algorithm used took three minutes per query. After we got involved, together with the VIBE group, we have an algorithm that works in one second per query, so we had a huge improvement to make this thing practical."

Yuval Peres in front of a poster that provides a graphical depiction of the effects of global optimization. Best to let him explain it:

"This poster shows what arises from fair allocation done locally. You have a thousand points spread here, and each one is trying to obtain exactly the same area as all the rest--not more than their quota, exactly their quota. The way they do it is each one grows a [color-coded] disc around it, at unit speed, and it captures all the area it reaches first. Some points get all their area nearby, but some points that are hemmed in by others, they grow this disc, but here [he points to a place where a disc's shape is warped by the presence of a previously grown disc nearby], they don't get any area, because this area is already captured by this center. They have to wait, and they somehow resurface out here [he points to an area far from the nexus of the warped disc] and get their fill of area here. At the end of the day, they all get the same area, but some of them have to go very far.

"It's a very simple method. It doesn't require any kind of coordination by the different centers and no central authority, and it gives a fair allocation. But, as you see, the structure is very complex, and some individuals have to go very far to get their quota. What turns out is that this is the hardest to do, when you want a fair allocation. ... Our contribution is: If you consider this scheme with quotas, it yields this very complex picture. Fair allocation is great, but without central authority, it's complicated.