-
NAME/
Michael Joseph Coulombe
-
STATUS/
Ph.D. Student
- CONTACT/
His research interests include provable algorithms and data structures, with applications from game analysis to concurrency, and the methods of expressing and analyzing them.
He acquired a Master's Degree in June 2015 from MIT for his work on MergeArray, working as a research assistant under Nir Shavit in the Multicore Algorithmics Group and the Computational Connectomics Group.
He previously studied Computer Science at the University of California, Davis, where he performed undergraduate research under Dan Gusfield on perfect phylogeny algorithms.
Publications
-
This Game Is Not Going To Analyze Itself
- with Aviv Adler, Joshua Ani, Lily Chung, Erik D. Demaine, Yevhenii Diomidov, Dylan Hendrickson, Jayson Lynch
- on arXiv: 2302.01145
- appeared at JCDCGGG 2022
-
Complexity of Solo Chess with Unlimited Moves
- with Josh Brunner, Lily Chung, Erik D. Demaine, Timothy Gomez, Jayson Lynch
- on arXiv: 2302.01405
- appeared at JCDCGGG 2022
-
Characterizing the Decidability of Finite State Automata Team Games with Communication
- with Jayson Lynch
- on arXiv: 2209.10324
- appeared at GandALF 2022, listing on EPTCS
-
The Legend of Zelda: The Complexity of Mechanics
- with Jeffrey Bosboom, Josh Brunner, Erik D. Demaine, Dylan H. Hendrickson, Jayson Lynch, Elle Najt
- on arXiv: 2203.17167
- appeared at TJCDCGGG 2021
-
Tetris is NP-hard even with O(1) rows or columns
- with Sualeh Asif, Erik D. Demaine, Martin L. Demaine, Adam Hesterberg, Jayson Lynch, and Mihir Singhal
- published in Journal of Information Processing volume 28, 2020
- DOI: 10.2197/ipsjjip.28.942
-
Edge Matching with Inequalities, Triangles, Unknown Shape, and Two Players
- with Jeffrey Bosboom, Charlotte Chen, Lily Chung, Spencer Compton, Erik D. Demaine, Martin L. Demaine, Ivan Tadeu Ferreira Antunes Filho, Dylan Hendrickson, Adam Hesterberg, Calvin Hsu, William Hu, Oliver Korten, Zhezheng Luo, and Lillian Zhang
- published in Journal of Information Processing volume 28, 2020
- DOI: 10.2197/ipsjjip.28.987
-
Who witnesses The Witness? Finding witnesses in The Witness is hard and sometimes impossible
- with Zachary Abel, Linus Hamilton, Jeffrey Bosboom, Adam Hesterberg, Mikhail Rudoy, Justin Kopinsky, Erik D. Demaine, Jayson Lynch, Clemens Thielen
- published by TCS, DOI: 10.1016/j.tcs.2020.05.031
- 6 / 25 / 2020
- Eurogamer article by Cian Maher
-
Cooperating in Video Games? Impossible! Undecidability of Team Multiplayer Games
- with Jayson Lynch
- appeared at FUN 2018, DOI: 10.4230/LIPIcs.FUN.2018.14
- published by TCS, DOI: 10.1016/j.tcs.2020.05.028
-
Construction, enumeration, and optimization of perfect phylogenies on multi-state data.
- with Kristian Stevens and Dan Gusfield
- appeared at ICCABS 2015
- IEEE Xplore Abstract
- Paper and Slides
- Software (#17)
-
MergeArray and Scalable, Relaxed, Concurrent, Mergeable Priority Queues
- Master's Thesis
- Source Code
- 05 / 20 / 2015
- Talk at Boston D Meetup
Teaching Assistantships at MIT
-
6.1400J Computability and Complexity Theory
- Spring / 2023
-
6.5210J Advanced Algorithms
- Fall / 2022
-
6.042J Mathematics for Computer Science
- Spring / 2022
- Spring / 2019
-
6.006 Introduction to Algorithms
- Fall / 2021
- Spring / 2021
- Spring / 2020
- Fall / 2018
- Spring / 2018
- Fall / 2017
-
6.836 Multicore Programming
- Fall / 2020
- Spring / 2017
- Spring / 2016
-
6.436 Fundamentals of Probability
- Fall / 2019
-
6.840 Theory of Computation
- Fall / 2014
Courses at MIT
-
6.892 Algorithmic Lower Bounds: Fun with Hardness Proofs
(Listener) Spring / 2019
-
8.033 Relativity
Fall / 2017
-
8.370 Quantum Computation
Fall / 2016
-
6.875 Cryptography & Cryptanalysis
(Listener) Spring / 2016
-
6.864 Advanced Natural Language Processing
Fall / 2015
-
6.878 Advanced Computational Biology: Genomes, Networks, Evolution
Fall / 2014
-
6.836 Multicore Programming
Spring / 2014
-
6.840 Theory of Computation
Fall / 2013
-
6.820 Foundations of Program Analysis
Fall / 2013
Last Updated: February 7, 2023