Weizmann Logo
ECCC
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style



REPORTS > AUTHORS > JOSHUA BRAKENSIEK:
All reports by Author Joshua Brakensiek:

TR21-026 | 23rd February 2021
Joshua Brakensiek, Venkatesan Guruswami, Sai Sandeep

Conditional Dichotomy of Boolean Ordered Promise CSPs

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


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


TR19-054 | 9th April 2019
Joshua Brakensiek, Venkatesan Guruswami

Bridging between 0/1 and Linear Programming via Random Walks

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


TR19-013 | 31st January 2019
Joshua Brakensiek, Sivakanth Gopi, Venkatesan Guruswami

CSPs with Global Modular Constraints: Algorithms and Hardness via Polynomial Representations

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


TR18-059 | 6th April 2018
Joshua Brakensiek, Venkatesan Guruswami

Combining LPs and Ring Equations via Structured Polymorphisms

Revisions: 1

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


TR17-141 | 19th September 2017
Joshua Brakensiek, Venkatesan Guruswami

A Family of Dictatorship Tests with Perfect Completeness for 2-to-2 Label Cover

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


TR17-080 | 1st May 2017
Joshua Brakensiek, Venkatesan Guruswami

The Quest for Strong Inapproximability Results with Perfect Completeness

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


TR16-183 | 16th November 2016
Joshua Brakensiek, Venkatesan Guruswami

Promise Constraint Satisfaction: Algebraic Structure and a Symmetric Boolean Dichotomy

Revisions: 2

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


TR16-029 | 7th March 2016
Joshua Brakensiek, Venkatesan Guruswami

New hardness results for graph and hypergraph colorings

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


TR15-116 | 21st July 2015
Joshua Brakensiek, Venkatesan Guruswami, Samuel Zbarsky

Efficient Low-Redundancy Codes for Correcting Multiple Deletions

Revisions: 1

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




ISSN 1433-8092 | Imprint