Problem 1

Let A = {A₁, Am} be a family of subsets of [n] = {1,...,n}. In other words,

A₁ [n] for every i E [m]. We denote

A = {

ZA = 24, and 4 the uniform distribution on 4.

{0,1}": Vi € [m], ‡j € A¡, £j=1},

1. Suppose that there exists a polynomial-time algorithm that receives the

family A and returns ZA. Construct a polynomial-time algorithm that

samples a vector x = {0,1}" from the distribution A.

2. Suppose that there exists a randomized algorithm that, given A, n > 0,

runs in time polynomial in A, log(n-¹) and returns a vector x = {0,1}¹

whose distribution is of total-variation distance at most n from A. Prove

that there exists an algorithm that, given A, e, runs in time polynomial

in A, ¹ and returns a number Ź such that

Pr

> 2/3.