Weizmann Logo
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style

Reports tagged with Dichotomy theorem:
TR16-039 | 15th March 2016
Adam Bouland, Laura Mancinska, Xue Zhang

Complexity Classification of Two-Qubit Commuting Hamiltonians

We classify two-qubit commuting Hamiltonians in terms of their computational complexity. Suppose one has a two-qubit commuting Hamiltonian $H$ which one can apply to any pair of qubits, starting in a computational basis state. We prove a dichotomy theorem: either this model is efficiently classically simulable or it allows one ... more >>>

TR19-040 | 19th February 2019
Sanjana Kolisetty, Linh Le, Ilya Volkovich, Mihalis Yannakakis

The Complexity of Finding {$S$}-factors in Regular Graphs

A graph $G$ has an \emph{$S$-factor} if there exists a spanning subgraph $F$ of $G$ such that for all $v \in V: \deg_F(v) \in S$.
The simplest example of such factor is a $1$-factor, which corresponds to a perfect matching in a graph. In this paper we study the computational ... more >>>

TR20-004 | 17th January 2020
Joshua Brakensiek, Venkatesan Guruswami, Marcin Wrochna, Stanislav Zivny

The Power of the Combined Basic LP and Affine Relaxation for Promise CSPs

Revisions: 1

In the field of constraint satisfaction problems (CSP), promise CSPs are an exciting new direction of study. In a promise CSP, each constraint comes in two forms: "strict" and "weak," and in the associated decision problem one must distinguish between being able to satisfy all the strict constraints versus not ... more >>>

ISSN 1433-8092 | Imprint