Direct Sum Testing: The General Case

Authors Irit Dinur, Konstantin Golubev



PDF
Thumbnail PDF

File

LIPIcs.APPROX-RANDOM.2019.40.pdf
  • Filesize: 474 kB
  • 11 pages

Document Identifiers

Author Details

Irit Dinur
  • The Weizmann Institute of Science, Rehovot, Israel
Konstantin Golubev
  • D-MATH, ETH Zurich, Switzerland

Cite AsGet BibTex

Irit Dinur and Konstantin Golubev. Direct Sum Testing: The General Case. In Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2019). Leibniz International Proceedings in Informatics (LIPIcs), Volume 145, pp. 40:1-40:11, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2019)
https://doi.org/10.4230/LIPIcs.APPROX-RANDOM.2019.40

Abstract

A function f:[n_1] x ... x[n_d]->F_2 is a direct sum if it is of the form f (a_1,...,a_d) = f_1(a_1) oplus ... oplus f_d (a_d), for some d functions f_i:[n_i]->F_2 for all i=1,..., d, and where n_1,...,n_d in N. We present a 4-query test which distinguishes between direct sums and functions that are far from them. The test relies on the BLR linearity test (Blum, Luby, Rubinfeld, 1993) and on the direct product test constructed by Dinur & Steurer (2014). We also present a different test, which queries the function (d+1) times, but is easier to analyze. In multiplicative +/- 1 notation, this reads as follows. A d-dimensional tensor with +/- 1 entries is called a tensor product if it is a tensor product of d vectors with +/- 1 entries, or equivalently, if it is of rank 1. The presented tests can be read as tests for distinguishing between tensor products and tensors that are far from being tensor products.

Subject Classification

ACM Subject Classification
  • Theory of computation → Design and analysis of algorithms
Keywords
  • property testing
  • direct sum
  • tensor product

Metrics

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

References

  1. Mihir Bellare, Don Coppersmith, JOHAN Hastad, Marcos Kiwi, and Madhu Sudan. Linearity testing in characteristic two. IEEE Transactions on Information Theory, 42(6):1781-1795, 1996. Google Scholar
  2. 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. Google Scholar
  3. Roee David, Irit Dinur, Elazar Goldenberg, Guy Kindler, and Igor Shinkar. Direct sum testing. SIAM Journal on Computing, 46(4):1336-1369, 2017. Google Scholar
  4. Irit Dinur and Elazar Goldenberg. Locally testing direct product in the low error range. In 2008 49th Annual IEEE Symposium on Foundations of Computer Science, pages 613-622. IEEE, 2008. Google Scholar
  5. Irit Dinur and Omer Reingold. Assignment testers: Towards a combinatorial proof of the PCP theorem. SIAM Journal on Computing, 36(4):975-1024, 2006. Google Scholar
  6. Irit Dinur and David Steurer. Direct product testing. In 2014 IEEE 29th Conference on Computational Complexity (CCC), pages 188-196. IEEE, 2014. Google Scholar
  7. Oded Goldreich and Shmuel Safra. A combinatorial consistency lemma with application to proving the PCP theorem. SIAM Journal on Computing, 29(4):1132-1154, 2000. Google Scholar
  8. Russell Impagliazzo, Ragesh Jaiswal, and Valentine Kabanets. Approximate list-decoding of direct product codes and uniform hardness amplification. SIAM Journal on Computing, 39(2):564-605, 2009. Google Scholar
  9. Russell Impagliazzo, Ragesh Jaiswal, Valentine Kabanets, and Avi Wigderson. Uniform direct product theorems: simplified, optimized, and derandomized. SIAM Journal on Computing, 39(4):1637-1665, 2010. Google Scholar
  10. Russell Impagliazzo, Valentine Kabanets, and Avi Wigderson. New direct-product testers and 2-query PCPs. SIAM Journal on Computing, 41(6):1722-1768, 2012. Google Scholar
  11. Tali Kaufman and Alexander Lubotzky. High dimensional expanders and property testing. In Proceedings of the 5th conference on Innovations in theoretical computer science, pages 501-506. ACM, 2014. Google Scholar
  12. Ryan O'Donnell. Analysis of boolean functions. Cambridge University Press, 2014. Google Scholar
  13. Madhu Sudan, Luca Trevisan, and Salil Vadhan. Pseudorandom generators without the XOR lemma. Journal of Computer and System Sciences, 62(2):236-266, 2001. Google Scholar
  14. Luca Trevisan. List-decoding using the XOR lemma. In 44th Annual IEEE Symposium on Foundations of Computer Science, 2003. Proceedings., pages 126-135. IEEE, 2003. Google Scholar
  15. Andrew C Yao. Theory and application of trapdoor functions. In 23rd Annual Symposium on Foundations of Computer Science (sfcs 1982), pages 80-91. IEEE, 1982. 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