3 Search Results for "N, Vishvajeet"

Document
RANDOM
DOI: 10.4230/LIPIcs.APPROX/RANDOM.2025.67
On Sums of INW Pseudorandom Generators

Authors: William M. Hoza and Zelin Lv

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

Abstract
We study a new approach for constructing pseudorandom generators (PRGs) that fool constant-width standard-order read-once branching programs (ROBPs). Let X be the n-bit output distribution of the INW PRG (Impagliazzo, Nisan, and Wigderson, STOC 1994), instantiated using expansion parameter λ. We prove that the bitwise XOR of t independent copies of X fools width-w programs with error n^{log(w + 1)} ⋅ (λ⋅log n)^t. Notably, this error bound is meaningful even for relatively large values of λ such as λ = 1/O(log n). Admittedly, our analysis does not yet imply any improvement in the bottom-line overall seed length required for fooling such programs - it just gives a new way of re-proving the well-known O(log² n) bound. Furthermore, we prove that this shortcoming is not an artifact of our analysis, but rather is an intrinsic limitation of our "XOR of INW" approach. That is, no matter how many copies of the INW generator we XOR together, and no matter how we set the expansion parameters, if the generator fools width-3 programs and the proof of correctness does not use any properties of the expander graphs except their spectral expansion, then we prove that the seed length of the generator is inevitably Ω(log² n). Still, we hope that our work might be a step toward constructing near-optimal PRGs fooling constant-width ROBPs. We suggest that one could try running the INW PRG on t correlated seeds, sampled via another PRG, and taking the bitwise XOR of the outputs.
Cite as

William M. Hoza and Zelin Lv. On Sums of INW Pseudorandom Generators. In Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2025). Leibniz International Proceedings in Informatics (LIPIcs), Volume 353, pp. 67:1-67:24, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2025)

Copy BibTex To Clipboard

@InProceedings{hoza_et_al:LIPIcs.APPROX/RANDOM.2025.67,
  author =	{Hoza, William M. and Lv, Zelin},
  title =	{{On Sums of INW Pseudorandom Generators}},
  booktitle =	{Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2025)},
  pages =	{67:1--67:24},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-397-3},
  ISSN =	{1868-8969},
  year =	{2025},
  volume =	{353},
  editor =	{Ene, Alina and Chattopadhyay, Eshan},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.APPROX/RANDOM.2025.67},
  URN =		{urn:nbn:de:0030-drops-244330},
  doi =		{10.4230/LIPIcs.APPROX/RANDOM.2025.67},
  annote =	{Keywords: INW generator, pseudorandomness, space-bounded computation, XOR Lemmas}
}
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}
}
  • Refine by Type
  • 3 Document/PDF
  • 2 Document/HTML

  • Refine by Publication Year
  • 2 2025
  • 1 2023

  • Refine by Author
  • 2 N, Vishvajeet
  • 1 Guo, Heng
  • 1 Hoza, William M.
  • 1 Kopparty, Swastik
  • 1 Lv, Zelin

  • Refine by Series/Journal
  • 3 LIPIcs

  • Refine by Classification
  • 2 Theory of computation → Pseudorandomness and derandomization
  • 1 Mathematics of computing → Combinatorics
  • 1 Mathematics of computing → Discrete mathematics
  • 1 Theory of computation → Complexity theory and logic
  • 1 Theory of computation → Computational geometry
  • Show More...

  • Refine by Keyword
  • 1 INW generator
  • 1 XOR Lemmas
  • 1 cluster expansion
  • 1 covers
  • 1 deterministic volume computation
  • Show More...

Any Issues?
X

Feedback on the Current Page

CAPTCHA

Thanks for your feedback!

Feedback submitted to Dagstuhl Publishing

Could not send message

Please try again later or send an E-mail
© 2023-2025 Schloss Dagstuhl – LZI GmbH About DROPS Imprint Privacy Contact