Manuela Fischer

I am currently a postdoctoral researcher in the School of Computer Science at Reykjavík University in the group of Magnús M. Halldórsson.

Prior to that, I was a PhD student in the Discrete and Distributed Algorithms Group at the Institute of Theoretical Computer Science in the Computer Science department of ETH Zurich, advised by Prof. Mohsen Ghaffari, where my research was supported by a Google PhD Fellowship.

Contact Information

Manuela Fischer

manuela.fischer at inf.ethz.ch


Manuscripts

Deterministic (1 + eps)-Approximate Maximum Matching with poly(1/eps) Passes in the Semi-Streaming Model
Manuela Fischer, Slobodan Mitrović, and Jara Uitto
[arXiv]

Triangle resilience of the square of a Hamilton cycle in random graphs
Manuela Fischer, Nemanja Škorić, Angelika Steger, and Miloš Trujić
[arXiv]

Publications

Extreme k-Center Clustering
MohammadHossein Bateni, Manuela Fischer, Hossein Esfandiari, and Vahab Mirrokni
AAAI Conference on Artificial Intelligence (AAAI) 2021.

Breaking the Linear-Memory Barrier in MPC: Fast MIS on Trees with Strongly Sublinear Memory
Sebastian Brandt, Manuela Fischer, and Jara Uitto
Journal of Theoretical Computer Science (TCS) 2021.
[arXiv]

Tight Analysis of Parallel Randomized Greedy MIS
Manuela Fischer and Andreas Noever
ACM Transactions on Algorithms (TALG) 2020.
[arXiv] [Slides]

Improved Deterministic Distributed Matching via Rounding
Manuela Fischer
Journal of Distributed Computing 2020.
[arXiv] [Slides]

The Complexity of (Delta + 1)-Coloring in Congested Clique, Massively Parallel Computation, and Centralized Local Computation
Yi-Jun Chang, Manuela Fischer, Mohsen Ghaffari, Jara Uitto, and Yufan Zheng
ACM Symposium on Principles of Distributed Computing (PODC) 2019.
Best Student Paper Award at PODC'19
[arXiv]

Massively Parallel Computation of Matching and MIS in Sparse Graphs
Soheil Behnezhad, Sebastian Brandt, Masha Derakhshan, Manuela Fischer, MohammadTaghi Hajiaghayi, Richard M. Karp, and Jara Uitto
ACM Symposium on Principles of Distributed Computing (PODC) 2019.
[arXiv]

Breaking the Linear-Memory Barrier in MPC: Fast MIS on Trees with Strongly Sublinear Memory
Sebastian Brandt, Manuela Fischer, and Jara Uitto
International Colloquium on Structural Information and Communication Complexity (SIROCCO) 2019.
Best Student Paper Award at SIROCCO'19
Invited to the Journal of Theoretical Computer Science (TCS), Special Issue for SIROCCO 2019.
[arXiv]

A Simple Parallel and Distributed Sampling Technique: Local Glauber Dynamics
Manuela Fischer and Mohsen Ghaffari
International Symposium on DIStributed Computing (DISC) 2018.
[arXiv] [Slides]

Tight Analysis of Parallel Randomized Greedy MIS
Manuela Fischer and Andreas Noever
ACM-SIAM Symposium on Discrete Algorithms (SODA) 2018.
Invited to the ACM Transactions on Algorithms (TALG), Special Issue for SODA 2018.
[arXiv] [Slides]

Deterministic Distributed Edge-Coloring via Hypergraph Maximal Matching
Manuela Fischer, Mohsen Ghaffari, and Fabian Kuhn
IEEE Symposium on Foundations of Computer Science (FOCS) 2017.
Invited to the SIAM Journal of Computing (SICOMP), Special Issue for FOCS 2017.
[arXiv] [Slides]

Sublogarithmic Distributed Algorithms for Lovász Local Lemma, and the Complexity Hierarchy
Manuela Fischer and Mohsen Ghaffari
International Symposium on DIStributed Computing (DISC) 2017.
[arXiv] [Slides]

Improved Deterministic Distributed Matching via Rounding
Manuela Fischer
International Symposium on DIStributed Computing (DISC) 2017.
Best Student Paper Award at DISC'17
Invited to the Journal of Distributed Computing, Special Issue for DISC 2017.
[arXiv] [Slides]

Theses

Local Algorithms for Classic Graph Problems
PhD Thesis, submitted in May 2021, defended in June 2021

Robustness of Pósa's Conjecture
Master's Thesis, October 2016
[pdf] [arXiv]

Bootstrap Percolation with Individual Activation Thresholds
Bachelor's Thesis, September 2014
[pdf]

Talks

Local Glauber Dynamics
13.05.2020, Aalto CS Theory Seminar, Helsinki, Finland
[Slides]

The Complexity of (Delta + 1)-Coloring in Congested Clique, Massively Parallel Computation, and Centralized Local Computation
22.10.2019, Mittagsseminar ETH Zurich, Switzerland

The Complexity of (Delta + 1)-Coloring in Congested Clique, Massively Parallel Computation, and Centralized Local Computation
02.08.2019, PODC'19, Toronto, Canada

Breaking the Linear-Memory Barrier in MPC: Fast MIS on Trees with Strongly Sublinear Memory
22.07.2019, Workshop on Local Algorithms (WoLA) 2019, Zurich, Switzerland

Breaking the Linear-Memory Barrier in MPC: Fast MIS on Trees with Strongly Sublinear Memory
04.07.2019, SIROCCO'19, L'Aquila, Italy

Local Glauber Dynamics
05.03.2019, Google NYC Research Seminars, Google NYC, New York, USA
[Slides]

Local Glauber Dynamics
25.09.2018, Mittagsseminar ETH Zurich, Switzerland
[Slides]

Breaking the Linear-Memory Barrier in MPC: Fast MIS on Trees with Sublinear Memory per Machine
14.06.2018, Workshop on Local Algorithms (WoLA) 2018, MIT, Cambridge, Massachusetts, USA

Breaking the Linear-Memory Barrier in MPC: Fast MIS on Trees with Sublinear Memory per Machine
24.05.2018, Mittagsseminar ETH Zurich, Switzerland

Breaking the Linear-Memory Barrier in MPC: Fast MIS on Trees with Sublinear Memory per Machine
11.04.2018, Google Algorithms and Optimization PhD Workshop 2018, Google Zurich, Switzerland

Locality of Maximal Matching
07.03.2018, PIDSIA, IDSIA Lugano, Switzerland
[Slides]

Tight Analysis of Parallel Randomized Greedy MIS
10.01.2018, SODA'17, New Orleans, Lousiana, USA
[Slides]

Sublogarithmic Distributed Algorithms for Lovász Local Lemma, and the Complexity Hierarchy
18.10.2017, DISC'17, Vienna, Austria
[Slides]

Improved Deterministic Distributed Matching via Rounding
18.10.2017, DISC'17, Vienna, Austria
[Slides]

Deterministic Distributed Edge-Coloring via Hypergraph Maximal Matching
15.10.2017, FOCS'17, Berkeley, California, USA
[Slides]

Deterministic Distributed Edge-Coloring via Hypergraph Maximal Matching
21.09.2017, Mittagsseminar ETH Zurich, Switzerland
[Slides]

Deterministic Distributed Matching via Rounding
16.05.2017, Mittagsseminar ETH Zurich, Switzerland
[Slides]

Teaching

Data Structures and Algorithms
Reykjavík University, Fall 2021

Programmieren und Problemlösen
ETH Zurich, Spring 2021

Algorithms for Large-Scale Graph Processing
ETH Zurich, Spring 2021

Algorithms, Probability, and Computing
ETH Zurich, Fall 2020

Presenting Theoretical Computer Science
ETH Zurich, Spring 2020

Advanced Algorithms
ETH Zurich, Fall 2019

Seminar on Algorithms for Large-Scale Graph Processing
ETH Zurich, Fall 2019

Principles of Distributed Computing
ETH Zurich, Spring 2019

Advanced Algorithms
ETH Zurich, Fall 2018

Seminar on Algorithms for Large-Scale Graph Processing
ETH Zurich, Fall 2018

Principles of Distributed Computing
ETH Zurich, Spring 2018

Advanced Algorithms
ETH Zurich, Fall 2017

Principles of Distributed Computing
ETH Zurich, Spring 2017

Internships

IBM Research Europe and IBM T.J. Watson Research Center
IBM Research Europe, Zurich, Switzerland and IBM T.J. Watson Research Center, Yorktown Heights, New York, USA
August 2020 - November 2020

Google New York
Google NYC Algorithms and Optimiziation, New York City, New York, USA
December 2018 - March 2019

Program Committees

European Symposium on Algorithms (ESA) 2020