Konstantinos (Costis) Georgiou

 

Assistant Professor

Department of Combinatorics & Optimization

Faculty of Mathematics

University of Waterloo

 

200 University Avenue West

Waterloo, ON, N2L 3G1

Canada

 

Office: MC 4012

Phone: +1 (519) 888 4567 ext 37563

Fax: +1 (519) 725 5441

 

e-mail: k * (number two) * (my last name) AT math d0t uwaterloo d0t ca

 

 

Education        Publications     Teaching          C&O Reading Group  Service           Non Academic Stuff

 

Education

 

Thesis: Integrality Gaps for Strong Linear Programming and Semidefinite Programming Relaxations

Supervised by Avner Magen & Toni Pitassi.

 

Sponsored by the Departments of Mathematics, Informatics & Telecommunications, M.I.TH.E (University of Athens), the Department of Electrical and Computer Engineering (National Technical University of Athens), and by the Department of Computer Engineering and Information (University of Patras).

Thesis: Unfairness in Online Scheduling

Supervised by Elias Koutsoupias (2004)

 

 

 

Research Interests

 

Convex & Combinatorial Optimization, Approximation Algorithms, Game Theory, Hardness of Approximation

 

 

Conference Publications

 

 

·         On Integrality Ratios for Assymetric TSP in the Sherali-Adams Hierarchy

With Joseph Cheriyan, Zhihan Gao and Sahil Singla

To appear in 40th International Colloquium on Automata, Languages and Programming (ICALP 2013)

 

·         Understanding Set Cover: Sub-exponential Time Approximations and Lift-and-Project Methods

      With Eden Chlamtac and Zac Friggstad

      To appear in 17th Workshop on Algorithms and Data Structures (WADS’13)

Also in arXiv:1204.5489 (2012) [pdf]

 

·         Social Exchange Networks With Distant Bargaining

      With George Karakostas, Jochen Könemann and Zuzanna Stamirowska

      To appear in 19th Annual International Computing and Combinatorics Conference (COCOON'13)

 

·         Complexity of Barrier Coverage with Relocatable Sensors in the Plane

      With S. Dobrev, S. Durocher, M. Eftekhari, E. Kranakis, D. Krizanc, L. Narayanan, J. Opatrny, S. Shende, J. Urrutia

      To appear in 8th International Conference on Algorithms and Complexity (CIAC'13)

 

·         Better Balance by Being Biased: A 0.8776-Approximation for Max Bisection

      With Per Austrin and Siavosh Benabbas

      24th Symposium on Discrete Algorithms (SODA'13) [pdf]

      Also in arXiv:1205.0458 (2012) [pdf]

 

  • Black-Box Reductions for Cost-Sharing Mechanism Design

With Chaitanya Swamy

      23rd Symposium on Discrete Algorithms (SODA'12) [pdf]

 

  • Tight Integrality gap for Sherali-Adams SDPs for Vertex Cover

With Siavosh Benabbas, Siuon Chan and Avner Magen

31st Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2011) [pdf]

Also in Electronic Colloquium on Computational Complexity (ECCC), TR 10-169

 

  • 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]

 

  • 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]
and in Electronic Colloquium on Computational Complexity (ECCC), TR 096-061

 

  • 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]

 

  • 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]

 

  • Computability of Models for Sequence Assembly

With Paul Medvedev, Gene Myers and Michael Brudno

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

 

  • 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]
and in Electronic Colloquium on Computational Complexity (ECCC), TR 06-152

 

 

Journal Publications

 

  • SDP Gaps from Pairwise Independence

With Siavosh Benabbas, Avner Magen and Madhur Tulsiani.

Theory of Computing (2012) [pdf]

 

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

With Avner Magen, Toniann Pitassi and Iannis Tourlakis.

SICOMP (2010) [pdf]

 

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

With Evangelos Kranakis and Danny Krizanc.

Discrete Mathematics (2009) [pdf]

 

  • Distributed Dynamic Storage in Wireless Networks

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

International Journal of Distributed Sensor Networks (2005) [pdf]

 

 

Manuscripts

 

 

·         The Beachcombers' Problem: Walking and Searching with Mobile Robots

      With Jurek Czyzowicz, Leszek Gasieniec, Evangelos Kranakis and Fraser MacQuarrie

      arXiv:1304.7693 (2013) [pdf]

 

·         Efficient Algorithms for Solving Hypergraphic Steiner Tree Relaxations in Quasi-Bipartite Instances

      With Isaac Fung, Jochen Könemann and Malcolm Sharpe

      arXiv:1202.5049 (2011) [pdf]

 

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

With Avner Magen.

Technical Report CSRG-587,University of Toronto (2008) [pdf]

 

 

Theses

 

  • Integrality Gaps for Strong Linear Programming and Semidefinite Programming Relaxations

My PhD thesis, under the supervision of Avner Magen and Toni Pitassi (2010) [pdf]

 

  • Unfairness in Online Scheduling

My master thesis, under the supervision of Elias Koutsoupias (2004)

 

Teaching

 

University of Waterloo, Dept. of Combinatorics and Optimization (Instructor)

 

  • CO456 Introduction to Game Theory (Fall 2013 – upcoming)
  • MATH239 Introduction to Combinatorics (Fall 2013 – upcoming)
  • CO471-CO671 Semidefinite Optimization (Spring 2013) [graduate course]
  • ECE103 Discrete Mathematics (Spring 2013) [also coordinator]
  • CO250 Introduction to Optimization (Winter 2013)
  • CO372 Portfolio Optimization Models (Winter 2013)
  • ECE103 Discrete Mathematics (Winter 2012)

And the fun goes on. Here is why.

  • MATH115 Linear Algebra (Fall 2010)

And yes, a math course can be fun. Why? It is trivial!

 

University of Toronto, Dept. of Computer Science (Teaching Assistant)

  • CSC363 Computational Complexity and Computability (Winter 2007, Summer 2007, Fall 2008, Winter 2009, Fall 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, Summer 2010)
  • CSC236 Introduction to the Theory of Computation (Winter 2008)

 

National Technical University of Athens, School of Electrical and Computer Engineering (Teaching Assistant)

  • Algorithms and Complexity (Fall 2003, Fall 2004)
  • Introduction to Computer Programming (Fall 2004)

 

University of Athens, Dept. of Mathematics and Dept. of Informatics (Teaching Assistant, Graduate courses)

  • Algorithms and Complexity I (Fall 2002, Fall 2005)
  • Algorithms and Complexity II (Fall 2004)

 

University of Athens, Dept. of Mathematics (Teaching Assistant)

  • Computer Programming I (Fall 1999, Fall 2000)
  • Computer Programming II (Winter 2000)
  • Computer Graphics (Fall 2000, Fall 2001)

 

University of Athens, Dept. of Mathematics (Lab Assistant)

  • Computer Programming, Computer Graphics, Data Structures, Numerical Analysis (Fall 1999-Winter 2002).

 

Service

 

  • ISMP'12: 21st International Symposium on Mathematical Programming, 2012.

Organizer of a session in LP and SDP hierarchies, in the cluster of ``Combinatorial Optimization.''

  • FUN'12: 6th International Conference on Fun With Algorithms, 2012.

Member of Program Committee.

  • As of September 2010, I am organizing the C&O Reading Group. You are more than welcome to join us!
  • PLS-3: 3rd Panhellenic Logic Symposium, 2001.

Local Organizer.

 

Non Academic Stuff

 

  • Note by Note: Our contribution to the 101 Horror (student) Film Festival, Hart House, University of Toronto, 2006.

This is what we made in 101 hours out of the following (randomly chosen) ingredients.

Title: Note by Note

An item to be used: Bottle of wine.

A phrase to be used: We are going home, Candy. We are going home.

 

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