All reports by Author Ali Kemal Sinop:

__
TR12-111
| 5th September 2012
__

Venkatesan Guruswami, Ali Kemal Sinop#### Faster SDP hierarchy solvers for local rounding algorithms

__
TR11-066
| 25th April 2011
__

Venkatesan Guruswami, Ali Kemal Sinop#### Lasserre Hierarchy, Higher Eigenvalues, and Approximation Schemes for Quadratic Integer Programming with PSD Objectives

Revisions: 1

__
TR10-111
| 14th July 2010
__

Venkatesan Guruswami, Ali Kemal Sinop#### The complexity of finding independent sets in bounded degree (hyper)graphs of low chromatic number

__
TR09-099
| 16th October 2009
__

Venkatesan Guruswami, Ali Kemal Sinop#### Improved Inapproximability Results for Maximum k-Colorable Subgraph

Revisions: 1

Venkatesan Guruswami, Ali Kemal Sinop

Convex relaxations based on different hierarchies of

linear/semi-definite programs have been used recently to devise

approximation algorithms for various optimization problems. The

approximation guarantee of these algorithms improves with the number

of {\em rounds} $r$ in the hierarchy, though the complexity of solving

(or even writing down the solution for) ...
more >>>

Venkatesan Guruswami, Ali Kemal Sinop

We present an approximation scheme for optimizing certain Quadratic Integer Programming problems with positive semidefinite objective functions and global linear constraints. This framework includes well known graph problems such as Minimum graph bisection, Edge expansion, Uniform sparsest cut, and Small Set expansion, as well as the Unique Games problem. These ... more >>>

Venkatesan Guruswami, Ali Kemal Sinop

We prove almost tight hardness results for finding independent sets in bounded degree graphs and hypergraphs that admit a good

coloring. Our specific results include the following (where $\Delta$, assumed to be a constant, is a bound on the degree, and

$n$ is the number of vertices):

Venkatesan Guruswami, Ali Kemal Sinop

We study the maximization version of the fundamental graph coloring problem. Here the goal is to color the vertices of a $k$-colorable graph with $k$ colors so that a maximum fraction of edges are properly colored (i.e., their endpoints receive different colors). A random $k$-coloring properly colors an expected fraction ... more >>>