Under the auspices of the Computational Complexity Foundation (CCF)

REPORTS > KEYWORD > SUBMODULAR OPTIMIZATION:
Reports tagged with submodular optimization:
TR16-105 | 13th July 2016
Eric Blais, Clement Canonne, Talya Eden, Amit Levi, Dana Ron

#### Tolerant Junta Testing and the Connection to Submodular Optimization and Function Isomorphism

Revisions: 1

The function $f\colon \{-1,1\}^n \to \{-1,1\}$ is a $k$-junta if it depends on at most $k$ of its variables. We consider the problem of tolerant testing of $k$-juntas, where the testing algorithm must accept any function that is $\epsilon$-close to some $k$-junta and reject any function that is $\epsilon'$-far from ... 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 >>>

ISSN 1433-8092 | Imprint