Iannis Tourlakis
Sandford Fleming Building, Room 2304d,
Phone: (416) 946-7977
Department of Computer Science
University of Toronto
My CV
Teaching
Research
I am a post-doctoral fellow in the Department of Computer Science at the
University of Toronto. My
Ph.D. adviser was
Sanjeev Arora at
Princeton University. I received
my
M.Sc. (under the supervision of Stephen Cook) and B.Sc.
from the University of Toronto.
I am interested in Theoretical Computer Science.
In particular I explore how methods from convex optimization (linear
and semidefinite programming) can be used to come up with new
approximation
algorithms for NP-hard optimization problems.
In addition, I'm
interested
in
more "traditional" computational complexity topics like time-space
tradeoff lower bounds, derandomization, and the complexity of SAT
solvers.
Publications
-
Vertex cover resists SDPs tightened by local hypermetric
constraints
Konstantinos Georgiou, Avner Magen, Iannis Tourlakis
13th Conference on Integer Programming and Combinatorial
Optimization (IPCO) 2008
[pdf]
-
Integrality gaps of 2-o(1) for vertex cover SDPs in the
Lovasz-Schrijver hierarchy
Konstantinos Georgiou, Avner Magen, Toniann Pitassi, Iannis Tourlakis
IEEE Symposium on Foundations of Computer Science (FOCS) 2007
[pdf]
-
New lower bounds for vertex cover in the Lovasz-Schrijver hierarchy
Iannis Tourlakis
21st IEEE Conference on Computational Complexity (CCC) 2006
[pdf]
-
Proving integrality gaps without knowing the linear program
Sanjeev Arora, Bela Bollobas, Laszlo Lovasz, Iannis Tourlakis
Theory of Computing, Vol. 2, p19-51, 2006
[pdf]
-
Towards optimal integrality gaps for hypergraph vertex cover in the
Lovasz-Schrijver hierarchy
Iannis Tourlakis
APPROX'2005 [ps]
-
Towards strong nonapproximability results in the Lovasz-Schrijver
hierarchy
Mikhail Alekhnovich, Sanjeev Arora, Iannis Tourlakis
ACM Symposium on the Theory of Computing (STOC) 2005 [ps]
-
Time-space tradeoffs for SAT on non-uniform machines
Iannis Tourlakis
JCSS, Vol. 63, p268-287, 2001 (Special issue on CCC2000; contains
stronger results than conference version) [pdf]
-
Time-space lower bounds for SAT on uniform and non-uniform
machines
Iannis Tourlakis
15th IEEE Conference on Computational Complexity (CCC) 2000 [ps]
Theses
-
New lower bounds for Approximation Algorithms in the
Lovasz-Schrijver Hierarchy Princeton University
2006 (Ph.D. thesis) [pdf]
-
Some Results in Non-Uniform Complexity Theory University of Toronto
2000 (M.Sc. thesis) [ps]