Search filters

List of works by Venkatesan Guruswami

(2 + epsilon)-Sat Is NP-Hard

An Exponential Lower Bound on the Sub-Packetization of Minimum Storage Regenerating Codes

scientific article published in 2021

Beating the Random Ordering Is Hard: Every Ordering CSP Is Approximation Resistant

Beyond Single-Deletion Correcting Codes: Substitutions and Transpositions

scientific article published in 2023

Every Permutation CSP of arity 3 is Approximation Resistant

scientific article (publication date: July 2009)

Hardness of Approximate Hypergraph Coloring

On the List-Decodability of Random Linear Codes

On the list-decodability of random linear codes

Parameterized Inapproximability Hypothesis under Exponential Time Hypothesis

scientific article published on 11 June 2024

Query Strategies for Priced Information

Super-polylogarithmic hypergraph coloring hardness via low-degree long codes

Paulina is supported by:

About Paulina

Help