Testing +/- 1-Weight Halfspaces
We consider the problem of testing whether a Boolean function f:{ − 1,1} [superscript n] →{ − 1,1} is a ±1-weight halfspace, i.e. a function of the form f(x) = sgn(w [subscript 1] x [subscript 1] + w [subscript 2] x [subscript 2 ]+ ⋯ + w [subscript n] x [subscript n] ) where the weights w i...
| Main Authors: | , , , |
|---|---|
| Other Authors: | |
| Format: | Article |
| Language: | en_US |
| Published: |
Springer Berlin Heidelberg
2010
|
| Online Access: | http://hdl.handle.net/1721.1/52307 https://orcid.org/0000-0002-4353-7639 |
| _version_ | 1811077550793818112 |
|---|---|
| author | Matulef, Kevin M. O'Donnell, Ryan Rubinfeld, Ronitt Sevedio, Rocco A. |
| author2 | Massachusetts Institute of Technology. Department of Electrical Engineering and Computer Science |
| author_facet | Massachusetts Institute of Technology. Department of Electrical Engineering and Computer Science Matulef, Kevin M. O'Donnell, Ryan Rubinfeld, Ronitt Sevedio, Rocco A. |
| author_sort | Matulef, Kevin M. |
| collection | MIT |
| description | We consider the problem of testing whether a Boolean function f:{ − 1,1} [superscript n] →{ − 1,1} is a ±1-weight halfspace, i.e. a function of the form f(x) = sgn(w [subscript 1] x [subscript 1] + w [subscript 2] x [subscript 2 ]+ ⋯ + w [subscript n] x [subscript n] ) where the weights w i take values in { − 1,1}. We show that the complexity of this problem is markedly different from the problem of testing whether f is a general halfspace with arbitrary weights. While the latter can be done with a number of queries that is independent of n [7], to distinguish whether f is a ±-weight halfspace versus ε-far from all such halfspaces we prove that nonadaptive algorithms must make Ω(logn) queries. We complement this lower bound with a sublinear upper bound showing that $O(\sqrt{n}\cdot $poly$(\frac{1}{\epsilon}))$ queries suffice. |
| first_indexed | 2024-09-23T10:44:49Z |
| format | Article |
| id | mit-1721.1/52307 |
| institution | Massachusetts Institute of Technology |
| language | en_US |
| last_indexed | 2024-09-23T10:44:49Z |
| publishDate | 2010 |
| publisher | Springer Berlin Heidelberg |
| record_format | dspace |
| spelling | mit-1721.1/523072022-09-27T14:41:31Z Testing +/- 1-Weight Halfspaces Matulef, Kevin M. O'Donnell, Ryan Rubinfeld, Ronitt Sevedio, Rocco A. Massachusetts Institute of Technology. Department of Electrical Engineering and Computer Science Rubinfeld, Ronitt Matulef, Kevin M. Rubinfeld, Ronitt We consider the problem of testing whether a Boolean function f:{ − 1,1} [superscript n] →{ − 1,1} is a ±1-weight halfspace, i.e. a function of the form f(x) = sgn(w [subscript 1] x [subscript 1] + w [subscript 2] x [subscript 2 ]+ ⋯ + w [subscript n] x [subscript n] ) where the weights w i take values in { − 1,1}. We show that the complexity of this problem is markedly different from the problem of testing whether f is a general halfspace with arbitrary weights. While the latter can be done with a number of queries that is independent of n [7], to distinguish whether f is a ±-weight halfspace versus ε-far from all such halfspaces we prove that nonadaptive algorithms must make Ω(logn) queries. We complement this lower bound with a sublinear upper bound showing that $O(\sqrt{n}\cdot $poly$(\frac{1}{\epsilon}))$ queries suffice. 2010-03-04T19:27:20Z 2010-03-04T19:27:20Z 2009 Article http://purl.org/eprint/type/JournalArticle 978-3-642-03684-2 http://hdl.handle.net/1721.1/52307 Matulef, Kevin et al. “Testing ±1-weight halfspace.” Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques 2009. https://orcid.org/0000-0002-4353-7639 en_US http://dx.doi.org/10.1007/978-3-642-03685-9_48 Lecture Notes in Computer Science Attribution-Noncommercial-Share Alike 3.0 Unported http://creativecommons.org/licenses/by-nc-sa/3.0/ application/pdf Springer Berlin Heidelberg Ronitt Rubinfeld |
| spellingShingle | Matulef, Kevin M. O'Donnell, Ryan Rubinfeld, Ronitt Sevedio, Rocco A. Testing +/- 1-Weight Halfspaces |
| title | Testing +/- 1-Weight Halfspaces |
| title_full | Testing +/- 1-Weight Halfspaces |
| title_fullStr | Testing +/- 1-Weight Halfspaces |
| title_full_unstemmed | Testing +/- 1-Weight Halfspaces |
| title_short | Testing +/- 1-Weight Halfspaces |
| title_sort | testing 1 weight halfspaces |
| url | http://hdl.handle.net/1721.1/52307 https://orcid.org/0000-0002-4353-7639 |
| work_keys_str_mv | AT matulefkevinm testing1weighthalfspaces AT odonnellryan testing1weighthalfspaces AT rubinfeldronitt testing1weighthalfspaces AT sevedioroccoa testing1weighthalfspaces |