Weizmann Logo
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style

All reports by Author Jakub Opršal:

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