Sample spaces uniform on neighborhoods

ABSTRACT

Let a universe of m elements be given, along with a family of subsets of the universe (neighborhoods), each of size at most k. We describe methods for assigning the m elements to points in a small-dimensional vector space (over GF(2)), in such a way that the elements in each neighborhood are assigned to an independent set of vectors. Such constructions lead, through a standard correspondence between linear and statistical independence, to the construction of small sample spaces which restrict to the uniform distribution in each neighborhood. (The sample space is a uniformly-weighted family of binary m-vectors). The size of such a small space will be a function of the number of neighborhoods; and for sparse families, will be substantially smaller than any space which restricts to the uniform distribution in all k-sets. Previous work on small spaces with limited independence focused on providing independence or near-independence in every k-set of the universe. We show how to construct the sample spaces efficiently both sequentially and in parallel. In case there are polynomially many (in m) neighborhoods, each of size O(log m), the parallel construction is in NC. These spaces provide a new derandomization technique for algorithms; particularly, algorithms related to the Lova´sz local lemma. We also describe applications to the exhaustive testing of VLSI circuits, and to coding for burst errors on noisy channels.

REFERENCES

• 1: Noga Alon, A parallel algorithmic version of the Local Lemma, Proceedings of the 32nd annual symposium on Foundations of computer science, p.586-593, September 1991, San Juan, Puerto Rico [doi>10.1109/SFCS.1991.185423]
• 2: Noga Alon , László Babai , Alon Itai, A fast and simple randomized parallel algorithm for the maximal independent set problem, Journal of Algorithms, v.7 n.4, p.567-583, Dec. 1986 [doi>10.1016/0196-6774(86)90019-2]
• 3: N. Alon, O. Goldreich, J. I-Iastad, and R. Peralta. Simple constructions of almost k-wise independent random variables, in Proceedings of the 31st Annual Symposium on Foundations of Computer Science, pages 544-553, 1990.
• 4: L~szl6 Babai and P#ter Frankl. Linear algebra methods in combinatorics. Preliminary Version, 1988.
• 5: J. Beck. An algorithmic approach to the Lov~sz local lemma I. To appear in Random Structures and Algorithms.
• 6: B. Berger and j. Rompel. Simulating (logc n)- wise independence in NC. In Proceedings of the 30th Annual Symposium on Foundations of Computer Science, pages 2-7, 1989.
• 7: B. Chor, O. Goldreich, J. ttastad, J. Friedman, S. Rudich, and R. Smolenski. The bit extraction problem or t-resilient functions. In Proceedings of the 26th Annual Symposium on Foundations of Computer Science, pages 396- 407, 1985.
• 8: Z. Fiiredi, J. R. Griggs, and D. J. Kleitman. Representations of families of triples over GF(2). IMA Preprint Series # 422, 1988.
• 9: Robert G. Gallager, Information Theory and Reliable Communication, John Wiley & Sons, Inc., New York, NY, 1968
• 10: Richard M. Karp , Avi Wigderson, A fast parallel algorithm for the maximal independent set problem, Journal of the ACM (JACM), v.32 n.4, p.762-773, Oct. 1985 [doi>10.1145/4221.4226]
• 11: Michael Luby, A simple parallel algorithm for the maximal independent set problem, SIAM Journal on Computing, v.15 n.4, p.1036-1055, Nov. 1986 [doi>10.1137/0215074]
• 12: F. J. MacWilliams and N. J. A. Sloane. The Theory of Error-Correcting Codes. North- Holland, 1977.
• 13: Rajeev Motwani , Joseph Seffi Naor , Moni Naor, The probabilistic method yields deterministic parallel algorithms, Proceedings of the 30th IEEE symposium on Foundations of computer science, p.478-516, December 1994, Research Triangle Park, North Carolina, United States
• 14: J. Naor , M. Naor, Small-bias probability spaces: efficient constructions and applications, Proceedings of the twenty-second annual ACM symposium on Theory of computing, p.213-223, May 13-17, 1990, Baltimore, Maryland, United States [doi>10.1145/100216.100244]
• 15: Prabhakar Raghavan, Probabilistic construction of deterministic algorithms: approximating packing integer programs, Journal of Computer and System Sciences, v.37 n.2, p.130-143, October 1988 [doi>10.1016/0022-0000(88)90003-7]
• 16: G. Seroussi and N. H. Bshouty. Vector sets for exhaustive testing of logic circuits. IEEE Transactions on Information Theory, 34(3):513-522, 1988.
• 17: Joel Spencer. Ten Lectures on the Probabili,#tic Method. SIAM, 1987.
• 18: Umesh Virkumar Vazirani, Randomness, adversaries and computation (random polynomial time), 1986

INDEX TERMS

Primary Classification:
  F. Theory of Computation
  F.1 COMPUTATION BY ABSTRACT DEVICES
      F.1.2 Modes of Computation
          Subjects: Probabilistic computation

Additional Classification:
  G. Mathematics of Computing
  G.3 PROBABILITY AND STATISTICS
      Subjects: Probabilistic algorithms (including Monte Carlo)

General Terms:
Algorithms, Theory