Weizmann Logo
ECCC
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style



REPORTS > AUTHORS > JAKUB OPRŠAL:
All reports by Author Jakub Opršal:

TR22-126 | 12th September 2022
Andrei Krokhin, Jakub Opršal

An Invitation to the Promise Constraint Satisfaction Problem

The study of the complexity of the constraint satisfaction problem (CSP), centred around the Feder-Vardi Dichotomy Conjecture, has been very prominent in the last two decades. After a long concerted effort and many partial results, the Dichotomy Conjecture has been proved in 2017 independently by Bulatov and Zhuk.

At about ... more >>>


TR20-040 | 25th March 2020
Andrei Krokhin, Jakub Opršal, Marcin Wrochna, Stanislav Zivny

Topology and adjunction in promise constraint satisfaction

Revisions: 1

The approximate graph colouring problem concerns colouring a $k$-colourable
graph with $c$ colours, where $c\geq k$. This problem naturally generalises
to promise graph homomorphism and further to promise constraint satisfaction
problems. Complexity analysis of all these problems is notoriously difficult.
In this paper, we introduce ... more >>>


TR19-092 | 9th July 2019
Venkatesan Guruswami, Jakub Opršal, Sai Sandeep

Revisiting Alphabet Reduction in Dinur's PCP

Dinur's celebrated proof of the PCP theorem alternates two main steps in several iterations: gap amplification to increase the soundness gap by a large constant factor (at the expense of much larger alphabet size), and a composition step that brings back the alphabet size to an absolute constant (at the ... more >>>


TR19-053 | 5th April 2019
Andrei Krokhin, Jakub Opršal

The complexity of 3-colouring $H$-colourable graphs

We study the complexity of approximation on satisfiable instances for graph homomorphism problems. For a fixed graph $H$, the $H$-colouring problem is to decide whether a given graph has a homomorphism to $H$. By a result of Hell and Nešet?il, this problem is NP-hard for any non-bipartite graph $H$. In ... more >>>




ISSN 1433-8092 | Imprint