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 similarity search in high dimensional spaces

2016/21/N/ST6/01468

Keywords:

similarity search nearest neighbor search high dimensional spaces approximate algorithm

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

Karol Węgrzycki 

Number of co-investigators in the project: 2

Call: PRELUDIUM 11 - announced on 2016-03-15

Amount awarded: 59 400 PLN

Project start date (Y-m-d): 2017-02-20

Project end date (Y-m-d): 2020-02-19

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.

Information in the final report

  • Publication in academic press/journals (1)
  • Articles in post-conference publications (4)
  1. Improved Distance Queries and Cycle Counting by Frobenius Normal Form
    Authors:
    Piotr Sankowski, Karol Węgrzycki
    Academic press:
    Theory of Computing Systems (rok: 2018, tom: Topical Collect, strony: 19), Wydawca: Springer US
    Status:
    Published
    DOI:
    10.1007/s00224-018-9894-x - link to the publication
  1. A Subquadratic Approximation Scheme for Partition
    Authors:
    Marcin Mucha, Karol Wegrzycki, Michal Wlodarczyk
    Conference:
    Symposium on Discrete Algorithms (SODA 2019) (rok: 2019, ), Wydawca: SIAM
    Data:
    konferencja 6-9 styczeń 2019
    Status:
    Published
  2. Equal-Subset-Sum Faster Than the Meet-in-the-Middle
    Authors:
    Marcin Mucha, Jesper Nederlof, Jakub Pawlewicz, Karol Wegrzycki
    Conference:
    27th Annual European Symposium on Algorithms ESA 2019 (rok: 2019, ), Wydawca: Schloss Dagstuhl--Leibniz-Zentrum fuer Informatik
    Data:
    konferencja 9-11.09.2019
    Status:
    Published
  3. Hamiltonian Cycle Parameterized by Treedepth in Single Exponential Time and Polynomial Space.
    Authors:
    Jesper Nederlof, Michal Pilipczuk, Céline M. F. Swennenhuis, Karol Wegrzycki
    Conference:
    Graph-Theoretic Concepts in Computer Science - 46th International Workshop, {WG} 2020 (rok: 2020, ), Wydawca: Springer
    Data:
    konferencja 24-26 Czerwiec 2020
    Status:
    Published
  4. Approximating APSP without Scaling: Equivalence of Approximate Min-Plus and Exact Min-Max
    Authors:
    Karl Bringmann, Marvin Künnemann, Karol Węgrzycki
    Conference:
    51st ACM Symposium on Theory of Computing (STOC 2019) (rok: 2019, ), Wydawca: ACM
    Data:
    konferencja 23-26 Czerwiec 2019
    Status:
    Published