Stefan Neumann, MSc


Faculty of Computer Science
University of Vienna
Room 6.23
Waehringerstrasse 29/6.32
1090 Wien-Vienna, Austria

phone +43-1-4277-78341
web: personal homepage

Teaching: course directory


Monika Henzinger

MSc (Computer Science)

Research area in the program
Combinatorial Optimization


  • dynamic graph algorithms
  • conditional lower bounds
  • cell-probe lower bounds
  • data mining

Research Interests

My research interests are centered around the analysis of dynamic graph algorithms. For these problems I am particularly interested in deriving lower bounds (both conditional and unconditional) and upper bounds (fully dynamic algorithms and dynamic algorithms with only a small number of updates). Besides that, I also like data mining.

Scientific CV

Since 2016, PhD student at University of Vienna
2013-2015, MSc in Computer Science at Max Planck Institute of Computer Science and Saarland University
2010-2013, BSc in Mathematics at University of Jena

[ Download CV ]


Work in progress

Henzinger, M., Neumann, S. & Wiese, A. (2019) Fully Dynamic Independent Set of Rectangles.

Dell, H. Neumann, S. & Upfal, E. (2019). Conditional Hardness for Frequent Itemset Data Structures.

Cohen-Addad, V., Miettinen, P. & Neumann, S. (2019). Computing Boolean Matrix Factorizations in Data Streams.

Accepted / published papers

Henzinger, M. & Neumann, S. (2016). Incremental and Fully Dynamic Subgraph Connectivity for Emergency Planning. In: 24th Annual European Symposium on Algorithms (ESA 2016).

Neumann, S. & Wiese, A. (2016). This House Proves That Debating Is Harder Than Soccer. In: Eighth International Conference on Fun with Algorithms, 25:1-25:14.

Neumann, S., Gemulla, R. & Miettinen, P. (2016). What You Will Gain By Rounding: Theory and Algorithms for Rounding Rank. ICDM'16.

Neumann, S. & Miettinen, P. (2017). Reductions for Frequency-Based Data Mining Problems. ICDM'17.

Henzinger, M., Lincoln, A., Neumann, S. & Vassilevska Williams, V. (2017). Conditional Hardness for Sensitivity Problems. 8th Innovations in Theoretical Computer Science, ITCS.

Neumann, S., Ritter, J. & Budhathoki, K. (2018). Ranking the Teams in European Football Leagues with Agony. MLSA@PKDD/ECML'18.

Neumann, S. (2018). Bipartite Stochastic Block Models with Tiny Clusters. NeurIPS'18.

Henzinger, M., Neumann, S., Schmid, S. (2019). Efficient Distributed Workload (Re-) Embedding. SIGMETRICS'19 and POMACS Journal.

Bhattacharya, S., Henzinger, M. & Neumann S. (2019). New Amortized Cell-Probe Lower Bounds for Dynamic Problems. Theoretical Computer Science.