M. Stoeckl

Research

Interests: Streaming algorithms, communication complexity, randomized algorithms, derandomization, computational complexity, privacy, lower bounds.

Papers

Conference:

• "Adversarially robust coloring for graph streams", with P. Ghosh and A. Chakrabarti. Full version on arXiv. PDF. Poster for a more general audience. Presentation slides.
• "Streaming algorithms for the Missing Item Finding problem". Full version on arXiv. PDF. Presentation slides.
• "Coloring in Graph Streams via Deterministic and Adversarially Robust Algorithms", with S. Assadi, A. Chakrabarti, P. Ghosh. PDF. Poster. Presentation slides.
• "Low-Memory Algorithms for Online and W-Streaming Edge Coloring", with P. Ghosh. Full version on arXiv. Poster.
• "Finding missing items requires strong forms of randomness", with A. Chakrabarti. Full version on arXiv. PDF. Presentation slides.

Preprint:

• "The Element Extraction Problem and the Cost of Determinism and Limited Adaptivity in Linear Queries", with A. Chakrabarti. PDF.

Unpublished:

• "On the parallel query complexity of pebbling formulas on pyramid graphs." PDF.
• "Lecture notes on the proof of the (improved) sunflower lemma." PDF.
• Lecture notes for a more accessible HyperLogLog analysis (PDF).

Thesis: "On adaptivity and randomness for streaming algorithms." PDF. Presentation slides (PDF).

Older work: 10.1016/j.nima.2019.04.046 (PDF) and 10.1063/1.5016292 (PDF).

Notes

Math honors paper on the distinct distance problem. Some intermediate work. Interesting figures. A prime-dimensional box problem construction.

My research notes are available at "notes/research/research_notesXX.html", where XX is replaced by a %02d-formatted number.

In progress paper on deterministic bijection-shift hash function selection: has reached git commit 887627cdbfc57c838ffc27d14ce4d6a6bab444b8, draft; status: paused.

Code

Waypipe is a transparent proxy for Wayland applications, which enables workflows similar to ssh -X. Development notes: GSOC 2019 project. 2024 Rust rewrite.

swaylock-plugin is fork of swaylock which allows using animated backgrounds from other programs. (With windowtolayer, general Wayland applications can be made to draw as backgrounds.)

wborder modifies Wayland applications to add a colored border

Maintainer for: the (mostly dormant) game Trackballs.

I also have some projects on: GitHub, sourcehut.

Status