Document Open Access Logo

Low-Degree Testing over Grids

Authors Prashanth Amireddy , Srikanth Srinivasan , Madhu Sudan

PDF
Thumbnail PDF

File

LIPIcs.APPROX-RANDOM.2023.41.pdf
  • Filesize: 0.92 MB
  • 22 pages

Document Identifiers

Author Details

Prashanth Amireddy
  • School of Engineering and Applied Sciences, Harvard University, Cambridge, MA, USA
Srikanth Srinivasan
  • Department of Computer Science, Aarhus University, Denmark
Madhu Sudan
  • School of Engineering and Applied Sciences, Harvard University, Cambridge, MA, USA

Funding

  • Amireddy, Prashanth: Supported in part by a Simons Investigator Award and NSF Award CCF 2152413 to Madhu Sudan.
  • Srinivasan, Srikanth: Supported by a start-up package from Aarhus University. Work done while visiting the Meta-Complexity program at the Simons Institute for the Theory of Computing, UC Berkeley.
  • Sudan, Madhu: Supported in part by a Simons Investigator Award and NSF Award CCF 2152413.

Cite As Get BibTex

Prashanth Amireddy, Srikanth Srinivasan, and Madhu Sudan. Low-Degree Testing over Grids. In Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2023). Leibniz International Proceedings in Informatics (LIPIcs), Volume 275, pp. 41:1-41:22, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2023) https://doi.org/10.4230/LIPIcs.APPROX/RANDOM.2023.41

Abstract

We study the question of local testability of low (constant) degree functions from a product domain 𝒮_1 × … × 𝒮_n to a field 𝔽, where 𝒮_i ⊆ 𝔽 can be arbitrary constant sized sets. We show that this family is locally testable when the grid is "symmetric". That is, if 𝒮_i = 𝒮 for all i, there is a probabilistic algorithm using constantly many queries that distinguishes whether f has a polynomial representation of degree at most d or is Ω(1)-far from having this property. In contrast, we show that there exist asymmetric grids with |𝒮_1| = ⋯ = |𝒮_n| = 3 for which testing requires ω_n(1) queries, thereby establishing that even in the context of polynomials, local testing depends on the structure of the domain and not just the distance of the underlying code. 
The low-degree testing problem has been studied extensively over the years and a wide variety of tools have been applied to propose and analyze tests. Our work introduces yet another new connection in this rich field, by building low-degree tests out of tests for "junta-degrees". A function f:𝒮_1 × ⋯ × 𝒮_n → 𝒢, for an abelian group 𝒢 is said to be a junta-degree-d function if it is a sum of d-juntas. We derive our low-degree test by giving a new local test for junta-degree-d functions. For the analysis of our tests, we deduce a small-set expansion theorem for spherical/hamming noise over large grids, which may be of independent interest.

Subject Classification

ACM Subject Classification
  • Theory of computation → Probabilistic computation
Keywords
  • Property testing
  • Low-degree testing
  • Small-set expansion
  • Local testing

Metrics

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

Related Versions

References

  1. Noga Alon, Tali Kaufman, Michael Krivelevich, Simon Litsyn, and Dana Ron. Testing reed-muller codes. IEEE Trans. Inf. Theory, 51(11):4032-4039, 2005. URL: https://doi.org/10.1109/TIT.2005.856958.
  2. Sanjeev Arora, Carsten Lund, Rajeev Motwani, Madhu Sudan, and Mario Szegedy. Proof verification and the hardness of approximation problems. J. ACM, 45(3):501-555, 1998. URL: https://doi.org/10.1145/278298.278306.
  3. Sanjeev Arora and Shmuel Safra. Probabilistic checking of proofs: A new characterization of NP. J. ACM, 45(1):70-122, 1998. URL: https://doi.org/10.1145/273865.273901.
  4. Vipul Arora, Arnab Bhattacharyya, Noah Fleming, Esty Kelman, and Yuichi Yoshida. Low degree testing over the reals. In Nikhil Bansal and Viswanath Nagarajan, editors, Proceedings of the 2023 ACM-SIAM Symposium on Discrete Algorithms, SODA 2023, Florence, Italy, January 22-25, 2023, pages 738-792. SIAM, 2023. URL: https://doi.org/10.1137/1.9781611977554.ch31.
  5. László Babai, Lance Fortnow, Leonid A. Levin, and Mario Szegedy. Checking computations in polylogarithmic time. In Cris Koutsougeras and Jeffrey Scott Vitter, editors, Proceedings of the 23rd Annual ACM Symposium on Theory of Computing, May 5-8, 1991, New Orleans, Louisiana, USA, pages 21-31. ACM, 1991. URL: https://doi.org/10.1145/103418.103428.
  6. László Babai, Lance Fortnow, and Carsten Lund. Non-deterministic exponential time has two-prover interactive protocols. Comput. Complex., 1:3-40, 1991. URL: https://doi.org/10.1007/BF01200056.
  7. Mitali Bafna, Srikanth Srinivasan, and Madhu Sudan. Local decoding and testing of polynomials over grids. Random Struct. Algorithms, 57(3):658-694, 2020. URL: https://doi.org/10.1002/rsa.20933.
  8. Boaz Barak, Parikshit Gopalan, Johan Håstad, Raghu Meka, Prasad Raghavendra, and David Steurer. Making the long code shorter. SIAM J. Comput., 44(5):1287-1324, 2015. URL: https://doi.org/10.1137/130929394.
  9. Eli Ben-Sasson, Prahladh Harsha, and Sofya Raskhodnikova. Some 3cnf properties are hard to test. SIAM J. Comput., 35(1):1-21, 2005. URL: https://doi.org/10.1137/S0097539704445445.
  10. Arnab Bhattacharyya, Swastik Kopparty, Grant Schoenebeck, Madhu Sudan, and David Zuckerman. Optimal testing of reed-muller codes. In 51th Annual IEEE Symposium on Foundations of Computer Science, FOCS 2010, October 23-26, 2010, Las Vegas, Nevada, USA, pages 488-497. IEEE Computer Society, 2010. URL: https://doi.org/10.1109/FOCS.2010.54.
  11. Manuel Blum, Michael Luby, and Ronitt Rubinfeld. Self-testing/correcting with applications to numerical problems. J. Comput. Syst. Sci., 47(3):549-595, 1993. URL: https://doi.org/10.1016/0022-0000(93)90044-W.
  12. Andrej Bogdanov and Gautam Prakriya. Direct sum and partitionability testing over general groups. In Nikhil Bansal, Emanuela Merelli, and James Worrell, editors, 48th International Colloquium on Automata, Languages, and Programming, ICALP 2021, July 12-16, 2021, Glasgow, Scotland (Virtual Conference), volume 198 of LIPIcs, pages 33:1-33:19. Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2021. URL: https://doi.org/10.4230/LIPIcs.ICALP.2021.33.
  13. Irit Dinur and Konstantin Golubev. Direct sum testing: The general case. In Dimitris Achlioptas and László A. Végh, editors, Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques, APPROX/RANDOM 2019, September 20-22, 2019, Massachusetts Institute of Technology, Cambridge, MA, USA, volume 145 of LIPIcs, pages 40:1-40:11. Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2019. URL: https://doi.org/10.4230/LIPIcs.APPROX-RANDOM.2019.40.
  14. Elad Haramaty, Noga Ron-Zewi, and Madhu Sudan. Absolutely sound testing of lifted codes. Theory Comput., 11:299-338, 2015. URL: https://doi.org/10.4086/toc.2015.v011a012.
  15. Elad Haramaty, Amir Shpilka, and Madhu Sudan. Optimal testing of multivariate polynomials over small prime fields. SIAM J. Comput., 42(2):536-562, 2013. URL: https://doi.org/10.1137/120879257.
  16. Wassily Hoeffding. Probability inequalities for sums of bounded random variables. The collected works of Wassily Hoeffding, pages 409-426, 1994. Google Scholar
  17. Charanjit S. Jutla, Anindya C. Patthak, Atri Rudra, and David Zuckerman. Testing low-degree polynomials over prime fields. Random Struct. Algorithms, 35(2):163-193, 2009. URL: https://doi.org/10.1002/rsa.20262.
  18. Tali Kaufman and Dor Minzer. Improved optimal testing results from global hypercontractivity. In 63rd IEEE Annual Symposium on Foundations of Computer Science, FOCS 2022, Denver, CO, USA, October 31 - November 3, 2022, pages 98-109. IEEE, 2022. URL: https://doi.org/10.1109/FOCS54457.2022.00017.
  19. Tali Kaufman and Dana Ron. Testing polynomials over general fields. SIAM J. Comput., 36(3):779-802, 2006. URL: https://doi.org/10.1137/S0097539704445615.
  20. Nathan Linial, Yishay Mansour, and Noam Nisan. Constant depth circuits, fourier transform, and learnability. J. ACM, 40(3):607-620, 1993. URL: https://doi.org/10.1145/174130.174138.
  21. Ryan O'Donnell. Analysis of Boolean Functions. Cambridge University Press, 2014. URL: http://www.cambridge.org/de/academic/subjects/computer-science/algorithmics-complexity-computer-algebra-and-computational-g/analysis-boolean-functions.
  22. Øystein Ore. Über höhere kongruenzen. Norsk Mat. Forenings Skrifter, 1(7):15, 1922. Google Scholar
  23. Yury Polyanskiy. Hypercontractivity of spherical averages in hamming space. SIAM J. Discret. Math., 33(2):731-754, 2019. URL: https://doi.org/10.1137/15M1046575.
  24. Ronitt Rubinfeld and Madhu Sudan. Robust characterizations of polynomials with applications to program testing. SIAM J. Comput., 25(2):252-271, 1996. URL: https://doi.org/10.1137/S0097539793255151.
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 About DROPS Imprint Privacy Contact