Document Open Access Logo

Distribution-Free Testing of Linear Functions on ℝⁿ

Authors Noah Fleming, Yuichi Yoshida

PDF
Thumbnail PDF

File

LIPIcs.ITCS.2020.22.pdf
  • Filesize: 0.57 MB
  • 19 pages

Document Identifiers

Author Details

Noah Fleming
  • University of Toronto, Toronto, Canada
Yuichi Yoshida
  • National Institute of Informatics, Tokyo, Japan

Funding

  • Fleming, Noah: Supported by MITACS JSPS and NSERC.
  • Yoshida, Yuichi: Supported by JSPS KAKENHI Grant Number JP17H04676 and JP18H05291.

Cite AsGet BibTex

Noah Fleming and Yuichi Yoshida. Distribution-Free Testing of Linear Functions on ℝⁿ. In 11th Innovations in Theoretical Computer Science Conference (ITCS 2020). Leibniz International Proceedings in Informatics (LIPIcs), Volume 151, pp. 22:1-22:19, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2020)
https://doi.org/10.4230/LIPIcs.ITCS.2020.22

Abstract

We study the problem of testing whether a function f:ℝⁿ → ℝ is linear (i.e., both additive and homogeneous) in the distribution-free property testing model, where the distance between functions is measured with respect to an unknown probability distribution over ℝⁿ. We show that, given query access to f, sampling access to the unknown distribution as well as the standard Gaussian, and ε > 0, we can distinguish additive functions from functions that are ε-far from additive functions with O((1/ε)log(1/ε)) queries, independent of n. Furthermore, under the assumption that f is a continuous function, the additivity tester can be extended to a distribution-free tester for linearity using the same number of queries. On the other hand, we show that if we are only allowed to get values of f on sampled points, then any distribution-free tester requires Ω(n) samples, even if the underlying distribution is the standard Gaussian.

Subject Classification

ACM Subject Classification
  • Theory of computation → Streaming, sublinear and near linear time algorithms
Keywords
  • Property Testing
  • Distribution-Free Testing
  • Linearity Testing

Metrics

  • Access Statistics
  • Total Accesses (updated on a weekly basis)
    0
    PDF Downloads
    0
    Metadata Views

References

  1. Sigal Ar, Manuel Blum, Bruno Codenotti, and Peter Gemmell. Checking approximate computations over the reals. In Proceedings of the 35th Annual ACM Symposium on Theory of Computing (STOC), pages 786-795, 1993. URL: https://doi.org/10.1145/167088.167288.
  2. Sanjeev Arora, Carsten Lund, Rajeev Motwani, Madhu Sudan, and Mario Szegedy. Proof Verification and Hardness of Approximation Problems. In Proceedings of the 33rd Annual Symposium on Foundations of Computer Science (FOCS), pages 14-23, 1992. URL: https://doi.org/10.1109/SFCS.1992.267823.
  3. Maria-Florina Balcan, Eric Blais, Avrim Blum, and Liu Yang. Active Property Testing. In Proceedings of the 53rd Annual IEEE Symposium on Foundations of Computer Science (FOCS), pages 21-30, 2012. URL: https://doi.org/10.1109/FOCS.2012.64.
  4. Robert Gardner Bartle and Donald R Sherbert. Introduction to real analysis. Hoboken, NJ: Wiley, 2011. Google Scholar
  5. Mihir Bellare, Oded Goldreich, and Madhu Sudan. Free Bits, PCPs and Non-Approximability - Towards Tight Results. In Proceedings of the 36th Annual Symposium on Foundations of Computer Science (FOCS), pages 422-431, 1995. URL: https://doi.org/10.1109/SFCS.1995.492573.
  6. Aleksandrs Belovs. Quantum Algorithm for Distribution-Free Junta Testing. In Proceedings of the 14th International Computer Science Symposium in Russia (CSR), pages 50-59, 2019. URL: https://doi.org/10.1007/978-3-030-19955-5_5.
  7. Michael Ben Or, Don Coppersmith, Mike Luby, and Ronitt Rubinfeld. Non-Abelian homomorphism testing, and distributions close to their self-convolutions. Random Structures & Algorithms, 32(1):49-70, January 2008. Google Scholar
  8. Arnab Bhattacharyya, Swastik Kopparty, Grant Schoenebeck, Madhu Sudan, and David Zuckerman. Optimal Testing of Reed-Muller Codes. In Proceedings of the 51st Annual IEEE Symposium on Foundations of Computer Science (FOCS), pages 488-497, 2010. Google Scholar
  9. Eric Blais. Testing juntas nearly optimally. In Proceedings of the 41st Annual ACM Symposium on Theory of Computing (STOC), pages 151-158, 2009. Google Scholar
  10. Eric Blais, Amit Weinstein, and Yuichi Yoshida. Partially Symmetric Functions Are Efficiently Isomorphism Testable. SIAM Journal on Computing, 44(2):411-432, 2015. Google Scholar
  11. Manuel Blum, Michael Luby, and Ronitt Rubinfeld. Self-Testing/Correcting with Applications to Numerical Problems. Journal of Computer and System Sciences, 47(3):549-595, 1993. URL: https://doi.org/10.1016/0022-0000(93)90044-W.
  12. Nader H. Bshouty. Almost Optimal Distribution-Free Junta Testing. In Proceedings of the 34th Computational Complexity Conference (CCC), pages 2:1-2:13, 2019. URL: https://doi.org/10.4230/LIPIcs.CCC.2019.2.
  13. Xi Chen, Adam Freilich, Rocco A. Servedio, and Timothy Sun. Sample-Based High-Dimensional Convexity Testing. In Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM), pages 37:1-37:20, 2017. URL: https://doi.org/10.4230/LIPIcs.APPROX-RANDOM.2017.37.
  14. Xi Chen and Jinyu Xie. Tight Bounds for the Distribution-Free Testing of Monotone Conjunctions. In Proceedings of the 27th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA), pages 54-71, 2016. URL: https://doi.org/10.1137/1.9781611974331.ch5.
  15. Anindya De, Elchanan Mossel, and Joe Neeman. Is your function low-dimensional? arXiv e-prints, page arXiv:1806.10057, 2018. URL: http://arxiv.org/abs/1806.10057.
  16. Elya Dolev and Dana Ron. Distribution-Free Testing for Monomials with a Sublinear Number of Queries. Theory of Computing, 7(1):155-176, 2011. URL: https://doi.org/10.4086/toc.2011.v007a011.
  17. Funda Ergün, Ravi Kumar, and Ronitt Rubinfeld. Checking Approximate Computations of Polynomials and Functional Equations. SIAM Journal on Computing, 31(2):550-576, 2001. URL: https://doi.org/10.1137/S0097539798337613.
  18. Eldar Fischer, Guy Kindler, Dana Ron, Shmuel Safra, and Alex Samorodnitsky. Testing juntas. Journal of Computer and System Sciences, 68(4):753-787, 2004. Google Scholar
  19. Peter Gemmell, Richard J. Lipton, Ronitt Rubinfeld, Madhu Sudan, and Avi Wigderson. Self-Testing/Correcting for Polynomials and for Approximate Functions. In Proceedings of the 23rd Annual ACM Symposium on Theory of Computing (STOC), pages 32-42, 1991. URL: https://doi.org/10.1145/103418.103429.
  20. Dana Glasner and Rocco A. Servedio. Distribution-Free Testing Lower Bounds for Basic Boolean Functions. In Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM), pages 494-508, 2007. URL: https://doi.org/10.1007/978-3-540-74208-1_36.
  21. Oded Goldreich. Introduction to Property Testing. Cambridge University Press, 2017. URL: https://doi.org/10.1017/9781108135252.
  22. Oded Goldreich, Shafi Goldwasser, and Dana Ron. Property Testing and its Connection to Learning and Approximation. Journal of the ACM, 45(4):653-750, 1998. URL: https://doi.org/10.1145/285055.285060.
  23. Shirley Halevy and Eyal Kushilevitz. Distribution-Free Property-Testing. SIAM Journal on Computing, 37(4):1107-1138, 2007. URL: https://doi.org/10.1137/050645804.
  24. Nathaniel Harms. Testing Halfspaces over Rotation-Invariant Distributions. In Proceedings of the 30th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA), pages 694-713, 2019. URL: https://doi.org/10.1137/1.9781611975482.44.
  25. Johan Håstad. Clique is Hard to Approximate Within n^1-ε. In Proceedings of the 37th Annual Symposium on Foundations of Computer Science (FOCS), pages 627-636, 1996. URL: https://doi.org/10.1109/SFCS.1996.548522.
  26. Tali Kaufman and Dana Ron. Testing Polynomials over General Fields. SIAM Journal on Computing, 36(3):779-802, 2006. URL: https://doi.org/10.1137/S0097539704445615.
  27. Marcos A. Kiwi, Frédéric Magniez, and Miklos Santha. Approximate Testing with Relative Error. In Proceedings of the 31st Annual ACM Symposium on Theory of Computing (STOC), pages 51-60, 1999. URL: https://doi.org/10.1145/301250.301269.
  28. Marcos A. Kiwi, Frédéric Magniez, and Miklos Santha. Exact and Approximate Testing/Correcting of Algebraic Functions: A Survey. In Theoretical Aspects of Computer Science, Advanced Lectures (First Summer School on Theoretical Aspects of Computer Science, Tehran, Iran, July 2000), pages 30-83, 2000. URL: https://doi.org/10.1007/3-540-45878-6_2.
  29. Pravesh Kothari, Amir Nayyeri, Ryan O'Donnell, and Chenggang Wu. Testing Surface Area. In Proceedings of the 25th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA), pages 1204-1214, 2014. URL: https://doi.org/10.1137/1.9781611973402.89.
  30. Zhengyang Liu, Xi Chen, Rocco A. Servedio, Ying Sheng, and Jinyu Xie. Distribution-free Junta Testing. ACM Transactions on Algorithms, 15(1):1:1-1:23, 2019. URL: https://doi.org/10.1145/3264434.
  31. Kevin Matulef, Ryan O'Donnell, Ronitt Rubinfeld, and Rocco A Servedio. Testing Halfspaces. SIAM Journal on Computing, 39(5):2004-2047, 2010. Google Scholar
  32. Kevin Matulef, Ryan O'Donnell, Ronitt Rubinfeld, and Rocco A. Servedio. Testing (Subclasses of) Halfspaces. In Property Testing - Current Research and Surveys, pages 334-340. Springer, 2010. URL: https://doi.org/10.1007/978-3-642-16367-8_27.
  33. Kevin Matulef, Ryan O’Donnell, Ronitt Rubinfeld, and Rocco A Servedio. Testing ±1-weight halfspace. In Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM), pages 646-657. Springer, 2009. Google Scholar
  34. Joe Neeman. Testing surface area with arbitrary accuracy. In Proceedings of the 46th Annual ACM Symposium on Theory of Computing (STOC), pages 393-397, 2014. URL: https://doi.org/10.1145/2591796.2591807.
  35. Kenta Oono and Yuichi Yoshida. Testing properties of functions on finite groups. Random Structures & Algorithms, 49(3):579-598, 2016. Google Scholar
  36. Sofya Raskhodnikova and Ronitt Rubinfeld. Linearity and Group Homomorphism Testing/Testing Hadamard Codes. Encyclopedia of Algorithms, pages 1-6, 2014. Google Scholar
Questions / Remarks / Feedback
X

Feedback for Dagstuhl Publishing


Thanks for your feedback!

Feedback submitted

Could not send message

Please try again later or send an E-mail
© 2023-2024 Schloss Dagstuhl – LZI GmbH Imprint Privacy Contact