Improved pseudorandom generators for combinatorial rectangles
type: Item
instance of: scholarly article
title: Improved pseudorandom generators for combinatorial rectangles
zbMATH Open document ID: 1012.05047
author: Chi-Jen Lu
published in: Combinatorica
publication date: 2003-05-18T00:00:00Z
review text: The author constructs a pseudorandom generator that approximates the volume of combinatorial rectangles in \(\{1, \dots, m \}^d\) within \(\varepsilon\) error. The generator uses \(O(\log m + \log d + \log^{3/2}1/\varepsilon)\) bits, which improves the \(O(\log m + \log d + \log^{2}1/\varepsilon)\) result of \textit{R. Armoni, M. Saks, A. Wigderson} and \textit{S. Zhou} [Proc. 37th Ann. IEEE Symp. on Foundations of Computer Sci., 412-421 (1996)]. For a special class of rectangles (with at most \(t \geq \log 1/\varepsilon\) nontrivial dimensions and each dimension being an interval) a generator using \(O(\log \log d + \log 1/\varepsilon \log^{1/2}\frac{t}{\log 1/\varepsilon})\) is given. The best known before was \(O(\log \log d + \log 1/\varepsilon \log \frac{t}{\log 1/\varepsilon})\) by \textit{S. Chari, P. Rohatgi} and \textit{A. Srinivasan} [J.Comput. Syst. Sci. 61, 81-107 (2000; Zbl 0960.68172)].
reviewed by: András Pluhár
Mathematics Subject Classification ID: 05B40
Mathematics Subject Classification ID: 68Q25
Mathematics Subject Classification ID: 68R05
zbMATH DE Number: 1912035
zbMATH Keywords: pseudorandom
zbMATH Keywords: generator
zbMATH Keywords: combinatorial
zbMATH Keywords: rectangules
MaRDI profile type: Publication
full work available at URL: s004930200021
OpenAlex ID: W2041493762
DOI: 10.1007/S004930200021
description: scientific article; zbMATH DE number 1912035