3 Search Results for "Vuong, Thuy-Duong"

Document
DOI: 10.4230/LIPIcs.ITCS.2022.5
Domain Sparsification of Discrete Distributions Using Entropic Independence

Authors: Nima Anari, Michał Dereziński, Thuy-Duong Vuong, and Elizabeth Yang

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

Abstract
We present a framework for speeding up the time it takes to sample from discrete distributions μ defined over subsets of size k of a ground set of n elements, in the regime where k is much smaller than n. We show that if one has access to estimates of marginals P_{S∼ μ} {i ∈ S}, then the task of sampling from μ can be reduced to sampling from related distributions ν supported on size k subsets of a ground set of only n^{1-α}⋅ poly(k) elements. Here, 1/α ∈ [1, k] is the parameter of entropic independence for μ. Further, our algorithm only requires sparsified distributions ν that are obtained by applying a sparse (mostly 0) external field to μ, an operation that for many distributions μ of interest, retains algorithmic tractability of sampling from ν. This phenomenon, which we dub domain sparsification, allows us to pay a one-time cost of estimating the marginals of μ, and in return reduce the amortized cost needed to produce many samples from the distribution μ, as is often needed in upstream tasks such as counting and inference. For a wide range of distributions where α = Ω(1), our result reduces the domain size, and as a corollary, the cost-per-sample, by a poly(n) factor. Examples include monomers in a monomer-dimer system, non-symmetric determinantal point processes, and partition-constrained Strongly Rayleigh measures. Our work significantly extends the reach of prior work of Anari and Dereziński who obtained domain sparsification for distributions with a log-concave generating polynomial (corresponding to α = 1). As a corollary of our new analysis techniques, we also obtain a less stringent requirement on the accuracy of marginal estimates even for the case of log-concave polynomials; roughly speaking, we show that constant-factor approximation is enough for domain sparsification, improving over O(1/k) relative error established in prior work.
Cite as

Nima Anari, Michał Dereziński, Thuy-Duong Vuong, and Elizabeth Yang. Domain Sparsification of Discrete Distributions Using Entropic Independence. In 13th Innovations in Theoretical Computer Science Conference (ITCS 2022). Leibniz International Proceedings in Informatics (LIPIcs), Volume 215, pp. 5:1-5:23, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2022)

Copy BibTex To Clipboard

@InProceedings{anari_et_al:LIPIcs.ITCS.2022.5,
  author =	{Anari, Nima and Derezi\'{n}ski, Micha{\l} and Vuong, Thuy-Duong and Yang, Elizabeth},
  title =	{{Domain Sparsification of Discrete Distributions Using Entropic Independence}},
  booktitle =	{13th Innovations in Theoretical Computer Science Conference (ITCS 2022)},
  pages =	{5:1--5:23},
  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.5},
  URN =		{urn:nbn:de:0030-drops-156013},
  doi =		{10.4230/LIPIcs.ITCS.2022.5},
  annote =	{Keywords: Domain Sparsification, Markov Chains, Sampling, Entropic Independence}
}
Document
APPROX
DOI: 10.4230/LIPIcs.APPROX/RANDOM.2020.56
An Extension of Plücker Relations with Applications to Subdeterminant Maximization

Authors: Nima Anari and Thuy-Duong Vuong

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

Abstract
Given a matrix A and k ≥ 0, we study the problem of finding the k × k submatrix of A with the maximum determinant in absolute value. This problem is motivated by the question of computing the determinant-based lower bound of cite{LSV86} on hereditary discrepancy, which was later shown to be an approximate upper bound as well [Matoušek, 2013]. The special case where k coincides with one of the dimensions of A has been extensively studied. Nikolov gave a 2^{O(k)}-approximation algorithm for this special case, matching known lower bounds; he also raised as an open problem the question of designing approximation algorithms for the general case. We make progress towards answering this question by giving the first efficient approximation algorithm for general k× k subdeterminant maximization with an approximation ratio that depends only on k. Our algorithm finds a k^{O(k)}-approximate solution by performing a simple local search. Our main technical contribution, enabling the analysis of the approximation ratio, is an extension of Plücker relations for the Grassmannian, which may be of independent interest; Plücker relations are quadratic polynomial equations involving the set of k× k subdeterminants of a k× n matrix. We find an extension of these relations to k× k subdeterminants of general m× n matrices.
Cite as

Nima Anari and Thuy-Duong Vuong. An Extension of Plücker Relations with Applications to Subdeterminant Maximization. In Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2020). Leibniz International Proceedings in Informatics (LIPIcs), Volume 176, pp. 56:1-56:16, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2020)

Copy BibTex To Clipboard

@InProceedings{anari_et_al:LIPIcs.APPROX/RANDOM.2020.56,
  author =	{Anari, Nima and Vuong, Thuy-Duong},
  title =	{{An Extension of Pl\"{u}cker Relations with Applications to Subdeterminant Maximization}},
  booktitle =	{Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2020)},
  pages =	{56:1--56:16},
  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.56},
  URN =		{urn:nbn:de:0030-drops-126596},
  doi =		{10.4230/LIPIcs.APPROX/RANDOM.2020.56},
  annote =	{Keywords: Pl\"{u}cker relations, determinant maximization, local search, exchange property, discrete concavity, discrepancy}
}
Document
Track A: Algorithms, Complexity and Games
DOI: 10.4230/LIPIcs.ICALP.2019.46
Approximation Algorithms for Min-Distance Problems

Authors: Mina Dalirrooyfard, Virginia Vassilevska Williams, Nikhil Vyas, Nicole Wein, Yinzhan Xu, and Yuancheng Yu

Published in: LIPIcs, Volume 132, 46th International Colloquium on Automata, Languages, and Programming (ICALP 2019)

Abstract
We study fundamental graph parameters such as the Diameter and Radius in directed graphs, when distances are measured using a somewhat unorthodox but natural measure: the distance between u and v is the minimum of the shortest path distances from u to v and from v to u. The center node in a graph under this measure can for instance represent the optimal location for a hospital to ensure the fastest medical care for everyone, as one can either go to the hospital, or a doctor can be sent to help. By computing All-Pairs Shortest Paths, all pairwise distances and thus the parameters we study can be computed exactly in O~(mn) time for directed graphs on n vertices, m edges and nonnegative edge weights. Furthermore, this time bound is tight under the Strong Exponential Time Hypothesis [Roditty-Vassilevska W. STOC 2013] so it is natural to study how well these parameters can be approximated in O(mn^{1-epsilon}) time for constant epsilon>0. Abboud, Vassilevska Williams, and Wang [SODA 2016] gave a polynomial factor approximation for Diameter and Radius, as well as a constant factor approximation for both problems in the special case where the graph is a DAG. We greatly improve upon these bounds by providing the first constant factor approximations for Diameter, Radius and the related Eccentricities problem in general graphs. Additionally, we provide a hierarchy of algorithms for Diameter that gives a time/accuracy trade-off.
Cite as

Mina Dalirrooyfard, Virginia Vassilevska Williams, Nikhil Vyas, Nicole Wein, Yinzhan Xu, and Yuancheng Yu. Approximation Algorithms for Min-Distance Problems. In 46th International Colloquium on Automata, Languages, and Programming (ICALP 2019). Leibniz International Proceedings in Informatics (LIPIcs), Volume 132, pp. 46:1-46:14, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2019)

Copy BibTex To Clipboard

@InProceedings{dalirrooyfard_et_al:LIPIcs.ICALP.2019.46,
  author =	{Dalirrooyfard, Mina and Williams, Virginia Vassilevska and Vyas, Nikhil and Wein, Nicole and Xu, Yinzhan and Yu, Yuancheng},
  title =	{{Approximation Algorithms for Min-Distance Problems}},
  booktitle =	{46th International Colloquium on Automata, Languages, and Programming (ICALP 2019)},
  pages =	{46:1--46:14},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-109-2},
  ISSN =	{1868-8969},
  year =	{2019},
  volume =	{132},
  editor =	{Baier, Christel and Chatzigiannakis, Ioannis and Flocchini, Paola and Leonardi, Stefano},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.ICALP.2019.46},
  URN =		{urn:nbn:de:0030-drops-106223},
  doi =		{10.4230/LIPIcs.ICALP.2019.46},
  annote =	{Keywords: fine-grained complexity, graph algorithms, diameter, radius, eccentricities}
}
  • Refine by Author
  • 2 Anari, Nima
  • 2 Vuong, Thuy-Duong
  • 1 Dalirrooyfard, Mina
  • 1 Dereziński, Michał
  • 1 Vyas, Nikhil
  • Show More...

  • Refine by Classification
  • 1 Mathematics of computing → Graph algorithms
  • 1 Theory of computation → Approximation algorithms analysis
  • 1 Theory of computation → Random walks and Markov chains
  • 1 Theory of computation → Randomized local search
  • 1 Theory of computation → Randomness, geometry and discrete structures
  • Show More...

  • Refine by Keyword
  • 1 Domain Sparsification
  • 1 Entropic Independence
  • 1 Markov Chains
  • 1 Plücker relations
  • 1 Sampling
  • Show More...

  • Refine by Type
  • 3 document

  • Refine by Publication Year
  • 1 2019
  • 1 2020
  • 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