A Hypergraph Dictatorship Test with Perfect Completeness

DOI10.1007/978-3-642-03685-9_34zbMath1255.68147arXiv0811.1922OpenAlexW3121681840MaRDI QIDQ3638897

Victor Chen

Publication date: 28 October 2009

Published in: Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (Search for Journal in Brave)

Full work available at URL: https://arxiv.org/abs/0811.1922

zbMATH Keywords

Fourier analysisproperty testingPCPGowers norm

Mathematics Subject Classification ID

Hypergraphs (05C65) Complexity classes (hierarchies, relations among complexity classes, etc.) (68Q15) Randomized algorithms (68W20)

Related Items (1)

Query-Efficient Dictatorship Testing with Perfect Completeness

This page was built for publication: A Hypergraph Dictatorship Test with Perfect Completeness