Assistant professor at the Department of Computer Science, Ben Gurion University.

I received my PhD from the Computer Science Department at Princeton University, where my advisor was Sanjeev Arora.

A pronunciation guide for my name.
 
E-mail: chlamtac [at] cs [dot] bgu [dot] ac [dot] il

For more information, see my CV.
Research Interests
 
    I am primarily interested in approximation algorithms which exploit convex optimization tools (e.g. linear programming, semi-definite programming). Much of my work (though by no means all) focuses on demonstrating the potential of hierarchies of convex relaxations, which until recently remained outside the algorithmic toolkit.
 
Book Chapter (preprint)
 
    Convex Relaxations and Integrality Gaps, with Madhur Tulsiani. In the Springer "Handbook on Semidefinite, Conic and Polynomial Optimization".
 
Dissertation
 
    My PhD Thesis, containing the most polished versions of some of the following results (specifically, from STOC’06, FOCS’07, APPROX’08), can be found here.
 
Publications - Theory
 
  1. •Understanding Set Cover: Sub-exponential Time Approximations and Lift-and-Project Methods
  2. with Zachary Friggstad and Konstantinos Georgiou. Submitted.
  3. •Everywhere-Sparse Spanners Via Dense Subgraphs (full version on arXiv)
  4. with Michael Dinitz and Robert Krauthgamer. To appear in IEEE Symposium on Foundations of Computer Science (FOCS) 2012.
  5. •Linear Index Coding Via Semidefinite Programming (full version on arXiv)
  6. with Ishay Haviv. Appeared in ACM-SIAM Symposium on Discrete Algorithms (SODA) 2012.
  7. •Inapproximability of NP-Complete Variants of Nash Equilibrium (full version on arXiv)
  8. with Per Austrin and Mark Braverman. Appeared in Workshop on Approximation Algorithms for Combinatorial Optimization Problems (APPROX) 2011. To appear in Theory of Computing.
  9. •Approximating Sparsest Cut in Graphs of Bounded Treewidth (full version on arXiv)
  10. with Robert Krauthgamer and Prasad Raghavendra. Appeared in Workshop on Approximation Algorithms for Combinatorial Optimization Problems (APPROX) 2010.
  11. •Detecting High Log-Densities - an O(n1/4) Approximation for Densest k-Subgraph (arXiv)
  12. with Aditya Bhaskara, Moses Charikar, Uriel Feige and Aravindan Vijayaraghavan. Appeared in ACM Symposium on Theory of Computing (STOC) 2010.
  13. •Improved Approximation Guarantees Through Higher Levels of SDP Hierarchies
  14. with Gyanit Singh. Appeared in Workshop on Approximation Algorithms for Combinatorial Optimization Problems (APPROX) 2008.
  15. •Approximation Algorithms Using Hierarchies of Semidefinite Programming Relaxations
  16. (single author). Appeared in IEEE Symposium on Foundations of Computer Science (FOCS) 2007.
  17. •How to Play Unique Games Using Embeddings
  18. with Konstantin Makarychev and Yury Makarychev. Appeared in IEEE Symposium on Foundations of Computer Science (FOCS) 2006.
  19. •New Approximation Guarantee for Chromatic Number
  20. with Sanjeev Arora and Moses Charikar. Appeared in ACM Symposium on Theory of Computing (STOC) 2006.
  21. •Improved Approximation of the Minimum Cover Time
  22. with Uriel Feige. In Theoretical Computer Science, Volume 341, Issue 1, Pages 22-38.
  23.  
Publications - Interdisciplinary
 
  1. •Efficient Traversal of Mesh Edges using Adjacency Primitives
  2. with Pedro V. Sander, Diego Nehab and Hugues Hoppe. Appeared in SIGGRAPH Asia 2008.
  3.  
Personal
 
    Follow the link at the end of this sentence if, like me, you speak Hebrew, and you like animals.