|
I received my PhD from Department of Computer Science, University of Toronto under supervision of Toniann Pitassi. My area of research was Theoretical Computer Science: Combinatorial Optimization, Approximation Algorithms and Complexity Theory in general and Linear programming and Semidefinite programming relaxations, their integrality gaps and their application to Combinatorial Optimization problems in particular.
An Isoperimetric Inequality for the Hamming Cube with Applications for Integrality Gaps in Degree-bounded Graphs, with Hamed Hatami and Avner Magen. in preparation.
Better Balance by Being Biased: A 0.8776-Approximation for Max Bisection, with Per Austrin and Konstantinos Georgiou. to appear in SODA 2013. [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. in Theory of Computing [final version] [bibtex]
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
to appear in Discrete Mathematics & Theoretical Computer Science. A preliminary version appeared in LATIN2010.
[draft full version] [conference version] [bibtex]