My webpage has moved here.





Konstantinos (Costis) Georgiou

Konstantinos Georgiou

I am a Ph.D. candidate at the

of Computer Science
of Toronto

Sandford Fleming Building

10 King's College Road, Room 3302
Toronto, Ontario M5S 3G4


Office: SF 4302c

Phone: +1 (416) 946 3924








  • Currently, I am a Ph.D. student under the supervision of Avner Magen  at the Department of Computer Science of the University of Toronto. I belong to the theory group.


  • M.Sc. from the Graduate Program in Logic, Algorithms and Computation (M.P.L.A) , sponsored by the Departments of Mathematics, Informatics & Telecommunications and M.I.TH.E. (Methodology, History and Theory of Science), of the University of Athens, by the General Sciences Department and the Department of Electrical and Computer Engineering of the National Technical University of Athens and by the Department of Computer Engineering and Information of the University of Patras.


  • B.Sc from the Department of Mathematics of the University of Athens.



Research Interests


Complexity, Convex Optimization, Metric Embeddings.



Publications and Manuscripts


  • On the Tightening of the Standard SDP for Vertex Cover with l1 Inequalities

With Avner Magen and Iannis Tourlakis.

      29th Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2009), [pdf] [bib]


  • Optimal Sherali-Adams Gaps from Pairwise Independence

With Avner Magen and Madhur Tulsiani.

12th Intl. Workshop on Approximation Algorithms for Combinatorial Optimization Problems (APPROX 2009), [pdf] [bib]
and in Electronical Cololoquium on Computational Complexity (ECCC), TR 096-061


  • Random Maximal Independent Sets and the Unfriendly Theater Seating Arrangement Problem

With Evangelos Kranakis and Danny Krizanc.

Discrete Mathematics, [pdf] [bib]


  • Expansion Fools the Sherali-Adams System: Compromising Local and Global Arguments

With Avner Magen.

Technical Report CSRG-587,University of Toronto, November 2008, [pdf] [bib]


  • Complexity and Algorithms for Well Structured k-SAT Instances

With Periklis Papakonstantinou.

11th International Conference on Theory and Applications of Satisfiability Testing (SAT 2008), [pdf] [bib]


  • Vertex Cover Resists SDPs Tightened by Local Hypermetric Inequalities

With Avner Magen and Iannis Tourlakis.

13th  Conference on Integer Programming and Combinatorial Optimization (IPCO 2008), [pdf] [bib]


  • Computability and Equivalence of Models for Sequence Assembly

With Paul Medvedev, Gene Myers and Michael Brudno

7th  Workshop on Algorithms in Bioinformatics (WABI 2007), [pdf] [bib]


  • Integrality Gaps of 2-o(1) for Vertex Cover SDPs in the Lovasz-Schrijver Hierarchy

With Avner Magen, Toniann Pitassi and Iannis Tourlakis.

48th IEEE Symposium of Foundations of Computer Science (FOCS 2007), [pdf] [bib]
and in Electronical Cololoquium on Computational Complexity (ECCC), TR 06-152


  • Distributed Dynamic Storage in Wireless Networks

With Evangelos Kranakis, Ricardo Marcelin-Jimenez, Sergio Rajsbaum, Jorge Urrutia.

International Journal of Distributed Sensor Networks, [pdf] [bib]


  • Unfairness in Online Scheduling

My master thesis, under the supervision of Elias Koutsoupias, 2004 (in greek) [pdf] [bib]





This far I have been a teaching assistant for the following courses:

  • CSC363 Computational Complexity and Computability (Winter 2007, Summer 2007, Fall 2008, Winter 2009, Winter 2010)
  • CSC373 Algorithm Design and Analysis (Fall 2005, Winter 2006, Summer 2006, Summer 2009)
  • CSC165 Mathematical Expression and Reasoning for Computer Science (Fall 2006, Winter 2010)
  • CSC236 Introduction to the Theory of Computation (Winter 2008)



Courses at UofT


  • CSC2221 Introduction to Distributed Computing
  • CSC2416 Machine Learning Theory
  • CSC214 Metric Embeddings
  • CSC2307 Numerical Software
  • CSC2401 Computational Complexity
  • CSC2410 Introduction to Graph Theory
  • CSC2125 Topics in Software Engineering
  • CSC2426 Topics in Cryptography
  • CSC2428 Theory of Computation: PCP & Hardness


Non Academic Stuff


  • I am a proud supporter of Teleios Kiklos, the coolest bookstore in downtown Athens.