All reports by Author Joshua Brakensiek:

__
TR21-026
| 23rd February 2021
__

Joshua Brakensiek, Venkatesan Guruswami, Sai Sandeep#### Conditional Dichotomy of Boolean Ordered Promise CSPs

__
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

__
TR19-054
| 9th April 2019
__

Joshua Brakensiek, Venkatesan Guruswami#### Bridging between 0/1 and Linear Programming via Random Walks

__
TR19-013
| 31st January 2019
__

Joshua Brakensiek, Sivakanth Gopi, Venkatesan Guruswami#### CSPs with Global Modular Constraints: Algorithms and Hardness via Polynomial Representations

__
TR18-059
| 6th April 2018
__

Joshua Brakensiek, Venkatesan Guruswami#### Combining LPs and Ring Equations via Structured Polymorphisms

Revisions: 1

__
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: 2

__
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

Revisions: 1

Joshua Brakensiek, Venkatesan Guruswami, Sai Sandeep

Promise Constraint Satisfaction Problems (PCSPs) are a generalization of Constraint Satisfaction Problems (CSPs) where each predicate has a strong and a weak form and given a CSP instance, the objective is to distinguish if the strong form can be satisfied vs. even the weak form cannot be satisfied. Since their ... more >>>

Joshua Brakensiek, Venkatesan Guruswami, Marcin Wrochna, Stanislav Zivny

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

Joshua Brakensiek, Venkatesan Guruswami

Under the Strong Exponential Time Hypothesis, an integer linear program with $n$ Boolean-valued variables and $m$ equations cannot be solved in $c^n$ time for any constant $c < 2$. If the domain of the variables is relaxed to $[0,1]$, the associated linear program can of course be solved in polynomial ... more >>>

Joshua Brakensiek, Sivakanth Gopi, Venkatesan Guruswami

We study the complexity of Boolean constraint satisfaction problems (CSPs) when the assignment must have Hamming weight in some congruence class modulo $M$, for various choices of the modulus $M$. Due to the known classification of tractable Boolean CSPs, this mainly reduces to the study of three cases: 2SAT, HornSAT, ... more >>>

Joshua Brakensiek, Venkatesan Guruswami

Promise CSPs are a relaxation of constraint satisfaction problems where the goal is to find an assignment satisfying a relaxed version of the constraints. Several well known problems can be cast as promise CSPs including approximate graph and hypergraph coloring, discrepancy minimization, and interesting variants of satisfiability. Similar to CSPs, ... more >>>

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