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



  • December 7, 2017: Talk by Yeganeh Bahoo

    Yeganeh will be presenting "Connecting Points in the Presence of Obstacles in the Plane"

  • November 22, 2017: Talk by Dr. Shahin Kamali

    Shahin will be presenting "Online Bin Packing"

  • November 8, 2017: Talk by Dr. Stephane Durocher

    Steph will be presenting "Bounding the Locality of Distributed Routing Algorithms"

  • October 25, 2017: Talk by Nima Sheibani

    Nima will be presenting a report on papers from GD 2017: the 25th Annual Symposium on Graph Drawing & Network Visualization

  • October 11, 2017: Talk by Ivan Chernatcev

    Ivan will be speaking about his research project as an undergraduate research assistant during the summer of 2017.

Faculty

Stephane Durocher

Associate Professor
Home page

Avery Miller

Assistant Professor
Home page

Shahin Kamali

Assistant Professor
Home page

Members


Current

Garrett Suss
Ivan Chernatcev
Kelly Ramsay
Nima Sheibani
Timothy Zapp
Yeganeh Bahoo
Former

Debajyoti Mondal
Derek Cormier
Joshua Hernandez
Kyle Joseph
Lyndon Miller
Matthew Skala
Mohammad Abdul Wahid
Robby Singh
Robert Fraser
Saeed Mehrabi
Sahar Mehrpour
Tristan Ratchford

Projects

Click on a project for more information

Recent Publications (2016/2017)

Click here for all publications

Title Authors Venue Links
Buffer Size for Routing Limited-Rate Adversarial TrafficAvery Miller
Boaz Patt-Shamir
CoRRPublication Link
Buffer Size for Routing Limited-Rate Adversarial TrafficAvery Miller
Boaz Patt-Shamir
DISCPublication Link
Compact Navigation Oracles for Graphs with Bounded Clique-WidthShahin Kamali
DCCPublication Link
Computing conforming partitions of orthogonal polygons with minimum stabbing numberStephane Durocher
Saeed Mehrabi
Theor. Comput. Sci.Publication Link
Constant-Length Labeling Schemes for Deterministic Radio BroadcastFaith Ellen
Barun Gorain
Avery Miller
Andrzej Pelc
CoRRPublication Link
Deterministic Distributed Construction of $T$-Dominating Sets in Time $T$Avery Miller
Andrzej Pelc
CoRRPublication Link
Deterministic distributed construction of T-dominating sets in time TAvery Miller
Andrzej Pelc
Discrete Applied MathematicsPublication Link
Drawing Planar Graphs with Reduced HeightStephane Durocher
Debajyoti Mondal
J. Graph Algorithms Appl.Publication Link
Efficient broadcast trees for weighted verticesHovhannes A. Harutyunyan
Shahin Kamali
Discrete Applied MathematicsPublication Link
Election vs. Selection: How Much Advice is Needed to Find the Largest Node in a Graph?Avery Miller
Andrzej Pelc
SPAAPublication Link
Exploring Increasing-Chord Paths and TreesYeganeh Bahoo
Stephane Durocher
Sahar Mehrpour
Debajyoti Mondal
CoRRPublication Link
Global Synchronization and Consensus Using Beeps in a Fault-Prone MACKokouvi Hounkanli
Avery Miller
Andrzej Pelc
ALGOSENSORSPublication Link
Guarding monotone art galleries with sliding cameras in linear timeMark de Berg
Stephane Durocher
Saeed Mehrabi
J. Discrete AlgorithmsPublication Link
Guarding orthogonal art galleries with sliding camerasStephane Durocher
Omrit Filtser
Robert Fraser
Saeed Mehrabi
Ali D. Mehrabi
Comput. Geom.Publication Link
Linear-Space Data Structures for Range Frequency Queries on Arrays and TreesStephane Durocher
Rahul Shah
Matthew Skala
Sharma V. Thankachan
AlgorithmicaPublication Link
On the Advice Complexity of the k-server Problem Under Sparse MetricsSushmita Gupta
Shahin Kamali
Alejandro López-Ortiz
Theory Comput. Syst.Publication Link
On the Biplanar Crossing Number of KStephane Durocher
Ellen Gethner
Debajyoti Mondal
CCCGPublication Link
On the list update problem with adviceJoan Boyar
Shahin Kamali
Kim S. Larsen
Alejandro López-Ortiz
Inf. Comput.Publication Link
Online Bin Packing with AdviceJoan Boyar
Shahin Kamali
Kim S. Larsen
Alejandro López-Ortiz
AlgorithmicaPublication Link
Online List UpdateShahin Kamali
Encyclopedia of AlgorithmsPublication Link
Polygon Simplification by Minimizing Convex CornersYeganeh Bahoo
Stephane Durocher
J. Mark Keil
Saeed Mehrabi
Sahar Mehrpour
Debajyoti Mondal
COCOONPublication Link
Relating Graph Thickness to Planar Layers and Bend ComplexityStephane Durocher
Debajyoti Mondal
ICALPPublication Link
Relating Graph Thickness to Planar Layers and Bend ComplexityStephane Durocher
Debajyoti Mondal
CoRRPublication Link
Robust Multi-tenant Server Consolidation in the Cloud for Data Analytics WorkloadsKhuzaima Daudjee
Shahin Kamali
Joseph Mate
ICDCSPublication Link
Routing in Geometric NetworksStephane Durocher
Leszek Gasieniec
Prudence W. H. Wong
Encyclopedia of AlgorithmsPublication Link
Thickness and colorability of geometric graphsStephane Durocher
Ellen Gethner
Debajyoti Mondal
Comput. Geom.Publication Link
Time versus cost tradeoffs for deterministic rendezvous in networksAvery Miller
Andrzej Pelc
Distributed ComputingPublication Link
Time vs. Information Tradeoffs for Leader Election in Anonymous TreesChristian Glacet
Avery Miller
Andrzej Pelc
ACM Trans. AlgorithmsPublication Link
Time vs. Information Tradeoffs for Leader Election in Anonymous TreesChristian Glacet
Avery Miller
Andrzej Pelc
SODAPublication Link
Time-Space Trade-Off for Finding the -Visibility Region of a Point in a PolygonYeganeh Bahoo
Bahareh Banyassady
Prosenjit Bose
Stephane Durocher
Wolfgang Mulzer
WALCOMPublication Link
Time-Space Trade-off for Finding the k-Visibility Region of a Point in a PolygonYeganeh Bahoo
Bahareh Banyassady
Prosenjit Bose
Stephane Durocher
Wolfgang Mulzer
CoRRPublication 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. If you are interested in applying for admission, 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)