DROPS

Document

RANDOM

DOI: 10.4230/LIPIcs.APPROX/RANDOM.2020.18

On Testing and Robust Characterizations of Convexity

Authors: Eric Blais and Abhinav Bommireddi

Published in: LIPIcs, Volume 176, Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2020)

Abstract

A body K ⊂ ℝⁿ is convex if and only if the line segment between any two points in K is completely contained within K or, equivalently, if and only if the convex hull of a set of points in K is contained within K. We show that neither of those characterizations of convexity are robust: there are bodies in ℝⁿ that are far from convex - in the sense that the volume of the symmetric difference between the set K and any convex set C is a constant fraction of the volume of K - for which a line segment between two randomly chosen points x,y ∈ K or the convex hull of a random set X of points in K is completely contained within K except with exponentially small probability. These results show that any algorithms for testing convexity based on the natural line segment and convex hull tests have exponential query complexity.

Cite as

Eric Blais and Abhinav Bommireddi. On Testing and Robust Characterizations of Convexity. In Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2020). Leibniz International Proceedings in Informatics (LIPIcs), Volume 176, pp. 18:1-18:15, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2020)

Copy BibTex To Clipboard

@InProceedings{blais_et_al:LIPIcs.APPROX/RANDOM.2020.18,
  author =	{Blais, Eric and Bommireddi, Abhinav},
  title =	{{On Testing and Robust Characterizations of Convexity}},
  booktitle =	{Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2020)},
  pages =	{18:1--18:15},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-164-1},
  ISSN =	{1868-8969},
  year =	{2020},
  volume =	{176},
  editor =	{Byrka, Jaros{\l}aw and Meka, Raghu},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.APPROX/RANDOM.2020.18},
  URN =		{urn:nbn:de:0030-drops-126214},
  doi =		{10.4230/LIPIcs.APPROX/RANDOM.2020.18},
  annote =	{Keywords: Convexity, Line segment test, Convex hull test, Intersecting cones}
}

Document

DOI: 10.4230/LIPIcs.ITCS.2017.33

Testing Submodularity and Other Properties of Valuation Functions

Authors: Eric Blais and Abhinav Bommireddi

Published in: LIPIcs, Volume 67, 8th Innovations in Theoretical Computer Science Conference (ITCS 2017)

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.

Cite as

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)

Copy BibTex To Clipboard

@InProceedings{blais_et_al:LIPIcs.ITCS.2017.33,
  author =	{Blais, Eric and Bommireddi, Abhinav},
  title =	{{Testing Submodularity and Other Properties of Valuation Functions}},
  booktitle =	{8th Innovations in Theoretical Computer Science Conference (ITCS 2017)},
  pages =	{33:1--33:17},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-029-3},
  ISSN =	{1868-8969},
  year =	{2017},
  volume =	{67},
  editor =	{Papadimitriou, Christos H.},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ITCS.2017.33},
  URN =		{urn:nbn:de:0030-drops-81619},
  doi =		{10.4230/LIPIcs.ITCS.2017.33},
  annote =	{Keywords: Property testing, Testing by implicit learning, Self-bounding functions}
}

Search Results

Documents authored by Bommireddi, Abhinav

On Testing and Robust Characterizations of Convexity

Abstract

Cite as

Testing Submodularity and Other Properties of Valuation Functions

Abstract

Cite as

Thanks for your feedback!

Could not send message