Geometric, Approximation & Distributed Algorithms
A Computer Science Theory Lab at the University of Manitoba

About

 
Welcome to the GADA lab at the University of Manitoba! We study algorithms and the complexity of problems from a wide variety of research domains, such as computational geometry, approximation algorithms, online algorithms, and distributed algorithms. The common theme to all of our activities is the rich interplay between interesting problems from Computer Science and the techniques and rigour of Mathematics. Our weekly meetings alternate between problem-solving sessions and research talks, and anyone can join us! Explore this page to find out more.

Recent News



  • Paper accepted!

    "2-Coloring Point Guards in a k-Guarded Polygon" was accepted to EuroCG 2024. Congratulations to lab members Stephane Durocher, Myroslav Kryven, Fengy Liu, Amirhossein Mashghdoust and Ikaro Penha Costa

  • Paper accepted!

    "Cops and Robbers on 1-Planar Graphs" was accepted to GD 2023. Congratulations to lab members Stephane Durocher, Shahin Kamali, Myroslav Kryven, Fengyi Liu, Amirhossein Mashghdoust, Avery Miller, Pouria Zamani Nezhad, Ikaro Penha Costa and Timothy Zapp

  • Tim Zapp

    Congratulations to Tim Zapp on successfully defending their M.Sc. thesis!

  • MohammadMasoud Shabanijou

    Congratulations to MohammadMasoud Shabanijou on successfully defending his M.Sc. thesis!

  • Dehou Zhang

    Congratulations to Dehou Zhang on successfully defending his M.Sc. thesis!

Faculty

Stephane Durocher

Professor
Home page

Ben Li

Associate Professor
Home page

Avery Miller

Associate Professor
Home page

Leqi (Jimmy) Zhu

Assistant Professor (Starting July 2024)
Home page

Members


Current

Alex Kitt
Amirhossein Mashghdoust
Fengyi Liu
Hritik Punj
Ikaro Penha Costa
Jacob Janzen
Jamilush Talukder
Myroslav Kryven
Sahar Lamey
Saulo dos Santos
Former

Akshay Sharma
Anthony d'Angelo
Arezoo Sajadpour
Benjamin Schneider
Bikramjit Dhaliwal
Colin Krisko
Dalin Chen
Debajyoti Mondal
Dehou Zhang
Derek Cormier
Francisco de la Rosa
Garrett Suss
Ishan Chopra
Ivan Chernavtcev
Janani Sundaresan
Joe Vermander
Joshua Hernandez
Kelly Ramsay
Kenny Zhang
Kimia Shadkami
Kyle Joseph
Lyndon Miller
Matthew Skala
Mohammad Abdul Wahid
Mohammadmasoud Shabanijou
Nima Sheibani
Pooya Nikbakht
Pouria ZamaniNezhad
Robby Singh
Robert Fraser
Sachini Rajapakse
Saeed Mehrabi
Sahar Mehrpour
Sameer Naib
Sean Egan
Spencer Szabados
Timothy Zapp
Tristan Ratchford
Ullash Saha
Yeakub Hassan
Yeganeh Bahoo
Yongzhen Ren

Projects

Click on a project for more information

Recent Publications (2023/2024)

Click here for all publications

Title Authors Venue Links
Approximating the Smallest k-Enclosing Geodesic Disc in a Simple PolygonProsenjit Bose
Anthony D'Angelo
Stephane Durocher
CoRRPublication Link
Approximating the Smallest k-Enclosing Geodesic Disc in a Simple PolygonProsenjit Bose
Anthony D'Angelo
Stephane Durocher
WADSPublication Link
Bottleneck Convex Subsets: Finding k Large Convex Sets in a Point SetStephane Durocher
J. Mark Keil
Saeed Mehrabi
Debajyoti Mondal
Int. J. Comput. Geom. Appl.Publication Link
Byzantine Agreement with Optimal Resilience via Statistical Fraud DetectionShang-En Huang
Seth Pettie
Leqi Zhu
SODAPublication Link
Cops and Robbers on 1-Planar GraphsIkaro Penha Costa
Stephane Durocher
Shahin Kamali
Myroslav Kryven
Fengyi Liu
Amirhossein Mashghdoust
Avery Miller
Pouria Zamani Nezhad
Timothy Zapp
CoRRPublication Link
Cops and Robbers on 1-Planar GraphsIkaro Penha Costa
Stephane Durocher
Shahin Kamali
Myroslav Kryven
Fengyi Liu
Amirhossein Mashghdoust
Avery Miller
Pouria Zamani Nezhad
Timothy Zapp
GD (2)Publication Link
Curve Stabbing Depth: Data Depth for Plane CurvesStephane Durocher
Alexandre Leblanc
Spencer Szabados
CoRRPublication Link
Efficiency and optimization of government service resource allocation in a cloud computing environmentYa-guang Guo
Yixiong Wang
Jun Xu
Qian Yin
Leqi Zhu
J. Cloud Comput.Publication Link
Fast Deterministic Rendezvous in Labeled LinesAvery Miller
Andrzej Pelc
DISCPublication Link
Fast Deterministic Rendezvous in Labeled LinesAvery Miller
Andrzej Pelc
CoRRPublication Link
Four shades of deterministic leader election in anonymous networksBarun Gorain
Avery Miller
Andrzej Pelc
Distributed Comput.Publication Link
Minimum Ply Covering of Points with Unit SquaresStephane Durocher
J. Mark Keil
Debajyoti Mondal
WALCOMPublication Link
On the Restricted k-Steiner Tree ProblemProsenjit Bose
Anthony D'Angelo
Stephane Durocher
CoRRPublication Link
Reconfiguration of Multisets with Applications to Bin PackingJeffrey Kam
Shahin Kamali
Avery Miller
Naomi Nishimura
WALCOMPublication Link
Why Extension-Based Proofs FailDan Alistarh
James Aspnes
Faith Ellen
Rati Gelashvili
Leqi Zhu
SIAM J. Comput.Publication Link

Join The Lab

 

If you are currently a student or faculty member at the University of Manitoba, send an e-mail to one of our lab's faculty members to find out how to join our mailing list and attend our lab meetings.

We have funding available to provide financial support for highly motivated and qualified graduate students interested in pursuing a M.Sc. or Ph.D. degree. We also welcome visitors that wish to participate in our lab's research projects. If you are interested in the above opportunities, send an e-mail to one of our lab's faculty members, and include the following:

  • Confirmation that you have read this web page
  • A brief description of topics or specific research problems in theoretical computer science that interest you (these could be, but need not be restricted to, topics related to our lab's current research)
  • An overview of any research experience you have (e.g., a research internship, a course project related to your research interests, your undergraduate thesis, or graduate courses taken)
  • Your curriculum vitae, including degrees obtained and their corresponding institutions, and a list of any academic awards, scholarships, or bursaries received
  • Your grade point average and, if available, an electronic (or scanned) copy of your transcripts
  • A list of senior courses you took in theoretical computer science and mathematics
  • A list of your publications (if any)
  • Contact information for at least two references (email and telephone)