Improved pseudorandom generators for combinatorial rectangles (Q1872894): Difference between revisions

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)].