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 6316

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              URprogram-s14          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

 

·         Lift & Project Systems Performing on the Partial Vertex Cover Polytope

With Edward Lee

To appear in the 34th Foundations of Software Technology and Theoretical Computer Science (FSTTCS’14)

Also in arXiv: 1409.6365 (2014) [pdf]

 

·         The Multi-source Beachcombers' Problem

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

      To appear in the 10th International Symposium on Algorithms and Experiments for Sensor Systems, Wireless Networks and Distributed Robotics (ALGOSENSORS’14)

 

·         Stable Marriage with General Capacities

With Linda Farczadi and Jochen Könemann

To appear in the 7th International Symposium on Algorithmic Game Theory (SAGT’14)

Also in arXiv:1407.1853 (2014) [pdf]

 

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

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

      To appear in the 21st  International Colloquium on Structural Information and Communication Complexity (SIROCCO’14)

      Also in arXiv:1304.7693 (2013) [pdf]

 

·         Excuse Me! or The Courteous Theatregoers' Problem

With Evangelos Kranakis, Danny Krizanc

7th International Conference on Fun With Aalgorithms (FUN’14)

Also in arXiv:1403.1988 (2014) [pdf]

 

·         Network Bargaining with General Capacities

With Linda Farczadi and Jochen Könemann

21st European Symposium on Algorithms (ESA’13)

Also in arXiv:1306.4302 (2013) [pdf]

 

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

With Joseph Cheriyan, Zhihan Gao and Sahil Singla

40th International Colloquium on Automata, Languages and Programming (ICALP’13) [pdf]

Also in arXiv:1405.0945 (2014) [pdf]

 

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

      With Eden Chlamtac and Zac Friggstad

      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

      19th Annual International Computing and Combinatorics Conference (COCOON'13) [pdf]

 

·         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

      8th International Conference on Algorithms and Complexity (CIAC'13) [pdf]

 

·         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

 

·         Black-Box Reductions for Cost-Sharing Mechanism Design

With Chaitanya Swamy

Games and Economic Behavior (2013) [pdf]

 

·         Social Exchange Networks With Distant Bargaining

      With George Karakostas, Jochen Könemann and Zuzanna Stamirowska

      Theoretical Computer Science (2013) [pdf]

 

  • 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

 

·         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)

 

  • CO250 Introduction to Optimization (Fall 2014)
  • CO250 Introduction to Optimization (Winter 2014)
  • CO372 Portfolio Optimization Models (Winter 2014)

The instructor, as seen by winter14 students (either co250 or co372) – thanks for the pic!

  • CO456 Introduction to Game Theory (Fall 2013)
  • MATH239 Introduction to Combinatorics (Fall 2013)
  • CO471-CO671 Semidefinite Optimization (Spring 2013) [graduate course]
  • ECE103 Discrete Mathematics (Spring 2013) [also coordinator]

How does a fun class look like? Of course like this.

  • 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

 

  • FCT’15: 20th International Symposium on Fundamentals of Computation Theory, 2015.

Member of Program Committee.

  • CSoNet'14: 3rd Workshop on Computational Social Networks, 2014.

Member of Program Committee.

  • APPROX’14: 17th International Workshop on Approximation Algorithms for Combinatorial Optimization Problems, 2014.

Member of Program Committee.

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