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



  • January 15, 2020: Talk by Kenny Zhang

    Kenny will be giving a talk titled "Burning Two Worlds: Algorithms for Burning Dense and Tree-like Graphs"

  • Yeganeh Bahoo, PhD

    Congratulations to Yeganeh Bahoo on her successful PhD thesis defense!

  • Nima Sheibani, M.Sc.

    Congratulations to Nima Sheibani on a successful M.Sc. thesis defense!

  • Undergraduate Research Awards

    Congratulations to Ishan Chopra, Tim Zapp, Kenny Zhang, and Joe Vermander on receiving Undergraduate Research Awards!

  • Kelly Ramsay, M.Sc.

    Congratulations to Kelly Ramsay on her successful M.Sc. thesis defense!

Faculty

Stephane Durocher

Professor
Home page

Avery Miller

Assistant Professor
Home page

Shahin Kamali

Assistant Professor
Home page

Members


Current

Arezoo Sajadpour
Colin Krisko
Dehou Zhang
Fengyi Liu
Kimia Shadkami
Masood Shabani
Pooya Nikbakht
Sameer Naib
Saulo dos Santos
Timothy Zapp
Ullash Saha
Yeakub Hassan
Yongzhen Ren
Former

Dalin Chen
Debajyoti Mondal
Derek Cormier
Francisco de la Rosa
Garrett Suss
Ishan Chopra
Ivan Chernavtcev
Janani Sundaresan
Joe Vermander
Joshua Hernandez
Kelly Ramsay
Kenny Zhang
Kyle Joseph
Lyndon Miller
Matthew Skala
Mohammad Abdul Wahid
Nima Sheibani
Robby Singh
Robert Fraser
Saeed Mehrabi
Sahar Mehrpour
Sean Egan
Tristan Ratchford
Yeganeh Bahoo

Projects

Click on a project for more information

Recent Publications (2019/2020)

Click here for all publications

Title Authors Venue Links
A simple linear-space data structure for constant-time range minimum queryStephane Durocher
Robby Singh
Theor. Comput. Sci.Publication Link
A time-space trade-off for computing the -visibility region of a point in a polygonYeganeh Bahoo
Bahareh Banyassady
Prosenjit K. Bose
Stephane Durocher
Wolfgang Mulzer
Theor. Comput. Sci.Publication Link
An Efficient Miner Strategy for Selecting Cryptocurrency TransactionsChukwuka Chukwuocha
Shahin Kamali
Saulo dos Santos
Ruppa K. Thulasiram
BlockchainPublication Link
Approximation Algorithms for Graph BurningAnthony Bonato
Shahin Kamali
TAMCPublication Link
Burning Two WorldsShahin Kamali
Avery Miller
Kenny Zhang
SOFSEMPublication Link
Burning Two Worlds: Algorithms for Burning Dense and Tree-like GraphsShahin Kamali
Avery Miller
Kenny Zhang
CoRRPublication Link
Clustering Moving Entities in Euclidean SpaceStephane Durocher
Md Yeakub Hassan
SWATPublication Link
Compact Representation of Graphs with Small Bandwidth and TreedepthShahin Kamali
DCCPublication Link
Computing the k-Crossing Visibility Region of a Point in a PolygonYeganeh Bahoo
Prosenjit Bose
Stephane Durocher
Thomas C. Shermer
IWOCAPublication Link
Constant-Length Labeling Schemes for Deterministic Radio BroadcastFaith Ellen
Barun Gorain
Avery Miller
Andrzej Pelc
SPAAPublication Link
Deterministic Leader Election in Anonymous Radio NetworksAvery Miller
Andrzej Pelc
Ram Narayan Yadav
CoRRPublication Link
Drawing HV-Restricted Planar GraphsStephane Durocher
Stefan Felsner
Saeed Mehrabi
Debajyoti Mondal
CoRRPublication Link
Drawing plane triangulations with few segmentsStephane Durocher
Debajyoti Mondal
Comput. Geom.Publication Link
Global Synchronization and Consensus Using Beeps in a Fault-Prone Multiple Access ChannelKokouvi Hounkanli
Avery Miller
Andrzej Pelc
Theor. Comput. Sci.Publication Link
Integrated rank-weighted depthStephane Durocher
Alexandre Leblanc
Kelly Ramsay
J. Multivar. Anal.Publication Link
Lossless Image Compression Using List Update AlgorithmsArezoo Abdollahi
Neil D. B. Bruce
Shahin Kamali
Rezaul Karim
SPIREPublication Link
Online Bin Covering with AdviceJoan Boyar
Lene M. Favrholdt
Shahin Kamali
Kim S. Larsen
WADSPublication Link
Online Bin Covering with AdviceJoan Boyar
Lene M. Favrholdt
Shahin Kamali
Kim S. Larsen
CoRRPublication Link
Online Computation with Untrusted AdviceSpyros Angelopoulos
Christoph Dürr
Shendan Jin
Shahin Kamali
Marc P. Renault
CoRRPublication Link
Online Computation with Untrusted AdviceSpyros Angelopoulos
Christoph Dürr
Shendan Jin
Shahin Kamali
Marc P. Renault
ITCSPublication Link
Polygon simplification by minimizing convex cornersYeganeh Bahoo
Stephane Durocher
J. Mark Keil
Saeed Mehrabi
Sahar Mehrpour
Debajyoti Mondal
Theor. Comput. Sci.Publication Link
Randomized Two-Valued Bounded Delay Online Buffer ManagementChristoph Dürr
Shahin Kamali
CoRRPublication Link
Watchtower for k-crossing VisibilityYeganeh Bahoo
Prosenjit Bose
Stephane Durocher
CCCGPublication Link
With Great Speed Come Small Buffers: Space-Bandwidth Tradeoffs for RoutingAvery Miller
Boaz Patt-Shamir
Will Rosenbaum
CoRRPublication Link
With Great Speed Come Small Buffers: Space-Bandwidth Tradeoffs for RoutingAvery Miller
Boaz Patt-Shamir
Will Rosenbaum
PODCPublication 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)