Monte-Carlo Algorithms Use random bits to determine whether X  L

Monte-Carlo Algorithms

• Use random bits to determine whether x  L

• Random tape is one-way

• Bad witness:

• a sequence of random bits that leads to an error

• Error probability:

• proportional volume of bad witness set

• (r,-Monte-Carlo algorithm:

• uses r random bits
• has a constant error probability 0 < 1/2

Deterministic Amplification

• Goals:

• to amplify the success of a Monte-Carlo algorithm
• to save random bits

• Deterministic Amplifier:

• Given: (r,)-Monte-Carlo algorithm for L

• Yields: (l,)-Monte-Carlo algorithm for L with:

• - 
• - l  r as small as possible

• Amplifies the success of the algorithm

• Tries to save random bits

Naive Amplification

Black-Box Amplification

Weak Extractors (1)

Weak Extractors (2)

• Bad witness set of A:

• a subset W  V2 of volume < 

• Bad witness set of MA:

• the set of yV1 whose majority of neighbors belong to W

• ()-weak extractor:

• For any subset W  V2 of volume < , the set of y  V1 whose majority of neighbors belong to W is of volume < 

Known Amplifiers

Applicability of Black-Box Amplifiers

• C-applicability:

• for all A  C, also MA  C

• Determined by the complexity of computing neighborhoods in the weak extractor

• All above amplifiers are BPP-applicable

Space-Bounded Amplification

• An (S,p)-efficient black-box amplifier:

• uses S space for computing the k neighbors in the weak extractor
• runs at most p simulations simultaneously (p-parallel)

• If A uses SA space, then MA uses O(S + pSA) space

• BPL - logspace polynomial time Monte-Carlo algorithms

• Fact:

• BPL-applicability  (O(log(n),O(1))-efficiency

BPL-Applicable Black-Box Amplifiers

• Problems:

• Naive amplifier is BPL-applicable but uses too many random bits
• Straightforward implementations of other amplifiers need to store the random seed in their work space
• random seed may be of polynomial size

• Conclusion:

• No known BPL-applicable amplifier that uses a small number of random bits

Positive Result

• Theorem:

• A new implementation of the AKS amplifier:

• uses O(k) space for computing the k neighbors in the weak extractor
• k-parallel

• Corollary:

• For any constant 0 <  we obtain an amplifier which is:

• BPL-applicable
• reduces the error from  to 
• uses r + O(1) random bits

Negative Result

• Theorem:

• Any black-box amplifier that:

• is p-parallel
• uses < r/4 space for computing the k neighbors
• uses O(r) random bits

• cannot reduce an  error probability to less thanO(p).

• Corollary:

• BPL-applicable black-box amplifiers that use O(r) random bits can achieve only a constant amplification.

The AKS Amplifier

• G: d-regular expander on 2r nodes (d is constant)

• The AKS weak extractor:

• V1 - all walks on G of length k
• V2 - all nodes of G
• every walk is connected to all the nodes that occur in it

• Theorem (AKS,CW,IZ):

• The AKS amplifier uses r + O(k) random bits and reduces the error probability from  to k).

Proof of Positive Result (1)

• We want to find a new implementation of the AKS amplifier which:

• has a one-way access to the random seed (a random walk on G)
• computes the k neighbors of the seed (the k nodes of the walk) in O(k) space
• runs at most k simulations simultaneously

Online Constant-Space Expanders

• Online constant space expander:

• Has a neighborhood algorithm R, which if given:

• a node v  G
• a neighbor index j
• outputs:
• the j’th neighbor of v
• with:
• one-way access to the bits of v
• constant space

Proof of Positive Result (2)

• Use an online constant-space expander G

• Run the k simulations simultaneously

• Encoding of a walk: j1,…,jk,v0

• Initialization:

• read j1,…,jk from the random tape

• Make r iterations. At the ith iteration:

• read the ith bit of v0
• compute the ith bits of v1,…,vk
• feed these bits into the simulations A1,…,Ak

Proof of Positive Result (3)

The Margulis-Gabber-Galil Expander

• A graph on m2 nodes

• Every node is a pair (x,y) where x,y  Zm

• (x,y) is connected to

• (x+y,y), (x-y,y)
• (x+y+1,y), (x-y-1,y)
• (x,y+x), (x,y-x)
• (x,y+x+1), (x,y-x-1)

• (all operations are modulo m)

The MGG Expander is Online Constant-Space

• Theorem:

• Under a certain encoding, the MGG expander on 22w nodes is an online constant-space expander.

• Proof:

• Encoding for a node (x,y): x1,y1,x2,y2,…,xw,yw
• To compute (x’,y’), a neighbor of (x,y), we need to calculate a few summations modulo 2w.
• Calculation of x’i,y’i requires only xi,yi and a few carry bits
• Can be carried out online and in constant space

Idea of the Negative Result’s Proof

• Information-theoretic fact:

• A black-box amplifier that makes k simulations cannot reduce an  error probability to less than O(k).

• We show that if a black-box amplifier:

• cannot store the seed in its work space
• uses cr random bits
• is p-parallel
• then it works as if k = cp.

Summary of Results

• First non-trivial BPL-applicable amplifier

• Proof of optimality with respect to BPL-applicable black-box amplifiers that use O(r) random bits

• First example of an online constant-space expander

• First example of an online constant-space weak extractor

Open Problems

• Can non-black-box amplifiers do better than a constant amplification for BPL algorithms?

• Other applications of online constant-space weak extractors and expanders?

Thank You