Siavosh Benabbas

According to our database, Siavosh Benabbas authored at least 9 papers between 2010 and 2013.

Collaborative distances:

• Dijkstra number of four.
• Erdős number of three.

2013

Better Balance by Being Biased: A 0.8776-Approximation for Max Bisection.

Per Austrin, Siavosh Benabbas, Konstantinos Georgiou

Proceedings of the Twenty-Fourth Annual ACM-SIAM Symposium on Discrete Algorithms, 2013

2012

On Hierarchies of Strong SDP Relaxations for Combinatorial Optimization Problems.

Siavosh Benabbas

PhD thesis, 2012

SDP Gaps from Pairwise Independence.

Siavosh Benabbas, Konstantinos Georgiou, Avner Magen, Madhur Tulsiani

Theory Comput., 2012

2011

Efficient Sum-Based Hierarchical Smoothing Under \ell_1-Norm

Siavosh Benabbas, Hyun Chul Lee, Joel Oren, Yuli Ye

CoRR, 2011

Tight Gaps for Vertex Cover in the Sherali-Adams SDP Hierarchy.

Siavosh Benabbas, Siu On Chan, Konstantinos Georgiou, Avner Magen

Proceedings of the IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science, 2011

Verifiable Delegation of Computation over Large Datasets.

Siavosh Benabbas, Rosario Gennaro, Yevgeniy Vahlis

Proceedings of the Advances in Cryptology - CRYPTO 2011, 2011

2010

The Sherali-Adams System Applied to Vertex Cover: Why Borsuk Graphs Fool Strong LPs and some Tight Integrality Gaps for SDPs.

Siavosh Benabbas, Konstantinos Georgiou, Avner Magen

Electron. Colloquium Comput. Complex., 2010

On Quadratic Threshold CSPs.

Per Austrin, Siavosh Benabbas, Avner Magen

Proceedings of the LATIN 2010: Theoretical Informatics, 2010

Extending SDP Integrality Gaps to Sherali-Adams with Applications to Quadratic Programming and MaxCutGain.

Siavosh Benabbas, Avner Magen

Proceedings of the Integer Programming and Combinatorial Optimization, 2010