Understanding Communication Complexity in Complexity Theory
Explore the fascinating world of communication complexity within complexity theory, covering topics such as randomized protocols, deterministic protocols, and the analysis of communication protocols for computational tasks like equality computation.
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 2025 Instructor: William Hoza 1
Communication Complexity Communication Complexity 2
Communication complexity Communication channel Goal: Compute ? ?,? using as little communication as possible Bob holds ? Alice holds ? 3
Communication complexity of equality EQ?: 0,1? 0,1? {0,1} EQ??,? = 1 if ? = ? if ? ? 0 Theorem: Every deterministic communication protocol that computes EQ? has cost at least ? + 1 4
Randomized communication complexity Communication channel Bob holds ? Alice holds ? 5
Randomized communication complexity of EQ? Let ? > 0 be any constant 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! Proof: Next five slides 6
Randomized protocol for EQ? Think of ?,? {0,1}? as numbers ?,? {0,1, ,2? 1} Let ?1 ?2 ?3 be the sequence of all prime numbers Protocol: 1. Alice picks ? 1,2, ,?/? uniformly at random (WLOG, ?/? is a power of two) 2. Alice sends ? and ? mod ?? 3. Bob sends a bit indicating whether ? mod ??= ? mod ?? 4. If so, they accept, otherwise, they reject 7
Protocol: Analysis of the protocol: Correctness Pick ? 1,2, ,?/? u.a.r. 1. Send ? and ? mod ?? 2. Check whether ? ? mod ?? 3. If ? = ?, then Pr accept = Pr ? ? mod ?? = 1 If ? ?, then Pr accept = Pr ? ? mod ?? = Pr ?? divides ? ? Let BAD be the set of prime numbers that divide ? ? 2BAD ? BAD? ? ? < 2? Pr accept = Pr ?? BAD BAD ? < ?/?= ? ?/? 8
Protocol: Analysis of the protocol: Efficiency Pick ? 1,2, ,?/? u.a.r. 1. Send ? and ? mod ?? 2. Check whether ? ? mod ?? 3. Sending ? costs ? log? bits of communication Sending ? mod ?? costs ? log?? bits of communication How big is ?? (the ?-th prime)? Chebyshev s Estimate: Let?? be the ?-th prime. Then ??= ? ? log? . = log ? ?2 Therefore, log??= log ? ? log? = ? log? All that remains is to prove Chebyshev s Estimate (Next two slides) 9
Step 1: Legendres Formula Legendre s Formula: For any ? and any prime ?, the exponent of ? in ?/??. the prime factorization of ?! is precisely ?=1 Proof: Among the numbers 1,2,3, ,?: ?/? of them are multiples of ? ?/?2 of them are multiples of ?2 ?/?3 of them are multiples of ?3 Etc. 10
Proof of Chebyshevs Estimate 2? ! ?!2 ? = ?1 ?2 ?2 ? 2? ? Let ? = 2? log? 0.5 ?2 and let ?1 = 2? ? ?? 2? Legendre ??= 2 log??2? , so ?? ? ? ?? ?? ?=1 2? ? Therefore, 2? 2? = 2 log 2?, i.e., ?/log 2? ? Therefore, ?? ? 2? = ? ? log? 11
Which of the following best describes the protocol? Randomized communication complexity of EQ? pairs of inputs A: The protocol succeeds on most B: The amount of communication is rarely more than ? log? 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 Let ? > 0 be any constant 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! 12
Which problems Which problems can be solved can be solved through computation? through computation? 13
Randomized Turing machines 1 1 1 0 Input tape Randomness tape 14
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 ? 0,1?, 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) 15
Acceptance probability Let ? be a randomized Turing machine and let ? 0,1 To run ? on ?, we select ? 0,1? ? uniformly at random and initialize ? with ? on tape 1 and ? on tape 2 ? ? accepts ? when tape 2 is initialized with ? 2? ? Pr ? accepts ? = 16
Randomized TMs: Deciding a language Let ? be a randomized time-? Turing machine for some ?: Let ? 0,1 and let ? 0,1 We say ? decides ? with error probability ? if for every ? 0,1 : If ? ?, then Pr ? accepts ? 1 ? If ? ?, then Pr ? accepts ? ? 17
The complexity class BPP Definition:BPP is the set of languages ? 0,1 such that there exists a randomized polynomial-time Turing machine that decides ? with error probability 1/3 Bounded-error Probabilistic Polynomial-time 18
Example: High school algebra Expand and simplify: ? + 1 ? 1 This type of expression is called an arithmetic formula How difficult is this type of exercise? 19
Arithmetic formulas Definition: A ?-variate arithmetic formula is a rooted binary tree Each internal node is labeled with + or Each leaf is labeled with 0, 1, 1, or a variable among ?1, ,?? It computes ?: ? + + E.g., ? ?1,?2 = ?1 ?2 ?1+ ?2 ?1 ?1 ?2 ?2 1 20
Polynomial identity testing Problem: Given an arithmetic formula ?, determine whether ? 0 As a language:PIT = ? ? is an arithmetic formula and ? 0 High school algorithm: Expand ? into monomials, then simplify by canceling like terms What is the time complexity of this algorithm? B:2 ? A:poly ? C:? 1 D: Respond at PollEv.com/whoza or text whoza to 22333 21
Example: Polynomial identity testing Given: ? = ? 1 1 + ? ? ? 1 ? ? ? + ? + 1 ? 1 ? ? ? ? 1 ? Expand: ? ?2? ?2?? ?2?? + ?2??? ??? + ???? + ???? ????? + ?2?2 ?2?2? ?2??? + ?2???? ???2+ ???2? + ????? ?????? ?? + ??? + ??? ???? + ?? ??? ??? + ???? ?2 + ?2? + ??? ???? + ?2? ?2?? ??? + ???? + ?2?? ?2??? ???? + ????? ?2? + ?2?? + ??? ???? + ??? ???? ??? + ???? ?? + ??? + ?? ??? ??2?? + ??2??? + ????? ?????? + ??2? ??2?? ???? + ????? ???? + ????? + ???? ????? + ??? ???? ??? + ???? Everything cancels out: ? 0 22
Polynomial identity testing Expanding ? takes 2 ? time in some cases E.g., ? = ? + ? ? + ? ? + ? ? + ? Open Question: Is PIT P? Next 10 slides: We will prove PIT BPP 23
Evaluating an arithmetic formula Let ? be a ?-variate arithmetic formula and let ? ? Lemma: Given ?, ? , one can compute ? ? in polynomial time. 12 ?1= 2 6 2 ?2= 4 + + 4 ? ?1,?2 = 12 ?2 ?1 ?1 2 4 2 ?2 1 4 24
