5 Search Results for "Kumar, Rohit"

Document
DOI: 10.4230/OASIcs.FAB.2021.3
DAISIM: A Computational Simulator for the MakerDAO Stablecoin

Authors: Shreyas Bhat, Ayten Betul Kahya, Bhaskar Krishnamachari, and Rohit Kumar

Published in: OASIcs, Volume 92, 4th International Symposium on Foundations and Applications of Blockchain 2021 (FAB 2021)

Abstract
We present a computational simulation of the single-collateral DAI stablecoin launched by the MakerDAO project in 2017. At the core of the simulation is a model of cryptocurrency investors acting as rational Markowitz mean-variance portfolio optimizers, with heterogeneous risk tolerance. The simulator, called DAISIM, incorporates automated order matching and price update mechanisms to determine the DAI price. We use the simulator to evaluate how the single-collateral DAI price, as well as portfolio allocations, vary for a given population of investors as a function of exogenous parameters such as the price of ETH and various system parameters including stability rate and transaction fee. DAISIM is being made available as open-source and may be useful in evaluating other similar projects.
Cite as

Shreyas Bhat, Ayten Betul Kahya, Bhaskar Krishnamachari, and Rohit Kumar. DAISIM: A Computational Simulator for the MakerDAO Stablecoin. In 4th International Symposium on Foundations and Applications of Blockchain 2021 (FAB 2021). Open Access Series in Informatics (OASIcs), Volume 92, pp. 3:1-3:13, Schloss Dagstuhl - Leibniz-Zentrum für Informatik (2021)

Copy BibTex To Clipboard

@InProceedings{bhat_et_al:OASIcs.FAB.2021.3,
  author =	{Bhat, Shreyas and Kahya, Ayten Betul and Krishnamachari, Bhaskar and Kumar, Rohit},
  title =	{{DAISIM: A Computational Simulator for the MakerDAO Stablecoin}},
  booktitle =	{4th International Symposium on Foundations and Applications of Blockchain 2021 (FAB 2021)},
  pages =	{3:1--3:13},
  series =	{Open Access Series in Informatics (OASIcs)},
  ISBN =	{978-3-95977-196-2},
  ISSN =	{2190-6807},
  year =	{2021},
  volume =	{92},
  editor =	{Gramoli, Vincent and Sadoghi, Mohammad},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/OASIcs.FAB.2021.3},
  URN =		{urn:nbn:de:0030-drops-139899},
  doi =		{10.4230/OASIcs.FAB.2021.3},
  annote =	{Keywords: Stablecoin, Simulator, MakerDAO}
}
Document
RANDOM
DOI: 10.4230/LIPIcs.APPROX/RANDOM.2020.8
Polynomial Identity Testing for Low Degree Polynomials with Optimal Randomness

Authors: Markus Bläser and Anurag Pandey

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

Abstract
We give a randomized polynomial time algorithm for polynomial identity testing for the class of n-variate poynomials of degree bounded by d over a field 𝔽, in the blackbox setting. Our algorithm works for every field 𝔽 with | 𝔽 | ≥ d+1, and uses only d log n + log (1/ ε) + O(d log log n) random bits to achieve a success probability 1 - ε for some ε > 0. In the low degree regime that is d ≪ n, it hits the information theoretic lower bound and differs from it only in the lower order terms. Previous best known algorithms achieve the number of random bits (Guruswami-Xing, CCC'14 and Bshouty, ITCS'14) that are constant factor away from our bound. Like Bshouty, we use Sidon sets for our algorithm. However, we use a new construction of Sidon sets to achieve the improved bound. We also collect two simple constructions of hitting sets with information theoretically optimal size against the class of n-variate, degree d polynomials. Our contribution is that we give new, very simple proofs for both the constructions.
Cite as

Markus Bläser and Anurag Pandey. Polynomial Identity Testing for Low Degree Polynomials with Optimal Randomness. In Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2020). Leibniz International Proceedings in Informatics (LIPIcs), Volume 176, pp. 8:1-8:13, Schloss Dagstuhl - Leibniz-Zentrum für Informatik (2020)

Copy BibTex To Clipboard

@InProceedings{blaser_et_al:LIPIcs.APPROX/RANDOM.2020.8,
  author =	{Bl\"{a}ser, Markus and Pandey, Anurag},
  title =	{{Polynomial Identity Testing for Low Degree Polynomials with Optimal Randomness}},
  booktitle =	{Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2020)},
  pages =	{8:1--8:13},
  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.8},
  URN =		{urn:nbn:de:0030-drops-126112},
  doi =		{10.4230/LIPIcs.APPROX/RANDOM.2020.8},
  annote =	{Keywords: Algebraic Complexity theory, Polynomial Identity Testing, Hitting Set, Pseudorandomness}
}
Document
DOI: 10.4230/LIPIcs.CCC.2020.5
Lower Bounds for Matrix Factorization

Authors: Mrinal Kumar and Ben Lee Volk

Published in: LIPIcs, Volume 169, 35th Computational Complexity Conference (CCC 2020)

Abstract
We study the problem of constructing explicit families of matrices which cannot be expressed as a product of a few sparse matrices. In addition to being a natural mathematical question on its own, this problem appears in various incarnations in computer science; the most significant being in the context of lower bounds for algebraic circuits which compute linear transformations, matrix rigidity and data structure lower bounds. We first show, for every constant d, a deterministic construction in time exp(n^(1-Ω(1/d))) of a family {M_n} of n × n matrices which cannot be expressed as a product M_n = A_1 ⋯ A_d where the total sparsity of A_1,…,A_d is less than n^(1+1/(2d)). In other words, any depth-d linear circuit computing the linear transformation M_n⋅ 𝐱 has size at least n^(1+Ω(1/d)). This improves upon the prior best lower bounds for this problem, which are barely super-linear, and were obtained by a long line of research based on the study of super-concentrators (albeit at the cost of a blow up in the time required to construct these matrices). We then outline an approach for proving improved lower bounds through a certain derandomization problem, and use this approach to prove asymptotically optimal quadratic lower bounds for natural special cases, which generalize many of the common matrix decompositions.
Cite as

Mrinal Kumar and Ben Lee Volk. Lower Bounds for Matrix Factorization. In 35th Computational Complexity Conference (CCC 2020). Leibniz International Proceedings in Informatics (LIPIcs), Volume 169, pp. 5:1-5:20, Schloss Dagstuhl - Leibniz-Zentrum für Informatik (2020)

Copy BibTex To Clipboard

@InProceedings{kumar_et_al:LIPIcs.CCC.2020.5,
  author =	{Kumar, Mrinal and Volk, Ben Lee},
  title =	{{Lower Bounds for Matrix Factorization}},
  booktitle =	{35th Computational Complexity Conference (CCC 2020)},
  pages =	{5:1--5:20},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-156-6},
  ISSN =	{1868-8969},
  year =	{2020},
  volume =	{169},
  editor =	{Saraf, Shubhangi},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.CCC.2020.5},
  URN =		{urn:nbn:de:0030-drops-125578},
  doi =		{10.4230/LIPIcs.CCC.2020.5},
  annote =	{Keywords: Algebraic Complexity, Linear Circuits, Matrix Factorization, Lower Bounds}
}
Document
DOI: 10.4230/LIPIcs.FSTTCS.2009.2324
Approximating Fault-Tolerant Group-Steiner Problems

Authors: Rohit Khandekar, Guy Kortsarz, and Zeev Nutov

Published in: LIPIcs, Volume 4, IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (2009)

Abstract
In this paper, we initiate the study of designing approximation algorithms for {\sf Fault-Tolerant Group-Steiner} ({\sf FTGS}) problems. The motivation is to protect the well-studied group-Steiner networks from edge or vertex failures. In {\sf Fault-Tolerant Group-Steiner} problems, we are given a graph with edge- (or vertex-) costs, a root vertex, and a collection of subsets of vertices called groups. The objective is to find a minimum-cost subgraph that has two edge- (or vertex-) disjoint paths from each group to the root. We present approximation algorithms and hardness results for several variants of this basic problem, e.g., edge-costs vs. vertex-costs, edge-connectivity vs. vertex-connectivity, and $2$-connecting from each group a single vertex vs. many vertices. Main contributions of our paper include the introduction of very general structural lemmas on connectivity and a charging scheme that may find more applications in the future. Our algorithmic results are supplemented by inapproximability results, which are tight in some cases. Our algorithms employ a variety of techniques. For the edge-connectivity variant, we use a primal-dual based algorithm for covering an {\em uncros\-sable} set-family, while for the vertex-connectivity version, we prove a new graph-theoretic lemma that shows equivalence between obtaining two vertex-disjoint paths from two vertices and $2$-connecting a carefully chosen single vertex. To handle large group-sizes, we use a $p$-Steiner tree algorithm to identify the ``correct'' pair of terminals from each group to be connected to the root. We also use a non-trivial charging scheme to improve the approximation ratio for the most general problem we consider.
Cite as

Rohit Khandekar, Guy Kortsarz, and Zeev Nutov. Approximating Fault-Tolerant Group-Steiner Problems. In IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science. Leibniz International Proceedings in Informatics (LIPIcs), Volume 4, pp. 263-274, Schloss Dagstuhl - Leibniz-Zentrum für Informatik (2009)

Copy BibTex To Clipboard

@InProceedings{khandekar_et_al:LIPIcs.FSTTCS.2009.2324,
  author =	{Khandekar, Rohit and Kortsarz, Guy and Nutov, Zeev},
  title =	{{Approximating Fault-Tolerant Group-Steiner Problems}},
  booktitle =	{IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science},
  pages =	{263--274},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-939897-13-2},
  ISSN =	{1868-8969},
  year =	{2009},
  volume =	{4},
  editor =	{Kannan, Ravi and Narayan Kumar, K.},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.FSTTCS.2009.2324},
  URN =		{urn:nbn:de:0030-drops-23243},
  doi =		{10.4230/LIPIcs.FSTTCS.2009.2324},
  annote =	{Keywords: Fault-tolerance, group Steiner problem, edge-disjointness, vertex-disjointness, approximation, connectivity}
}
Document
DOI: 10.4230/LIPIcs.FSTTCS.2009.2325
Bounded Size Graph Clustering with Applications to Stream Processing

Authors: Rohit Khandekar, Kirsten Hildrum, Sujay Parekh, Deepak Rajan, Jay Sethuraman, and Joel Wolf

Published in: LIPIcs, Volume 4, IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (2009)

Abstract
We introduce a graph clustering problem motivated by a stream processing application. Input to our problem is an undirected graph with vertex and edge weights. A cluster is a subset of the vertices. The {\em size} of a cluster is defined as the total vertex weight in the subset plus the total edge weight at the boundary of the cluster. The bounded size graph clustering problem ($\GC$) is to partition the vertices into clusters of size at most a given budget and minimize the total edge-weight across the clusters. In the {\em multiway cut} version of the problem, we are also given a subset of vertices called {\em terminals}. No cluster is allowed to contain more than one terminal. Our problem differs from most of the previously studied clustering problems in that the number of clusters is not specified. We first show that the feasibility version of the multiway cut $\GC$ problem, i.e., determining if there exists a clustering with bounded-size clusters satisfying the multiway cut constraint, can be solved in polynomial time. Our algorithm is based on the min-cut subroutine and an uncrossing argument. This result is in contrast with the NP-hardness of the min-max multiway cut problem, considered by Svitkina and Tardos (2004), in which the number of clusters must equal the number of terminals. Our results for the feasibility version also generalize to any symmetric submodular function. We next show that the optimization version of $\GC$ is NP-hard by showing an approximation-preserving reduction from the $\frac 13$-balanced cut problem. Our main result is an $O(\log^2 n)$-approximation to the optimization version of the multiway cut $\GC$ problem violating the budget by an $O(\log n)$ factor, where $n$ denotes the number of vertices. Our algorithm is based on a set-cover-like greedy approach which iteratively computes bounded-size clusters to maximize the number of new vertices covered.
Cite as

Rohit Khandekar, Kirsten Hildrum, Sujay Parekh, Deepak Rajan, Jay Sethuraman, and Joel Wolf. Bounded Size Graph Clustering with Applications to Stream Processing. In IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science. Leibniz International Proceedings in Informatics (LIPIcs), Volume 4, pp. 275-286, Schloss Dagstuhl - Leibniz-Zentrum für Informatik (2009)

Copy BibTex To Clipboard

@InProceedings{khandekar_et_al:LIPIcs.FSTTCS.2009.2325,
  author =	{Khandekar, Rohit and Hildrum, Kirsten and Parekh, Sujay and Rajan, Deepak and Sethuraman, Jay and Wolf, Joel},
  title =	{{Bounded Size Graph Clustering with Applications to Stream Processing}},
  booktitle =	{IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science},
  pages =	{275--286},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-939897-13-2},
  ISSN =	{1868-8969},
  year =	{2009},
  volume =	{4},
  editor =	{Kannan, Ravi and Narayan Kumar, K.},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.FSTTCS.2009.2325},
  URN =		{urn:nbn:de:0030-drops-23250},
  doi =		{10.4230/LIPIcs.FSTTCS.2009.2325},
  annote =	{Keywords: Graph partitioning, uncrossing, Gomory-Hu trees, symmetric submodular functions}
}
  • Refine by Author
  • 2 Khandekar, Rohit
  • 1 Bhat, Shreyas
  • 1 Bläser, Markus
  • 1 Hildrum, Kirsten
  • 1 Kahya, Ayten Betul
  • Show More...

  • Refine by Classification
  • 2 Theory of computation → Algebraic complexity theory
  • 1 Applied computing → Digital cash
  • 1 Theory of computation → Circuit complexity

  • Refine by Keyword
  • 1 Algebraic Complexity
  • 1 Algebraic Complexity theory
  • 1 Fault-tolerance
  • 1 Gomory-Hu trees
  • 1 Graph partitioning
  • Show More...

  • Refine by Type
  • 5 document

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

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 Schloss Dagstuhl - LZI GmbH Imprint Privacy Contact