This is an archived page of a former group member.

# Research Interests

My research interests include several topics of algorithmics and theoretical computer science.

- graph theory
- graph algorithms
- random graphs
- scale-free networks

- satisfiability
- random SAT models
- phase transitions
- proof complexity

- algorithms
- random algorithms
- load balancing
- approximation algorithms

# Teaching

As Advisor

- Optimizing Project Schedules (BSc Project, 2017/18)
- Analysis of random geometric SAT instances (MSc Project, Winter 2017/18)
- Geometry in industrial model-checking SAT instances (MSc Project, Winter 2017/18)
- Efficient Shortest Paths on Portable Devices (BSc-Projekt, 2016/17)
- Finding a Parking Place Quickly (BSc-Projekt, 2015/16)

# Activities

Since 2017 I am a member of the HPI's board game club.

Past Activities:

- member of the HPI Research School on "Service-Oriented Systems Engineering"
- co-organizing the group's weekly Research Seminar
- member of the organization committee for the 13th Symposium on Future Trends in Service-Oriented Computing 2018
- member of the organization committee for the 12th Symposium on Future Trends in Service-Oriented Computing 2017

### Power-Law Random SAT generator

The algorithm for this generator was proposed by Ansótegui et al. in "Towards industrial-like random SAT instances" (IJCAI 2009).

We used this generator for the experiments in "Phase Transitions for Scale-Free SAT Formulas" (AAAI 2017) and "Bounds on the Satisfiability Threshold for Power Law Distributed Random SAT" (ESA 2017).

The code of our implementation can be found here.

## Publications

2023 [ nach oben ]

2021 [ nach oben ]

- Bläsius, Thomas; Friedrich, Tobias; Göbel, Andreas; Levy, Jordi; Rothenberger, Ralf
**The Impact of Heterogeneity and Geometry on the Proof Complexity of Random Satisfiability**Symposium on Discrete Algorithms (SODA) 2021: 42–53 - Friedrich, Tobias; Neumann, Frank; Rothenberger, Ralf; Sutton, Andrew M.
**Solving Non-Uniform Planted and Filtered Random SAT Formulas Greedily**Theory and Applications of Satisfiability Testing (SAT) 2021: 188–206

2020 [ nach oben ]

2019 [ nach oben ]

- Friedrich, Tobias; Krejca, Martin S.; Rothenberger, Ralf; Arndt, Tobias; Hafner, Danijar; Kellermeier, Thomas; Krogmann, Simon; Razmjou, Armin
**Routing for On-Street Parking Search using Probabilistic Data**AI Communications 2019: 113–124 - Friedrich, Tobias; Göbel, Andreas; Neumann, Frank; Quinzan, Francesco; Rothenberger, Ralf
**Greedy Maximization of Functions with Bounded Curvature Under Partition Matroid Constraints**Conference on Artificial Intelligence (AAAI) 2019: 2272–2279 - Peters, Jannik; Stephan, Daniel; Amon, Isabel; Gawendowicz, Hans; Lischeid, Julius; Salabarria, Julius; Umland, Jonas; Werner, Felix; Krejca, Martin S.; Rothenberger, Ralf; Kötzing, Timo; Friedrich, Tobias
**Mixed Integer Programming versus Evolutionary Computation for Optimizing a Hard Real-World Staff Assignment Problem**International Conference on Automated Planning and Scheduling (ICAPS) 2019: 541–554 - Friedrich, Tobias; Rothenberger, Ralf
**The Satisfiability Threshold for Non-Uniform Random 2-SAT**International Colloquium on Automata, Languages and Programming (ICALP) 2019: 61:1–61:14 - Friedrich, Tobias; Rothenberger, Ralf
**Sharpness of the Satisfiability Threshold for Non-Uniform Random \(k\)-SAT.**International Joint Conference on Artificial Intelligence (IJCAI) 2019: 6151–6155

2018 [ nach oben ]

- Bläsius, Thomas; Eube, Jan; Feldtkeller, Thomas; Friedrich, Tobias; Krejca, Martin S.; Lagodzinski, J. A. Gregor; Rothenberger, Ralf; Severin, Julius; Sommer, Fabian; Trautmann, Justin
**Memory-restricted Routing With Tiled Map Data**Systems, Man, and Cybernetics (SMC) 2018: 3347–3354 - Friedrich, Tobias; Rothenberger, Ralf
**Sharpness of the Satisfiability Threshold for Non-Uniform Random k-SAT**Theory and Applications of Satisfiability Testing (SAT) 2018: 273–291Best Paper Award

2017 [ nach oben ]

- Friedrich, Tobias; Krohmer, Anton; Rothenberger, Ralf; Sauerwald, Thomas; Sutton, Andrew M.
**Bounds on the Satisfiability Threshold for Power Law Distributed Random SAT**European Symposium on Algorithms (ESA) 2017: 37:1–37:15 - Friedrich, Tobias; Krohmer, Anton; Rothenberger, Ralf; Sutton, Andrew M.
**Phase Transitions for Scale-Free SAT Formulas**Conference on Artificial Intelligence (AAAI) 2017: 3893–3899

2016 [ nach oben ]

- Chauhan, Ankit; Friedrich, Tobias; Rothenberger, Ralf
**Greed is Good for Deterministic Scale-Free Networks**Foundations of Software Technology and Theoretical Computer Science (FSTTCS) 2016: 33:1–33:15 - Arndt, Tobias; Hafner, Danijar; Kellermeier, Thomas; Krogmann, Simon; Razmjou, Armin; Krejca, Martin S.; Rothenberger, Ralf; Friedrich, Tobias
**Probabilistic Routing for On-Street Parking Search**European Symposium on Algorithms (ESA) 2016: 6:1–6:13

2015 [ nach oben ]

- Rothenberger, Ralf; Grau, Sascha; Rossberg, Michael
**Dominating an s-t-Cut in a Network**Current Trends in Theory and Practice of Computer Science (SOFSEM) 2015: 401–411 - Bringmann, Karl; Friedrich, Tobias; Hoefer, Martin; Rothenberger, Ralf; Sauerwald, Thomas
**Ultra-Fast Load Balancing on Scale-Free Networks**International Colloquium on Automata, Languages and Programming (ICALP) 2015: 516–527