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 language | English |
---|---|
Pages (from-to) | 301-305 |
Number of pages | 5 |
Journal | INFORMATION PROCESSING LETTERS |
Volume | 90 |
Issue number | 6 |
DOIs | |
Publication status | Published - 2004 |