Document Open Access Logo

Partial Function Extension with Applications to Learning and Property Testing

Authors Umang Bhaskar, Gunjan Kumar

PDF
Thumbnail PDF

File

LIPIcs.ISAAC.2020.46.pdf
  • Filesize: 487 kB
  • 16 pages

Document Identifiers

Author Details

Umang Bhaskar
  • Tata Institute of Fundamental Research, Mumbai, India
Gunjan Kumar
  • Tata Institute of Fundamental Research, Mumbai, India

Funding

This research was supported by the Department of Atomic Energy, Government of India, under project no. RTI4001.
  • Bhaskar, Umang: UB acknowledges support from a Ramanujan Fellowship (SERB - SB/S2/RJN-055/2015) and an Early Career Research Award (SERB - ECR/2018/002766) from the Government of India.
  • Kumar, Gunjan: GK acknowledges support from a TCS fellowship.

Cite AsGet BibTex

Umang Bhaskar and Gunjan Kumar. Partial Function Extension with Applications to Learning and Property Testing. In 31st International Symposium on Algorithms and Computation (ISAAC 2020). Leibniz International Proceedings in Informatics (LIPIcs), Volume 181, pp. 46:1-46:16, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2020)
https://doi.org/10.4230/LIPIcs.ISAAC.2020.46

Abstract

Partial function extension is a basic problem that underpins multiple research topics in optimization, including learning, property testing, and game theory. Here, we are given a partial function consisting of n points from a domain and a function value at each point. Our objective is to determine if this partial function can be extended to a function defined on the domain, that additionally satisfies a given property, such as linearity. We formally study partial function extension to fundamental properties in combinatorial optimization - subadditivity, XOS, and matroid independence. A priori, it is not clear if partial function extension for these properties even lies in NP (or coNP). Our contributions are twofold. Firstly, for the properties studied, we give bounds on the complexity of partial function extension. For subadditivity and XOS, we give tight bounds on approximation guarantees as well. Secondly, we develop new connections between partial function extension and learning and property testing, and use these to give new results for these problems. In particular, for subadditive functions, we give improved lower bounds on learning, as well as the first subexponential-query tester.

Subject Classification

ACM Subject Classification
  • Theory of computation → Approximation algorithms analysis
Keywords
  • Partial function extension
  • subadditivity
  • matroid rank
  • approximation algorithms
  • learning
  • property testing

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 SODA, pages 1025-1035, 2012. Google Scholar
  2. Maria-Florina Balcan, Florin Constantin, Satoru Iwata, and Lei Wang. Learning valuation functions. In COLT 2012, June 25-27, 2012, Edinburgh, Scotland, pages 4.1-4.24, 2012. Google Scholar
  3. Maria Florina Balcan, Florin Constantin, Satoru Iwata, and Lei Wang. Learning valuation functions. In Conference on Learning Theory, pages 4-1, 2012. Google Scholar
  4. Maria-Florina Balcan and Nicholas J. A. Harvey. Learning submodular functions. In STOC 2011, San Jose, CA, USA, 6-8 June 2011, pages 793-802, 2011. Google Scholar
  5. Umang Bhaskar and Gunjan Kumar. The complexity of partial function extension for coverage functions. In APPROX/RANDOM Conference, volume 145 of LIPIcs, pages 30:1-30:21, 2019. Google Scholar
  6. Umang Bhaskar and Gunjan Kumar. A non-extendibility certificate for submodularity and applications. In International Computing and Combinatorics Conference, pages 603-614. Springer, 2020. Google Scholar
  7. Kshipra Bhawalkar and Tim Roughgarden. Welfare guarantees for combinatorial auctions with item bidding. In SODA, pages 700-709, 2011. Google Scholar
  8. Endre Boros, Toshihide Ibaraki, and Kazuhisa Makino. Error-free and best-fit extensions of partially defined Boolean functions. Inf. Comput., 140(2):254-283, 1998. Google Scholar
  9. Deeparnab Chakrabarty and C. Seshadhri. Optimal bounds for monotonicity and Lipschitz testing over hypercubes and hypergrids. In STOC, pages 419-428, 2013. Google Scholar
  10. Irit Dinur and David Steurer. Analytical approach to parallel repetition. In STOC 2014, pages 624-633. ACM, 2014. Google Scholar
  11. Shahar Dobzinski. Two randomized mechanisms for combinatorial auctions. In APPROX-RANDOM, volume 4627 of Lecture Notes in Computer Science, pages 89-103. Springer, 2007. Google Scholar
  12. Arkadii G D’yachkov, Il'ya Viktorovich Vorob’ev, NA Polyansky, and V Yu Shchukin. Bounds on the rate of disjunctive codes. Problems of Information Transmission, 50(1):27-56, 2014. Google Scholar
  13. Paul Erdös, Peter Frankl, and Zoltán Füredi. Families of finite sets in which no set is covered by the union ofr others. Israel Journal of Mathematics, 51(1):79-89, 1985. Google Scholar
  14. Uriel Feige. On maximizing welfare when utility functions are subadditive. SIAM Journal on Computing, 39(1):122-142, 2009. Google Scholar
  15. Navin Kashyap, Emina Soljanin, and Pascal Vontobel. Applications of matroid theory and combinatorial optimization to information and coding theory, 2009. Google Scholar
  16. Benny Lehmann, Daniel J. Lehmann, and Noam Nisan. Combinatorial auctions with decreasing marginal utilities. Games and Economic Behavior, 55(2):270-296, 2006. Google Scholar
  17. James Oxley. What is a matroid. Cubo Matemática Educacional, 5(3):179-218, 2003. Google Scholar
  18. Michal Parnas, Dana Ron, and Ronitt Rubinfeld. On testing convexity and submodularity. SIAM J. Comput., 32(5):1158-1184, 2003. Google Scholar
  19. Hans JM Peters and Peter P Wakker. Convex functions on non-convex domains. Economics letters, 22(2-3):251-255, 1986. Google Scholar
  20. Leonard Pitt and Leslie G. Valiant. Computational limitations on learning from examples. J. ACM, 35(4):965-984, 1988. Google Scholar
  21. Thomas J Schaefer. The complexity of satisfiability problems. In STOC 1978, pages 216-226. ACM, 1978. Google Scholar
  22. C. Seshadhri and Jan Vondrák. Is submodularity testable? Algorithmica, 69(1):1-25, 2014. Google Scholar
  23. Paul D. Seymour. Recognizing graphic matroids. Combinatorica, 1(1):75-78, 1981. Google Scholar
  24. Donald M. Topkis. Minimizing a submodular function on a lattice. Operations Research, 26(2):305-321, 1978. Google Scholar
  25. Dominic JA Welsh. Matroid theory. Courier Corporation, 2010. Google Scholar
  26. Hassler Whitney. On the abstract properties of linear dependence. American Journal of Mathematics, 57(3):509-533, 1935. Google Scholar
  27. William K Wootters. Entanglement of formation of an arbitrary state of two qubits. Physical Review Letters, 80(10):2245, 1998. 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