WIXLIB

Randomness in ComputingLECTURE 25Last time Probabilistic method Lovasz Local LemmaToday Algorithmic Lovasz LocalLemma12/2/2021Sofya Raskhodnikova;Randomness in Computing

ExerciseConsider an algorithm 𝒜 for problem 𝓟 that, on inputs of length 𝑛,uses 𝑅(𝑛) random bits, runs in time 𝑇(𝑛), and produces the correctYES/NO answer for the given input with probability 1/2.Give a deterministic algorithm for 𝓟 and analyze its running time.The running time of your algorithm is big-O ofA. 𝑇(𝑛)B. 𝑅 𝑛 𝑇(𝑛)C.2𝑅𝑛 𝑇(𝑛)D. 𝑅 𝑛 2𝑇E.F.12/2/2021𝑛2𝑅 𝑛 2𝑇 𝑛Larger than all of the above.Sofya Raskhodnikova; Randomness in Computing

Lovasz Local Lemma (LLL) Event 𝐸 is mutually independent from the events 𝐸1 , , 𝐸𝑛if, for any subset 𝐼 [𝑛],Pr 𝐸 ሩ 𝐸𝑗 ] Pr[𝐸] .𝑗 𝐼 A dependency graph for events 𝐵1 , , 𝐵𝑛 is a graph with vertexset [𝑛] and edge set 𝐸, s.t. 𝑖 𝑛 , event 𝐵𝑖 is mutuallyindependent of all events 𝐵𝑗 𝑖, 𝑗 𝐸}.Lovasz Local LemmaLet 𝐵1 , , 𝐵𝑛 be events over a common sample space s.t.1. max degree of the dependency graph of 𝐵1 , , 𝐵𝑛 is at most 𝒅2. 𝑖 𝑛 , Pr 𝐵𝑖 𝒑If 𝒆𝒑 𝒅 𝟏 𝟏 then Pr 𝐵 𝑛 𝑖ځ ഥ𝑖 012/2/2021Sofya Raskhodnikova; Randomness in Computing

Application of LLLTheoremIf 𝒆𝒌𝟐𝒏𝒌 𝟐1 𝒌𝟐 1 2 1 then edges of 𝐾𝑛 can be coloredwith 2 colors so that there is no monochromatic 𝐾𝑘 .Proof:12/2/2021Sofya Raskhodnikova; Randomness in Computing

Canonical special case of LLL: kSAT Notation: 𝑛 number of variables, 𝑚 number of clausesObservation: If 𝑚 2𝑘 , then the formula is satisfiable.Proof: Pick a uniformly random assignment. Let 𝐵𝑖 be the event that clause 𝑖 is violated.12/2/2021Sofya Raskhodnikova; Randomness in Computing; based on Tim Roughgarden’s notes

Statement of LLL for 𝒌SAT Dependency graph: Vertices correspond to clausesedge (𝑖, 𝑗) iff clauses 𝑖 and 𝑗 share a variableIf clause 𝑖 contains 𝑥 and clause 𝑗 contains 𝑥,ҧ it counts as sharing a variable.deg 𝑖 number of clauses sharing a variable with clause 𝑖 Let 𝑑 1 max deg(𝑖) max # of clauses one variable appears in.𝑖Algorithmic Lovasz Local Lemma for 𝑘SAT𝒌 𝟑If 𝒅 𝟐 𝟐𝒌𝟖for some 𝑘CNF formula 𝜙, then 𝜙 is satisfiable.Moreover, a satisfying assignment can be found in 𝑂(𝑚2 log 𝑚)time with probability at least 1 2 𝑚 .12/2/2021Sofya Raskhodnikova; Randomness in Computing

Moser-Tardos Algorithm for LLLInput: a 𝑘CNF formula with clauses 𝐶1 , , 𝐶𝑚on 𝑛 variables and with 𝑑 2𝑘 3Global variable1. Let 𝑅 be a random assignment where each variable isassigned 0 or 1 uniformly and independently.2. While some clause 𝐶 is violated by 𝑅, run FIX(𝐶)3. 𝐑𝐞𝐭𝐮𝐫𝐧 𝑅.FIX(𝐶)1. Pick new values for 𝑘 variables in 𝐶 uniformly andindependently and update 𝑅.2. While some clause 𝐷 that shares a variable with 𝐶 isviolated by 𝑅, run FIX(𝐷)𝑫 could be 𝑪 if we chose the same values as before12/2/2021Sofya Raskhodnikova; Randomness in Computing

Correctness of ObservationIf FIX(𝐶) terminates, then it terminates with an assignmentin which 𝐶 and all clauses sharing a variable with 𝐶 are satisfied.12/2/2021Sofya Raskhodnikova; Randomness in Computing

Correctness of Moser-TardosLemma (Correctness)A call to FIX that terminates does not change anyclauses of the formula from satisfied to violated.Proof: Suppose for contradiction that some call FIX(𝐶) terminated andchanged an assignment to clause 𝐷 from satisfied to violated, and considerthe first such call. 𝐷 can’t share a variable with 𝐶 by Observation. Then randomly reassigning variables of 𝐶 does not affect variables of 𝐷 All calls to FIX that the current call made terminated before this call didand, by assumption that this is the first bad call to terminate,could not have spoiled 𝐷.Theorem (Correctness)If Moser-Tardos terminates, it outputs a satisfying assignment.12/2/2021Sofya Raskhodnikova; Randomness in Computing

Run time of Moser-Tardos Assume: 𝑚 2𝑘 (o.w. trivial by other means)Theorem (Run time)If 𝒅 𝟐𝒌 𝟑 then Moser-Tardos terminates after 𝑂(𝑚 log 𝑚)resampling steps with probability at least 1 2 𝑚 . Proof idea: Clever way to compress’’ random bitsif the algorithm runs for too long.Observation 2If a function 𝑓: 𝐴 𝐵 is injectiveSet A(i.e., invertible on its range 𝑓(𝐴))then 𝐵 𝐴 .12/2/2021Sofya Raskhodnikova; Randomness in ComputingSet B𝒇

Function 𝒇𝑻 Suppose we stop Moser-Tardos after 𝑇 resampling steps.Randomness used:𝒏 bits for initial assignment𝒌 bits for each resampling stepTotal: 𝒏 𝑻𝒌 bits Let 𝐴 be the set of all choices for 𝑛 𝑇𝑘 bits𝑓𝑇 𝑥0 , 𝑦0initialassignment12/2/2021𝑻𝒌 bits forreassignment 𝑥 𝑇 , 𝑧𝑇assignmentafter 𝑻resamplingstepstranscriptafter 𝑻resamplingstepsSofya Raskhodnikova; Randomness in Computing

Transcript Each call to FIX gets recorded as follows:If FIX 𝐶 is called by the algorithm𝟏index of the clause 𝐶 on which FIX is calledIf FIX 𝐷 is a recursive call made by FIX 𝐶𝟏 index’’ of the clause 𝐷 among all clauses that overlap with clause 𝐶 When a call to FIX returns,𝟎 is written on the transcript12/2/2021Sofya Raskhodnikova; Randomness in Computing

Run time of Moser-TardosLemma 1Function 𝑓𝑇 is invertible on all inputs (𝑥0 , 𝑦0 ) for which Moser-Tardosdoes not terminate within 𝑇 steps when run with randomness (𝑥0 , 𝑦0 ).Lemma 2Length of transcript 𝑧𝑇 is at most 𝒎(⌈𝐥𝐨𝐠 𝟐 𝒎⌉ 𝟐) 𝑻 (𝒌 𝟏) .12/2/2021Sofya Raskhodnikova; Randomness in Computing

Proof of TheoremFirst, consider 𝑇 such that Moser-Tardos never terminates within 𝑇resampling steps. There is a valid transcript 𝑧𝑇 for every choice ofthe random 𝑛 𝑇𝑘 bits needed to run Moser-Tardos12/2/2021Sofya Raskhodnikova; Randomness in Computing

Proof of Theorem (continued)Now, consider 𝑇 such that Moser-Tardos fails to terminate1w.p. 𝑚 within 𝑇 resampling steps.2 Then 𝑓𝑇 is invertible on the set of size 2𝑛 𝑇𝑘 𝑚12/2/2021Sofya Raskhodnikova; Randomness in Computing

Proof of Lemma 1Lemma 1Function 𝑓𝑇 is invertible on all inputs (𝑥0 , 𝑦0 ) for which Moser-Tardosdoes not terminate within 𝑇 steps when run with randomness (𝑥0 , 𝑦0 ).Proof: The recursion tree is uniquely defined by 𝑧𝑇 FIX is only called on violated clauses, and each clause has aunique violating assignment.12/2/2021Sofya Raskhodnikova; Randomness in Computing

Algorithmic LLL for 𝒌SATAlgorithmic Lovasz Local Lemma for 𝑘SATIf 𝒅 𝟐𝒌 𝟑 𝟐𝒌𝟖for some 𝑘CNF formula 𝜙, then 𝜙 is satisfiable.Moreover, a satisfying assignment can be found in 𝑂(𝑚2 log 𝑚)time with probability at least 1 2 𝑚 .12/2/2021Sofya Raskhodnikova; Randomness in Computing

4/23/2020 Randomness in Computing LECTURE 25 Last time Drunkard’s walk Markov chains Randomize