Group items tagged

Neat.

"A paper posted online in January takes theoretical computer scientists halfway toward proving one of the biggest conjectures in their field. The new study, when combined with three other recent papers, offers the first tangible progress toward proving the Unique Games Conjecture since it was proposed in 2002 by Subhash Khot, a computer scientist now at New York University. Over the past decade and a half, the conjecture - which asks whether you can efficiently color networks in a certain way - has inspired discoveries in topics as diverse as the geometry of foams and the stability of election systems. And if the conjecture can be proved, its implications will reach far beyond network-coloring: It will establish what is the best algorithm for every problem in which you're trying to satisfy as many as possible of a set of constraints - the rules in a sudoku puzzle, or the seating preferences of a collection of wedding guests, for instance."