4 Search Results for "Shah, Rikhav"

Document
DOI: 10.4230/LIPIcs.ITCS.2022.108
A Spectral Approach to Polytope Diameter

Authors: Hariharan Narayanan, Rikhav Shah, and Nikhil Srivastava

Published in: LIPIcs, Volume 215, 13th Innovations in Theoretical Computer Science Conference (ITCS 2022)

Abstract
We prove upper bounds on the graph diameters of polytopes in two settings. The first is a worst-case bound for integer polytopes in terms of the length of the description of the polytope (in bits) and the minimum angle between facets of its polar. The second is a smoothed analysis bound: given an appropriately normalized polytope, we add small Gaussian noise to each constraint. We consider a natural geometric measure on the vertices of the perturbed polytope (corresponding to the mean curvature measure of its polar) and show that with high probability there exists a "giant component" of vertices, with measure 1-o(1) and polynomial diameter. Both bounds rely on spectral gaps - of a certain Schrödinger operator in the first case, and a certain continuous time Markov chain in the second - which arise from the log-concavity of the volume of a simple polytope in terms of its slack variables.
Cite as

Hariharan Narayanan, Rikhav Shah, and Nikhil Srivastava. A Spectral Approach to Polytope Diameter. In 13th Innovations in Theoretical Computer Science Conference (ITCS 2022). Leibniz International Proceedings in Informatics (LIPIcs), Volume 215, pp. 108:1-108:22, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2022)

Copy BibTex To Clipboard

@InProceedings{narayanan_et_al:LIPIcs.ITCS.2022.108,
  author =	{Narayanan, Hariharan and Shah, Rikhav and Srivastava, Nikhil},
  title =	{{A Spectral Approach to Polytope Diameter}},
  booktitle =	{13th Innovations in Theoretical Computer Science Conference (ITCS 2022)},
  pages =	{108:1--108:22},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-217-4},
  ISSN =	{1868-8969},
  year =	{2022},
  volume =	{215},
  editor =	{Braverman, Mark},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.ITCS.2022.108},
  URN =		{urn:nbn:de:0030-drops-157044},
  doi =		{10.4230/LIPIcs.ITCS.2022.108},
  annote =	{Keywords: Polytope diameter, Markov Chain}
}
Document
RANDOM
DOI: 10.4230/LIPIcs.APPROX/RANDOM.2021.40
Smoothed Analysis of the Condition Number Under Low-Rank Perturbations

Authors: Rikhav Shah and Sandeep Silwal

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

Abstract
Let M be an arbitrary n by n matrix of rank n-k. We study the condition number of M plus a low-rank perturbation UV^T where U, V are n by k random Gaussian matrices. Under some necessary assumptions, it is shown that M+UV^T is unlikely to have a large condition number. The main advantages of this kind of perturbation over the well-studied dense Gaussian perturbation, where every entry is independently perturbed, is the O(nk) cost to store U,V and the O(nk) increase in time complexity for performing the matrix-vector multiplication (M+UV^T)x. This improves the Ω(n²) space and time complexity increase required by a dense perturbation, which is especially burdensome if M is originally sparse. Our results also extend to the case where U and V have rank larger than k and to symmetric and complex settings. We also give an application to linear systems solving and perform some numerical experiments. Lastly, barriers in applying low-rank noise to other problems studied in the smoothed analysis framework are discussed.
Cite as

Rikhav Shah and Sandeep Silwal. Smoothed Analysis of the Condition Number Under Low-Rank Perturbations. In Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2021). Leibniz International Proceedings in Informatics (LIPIcs), Volume 207, pp. 40:1-40:21, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2021)

Copy BibTex To Clipboard

@InProceedings{shah_et_al:LIPIcs.APPROX/RANDOM.2021.40,
  author =	{Shah, Rikhav and Silwal, Sandeep},
  title =	{{Smoothed Analysis of the Condition Number Under Low-Rank Perturbations}},
  booktitle =	{Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2021)},
  pages =	{40:1--40:21},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-207-5},
  ISSN =	{1868-8969},
  year =	{2021},
  volume =	{207},
  editor =	{Wootters, Mary and Sanit\`{a}, Laura},
  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.2021.40},
  URN =		{urn:nbn:de:0030-drops-147332},
  doi =		{10.4230/LIPIcs.APPROX/RANDOM.2021.40},
  annote =	{Keywords: Smoothed analysis, condition number, low rank noise}
}
Document
Track A: Algorithms, Complexity and Games
DOI: 10.4230/LIPIcs.ICALP.2020.98
Property Testing of LP-Type Problems

Authors: Rogers Epstein and Sandeep Silwal

Published in: LIPIcs, Volume 168, 47th International Colloquium on Automata, Languages, and Programming (ICALP 2020)

Abstract
Given query access to a set of constraints S, we wish to quickly check if some objective function φ subject to these constraints is at most a given value k. We approach this problem using the framework of property testing where our goal is to distinguish the case φ(S) ≤ k from the case that at least an ε fraction of the constraints in S need to be removed for φ(S) ≤ k to hold. We restrict our attention to the case where (S,φ) are LP-Type problems which is a rich family of combinatorial optimization problems with an inherent geometric structure. By utilizing a simple sampling procedure which has been used previously to study these problems, we are able to create property testers for any LP-Type problem whose query complexities are independent of the number of constraints. To the best of our knowledge, this is the first work that connects the area of LP-Type problems and property testing in a systematic way. Among our results are property testers for a variety of LP-Type problems that are new and also problems that have been studied previously such as a tight upper bound on the query complexity of testing clusterability with one cluster considered by Alon, Dar, Parnas, and Ron (FOCS 2000). We also supply a corresponding tight lower bound for this problem and other LP-Type problems using geometric constructions.
Cite as

Rogers Epstein and Sandeep Silwal. Property Testing of LP-Type Problems. In 47th International Colloquium on Automata, Languages, and Programming (ICALP 2020). Leibniz International Proceedings in Informatics (LIPIcs), Volume 168, pp. 98:1-98:18, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2020)

Copy BibTex To Clipboard

@InProceedings{epstein_et_al:LIPIcs.ICALP.2020.98,
  author =	{Epstein, Rogers and Silwal, Sandeep},
  title =	{{Property Testing of LP-Type Problems}},
  booktitle =	{47th International Colloquium on Automata, Languages, and Programming (ICALP 2020)},
  pages =	{98:1--98:18},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-138-2},
  ISSN =	{1868-8969},
  year =	{2020},
  volume =	{168},
  editor =	{Czumaj, Artur and Dawar, Anuj and Merelli, Emanuela},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.ICALP.2020.98},
  URN =		{urn:nbn:de:0030-drops-125056},
  doi =		{10.4230/LIPIcs.ICALP.2020.98},
  annote =	{Keywords: property pesting, LP-Type problems, random sampling}
}
Document
DOI: 10.4230/LIPIcs.ITCS.2020.69
Testing Properties of Multiple Distributions with Few Samples

Authors: Maryam Aliakbarpour and Sandeep Silwal

Published in: LIPIcs, Volume 151, 11th Innovations in Theoretical Computer Science Conference (ITCS 2020)

Abstract
We propose a new setting for testing properties of distributions while receiving samples from several distributions, but few samples per distribution. Given samples from s distributions, p_1, p_2, …, p_s, we design testers for the following problems: (1) Uniformity Testing: Testing whether all the p_i’s are uniform or ε-far from being uniform in ℓ_1-distance (2) Identity Testing: Testing whether all the p_i’s are equal to an explicitly given distribution q or ε-far from q in ℓ_1-distance, and (3) Closeness Testing: Testing whether all the p_i’s are equal to a distribution q which we have sample access to, or ε-far from q in ℓ_1-distance. By assuming an additional natural condition about the source distributions, we provide sample optimal testers for all of these problems.
Cite as

Maryam Aliakbarpour and Sandeep Silwal. Testing Properties of Multiple Distributions with Few Samples. In 11th Innovations in Theoretical Computer Science Conference (ITCS 2020). Leibniz International Proceedings in Informatics (LIPIcs), Volume 151, pp. 69:1-69:41, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2020)

Copy BibTex To Clipboard

@InProceedings{aliakbarpour_et_al:LIPIcs.ITCS.2020.69,
  author =	{Aliakbarpour, Maryam and Silwal, Sandeep},
  title =	{{Testing Properties of Multiple Distributions with Few Samples}},
  booktitle =	{11th Innovations in Theoretical Computer Science Conference (ITCS 2020)},
  pages =	{69:1--69:41},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-134-4},
  ISSN =	{1868-8969},
  year =	{2020},
  volume =	{151},
  editor =	{Vidick, Thomas},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.ITCS.2020.69},
  URN =		{urn:nbn:de:0030-drops-117545},
  doi =		{10.4230/LIPIcs.ITCS.2020.69},
  annote =	{Keywords: Hypothesis Testing, Property Testing, Distribution Testing, Identity Testing, Closeness Testing, Multiple Sources}
}
  • Refine by Author
  • 3 Silwal, Sandeep
  • 2 Shah, Rikhav
  • 1 Aliakbarpour, Maryam
  • 1 Epstein, Rogers
  • 1 Narayanan, Hariharan
  • Show More...

  • Refine by Classification
  • 1 Mathematics of computing → Hypothesis testing and confidence interval computation
  • 1 Mathematics of computing → Mathematical optimization
  • 1 Mathematics of computing → Numerical analysis
  • 1 Theory of computation → Design and analysis of algorithms
  • 1 Theory of computation → Random walks and Markov chains
  • Show More...

  • Refine by Keyword
  • 1 Closeness Testing
  • 1 Distribution Testing
  • 1 Hypothesis Testing
  • 1 Identity Testing
  • 1 LP-Type problems
  • Show More...

  • Refine by Type
  • 4 document

  • Refine by Publication Year
  • 2 2020
  • 1 2021
  • 1 2022

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