@article {17603,
	title = {Improved Algorithms via Approximations of Probability Distributions},
	journal = {Journal of Computer and System Sciences},
	volume = {61},
	year = {2000},
	month = {2000/08//},
	pages = {81 - 107},
	abstract = {We present two techniques for constructing sample spaces that approximate probability distributions. The first is a simple method for constructing the small-bias probability spaces introduced by Naor and Naor. We show how to efficiently combine this construction with the method of conditional probabilities to yield improved parallel algorithms for problems such as set discrepancy, finding large cuts in graphs, and finding large acyclic subgraphs. The second is a construction of small probability spaces approximating general independent distributions which are of smaller size than the constructions of Even, Goldreich, Luby, Nisan, and Veli{\v c}kovi{\'c}.},
	keywords = {derandomization, discrepancy, explicit constructions, graph coloring, Parallel algorithms, small sample spaces},
	isbn = {0022-0000},
	doi = {10.1006/jcss.1999.1695},
	url = {http://www.sciencedirect.com/science/article/pii/S0022000099916951},
	author = {Chari,Suresh and Rohatgi,Pankaj and Srinivasan, Aravind}
}
@article {17595,
	title = {Explicit OR-dispersers with polylogarithmic degree},
	journal = {Journal of the ACM (JACM)},
	volume = {45},
	year = {1998},
	month = {1998/01//},
	pages = {123 - 154},
	abstract = {An (N, M, T)-OR-disperser is a bipartite multigraph G=(V, W, E) with |V| = N, and |W| = M, having the following expansion property: any subset of V having at least T vertices has a neighbor set of size at least M/2. For any pair of constants \&xgr;, \&lgr;, 1 >= \&xgr; > \&lgr; >= 0, any sufficiently large N, and for any T >= 2(logN) M <= 2(log N)\&lgr;, we give an explicit elementary construction of an (N, M,    T)-OR-disperser such that the out-degree of any vertex in V is at most polylogarithmic in N. Using this with known applications of OR-dispersers yields several results. First, our construction implies that the complexity class Strong-RP defined by Sipser, equals RP. Second, for any fixed \&eegr; > 0, we give the first polynomial-time simulation of RP algorithms using the output of any {\textquotedblleft}\&eegr;-minimally random{\textquotedblright} source. For any integral R > 0, such a source accepts a single request for an R-bit string and generates the string according to a distribution that assigns probability at most 2-R\&eegr; to any string. It is minimally random in the sense that  any weaker source is insufficient to do a black-box polynomial-time simulation of RP algorithms.},
	keywords = {derandomization, expander graphs, explicit constructions, hardness of approximation, hashing lemmas, imperfect sources of randomness, measures of information, pseudo-random generators, randomized computation, time-space tradeoffs},
	isbn = {0004-5411},
	doi = {10.1145/273865.273915},
	url = {http://doi.acm.org/10.1145/273865.273915},
	author = {Saks,Michael and Srinivasan, Aravind and Zhou,Shiyu}
}
@conference {17554,
	title = {Approximating hyper-rectangles: learning and pseudo-random sets},
	booktitle = {Proceedings of the twenty-ninth annual ACM symposium on Theory of computing},
	series = {STOC {\textquoteright}97},
	year = {1997},
	month = {1997///},
	pages = {314 - 323},
	publisher = {ACM},
	organization = {ACM},
	address = {New York, NY, USA},
	keywords = {approximations of distributions, derandomization, explicit constructions, machine learning, multiple-instance learning, PAC learning, pseudorandomness, Ramsey graphs, random graphs, rectangles, sample complexity},
	isbn = {0-89791-888-6},
	doi = {10.1145/258533.258611},
	url = {http://doi.acm.org/10.1145/258533.258611},
	author = {Auer,Peter and Long,Philip M. and Srinivasan, Aravind}
}
@conference {17660,
	title = {Splitters and near-optimal derandomization},
	booktitle = {, 36th Annual Symposium on Foundations of Computer Science, 1995. Proceedings},
	year = {1995},
	month = {1995/10/23/25},
	pages = {182 - 191},
	publisher = {IEEE},
	organization = {IEEE},
	abstract = {We present a fairly general method for finding deterministic constructions obeying what we call k-restrictions; this yields structures of size not much larger than the probabilistic bound. The structures constructed by our method include (n,k)-universal sets (a collection of binary vectors of length n such that for any subset of size k of the indices, all 2k configurations appear) and families of perfect hash functions. The near-optimal constructions of these objects imply the very efficient derandomization of algorithms in learning, of fixed-subgraph finding algorithms, and of near optimal ΣIIΣ threshold formulae. In addition, they derandomize the reduction showing the hardness of approximation of set cover. They also yield deterministic constructions for a local-coloring protocol, and for exhaustive testing of circuits},
	keywords = {Boosting, Circuit testing, computational complexity, computational linguistics, Computer science, Contracts, derandomization, deterministic constructions, Educational institutions, Engineering profession, exhaustive testing, fairly general method, fixed-subgraph finding algorithms, hardness of approximation, Information systems, k-restrictions, learning, local-coloring protocol, MATHEMATICS, near-optimal constructions, near-optimal derandomization, Parallel algorithms, probabilistic bound, probability, Protocols, randomised algorithms, Set cover, splitters},
	isbn = {0-8186-7183-1},
	doi = {10.1109/SFCS.1995.492475},
	author = {Naor,M. and Schulman,L. J and Srinivasan, Aravind}
}
