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 :
paper is on his homepage.
Monday, January 12, 2009
Wednesday, January 07, 2009
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 ?