Projects funded by the NCN

Information on the principal investigator and host institution

Information of the project and the call

Keywords

Equipment

Delete all

Numerical and structural invariants in algebra, logic and constraint satisfaction problems

2014/14/A/ST6/00138

Keywords:

decidability classification theory constraint satisfaction

Descriptors:

  • ST6_4: Formal methods, foundations of computer science, including theoretical computer science, quantum algorithms
  • ST1_15: Mathematical aspects of computer science
  • ST1_1: Logic and foundations

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

prof. Paweł Idziak 

Number of co-investigators in the project: 7

Call: MAESTRO 6 - announced on 2014-06-16

Amount awarded: 2 570 854 PLN

Project start date (Y-m-d): 2015-10-01

Project end date (Y-m-d): 2022-09-30

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

Project status: Project settled

Equipment purchased [PL]

  1. Laptopy (2 szt.) (14 528 PLN)

Information in the final report

  • Publication in academic press/journals (6)
  • Articles in post-conference publications (17)
  1. A new lower bound for the on-line coloring of intervals with bandwidth
    Authors:
    Patryk Mikos
    Academic press:
    Theoretical Computer Science (rok: 2018, tom: 708, strony: 96-100), Wydawca: ELSEVIER
    Status:
    Published
    DOI:
    10.029 - link to the publication
  2. Satisfiability in multi-valued circuits
    Authors:
    Pawel M. Idziak and Jacek Krzaczkowski
    Academic press:
    SIAM Journal of Computing (rok: 2022, tom: 51(3), strony: 337-378), Wydawca: SIAM - Society for Industrial and Applied Mathematics
    Status:
    Published
    DOI:
    10.1137/18M1220194 - link to the publication
  3. The complexity of counting quantifiers on equality languages
    Authors:
    Barnaby Martin, András Pongrácz, Michał Wrona
    Academic press:
    Theoretical Computer Science (rok: 2017, tom: 670, strony: 56-67), Wydawca: Elsevier
    Status:
    Published
    DOI:
    10.1016/j.tcs.2017.01.022 - link to the publication
  4. The Complexity of Minimal Inference Problem for Conservative Constraint Languages
    Authors:
    Michał Wrona
    Academic press:
    ACM Transactions on Computational Logic (rok: 2019, tom: 20(2), strony: 12785), Wydawca: ACM - Association for Computing Machinery
    Status:
    Published
    DOI:
    10.1145/3301410 - link to the publication
  5. Efficient Enumeration of Non-isomorphic Interval Graphs
    Authors:
    Patryk Mikos
    Academic press:
    Discrete Mathematics and Theoretical Computer Science (rok: 2021, tom: 23, strony: bd), Wydawca: episciences.org
    Status:
    Published
    DOI:
    10.46298/dmtcs.6164 - link to the publication
  6. Equation satisfiability in solvable groups
    Authors:
    Paweł Idziak, Piotr Kawałek, Jacek Krzaczkowski and Armin Weiß
    Academic press:
    Theory of Computing Systems (rok: 2022, tom: 267, strony: N/A), Wydawca: Springer Verlag
    Status:
    Published
    DOI:
    10.1007/s00224-022-10082-z - link to the publication
  1. Expressive power, satisfiability and equivalence of circuits over nilpotent algebras
    Authors:
    Paweł Idziak, Piotr Kawałek, Jacek Krzaczkowski
    Conference:
    MFCS - International Symposium on Mathematical Foundations of Computer Science (rok: 2018, ), Wydawca: LIPICS - Schloss Dagstuhl – Leibniz-Zentrum für Informatik, Dagstuhl Publishing, Germany
    Data:
    konferencja August 27-31, 2018, Liverpool (UK)
    Status:
    Published
    DOI:
    link to the publication
  2. Relational Width of First-Order Expansions of Homogeneous Graphs with Bounded Strict Width
    Authors:
    Michał Wrona
    Conference:
    STACS - 37th International Symposium on Theoretical Aspects of Computer Science (rok: 2020, ), Wydawca: Leibniz International Proceedings in Informatics Schloss Dagstuhl – Leibniz-Zentrum für Informatik, Dagstuhl Publishing, Germany
    Data:
    konferencja March 10 — 13, 2020
    Status:
    Published
  3. Satisfiability in multi-valued circuits
    Authors:
    Paweł Idziak, Jacek Krzaczkowski
    Conference:
    LICS - ACM/IEEE Symposium on Logic in Computer Science (rok: 2018, ), Wydawca: Association for Computing Machinery.
    Data:
    konferencja July 9–12, 2018, Oxford, United Kingdom.
    Status:
    Published
    DOI:
    link to the publication
  4. Solving Equations–kith and kin
    Authors:
    Paweł Idziak, Jacek Krzaczkowski
    Conference:
    Algebras and Lattices in Hawai'i (rok: 2018, ), Wydawca: University of Hawaii
    Data:
    konferencja May 22–24, 2018, University of Hawai'i at Manoa
    Status:
    Published
    DOI:
    link to the publication
  5. The complexity of minimal inference problem for conservative constraint languages
    Authors:
    Michał Wrona
    Conference:
    LICS - ACM/IEEE Symposium on Logic in Computer Science (rok: 2017, ), Wydawca: IEEE Computer Society
    Data:
    konferencja June 20-23, 2017
    Status:
    Published
  6. Satisfiability Problems for Finite Groups
    Authors:
    Paweł Idziak, Piotr Kawałek, Jacek Krzaczkowski and Armin Weiß
    Conference:
    49th International Colloquium on Automata, Languages, and Programming (ICALP 2022) (rok: 2022, ), Wydawca: Schloss Dagstuhl – Leibniz-Zentrum für Informatik, Dagstuhl Publishing, Germany
    Data:
    konferencja July 4-8, 2022
    Status:
    Published
    DOI:
    link to the publication
  7. Sensitive Instances of the Constraint Satisfaction Problem
    Authors:
    Libor Barto, Marcin Kozik, Johnson Tan, Matthew Valeriote
    Conference:
    47th International Colloquium on Automata, Languages, and Programming (ICALP 2020) (rok: 2020, ), Wydawca: Schloss Dagstuhl – Leibniz-Zentrum für Informatik, Dagstuhl Publishing, Germany
    Data:
    konferencja July 8-11, 2020; Saarbrücken, Germany
    Status:
    Published
  8. Even faster algorithms for CSAT over supernilpotent algebras
    Authors:
    Piotr Kawałek, Jacek Krzaczkowski
    Conference:
    MFCS - Mathematical Foundations of Computer Science (rok: 2020, ), Wydawca: Leibniz International Proceedings in Informatics Schloss Dagstuhl – Leibniz-Zentrum für Informatik, Dagstuhl Publishing, Germany
    Data:
    konferencja August 24-28, 2020
    Status:
    Published
  9. Minimal Inference Problem Over Finite Domains: The Landscape of Complexity
    Authors:
    Michał Wrona
    Conference:
    Logic Programming and Nonmonotonic Reasoning (rok: 2017, ), Wydawca: Springer
    Data:
    konferencja July 3-6, 2017
    Status:
    Published
  10. Online Coloring of Short Intervals
    Authors:
    Joanna Chybowska-Sokól, Grzegorz Gutowski, Konstanty Junosza-Szaniawski, Patryk Mikos, Adam Polak
    Conference:
    Approximation, randomization, and combinatorial optimization : algorithms and techniques (APPROX/RANDOM 2020) (rok: 2020, ), Wydawca: Dagstuhl : Schloss Dagstuhl-Leibniz-Zentrum fuer Informatik
    Data:
    konferencja August 17-19, 2020
    Status:
    Published
  11. Satisfiability of Circuits and Equations Over Finite Malcev Algebras
    Authors:
    Paweł Idziak, Piotr Kawałek and Jacek Krzaczkowski
    Conference:
    39th International Symposium on Theoretical Aspects of Computer Science (STACS 2022) (rok: 2022, ), Wydawca: LIPICS - Leibniz International Proceedings in Informatics Schloss Dagstuhl – Leibniz-Zentrum für Informatik, Dagstuhl Publishing, Germany
    Data:
    konferencja March 15-18, 2022
    Status:
    Published
  12. The complexity of counting quantifiers on equality languages
    Authors:
    Barnaby Martin, András Pongrácz, Michał Wrona
    Conference:
    12th Conference on Computability in Europe, Paris, France (rok: 2016, ), Wydawca: Springer
    Data:
    konferencja 27.06-1.07.2016
    Status:
    Published
    DOI:
    link to the publication
  13. Complexity of Modular Circuits
    Authors:
    Paweł Idziak, Piotr Kawałek, Jacek Krzaczkowski
    Conference:
    37th Annual ACM/IEEE Symposium on Logic in Computer Science (LICS 2022) (rok: 2022, ), Wydawca: Association for Computing Machinery (ACM)
    Data:
    konferencja August 2-5, 2022
    Status:
    Published
  14. Intermediate problems in modular circuits satisfiability
    Authors:
    Paweł Idziak, Piotr Kawałek, Jacek Krzaczkowski
    Conference:
    35th Annual ACM/IEEE Symposium on Logic in Computer Science (2020) (rok: 2020, ), Wydawca: Association for Computing Machinery (ACM)
    Data:
    konferencja July 8-11, 2020, Saarbrücken, Germany
    Status:
    Published
  15. Lower Bounds for On-line Interval Coloring with Vector and Cardinality Constraints
    Authors:
    Grzegorz Gutowski, Patryk Mikos
    Conference:
    SOFSEM 2017: Theory and Practice of Computer Science, Limerick, Ireland (rok: 2017, ), Wydawca: Springer
    Data:
    konferencja 16-20.01.2017
    Status:
    Published
    DOI:
    link to the publication
  16. Minimal Taylor Algebras as a Common Framework for the Three Algebraic Approaches to the CSP
    Authors:
    Libor Barto, Zarathustra Brady, Andrei Bulatov, Marcin Kozik, Dmitriy Zhuk
    Conference:
    LICS - 36th Annual ACM/IEEE Symposium on Logic in Computer Science (2021) (rok: 2021, ), Wydawca: Association for Computing Machinery (ACM)
    Data:
    konferencja 29 June – 02 July 2021
    Status:
    Published
  17. On The Relational Width of First-Order Expansions of Finitely Bounded Homogeneous Binary Cores with Bounded Strict Width∗
    Authors:
    Michał Wrona
    Conference:
    35th Annual ACM/IEEE Symposium on Logic in Computer Science (2020) (rok: 2020, ), Wydawca: Association for Computing Machinery (ACM)
    Data:
    konferencja July 8-11, 2020, Saarbrücken, Germany
    Status:
    Published

O Narodowym Centrum Nauki

Finansowanie nauki

Współpraca zagraniczna

Centrum prasowe

Deklaracja dostępności
Przetwarzanie danych osobowych
Polityka cookies

Partnerzy