Avery Miller

Office: E2 - 406 EITC, University of Manitoba
Email: avery.miller@umanitoba.ca
Member of the Geometric, Approximation, and Distributed Algorithms Lab

Employment
  • Assistant Professor ‐ University of Manitoba (2016 - Present)
  • Postdoctoral Scholar ‐ Tel Aviv University (Supervised by Boaz Patt-Shamir, 2015-2016)
  • Postdoctoral Scholar ‐ UniversitĂ© du QuĂ©bec en Outaouais (Supervised by Andrzej Pelc, 2014-2015)

Education
  • University of Toronto ‐ Ph.D. in Computer Science (Supervised by Faith Ellen)
  • University of Toronto ‐ M.Sc. in Computer Science (Supervised by Faith Ellen)
  • University of Waterloo ‐ B.Math. in Computer Science and Combinatorics & Optimization


If you are passionate about algorithms and mathematics, and you are looking for a supervisor for graduate studies (or undergraduate research), then send me an e-mail!


Research Interests

My research interests lie in theoretical computer science and algorithms, with a focus on mathematically proving lower bounds on the complexity of problems. I have a strong background and keen interest in graph theory and distributed algorithms.

Some projects I've been thinking about recently:

Distributed Computing in Anonymous Networks

Many algorithms for communication networks are designed under the assumption that each process has a unique identifier (ID). We investigate what is possible when processes have no ID at all. This might come up in situations where it is difficult to assign unique ID's to devices, or perhaps in situations where the processes want to remain anonymous due to privacy concerns. We consider fundamental network tasks (e.g., leader election) and characterize in which situations the task can be efficiently solved (or solved at all).

Some relevant publications:

  • Four Shades of Deterministic Leader Election in Anonymous Networks (SPAA 2021)
  • Deterministic Leader Election in Anonymous Radio Networks (SPAA 2020)
  • Time vs. Information Tradeoffs for Leader Election in Anonymous Trees (SODA 2016, ACM Transactions on Algorithms)

Distributed Computing in Radio Networks

Communication among nodes in a wireless radio network has to overcome the challenge that simultaneous transmissions by nearby nodes can lead to message loss due to signal interference. Algorithms that avoid all interference can be very costly, so our research involves designing algorithms that work efficiently despite the loss of some messages. This becomes especially challenging when we consider networks of mobile nodes. So far, our work has focused on problems such as broadcasting (one-to-all communication), gossiping (all-to-all communication), neighbour discovery, and leader election.

Some relevant publications:

  • Local Gossip and Neighbour Discovery in Mobile Ad Hoc Radio Networks (ALGOSENSORS 2018)
  • Global Synchronization and Consensus Using Beeps in a Fault-Prone Multiple Access Channel (ALGOSENSORS 2016, Theoretical Computer Science)
  • On the complexity of neighbourhood learning in radio networks (ALGOSENSORS 2013, Theoretical Computer Science)

Distributed Computing by Mobile Agents

We study situations where mobile robots must collectively accomplish a task without the help of a central coordinator. One common task is Gathering (or Rendezvous): we want all robots to meet at the same place at the same time, perhaps in order to share information or coordinate future actions. We consider environments such as networks or the 2D-plane, and we want to design good algorithms with respect to performance measures such as: minimizing time to completion, maximizing resilience to faults/failures, or minimizing how much initial information the robots need.

Some relevant publications:

  • Fast Byzantine Gathering with Visibility in Graphs (ALGOSENSORS 2020)
  • Time Versus Cost Tradeoffs for Deterministic Rendezvous in Networks (PODC 2014, Distributed Computing)

The Role of Information in Distributed Computing

Solving problems efficiently in distributed systems is often impossible, the main reason being that each device in the system doesn't have information about the system as a whole. In particular, each device only has local information: it might know its own ID (or MAC address) and maybe some information about its immediate neighbours, but doesn't know anything beyond that. Can a small amount of additional information help? One approach is to provide the same global information (e.g., the size, diameter, or maximum degree of the network) to all processes, which is often called advice. Another approach is to provide to each process a small (and possibly different) piece of information, which is often called a labeling scheme.
We have worked on determining how much information should be given in order to bring down the complexity of a problem, or to make a problem solvable. We have done this in various models (e.g., anonymous networks, radio networks, mobile agents) and with various problems (e.g., broadcasting, robot gathering, and leader election).

Some relevant publications:

  • Constant-Length Labeling Schemes for Deterministic Radio Broadcast (SPAA 2019, ACM Transactions on Parallel Computing)
  • Election vs. Selection: How Much Advice is Needed to Find the Largest Node in a Graph? (SPAA 2016)
  • Tradeoffs between Cost and Information for Rendezvous and Treasure Hunt (OPODIS 2014, Journal of Parallel and Distributed Computing)

Network Traffic Management with Limited Memory

Consider a set of routers forming a network, and each router has a memory buffer with limited size. If more packets arrive at a router than it can store in its memory, it must drop some of the packets, and they are lost forever. Packets arrive at routers in two ways: either they are forwarded by other routers in the network, or they are injected into the router directly from an external source. We consider the task of creating and analyzing algorithms that decide when and where each router should forward packets in the network, with the goal of dropping as few packets as possible.

Some relevant publications:

  • With Great Speed Come Small Buffers: Space-Bandwidth Tradeoffs for Routing (PODC 2019)
  • Buffer Size for Routing Limited-Rate Adversarial Traffic (DISC 2016)

Graph Burning

Graph burning is a model for the spread of social influence in networks. The objective is to measure how quickly a fire (e.g., a piece of fake news) can be spread in a network. The burning process takes place in discrete rounds. In each round, a new fire breaks out at a selected vertex and burns it. Meanwhile, the old fires extend to their adjacent vertices and burn them. A "burning schedule" selects where the new fire breaks out in each round, and the "burning problem" asks for a schedule that burns all vertices in a minimum number of rounds, termed the "burning number" of the graph.
We have worked on creating efficient algorithms that find optimal (or near-optimal) burning schedules, and also on proving bounds on how quickly graphs can be burned.

Some relevant publications:

  • Burning Two Worlds: Algorithms for Burning Dense and Tree-like Graphs (SOFSEM 2020)


Teaching

Automata Theory and Formal Languages

COMP 3030

An introduction to the theory of computability: how can we formally define machines, and how can we prove that certain problems are solvable or unsolvable by these machines? We consider these questions with regards to Turing Machines, but we also consider simpler automata and systems (e.g., DFA's, NFA's, PDA's, DPDA's, regular expressions, and context-free grammars).

Fall 2016 - 2021

Analysis of Algorithms

COMP 2080

First, we learn the tools and techniques for analyzing code: proving correctness and estimating running time of iterative and recursive algorithms. We learn to express running time using asymptotic notation, which allows us to quickly compare the efficiency of different algorithms. In the second half of the course, we put these techniques into action by applying them to examples of some popular algorithmic approaches: divide-and-conquer algorithms, greedy algorithms, dynamic programming algorithms, and randomized algorithms.

Winter 2019 - 2022

Lower Bounds and Impossibility

COMP 4060 and COMP 7750

No doubt you have heard the mantra "Anything is possible if you just put your mind to it!" Nope, not true, particularly when it comes to computing. This course provides a survey of various research domains (e.g., data structures, shared memory systems, networks, mobile robots, Turing machines) and focuses on the techniques and results used to formally prove that certain important problems cannot be solved efficiently (or at all!)

Winter 2018, 2019, 2021

Introduction to the Theory of Distributed Computing

COMP 4060 and COMP 7750

This course focuses on defining formal models of computation for various types of distributed systems, e.g., shared memory, message passing, radio networks, and mobile agents. In each case, we consider important tasks and learn popular algorithmic techniques used to solve these tasks. We also learn how to prove the correctness of algorithms and how to analyze their efficiency and/or fault-tolerance.

Winter 2017, 2020

Discrete Mathematics for Computer Science

COMP 2130

An introduction to some of the mathematical tools needed for future computer science courses. We start with propositional and predicate logic, and learn various proof techniques (e.g., direct, indirect, contradiction, induction). We practice these techniques via classical number theory (e.g., divisibility, GCD, Diophantine equations, modular arithmetic, RSA cryptography). We also study definitions and important results concerning sets, functions, relations, counting, and graph theory.

Winter 2018

Academic Service

Program Committees
  • OPODIS 2021
  • SPAA 2021
  • OPODIS 2018
  • I-SPAN 2017

Organizing Committees
  • PODC 2021 - Organizing Chair
  • PODC 2020 - Treasurer
  • OPODIS 2019 - Proceedings Chair
  • PODC 2019 - Workshop Chair
  • CCCG 2018 - Organizing Co-Chair
  • PODC 2016 - Communications Co-Chair
  • SSS 2015 - Technical Assistant

Reviewing
  • Conference subreviewing:
    • DISC
    • ICALP
    • ICDCS
    • LATIN
    • OPODIS
    • SIROCCO
    • SODA
    • SPAA
    • SWAT
  • Journal submission reviewer:
    • ACM Transactions on Algorithms
    • Algorithmica
    • Distributed Computing
    • Information and Computation
    • Journal of Computer and System Sciences
    • SIAM Journal on Computing
    • Theoretical Computer Science

Conference Publications

Labeling Schemes for Deterministic Radio Multi-Broadcast
(WG 2021)

Download PDF (arXiv preprint)

Colin Krisko, Avery Miller: "Labeling Schemes for Deterministic Radio Multi-Broadcast", 47th International Workshop on Graph-Theoretic Concepts in Computer Science (WG 2021), to appear.

Four Shades of Deterministic Leader Election in Anonymous Networks
(SPAA 2021)

Download PDF (arXiv preprint)

Barun Gorain, Avery Miller, Andrzej Pelc: "Four Shades of Deterministic Leader Election in Anonymous Networks", ACM Symposium on Parallelism in Algorithms and Architectures (SPAA 2021), to appear.

Fast Byzantine Gathering with Visibility in Graphs
(ALGOSENSORS 2020)

Publication Link Download PDF (arXiv preprint)

Avery Miller, Ullash Saha: "Fast Byzantine Gathering with Visibility in Graphs", International Symposium on Algorithms and Experiments for Wireless Sensor Networks (ALGOSENSORS 2020), pp. 140-153.

Deterministic Leader Election in Anonymous Radio Networks
(SPAA 2020)

Publication Link Download PDF (arXiv preprint)

Avery Miller, Andrzej Pelc, Ram Narayan Yadav: "Deterministic Leader Election in Anonymous Radio Networks", ACM Symposium on Parallelism in Algorithms and Architectures (SPAA 2020), pp. 407-417.

Burning Two Worlds: Algorithms for Burning Dense and Tree-like Graphs
(SOFSEM 2020)

Publication Link Download PDF (arXiv preprint)

Shahin Kamali, Avery Miller, Kenny Zhang: "Burning Two Worlds", SOFSEM 2020: Theory and Practice of Computer Science, pp. 113-124.

With Great Speed Come Small Buffers: Space-Bandwidth Tradeoffs for Routing
(PODC 2019)

Publication Link Download PDF (arXiv preprint)

Avery Miller, Boaz Patt-Shamir, Will Rosenbaum: "With Great Speed Come Small Buffers: Space-Bandwidth Tradeoffs for Routing", Proceedings of the 2019 ACM Symposium on Principles of Distributed Computing (PODC '19), pp. 117-126.

Constant-Length Labeling Schemes for Deterministic Radio Broadcast
(SPAA 2019 - Best Paper Award)

Publication Link Download PDF (arXiv preprint)

Faith Ellen, Barun Gorain, Avery Miller, Andrzej Pelc: "Constant-Length Labeling Schemes for Deterministic Radio Broadcast", ACM Symposium on Parallelism in Algorithms and Architectures (SPAA 2019), pp. 171-178.

Local Gossip and Neighbour Discovery in Mobile Ad Hoc Radio Networks
(ALGOSENSORS 2018)

Publication Link Download PDF

Avery Miller: "Local Gossip and Neighbour Discovery in Mobile Ad Hoc Radio Networks", Algorithms for Sensor Systems - 14th International Symposium on Algorithms and Experiments for Wireless Sensor Networks (ALGOSENSORS 2018), pp. 1-14.

Buffer Size for Routing Limited-Rate Adversarial Traffic
(DISC 2016)

Publication Link Download PDF (arXiv preprint)

Avery Miller, Boaz Patt-Shamir: "Buffer Size for Routing Limited-Rate Adversarial Traffic", International Symposium on Distributed Computing (DISC 2016), pp. 328-341.

Global Synchronization and Consensus Using Beeps in a Fault-Prone MAC
(ALGOSENSORS 2016)

Publication Link Download PDF (arXiv preprint)

Kokouvi Hounkanli, Avery Miller, Andrzej Pelc: "Global Synchronization and Consensus Using Beeps in a Fault-Prone MAC", Algorithms for Sensor Systems - 12th International Symposium on Algorithms and Experiments for Wireless Sensor Networks (ALGOSENSORS 2016), pp. 16-28

Election vs. Selection: How Much Advice is Needed to Find the Largest Node in a Graph?
(SPAA 2016)

Publication Link Download PDF (arXiv preprint)

Avery Miller, Andrzej Pelc: "Election vs. Selection: How Much Advice is Needed to Find the Largest Node in a Graph?", ACM Symposium on Parallelism in Algorithms and Architectures (SPAA 2016), pp. 377-386.

Time vs. Information Tradeoffs for Leader Election in Anonymous Trees
(SODA 2016)

Publication Link Download PDF (arXiv preprint)

Christian Glacet, Avery Miller, Andrzej Pelc: "Time vs. Information Tradeoffs for Leader Election in Anonymous Trees", ACM-SIAM Symposium on Discrete Algorithms (SODA 2016), pp. 600-609.

Tradeoffs Between Cost and Information for Rendezvous and Treasure Hunt
(OPODIS 2014)

Publication Link Download PDF (arXiv preprint)

Avery Miller, Andrzej Pelc: "Tradeoffs Between Cost and Information for Rendezvous and Treasure Hunt", Proc. 18th International Conference on Principles of Distributed Systems (OPODIS 2014), pp. 263-276.

Fast Rendezvous with Advice
(ALGOSENSORS 2014)

Publication Link Download PDF (arXiv preprint)

Avery Miller, Andrzej Pelc, "Fast Rendezvous with Advice", Proc. 10th International Symposium on Algorithms and Experiments for Sensor Systems, Wireless Networks and Distributed Robotics (ALGOSENSORS 2014), pp. 75-87.

Time Versus Cost Tradeoffs for Deterministic Rendezvous in Networks
(PODC 2014)

Publication Link Download PDF (arXiv preprint)

Avery Miller, Andrzej Pelc, "Time versus cost tradeoffs for deterministic rendezvous in networks", Proc. 33rd Annual ACM Symposium on Principles of Distributed Computing (PODC 2014), pp. 282-290.

On the Complexity of Fixed-Schedule Neighbourhood Learning in Wireless Ad Hoc Radio Networks
(ALGOSENSORS 2013)

Publication Link

Avery Miller, "On the Complexity of Fixed-Schedule Neighbourhood Learning in Wireless Ad Hoc Radio Networks", Proc. 9th International Symposium on Algorithms and Experiments for Sensor Systems, Wireless Networks and Distributed Robotics (ALGOSENSORS 2013), pp. 244-259.

Gossiping in one-dimensional synchronous ad hoc wireless radio networks
(TADDS 2012)

Publication Link

Avery Miller, "Gossiping in one-dimensional synchronous ad hoc wireless radio networks", Proc. 4th Workshop on Theoretical Aspects of Dynamic Distributed Systems (TADDS 2012), pp. 32-43.

Meeting your Neighbours
(ICALP2011GT)

Download PDF

Avery Miller, "Meeting Your Neigbours", Proc. ICALP2011GT Algorithms and Data Structures for selection, identification and encoding: proceedings of the ICALP 2011 Group Testing Workshop, pp. 1-19.

Gossiping in Jail
(ALGOSENSORS 2009)

Publication Link Download PDF

Avery Miller, "Gossiping in Jail." Proc. 5th International Workshop on Algorithmic Aspects of Wireless Sensor Networks (ALGOSENSORS 2009), LNCS 5804, pp. 242-251.


Journal Publications

Constant-Length Labeling Schemes for Deterministic Radio Broadcast
(ACM Transactions on Parallel Computing)

Faith Ellen, Barun Gorain, Avery Miller, Andrzej Pelc: "Constant-Length Labeling Schemes for Deterministic Radio Broadcast", ACM Transactions on Parallel Computing, to appear.

Global Synchronization and Consensus Using Beeps in a Fault-Prone MAC
(Theoretical Computer Science)

Publication Link

Kokouvi Hounkanli, Avery Miller, Andrzej Pelc. "Global Synchronization and Consensus Using Beeps in a Fault-Prone Multiple Access Channel", Theoretical Computer Science, Volume 806, February 2020, pp. 567-576.

Deterministic distributed construction of T-dominating sets in time T
(Discrete Applied Mathematics)

Publication Link Download PDF (arXiv preprint)

Avery Miller, Andrzej Pelc. "Deterministic distributed construction of T-dominating sets in time T", Discrete Applied Mathematics, Volume 222, 11 May 2017, Pages 172-178.

Time vs. Information Tradeoffs for Leader Election in Anonymous Trees
(ACM Transactions on Algorithms)

Publication Link

Christian Glacet, Avery Miller, and Andrzej Pelc. Time vs. Information Tradeoffs for Leader Election in Anonymous Trees. ACM Trans. Algorithms 13, 3, Article 31 (March 2017)

Time Versus Cost Tradeoffs for Deterministic Rendezvous in Networks
(Distributed Computing)

Publication Link

Avery Miller, Andrzej Pelc. "Time Versus Cost Tradeoffs for Deterministic Rendezvous in Networks", Distributed Computing 29(1): pp. 51-64 (2016).

Fast Rendezvous with Advice
(Theoretical Computer Science)

Publication Link

Avery Miller, Andrzej Pelc. "Fast rendezvous with advice", Theoretical Computer Science, Volume 608, Part 2, December 2015, pp. 190-198.

On the complexity of neighbourhood learning in radio networks
(Theoretical Computer Science)

Publication Link

Avery Miller. "On the complexity of neighbourhood learning in radio networks", Theoretical Computer Science, Volume 608, Part 2, December 2015, pp. 135-145.

Tradeoffs Between Cost and Information for Rendezvous and Treasure Hunt
(Journal of Parallel and Distributed Computing)

Publication Link

Avery Miller, Andrzej Pelc. "Tradeoffs between cost and information for rendezvous and treasure hunt", Journal of Parallel and Distributed Computing, Volume 83, September 2015, pp. 159-167.

Decimations of languages and state complexity
(Theoretical Computer Science)

Publication Link

Dalia Krieger, Avery Miller, Narad Rampersad, Bala Ravikumar, Jeffrey O. Shallit. "Decimations of languages and state complexity." Theoretical Computer Science Volume 410 (24-25) May 2009, pp. 2401-2409.