Derandomization and Group Testing

R. Dorfman, “The detection of defective members of large populations,” Annals of Mathematical Statistics , vol. 14, pp. 436–440, 1943

1943

Earlier work this paper cites.

W. Kautz and R. Singleton, “Nonrandom binary superimposed codes,” IEEE Transactions on Information Theory , vol. 10, pp. 363–377, 1964

1964

Earlier work this paper cites.

E. Knill, “Lower bounds for identifying subset members with subset queries,” in Proceedings of the 6 6 th Symposium on Discrete Algorithms (SODA) , 1995, pp. 369–377

1995

Earlier work this paper cites.

J. Radhakrishan and A. Ta-Shma, “Tight bounds for depth-two superconcentrators,” in Proceedings of the 38 38 th Annual IEEE Symposium on Foundations of Computer Science (FOCS) , 1997, p. 585–594

1997

Earlier work this paper cites.

D.-Z. Du and F. Hwang, Combinatorial Group Testing and its Applications , 2nd ed. World Scientific, 2000

2000

Earlier work this paper cites.

D. Stinson, R. Wei, and L. Zhu, “Some new bounds for cover-free families,” Journal of Combinatorial Theory, Series A , vol. 90, pp. 224–234, 2000

2000

Earlier work this paper cites.

A. Ta-Shma, C. Umans, and D. Zuckerman, “Lossless condensers, unbalanced expanders, and extractors,” in Proceedings of the 33 33 rd Annual ACM Symposium on Theory of Computing (STOC) , 2001, pp. 143–152

2001

Earlier work this paper cites.

L. Trevisan, “Extractors and pseudorandom generators,” Journal of the ACM , vol. 48, no. 4, p. 860–879, 2001

2001

Cited alongside, same era.

M. Capalbo, O. Reingold, S. Vadhan, and A. Wigderson, “Randomness conductors and constant-degree expansion beyond the degree/2 barrier,” in Proceedings of the 34 34 th Annual ACM Symposium on Theory of Computing (STOC) , 2002, pp. 659–668

2002

Cited alongside, same era.

A. D’yachkov, P. Vilenkin, A. Macula, and D. Torney, “Families of finite sets in which no intersection of ℓ \ell sets is covered by the union of s s others,” Journal of Combinatorial Theory, Series A , vol. 99, pp. 195–218, 2002

2002

Cited alongside, same era.

R. Raz, O. Reingold, and S. Vadhan, “Extracting all the randomness and reducing the error in Trevisan’s extractor,” Journal of Computer and System Sciences , vol. 65, no. 1, p. 97–128, 2002

Original

2002

Cited alongside, same era.

L. Trevisan, “Pseudorandomness and combinatorial constructions,” in Proceedings of the International Congress of Mathematicians (ICM’06) , 2006

2006

Later among the works it cites.

P. Damaschke, “Threshold group testing,” in General Theory of Information Transfer and Combinatorics , ser. Lecture Notes in Computer Science, vol. 4123, 2006, pp. 707–718

2006

Later among the works it cites.

E. Porat and A. Rothschild, “Explicit non-adaptive combinatorial group testing schemes,” in Proceedings of the 35 35 th International Colloquium on Automata, Languages and Programming (ICALP) , ser. Lecture Notes in Computer Science, vol. 5125, 2008, pp. 748–759

2008

Later among the works it cites.

M. Cheraghchi, “Noise-resilient group testing: Limitations and constructions,” in Proceedings of the 17 17 th International Symposium on Fundamentals of Computation Theory (FCT) , ser. Lecture Notes in Computer Science, vol. 5699, 2009, pp. 62–73

2009

Later among the works it cites.