A lower bound for testing juntas

Hana Chockler, Dan Gutfreund

Research output: Contribution to journalArticlepeer-review

43 Citations (Scopus)

Abstract

We show an \Omega(m) lower bound on the number of queries required to test whether a Boolean function depends on at most m out of its n variables. This improves a previously known lower bound for testing this property. Our proof is simple and uses only elementary techniques.
Original languageEnglish
Pages (from-to)301-305
Number of pages5
JournalINFORMATION PROCESSING LETTERS
Volume90
Issue number6
DOIs
Publication statusPublished - 2004

Fingerprint

Dive into the research topics of 'A lower bound for testing juntas'. Together they form a unique fingerprint.

Cite this