Assistant professor at the Department of Computer Science at Ben Gurion University. I received my PhD from the Computer Science Department at Princeton University, where my advisor was Sanjeev Arora. People often find my name confusing or difficult to pronounce. Click here to hear it pronounced by a native speaker. Contact me by e-mail at: chlamtac [at] cs [dot] bgu [dot] ac [dot] il |  |
Research Interests
Professional Activities
One of my key interests lies in approximation algorithms which exploit convex optimization tools (e.g. linear programming, semi-definite programming). Within this framework, much of my work focuses on understanding the algorithmic potential of hierarchies of convex relaxations. I am also quite interested in the log-density method, a technique we pioneered in 2010, which uses average-case intuition in order to achieve worst-case approximation guarantees.
Book Chapter
Book Chapter
Convex Relaxations and Integrality Gaps, with Madhur Tulsiani. Appeared in the Springer "Handbook on Semidefinite, Conic and Polynomial Optimization".
Publications - Theory
- Approximating the Norms of Graph Spanners
with Michael Dinitz and Thomas Robinson. In Workshop on Approximation Algorithms for Combinatorial Optimization Problems (APPROX) 2019. - The Norms of Graph Spanners (arXiv)
with Michael Dinitz and Thomas Robinson. In International Colloquium on Automata, Languages and Programming (ICALP) 2019. - Sherali-Adams Integrality Gaps Matching the Log-Density Threshold (arXiv)
with Pasin Manurangsi. In Workshop on Approximation Algorithms for Combinatorial Optimization Problems (APPROX) 2018. - Minimizing the Union: Tight Approximations for Small Set Bipartite Vertex Expansion (arXiv)
with Michael Dinitz and Yury Makarychev. In Symposium on Discrete Algorithms (SODA) 2017. - Approximation Algorithms for Label Cover and The Log-Density Threshold
with Pasin Manurangsi, Dana Moshkovitz, and Aravindan Vijayaraghavan. In Symposium on Discrete Algorithms (SODA) 2017. - Approximating Spanners and Directed Steiner Forest: Upper and Lower Bounds (arXiv)
with Michael Dinitz, Guy Kortsarz, and Bundit Laekhanukit. In Symposium on Discrete Algorithms (SODA) 2017. - The Densest k-Subhypergraph Problem (arXiv)
with Michael Dinitz, Christian Konrad, Guy Kortsarz, and George Rabanca.
In Workshop on Approximation Algorithms for Combinatorial Optimization Problems (APPROX) 2016. - Lowest Degree k-Spanner: Approximation and Hardness
with Michael Dinitz.
Conference version: In Workshop on Approximation Algorithms for Combinatorial Optimization Problems (APPROX) 2014.
Journal version: In Theory of Computing, Volume 12, 2016. Special Issue devoted to RANDOM-APPROX 2014. - Lift-and-Project Methods for Set Cover and Knapsack
with Zachary Friggstad and Konstantinos Georgiou. In Symposium on Algorithms and Data Structures (WADS) 2013. - Everywhere-Sparse Spanners via Dense Subgraphs (arXiv)
with Michael Dinitz and Robert Krauthgamer. In Symposium on Foundations of Computer Science (FOCS) 2012. - Linear Index Coding Via Semidefinite Programming (arXiv)
with Ishay Haviv.
Conference Version: In Symposium on Discrete Algorithms (SODA) 2012.
Journal Version: In Combinatorics, Probability and Computing. 23(2): 223--247, 2014. - Inapproximability of NP-Complete Variants of Nash Equilibrium (arXiv)
with Per Austrin and Mark Braverman.
Conference Version: In Workshop on Approximation Algorithms for Combinatorial Optimization Problems (APPROX) 2011.
Journal Version: Theory of Computing 9:117-142, 2013. - Approximating Sparsest Cut in Graphs of Bounded Treewidth (arXiv)
with Robert Krauthgamer and Prasad Raghavendra. In Workshop on Approximation Algorithms for Combinatorial Optimization Problems (APPROX) 2010. - Detecting High Log-Densities - an O(n1/4) Approximation for Densest k-Subgraph (arXiv)
with Aditya Bhaskara, Moses Charikar, Uriel Feige, and Aravindan Vijayaraghavan. In Symposium on Theory of Computing (STOC) 2010. - Improved Approximation Guarantees Through Higher Levels of SDP Hierarchies
with Gyanit Singh. In Workshop on Approximation Algorithms for Combinatorial Optimization Problems (APPROX) 2008. - Approximation Algorithms Using Hierarchies of Semidefinite Programming Relaxations
(single author) In Symposium on Foundations of Computer Science (FOCS) 2007. - How to Play Unique Games Using Embeddings
with Konstantin Makarychev and Yury Makarychev. In Symposium on Foundations of Computer Science (FOCS) 2006. - New Approximation Guarantee for Chromatic Number
with Sanjeev Arora and Moses Charikar. In Symposium on Theory of Computing (STOC) 2006. - Improved Approximation of the Minimum Cover Time
with Uriel Feige. In Theoretical Computer Science, 341(1):22-38, 2005.
Publications - Interdisciplinary
- Efficient Traversal of Mesh Edges using Adjacency Primitives
with Pedro V. Sander, Diego Nehab, and Hugues Hoppe (principal investigators). In ACM SIGGRAPH Asia 2008
Dissertation
My PhD thesis, containing the most polished versions of some of the above results (specifically from STOC'06, FOCS'07, and APPROX'08).
- Program committee member: APPROX 2013, APPROX 2014, and SODA 2016.