Projects funded by the NCN

Information on the principal investigator and host institution

Information of the project and the call

Keywords

Equipment

Delete all

Efficient algorithms and conditional lower bounds for problems on trees

2017/27/N/ST6/02719

Keywords:

algorithm tree graph lower bound dynamic programming

Descriptors:

  • ST6_6: Algorithms, parallel, distributed and network algorithms, algorithmic game theory
  • ST6_4: Formal methods, foundations of computer science, including theoretical computer science, quantum algorithms

Panel:

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

Host institution :

Uniwersytet Wrocławski, Wydział Matematyki i Informatyki

woj. dolnośląskie

Other projects carried out by the institution 

Principal investigator (from the host institution):

Bartłomiej Dudek 

Number of co-investigators in the project: 2

Call: PRELUDIUM 14 - announced on 2017-09-15

Amount awarded: 180 200 PLN

Project start date (Y-m-d): 2018-09-03

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

Project duration:: 37 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. Laptop (6 000 PLN)
  2. Monitor (1 000 PLN)
  3. Licencje i oprogramowanie (1 000 PLN)

Information in the final report

  • Articles in post-conference publications (6)
  1. All non-trivial variants of 3-LDT are equivalent
    Authors:
    Bartłomiej Dudek, Paweł Gawrychowski, Tatiana Starikovskaya
    Conference:
    52nd Annual ACM SIGACT Symposium on Theory of Computing (STOC 2020) (rok: 2020, ), Wydawca: ACM
    Data:
    konferencja 22-26.06.2020
    Status:
    Published
  2. Counting 4-Patterns in Permutations Is Equivalent to Counting 4-Cycles in Graphs
    Authors:
    Bartłomiej Dudek, Paweł Gawrychowski
    Conference:
    31st International Symposium on Algorithms and Computation (ISAAC 2020) (rok: 2020, ), Wydawca: Schloss Dagstuhl - Leibniz-Zentrum fur Informatik
    Data:
    konferencja 14-18.12.2020
    Status:
    Published
    DOI:
    link to the publication
  3. Generalised Pattern Matching Revisited
    Authors:
    Bartłomiej Dudek, Paweł Gawrychowski, Tatiana Starikovskaya
    Conference:
    37th International Symposium on Theoretical Aspects of Computer Science (STACS 2020) (rok: 2020, ), Wydawca: Schloss Dagstuhl - Leibniz-Zentrum fur Informatik
    Data:
    konferencja 10-13.03.2020
    Status:
    Published
    DOI:
    link to the publication
  4. Computing quartet distance is equivalent to counting 4-cycles
    Authors:
    Bartłomiej Dudek, Paweł Gawrychowski
    Conference:
    51st Annual ACM SIGACT Symposium on Theory of Computing (rok: 2019, ), Wydawca: ACM
    Data:
    konferencja 43619
    Status:
    Published
  5. Streaming Regular Expression Membership and Pattern Matching
    Authors:
    Bartłomiej Dudek, Paweł Gawrychowski, Garance Gourdel, Tatiana Starikovskaya
    Conference:
    ACM-SIAM Symposium on Discrete Algorithms (SODA) (rok: 2022, ), Wydawca: SIAM
    Data:
    konferencja 9-12.01.2022
    Status:
    Published
  6. Strictly In-Place Algorithms for Permuting and Inverting Permutations
    Authors:
    Bartłomiej Dudek, Paweł Gawrychowski, Karol Pokorski
    Conference:
    Algorithms and Data Structures - 17th International Symposium (WADS) (rok: 2021, ), Wydawca: Springer
    Data:
    konferencja 9-11.08.2021
    Status:
    Published

O Narodowym Centrum Nauki

Finansowanie nauki

Współpraca zagraniczna

Centrum prasowe

Deklaracja dostępności
Przetwarzanie danych osobowych
Polityka cookies

Partnerzy