Projects funded by the NCN

Information on the principal investigator and host institution

Information of the project and the call

Keywords

Equipment

Delete all

Limits of Databases

2016/21/D/ST6/01485

Keywords:

conjunctive queries graph limits

Descriptors:

  • ST6_4: Formal methods, foundations of computer science, including theoretical computer science, quantum algorithms
  • ST6_6: Algorithms, parallel, distributed and network algorithms, algorithmic game theory
  • ST6_10: Web and information systems, database systems, internet technologies, including information retrieval and digital libraries

Panel:

ST6 - Computer science and informatics: informatics and information systems, computer science, scientific computing, intelligent systems

Host institution :

Uniwersytet Warszawski, Wydział Matematyki, Informatyki i Mechaniki

woj. mazowieckie

Other projects carried out by the institution 

Principal investigator (from the host institution):

dr Szymon Toruńczyk 

Number of co-investigators in the project: 3

Call: SONATA 11 - announced on 2016-03-15

Amount awarded: 342 630 PLN

Project start date (Y-m-d): 2017-02-20

Project end date (Y-m-d): 2021-02-19

Project duration:: 48 months (the same as in the proposal)

Project status: Project settled

Project description

Download the project description in a pdf file

Note - project descriptions were prepared by the authors of the applications themselves and placed in the system in an unchanged form.

Equipment purchased [PL]

  1. drukarka.
  2. tablet.
  3. Komputer stacjonarny (8 000 PLN)
  4. Laptop (2 szt.) (16 000 PLN)

Information in the final report

  • Publication in academic press/journals (1)
  • Articles in post-conference publications (8)
  1. Definable isomorphism problem
    Authors:
    Keshvardoost, Khadijeh and Klin, Bartek and Lasota, Sławomir and Ochremiak, Joanna and Toruńczyk, Szymon
    Academic press:
    Logical Methods in Computer Science (rok: 2019, tom: 15, strony: 14:1-14:19), Wydawca: Computing Research Repository
    Status:
    Published
    DOI:
    10.23638/LMCS-15(4:14)2019 - link to the publication
  1. Progressive Algorithms for Domination and Independence
    Authors:
    Grzegorz Fabianski, Michał Pilipczuk, Sebastian Siebertz, Szymon Toruńczyk
    Conference:
    36th International Symposium on Theoretical Aspects of Computer Science, STACS 2019 (rok: 2019, ), Wydawca: Schloss Dagstuhl - Leibniz-Zentrum fur Informatik
    Data:
    konferencja 43507
    Status:
    Published
  2. Aggregate queries on sparse databases
    Authors:
    Szymon Toruńczyk
    Conference:
    Symposium on Principles of Database Systems (PODS 2020) (rok: 2020, ), Wydawca: ACM
    Data:
    konferencja Lipiec 2020
    Status:
    Published
  3. On computability and tractability for infinite sets
    Authors:
    Mikołaj Bojańczyk, Szymon Toruńczyk
    Conference:
    Proceedings of the 33rd Annual ACM/IEEE Symposium on Logic in Computer Science (LICS) 2018 (rok: 2018, ), Wydawca: ACM
    Data:
    konferencja 09-12 lipca 2018
    Status:
    Published
  4. On the number of types in sparse graphs
    Authors:
    Michał Pilipczuk, Sebastian Siebertz, Szymon Toruńczyk
    Conference:
    Proceedings of the 33rd Annual ACM/IEEE Symposium on Logic in Computer Science (LICS) 2018 (rok: 2018, ), Wydawca: ACM
    Data:
    konferencja 09-12 lipca 2018
    Status:
    Published
  5. Finite Query Answering in Expressive Description Logics with Transitive Roles
    Authors:
    Tomasz Gogacz, Yazmin Angélica Ibáñez-García, Filip Murlak
    Conference:
    Principles of Knowledge Representation and Reasoning: Proceedings of the Sixteenth International Conference (KR) 2018 (rok: 2018, ), Wydawca: AAAI Press
    Data:
    konferencja 30 październik-2 listopad 2018
    Status:
    Published
  6. First-Order Interpretations of Bounded Expansion Classes
    Authors:
    Jakub Gajarský, Stephan Kreutzer, Jaroslav Nesetril, Patrice Ossona de Mendez, Michal Pilipczuk, Sebastian Siebertz, Szymon Toruńczyk
    Conference:
    International Colloquium on Automata, Languages and Programming (ICALP) 2018 (rok: 2018, ), Wydawca: Leibniz International Proceedings in Informatics Schloss Dagstuhl – Leibniz-Zentrum für Informatik, Dagstuhl Publishing, Germany
    Data:
    konferencja 9-13 lipca 2018
    Status:
    Published
  7. Uniformisations of Regular Relations Over Bi-Infinite Words
    Authors:
    Grzegorz Fabiański, Michał Skrzypczak, Szymon Toruńczyk
    Conference:
    35th Annual Symposium on Logic in Computer Science (LICS 2020) (rok: 2020, ), Wydawca: ACM
    Data:
    konferencja Lipiec 2020
    Status:
    Published
  8. Parameterized circuit complexity of model-checking on sparse structures
    Authors:
    Michal Pilipczuk, Sebastian Siebertz, Szymon Toruńczyk
    Conference:
    Proceedings of the 33rd Annual ACM/IEEE Symposium on Logic in Computer Science (LICS) 2018 (rok: 2018, ), Wydawca: ACM
    Data:
    konferencja 9-12 lipca 2018
    Status:
    Published

O Narodowym Centrum Nauki

Finansowanie nauki

Współpraca zagraniczna

Centrum prasowe

Deklaracja dostępności
Przetwarzanie danych osobowych
Polityka cookies

Partnerzy