2017-04-26
Apr 26 In-Class Exercise.
Post your solution to the Apr 26 In-Clas Exercise to this thread.
Best,
Chris
Post your solution to the Apr 26 In-Clas Exercise to this thread.
Best,
Chris
We want to implement this BPP algorithm in hardware. As we know that BPP is contained in P/poly, this is possible. As long as we can find a 'good' seed for our probabilistic TM, we can implement this compression algorithm in a circuit. To find this 'good' seed, we know that half of all strings of length m are good. We can implement a circuit with a hardcoded string of length m a handful of times and run the input on each circuit, taking the majority rule. We can use Chernoff bounds to find a suitable amount of random strings to hardcode and tune our margin of error to be exponentially small.
We want to implement this BPP algorithm in hardware. As we know that BPP is contained in P/poly, this is possible. As long as we can find a 'good' seed for our probabilistic TM, we can implement this compression algorithm in a circuit. To find this 'good' seed, we know that half of all strings of length m are good. We can implement a circuit with a hardcoded string of length m a handful of times and run the input on each circuit, taking the majority rule. We can use Chernoff bounds to find a suitable amount of random strings to hardcode and tune our margin of error to be exponentially small.
To find the random string that is correct for every input x: run k circuits based off of random strings in parallel, and take the result of the majority. If (k>1000) the chance that the circuit set will malfunction is small enough to be negligible.
To find the random string that is correct for every input x: run k circuits based off of random strings in parallel, and take the result of the majority. If (k>1000) the chance that the circuit set will malfunction is small enough to be negligible.
Using the proof for the theorem that proves BPP is contained in P/Poly. We have choose to one (`r_0`) of the many random strings for which the `TM M(x,r_0) = COMPRESSION(x)`. We know our `x` is of a fixed length. We know there are `2^m/2` many strings from the set of random strings that will always give us the result `TM M(x,r_0) = COMPRESSION(x)` for all `x` of length `10^12`. We can find this `r_0` by using Chernoff bounds to find a good guess for the number of circuits to hardwire in order bring the error rate down to a negligible amount and then choose the circuit which gives the correct output after running them for a reasonable number of times.
Using the proof for the theorem that proves BPP is contained in P/Poly. We have choose to one (@BT@r_0@BT@) of the many random strings for which the @BT@TM M(x,r_0) = COMPRESSION(x)@BT@. We know our @BT@x@BT@ is of a fixed length. We know there are @BT@2^m/2@BT@ many strings from the set of random strings that will always give us the result @BT@TM M(x,r_0) = COMPRESSION(x)@BT@ for all @BT@x@BT@ of length @BT@10^12@BT@. We can find this @BT@r_0@BT@ by using Chernoff bounds to find a good guess for the number of circuits to hardwire in order bring the error rate down to a negligible amount and then choose the circuit which gives the correct output after running them for a reasonable number of times.
We know that BPP is contained in P/poly. We have to find a string r0, to implement the compression algorithm. We know that there 2^m/2 strings that are good. We can find string r0 of length m using Chernoff bounds. By choosing a suitable value of k we can reduce the error rate of the circuit to a negligible value.
We know that BPP is contained in P/poly. We have to find a string r0, to implement the compression algorithm. We know that there 2^m/2 strings that are good. We can find string r0 of length m using Chernoff bounds. By choosing a suitable value of k we can reduce the error rate of the circuit to a negligible value.
We could hardwire circuits and then use the same string parallel on these circuits and then select from the majority. For very large number of iterations the chances of failure will drop of exponentially according to Chernoff bounds. we can make the algorithm accurate just by running it for multiple iterations
We could hardwire circuits and then use the same string parallel on these circuits and then select from the majority. For very large number of iterations the chances of failure will drop of exponentially according to Chernoff bounds. we can make the algorithm accurate just by running it for multiple iterations
2017-04-30
We can take a set of circuits, implement the BPP algorithm on each, run the input of size 10^12, and take the majority of the outcome. This is achievable by applying Chernoff Bounds, where we can accept with a low error rate.
We can take a set of circuits, implement the BPP algorithm on each, run the input of size 10^12, and take the majority of the outcome. This is achievable by applying Chernoff Bounds, where we can accept with a low error rate.
(c) 2024 Yioop - PHP Search Engine