The non-adaptive query complexity of testing k-parities
| Authors |
|
|---|---|
| Publication date | 2013 |
| Journal | Chicago Journal of Theoretical Computer Science |
| Article number | 6 |
| Volume | Issue number | 2013 |
| Number of pages | 11 |
| Organisations |
|
| Abstract | We prove tight bounds of Θ(klogk) queries for non-adaptively testing whether a function f:{0,1}n→{0,1} is a k-parity or far from any k-parity. The lower bound combines a recent method of Blais, Brody and Matulef to get lower bounds for testing from communication complexity with an Ω(klogk) lower bound for the one-way communication complexity of k-disjointness. |
| Document type | Article |
| Note | With source material file |
| Language | English |
| Published at | https://doi.org/10.4086/cjtcs.2013.006 |
| Downloads |
cj13-06
(Final published version)
|
| Supplementary materials | |
| Permalink to this page | |