Search Results

Documents authored by N, Vishvajeet

Document
DOI: 10.4230/LIPIcs.ITCS.2025.57
Deterministic Approximation for the Volume of the Truncated Fractional Matching Polytope

Authors: Heng Guo and Vishvajeet N

Published in: LIPIcs, Volume 325, 16th Innovations in Theoretical Computer Science Conference (ITCS 2025)

Abstract
We give a deterministic polynomial-time approximation scheme (FPTAS) for the volume of the truncated fractional matching polytope for graphs of maximum degree Δ, where the truncation is by restricting each variable to the interval [0,(1+δ)/Δ], and δ ≤ C/Δ for some constant C > 0. We also generalise our result to the fractional matching polytope for hypergraphs of maximum degree Δ and maximum hyperedge size k, truncated by [0,(1+δ)/Δ] as well, where δ ≤ CΔ^{-(2k-3)/(k-1)}k^{-1} for some constant C > 0. The latter result generalises both the first result for graphs (when k = 2), and a result by Bencs and Regts (2024) for the truncated independence polytope (when Δ = 2). Our approach is based on the cluster expansion technique.
Cite as

Heng Guo and Vishvajeet N. Deterministic Approximation for the Volume of the Truncated Fractional Matching Polytope. In 16th Innovations in Theoretical Computer Science Conference (ITCS 2025). Leibniz International Proceedings in Informatics (LIPIcs), Volume 325, pp. 57:1-57:14, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2025)

Copy BibTex To Clipboard

@InProceedings{guo_et_al:LIPIcs.ITCS.2025.57,
  author =	{Guo, Heng and N, Vishvajeet},
  title =	{{Deterministic Approximation for the Volume of the Truncated Fractional Matching Polytope}},
  booktitle =	{16th Innovations in Theoretical Computer Science Conference (ITCS 2025)},
  pages =	{57:1--57:14},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-361-4},
  ISSN =	{1868-8969},
  year =	{2025},
  volume =	{325},
  editor =	{Meka, Raghu},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ITCS.2025.57},
  URN =		{urn:nbn:de:0030-drops-226858},
  doi =		{10.4230/LIPIcs.ITCS.2025.57},
  annote =	{Keywords: deterministic volume computation, cluster expansion, explicit polytopes}
}
Document
RANDOM
DOI: 10.4230/LIPIcs.APPROX/RANDOM.2023.52
Extracting Mergers and Projections of Partitions

Authors: Swastik Kopparty and Vishvajeet N

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

Abstract
We study the problem of extracting randomness from somewhere-random sources, and related combinatorial phenomena: partition analogues of Shearer’s lemma on projections. A somewhere-random source is a tuple (X_1, …, X_t) of (possibly correlated) {0,1}ⁿ-valued random variables X_i where for some unknown i ∈ [t], X_i is guaranteed to be uniformly distributed. An extracting merger is a seeded device that takes a somewhere-random source as input and outputs nearly uniform random bits. We study the seed-length needed for extracting mergers with constant t and constant error. Since a somewhere-random source has min-entropy at least n, a standard extractor can also serve as an extracting merger. Our goal is to understand whether the further structure of being somewhere-random rather than just having high entropy enables smaller seed-length, and towards this we show: - Just like in the case of standard extractors, seedless extracting mergers with even just one output bit do not exist. - Unlike the case of standard extractors, it is possible to have extracting mergers that output a constant number of bits using only constant seed. Furthermore, a random choice of merger does not work for this purpose! - Nevertheless, just like in the case of standard extractors, an extracting merger which gets most of the entropy out (namely, having Ω(n) output bits) must have Ω(log n) seed. This is the main technical result of our work, and is proved by a second-moment strengthening of the graph-theoretic approach of Radhakrishnan and Ta-Shma to extractors. All this is in contrast to the status for condensing mergers (where the output is only required to have high min-entropy), whose seed-length/output-length tradeoffs can all be fully explained by using standard condensers. Inspired by such considerations, we also formulate a new and basic class of problems in combinatorics: partition analogues of Shearer’s lemma. We show basic results in this direction; in particular, we prove that in any partition of the 3-dimensional cube [0,1]³ into two parts, one of the parts has an axis parallel 2-dimensional projection of area at least 3/4.
Cite as

Swastik Kopparty and Vishvajeet N. Extracting Mergers and Projections of Partitions. In Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2023). Leibniz International Proceedings in Informatics (LIPIcs), Volume 275, pp. 52:1-52:22, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2023)

Copy BibTex To Clipboard

@InProceedings{kopparty_et_al:LIPIcs.APPROX/RANDOM.2023.52,
  author =	{Kopparty, Swastik and N, Vishvajeet},
  title =	{{Extracting Mergers and Projections of Partitions}},
  booktitle =	{Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2023)},
  pages =	{52:1--52:22},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-296-9},
  ISSN =	{1868-8969},
  year =	{2023},
  volume =	{275},
  editor =	{Megow, Nicole and Smith, Adam},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.APPROX/RANDOM.2023.52},
  URN =		{urn:nbn:de:0030-drops-188777},
  doi =		{10.4230/LIPIcs.APPROX/RANDOM.2023.52},
  annote =	{Keywords: randomness extractors, randomness mergers, extracting mergers, partitions, projections of partitions, covers, projections of covers}
}
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 About DROPS Imprint Privacy Contact