A Survey on Threshold Direct Product Theorems

Ragesh Jaiswal, Columbia University, New York

Threshold Direct Product Theorems say that if there is a problem that is hard to solve on the average, then the hardness of solving larger than some threshold fraction of k instances of the problem increases exponentially with k. Proofs of the above statement can be interpreted as constructive proofs of concentration bounds. I will give a survey on results which build up to and give a constructive proof with bounds matching those of the classical concentration inequalities.