Document Open Access Logo

Testing Submodularity and Other Properties of Valuation Functions

Authors Eric Blais, Abhinav Bommireddi

PDF
Thumbnail PDF

File

LIPIcs.ITCS.2017.33.pdf
  • Filesize: 0.55 MB
  • 17 pages

Document Identifiers

Author Details

Eric Blais
Abhinav Bommireddi

Cite As Get BibTex

Eric Blais and Abhinav Bommireddi. Testing Submodularity and Other Properties of Valuation Functions. In 8th Innovations in Theoretical Computer Science Conference (ITCS 2017). Leibniz International Proceedings in Informatics (LIPIcs), Volume 67, pp. 33:1-33:17, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2017) https://doi.org/10.4230/LIPIcs.ITCS.2017.33

Abstract

We show that for any constant \epsilon > 0 and p \ge 1, it is possible to distinguish functions f : \{0,1\}^n \to [0,1] that are submodular from those that are \epsilon-far from every submodular function in \ell_p distance with a constant number of queries. 
		
More generally, we extend the testing-by-implicit-learning framework of Diakonikolas et al.(2007) to show that every property of real-valued functions that is well-approximated in \ell_2 distance by a class of k-juntas for some k = O(1) can be tested in the \ell_p-testing model with a constant number of queries. This result, combined with a recent junta theorem of Feldman and \Vondrak (2016), yields the constant-query testability of submodularity. It also yields constant-query testing algorithms for a variety of other natural properties of valuation functions, including fractionally additive (XOS) functions, OXS functions, unit demand functions, coverage functions, and self-bounding functions.

Subject Classification

Keywords
  • Property testing
  • Testing by implicit learning
  • Self-bounding functions

Metrics

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

References

  1. Ashwinkumar Badanidiyuru, Shahar Dobzinski, Hu Fu, Robert Kleinberg, Noam Nisan, and Tim Roughgarden. Sketching valuation functions. In Yuval Rabani, editor, Proceedings of the Twenty-Third Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2012, Kyoto, Japan, January 17-19, 2012, pages 1025-1035. SIAM, 2012. URL: http://portal.acm.org/citation.cfm?id=2095197&CFID=63838676&CFTOKEN=79617016.
  2. Maria-Florina Balcan, Florin Constantin, Satoru Iwata, and Lei Wang. Learning valuation functions. In Shie Mannor, Nathan Srebro, and Robert C. Williamson, editors, COLT 2012 - The 25th Annual Conference on Learning Theory, June 25-27, 2012, Edinburgh, Scotland, volume 23 of JMLR Proceedings, pages 4.1-4.24. JMLR.org, 2012. URL: http://www.jmlr.org/proceedings/papers/v23/balcan12b/balcan12b.pdf.
  3. Maria-Florina Balcan and Nicholas J. A. Harvey. Learning submodular functions. In Proceedings of the 43rd ACM Symposium on Theory of Computing, STOC 2011, San Jose, CA, USA, 6-8 June 2011, pages 793-802, 2011. URL: http://dx.doi.org/10.1145/1993636.1993741.
  4. Piotr Berman, Sofya Raskhodnikova, and Grigory Yaroslavtsev. L_p-testing. In David B. Shmoys, editor, Symposium on Theory of Computing, STOC 2014, New York, NY, USA, May 31 - June 03, 2014, pages 164-173. ACM, 2014. URL: http://dx.doi.org/10.1145/2591796.2591887.
  5. Eric Blais. Testing juntas nearly optimally. In Michael Mitzenmacher, editor, Proceedings of the 41st Annual ACM Symposium on Theory of Computing, STOC 2009, Bethesda, MD, USA, May 31 - June 2, 2009, pages 151-158. ACM, 2009. URL: http://dx.doi.org/10.1145/1536414.1536437.
  6. Eric Blais, Amit Weinstein, and Yuichi Yoshida. Partially symmetric functions are efficiently isomorphism testable. SIAM J. Comput., 44(2):411-432, 2015. URL: http://dx.doi.org/10.1137/140971877.
  7. 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: http://dx.doi.org/10.1016/0022-0000(93)90044-W.
  8. Deeparnab Chakrabarty and Zhiyi Huang. Recognizing coverage functions. SIAM Journal on Discrete Mathematics, 29(3):1585-1599, 2015. http://arxiv.org/abs/http://dx.doi.org/10.1137/140964072,
  9. Sourav Chakraborty, David García-Soriano, and Arie Matsliah. Efficient sample extractors for juntas with applications. In Luca Aceto, Monika Henzinger, and Jirí Sgall, editors, Automata, Languages and Programming - 38th International Colloquium, ICALP 2011, Zurich, Switzerland, July 4-8, 2011, Proceedings, Part I, volume 6755 of Lecture Notes in Computer Science, pages 545-556. Springer, 2011. URL: http://dx.doi.org/10.1007/978-3-642-22006-7_46.
  10. Ilias Diakonikolas, Homin K. Lee, Kevin Matulef, Krzysztof Onak, Ronitt Rubinfeld, Rocco A. Servedio, and Andrew Wan. Testing for concise representations. In 48th Annual IEEE Symposium on Foundations of Computer Science (FOCS 2007), October 20-23, 2007, Providence, RI, USA, Proceedings, pages 549-558. IEEE Computer Society, 2007. URL: http://dx.doi.org/10.1109/FOCS.2007.32.
  11. Ilias Diakonikolas, Homin K. Lee, Kevin Matulef, Rocco A. Servedio, and Andrew Wan. Efficiently testing sparse GF(2) polynomials. In Luca Aceto, Ivan Damgård, Leslie Ann Goldberg, Magnús M. Halldórsson, Anna Ingólfsdóttir, and Igor Walukiewicz, editors, Automata, Languages and Programming, 35th International Colloquium, ICALP 2008, Reykjavik, Iceland, July 7-11, 2008, Proceedings, Part I: Tack A: Algorithms, Automata, Complexity, and Games, volume 5125 of Lecture Notes in Computer Science, pages 502-514. Springer, 2008. URL: http://dx.doi.org/10.1007/978-3-540-70575-8_41.
  12. Irit Dinur and Samuel Safra. On the hardness of approximating minimum vertex cover. Annals of Mathematics, 162:2005, 2004. Google Scholar
  13. Uriel Feige. On maximizing welfare when utility functions are subadditive. SIAM J. Comput., 39(1):122-142, 2009. URL: http://dx.doi.org/10.1137/070680977.
  14. Uriel Feige, Vahab S. Mirrokni, and Jan Vondrák. Maximizing non-monotone submodular functions. SIAM J. Comput., 40(4):1133-1153, 2011. URL: http://dx.doi.org/10.1137/090779346.
  15. Vitaly Feldman and Pravesh Kothari. Learning coverage functions and private release of marginals. In Maria-Florina Balcan, Vitaly Feldman, and Csaba Szepesvári, editors, Proceedings of The 27th Conference on Learning Theory, COLT 2014, Barcelona, Spain, June 13-15, 2014, volume 35 of JMLR Workshop and Conference Proceedings, pages 679-702. JMLR.org, 2014. URL: http://jmlr.org/proceedings/papers/v35/feldman14a.html.
  16. Vitaly Feldman and Jan Vondrák. Tight bounds on low-degree spectral concentration of submodular and XOS functions. In Venkatesan Guruswami, editor, IEEE 56th Annual Symposium on Foundations of Computer Science, FOCS 2015, Berkeley, CA, USA, 17-20 October, 2015, pages 923-942. IEEE Computer Society, 2015. URL: http://dx.doi.org/10.1109/FOCS.2015.61.
  17. Vitaly Feldman and Jan Vondrák. Optimal bounds on approximation of submodular and XOS functions by juntas. SIAM J. Comput., 45(3):1129-1170, 2016. URL: http://dx.doi.org/10.1137/140958207.
  18. Eldar Fischer, Guy Kindler, Dana Ron, Shmuel Safra, and Alex Samorodnitsky. Testing juntas. J. Comput. Syst. Sci., 68(4):753-787, 2004. URL: http://dx.doi.org/10.1016/j.jcss.2003.11.004.
  19. David Freedman. A remark on the difference between sampling with and without replacement. Journal of the American Statistical Association, 72(359):681-681, 1977. URL: http://dx.doi.org/10.1080/01621459.1977.10480637.
  20. Ehud Friedgut. On the measure of intersecting families, uniqueness and stability. Combinatorica, 28(5):503-528, 2008. URL: http://dx.doi.org/10.1007/s00493-008-2318-9.
  21. Oded Goldreich, Shafi Goldwasser, and Dana Ron. Property testing and its connection to learning and approximation. J. ACM, 45(4):653-750, 1998. URL: http://dx.doi.org/10.1145/285055.285060.
  22. Parikshit Gopalan, Ryan O'Donnell, Rocco A. Servedio, Amir Shpilka, and Karl Wimmer. Testing fourier dimensionality and sparsity. SIAM J. Comput., 40(4):1075-1100, 2011. URL: http://dx.doi.org/10.1137/100785429.
  23. Eyal Kushilevitz and Yishay Mansour. Learning decision trees using the fourier spectrum. SIAM J. Comput., 22(6):1331-1348, 1993. URL: http://dx.doi.org/10.1137/0222080.
  24. Benny Lehmann, Daniel J. Lehmann, and Noam Nisan. Combinatorial auctions with decreasing marginal utilities. Games and Economic Behavior, 55(2):270-296, 2006. URL: http://dx.doi.org/10.1016/j.geb.2005.02.006.
  25. Kevin Matulef, Ryan O'Donnell, Ronitt Rubinfeld, and Rocco A. Servedio. Testing halfspaces. SIAM J. Comput., 39(5):2004-2047, 2010. URL: http://dx.doi.org/10.1137/070707890.
  26. 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.
  27. Michal Parnas, Dana Ron, and Alex Samorodnitsky. Testing basic boolean formulae. SIAM J. Discrete Math., 16(1):20-46, 2002. URL: http://epubs.siam.org/sam-bin/dbq/article/40744.
  28. Ronitt Rubinfeld and Madhu Sudan. Robust characterizations of polynomials with applications to program testing. SIAM J. Comput., 25(2):252-271, 1996. URL: http://dx.doi.org/10.1137/S0097539793255151.
  29. Rocco A. Servedio. Testing by implicit learning: A brief survey. In Property Testing - Current Research and Surveys, pages 197-210, 2010. URL: http://dx.doi.org/10.1007/978-3-642-16367-8_11.
  30. C. Seshadhri and Jan Vondrák. Is submodularity testable? In Bernard Chazelle, editor, Innovations in Computer Science - ICS 2010, Tsinghua University, Beijing, China, January 7-9, 2011. Proceedings, pages 195-210. Tsinghua University Press, 2011. URL: http://conference.itcs.tsinghua.edu.cn/ICS2011/content/papers/21.html.
  31. Karl Wimmer and Yuichi Yoshida. Testing linear-invariant function isomorphism. In Fedor V. Fomin, Rusins Freivalds, Marta Z. Kwiatkowska, and David Peleg, editors, Automata, Languages, and Programming - 40th International Colloquium, ICALP 2013, Riga, Latvia, July 8-12, 2013, Proceedings, Part I, volume 7965 of Lecture Notes in Computer Science, pages 840-850. Springer, 2013. URL: http://dx.doi.org/10.1007/978-3-642-39206-1_71.
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