All reports by Author Jakub Opršal:

__
TR20-040
| 25th March 2020
__

Andrei Krokhin, Jakub Opršal, Marcin Wrochna, Stanislav Zivny#### Topology and adjunction in promise constraint satisfaction

Revisions: 1

__
TR19-092
| 9th July 2019
__

Venkatesan Guruswami, Jakub Opršal, Sai Sandeep#### Revisiting Alphabet Reduction in Dinur's PCP

__
TR19-053
| 5th April 2019
__

Andrei Krokhin, Jakub Opršal#### The complexity of 3-colouring $H$-colourable graphs

Andrei Krokhin, Jakub Opršal, Marcin Wrochna, Stanislav Zivny

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

Venkatesan Guruswami, Jakub Opršal, Sai Sandeep

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

Andrei Krokhin, Jakub Opršal

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