Class Note for CMPSCI 601 at UMass(45)
Class Note for CMPSCI 601 at UMass(45)
Popular in Course
Popular in Department
This 18 page Class Notes was uploaded by an elite notetaker on Friday February 6, 2015. The Class Notes belongs to a course at University of Massachusetts taught by a professor in Fall. Since its upload, it has received 13 views.
Reviews for Class Note for CMPSCI 601 at UMass(45)
Report this Material
What is Karma?
Karma is the currency of StudySoup.
You can buy or earn more Karma at anytime and redeem it for class notes, study guides, flashcards, and more!
Date Created: 02/06/15
CMPSCI 601 Recall From Last Time Lecture 26 Theorem 0 If m is prime then SolovayStrassenm returns prob ably prime 0 If m is not prime then the probability that Solovay Strassenm returns probably prime is less than 12 Corollary PRIME E Truly Feasible De nition A decision problem 5 is in BPP Bounded Probabilistic Polynomial Time iff there is a probabilis tic polynomialtime algorithm A such that for all inputs w if w E S then Pr0bAw 2 l cow towns if w g S then Pr0bAw 2 l Equivalently there is a probabilistic polynomialtime algorithm A such that for all n and all inputs w of length n 7 1 if w E S then ProbA39w1 2 1 27 if m gz S then ProbA39w 1 S 21 Other Randomized Classes 0 NP Pr0bAw l gt 0 iffw E S 0 RP Pr0bAw 2 l 2 12 for w E 5 else ProbA 2 l 0 PP Pr0bAw 2 l gt 12 form 6 5 else ProbA 2 l CMPSCI 601 Undirected Reachability Lecture 26 REACH 2 0 undirected I s1t G Fact 261 Let be the expected number of steps in a random walk to visit all vertices in connected graph G starting from 239 Then g 2en 1 Corollary 262 REACH E BPL wwww A look at this directed graph should convince you that a random walk on it is not likely to reach all vertices in polynomial time To get to vertex t from 3 you would have to guess right about n times in a row It s very plausible that REACH is in L and one might hope to prove it by derandomizing the random walk There must exist a single sequence of choices of size 0023 that visits every node of any undirected labelled nnode graph But randomization doesn t seem to help much with the general REACH problem CMPSCI 601 Cryptography Lecture 26 OneTime Pad p 6 01quot m 6 01quot Epz 2 p691 Dpx 2 p692 D 7Epam 29690969772 2 m p 0110010101 m 0000111100 Epm 0110101001 DpEpm0000111100 Theorem 263 If p is chosen at random and known only to A and B then I E p m provides no information to E about m except perhaps its length 2 Better not use p more than once XOR of two mes sages with same pad is plaintext XOR plaintext easy to attack CMPSCI 601 RSA Lecture 26 B chooses p q nbit primes B chooses GCDe g0pq 1 901 p 1q 1 B publishes pg 6 keeps p q secret B computes d k st ed kg0pq 2 1 Break message into pieces shorter than 2n bits EBQT z are mod pa BBQ 2 xd mod pa DBEBm E med mOdeI E mlksphaq mod pg E m m pqk mOd 191 2 m mod pa EBD3m mod m For suf ciently large n n 2 128 is ne in 2002 It is widely believed that E 3m divulges no useful information about m to anyone not knowing p q or d Message signing Let m 2 B promises to give A 10 by 51702 Let m 2 m o 7 where 7 is nonce or current date and time It is widely believed that D 3m could be produced only by B Thus it can be used as a contract signed by B Useful for proving authenticity CMPSCI 601 Interactive Proofs Lecture 26 Goldwasser Micali Rackoff Babai Decision problem D input string 1 Two players Prover Merlin is computationally allpowerful Wants to convince Veri er that a E D Veri er Arthur probabilistic polynomialtime TM Wants to know the truth about whether 1 E D Inputx n tzn O A has 1 M has 1 1 ip 01 compute m1 gt 2 lt 7712 3 ip 03 compute 7713 gt 4 lt 7714 2t lt m2t 2t 1 ip 02t1 acceptor reject 10 De nition 264 D 6 IP iff there is such a polynomial time interactive protocol 1 If 1 E D then there exists a strategy for M 2 ProbA accepts gt g 2 If a g D then for all strategies for M l ProbA accepts lt 3 A Observation 265 Iterating makes probabilities of error exponentially small Special Cases of IP 0 Deterministic Arthur NP 0 N0 Merlin BPP ll De nition 266 MA is the set of decision problems ad mitting two step proofs where Merlin moves rst AM is the set of decision problems admitting two step proofs where Arthur moves rst AM2k AMAM AM 4 2k Fact 267 Babai For all k 2 2 AMk 2 AM NP P MAiAM AMpoly IP PSPACE BPNP BPP 12 Fact 268 GoldwasserSipser T he power of interactive proofs is unchanged if M knowns A s com tosses For allk IPk AMk IP AMnOlt1gt 13 Graph NonIsomorphism 6 AM Input 00019 n 110011 211011 O A has 0001 M has 0001 1 ipnl7 gt 01 lp7l 17l39r 6 S71 71 1C772 1739 39 39 77FTGI T gt 2 lt m2 6 0v1r 3 accept iff R 2 m2 Proposition 269 Graph NonIsomorphl39sm 6 AM Proof If GO 9 G 1 then A will accept with probability 1 If GO g G 1 then A will accept with probability 3 2quot A Corollary 2610 If Graph Isomorphism is NPcomplete then PH collapses to 215 14 Fact 2611 Shamir s Theorem IP 2 PSPACE proof that IP g PSPACE Evaluate the game tree For M s moves choose the maximum value For A s moves choose the average value 9 m m gg k Hard Direction Construct an interactive proof that a string is in QSAT There are proofs in P and in Sipser 15 CMPSCI 601 PCP S Lecture 26 Any decision problem D E NP has a deterministic polynomial time veri er By adding randomness to the veri er we can greatly re strict its computational power and the number of bits of H that it needs to look at while still enabling it to accept all of NP We say that a veri er A is 7402 qnrestricted iff for all inputs of size n and all proofs H A uses at most Orn random bits and examines at most Oqn bits of its proof H Let PCPrn be the set of boolean queries that are accepted by Mn qnrestricted veri ers Fact 2612 PCP Theorem NP 2 PCPlogn 01 Fact 2613 Hastad NP 2 PCPlog n 3 l6 MAXBSAT given a 3CNF formula nd a truth as signment that maximizes the number of true clauses x1 ng Vfg x1 V5134 ij AT1VT2VT4 xQVT3Vx7 T2V3V5 V V WVTQVm V kas Proposition 2614 MAXBSAT has a polynomialtime 6 2 approximation algorithm Proof Be greedy Q Open for Years Assuming NP 7E P is there some 6 0 lt e lt 1 st MAXBSAT has no PTIME eapproximation algorithm 17 Theorem 2615 The PCP theorem NP 2 PCPlog n 1 is equivalent to the fact that If P NP then Forsome 6 1gt 6 gt 0 MAXBSAT has no polynomialtime eapproximation algorithm Fact 2616 MAXBSAT has a PTIME approximation algorithm with e 2 i and no better ratio can be achieved unless P 2 NP References 0 Approximation Algorithms for NP Hara Problems Dorit Hochbaum 6d 1997 PWS 0 Sanjeev Arora The Approximability ofNPhard Prob lems STOC 98 wwwcsprincetoneduNarora 18
Are you sure you want to buy this material for
You're already Subscribed!
Looks like you've already subscribed to StudySoup, you won't need to purchase another subscription to get this material. To access this material simply click 'View Full Document'