Tags » Unique Games Conjecture

On extended formulations

Several results in theoretical computer science are characterized by the conditional sentence “.. unless P NP”. As an example, a well known fact is that the… 1,290 more words

Combinatorial Optimization

A look at the Unique Games Conjecture

A central question in computer science is the famous problem of whether the decision problems whose solution can be checked in polynomial time can also be solved in polynomial time, also known as the P vs. 1,277 more words

Approximation Algorithms

What's Blue and White and Red All Over?

Election and debate special from GLL—note update

Aram Harrow is both a computer scientist and a physicist—something that makes him unique and special. Few people can explain what a probabilistic Turing Machine is and also what… 2,218 more words


Bloomington summer school recap

A couple months ago, at Indiana University, David Fisher, Nets Katz, and I  organized a summer school on Analysis and geometry in the theory of computation… 1,220 more words


Lecture 2: Spectral partitioning and near-optimal foams

In the last lecture, we reduced the problem of cheating in (the k-times repeated m-cycle game) to finding a small set of edges in whose removal eliminates all topologically non-trivial cycles.  1,228 more words


Lecture 1: Cheating with foams

This the first lecture for CSE 599S:  Analytical and geometric methods in the theory of computation.  Today we’ll consider the gap amplification problem for 2-prover games, and see how it’s intimately related to some high-dimensional isoperimetric problems about foams.  2,277 more words