Jeremy Hurwitz
Reputation
1,151
Next privilege 2,000 Rep.
 Apr4 comment Meaning of amortized analysis of an algorithm Thanks, @hengxin. Fixed. Apr4 revised Meaning of amortized analysis of an algorithm add missing subscripts Mar19 awarded Nice Answer Aug3 comment Computation with a memory wiped computer @Pastafarianist, that's an excellent question. It took me longer than I'd like to admit to figure it out. The short answer is that it's hidden in the recursion, specifically AND(f1, AND(f2, f3)). To compute R3<--R3+f1f2R1, we need the same value to be in R1 in lines 1 and 3. So the intermediate results from lines 1 and 2 must be stored in R2 and R3. Now look at the recursion in line 2, and suppose f2=AND(g1,g2). When computing f2, R2 is now the register that must remain fixed, so the intermediate results for g1 and g2 are stored in R1 and R3. Jul27 awarded Yearling Jul16 awarded Good Answer Jul27 awarded Yearling Jul24 awarded Nice Answer Nov13 answered Meaning of amortized analysis of an algorithm Nov1 comment Can a graph be non 3-colourable without having k4 as a sub graph? Sorry! That should have said "square with one diagonal". I've fixed it. Nov1 revised Can a graph be non 3-colourable without having k4 as a sub graph? edited body Oct31 comment Can a graph be non 3-colourable without having k4 as a sub graph? In general, there's no "easy" characterization of 3-colorability. Determining whether a graph is 3-colorable is NP-complete, so no characterization can be in P (such as checking whether it contains $K_4$, which is $O(n^4)$). Oct31 answered Can a graph be non 3-colourable without having k4 as a sub graph? Oct27 comment Computational Complexity of Modular Exponentiation On the wikipedia page, the input is described as "Two $n$-digit numbers". So $\Theta(n)$ is linear in the length of the input. In general, whenever you read a running time, always ask yourself what the $n$ is referring two -- both (1) the number of bits and (2) the value being represented are common idioms, so you need to decide based on context which is being used. Oct24 answered Computational Complexity of Modular Exponentiation Jul27 awarded Yearling Jul15 comment Time complexity to calculate a digit in a decimal Champernowne's constant can be computed in real-time. See rjlipton.wordpress.com/2012/06/04/…. Jul15 answered Time complexity to calculate a digit in a decimal Jul10 comment Deciding a problem: is it in $NP$, $NPC$ or $P$? To show that a problem is in NP, you need to give the certificate and the verifier. In this case, the certificate consists of both the split and the two satisfying assignments. The verifier checks that the split is valid and that the provided assignments satisfy them. Jul3 comment Security analysis of a matrix multiplication protocol @user996522: The key is that R is chosen uniformly at random. By analogy, consider picking a point in $[0,1)$. Let A be an arbitrary point in the interval, and let let R by a uniform random value in $[0,1)$. Then $A+R$ is uniformly random over the interval $[A, A+1)$, and so the fractional part is uniform over $[0,1)$.