Tight Bounds for the Distribution-Free Testing of Monotone Conjunctions

DOI10.1137/1.9781611974331.ch5zbMath1410.68387arXiv1511.03333OpenAlexW2234555324MaRDI QIDQ4575580

Xi Chen, Jinyu Xie

Publication date: 16 July 2018

Published in: Proceedings of the Twenty-Seventh Annual ACM-SIAM Symposium on Discrete Algorithms (Search for Journal in Brave)

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

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Randomized algorithms (68W20)

Related Items (4)

Testing graphs against an unknown distribution ⋮ On one-sided testing affine subspaces ⋮ Almost Optimal Testers for Concise Representations. ⋮ Almost optimal distribution-free junta testing

This page was built for publication: Tight Bounds for the Distribution-Free Testing of Monotone Conjunctions