1,121 reputation
511
bio website
location Mountain View, CA
age 28
visits member for 4 years, 4 months
seen Dec 8 at 6:59

I'm a software engineer at Google. Before that, I was a PhD student at CalTech in theoretical computer science.


Aug
3
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.
Jul
27
awarded  Yearling
Jul
16
awarded  Good Answer
Jul
27
awarded  Yearling
Jul
24
awarded  Nice Answer
Nov
13
answered Meaning of amortized analysis of an algorithm
Nov
1
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.
Nov
1
revised Can a graph be non 3-colourable without having k4 as a sub graph?
edited body
Oct
31
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)$).
Oct
31
answered Can a graph be non 3-colourable without having k4 as a sub graph?
Oct
27
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.
Oct
24
answered Computational Complexity of Modular Exponentiation
Jul
27
awarded  Yearling
Jul
15
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/….
Jul
15
answered Time complexity to calculate a digit in a decimal
Jul
10
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.
Jul
3
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)$.
Jul
3
comment A challenge by R. P. Feynman: give counter-intuitive theorems that can be translated into everyday language
Good catch @Generic! @Casebash: The main paper is cs.ucla.edu/~rafail/PUBLIC/BCFGGOS.pdf, which has lots of good references in it.
Jun
13
revised A model of computation for co-CFLs?
close mismatched $
Jun
12
answered A model of computation for co-CFLs?