5 Search Results for "Shah, Rikhav"

Document

DOI: 10.4230/LIPIcs.FUN.2024.29

Achieving the Highest Possible Elo Rating

Authors: Rikhav Shah

Published in: LIPIcs, Volume 291, 12th International Conference on Fun with Algorithms (FUN 2024)

Abstract

Elo rating systems measure the approximate skill of each competitor in a game or sport. A competitor’s rating increases when they win and decreases when they lose. Increasing one’s rating can be difficult work; one must hone their skills and consistently beat the competition. Alternatively, with enough money you can rig the outcome of games to boost your rating. This paper poses a natural question for Elo rating systems: say you manage to get together n people (including yourself) and acquire enough money to rig k games. How high can you get your rating, asymptotically in k? In this setting, the people you gathered aren't very interested in the game, and will only play if you pay them to. This paper resolves the question for n = 2 up to constant additive error, and provides close upper and lower bounds for all other n, including for n growing arbitrarily with k. There is a phase transition at n = k^{1/3}: there is a huge increase in the highest possible Elo rating from n = 2 to n = k^{1/3}, but (depending on the particular Elo system used) little-to-no increase for any higher n. Past the transition point n > k^{1/3}, the highest possible Elo is at least Θ(k^{1/3}). The corresponding upper bound depends on the particular system used, but for the standard Elo system, is Θ(k^{1/3}log(k)^{1/3}).

Cite as

Rikhav Shah. Achieving the Highest Possible Elo Rating. In 12th International Conference on Fun with Algorithms (FUN 2024). Leibniz International Proceedings in Informatics (LIPIcs), Volume 291, pp. 29:1-29:21, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2024)

Copy BibTex To Clipboard

@InProceedings{shah:LIPIcs.FUN.2024.29,
  author =	{Shah, Rikhav},
  title =	{{Achieving the Highest Possible Elo Rating}},
  booktitle =	{12th International Conference on Fun with Algorithms (FUN 2024)},
  pages =	{29:1--29:21},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-314-0},
  ISSN =	{1868-8969},
  year =	{2024},
  volume =	{291},
  editor =	{Broder, Andrei Z. and Tamir, Tami},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.FUN.2024.29},
  URN =		{urn:nbn:de:0030-drops-199376},
  doi =		{10.4230/LIPIcs.FUN.2024.29},
  annote =	{Keywords: Elo, rating system, monotonic invariant, Euler’s method, mass movement}
}

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.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.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.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.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 Shah, Rikhav
3 Silwal, Sandeep
1 Aliakbarpour, Maryam
1 Epstein, Rogers
1 Narayanan, Hariharan
Show More...

Refine by Classification
1 Mathematics of computing → Combinatorics
1 Mathematics of computing → Discrete mathematics
1 Mathematics of computing → Hypothesis testing and confidence interval computation
1 Mathematics of computing → Mathematical optimization
1 Mathematics of computing → Numerical analysis
Show More...

Refine by Keyword
1 Closeness Testing
1 Distribution Testing
1 Elo
1 Euler’s method
1 Hypothesis Testing
Show More...

Refine by Type
5 document

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