Name
Abstract | ||
|---|---|---|
Given a Boolean function $${f : \\mathbb{F}_{2}^{n} \\to \\{0,1\\}}$$ f : F 2 n ¿ { 0 , 1 } , we say a triple (x, y, x + y) is a triangle in f if $${f(x)\\!=\\!f(y)\\!=\\!f(x+y)\\!=\\!1}$$ f ( x ) = f ( y ) = f ( x + y ) = 1 . A triangle-free function contains no triangle. If f differs from every triangle-free function on at least $${\\epsilon \\cdot 2^n}$$ ∈ · 2 n points, then f is said to be $${\\epsilon}$$ ∈ -far from triangle-free.In this work, we analyze the query complexity of testers that, with constant probability, distinguish triangle-free functions from those $${\\epsilon}$$ ∈ -far from triangle-free. Let the canonical tester for triangle-freeness denotes the algorithm that repeatedly picks x and y uniformly and independently at random from $${\\mathbb{F}_2^n}$$ F 2 n , queries f(x), f(y) and f(x + y), and checks whether f(x) = f(y) = f(x + y) = 1. Green showed that the canonical tester rejects functions $${\\epsilon}$$ ∈ -far from triangle-free with constant probability if its query complexity is a tower of 2's whose height is polynomial in $${1/\\epsilon}$$ 1 / ∈ . Fox later improved the height of the tower in Green's upper bound to $${O(\\log{1/\\epsilon})}$$ O ( log 1 / ∈ ) . A trivial lower bound of $${\\Omega(1/\\epsilon)}$$ Ω ( 1 / ∈ ) on the query complexity is immediate. In this paper, we give the first non-trivial lower bound for the number of queries needed. We show that, for every small enough $${\\epsilon}$$ ∈ , there exists an integer $${n_{0}(\\epsilon)}$$ n 0 ( ∈ ) such that for all $${n\\geq n_{0}}$$ n ¿ n 0 there exists a function $${f :\\mathbb{F}_{2}^{n} \\to \\{0,1\\}}$$ f : F 2 n ¿ { 0 , 1 } depending on all n variables which is $${\\epsilon}$$ ∈ -far from being triangle-free and requires $${\\Omega \\left((\\frac{1}{\\epsilon})^{4.847\\cdots}\\right)}$$ Ω ( 1 ∈ ) 4.847 ¿ queries for the canonical tester. We also show that the query complexity of any general (possibly adaptive) one-sided tester for triangle-freeness is at least square root of the query complexity of the corresponding canonical tester. Consequently, this means that any one-sided tester for triangle-freeness must make at least $${\\Omega\\left((\\frac{1}{\\epsilon})^{2.423\\cdots}\\right)}$$ Ω ( 1 ∈ ) 2.423 ¿ queries. |
Year | DOI | Venue |
|---|---|---|
2015 | 10.1007/s00037-014-0092-1 | Electronic Colloquium on Computational Complexity |
Keywords | DocType | Volume |
property testing | Journal | 24 |
Issue | ISSN | ISBN |
1 | 1420-8954 | 978-0-89871-698-6 |
Citations | PageRank | References |
7 | 0.46 | 23 |
Authors | ||
2 | ||
Name | Order | Citations | PageRank |
|---|---|---|---|
| Arnab Bhattacharyya | 1 | 214 | 27.99 |
| Ning Xie | 2 | 70 | 9.29 |