Research output per year
Research output per year
- 10 results
Search results
-
2024
A topological proof of the Hell–Nešetřil dichotomy
Meyer, S. & Opršal, J., 4 Oct 2024, (Accepted/In press) Proceedings of the 2025 Annual ACM-SIAM Symposium on Discrete Algorithms (SODA). Society for Industrial and Applied Mathematics (SIAM), (Proceedings).Research output: Chapter in Book/Report/Conference proceeding › Conference contribution
Open Access -
Hardness of Linearly Ordered 4-Colouring of 3-Colourable 3-Uniform Hypergraphs
Filakovský, M., Nakajima, T.-V., Opršal, J., Tasinato, G. & Wagner, U., 11 Mar 2024, 41st International Symposium on Theoretical Aspects of Computer Science (STACS 2024). Beyersdorff , O., Kanté, M. M., Kupferman, O. & Lokshtanov, D. (eds.). Dagstuhl, Germany: Schloss Dagstuhl - Leibniz-Zentrum für Informatik , p. 34:1-34:19 19 p. 34. (Leibniz International Proceedings in Informatics (LIPIcs); vol. 289).Research output: Chapter in Book/Report/Conference proceeding › Conference contribution
Open AccessFile20 Downloads (Pure) -
Local consistency as a reduction between constraint satisfaction problems
Dalmau, V. & Opršal, J., 8 Jul 2024, LICS '24: Proceedings of the 39th Annual ACM/IEEE Symposium on Logic in Computer Science. Association for Computing Machinery , 15 p. 29Research output: Chapter in Book/Report/Conference proceeding › Conference contribution
Open AccessFile50 Downloads (Pure) -
Right-Adjoints for Datalog Programs
ten Cate, B., Dalmau, V. & Opršal, J., 14 Mar 2024, 27th International Conference on Database Theory (ICDT 2024). Cormode, G. & Shekelyan, M. (eds.). Schloss Dagstuhl, 10. (Leibniz International Proceedings in Informatics, LIPIcs; vol. 290).Research output: Chapter in Book/Report/Conference proceeding › Conference contribution
Open AccessFile29 Downloads (Pure) -
2020
Revisiting alphabet reduction in Dinur's PCP
Guruswami, V., Opršal, J. & Sandeep, S., 2020, Leibniz International Proceedings in Informatics, LIPIcs.Research output: Chapter in Book/Report/Conference proceeding › Conference contribution
-
2019
Algebraic approach to promise constraint satisfaction
Bulín, J., Krokhin, A. & Opršal, J., 23 Jun 2019, STOC 2019: Proceedings of the 51st Annual ACM SIGACT Symposium on Theory of Computing. Charikar, M. & Cohen, E. (eds.). Association for Computing Machinery (ACM), p. 602–613 12 p.Research output: Chapter in Book/Report/Conference proceeding › Conference contribution
Open Access -
The complexity of 3-colouring H-colourable graphs
Krokhin, A. & Oprsal, J., 2019, Proceedings - Annual IEEE Symposium on Foundations of Computer Science, FOCS.Research output: Chapter in Book/Report/Conference proceeding › Conference contribution
-
Topology is relevant (in a dichotomy conjecture for infinite-domain constraint satisfaction problems)
Bodirsky, M., Mottet, A., Olšák, M., Oprsal, J., Pinsker, M. & Willard, R., 2019, Proceedings - Symposium on Logic in Computer Science.Research output: Chapter in Book/Report/Conference proceeding › Conference contribution
-
2017
Robust algorithms with polynomial loss for near-unanimity CSPs
Dalmau, V., Kozik, M., Krokhin, A., Makarychev, K., Makarychev, Y. & Opršal, J., 4 Jan 2017, Proceedings of the Twenty-Eighth Annual ACM-SIAM Symposium on Discrete Algorithms. Klein, P. N. (ed.). Society for Industrial and Applied Mathematics (SIAM)Research output: Chapter in Book/Report/Conference proceeding › Conference contribution
-
2014
Universal Lyndon words
Carpi, A., Fici, G., Holub, Š., Opršal, J. & Sciortino, M., 2014, Mathematical Foundations of Computer Science 2014 - 39th International Symposium, MFCS 2014, Proceedings. PART 1 ed. Springer Verlag, p. 135-146 12 p. (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); vol. 8634 LNCS, no. PART 1).Research output: Chapter in Book/Report/Conference proceeding › Conference contribution