Projects funded by the NCN

Information on the principal investigator and host institution

Information of the project and the call

Keywords

Equipment

Delete all

Algebraic theory for CSP (tractability, approximation and optimization)

2014/13/B/ST6/01812

Keywords:

Constraint Satisfaction Problem computational complexity approximation algorithms optimization

Descriptors:

  • ST6_4: Formal methods, foundations of computer science, including theoretical computer science, quantum algorithms
  • ST6_6: Algorithms, parallel, distributed and network algorithms, algorithmic game theory
  • ST1_18: Control theory and optimisation

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 hab. Marcin Kozik 

Number of co-investigators in the project: 3

Call: OPUS 7 - announced on 2014-03-17

Amount awarded: 486 920 PLN

Project start date (Y-m-d): 2015-02-18

Project end date (Y-m-d): 2019-02-17

Project duration:: 48 months (the same as in the proposal)

Project status: Project settled

Equipment purchased [PL]

  1. Laptop (8 000 PLN)

Information in the final report

  • Publication in academic press/journals (9)
  • Articles in post-conference publications (3)
  • Book publications / chapters in book publications (1)
  1. Taylor's modularity conjecture and related problems for idempotent varieties
    Authors:
    Jakub Oprsal
    Academic press:
    Order (rok: 2018, tom: 35, strony: 433-460), Wydawca: Springer
    Status:
    Published
    DOI:
    10.1007/s11083-017-9441-4 - link to the publication
  2. The subpower membership problem for semigroups
    Authors:
    Andrei Bulatov, Marcin Kozik, Peter Mayr, Markus Steindl
    Academic press:
    International Journal of Algebra and Computation (rok: 2016, tom: 26, strony: 1435-1451), Wydawca: World Scientific
    Status:
    Published
    DOI:
    10.1142/S0218196716500612 - link to the publication
  3. On lattice representations with posets
    Authors:
    Gergo Gyenizse
    Academic press:
    Order , Wydawca: Springer
    Status:
    Submitted
    DOI:
    brak - link to the publication
  4. Solving CSPs using weak local consistency
    Authors:
    Marcin Kozik
    Academic press:
    SIAM Journal on Computing , Wydawca: SIAM Publications
    Status:
    Accepted for publication
    DOI:
    brak - link to the publication
  5. Local loop lemma
    Authors:
    Miroslav Olsak
    Academic press:
    Algebra Universalis (rok: 2020, tom: 81, strony: article no. 14), Wydawca: Springer
    Status:
    Published
    DOI:
    10.1007/s00012-020-0644-y - link to the publication
  6. Robust algorithms with polynomial loss for near-unanimity CSPs
    Authors:
    Victor Dalmau, Marcin Kozik, Andrzej Krokhin, Konstantin Makarychev, Yury Makarychev, Jakub Oprsal
    Academic press:
    SIAM Journal on Computing (rok: 2019, tom: 48(6), strony: 1763–1795), Wydawca: SIAM Publications
    Status:
    Published
    DOI:
    10.1137/18M1163932 - link to the publication
  7. Directed SD(v) terms
    Authors:
    Marcin Kozik
    Academic press:
    Bulletin of the London Mathematical Society , Wydawca: London Mathematical Society
    Status:
    Submitted
    DOI:
    brak - link to the publication
  8. Maltsev conditions for general congruence meet-semidistributive algebras
    Authors:
    Miroslav Olsak
    Academic press:
    Journal of Symbolic Logic , Wydawca: Cambridge University Press
    Status:
    Submitted
    DOI:
    brak - link to the publication
  9. Loop conditions for strongly connected graphs
    Authors:
    Miroslav Olsak
    Academic press:
    International Journal of Algebra and Computation (rok: 2020, tom: 30(03), strony: 467-499), Wydawca: WORLD SCIENTIFIC PUBL
    Status:
    Published
    DOI:
    10.1142/S0218196720500083 - link to the publication
  1. Dichotomy for symmetric Boolean PCSPs
    Authors:
    Miron Ficak, Marcin Kozik, Miroslav Olsak, Szymon Stankiewicz
    Conference:
    46th International Colloquium on Automata, Languages and Programming (ICALP 2019) (rok: 2019, ), Wydawca: Leibniz International Proceedings in Informatics
    Data:
    konferencja 8-9.06.2019
    Status:
    Published
    DOI:
    link to the publication
  2. Robust algorithms with polynomial loss for near-unanimity CSPs
    Authors:
    Victor Dalmau, Marcin Kozik, Andrei Krokhin, Konstantin Makarychev, Yuri Makarychev, Jakub Oprsal
    Conference:
    Twenty-Eighth Annual ACM-SIAM Symposium on Discrete Algorithms (SODA) (rok: 2016, ), Wydawca: SIAM
    Data:
    konferencja 10-12.01.2016
    Status:
    Published
    DOI:
    link to the publication
  3. Sensitive Instances of the Constraint Satisfaction Problem
    Authors:
    Libor Barto, Marcin Kozik, Johnson Tan, Matt Valeriote
    Conference:
    47th International Colloquium on Automata, Languages, and Programming (ICALP 2020) (rok: 2020, ), Wydawca: Schloss Dagstuhl--Leibniz-Zentrum f{"u}r Informatik
    Data:
    konferencja 8-11.07.2020
    Status:
    Published
    DOI:
    link to the publication
  1. Absorption in Universal Algebra and CSP
    Authors:
    Libor Barto, Marcin Kozik
    Book:
    The Constraint Satisfaction Problem: Complexity and Approximability (rok: 2017, tom: 7, strony: 45-77), Wydawca: Shloss Dagstuhl
    Status:
    Published
    DOI:
    link to the publication

O Narodowym Centrum Nauki

Finansowanie nauki

Współpraca zagraniczna

Centrum prasowe

Deklaracja dostępności
Przetwarzanie danych osobowych
Polityka cookies

Partnerzy