**Chair for**** Algorithm Engineering**

Hasso Plattner Institute

Office: A-1.13

Tel: +49 331 5509-417

E-Mail: Ralf.Rothenberger(at)hpi.de

# 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

I am co-organizing our weekly Research Seminar. Also, I am a member of the HPI's Research School on "Service-Oriented Systems Engineering".

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

Past Activities:

- 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

2021 [ nach oben ]

- The Impact of Heterogeneity and Geometry on the Proof Complexity of Random Satisfiability. Symposium on Discrete Algorithms (SODA) 2021

2020 [ nach oben ]

- Greed is Good for Deterministic Scale-Free Networks. Algorithmica 2020: 3338–3389

2019 [ nach oben ]

- Sharpness of the Satisfiability Threshold for Non-Uniform Random \(k\)-SAT.International Joint Conference on Artificial Intelligence (IJCAI) 2019: 6151-6155
- The Satisfiability Threshold for Non-Uniform Random 2-SAT. International Colloquium on Automata, Languages and Programming (ICALP) 2019: 61:1-61:14
- 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
- Routing for On-Street Parking Search using Probabilistic Data. AI Communications 2019: 113-124
- Greedy Maximization of Functions with Bounded Curvature Under Partition Matroid Constraints. Conference on Artificial Intelligence (AAAI) 2019: 2272-2279

2018 [ nach oben ]

- Memory-restricted Routing With Tiled Map Data. Systems, Man, and Cybernetics (SMC) 2018: 3347-3354
- 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 ]

- Bounds on the Satisfiability Threshold for Power Law Distributed Random SAT. European Symposium on Algorithms (ESA) 2017: 37:1-37:15
- Phase Transitions for Scale-Free SAT Formulas. Conference on Artificial Intelligence (AAAI) 2017: 3893-3899

2016 [ nach oben ]

- Greed is Good for Deterministic Scale-Free Networks. Foundations of Software Technology and Theoretical Computer Science (FSTTCS) 2016: 33:1-33:15
- Probabilistic Routing for On-Street Parking Search. European Symposium on Algorithms (ESA) 2016: 6:1-6:13

2015 [ nach oben ]

- Dominating an s-t-Cut in a Network. Current Trends in Theory and Practice of Computer Science (SOFSEM) 2015: 401-411
- Ultra-Fast Load Balancing on Scale-Free Networks. International Colloquium on Automata, Languages and Programming (ICALP) 2015: 516-527