Derandomization Using Conditional Expectation: Solving Graph and Distance Problems
Learn about derandomization through conditional expectation in randomized algorithms. Explore how to deterministically compute graph cuts and distance oracles using clever probabilistic techniques. Can you solve these graph problems without relying on randomness?
Download Presentation
Please find below an Image/Link to download the presentation.
The content on the website is provided AS IS for your information and personal use only. It may not be sold, licensed, or shared on other websites without obtaining consent from the author. If you encounter any issues during the download, it is possible that the publisher has removed the file from their server.
You are allowed to download the files provided on this website for personal or commercial use, subject to the condition that they are used lawfully. All files are the property of their respective owners.
The content on the website is provided AS IS for your information and personal use only. It may not be sold, licensed, or shared on other websites without obtaining consent from the author.
E N D
Presentation Transcript
Randomized Algorithms CS648 Lecture 25 Derandomization using conditional expectation A probability gem 1
DERANDOMIZATION USING CONDITIONAL EXPECTATION 2
Problem 1: Large cut in a graph Problem: Let ? = (?,?) be an undirected graph on ? vertices and ? edges. Compute a cut of size at least ?/?. A randomized algorithm: ? ; ? ; For each vertex ? ? Add ? to ? or ? randomly with probability ? ? independent of other vertices return the cut defined by (?,?). ?: size of cut (?,?) returned by the randomized algorithm. E[?] =?/? Question: How to deterministically compute a cut of size ?/? in ?(?) time? A simple application of conditional expectation 3
Problem 2: Approximate Distance Oracles Problem: Let ? = (?,?) be an undirected graph on ? vertices and ? edges. Compute a 3-approximate distance oracle of size ?(??+?/?). A randomized algorithm: ? ; ? Add each vertex from ? to ? randomly independently with probability ? = ?. for each ? ?\?, compute Ball(?,?,?) for each ? ?, compute distance to all vertices. ?: ? ?\?|Ball(?,?,?) | returned by the randomized algorithm. E[?] =??+?/? Question: How to deterministically compute a 3-approximate distance oracle of size O(??+?/?) ? A non-trivial application of conditional expectation (published in ICALP 2005) 4
Problem 3: Min-Cut Problem: Let ? = (?,?) be an undirected graph on ? vertices and ? edges. Compute minimum cut of ?. Randomized algorithmMin-cut(?): { Repeat ? ? times { Let ? ??; ? Contract(?,?). } return the edges of multi-graph ?; } Theorem: The algorithm computes a min-cut with probability at least ? ?. Question: How to deterministically compute a min-cut in time ?(?? ??????? ?) ? No idea whether we can use conditional expectation ? 5
Large cut in a graph A randomized algorithm: ? ; ? ; For each vertex ? ? Add ? to ? or ? randomly with probability ? ? independent of other vertices return the cut defined by (?,?). ?? ?? ?? ?? ??+? ?? 6
Notations: For a given graph ? = (?,?), ?,? ? and ? ?, ?(?): set of all edges from ? that have ? as one of the endpoint. ?(?): set of all edges from ? that have at least one end point in ?. ?(?,?): set of all edges from ? with one endpoint in ? and another in?. ?(?,?)=? (? ?) ?(?,?): set of all edges from ? with one endpoint ? and another endpoint in ?. ?(?,?)=? (? ?) 7
Notations: ?: random variable denoting the number of edges in a cut output by the algorithm. ??: random variable taking value 1 if ?? ? and 0 otherwise ??: {??, ??, , ??} ??: {??, ??, , ??} where ?? {?,?} for 1 ? ?. ??= ??means??= ??, ,??= ??. 8
CONDITIONAL EXPECTATION Make sure you understand Conditional expectation before using it. So try to focus on the following slide. 9
? ? ??= ?? =? ?? ?? ?? ?? ?? ??+? ?? ? ? 10
? ? ??= ?? =? ?? ?? ?? ?? ?? ??+? ?? ?,?? ?)| + |?(?? |?(?\??)|/? ? ?? ? ?? ? ? 11
DERANDOMIZATION USING CONDITIONAL EXPECTATION 12
Role of conditional expectation ? ? =? ? ?? ? ??= ? ?? ? ??= ? + Either ? ? ??= ? ? ? or ? ? ??= ? ? ? In general, ? ?|??= ?? =? ? ?? ? ??= ??,??+?= ? ?? ? ??= ??,??+?= ? + Either ? ? ??= ??,??+?= ? ? ?|??= ?? or ? ? ??= ??,??+?= ? ? ?|??= ?? 13
The Binary tree associated with the Randomized algorithm ? ? ? ? ??= ? ? ? ??= ? ? ? ??= ?,??= ? ? A cut of value ?/? 14
Using Conditional expectation ? ?= ? ? We wish to make choices for ?? s such that ? ? ? ? ??= ?? ? ? ??= ??,??= ?? ? ?|??= ?? IDEA: Given that ? ?|??= ?? ? ?, choose ??+? such that ? ?|??+?= ??+? ? ?|??= ?? 15
? ? ??= ?? ? ? 16
? ? ??= ?? ? ? ?? ?? ?? ?? ?? ??+? ?? ? ?? ? ?? ? ? ??= ??= |?(?? |?(?\??)|/? ?,?? ?)| + ? ? 17
? ? ??= ?? ? ? ?,?? ?)| + |?(?\??)|/? ? ? ??= ??= |?(?? ? ? ??= ?? =? ?? ? ??= ??,??+?= ? +? ?? ? ??= ??,??+? = ? ?,?? ?)| + |?(??+?,?? ?)| +|?(?\??+?)|/? ? ? ??= ??,??+?= ? = ?? |?(?? ?,?? ?)| + |?(??+?,?? ?)| +|?(?\??+?)|/? |?(?? ? ? ??= ??,??+?= ? = ?? Question: Should we assign ??+? to ? or to ? ? ?)| |?(??+?,?? ?)| Assign ??+? to ? if |?(??+?,?? 18
Making Choice for ??+? ?? ?? ?? ?? ?? ??+? ?? ? ?? ? ?? ??+? ??+? ? ? 19
Deterministic algorithm for Large cut Input: ? = (?,?) ? ; ? For each vertex ? ? { if |?(?,?)|> |?(?,?)| Add ? to ?; else Add ? to ?; } return the cut defined by (?,?). ; This was a simple example of using conditional expectation derandomize a algorithm. But it conveys the crux of this powerful method. In order to use it to derandomize any other algorithm, all you might need is creative and analytical skills. Also remember, we can not hope to derandomized every randomized algorithm. But if it is possible to derandomize and conditional expectation may prove to be a useful tool. to randomized algorithm, Time Complexity: O(?). Theorem: There is a deterministic O(?) time algorithm to compute a cut of size at least ?/? in any given undirected graph. 20
Selecting a random number Question: How many random bits are needed to select a number randomly uniformly from [1,32] ? Answer: 5 Question: How many random bits are needed to select a number randomly uniformly from [1,34] ? Answer: < 6 2 2 1. Select a random number ? from [1,64] 2. If? ?? return? ; else repeat; 22
Selecting a random interval Question: There are ? ? rational numbers ? < ??< ??< < ?? ?< ?. ? intervals {(?,??), (??,??), ,(?? ?< ?)} How to select an interval randomly with probability proportional to their length? Example: ? = ? ? ??? ?????? ???????, ??= ??????? , ??= ???????, ??= Answer: 1. Select a random number ? from [?,???] 2. If? ??????? { if ? ??, returnI; if ? ??, returnII; if ? ??, returnIII; else return IV; } else repeat; 23
Selecting a random interval There are ? ? rational numbers ? < ??< ??< < ?? ?< ?, with common denominator ?. ? intervals {(?,??), (??,??), ,(?? ?< ?)} Example : ? = ??, ? = ????. Question: How many random bits are needed for selecting an interval randomly with probability proportional to their length? Answer: ? ??? ? Surprise: In fact we just need ? ??? ? bits only. 24
SOLUTION FOR 2 INTERVALS 25
? ??= ?? 1 0 0 1 0 1 ? 0 0 1 1 0 0 1 1 0 0 0 1 . 0 1 0 1 1 0 1 2 3 4 5 6 7 8 9 10 30 31 26
? ??= ?? 1 0 0 1 0 1 ? 0 0 1 1 0 0 1 1 0 0 0 1 . 0 1 0 1 1 0 1 2 3 4 5 6 7 8 9 10 30 31 27
? ??= ?? 1 0 1 2 0 1 1 4 ? 1 0 1 8 Show that expected number of random bits needed to select an interval is ?? 1 ?? 16 1 32 1 32 0 1 2 3 4 5 6 7 8 9 10 30 31 28
? For any ??= ?? The expected number of random bits needed: 2? + 2? ? 2? 1 ?<? < 2 for any value of ? Last gem of this course: There are ? intervals {(?,??), (??,??), ,(?? ?< ?)}, where ?? s are rational. Show that we need expected ?(log ?) random bits to select an interval randomly. 29
Last slide Question: Why did the instructor conclude the course with a probability gem ? Answer: It is the joy of pondering over a probabilistic or algorithmic puzzle that is the strongest driving force to teach this course. Perhaps the same is the driving force for you to study this course. You disagree! You will realize this fact after a few years down the line Thanks for the attention you paid to this course 30
