Around optimality of dynamic programming algorithms
2017/27/N/ST6/01334
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 Jagielloński, Wydział Matematyki i Informatyki
Voivodeship: małopolskie
Principal investigator (from the host institution)
Number of co-investigators in the project: 2
Call
PRELUDIUM 14 – announced on 2017-09-15
- Amount awarded
- 174 400 PLN
- Project start date
- 2018-06-29
- Project end date
- 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]
- Wysokowydajny laptop wraz z osprzętem. Cost: 8 500 PLN
Information in the final report
Articles in post-conference publications (6)
-
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) (year: 2020, pages: 53:1-53:18), Publisher: Schloss Dagstuhl--Leibniz-Zentrum fuer Informatik
- Date:
- conference 12-14.01.2020
- Status:
- Published
-
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) (year: 2020, pages: 345-355), Publisher: Proceedings of Machine Learning Research (PMLR)
- Date:
- conference 13-18.07.2020
- Status:
- Published
-
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 (year: 2020, pages: 30-47), Publisher: SIAM
- Date:
- conference 5-8.01.2020
- Status:
- Published
-
Euler Meets GPU: Practical Graph Algorithms with Theoretical Guarantees
- Authors:
- Adam Polak, Adrian Siwiec, Michał Stobierski
- Conference:
- 35th IEEE International Parallel & Distributed Processing Symposium (year: 2021, pages: 233-244), Publisher: IEEE
- Date:
- conference 17-21.05.2021
- Status:
- Published
-
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) (year: 2021, pages: 106:1-106:19), Publisher: Schloss Dagstuhl--Leibniz-Zentrum fuer Informatik
- Date:
- conference 12-16.07.2021
- Status:
- Published
-
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) (year: 2021, pages: 75:1-75:20), Publisher: Schloss Dagstuhl--Leibniz-Zentrum fuer Informatik
- Date:
- conference 12-16.07.2021
- Status:
- Published