Homepage of Siavosh Benabbas

Siavosh Benabbas

Department of Computer Science, University of Toronto

10 King's College Rd.

Toronto, Ontario M5S 3G4, Canada

Email: My first name AT cs DOT toronto DOT edu

Phone: 416-978-4236

I am a PhD candidate under supervision of Toniann Pitassi at Department of Computer Science of University of Toronto. I am interested in theoretical computer science.

Research Interests

Linear programming and Semidefinite programming relaxations, their integrality gaps and their applications to combinatorial optimization problems.
Combinatorial Optimization & Approximation algorithms
Computational complexity and Cryptography

Publications

Efficient Sum-Based Hierarchical Smoothing Under \ell_1-Norm, with Hyun Chul Lee, Joel Oren and Yuli Ye. in submission. [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

Currently I am a PhD candidate in Department of Computer Science, University of Toronto under supervision of Toniann Pitassi.
I was supervised by Avner Magen until he tragically passed away in May 2010. A memorial page has been set up here.
I got my M.Sc. from University of Toronto under supervision of Avner Magen and Charles Rackoff.
I got my B.Sc. from Sharif University of Technology under supervision of Mohammad Ghodsi in the Department of Computer Engineering.

Other stuff

As of September 2008 I am organizing the Theory Student Seminars.