48 citations · 103 across the 33 of their papers we have counts for
11 papers · 1 filter
Cores Characterize the One-Pass Streaming Complexity of CSPs
Joshua Brakensiek, Aaron Putterman, Amatya Sharma +1
We study the one-pass streaming complexity of CSPs over a fixed finite relation under three natural objectives: , deciding whether all constraints can be satis…
Separating Non-redundancy and Chain Length
Joshua Brakensiek, Venkatesan Guruswami, Aaron Putterman
For a constraint satisfaction problem defined by a relation , its non-redundancy is the size of largest instance (as a function of the number of variables)…
Classification of Non-redundancy of Boolean Predicates of Arity 4
Joshua Brakensiek, Venkatesan Guruswami, Aaron Putterman
Given a constraint satisfaction problem (CSP) predicate , the non-redundancy (NRD) of is maximum-sized instance on variables such that for every clause of…
MAX BISECTION might be harder to approximate than MAX CUT
Joshua Brakensiek, Neng Huang, Aaron Potechin +1
The MAX BISECTION problem seeks a maximum-size cut that evenly divides the vertices of a given undirected graph. An open problem raised by Austrin, Benabbas, and Georgiou is whethe…
Tight approximability of MAX 2-SAT and relatives, under UGC
Joshua Brakensiek, Neng Huang, Uri Zwick
Austrin showed that the approximation ratio obtained by the MAX 2-SAT approximation algorithm of Lewin, Livnat and Zwick (LLZ) is optimal modulo the Unique Ga…
Separating MAX 2-AND, MAX DI-CUT and MAX CUT
Joshua Brakensiek, Neng Huang, Aaron Potechin +1
Assuming the Unique Games Conjecture (UGC), the best approximation ratio that can be obtained in polynomial time for the MAX CUT problem is , obtained…
Conditional Dichotomy of Boolean Ordered Promise CSPs
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 i…
On the Mysteries of MAX NAE-SAT
Joshua Brakensiek, Neng Huang, Aaron Potechin +1
MAX NAE-SAT is a natural optimization problem, closely related to its better-known relative MAX SAT. The approximability status of MAX NAE-SAT is almost completely understood if al…
CSPs with Global Modular Constraints: Algorithms and Hardness via Polynomial Representations
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 th…
An Algorithmic Blend of LPs and Ring Equations for Promise CSPs
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 proble…
Promise Constraint Satisfaction: Algebraic Structure and a Symmetric Boolean Dichotomy
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 or -hard. This p…