Randomly Supported Independence and Resistance

DOI10.1137/100783534zbMath1216.68115OpenAlexW2083360043WikidataQ56958835 ScholiaQ56958835MaRDI QIDQ2999851

Per Austrin, Johan T. Håstad

Publication date: 17 May 2011

Published in: SIAM Journal on Computing (Search for Journal in Brave)

Full work available at URL: http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.185.908

zbMATH Keywords

constraint satisfaction\(k\)-wise independenceapproximation resistance

Mathematics Subject Classification ID

Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Approximation algorithms (68W25)

Related Items (5)

A query efficient non-adaptive long code test with perfect completeness ⋮ Nonlocal Games with Noisy Maximally Entangled States are Decidable ⋮ On the Approximability of Presidential Type Predicates ⋮ Unnamed Item ⋮ Gaussian bounds for noise correlation of resilient functions

This page was built for publication: Randomly Supported Independence and Resistance