Ali Kemal Sinop
Simons Institute for the Theory of Computing
121 Calvin Lab
Berkeley, CA 94720.
I am currently a research fellow at the
Simons Institute for the Theory of Computing, UC Berkeley.
Before this, I spent two years as a postdoctoral researcher at the
School of Mathematics, Institute for Advanced
Computational Intractibility, Princeton University. I
received my PhD from
Carnegie Mellon University,
Computer Science Department where I was fortunate to be
by Prof. Venkatesan
My research interests are in the area of theoretical computer
science. More specifically I am interested in:
- approximation algorithms,
- hardness of approximation,
- spectral graph theory.
Prior to coming to CMU, I worked at
Corporate Research for two years under supervision
of Dr. Leo Grady
doing research on graph based methods for image segmentation.
Last but not least, my hometown
Dere in city
I was a lecturer at
A-Star Summer Computer Science Camp, 2012
I was also a teaching assistant for the following courses during my PhD:
Recent Publications (2009-present)
The Hardness of Approximation of Euclidean k-means
Spectral Embedding of k-Cliques, Graph Partitioning and
Rounding Lasserre SDPs using column selection and
spectrum-based approximation schemes for graph partitioning and
(This is a merged and definitive version of my FOCS 2011 and
SODA 2013 papers, with a significantly revised presentation
and additional new results.)
Towards a better approximation for Sparsest Cut?
Approximating Non-Uniform Sparsest Cut via Generalized
Faster SDP Hierarchy Solvers for Local Rounding
Constant Factor Lasserre Gaps for Graph Partitioning
Optimal Column-Based Low-Rank Matrix Reconstruction.
Lasserre Hierarchy, Higher Eigenvalues, and
Approximation Schemes for Quadratic Integer
Programming with PSD Objectives.
The complexity of finding independent sets in bounded degree (hyper)graphs of low chromatic number.
Improved inapproximability results for maximum k-colorable
Theory of Computing, 9:413-435, 2013.
- Extended abstract appeared in RANDOM-APPROX 2009.
- Joint work
Combinatorial Preconditioners and Multilevel Solvers for
Problems in Computer Vision and Image Processing.
Not So Recent Publications
Fast Approximate Random Walker Segmentation Using Eigenvector
A Seeded Image Segmentation Framework Unifying Graph Cuts and
Random Walker Which Yields A New Algorithm.
Uninitialized, Globally Optimal, Graph-Based Rectilinear
Shape Segmentation - The Opposing Metrics Method.
Accurate Banded Graph Cut Segmentation of Thin Structures
Using Laplacian Pyramids.