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. Everywhere-Sparse Spanners Via Dense Subgraphs (full version on arXiv)
  3. with Michael Dinitz and Robert Krauthgamer. To appear in IEEE Symposium on Foundations of Computer Science (FOCS) 2012.
  4. Linear Index Coding Via Semidefinite Programming (full version on arXiv)
  5. with Ishay Haviv. Appeared in ACM-SIAM Symposium on Discrete Algorithms (SODA) 2012.
  6. Inapproximability of NP-Complete Variants of Nash Equilibrium (full version on arXiv)
  7. with Per Austrin and Mark Braverman. Appeared in Workshop on Approximation Algorithms for Combinatorial Optimization Problems (APPROX) 2011. To appear in Theory of Computing.
  8. Approximating Sparsest Cut in Graphs of Bounded Treewidth (full version on arXiv)
  9. with Robert Krauthgamer and Prasad Raghavendra. Appeared in Workshop on Approximation Algorithms for Combinatorial Optimization Problems (APPROX) 2010.
  10. with Aditya Bhaskara, Moses Charikar, Uriel Feige and Aravindan Vijayaraghavan. Appeared in ACM Symposium on Theory of Computing (STOC) 2010.
  11. with Gyanit Singh. Appeared in Workshop on Approximation Algorithms for Combinatorial Optimization Problems (APPROX) 2008.
  12. Approximation Algorithms Using Hierarchies of Semidefinite Programming Relaxations
  13. (single author). Appeared in IEEE Symposium on Foundations of Computer Science (FOCS) 2007.
  14. with Konstantin Makarychev and Yury Makarychev. Appeared in IEEE Symposium on Foundations of Computer Science (FOCS) 2006.
  15. with Sanjeev Arora and Moses Charikar. Appeared in ACM Symposium on Theory of Computing (STOC) 2006.
  16. with Uriel Feige. In Theoretical Computer Science, Volume 341, Issue 1, Pages 22-38.
  17.  
Publications - Interdisciplinary
 
  1. with Pedro V. Sander, Diego Nehab and Hugues Hoppe. Appeared in SIGGRAPH Asia 2008.
  2.  
Personal
 
    Follow the link at the end of this sentence if, like me, you speak Hebrew, and you like animals.