7 Search Results for "Vuong, Thuy-Duong"

Document
Track A: Algorithms, Complexity and Games
DOI: 10.4230/LIPIcs.ICALP.2024.11
Approximate Counting for Spin Systems in Sub-Quadratic Time

Authors: Konrad Anand, Weiming Feng, Graham Freifeld, Heng Guo, and Jiaheng Wang

Published in: LIPIcs, Volume 297, 51st International Colloquium on Automata, Languages, and Programming (ICALP 2024)

Abstract
We present two randomised approximate counting algorithms with Õ(n^{2-c}/ε²) running time for some constant c > 0 and accuracy ε: 1) for the hard-core model with fugacity λ on graphs with maximum degree Δ when λ = O(Δ^{-1.5-c₁}) where c₁ = c/(2-2c); 2) for spin systems with strong spatial mixing (SSM) on planar graphs with quadratic growth, such as ℤ². For the hard-core model, Weitz’s algorithm (STOC, 2006) achieves sub-quadratic running time when correlation decays faster than the neighbourhood growth, namely when λ = o(Δ^{-2}). Our first algorithm does not require this property and extends the range where sub-quadratic algorithms exist. Our second algorithm appears to be the first to achieve sub-quadratic running time up to the SSM threshold, albeit on a restricted family of graphs. It also extends to (not necessarily planar) graphs with polynomial growth, such as ℤ^d, but with a running time of the form Õ(n²ε^{-2}/2^{c(log n)^{1/d}}) where d is the exponent of the polynomial growth and c > 0 is some constant.
Cite as

Konrad Anand, Weiming Feng, Graham Freifeld, Heng Guo, and Jiaheng Wang. Approximate Counting for Spin Systems in Sub-Quadratic Time. In 51st International Colloquium on Automata, Languages, and Programming (ICALP 2024). Leibniz International Proceedings in Informatics (LIPIcs), Volume 297, pp. 11:1-11:20, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2024)

Copy BibTex To Clipboard

@InProceedings{anand_et_al:LIPIcs.ICALP.2024.11,
  author =	{Anand, Konrad and Feng, Weiming and Freifeld, Graham and Guo, Heng and Wang, Jiaheng},
  title =	{{Approximate Counting for Spin Systems in Sub-Quadratic Time}},
  booktitle =	{51st International Colloquium on Automata, Languages, and Programming (ICALP 2024)},
  pages =	{11:1--11:20},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-322-5},
  ISSN =	{1868-8969},
  year =	{2024},
  volume =	{297},
  editor =	{Bringmann, Karl and Grohe, Martin and Puppis, Gabriele and Svensson, Ola},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ICALP.2024.11},
  URN =		{urn:nbn:de:0030-drops-201543},
  doi =		{10.4230/LIPIcs.ICALP.2024.11},
  annote =	{Keywords: Randomised algorithm, Approximate counting, Spin system, Sub-quadratic algorithm}
}
Document
Track A: Algorithms, Complexity and Games
DOI: 10.4230/LIPIcs.ICALP.2024.37
Fast Approximate Counting of Cycles

Authors: Keren Censor-Hillel, Tomer Even, and Virginia Vassilevska Williams

Published in: LIPIcs, Volume 297, 51st International Colloquium on Automata, Languages, and Programming (ICALP 2024)

Abstract
We consider the problem of approximate counting of triangles and longer fixed length cycles in directed graphs. For triangles, Tětek [ICALP'22] gave an algorithm that returns a (1±ε)-approximation in Õ(n^ω/t^{ω-2}) time, where t is the unknown number of triangles in the given n node graph and ω < 2.372 is the matrix multiplication exponent. We obtain an improved algorithm whose running time is, within polylogarithmic factors the same as that for multiplying an n× n/t matrix by an n/t × n matrix. We then extend our framework to obtain the first nontrivial (1± ε)-approximation algorithms for the number of h-cycles in a graph, for any constant h ≥ 3. Our running time is Õ(MM(n,n/t^{1/(h-2)},n)), the time to multiply n × n/(t^{1/(h-2)}) by n/(t^{1/(h-2)) × n matrices. Finally, we show that under popular fine-grained hypotheses, this running time is optimal.
Cite as

Keren Censor-Hillel, Tomer Even, and Virginia Vassilevska Williams. Fast Approximate Counting of Cycles. In 51st International Colloquium on Automata, Languages, and Programming (ICALP 2024). Leibniz International Proceedings in Informatics (LIPIcs), Volume 297, pp. 37:1-37:20, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2024)

Copy BibTex To Clipboard

@InProceedings{censorhillel_et_al:LIPIcs.ICALP.2024.37,
  author =	{Censor-Hillel, Keren and Even, Tomer and Vassilevska Williams, Virginia},
  title =	{{Fast Approximate Counting of Cycles}},
  booktitle =	{51st International Colloquium on Automata, Languages, and Programming (ICALP 2024)},
  pages =	{37:1--37:20},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-322-5},
  ISSN =	{1868-8969},
  year =	{2024},
  volume =	{297},
  editor =	{Bringmann, Karl and Grohe, Martin and Puppis, Gabriele and Svensson, Ola},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ICALP.2024.37},
  URN =		{urn:nbn:de:0030-drops-201809},
  doi =		{10.4230/LIPIcs.ICALP.2024.37},
  annote =	{Keywords: Approximate triangle counting, Approximate cycle counting Fast matrix multiplication, Fast rectangular matrix multiplication}
}
Document
Track A: Algorithms, Complexity and Games
DOI: 10.4230/LIPIcs.ICALP.2024.62
An FPRAS for Two Terminal Reliability in Directed Acyclic Graphs

Authors: Weiming Feng and Heng Guo

Published in: LIPIcs, Volume 297, 51st International Colloquium on Automata, Languages, and Programming (ICALP 2024)

Abstract
We give a fully polynomial-time randomized approximation scheme (FPRAS) for two terminal reliability in directed acyclic graphs (DAGs). In contrast, we also show the complementing problem of approximating two terminal unreliability in DAGs is #BIS-hard.
Cite as

Weiming Feng and Heng Guo. An FPRAS for Two Terminal Reliability in Directed Acyclic Graphs. In 51st International Colloquium on Automata, Languages, and Programming (ICALP 2024). Leibniz International Proceedings in Informatics (LIPIcs), Volume 297, pp. 62:1-62:19, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2024)

Copy BibTex To Clipboard

@InProceedings{feng_et_al:LIPIcs.ICALP.2024.62,
  author =	{Feng, Weiming and Guo, Heng},
  title =	{{An FPRAS for Two Terminal Reliability in Directed Acyclic Graphs}},
  booktitle =	{51st International Colloquium on Automata, Languages, and Programming (ICALP 2024)},
  pages =	{62:1--62:19},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-322-5},
  ISSN =	{1868-8969},
  year =	{2024},
  volume =	{297},
  editor =	{Bringmann, Karl and Grohe, Martin and Puppis, Gabriele and Svensson, Ola},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ICALP.2024.62},
  URN =		{urn:nbn:de:0030-drops-202057},
  doi =		{10.4230/LIPIcs.ICALP.2024.62},
  annote =	{Keywords: Approximate counting, Network reliability, Sampling algorithm}
}
Document
Track A: Algorithms, Complexity and Games
DOI: 10.4230/LIPIcs.ICALP.2024.79
From Trees to Polynomials and Back Again: New Capacity Bounds with Applications to TSP

Authors: Leonid Gurvits, Nathan Klein, and Jonathan Leake

Published in: LIPIcs, Volume 297, 51st International Colloquium on Automata, Languages, and Programming (ICALP 2024)

Abstract
We give simply exponential lower bounds on the probabilities of a given strongly Rayleigh distribution, depending only on its expectation. This resolves a weak version of a problem left open by Karlin-Klein-Oveis Gharan in their recent breakthrough work on metric TSP, and this resolution leads to a minor improvement of their approximation factor for metric TSP. Our results also allow for a more streamlined analysis of the algorithm. To achieve these new bounds, we build upon the work of Gurvits-Leake on the use of the productization technique for bounding the capacity of a real stable polynomial. This technique allows one to reduce certain inequalities for real stable polynomials to products of affine linear forms, which have an underlying matrix structure. In this paper, we push this technique further by characterizing the worst-case polynomials via bipartitioned forests. This rigid combinatorial structure yields a clean induction argument, which implies our stronger bounds. In general, we believe the results of this paper will lead to further improvement and simplification of the analysis of various combinatorial and probabilistic bounds and algorithms.
Cite as

Leonid Gurvits, Nathan Klein, and Jonathan Leake. From Trees to Polynomials and Back Again: New Capacity Bounds with Applications to TSP. In 51st International Colloquium on Automata, Languages, and Programming (ICALP 2024). Leibniz International Proceedings in Informatics (LIPIcs), Volume 297, pp. 79:1-79:20, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2024)

Copy BibTex To Clipboard

@InProceedings{gurvits_et_al:LIPIcs.ICALP.2024.79,
  author =	{Gurvits, Leonid and Klein, Nathan and Leake, Jonathan},
  title =	{{From Trees to Polynomials and Back Again: New Capacity Bounds with Applications to TSP}},
  booktitle =	{51st International Colloquium on Automata, Languages, and Programming (ICALP 2024)},
  pages =	{79:1--79:20},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-322-5},
  ISSN =	{1868-8969},
  year =	{2024},
  volume =	{297},
  editor =	{Bringmann, Karl and Grohe, Martin and Puppis, Gabriele and Svensson, Ola},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ICALP.2024.79},
  URN =		{urn:nbn:de:0030-drops-202229},
  doi =		{10.4230/LIPIcs.ICALP.2024.79},
  annote =	{Keywords: traveling salesman problem, strongly Rayleigh distributions, polynomial capacity, probability lower bounds, combinatorial lower bounds}
}
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.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.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.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 Feng, Weiming
  • 2 Guo, Heng
  • 2 Vuong, Thuy-Duong
  • 1 Anand, Konrad
  • Show More...

  • Refine by Classification
  • 3 Mathematics of computing → Approximation algorithms
  • 2 Mathematics of computing → Graph algorithms
  • 2 Theory of computation → Randomness, geometry and discrete structures
  • 1 Mathematics of computing → Probability and statistics
  • 1 Networks → Network reliability
  • Show More...

  • Refine by Keyword
  • 2 Approximate counting
  • 1 Approximate cycle counting Fast matrix multiplication
  • 1 Approximate triangle counting
  • 1 Domain Sparsification
  • 1 Entropic Independence
  • Show More...

  • Refine by Type
  • 7 document

  • Refine by Publication Year
  • 4 2024
  • 1 2019
  • 1 2020
  • 1 2022

© 2023-2024 Schloss Dagstuhl – LZI GmbH Imprint Privacy Contact