A large lower bound on the query complexity of a simple boolean function |
| |
Authors: | Beate Bollig |
| |
Affiliation: | FB 15, JWG-Univ. Frankfurt am Main, 60054 Frankfurt, Germany |
| |
Abstract: | Combinatorial property testing, initiated formally by Goldreich, Goldwasser, and Ron (1998) and inspired by Rubinfeld and Sudan (1996), deals with the relaxation of decision problems. Given a property P the aim is to decide whether a given input satisfies the property P or is far from having the property. For a family of boolean functions f=(fn) the associated property is the set of 1-inputs of f. Here, the known lower bounds on the query complexity of properties identified by boolean functions representable by (very) restricted branching programs of small size is improved up to Ω(n1/2), where n is the input length. |
| |
Keywords: | Computational complexity Branching programs Property testing Query complexity Randomized algorithms |
本文献已被 ScienceDirect 等数据库收录! |
|