Projects funded by the NCN


Information on the principal investigator and host institution

Information of the project and the call

Keywords

Equipment

Delete all

Tight Lower Bounds Under Strong Complexity Assumptions

2015/17/N/ST6/01224

Keywords:

algorithms complexity lower bounds hardness

Descriptors:

  • ST6_6: Algorithms, parallel, distributed and network algorithms, algorithmic game theory

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):

Arkadiusz Socała 

Number of co-investigators in the project: 2

Call: PRELUDIUM 9 - announced on 2015-03-16

Amount awarded: 64 800 PLN

Project start date (Y-m-d): 2016-03-16

Project end date (Y-m-d): 2018-09-15

Project duration:: 30 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.

Information in the final report

  • Articles in post-conference publications (2)
  1. Tight Lower Bounds for List Edge Coloring
    Authors:
    Łukasz Kowalik, Arkadiusz Socała
    Conference:
    16th Scandinavian Symposium and Workshops on Algorithm Theory (SWAT 2018) (rok: 2018, ), Wydawca: Schloss Dagstuhl - Leibniz-Zentrum fuer Informatik
    Data:
    konferencja 18-20 czerwca 2018
    Status:
    Published
  2. Tight Lower Bounds for the Complexity of Multicoloring.
    Authors:
    Marthe Bonamy, Łukasz Kowalik, Michał Pilipczuk, Arkadiusz Socała, Marcin Wrochna
    Conference:
    25th Annual European Symposium on Algorithms, ESA 2017 (rok: 2017, ), Wydawca: Schloss Dagstuhl - Leibniz-Zentrum fuer Informatik
    Data:
    konferencja 4-6 września 2017
    Status:
    Published