Konstantinos (Costis) Georgiou

 

Assistant Professor

Department of Mathematics

Ryerson University

 

350 Victoria St.

Toronto, ON, M5B 2K3

Canada

 

Office: ENG 250

Phone: +1 (416) 979 5000 ext 7400

 

email: my first (long) name AT ryerson d0t ca

 

 

Adjunct Research Professor

School of Computer Science

Carleton University

 


 

Education

Publications

Teaching

Student Supervision

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, Distributed Algorithms, Game Theory

 


 

Conference Publications

 

·       Search-and-Fetch with 2 Robots on a Disk: Wireless and Face-to-Face Communication Models

With George Karakostas and Evangelos Kranakis

To appear in the 6th International Conference on Operations Research and Enterprise Systems (ICORES’17) [link]

Also in arXiv: 1611.10208 (2016) [pdf]

 

·       Search on a Line by Byzantine Robots

With Jurek Czyzowicz, Evangelos Kranakis, Danny Krizanc, Lata Narayanan, Jurek Opatrny and Sunil Shende

To appear: 27th International Symposium on Algorithms and Computation (ISAAC’16) [link]

Also in arXiv: 1611.08209 (2016) [pdf]

 

·       Search-and-Fetch with One Robot on a Disk

With George Karakostas and Evangelos Kranakis

To appear: 12th International Symposium on Algorithms and Experiments for Wireless Sensor Networks (ALGOSENSORS’16)

 

·       Searching with Advice: Robot Fence-Jumping

With Evangelos Kranakis, and Alexandra Steau

To appear: 28th Canadian Conference on Computational Geometry (CCCG’16)

Also in arXiv: 1606.08023 (2016) [pdf]

 

·       Know When to Persist: Deriving Value from a Stream Buffer

With George Karakostas, Evangelos Kranakis, and Danny Krizanc

11th International Conference on Algorithmic Aspects of Information and Management (AAIM’16)

Also in arXiv: 1604.03009 (2016) [pdf]

 

·       Distributed Patrolling with Two-Speed Robots (and an Application to Transportation)

With Jurek Czyzowicz, Evangelos Kranakis, Fraser MacQuarrie, and Dominik Pajak

5th International Conference on Operations Research and Enterprise Systems (ICORES’16) [link], [link]

 

·       Evacuating Two Robots from Multiple Unknown Exits in a Circle

With Jurek Czyzowicz, Stefan Dobrev, Evangelos Kranakis and Fraser MacQuarrie [link]

17th International Conference on Distributed Computing and Networking (ICDCN’16), Distributed Computing Track.

 

·       Evacuating Robots from a Disk Using Face-to-Face Communication

With Jurek Czyzowicz, Evangelos Kranakis, Lata Narayanan, Jarda Opatrny and Birgit Vogtenhuber

8th International Conference on Algorithms and Complexity (CIAC'15) [link]

Also in arXiv: 1501.04985 (2015) [pdf]

 

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

With Edward Lee

34th Foundations of Software Technology and Theoretical Computer Science (FSTTCS’14) [link]

Also in arXiv: 1409.6365 (2014) [pdf]

 

·       The Multi-source Beachcombers' Problem

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

      10th International Symposium on Algorithms and Experiments for Sensor Systems, Wireless Networks and Distributed Robotics (ALGOSENSORS’14) [link]

 

·       Stable Marriage with General Preferences

With Linda Farczadi and Jochen Könemann

7th International Symposium on Algorithmic Game Theory (SAGT’14) [link]

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

      21st  International Colloquium on Structural Information and Communication Complexity (SIROCCO’14) [link]

      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) [link]

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) [link]

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) [link]

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) [link]

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) [link]

 

·       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) [link]

 

·       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) [link]

      Also in arXiv:1205.0458 (2012) [pdf]

 

With Chaitanya Swamy

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

 

With Siavosh Benabbas, Siuon Chan and Avner Magen

31st Foundations of Software Technology and Theoretical Computer Science (FSTTCS’11) [link]

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

 

With Avner Magen and Iannis Tourlakis.

      29th Foundations of Software Technology and Theoretical Computer Science (FSTTCS’09) [link]

 

With Avner Magen and Madhur Tulsiani.

12th Intl. Workshop on Approximation Algorithms for Combinatorial Optimization Problems (APPROX’09) [link]
and in Electronic Colloquium on Computational Complexity (ECCC), TR 096-061

 

With Periklis Papakonstantinou.

11th International Conference on Theory and Applications of Satisfiability Testing (SAT’08) [link]

 

With Avner Magen and Iannis Tourlakis.

13th Conference on Integer Programming and Combinatorial Optimization (IPCO’08) [link]

 

With Paul Medvedev, Gene Myers and Michael Brudno

7th Workshop on Algorithms in Bioinformatics (WABI’07) [link]

 

With Avner Magen, Toniann Pitassi and Iannis Tourlakis.

48th IEEE Symposium of Foundations of Computer Science (FOCS’07) [link]
and in Electronic Colloquium on Computational Complexity (ECCC), TR 06-152

 

 

Journal Publications

 

·       Searching with Advice: Robot Fence-Jumping

With Evangelos Kranakis, and Alexandra Steau

Accepted in Journal of Information Processing (2017)

 

·       Evacuating Two Robots from Multiple Unknown Exits in a Circle

With Jurek Czyzowicz, Stefan Dobrev, Evangelos Kranakis and Fraser MacQuarrie

Accepted in Theoretical Computer Science (2016) [link]

 

·       Stable Marriage with General Preferences

With Linda Farczadi and Jochen Könemann

Theory of Computing Systems (2016) [link]

 

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

With Joseph Cheriyan, Zhihan Gao and Sahil Singla

Mathematical Programming Series A (2016) [link]

 

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

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

Theoretical Computer Science (2015) [link]

 

·       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

Theoretical Computer Science (2015) [link]

 

·       Excuse Me! or The Courteous Theatregoers' Problem

With Evangelos Kranakis, Danny Krizanc

Theoretical Computer Science (2015) [link]

 

·       Black-Box Reductions for Cost-Sharing Mechanism Design

With Chaitanya Swamy

Games and Economic Behavior (2013) [link]

 

·       Social Exchange Networks With Distant Bargaining

      With George Karakostas, Jochen Könemann and Zuzanna Stamirowska

      Theoretical Computer Science (2013) [link]

 

With Siavosh Benabbas, Avner Magen and Madhur Tulsiani.

Theory of Computing (2012) [link]

 

With Avner Magen, Toniann Pitassi and Iannis Tourlakis.

SICOMP (2010) [link]

 

With Evangelos Kranakis and Danny Krizanc.

Discrete Mathematics (2009) [link]

 

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

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

 

 

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

 

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

 

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

 


Teaching

 

Ryerson University, Dept. of Mathematics (Instructor)

Fun with math in a movie theater. Of course with engineers!

Happy mornings with Linear Algebra

The tradition reaches RU. More happy engineers.

 

 

 

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

 

The tradition goes on. Another happy class. 

It is always my pleasure.

Evidence of awesomeness.

“I’m a refrigerator” (?), and a kind message.

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

Student’s opinion of the instructor.

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

And the fun goes on. Here is why.

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

 

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

 

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

 

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

 

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

 

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

 

 

 

 


Student Supervision

 

Post-docs

·       Dr. Hoda Chuang        March-May 2017

·       Dr. Tamer Abdou       NSERC Engage Grant, 2016-2017, Ryerson U.

 

Graduate (MSc) Students

·       Preeti Sharma             Ryerson University, Dept. of Mathematics, Winter 2017 - present

·       Alexandra Steau         Carleton University, School of Computer Science, (co-supervised with E. Kranakis), 2015-2017

 

Undergraduate Students

·       Astrid Olave Herrera  Fields USRP, Summer 2017, National University of Colombia

·       Jia Zhi (Andy) Jiang   Fields USRP, Summer 2017, Oxford University

·       Ian Seong                    Fields USRP, Summer 2017, Carleton College

·       Twesh Upadhyaya      Fields USRP, Summer 2017, University of Toronto

·       Yuval Yakubov           FoS, URO, Summer 2017, Ryerson U

·       Jay Griffiths               NSERC USRA, Summer 2017, Ryerson U

·       Bhargav Parsi             MITACS Globalink, Summer 2016, Indian School of Mines

·       Rui Liu                        NSERC USRA, Summer 2015, UWaterloo

·       Edward Lee                 NSERC USRA, Summer 2014, UWaterloo

 

 


Service

 

§  Conferences

 

Program Committee.

Local Arrangements Committee

Program Committee.

Program Committee.

Program Committee.

Program Committee.

Program Committee.

Program Committee.

Program Committee.

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

Program Committee.

Local Organizer.

 

 

§  Seminars Series Organizer

 

·       G@R seminar, Jan 2017 – present

(Ryerson University)

·       C&O reading group, February 2011 – July 2015

(University of Waterloo)

·       Undergraduate Research Program, Seminar Series, Spring 2014.

(University of Waterloo)

·       Undergraduate Research Program, Seminar Series, Spring 2015.

(University of Waterloo)

 

 


Non Academic Stuff

 

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