Space/time trade-offs in hash coding with allowable errors, Communications of the ACM, vol.13, issue.7, pp.13-422, 1970. ,
DOI : 10.1145/362686.362692
On the complexity of a concentrator, 7th International Telegrafc Conference, pp.318-319, 1973. ,
The complexity of an optimal nonblocking commutation scheme without reorganization, Problems of Information Transmission, vol.9, pp.64-66, 1974. ,
Bounds on the length of disjunctive codes. Problems of information transmission, pp.7-13, 1982. ,
Constant Depth Reducibility, SIAM Journal on Computing, vol.13, issue.2, pp.423-429, 1984. ,
DOI : 10.1137/0213028
Storing a sparse table with O(1) worst case access time, 23rd Annual Symposium on Foundations of Computer Science (sfcs 1982), pp.538-544, 1984. ,
DOI : 10.1109/SFCS.1982.39
Families of finite sets in which no set is covered by the union ofr others, Israel Journal of Mathematics, vol.27, issue.2, pp.79-89, 1985. ,
DOI : 10.1007/BF02772959
Almost optimal lower bounds for small depth circuits, Proceedings of the eighteenth annual ACM symposium on Theory of computing , STOC '86, pp.6-20, 1986. ,
DOI : 10.1145/12130.12132
On universal classes of fast high performance hash functions, their time-space trade-off, and their applications, Proc. of 30th IEEE FOCS, pp.20-25, 1989. ,
Pseudorandom generators for space-bounded computation, Combinatorica, vol.36, issue.4, pp.449-461, 1992. ,
DOI : 10.1007/BF01305237
Hardness vs randomness, Journal of Computer and System Sciences, vol.49, issue.2, pp.149-167, 1994. ,
DOI : 10.1016/S0022-0000(05)80043-1
Eigenvalues and expansion of regular graphs, Journal of the ACM, vol.42, issue.5, pp.1091-1106, 1995. ,
DOI : 10.1145/210118.210136
On universal classes of extremely random constant time hash functions and their time-space tradeoff, 1995. ,
Algorithms and Data Structures for External Memory, Foundations and Trends?? in Theoretical Computer Science, vol.2, issue.4, pp.209-271, 2001. ,
DOI : 10.1561/0400000014
Are Bitvectors Optimal?, Preliminary version: in Proc. of STOC, pp.1723-1744, 2000. ,
DOI : 10.1137/S0097539702405292
Randomness Conductors and Constant-Degree Lossless Expanders, Proc. of the 34th ACM STOC, pp.659-668 ,
Algorithmic derandomization via complexity theory, Proc. ACM STOC 2002, pp.619-626 ,
Storing information with extractors, Information Processing Letters, vol.83, issue.5, pp.267-274, 2002. ,
DOI : 10.1016/S0020-0190(02)00206-5
Expander graphs and their applications, Bulletin of the American Mathematical Society, vol.43, issue.04, pp.439-561, 2006. ,
DOI : 10.1090/S0273-0979-06-01126-8
Algorithms and Data Structures for External Memory. Series on Foundations and Trends in Theoretical Computer Science, 2008. ,
Poly-logarithmic Independence Fools AC^0 Circuits, 2009 24th Annual IEEE Conference on Computational Complexity, pp.3-8, 2009. ,
DOI : 10.1109/CCC.2009.35
Unbalanced expanders and randomness extractors from Parvaresh?Vardy codes, Journal of the ACM, vol.56, issue.4, 2009. ,
Theorems about space-bounded Kolmogorov complexity obtained by " naive " derandomization, Proc. Computer Science in Russia, 2011. Prelim. version: arXiv:1009, p.5108, 2010. ,
How strong is Nisan's pseudorandom generator? 2010. Electronic preprint ,