All reports by Author Joshua Brakensiek:

__
TR17-141
| 19th September 2017
__

Joshua Brakensiek, Venkatesan Guruswami#### A Family of Dictatorship Tests with Perfect Completeness for 2-to-2 Label Cover

__
TR17-080
| 1st May 2017
__

Joshua Brakensiek, Venkatesan Guruswami#### The Quest for Strong Inapproximability Results with Perfect Completeness

__
TR16-183
| 16th November 2016
__

Joshua Brakensiek, Venkatesan Guruswami#### Promise Constraint Satisfaction: Algebraic Structure and a Symmetric Boolean Dichotomy

Revisions: 1

__
TR16-029
| 7th March 2016
__

Joshua Brakensiek, Venkatesan Guruswami#### New hardness results for graph and hypergraph colorings

__
TR15-116
| 21st July 2015
__

Joshua Brakensiek, Venkatesan Guruswami, Samuel Zbarsky#### Efficient Low-Redundancy Codes for Correcting Multiple Deletions

Joshua Brakensiek, Venkatesan Guruswami

We give a family of dictatorship tests with perfect completeness and low-soundness for 2-to-2 constraints. The associated 2-to-2 conjecture has been the basis of some previous inapproximability results with perfect completeness. However, evidence towards the conjecture in the form of integrality gaps even against weak semidefinite programs has been elusive. ... more >>>

Joshua Brakensiek, Venkatesan Guruswami

The Unique Games Conjecture (UGC) has pinned down the approximability of all constraint satisfaction problems (CSPs), showing that a natural semidefinite programming relaxation offers the optimal worst-case approximation ratio for any CSP. This elegant picture, however, does not apply for CSP instances that are perfectly satisfiable, due to the imperfect ... more >>>

Joshua Brakensiek, Venkatesan Guruswami

A classic result due to Schaefer (1978) classifies all constraint satisfaction problems (CSPs) over the Boolean domain as being either in $\mathsf{P}$ or NP-hard. This paper considers a promise-problem variant of CSPs called PCSPs. A PCSP over a finite set of pairs of constraints $\Gamma$ consists of a pair $(\Psi_P, ... more >>>

Joshua Brakensiek, Venkatesan Guruswami

Finding a proper coloring of a $t$-colorable graph $G$ with $t$ colors is a classic NP-hard problem when $t\ge 3$. In this work, we investigate the approximate coloring problem in which the objective is to find a proper $c$-coloring of $G$ where $c \ge t$. We show that for all ... more >>>

Joshua Brakensiek, Venkatesan Guruswami, Samuel Zbarsky

We consider the problem of constructing binary codes to recover from $k$-bit deletions with efficient encoding/decoding, for a fixed $k$. The single deletion case is well understood, with the Varshamov-Tenengolts-Levenshtein code from 1965 giving an asymptotically optimal construction with $\approx 2^n/n$ codewords of length $n$, i.e., at most $\log n$ ... more >>>