Computer Science
Tel-Aviv University

0368.4159
Randomized and Derandomized Algorithms

Fall 2008

Date

Topic

More details

 24.1.08

Tail inequalities

• Markov, Chebyshev, Chernoff.

A comparison for X=sum(X_i) with: 1. no constraints, 2. pair-wise independence and 3. full independence

 24.1.08

Pair-wise independence.

• Finding a cut with a least half the edges [LW, 3]

• Existence - using the probabilistic method

• A sequential deterministic algorithm

• A parallel deterministic algorithm using pair-wise independence.

• Efficiently sampling a pair-wise independent distribution.[LW, 2]

• A simple parallel algorithm for the maximal independent set problem, Also [MR,12.3]

31.1,7.2,14.2 

Complexity background

31.1.08

basic notions

• The world: P,RP,NP,BPP,Σ₂,PH,PSPACE

• Sipser: BPP is in Σ₂

• Strong amplification and an alternative proof for BPP is in Σ2 (Goldreich and Zuckerman)

• MA and AM. We can assume perfect completeness. (Goldreich and Zuckerman)

• MA is in Σ2. AM in Π2.

• MA is in AM.

7.2.08

BPP seems like not being strong enough for NP

• Non-uniformity. P|poly. [AB, 7.6]

• Adelman: BPP is in P|poly

• Karp Lipton: If NP is in P|poly then PH= Σ_{2 .}

• The same if NP is in BPP. Interpretation: an indication that BPP can not solve SAT

 14.2.08

More connections between the uniformityand non-uniform worlds.

• . IP, IP=PSPACE (just the statement)

• PSPACE in P|poly implies PSPACE=MA

• NEXP in P|poly implies NEXP=MA (without a proof, IKW)

Derandomization vs. circuit lower bounds.

14.2.08

Does a derandomization exist for ACIT?

21.2.08

No derandomization before we prove circuit lower bounds

• Identity testing ( [AB, 7.2], [MR, 7.1-7.3]).

• Schwartz Zippel lemma . ACIT is in coRP.

• The permanent. The determinant. A probabilistic, parallel algorithm for the maximum matching problem (in a bipartite graph).. RNC vs. P.

• Valiant: The permanent is #P-complete (no proof)

• Kabanets and Impagliazzo: If Identity testing is in P, then either NEXP requires super-polynomial circuits, or Permanent requires super-polynomial algebraic circuits. Derandomizing Polynomial Identity Tests Means Proving Circuit Lower Bounds.

28.2.08, 6.3.08

Circuit lower bounds suffice for derandomization.

So may be Identity testing is not in P?

• PRG

• There are PRG against non-uniform circuits with small support.

• Such PRG imply derandomization.

• Nisan's generator fooling AC⁰

• The NW generator.

• [Impagliazzo Wigderson]: If E requires exponential size circuits than BPP=P.

• "Summary": Lower bounds "iff" derandomization.

13.3.08

How about circuit lower bounds?

• Natural lower bounds. Natural lower bounds imply no PRG (and OWF).

• The original paper: Natural proofs.

DLOG

Dehueristfy?

DLOG Elementary thoughts on discrete logarithms, C. Pomerance,

Baby step giant step

1. The pollard's-rho algorithm for DLOG and its heuristic analysis.

undirected connectivity in RL

13..308

20.3.08 

USTCON. SL. A probabilistic logspace algorithm solving USTCON using random walks.

λ₂ and λ=max{λ_2,-λn}. Small λ implies rapid mixing. (HLW, sec 3). The mixing lemma. (HLW, sec 2.4). Small λ implies small diameter. Small λ implies implies edge expansion. (LHS of HLW Thm 4.11, sec 4.5.1).

Edge expansion implies small λ₂ (RHS of HLW, Thm 4.11, sec 4.5.2). Any undirected, non-bipartite, connected graph has a somewhat small λ.

SL is in RL.

Expanders

27.3.08

The zig-zag construction

An explicit constructions of a constant degree graph with constant spectral gap. [AB, 16.4],

Omer Reingold, Salil. Vadhan, Avi. Wigderson.
Entropy Waves, The Zig-Zag Graph Product, and New Constant-Degree Expanders and Extractors.

A deterministic log-space algorithm for undirected connectivity.

28.3.08 

2.4.08

Savtich. BPL in DSPACE(log²n).

Omer Reingold, Undirected ST-Connectivity in Log-Space [AB, 16.5],

Finding a path between s and t.

Universal traversal sequences. Short UTS exist. Explicit UTS for π-labelled graphs.

Universal exploration sequences. Explicit UES.