Algebraic theory for CSP (tractability, approximation and optimization)

2014/13/B/ST6/01812

Keywords

Descriptors

  • ST6_4: Metody formalne, teoretyczne podstawy informatyki w tym informatyka teoretyczna
  • ST6_6: Algorytmika, algorytmy równoległe, rozproszone i sieciowe, algorytmiczna teoria gier
  • ST1_18: Zastosowania matematyki w innych naukach

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

Other projects carried out by the institution »

Principal investigator (from the host institution)

dr hab. Marcin Andrzej 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
2015-02-18
Project end date
2019-02-17
Project duration
48 months (the same as in the proposal)
Project status
Project settled

Equipment purchased [PL]

  1. Laptop. Cost: 8 000 PLN

Information in the final report

Publication in academic press/journals (6)

  1. Loop conditions for strongly connected graphs

    Authors:
    Miroslav Olsak
    Academic press:
    International Journal of Algebra and Computation (year: 2020, volume: 30(03), pages: 467-499), Publisher: WORLD SCIENTIFIC PUBL
    Status:
    Published
    DOI:
    10.1142/S0218196720500083 – link to the publication
  2. Local loop lemma

    Authors:
    Miroslav Olsak
    Academic press:
    Algebra Universalis (year: 2020, volume: 81, pages: article no. 14), Publisher: Springer
    Status:
    Published
    DOI:
    10.1007/s00012-020-0644-y – link to the publication
  3. 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 (year: 2019, volume: 48(6), pages: 1763–1795), Publisher: SIAM Publications
    Status:
    Published
    DOI:
    10.1137/18M1163932 – link to the publication
  4. Taylor's modularity conjecture and related problems for idempotent varieties

    Authors:
    Jakub Oprsal
    Academic press:
    Order (year: 2018, volume: 35, pages: 433-460), Publisher: Springer
    Status:
    Published
    DOI:
    10.1007/s11083-017-9441-4 – link to the publication
  5. The subpower membership problem for semigroups

    Authors:
    Andrei Bulatov, Marcin Kozik, Peter Mayr, Markus Steindl
    Academic press:
    International Journal of Algebra and Computation (year: 2016, volume: 26, pages: 1435-1451), Publisher: World Scientific
    Status:
    Published
    DOI:
    10.1142/S0218196716500612 – link to the publication
  6. Solving CSPs using weak local consistency

    Authors:
    Marcin Kozik
    Status:
    Accepted for publication

Articles in post-conference publications (3)

  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) (year: 2019, pages: 57:1-57:12), Publisher: Leibniz International Proceedings in Informatics
    Date:
    conference 8-9.06.2019
    Status:
    Published
    DOI:
    link to the publication
  2. 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) (year: 2020, pages: 110:1-110:18), Publisher: Schloss Dagstuhl--Leibniz-Zentrum f{u}r Informatik
    Date:
    conference 8-11.07.2020
    Status:
    Published
    DOI:
    link to the publication
  3. 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) (year: 2016, pages: 340-357), Publisher: SIAM
    Date:
    conference 10-12.01.2016
    Status:
    Published
    DOI:
    link to the publication

Book publications / chapters in book publications (1)

  1. Absorption in Universal Algebra and CSP

    Authors:
    Libor Barto, Marcin Kozik
    Book:
    The Constraint Satisfaction Problem: Complexity and Approximability (year: 2017, volume: 7, pages: 45-77), Publisher: Shloss Dagstuhl
    Status:
    Published
    DOI:
    link to the publication

« New search

Graphic design and implementation: Jakub Piotrowski