Distribution-free Junta Testing

DOI10.1145/3264434zbMath1454.68172arXiv1802.04859OpenAlexW2892448241WikidataQ129199703 ScholiaQ129199703MaRDI QIDQ4629971

Jinyu Xie, Zhengyang Liu, Ying Sheng, Xi Chen, Rocco A. Servedio

Publication date: 28 March 2019

Published in: ACM Transactions on Algorithms, Proceedings of the 50th Annual ACM SIGACT Symposium on Theory of Computing (Search for Journal in Brave)

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

zbMATH Keywords

property testingjuntasdistribution-free testingdistribution-free model

Mathematics Subject Classification ID

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

Related Items (3)

Testing graphs against an unknown distribution ⋮ Almost Optimal Testers for Concise Representations. ⋮ Almost optimal distribution-free junta testing

This page was built for publication: Distribution-free Junta Testing