Friday, January 23, 2009

Linial-Nisan Conjecture

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.

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 ?
Here is a puzzle : Prove (or disprove) that TROYIS is NP-complete.