Jakub Oprsal

39 papers A* 7A 2Journal 28Unranked 2
YearRankTypeTitle / Venue / Authors
2025 J jnl
A categorical perspective on constraint satisfaction: The wonderland of adjunctions.
CoRR
Maximilian Hadek, Tomas Jakl, Jakub Oprsal
2025 A* conf
A topological proof of the Hell-Nešetřil dichotomy.
SODA
Sebastian Meyer, Jakub Oprsal
2025 A* conf
Hardness of 4-Colouring k-Colourable Graphs.
STOC
Sergey Avvakumov, Marek Filakovský, Jakub Oprsal, Gianluca Tasinato, Uli Wagner
2025 J jnl
Hardness of 4-Colourings G-Colourable Graphs.
CoRR
Sergey Avvakumov, Marek Filakovský, Jakub Oprsal, Gianluca Tasinato, Uli Wagner
2024 J jnl
A topological proof of the Hell-Nešetřil dichotomy.
CoRR
Sebastian Meyer, Jakub Oprsal
2024 J jnl
Functors on Relational Structures Which Admit Both Left and Right Adjoints.
SIAM J. Discret. Math.
Víctor Dalmau, Andrei A. Krokhin, Jakub Oprsal
2024 A conf
Hardness of Linearly Ordered 4-Colouring of 3-Colourable 3-Uniform Hypergraphs.
STACS
Marek Filakovský, Tamio-Vesa Nakajima, Jakub Oprsal, Gianluca Tasinato, Uli Wagner
2024 A* conf
Local consistency as a reduction between constraint satisfaction problems.
LICS
Víctor Dalmau, Jakub Oprsal
2024 A conf
Right-Adjoints for Datalog Programs.
ICDT
Balder ten Cate, Víctor Dalmau, Jakub Oprsal
2023 J jnl
Functors on relational structures which admit both left and right adjoints.
CoRR
Víctor Dalmau, Andrei A. Krokhin, Jakub Oprsal
2023 J jnl
Hardness of linearly ordered 4-colouring of 3-colourable 3-uniform hypergraphs.
CoRR
Marek Filakovský, Tamio-Vesa Nakajima, Jakub Oprsal, Gianluca Tasinato, Uli Wagner
2023 J jnl
Local consistency as a reduction between constraint satisfaction problems.
CoRR
Victor Dalmau, Jakub Oprsal
2023 J jnl
Right-Adjoints for Datalog Programs, and Homomorphism Dualities over Restricted Classes.
CoRR
Balder ten Cate, Víctor Dalmau, Jakub Oprsal
2023 J jnl
Topology and Adjunction in Promise Constraint Satisfaction.
SIAM J. Comput.
Andrei A. Krokhin, Jakub Oprsal, Marcin Wrochna, Stanislav Zivný
2022 J jnl
An Invitation to the Promise Constraint Satisfaction Problem.
Electron. Colloquium Comput. Complex.
Andrei A. Krokhin, Jakub Oprsal
2022 J jnl
An invitation to the promise constraint satisfaction problem.
CoRR
Andrei A. Krokhin, Jakub Oprsal
2022 J jnl
An invitation to the promise constraint satisfaction problem.
ACM SIGLOG News
Andrei A. Krokhin, Jakub Oprsal
2021 J jnl
Algebraic Approach to Promise Constraint Satisfaction.
J. ACM
Libor Barto, Jakub Bulín, Andrei A. Krokhin, Jakub Oprsal
2020 — conf
Revisiting Alphabet Reduction in Dinur's PCP.
APPROX-RANDOM
Venkatesan Guruswami, Jakub Oprsal, Sai Sandeep
2020 J jnl
Topology and adjunction in promise constraint satisfaction.
CoRR
Andrei A. Krokhin, Jakub Oprsal, Marcin Wrochna, Stanislav Zivný
2020 J jnl
Topology and adjunction in promise constraint satisfaction.
Electron. Colloquium Comput. Complex.
Andrei A. Krokhin, Jakub Oprsal, Marcin Wrochna, Stanislav Zivný
2020 J jnl
ω-categorical structures avoiding height 1 identities.
CoRR
Manuel Bodirsky, Antoine Mottet, Miroslav Olsák, Jakub Oprsal, Michael Pinsker, Ross Willard
2019 A* conf
Algebraic approach to promise constraint satisfaction.
STOC
Jakub Bulín, Andrei A. Krokhin, Jakub Oprsal
2019 J jnl
Deciding the existence of minority terms.
CoRR
Alexandr Kazda, Jakub Oprsal, Matt Valeriote, Dmitriy Zhuk
2019 J jnl
Revisiting Alphabet Reduction in Dinur's PCP.
Electron. Colloquium Comput. Complex.
Venkatesan Guruswami, Jakub Oprsal, Sai Sandeep
2019 J jnl
Robust Algorithms with Polynomial Loss for Near-Unanimity CSPs.
SIAM J. Comput.
Víctor Dalmau, Marcin Kozik, Andrei A. Krokhin, Konstantin Makarychev, Yury Makarychev, Jakub Oprsal
2019 A* conf
The Complexity of 3-Colouring H-Colourable Graphs.
FOCS
Andrei A. Krokhin, Jakub Oprsal
2019 J jnl
The complexity of 3-colouring
Electron. Colloquium Comput. Complex.
Andrei A. Krokhin, Jakub Oprsal
2019 J jnl
The complexity of 3-colouring H-colourable graphs.
CoRR
Andrei A. Krokhin, Jakub Oprsal
2019 A* conf
Topology is relevant (in a dichotomy conjecture for infinite-domain constraint satisfaction problems).
LICS
Manuel Bodirsky, Antoine Mottet, Miroslav Olsák, Jakub Oprsal, Michael Pinsker, Ross Willard
2019 J jnl
Topology is relevant (in the infinite-domain dichotomy conjecture for constraint satisfaction problems).
CoRR
Manuel Bodirsky, Antoine Mottet, Miroslav Olsák, Jakub Oprsal, Michael Pinsker, Ross Willard
2018 J jnl
Algebraic approach to promise constraint satisfaction.
CoRR
Jakub Bulín, Andrei A. Krokhin, Jakub Oprsal
2018 J jnl
Complexity of term representations of finitary functions.
Int. J. Algebra Comput.
Erhard Aichinger, Nebojsa Mudrinski, Jakub Oprsal
2018 J jnl
Taylor's Modularity Conjecture and Related Problems for Idempotent Varieties.
Order
Jakub Oprsal
2017 A* conf
Robust algorithms with polynomial loss for near-unanimity CSPs.
SODA
Víctor Dalmau, Marcin Kozik, Andrei A. Krokhin, Konstantin Makarychev, Yury Makarychev, Jakub Oprsal
2016 J jnl
Robust algorithms with polynomial loss for near-unanimity CSPs.
CoRR
Víctor Dalmau, Marcin Kozik, Andrei A. Krokhin, Konstantin Makarychev, Yury Makarychev, Jakub Oprsal
2015 J jnl
The wonderland of reflections.
CoRR
Libor Barto, Jakub Oprsal, Michael Pinsker
2014 — conf
Universal Lyndon Words.
MFCS (1)
Arturo Carpi, Gabriele Fici, Stepan Holub, Jakub Oprsal, Marinella Sciortino
2014 J jnl
Universal Lyndon Words.
CoRR
Arturo Carpi, Gabriele Fici, Stepan Holub, Jakub Oprsal, Marinella Sciortino