2 papers
cs.DS2011
Rounding Semidefinite Programming Hierarchies via Global Correlation
Boaz Barak, Prasad Raghavendra, David Steurer
We show a new way to round vector solutions of semidefinite programming (SDP) hierarchies into integral solutions, based on a connection between these hierarchies and the spectrum…
math.CO2006
A Simple Explicit Construction of an $n^{\Tilde{O}(\log n)}$-Ramsey Graph
Boaz Barak
We show a simple explicit construction of an $2^{\Tilde{O}(\sqrt{\log n})}$ Ramsey graph. That is, we provide a $\poly(n)$-time algorithm to output the adjacency matrix of an undir…