SOFSEM is an annual winter conference devoted to the theory and practice of computer science. The conference traditionally focuses on the latest results and developments of fundamental research in computer science (informatics), inspired by the algorithmic challenges of our time. SOFSEM has a long tradition as a high-quality research conference, and a venue where researchers from academia and industry in all stages of their career can share their insights. The series of SOFSEM conferences began in 1974, and was only interrupted in 2022 due to the covid pandemic. In 2025, at its 50th edition, SOFSEM will be held as a physical event in Bratislava, Slovakia. The proceedings will be published in the subseries ARCoSS (Advanced Research in Computing and Software Science) of the Lecture Notes in Computer Science (LNCS) of Springer.


Topics

The program committee encourages submission of original research papers in all areas of foundations of computer science and artificial intelligence, including e.g.

  • AI-based algorithms and techniques,
  • algorithms (approximation, combinatorial, exact, online, parameterized, probabilistic, streaming, etc)
  • automata (cellular, finite, networked, etc), languages, machine models, rewriting systems
  • computability, decidability, classical and non-classical models of computation,
  • computational complexity (incuding e.g. communication, descriptional, fine-grained, Kolmogorov, non-uniform, fixed-parameter and structural complexity),
  • computational geometry,
  • computational learning,
  • cryptographic techniques and security,
  • data compression algorithms,
  • data- and pattern mining methods (includeing e.g. models, theory, algorithms)
  • discrete combinatorial optimization, heuristics, local search, SAT solvers, simulation
  • efficient data structures (including e.g. dynamic, geometric, and spatial datastructures)
  • experimental algorithmics, applications
  • formal models of systems (including e.g. concurrent, hybrid, reactive, mobile, net-based, and timed systems)
  • graph structure and algorithms,
  • intelligent algorithms,
  • logics of computation, process models, program synthesis
  • machine learning theory,
  • multi-agent algorithms and games,
  • nature-inspired computing,
  • network science,
  • neural network theory,
  • parallel and distributed computing,
  • quantum computing,
  • robotics
  • structural complexity,
  • visualization algorithms (including e.g. graph drawing, network layout)

and other relevant theory topics in computing and AI.

SOFSEM History

For more information about the history of SOFSEM, please visit the general SOFSEM website: https://www.sofsem.cz/.

Program

The talks will begin on Monday morning (January 20) and conclude on Thursday evening (January 23).

Please refer to the following link for the conference program: SOFSEM 2025 Program.

Committees
Program Chairs

Program Committee

Steering Committee

Invited Speakers

  • Paola Flocchini, University of Ottawa, Canada

    • Paola Flocchini obtained her Ph.D. degree from the University of Milan, Italy. She is currently a Full Professor and the University Research Chair on Intruder Agents and the Decontamination of Communication Networks at the University of Ottawa, Canada. Her main research areas are theoretical computer science, specifically, distributed computing with special focus on mobility (moving and computing) and on dynamicity (time-varying graphs). She is also interested in fundamental computational and algorithmic issues that arise among autonomous mobile computational entities, in the design of algorithmic solutions in the context of dynamic networks, and in sense of direction and other structural information. In 2019, she was awarded the Prize for Innovation in Distributed Computing.

  • Erik Jan van Leeuwen, Utrecht University, The Netherlands

    • Erik Jan van Leeuwen received his Ph.D. from the University of Amsterdam. He is currently an Assistant Professor in the Algorithms and Complexity group in the Department of Information and Computing Sciences at the Utrecht University, The Netherlands. His research is focused on algorithms for network science, specializing in parameterized algorithms and network structure.

  • Paul Spirakis, University of Liverpool, United Kingdom

    • Paul Spirakis is a Professor at the University of Liverpool and also Professor Emeritus in Patras University. His research interests are in the fields of algorithms, complexity and algorithmic game theory , as well as in foundations of distributed computing. Paul Spirakis is a Fellow of EATCS and Editor-in-Chief of the Theoretical Computer Science Journal (Track A). He has acquired several grants from EU and also EPSRC. He is also a Member of Academia Europaea.

  • Ivan Tyukin, King's College London, United Kingdom

    • Ivan Tyukin is currently a Professor of Mathematical Data Science and Modelling at King’s College London, UK. His reasearch focuses on creating a theory and practice for developing AI systems that are provably robust, resilient, certifiable, trustworthy, human-centric and data-driven. Ivan Tyukin has been awarded a prestigious Turing AI Acceleration Fellowship to lead innovative and creative AI research with transformative impact. He is also an Editor of Communications in Nonlinear Science and Numerical Simulations.

Submission Guidelines

Papers should be submitted electronically through EasyChair.

Submissions should be prepared in accordance with Springer’s Instructions for Authors of Proceedings, and use the LaTeX template provided on the authors’ page. The length should not exceed 12 pages (excluding refeernces).

No prior publication or simultaneous submission to other conferences or journals are allowed (except preprint repositories such as arXiv or workshops without formal published proceedings). There is no need to anonymize the submissions.

The conference will present a Best Paper Award. Additionally, authors of selected papers presented at the conference will be invited to submit extended versions to a special issue of the Journal of Computer and System Sciences.

Importand Dates

  • Submission Deadline: September 15, 2024 (abstract)
  • Submission Deadline: September 22, 2024 (full papers)
  • Authors' notification: November 12, 2024
  • Conference: January 20-23, 2025

Accepted Papers
  • Christoph Grüne, Janosch Fuchs and Tom Janßen: The Complexity of Graph Exploration Games
  • Jessica Enright, Laura Larios-Jones, Kitty Meeks and William Pettersson: Reachability in temporal graphs under perturbation
  • Susanne Albers and Sebastian Schubert: Online b-Matching with Stochastic Rewards
  • Jan Gutleben and Arne Meier: A SUBSET-SUM Characterisation of the A-Hierarchy
  • Jan Goedgebeur and Jarne Renders: Generation of Cycle Permutation Graphs and Permutation Snarks
  • Dániel Szabó and Simon Apers: Holey graphs: very large Betti numbers are testable
  • Christian Ortlieb: Minimal Schnyder Woods and Long Induced Paths in 3-Connected Planar Graphs
  • Henry Förster, Julia Katheder and Giacomo Ortali: Outer-(ap)RAC Graphs
  • Takuya Mieno, Shun Takahashi, Kazuhisa Seto and Takashi Horiyama: Online and Offline Algorithms for Counting Distinct Closed Factors via Sliding Suffix Trees
  • Konstantinos Georgiou, Caleb Jones and Jesse Lucier: Multi-Agent Search-Type Problems on Polygons
  • Reuben Tate and Stephan Eidenbenz: Warm-Started QAOA with Aligned Mixers Converges Slowly Near the Poles of the Bloch Sphere
  • Thomas Depian, Simon Dominik Fink, Alexander Firbas, Robert Ganian and Martin Nöllenburg: Pathways to Tractability for Geometric Thickness
  • Wouter Meulemans, Arjen Simons and Kevin Verbeek: Visual Complexity of Point Set Mappings
  • Antonio Lauerbach, Kendra Reiter and Marie Schmidt: The Complexity of Counting Turns in the Line-Based Dial-a-Ride Problem
  • Alexander Dobler, Stephen Kobourov, Debajyoti Mondal and Martin Nöllenburg. Representing Hypergraphs by Point-Line Incidences
  • Yuichi Asahiro, Jesper Jansson, Avraham A. Melkman, Eiji Miyano, Hirotaka Ono, Quan Xue, Yoshichika Yano and Shay Zakov. Shortest Longest-Path Graph Orientations for Trees
  • Pyry Herva and Jarkko Kari: On the periodic decompositions of multidimensional configurations
  • Pál András Papp, Georg Anegg and Albert-Jan N. Yzelman: DAG Scheduling in the BSP Model
  • Yutaro Numaya, Yoshito Kawasaki, Ryo Yoshinaka and Ayumi Shinohara: Query Learning of Context-Deterministic and Congruential Context-Free Languages over Infinite Alphabets
  • Emilio Di Giacomo, Walter Didimo, Eleni Katsanou, Lena Schlipf, Antonios Symvonis and Alexander Wolff: Minimum Monotone Spanning Trees
  • Philip Bille, Inge Li Gørtz and Max Pedersen: Fast Practical Compression of Deterministic Finite Automata
  • Philip Bille, Inge Li Gørtz, Maximo Perez Lopez and Tord Stordalen: Dynamic Range Minimum Queries on the Ultra-Wide Word RAM
  • Hiroki Shibata, Masakazu Ishihata and Shunsuke Inenaga: Packed Acyclic Deterministic Finite Automata
  • Eric Rivals: Incremental computation of the set of period sets
  • Tetiana Lavynska: Colorful 3-Rainbow Domination
  • Henning Fernau, Lakshmanan Kuppusamy and Indhumathi Raman: On Computational Completeness of Semi-Conditional Matrix Grammars
  • Kevin Mann and Henning Fernau: Roman Hitting Set
  • Sampriti Roy and Yadu Vasudev: Tolerant Testing and Distance Estimation for Distributions Under Memory Constraints
  • Rick van de Bovenkamp and Hsiang-Hsuan Liu: Online Busy Time Scheduling with Untrusted Prediction
  • Shay Golan and Arseny Shur: Expected Density of Random Minimizers
  • Ryuto Kitagawa, Michael Goodrich and Michael Mitzenmacher: Parallel Peeling of Invertible Bloom Lookup Tables in a Constant Number of Rounds
  • Angelo Monti and Blerina Sinaimeri: Disjoint covering of bipartite graphs with $s$-clubs
  • Kazuma Yamane, Yuto Nakashima, Kazuhisa Seto and Takashi Horiyama: Maximal $\alpha$-gapped Repeats in a Fibonacci String
  • Ankit Abhinav, Satyabrata Jana, Nidhi Purohit, Abhishek Sahu and Saket Saurabh: Parameterized Complexity of Feedback Vertex Set with Connectivity Constraints
  • Hermann Gruber, Markus Holzer and Christian Rauch: On Pumping Problems for Unary Regular Languages
  • Guillaume Malod: Exact characterizations of non-commutative algebraic complexity without homogeneity
  • Ivana Beòová, Jana Košecká, Michal Gregor, Martin Tamajka, Marcel Veselý and Marián Šimko: Beyond Image-Text Matching: Verb Understanding in Multimodal Transformers Using Guided Masking
  • Clément Dallard, Maël Dumas, Claire Hilaire and Anthony Perez: Sufficient conditions for polynomial-time detection of induced minors
  • Shubhada Aute, Fahad Panolan, Souvik Saha, Saket Saurabh and Anannya Upasana: Parameterized Complexity of Generalizations of Edge Dominating Set
  • Sriram Bhyravarapu, Karthika Dhayanchand, Muthucumaraswamy Rajamanickam, Saket Saurabh, Sanjay Seetharaman and Matthias Bentert: On the Complexity of Minimum Membership Dominating Set
  • Sriram Bhyravarapu, Pankaj Kumar and Saket Saurabh: On the Structural Parameterized Complexity of Defective Coloring
  • Kevin Buchin, Mart Hagedoorn, Guangping Li and Carolin Rehs: Orienteering (with Time Windows) on Restricted Graph Classes
  • Daya Gaur, Barun Gorain, Shaswati Patra and Rishi Ranjan Singh: Forest Covers and Bounded Forest Covers
  • Kamil Khadiev and Danil Serov: Quantum Algorithm for the Multiple String Matching Problem
  • Bruce M. Kapron and Koosha Samieefar: The Computational Complexity of Equilibria with Strategic Constraints
  • Gennaro Cordasco, Luisa Gargano and Adele Rescigno: Distance Vector Domination
  • Grzegorz P. Mika, Amel Bouzeghoub, Katarzyna Wêgrzyn-Wolska and Yessin M. Neggaz: Knowledge Neurons in the Knowledge Graph-based Link Prediction Models
  • Thai Bui and Hoa Vu: Massively Parallel Maximum Coverage Revisited
Proceedings

Proceedings of SOFSEM 2025 - Springer LNCS series:

Proceedings of previous SOFSEMs - Springer LNCS series:
(For some older proceedings, you may need to scroll down the page to find the download links)

Registration

The registration fee includes, among others, access to lectures, a social dinner, accommodation (arrival on January 19, departure on January 24), and full board (starting with dinner on January 19 and ending with breakfast on January 24). The participants will also have access to the current and all previous SOFSEM's proceedings in the LNCS series for the duration of the conference.

Students who at the time of the conference have not yet completed their PhD qualify for the student status of the registration.

Attendee Early (until December 20)       Late (from December 20)
Regular / Single room 950€ 1000€
Regular / Double room 795€ 845€
Student / Single room 850€ 900€
Student / Double room 695€ 745€

Complete your registration online by filling out this form: SOFSEM 2025 registration.

Visa

If you need a visa for attending the conference, contact the organizers at sofsem2025@sofsem.sk. We can send you an invitation letter, but please note that we are not able to obtain a police-certified invitation.

Venue

The conference will be held in the Sorea Regia Hotel in Bratislava, Slovakia (location on Google maps).

Travel Information
Reaching Bratislava from Vienna Airport

The most common way to reach Bratislava is via the Vienna International Airport, from where there are frequent regional bus connections directly to the bus stop Most SNP in the centre of Bratislava (about 45 minutes). The bus connections can be found here. The conference venue can be easily reached from Most SNP by taking a bus 29 or 37, or a tram 4.

Bratislava Airport

There are also several flights to and from Bratislava Airport operated mostly by low-cost carriers. The conference venue can be reached from the airport by taking a bus 61 and changing to a tram 4 or 9 at Trnavské mýto.

Reaching Bratislava by Train

Bratislava main train station is connected by international trains to Prague, Berlin, Warsaw, Budapest, etc. The conference venue can be reached from the main train station by taking a tram 1 and changing to a tram 9 at Poštová.

Travelling around Bratislava by public transport

Tickets can be purchased in ticket machines at public transport stops or alternatively you can use a bank card to buy ticket directly within the bus/tram (see these instructions).

Getting to the Conference Venue

The conference venue is located within the short walking distance from the public transport stop Kráľovské údolie (trams 4, 9 and buses 29, 31, 37, 39). See the interactive map below:

Places Worth Visiting

Contact

For any questions, please don't hesitate to contact us at sofsem2025@sofsem.sk.