Showing cs.DSShow all
2 papers · 1 filter
cs.DS2026
New Algorithms and Hardness Results for Robust Satisfiability of (Promise) CSPs
Joshua Brakensiek, Lorenzo Ciardo, Venkatesan Guruswami +2
In this paper, we continue the study of robust satisfiability of promise CSPs (PCSPs), initiated in (Brakensiek, Guruswami, Sandeep, STOC 2023 / Discrete Analysis 2025), and obtain…
cs.DS2024
Sum-of-Squares Lower Bounds for Independent Set in Ultra-Sparse Random Graphs
Pravesh Kothari, Aaron Potechin, Jeff Xu
We prove that for every , and large enough constant , with high probability over the choice of , the \Erdos-\Renyi random graph distribution, t…