Prof. Dr. Tobias Friedrich


Four Papers accepted at FOCS, ALGOSENSORS, DocEng and COCOON

We are happy to announce that four papers authored by group members were accepted at international conferences. Firstly, Nikhil Kumar had his paper An Approximate Generalization of the Okamura-Seymour Theorem accepted at the Symposium on Foundations of Computer Science (FOCS), one of the top conferences in computer science! This year, the conference will take place on October 31 - November 3 in Denver, USA. The paper studies the problem of multicommodity flows in planar graphs and proves an approximate max-flow min-cut theorem. This result generalizes a classical result of Okamura and Seymour to the case when the demands can be incident on multiple faces, and thus makes progress towards resolving the well-known GNRS-Conjecture.

Secondly, George Skretas and his co-authors got their paper The Complexity of Growing a Graph accepted at this years International Symposium on Algorithmics of Wireless Networks (ALOGSENSORS) which will be hosted by the Algorithm Engineering group from September 8-9, 2022. They investigate the growth process that networks exhibit in the real world. In particular, they introduce a graph theoretical model where vertices are added to the network via a replication process. The goal is compute growth schedules that grow any target graph starting from a singleton vertex.

Thirdly, the paper Optical Character Recognition Guided Image Super Resolution, created by Philipp Hildebrandt and Maximilian Schulze, students of the course Competitive Programming with Deep Learning 2, and advised by Sarel Cohen and Vanja Doskoč as well as Raid Saabni from The Academic College of Tel Aviv-Yaffo, Israel, is accepted at the ACM Symposium on Document Engineering (DocEng). The event itself will take place online from September 20-23, 2022. The authors combine text super-resolution and optical character recognition deep learning models to improve recognizing disturbed text in real-life images. This is a difficult problem, as information that is missing due to low resolution or out-of-focus text has to be recreated. At the same time they create a smaller theoretical model (in size) due to the usage of quantization techniques.

Lastly, Tobias Friedrich, Andreas Göbel, Maximilian Katzmann, Martin Krejca and Marcus Pappik got their paper Algorithms for hard-constraint point processes via discretization accepted at the International Computing and Combinatorics Conference (COCOON). This years edition will be held in Shenzhen China in October 22-24, 2022. The paper introduces the first deterministic approximation algorithm for continuous partition functions — important quantities from statistical physics. The approximation works by discretizing the underlying physical system, relating it to the well-understood discrete case.

  • An Approximate Generaliza... - Download
    Kumar, Nikhil An Approximate Generalization of the Okamura-Seymour TheoremSymposium on Foundations of Computer Science (FOCS) 2022
  • Optical Character Recogni... - Download
    Hildebrandt, Philipp; Schulze, Maximilian; Cohen, Sarel; Doskoč, Vanja; Saabni, Raid; Friedrich, Tobias Optical Character Recognition Guided Image Super ResolutionSymposium on Document Engineering (DocEng) 2022: 1–4
  • Algorithms for hard-const... - Download
    Friedrich, Tobias; Göbel, Andreas; Katzmann, Maximilian; Krejca, Martin S.; Pappik, Marcus Algorithms for hard-constraint point processes via discretizationInternational Computing and Combinatorics Conference (COCOON) 2022