A Query Efficient Non-adaptive Long Code Test with Perfect Completeness

DOI10.1007/978-3-642-15369-3_55zbMath1305.68105OpenAlexW122014950MaRDI QIDQ3588448

Yuichi Yoshida, Suguru Tamaki

Publication date: 10 September 2010

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

Full work available at URL: http://hdl.handle.net/2433/202504

zbMATH Keywords

influence of variablesdictatorship testamortized query complexitylong code test

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Approximation algorithms (68W25) Randomized algorithms (68W20)

Related Items

The Quest for Strong Inapproximability Results with Perfect Completeness