We study the question of whether the value of mathematical programs such as
linear and semidefinite programming hierarchies on a graph $G$, is preserved
when taking a small random subgraph $G'$ of $G$. We show that the value of the
Goemans-Williamson (1995) semidefinite program (SDP) for \maxcut of $G'$ is
more >>>

Assume that Alice and Bob, given an authentic channel, have a protocol where they end up with a bit S_A and S_B, respectively, such that with probability (1+eps)/2 these bits are equal. Further assume that conditioned on the event S_A = S_B no polynomial time bounded algorithm can predict the ... more >>>