License: Creative Commons Attribution 3.0 Unported license (CC BY 3.0)
When quoting this document, please refer to the following
DOI: 10.4230/LIPIcs.ISAAC.2020.46
URN: urn:nbn:de:0030-drops-133906
URL: http://dagstuhl.sunsite.rwth-aachen.de/volltexte/2020/13390/
Go to the corresponding LIPIcs Volume Portal

Bhaskar, Umang ; Kumar, Gunjan

Partial Function Extension with Applications to Learning and Property Testing

pdf-format:
LIPIcs-ISAAC-2020-46.pdf (0.5 MB)

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.

BibTeX - Entry

@InProceedings{bhaskar_et_al:LIPIcs:2020:13390,
  author =	{Umang Bhaskar and Gunjan Kumar},
  title =	{{Partial Function Extension with Applications to Learning and Property Testing}},
  booktitle =	{31st International Symposium on Algorithms and Computation (ISAAC 2020)},
  pages =	{46:1--46:16},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-173-3},
  ISSN =	{1868-8969},
  year =	{2020},
  volume =	{181},
  editor =	{Yixin Cao and Siu-Wing Cheng and Minming Li},
  publisher =	{Schloss Dagstuhl--Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/opus/volltexte/2020/13390},
  URN =		{urn:nbn:de:0030-drops-133906},
  doi =		{10.4230/LIPIcs.ISAAC.2020.46},
  annote =	{Keywords: Partial function extension, subadditivity, matroid rank, approximation algorithms, learning, property testing}
}

Keywords: Partial function extension, subadditivity, matroid rank, approximation algorithms, learning, property testing
Collection: 31st International Symposium on Algorithms and Computation (ISAAC 2020)
Issue Date: 2020
Date of publication: 04.12.2020

DROPS-Home | Fulltext Search | Imprint | Privacy Published by LZI