Document Search Results

Approximate graph colouring and the hollow shadow. (English) Zbl 07844617

Saha, Barna (ed.) et al., Proceedings of the 55th annual ACM SIGACT symposium on theory of computing, STOC ’23, Orlando, FL, USA, June 20–23, 2023. New York, NY: Association for Computing Machinery (ACM). 623-631 (2023).

MSC: 68Qxx

Cite Review PDF

Full Text: DOI

Brakensiek, Joshua; Guruswami, Venkatesan; Sandeep, Sai

SDPs and robust satisfiability of promise CSP. (English) Zbl 07844616

Saha, Barna (ed.) et al., Proceedings of the 55th annual ACM SIGACT symposium on theory of computing, STOC ’23, Orlando, FL, USA, June 20–23, 2023. New York, NY: Association for Computing Machinery (ACM). 609-622 (2023).

MSC: 68Qxx

Cite Review PDF

Full Text: DOI arXiv

Krokhin, Andrei; Opršal, Jakub; Wrochna, Marcin; Živný, Stanislav

Topology and adjunction in promise constraint satisfaction. (English) Zbl 07672224

SIAM J. Comput. 52, No. 1, 38-79 (2023).

MSC: 68Q17 68Q25 68R05 05C15

Cite Review PDF

Full Text: DOI arXiv

Ciardo, Lorenzo; Živný, Stanislav

CLAP: a new algorithm for promise CSPs. (English) Zbl 07672223

SIAM J. Comput. 52, No. 1, 1-37 (2023).

MSC: 68Q25 68R01 90C05

Cite Review PDF

Full Text: DOI arXiv

Nakajima, Tamio-Vesa; Živný, Stanislav

Linearly ordered colourings of hypergraphs. (English) Zbl 07870338

Bojańczyk, Mikołaj (ed.) et al., 49th EATCS international conference on automata, languages, and programming, ICALP 2022, Paris, France, July 4–8, 2022. Wadern: Schloss Dagstuhl – Leibniz-Zentrum für Informatik. LIPIcs – Leibniz Int. Proc. Inform. 229, Article 128, 18 p. (2022).

MSC: 68Nxx 68Qxx

Cite Review PDF

Full Text: DOI arXiv

Kazda, Alexandr; Mayr, Peter; Zhuk, Dmitriy

Small promise CSPs that reduce to large CSPs. (English) Zbl 07596573

Log. Methods Comput. Sci. 18, No. 3, Paper No. 25, 14 p. (2022).

MSC: 68R07 03B70 08A70

Cite Review PDF

Full Text: DOI arXiv

OA License

Asimi, Kristina; Barto, Libor

Finitely tractable promise constraint satisfaction problems. (English) Zbl 07724184

Bonchi, Filippo (ed.) et al., 46th international symposium on mathematical foundations of computer science, MFCS 2021, August 23–27, 2021, Tallinn, Estonia. Wadern: Schloss Dagstuhl – Leibniz-Zentrum für Informatik. LIPIcs – Leibniz Int. Proc. Inform. 202, Article 11, 16 p. (2021).

MSC: 68Qxx

Cite Review PDF

Full Text: DOI arXiv

Barto, Libor; Bulín, Jakub; Krokhin, Andrei; Opršal, Jakub

Algebraic approach to promise constraint satisfaction. (English) Zbl 1499.68140

J. ACM 68, No. 4, Article No. 28, 66 p. (2021).

MSC: 68Q25 05C15 08A70 68Q17

Cite Review PDF

Full Text: DOI

Brakensiek, Joshua; Guruswami, Venkatesan

Promise constraint satisfaction: algebraic structure and a symmetric Boolean dichotomy. (English) Zbl 1494.68094

SIAM J. Comput. 50, No. 6, 1663-1700 (2021).

MSC: 68Q25 08A70 68R07 68W25

Cite Review PDF

Full Text: DOI arXiv

Brandts, Alex; Wrochna, Marcin; Živný, Stanislav

The complexity of promise SAT on non-Boolean domains. (English) Zbl 1495.68157

ACM Trans. Comput. Theory 13, No. 4, Article No. 26, 20 p. (2021).

MSC: 68R07 08A70 68Q17 68Q25

Cite Review PDF

Full Text: DOI arXiv

Viola, Caterina; Živný, Stanislav

The combined basic LP and affine IP relaxation for promise VCSPs on infinite domains. (English) Zbl 07475101

ACM Trans. Algorithms 17, No. 3, Article No. 21, 23 p. (2021).

MSC: 68R07 68Q27 90C10 90C27

Cite Review PDF

Full Text: DOI arXiv Link

Deng, Guofeng; Sai, Ezzeddine El; Manders, Trevor; Mayr, Peter; Nakkirt, Poramate; Sparks, Athena

Sandwiches for promise constraint satisfaction. (English) Zbl 1509.68100

Algebra Univers. 82, No. 1, Paper No. 15, 9 p. (2021).

MSC: 68Q25 08A70 68R07 68Q17

Cite Review PDF

Full Text: DOI arXiv

Viola, Caterina; Živný, Stanislav

The combined basic LP and affine IP relaxation for promise VCSPs on infinite domains. (English) Zbl 07559456

Esparza, Javier (ed.) et al., 45th international symposium on mathematical foundations of computer science, MFCS 2020, August 25–26, 2020, Prague, Czech Republic. Proceedings. Wadern: Schloss Dagstuhl – Leibniz Zentrum für Informatik. LIPIcs – Leibniz Int. Proc. Inform. 170, Article 85, 15 p. (2020).

MSC: 68R07 68Q27 90C10 90C27

Cite Review PDF

Full Text: DOI

Ficak, Miron; Kozik, Marcin; Olšák, Miroslav; Stankiewicz, Szymon

Dichotomy for symmetric Boolean PCSPs. (English) Zbl 07561550

Baier, Christel (ed.) et al., 46th international colloquium on automata, languages, and programming, ICALP 2019, Patras, Greece, July 9–12, 2019. Proceedings. Wadern: Schloss Dagstuhl – Leibniz-Zentrum für Informatik. LIPIcs – Leibniz Int. Proc. Inform. 132, Article 57, 12 p. (2019).

MSC: 68Nxx 68Qxx

Cite Review PDF

Full Text: DOI arXiv

Barto, Libor

Algebraic theory of promise constraint satisfaction problems, first steps. (English) Zbl 1534.68074

Gąsieniec, Leszek Antoni (ed.) et al., Fundamentals of computation theory. 22nd international symposium, FCT 2019, Copenhagen, Denmark, August 12–14, 2019. Proceedings. Cham: Springer. Lect. Notes Comput. Sci. 11651, 3-17 (2019).

MSC: 68Q25 08A70 68R07

Cite Review PDF

Full Text: DOI arXiv

Bulín, Jakub; Krokhin, Andrei; Opršal, Jakub

Algebraic approach to promise constraint satisfaction. (English) Zbl 1433.68271

Charikar, Moses (ed.) et al., Proceedings of the 51st annual ACM SIGACT symposium on theory of computing, STOC ’19, Phoenix, AZ, USA, June 23–26, 2019. New York, NY: Association for Computing Machinery (ACM). 602-613 (2019).

MSC: 68R07 05C15 68Q17 68Q25

Cite Review PDF

Full Text: DOI arXiv

Found 16 Documents (Results 1–16)

Approximate graph colouring and the hollow shadow. (English) Zbl 07844617

SDPs and robust satisfiability of promise CSP. (English) Zbl 07844616

Topology and adjunction in promise constraint satisfaction. (English) Zbl 07672224

CLAP: a new algorithm for promise CSPs. (English) Zbl 07672223

Linearly ordered colourings of hypergraphs. (English) Zbl 07870338

Small promise CSPs that reduce to large CSPs. (English) Zbl 07596573

Finitely tractable promise constraint satisfaction problems. (English) Zbl 07724184

Algebraic approach to promise constraint satisfaction. (English) Zbl 1499.68140

Promise constraint satisfaction: algebraic structure and a symmetric Boolean dichotomy. (English) Zbl 1494.68094

The complexity of promise SAT on non-Boolean domains. (English) Zbl 1495.68157

The combined basic LP and affine IP relaxation for promise VCSPs on infinite domains. (English) Zbl 07475101

Sandwiches for promise constraint satisfaction. (English) Zbl 1509.68100

The combined basic LP and affine IP relaxation for promise VCSPs on infinite domains. (English) Zbl 07559456

Dichotomy for symmetric Boolean PCSPs. (English) Zbl 07561550

Algebraic theory of promise constraint satisfaction problems, first steps. (English) Zbl 1534.68074

Algebraic approach to promise constraint satisfaction. (English) Zbl 1433.68271

Filter Results by …

Document Type

Author

Serial

Year of Publication

Main Field