Distribution-free Junta Testing
From MaRDI portal
Publication:4629971
DOI10.1145/3264434zbMath1454.68172arXiv1802.04859MaRDI QIDQ4629971
Rocco A. Servedio, Xi Chen, Ying Sheng, Zhengyang Liu, Jinyu Xie
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
68Q17: Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.)
68W20: Randomized algorithms