# May 8: Open Day

of Doctoral Studies

in Computer Science

## Doctoral Studies in Computer Science

Do you consider pursuing PhD studies in Computer Science? Come to our Open Day of Doctoral Studies in Computer Science held on May 8, 2023! You will see a sample of research topics offered to PhD students and have a chance to chat with potential future PhD advisors.

### Doctoral School

In 2019 University of Warsaw opened the Doctoral School of Exact and Natural Sciences. Within it, Faculty of Mathematics, Informatics and Mechanics of University of Warsaw (MIMUW) and Institute of Mathematics of the Polish Academy of Sciences (IMPAN) run Warsaw Doctoral School of Mathematics and Computer Science (WDSMCS). Both MIMUW and IMPAN are known worldwide for top level research in Mathematics and Computer Science. Over 100 research grants are running in these institutions, including several highly competitive ERC (European Research Commission) grants.

#### Recruitment 2023

In 2023, we offer 22 PhD student positions in Mathematics and Computer Science. Applications are accepted from May 8 until June 19, 2023.

#### Important Links

More information can be found at the following websites:

14:00-14:15 | 14:00-14:15Welcome address | ||

Łukasz Kowalik | Welcome address and a presentation of the Institute and the PhD School | ||

14:15-15:15 | 14:15-15:15Session 1: Machine Learning + Computational Social Choice | ||

Jacek Cyranka | Neural ODEs for generative AI | ||

Tomasz Michalak | AI for public safety and security | ||

Piotr Rafał Miłoś | Sequential decision making with AI | ||

Piotr Skowron | Proportional algorithms for democratic decisions | ||

15:15-15:45 | 15:15-15:45Informal chat | ||

15:45-16:30 | 15:45-16:30Session 2: Logic in Computer Science | ||

Mikołaj Bojańczyk | Finite state computation | ||

Sławomir Lasota | Frontiers of automatic analysis of concurrent systems | ||

Michał Pilipczuk | Algorithms, structural graph theory, and logic | ||

16:30-17:00 | 16:30-17:00Informal chat | ||

17:00-18:00 | 17:00-18:00Session 3: Algorithms + Bioinformatics | ||

Piotr Sankowski | IDEAS NCBR PhD programme | ||

Anna Gambin | Computational molecular medicine | ||

Jakub Radoszewski | Quest for optimality in variants of text indexing | ||

Marcin Pilipczuk | Graphs without long induced paths: structure and algorithms, remote | ||

18:00-18:30 | 18:00-18:30Informal chat | ||

18:30-19:15 | 18:30-19:15Session 4: AI + Cryptography | ||

Łukasz Kuciński | Autonomous Agents and Language Models | ||

Stefan Dziembowski | Cryptography - theory and applications | ||

Ewa Szczurek last minute cancellation | AI in medicine last minute cancellation | ||

19:15-19:45 | 19:15-19:45Informal chat |

## Abstracts

I am interested in methods that can deliver a robust decision-making capability in complex scenarios. Such methods can be applied in control to obtain broadly intelligent agents.

At the core of this effort is solving credit assignment over prolonged horizons. I like to put, perhaps unorthodoxly, many problems under this umbrella. The tasks requiring extreme reasoning, like math solving, on the one side and classical continuous control in robotics, on the other side.

I will present research topics in several domains of the modern AI reserach:

- sequential modeling and transformers
- reinforcement learning
- multi-task and continual learning
- planning and learning

Concurrent systems are ubiquitous, and the impact of their reliability is continuously increasing. In consequence, we observe an increasing call for improving the quality of concurrent systems. It is well known that concurrent system designs are prone to subtle bugs that are inherently difficult to find by humans, and examples of costly damages caused by such bugs abound. One way of achieving improvement of quality of such systems is formal verification, i.e., automatic analysis methods.

The topic of the PhD is to push further theoretical foundations of automatic analysis of models of concurrent systems, by investigating the frontiers of such analysis, and to enhance its practical applicability. We will specifically concentrate on the model of Petri nets, also known as vector addition systems, a long established model of concurrency with extensive applications in modelling and analysis of hardware, software and database systems, as well as chemical, biological and business processes. The central algorithmic problem for Petri nets is reachability: whether from the given initial configuration there exists a sequence of valid execution steps that reaches the given final configuration. The complexity of the problem has remained unsettled for over 40 years, becoming a most important open question in formal models of concurrent systerms, until the recent series of breakthrough results by Czerwiński, Lasota, Lazic, Leroux, Mazowiecki and Orlikowski (2019-2021) that closed the problem. On the technical level, the topic of the PhD is to exploit novel ideas underlying these results, in order to identify tractable special cases, variants and extensions of the problem.

For fixed integer t, the class of Pt-free graphs consists of graph without the t-vertex path as an induced subgraph. It is conjectured that a number of combinatorial problems, including Maximum Independent Set, remains polynomial-time solvable in Pt-free graphs (for every fixed t). In the recent years, we have seen a number of results supporting this conjecture, but we are still far from understanding the structure of such graphs to fully prove it.

Resolving the conjecture is one of the first main goals of my NCN SONATA BIS project that is about to start, and where I have positions for PhD students.

In the talk I will highlight the main recent results, proof techniques, and possible next steps.

## Contact

Questions related to the Open Day should be sent to Jakub Radoszewski (jrad@mimuw.edu.pl) or Piotr Skowron (p.skowron@mimuw.edu.pl)

Questions related to PhD studies should be sent to Łukasz Kowalik (kowalik@mimuw.edu.pl)