Zmiana języka

Projects search

Efficient algorithms and conditional lower bounds for problems on trees

2017/27/N/ST6/02719

Keywords

Descriptors

  • ST6_6: Algorytmika, algorytmy równoległe, rozproszone i sieciowe, algorytmiczna teoria gier
  • ST6_4: Metody formalne, teoretyczne podstawy informatyki w tym informatyka teoretyczna

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

Voivodeship: 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
2018-09-03
Project end date
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. Cost: 6 000 PLN
  2. Licencje i oprogramowanie. Cost: 1 000 PLN
  3. Monitor. Cost: 1 000 PLN

Information in the final report

Articles in post-conference publications (6)

  1. 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) (year: 2020, pages: 23:1--23:18), Publisher: Schloss Dagstuhl - Leibniz-Zentrum fur Informatik
    Date:
    conference 14-18.12.2020
    Status:
    Published
    DOI:
    link to the publication

  2. 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) (year: 2021, pages: 329-342), Publisher: Springer
    Date:
    conference 9-11.08.2021
    Status:
    Published

  3. 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) (year: 2020, pages: 974-981), Publisher: ACM
    Date:
    conference 22-26.06.2020
    Status:
    Published

  4. Generalised Pattern Matching Revisited

    Authors:
    Bartłomiej Dudek, Paweł Gawrychowski, Tatiana Starikovskaya
    Conference:
    37th International Symposium on Theoretical Aspects of Computer Science (STACS 2020) (year: 2020, pages: 18:1--18:18), Publisher: Schloss Dagstuhl - Leibniz-Zentrum fur Informatik
    Date:
    conference 10-13.03.2020
    Status:
    Published
    DOI:
    link to the publication

  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) (year: 2022, pages: 670 - 694), Publisher: SIAM
    Date:
    conference 9-12.01.2022
    Status:
    Published

  6. 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 (year: 2019, pages: 733-743), Publisher: ACM
    Date:
    conference 43619
    Status:
    Published

« New search

Graphic design and implementation: Jakub Piotrowski