2 Search Results for "Bommireddi, Abhinav"

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-dev.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-dev.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}
}
  • Refine by Author
  • 2 Blais, Eric
  • 2 Bommireddi, Abhinav

  • Refine by Classification
  • 1 Theory of computation → Streaming, sublinear and near linear time algorithms

  • Refine by Keyword
  • 1 Convex hull test
  • 1 Convexity
  • 1 Intersecting cones
  • 1 Line segment test
  • 1 Property testing
  • Show More...

  • Refine by Type
  • 2 document

  • Refine by Publication Year
  • 1 2017
  • 1 2020

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