As most of you already know, Linial-Nisan Conjecture is settled by Mark Braverman. This settles a major open problem. Read the following blog posts for more details :

Braverman's paper is on his homepage.

## Friday, January 23, 2009

## Monday, January 12, 2009

### Train Probability Puzzle

The probability of observing a train in 30 minutes on a track is 665/729. What is the probability of observing a train in 5 minutes ?

Hint : Shoot for an elegant solution.

## Wednesday, January 07, 2009

### Troyis Game

I came across this game called Troyis. Being a theoretician, whenever I come across a new game, the first question that comes to my mind is "What is its complexity ?". Here is the decision version of Troyis :

- TROYIS : Given an instance of Troyis, can you paint all the white cells in <= k clicks ?

Subscribe to:
Posts (Atom)