Projects funded by the NCN

Information on the principal investigator and host institution

Information of the project and the call

Keywords

Equipment

Delete all

Around optimality of dynamic programming algorithms

2017/27/N/ST6/01334

Keywords:

algorithms computational complexity polynomial time fine-grained reductions

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 Jagielloński, Wydział Matematyki i Informatyki

woj. małopolskie

Other projects carried out by the institution 

Principal investigator (from the host institution):

dr Adam Polak 

Number of co-investigators in the project: 2

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

Amount awarded: 174 400 PLN

Project start date (Y-m-d): 2018-06-29

Project end date (Y-m-d): 2021-06-28

Project duration:: 36 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. Wysokowydajny laptop wraz z osprzętem (8 500 PLN)

Information in the final report

  • Articles in post-conference publications (6)
  1. Euler Meets GPU: Practical Graph Algorithms with Theoretical Guarantees
    Authors:
    Adam Polak, Adrian Siwiec, Michał Stobierski
    Conference:
    35th IEEE International Parallel & Distributed Processing Symposium (rok: 2021, ), Wydawca: IEEE
    Data:
    konferencja 17-21.05.2021
    Status:
    Published
  2. Faster Monotone Min-Plus Product, Range Mode, and Single Source Replacement Paths
    Authors:
    Yuzhou Gu, Adam Polak, Virginia Vassilevska Williams, Yinzhan Xu
    Conference:
    48th International Colloquium on Automata, Languages, and Programming (ICALP 2021) (rok: 2021, ), Wydawca: Schloss Dagstuhl--Leibniz-Zentrum fuer Informatik
    Data:
    konferencja 12-16.07.2021
    Status:
    Published
  3. Knapsack and Subset Sum with Small Items
    Authors:
    Adam Polak, Lars Rohwedder, Karol Węgrzycki
    Conference:
    48th International Colloquium on Automata, Languages, and Programming (ICALP 2021) (rok: 2021, ), Wydawca: Schloss Dagstuhl--Leibniz-Zentrum fuer Informatik
    Data:
    konferencja 12-16.07.2021
    Status:
    Published
  4. Equivalences between triangle and range query problems
    Authors:
    Lech Duraj, Krzysztof Kleiner, Adam Polak, Virginia Vassilevska Williams
    Conference:
    2020 ACM-SIAM Symposium on Discrete Algorithms (rok: 2020, ), Wydawca: SIAM
    Data:
    konferencja 5-8.01.2020
    Status:
    Published
  5. Monochromatic Triangles, Intermediate Matrix Products, and Convolutions
    Authors:
    Andrea Lincoln, Adam Polak, Virginia Vassilevska Williams
    Conference:
    11th Innovations in Theoretical Computer Science Conference (ITCS 2020) (rok: 2020, ), Wydawca: Schloss Dagstuhl--Leibniz-Zentrum fuer Informatik
    Data:
    konferencja 12-14.01.2020
    Status:
    Published
  6. Online metric algorithms with untrusted predictions
    Authors:
    Antonios Antoniadis, Christian Coester, Marek Elias, Adam Polak, Bertrand Simon
    Conference:
    37th International Conference on Machine Learning (ICML 2020) (rok: 2020, ), Wydawca: Proceedings of Machine Learning Research (PMLR)
    Data:
    konferencja 13-18.07.2020
    Status:
    Published

O Narodowym Centrum Nauki

Finansowanie nauki

Współpraca zagraniczna

Centrum prasowe

Deklaracja dostępności
Przetwarzanie danych osobowych
Polityka cookies

Partnerzy