|
Better Balance by Being Biased: A 0.8776-Approximation for Max Bisection, with Per Austrin and Konstantinos Georgiou. in preparation [draft] [bibtex]
Efficient Sum-Based Hierarchical Smoothing Under \ell_1-Norm, with Hyun Chul Lee, Joel Oren and Yuli Ye. in preparation. [draft] [bibtex]
Tight Integrality gap for Sherali-Adams SDPs for Vertex Cover, with Siu On Chan, Konstantinos Georgiou and Avner Magen. in FSTTCS 2011. [conference version] [draft full version] [bibtex]
SDP Gaps from Pairwise Independence, with Konstantinos Georgiou, Avner Magen and Madhur Tulsiani. to appear in Theory of Computing [draft]
Verifiable Delegation of Computation over Large Datasets, with Rosario Gennaro and Yevgeniy Vahlis. in CRYPTO 2011. [draft full version] [publisher's site] [bibtex]
Extending SDP Integrality Gaps to Sherali-Adams with
Applications to Quadratic Programming and
MaxCutGain, with Avner Magen
in IPCO2010.
[publisher's site] [bibtex]
On Quadratic Threshold CSPs, with Per Austrin and Avner Magen
in LATIN2010. [publisher's site] [bibtex]
Education
Teaching
Other stuff