Ali Kemal Sinop

Contact Information:

About Me (my resume as pdf)

I am currently a postdoctoral researcher in theoretical computer science at Center for Computational Intractibility, Princeton University and Institute for Advanced Study. I received my PhD from Carnegie Mellon University, Computer Science Department where I was fortunate to be advised by Prof. Venkatesan Guruswami.

My research interests are in theoretical computer science. More specifically I am interested in:

• hardness of approximation,
• approximation algorithms,
• spectral graph theory and linear algebra.

Last but not least, my hometown is Meram, Dere in city of Konya, Turkey .

Educational Background

• PhD in Computer Science, Carnegie Mellon University, 2007 - 2012.
• Thesis: Graph Partitioning and Semi-definite Programming Hierarchies.
• Advisor: Venkatesan Guruswami
• MS in Computer and Information Sciences, University of Pennsylvania, 2004 - 2005.
• BS in Computer Engineering Bilkent University in Ankara Turkey, 2000 - 2004.

Teaching

• Fall 2009, 21-301 Combinatorics, Instructor: Prof. Alan Frieze.
• Spring 2008, 15-750 Graduate Algorithms, Instructor: Prof. Gary Miller.

Recent Publications (2009-present)

• Approximating Non-Uniform Sparsest Cut via Generalized Spectra.
  • To appear in SODA 2013. arXiv, PDF.
  • Joint work with Venkatesan Guruswami.
• Faster SDP Hierarchy Solvers for Local Rounding Algorithms.
  • In FOCS 2012. arXiv, PDF.
  • Joint work with Venkatesan Guruswami.
• Constant Factor Lasserre Gaps for Graph Partitioning Problems.
  • Manuscript arXiv, PDF.
  • Joint work with Venkatesan Guruswami and Yuan Zhou.
• Optimal Column-Based Low-Rank Matrix Reconstruction.
  • In SODA 2012. arXiv, PDF.
  • SODA Presentation PPS.
  • Joint work with Venkatesan Guruswami.
• Lasserre Hierarchy, Higher Eigenvalues, and Approximation Schemes for Quadratic Integer Programming with PSD Objectives.
  • In FOCS 2011. Full version arXiv, PDF.
  • FOCS Presentation PPS.
  • Joint work with Venkatesan Guruswami.
• The complexity of finding independent sets in bounded degree (hyper)graphs of low chromatic number.
  • In SODA 2011, pdf.
  • Joint work with Venkatesan Guruswami.
• Improved inapproximability results for maximum k-colorable subgraph.
  • In APPROX 2009, arxiv, pdf.
  • Joint work with Venkatesan Guruswami.
• Combinatorial Preconditioners and Multilevel Solvers for Problems in Computer Vision and Image Processing.
  • Technical report: CMU, 2009, pdf.
  • Joint work with Ioannis Koutis, Gary L. Miller, and David Tolliver .

Not So Recent Publications

• Fast Approximate Random Walker Segmentation Using Eigenvector Precomputation.
  • In CVPR 2008, pdf.
  • Joint work with Leo Grady .
• A Seeded Image Segmentation Framework Unifying Graph Cuts and Random Walker Which Yields A New Algorithm.
  • In ICCV 2007, pdf.
  • Joint work with Leo Grady .
• Uninitialized, Globally Optimal, Graph-Based Rectilinear Shape Segmentation - The Opposing Metrics Method.
  • In ICCV 2007, pdf.
  • Joint work with Leo Grady .
• Accurate Banded Graph Cut Segmentation of Thin Structures Using Laplacian Pyramids.
  • In MICCAI 2006, pdf.
  • Joint work with Leo Grady .

Some Friends on the Web