Article ID | Journal | Published Year | Pages | File Type |
---|---|---|---|---|
10331948 | Information Processing Letters | 2005 | 6 Pages |
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
Related Topics
Physical Sciences and Engineering
Computer Science
Computational Theory and Mathematics
Authors
Beate Bollig,