Randomized Communication Complexity in Complexity Theory
Explore the concepts of communication complexity, deterministic and randomized protocols, and error probabilities in computing functions within the realm of complexity theory. Dive into the nuances of randomized communication protocols and their effectiveness in solving problems with minimal communication.
Uploaded on | 0 Views
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
CMSC 28100 Introduction to Complexity Theory Complexity Theory Spring 2024 Instructor: William Hoza 1
Communication complexity Communication channel Goal: Compute ? ?,? using as little communication as possible In each round, one party sends a single bit while the other party listens At the end, both parties Bob holds ? Alice holds ? announce ? ?,? 2
Communication complexity of equality EQ??,? = 1 if ? = ? if ? ? 0 Theorem: Every deterministic communication protocol that computes EQ? has cost at least ? + 1 3
Randomized communication complexity Communication channel In a randomized communication protocol, Alice and Bob are permitted to make decisions based on coin tosses Bob holds ? Alice holds ? 4
Randomized communication protocols Mathematically, we model a randomized communication protocol with ?-bit inputs as a deterministic communication protocol with ? + ? -bit inputs for some ? 0 Alice holds ??, where ? 0,1? and ? 0,1? Bob holds ??, where ? 0,1? and ? 0,1? Interpretation: ?,?are the actual inputs, and ?,? are the coin tosses 5
The output of a randomized protocol For each ?,? 0,1? and ?,? 0,1?, we have ? ??,?? 0,1 We define ? ?,? as follows: Pick ?,? 0,1? 0,1? uniformly at random, then set ? ?,? = ? ??,?? ? ?,? is a random variable. For each ? 0,1 , we have ?,? ? ??,?? = ? 0,1? 0,1? Pr ? ?,? = ? = 6
Computing a function with a randomized protocol Let ?: 0,1? 0,1? 0,1 and let ? > 0 Suppose that for every ?,? 0,1?, we have Pr ? ?,? = ? ?,? 1 ? In this case, we say that ? computes ? with error probability ? 7
Which of the following is an accurate description of the protocol? Randomized communication complexity of EQ? A: The protocol succeeds on most pairs of inputs B: The amount of communication is rarely more than ? log? Let ? > 0 be any constant C: For every pair of inputs, the protocol is likely to succeed D: It is likely that for every pair of inputs, the protocol succeeds Respond at PollEv.com/whoza or text whoza to 22333 Theorem: For every ? , there exists a randomized communication protocol with cost ? log? that computes EQ? with error probability ? Randomized protocols are exponentially better than deterministic protocols! 8
Randomized protocol for EQ? Assume without loss of generality that ?/? is a power of two Think of ?,? {0,1}? as numbers ?,? {0,1, ,2? 1} Let ?1,?2,?3, be the sequence of all prime numbers (in order) Protocol: 1. Alice picks ? 1,2, ,?/? uniformly at random and sends ?,? mod ?? to Bob 2. Bob sends a bit indicating whether ? mod ??= ? mod ?? 3. If so, they accept, otherwise, they reject 9
Analysis of the protocol: Correctness If ? = ?, then Pr ? mod ??= ? mod ?? = 1 Now suppose ? ? Pr error = Pr ? mod ??= ? mod ?? = Pr ?? divides ? ? Let BAD be the set of prime numbers that divide ? ? Every prime number is at least 2, so BAD log ? ? < ? ? There are ?/? candidate ? values, so Pr ?? BAD ?/?= ? 10
Analysis of the protocol: Efficiency We chose ? ?/?, so sending ? costs ? log? bits of communication Sending ? mod ?? costs ? log?? bits of communication How big could ?? be? Theorem: Let?? be the ?-th prime. Then ??= ? log? = ? ?2. (Proof is outside the scope of this course) We chose ? ?/?, so log??= log ? ?2 = ? log? 11
Which problems Which problems can be solved can be solved through computation? through computation? 12
Randomized Turing machines 1 1 0 Input tape Randomness tape 13
Randomized Turing machines Let ?: be a function (time bound) Definition: A randomized time-? Turing machine is a two-tape Turing machine ? such that for every ? , every ? ?, and every ? 0,1? ?, if we initialize ? with ? on tape 1 and ? on tape 2, then it halts within ? ? steps Interpretation: ? is the input and ? is the coin tosses (Giving ? more than ? ? random bits would be pointless) 14
Acceptance probability Let ? be a randomized Turing machine and let ? To run ? on ?, we select ? 0,1? ? uniformly at random and initialize ? with ? on tape 1 and ? on tape 2 ? might accept ? sometimes and reject ? other times ? ? accepts ? when tape 2 is initialized with ? 0,1? ? Pr ? accepts ? = 15
The complexity class BPP Let ? be a language Definition:? BPP if there exists a randomized polynomial-time Turing machine ? such that for every ? : If ? ?, then Pr ? accepts ? 2/3 If ? ?, then Pr ? accepts ? 1/3 Bounded-error Probabilistic Polynomial-time 16
