Venkatesan Guruswami

Algorithms and certificates for Boolean CSP refutation: smoothed is no harder than random

2022

We present an algorithm for strongly refuting smoothed instances of all Boolean CSPs. The smoothed model is a hybrid between worst and average-case input models, where the input is an arbitrary instance of the CSP …

Randomly Punctured Reed–Solomon Codes Achieve List-Decoding Capacity over Linear-Sized Fields

2024

Reed–Solomon codes are a classic family of error-correcting codes consisting of evaluations of low-degree polynomials over a finite field on some sequence of distinct field elements. They are widely known for their optimal unique-decoding capabilities, …