## Microwaves and birthdays

September 10, 2014

Without doubt, one of the largest differences between the USA and Israel is the microwave ovens. Whereas almost all microwaves I encountered in Israel had either analog rotary timers or preset “30 sec or 1 min” buttons, here in the states there is an overwhelming prevalence (100% of an astounding three cases) of numpad microwaves.

Seemingly, all you have to do is put in the number of minutes / seconds you want to heat, and fin, you are done.
But wait; is it minutes, or seconds? What happens if I put in a three or four digit number? Do I have to be an arithmetic expert to operate my microwave?
In what can only be stated as the “non-continuity of microwave space-time”, the input parsing is simple: if you put in xx:yy, it will run for xx minutes, and yy seconds. Simple and intuitive. The thing is, nothing constrains yy to be smaller than 60. 1:99 is as valid input as any, and will indeed run for 1 minute and 99 seconds (=159 seconds total). 2:00 is also a valid input, running for 2 minutes, 0 seconds (=120 seconds total).
This is the natural way to handle user input, and I totally approve of it, if only for the programmers’ and designers’ sake for not handling annoying details. There is a nice time discontinuity when you plot the actual cooking time against the numbers you punch in, if you arrange them in lexicographical order:

Starting from 60 seconds cook time, the user has two choices of how she wants the input to be shaped, rather than just the feeble one available with a rotary timer. This is in agreement with the USA’s enhanced economic and political freedom; it is no wonder that these microwaves are more prevalent here (as for me, you can find me standing dumbstruck in front of the machines, trying to decide which number I should punch in).

As the title of the above plot suggests, it is interesting to see how different minute lengths affect our options. The shorter the minute, the more overlap there will be, and the more options you will have, until finally, for SECONDS_PER_MINUTE = 1, we have 100(!) different options of input. Here is the example for a 30 second minute:

On the other hand, given that we work in base 10 and that our two digit numbers only go up to 99, if we had a longer minute (and kept the input method the same, allowing only two “seconds” digits), we would have gaps:

Not every desired time can be reached; we will likely not be seeing any 200 second minutes in the Imperial system any time soon.

This whole ordeal reminded me of a wonderful fact I stumbled upon that has to do with discretizing age. Consider the standard high school algebra question: Albert is X years old, and his son Jorgenhausfer is Y years old. When will Albert be twice as old as his son?
The question is easy, but one can also ask for how long Albert is twice as old as his son. It turns out that Albert will be twice as old as Jorgenhausfer for exactly one year, but that time period may be split into two sections, depending on their birthdays! I can do no better justice to the issue than the discussion given here:
http://www.math.brown.edu/~banchoff/twiceasold/

## Do not track

August 23, 2014

“Home is where the wifi connects automatically”.
The question remains to be asked, how does it know to connect automatically? Well, of course, the computer saves a list of network names (or other identifiers) and their passwords, and tries to connect when it sees one it recognizes. I bet the passwords are saved in plaintext, too, but you should know better than to use the same one for your wifi and for your bank.

Anyway, Ubuntu is no exception. This is a laptop, and I don’t have a GPS that records my coordinates at all time, so it’s still interesting to see that if you know enough about me and obtain access to my computer, you can track my position with fair accuracy. Here is a list of networks I’ve connected to, by default sorted by date.

Take a look at the connections. Can you reconstruct a map of where I’ve been as a function of time? Try to do so now.

.
.

All done?

.
.

I think the average user can, after a bit of thinking and googling, make at least some sense out of the somewhat-cryptic names. Certainly he will arrive at some route of the form: Technion -> Boston/MIT, with a stop in Europe. Here, let’s do it together. Start from the past:

ISRAEL-RAILWAYS – well, that’s easy. I sometimes take the train to the Technion, so no biggy there. Just two months ago I still had classes!
TechPublic, eewifi – TechPublic is, of course, the Technion’s campus-wide public wifi. eewifi is the same, for the department of electrical engineering. So a month ago I was certainly on campus.
caXXXyy – these are a bit a tricky, and require prior knowledge. “Canada” is the name of the dorms I live in. Specifically, ca94305 is my own apartment wifi. So after having connected to the public Technion wifi for the last time, I was at my dorms. But I haven’t been there for the past 29 days. It must be summer vacation.
Bezeq-n_6202 – my house wifi. Ok, you had no chance of guessing that :). But wait! Last time used, 27 days ago? Oh my, where have you been all this time?
Swisscom – that’s a Swiss communication company. How did that happen? Indeed, on my way to Boston I had a connection in Münich. Not quite Swiss, but close enough.
Loganwifi – Logan is Boston’s airport. I’ve been here for 26 days!
percher – stayed at a friend’s for a while. That might take a bit of digging. Seeing as it was used 22 days ago, and I arrived 26 days ago, one can conclude that I’ve stayed there for 4 days.
HMS public – unfortunately, not Her Majesty’s Ship, but Harvard Medical School. Went there for a visit.
MIT – ‘nough said. I spend most of my time here.
StataCenter – if it weren’t enough that you know at which institution I spend most of my time, you now also know the exact building. Oh well; as seen in a previous post, my wikipedia editing IP gives about that much information anyway.

How do you that I spend most of my time connected to the last two networks? Since it’s unlikely that I’ve been without internet access all this time (what with the blog posts and wikipedia edits and all), the fact that there are no networks in between MIT and StataCenter, and, say, the Percher / HMS ones, indicates that I’ve repeatedly connected to them, thus refreshing their status and putting them at the top of the recently used.

By the way, the Stata Center is a really cool place.

For me this isn’t confidential information – here, I’m posting it online. But I suppose that for those of us who wish to remain anonymous, for whatever reasons, wifi connection history is just one more problem to worry about. And seeing that my own connection history had entries from over a year ago, it stays with you for quite a while.

(footnote: I have intentionally omitted a network from the list, of the place I’m currently staying; I do not know if the owner would appreciate having the network name put here. This does not change the above analysis)

## Credo

August 14, 2014

I believe there is life outside of Earth. There are many planets in the observable universe, and thirteen billion years is a long time. I doubt, however, that DNA has much to do with it.
I believe P ≠ NP. How else could it be so hard to prove? Relatedly, even non-standard computing architectures, based on relativity, condensed matter, and quantum physics, have not yet breached it.
I believe in a Singularity. Eventually we will find out enough about individual consciousness to be able to bend it to our will; our bodies, too, will be under our control. What field in life hasn’t succumbed to engineering?
I believe it is possible to understand the world using physics. It seems unlikely (and despairing) to me that the world does not operate according to a set of rules that can be formally described; and while claiming that humans will eventually find out these rules is a strong statement, I look at what we have done so far in so little time, and cannot but be optimistic.

I believe all of these things, and many more. So Gauss-dammit Internet, if you tell me “This policeman pulled over a speeding couple – you won’t believe what happens next!” one more time, I swear I will personally go over there, and pull the plug on you myself.

## My first Wikipedia edit

August 6, 2014

Hurray! Yesterday I made my first Wikipedia edit. Years of meticulous dedication and research – in areas ranging from physics and mathematics to philosophy and absurdism – have finally paid off. I can only imagine all the wonderful places I can go from here. True, I spent about ten hours writing the whole thing, but certainly this is the starting point of a majestic career. The culmination of my open souce academic life can finally be seen here:

http://en.wikipedia.org/wiki/GCT

Yup – I added the 4th line, disambiguating geometric complexity theory from other, non-interesting matters, such as Gwinnet County Transit, or the ISO 639-3 code for a German dialect. Needless to say, not 10 minutes after hitting “save” (9, actually), my contribution was edited, trimmed of capital letters and a stray period. The wheels of perfection are grinding hard at work, I guess.

## Your weakness is not your technique

July 16, 2014

[Pre-post post-note: an amazing alignment of the stars! Just hours after writing this, I came across the much stronger Lockhart’s Lament. A must read, I daresay.]

Professors, teaching assistants, professional exam-writers, lend me your ears; I come to fix the exam, not to praise it. The exams that students solve, live after them; the results are oft interred with their bones.

This week I had my final examination in quantum mechanics 1. It had three open questions, two of which can basically be reduced to something as follows:
1) Apply the second order correction according to the scheme you learned in class to the following perturbation: …
2) Diagonalize a 3×3 matrix. Using the basis transform, express some vectors as a linear combination of other ones. Use these to obtain a wavefunction and integrate it.

In essence, the questions were just (very) technical mathematics exercises, not-so-cleverly disguised with an excuse for a physical background. This type of question is exactly what keeps me off my ass when studying for these exams. Is this a test in integration? A test in algebra? I already had those last year. I want to do some physics! In this case, converting the physical premise to the mathematical relations, or identifying the right equation in the formula sheet definitely didn’t count as “physics”.

As an analog, imagine a computer science class; over the semester, you went over the whole deal – sorting, graph flow, DFS/BFS, pattern matching. Now comes the final exam, and as you open up the questionnaire, your eyes grow wide with despair.

Question 1: Apply the quicksort algorithm to sort the following array. Make sure to write the complete derivation; a final answer only will not be accepted:
318, 330, 44, 304, 181, 472, 80, 245, 185, 45, 250, 285, 404, 370, 430, 194, 273, 180, 233, 146, 132, 473, 331, 291, 265, 444… [74 more items omitted]

What, isn’t that a legitimate question? After all, you learned about the quicksort method in class; here is your chance to show that indeed you know it, earning your exam points in earnest.
Oh, what’s that? It would be a dull and error-prone thing to do, that doesn’t really show the student’s proficiency in algorithms? It would be much better to have the student invent a similar but distinct algorithm to show that they grasp the concepts? In fact, inventing new algorithms and proving correctness and bounds is what actually happens in algorithms tests?!

It’s certainly possible to ask interesting questions, that actually require invoking the student’s physics-neurons instead of just the high-speed-integration ones. In fact, we had plenty of those in our classical mechanics lessons. And they might involve some difficult mathematics in order to get the right answer.

But when I compare my classical mechanics 1 exam with my quantum mechanics 1, I notice that the former’s (great) difficulty was in understanding what the hell I needed to do, while the latter’s was in diagonalizing quickly and keeping track of the trillions of minus signs, $\sqrt{2}$‘s and $\hbar$‘s. Admittedly, I am no expert, but for some reason I am quite certain that it is not quantum mechanics that is at fault here – certainly there is no dearth of physical reasoning which can also be backed up by mathematics (see Feynman vol. III, for example).

Professors, teaching assistants, professional exam-writers, lend me your ears! Cease the technical absurdity, and return physical insights to your exams! They shall make your students all the wiser, in addition to sparing them the sprained wrists and CTS. And if you claim that the exam should portray only what has been taught in class; well, what exactly have you been teaching then?

## Zero knowledge in the real world?

July 5, 2014

[Written under the influence of QCSD]
Not so long ago, I happened to watch the totally-accurate-in-every-possible-way film, “Travelling Salesman”. tl;dw: a squad of government-hired mathematicians are finally able to prove that P = NP, giving the state the power to answer every important computational question they can imagine (aka rob banks and fight terrorism). But when requested to hand over their findings, the mathematicians begin to doubt that they are doing the right thing (as opposed to, say, publishing the results and letting everyone enjoy the spoils). A difficult question indeed – unleashing a polynomial algorithm for an NP-complete problem does imply breaking almost all cryptosystems in use today, in addition to creating better flight plans for cross-country salesmen. Definitely, if we ever prove P = NP, the history of mankind will be divided into distinct “before” and “after” phases.
But what if the mathematicians aren’t interested in breaking ciphers, but just want their well deserved fame and glory for solving a very hard problem? It is here that I wonder if the computer science and mathematics communities are ready for non analytical proofs as part of science-doing, and not just as part of complexity classes.

A brief word of explanation first. The rigour with which results are demonstrated differs in various academic fields. In sociology and medicine, statistical significance is basically all there is, so saying “there is a less than 2% chance of our hypothesis being wrong given the clinical tests” is pretty darn good. In experimental physics, too, we can never be more sure than our measurement error. However, in theoretical physics, mathematics and computer science, an analytical proof, filled with lemmas, propositions and an abundance of silly symbols, is needed. Indeed, even computer-assisted proofs, ala the Four Color Theorem, are frowned upon and looked at with a wary eye.
One reason for the wariness of computers, of course, is that computer programs and hardware naturally have bugs, and who’s to say that the calculation was correct? Before stating that something is an irrevocable mathematical truth, one must be sure! Of course, humans make mistakes when writing and reading proofs as well; a small bug hiding in a 300 page manuscript might be able to evade all the reviewers and find itself in publication, impostering as a profound truth.

If printed mathematical texts can be wrong (god forbid!), why not accept that fact and welcome probabilistic proofs – proofs that are probably correct (why probably? because there is randomness involved), up to an error as small as we choose. Computer science already has this well defined – the BPP, MA, SZK, and PCP complexity classes, for example – but what about real-life science? (gee, now I know why Scott complains about naming conventions in complexity theory…)

I propose the following scheme: say our mathematician Bob wants to show the world that he has proved P = NP (and therefore, also P = co-NP), and in fact has discovered an algorithm for solving NP complete problems. However, he does not want to give away the algorithm, just show that he knows it. He thus set up a private server which handles incoming requests, and starts playing a sort of zero knowledge interactive proof protocol with the mathematical community. The community sends him boolean expressions of increasingly larger size n. For each expression s: if s is satisfiable, the server replies with a satisfying assignment. If not, the server replies with a proof that verifies that there does not exist a satisfying assignment. In other words, the server replies whether s is in SAT or in SAT-complement, and either way provides a proof for it. These are NP and co-NP complete problems, so solving them in polynomial time shows that P = NP.
Now, all currently known algorithms take super-polynomial time to run. So if Bob only had access to known algorithms, he would not be able to solve the problems as n becomes larger. However, assuming that the polynomial in Bob’s algorithm isn’t of very high degree, and that its leading coefficients aren’t gigantic, he can answer the questions even for large expressions. Knowing Bob’s computational power, the community could very well know if he runs in exponential or polynomial time, proving that he does not lie.
Where does probability come into play? Well, it may be that Bob is guessing. Bob might be a fraud, and whenever he gets a boolean expression, he randomly generates polynomial-sized certificates, and sees if they prove satisfaction / unsatisfaction of the expression. Of course, his chances of succeeding are exponentially small as n gets larger, but for every finite number of tests the community presses upon him, there is always a finite chance that he gets it right. Also, even if Bob runs a deterministic super-polynomial algorithm, for some lucky expressions he might be able to get the right answers quickly** (see problem below), so the community itself needs to randomize the expressions they send.

As it is, will this kind of “proof” catch on among fellow mathematicians? I doubt it. Even if you exclude the whole “his algorithm runs fast so it must be polynomial” problem, I think we are still far off from a more ideal world: one that has, in addition to science journals, an international array of servers dedicated to interactive, zero knowledge, and other probabilistic proofs (actually, under plausible assumptions, most those can be de-interactivated, no?), representing those theorems and propositions which we almost know are true; we’re just missing an ε.

Notes on note:
Note and future thoughts: The solution I have given is a bit awkward, in that it requires Bob to solve a lot of NP and co-NP problems, instead of just giving a normal zero knowledge proof to the expression “P = NP”. Suppose Bob only knows an algorithm for SAT. Can he encode it in such a way so that he can prove that it is indeed a polynomial algorithm for SAT, but that no one else will be able to use it? This is different from the zero-knowledge that I know of, in the sense that we aren’t just asking whether a specific string is in some language (aka an expression is in SAT) – we want to show that a string (program / proof) has some properties, without showing that actual string. If there are any real complexity theorists reading this, please do leave a comment.

Note to note to note: I recall hearing somewhere about encrypted zero knowledge computation – that is, Bob could send his algorithm to the community in an encrypted form, so that the community will do the calculations but have no idea what they are doing (and the computation will be different for each input, so they will not be able to reproduce the algorithm on different inputs than what they already asked). First of all, this is cool. Second, this will help base the fact that the algorithm is polynomial – but still won’t get around the lucky guesses that Bob could make if he frauds up a super-polynomial algorithm.

Too cool not to note: On the subject of “errors in human-reviewed manuscripts”: if rigour and no-chance-for-error is what you are looking for, why not submit formal proofs to the leading journals? This would constitute a sequence of lines; the first few would be the axioms, and the rest would be logically irrefutable inferences from the previous lines. The last would be the theorem you want to prove, stemming irrevocably from the axioms. Any monkey / mathematician / computer could go over these proofs and verify that they are true, no chance of error involved. Of course, I’m not the one to think of this idea, many have done so before me; for example, the QED manifesto (now, that’s a name I could live by…).

**Problem with solution: I assume here that expressions the mathematical community sends are, probabilistically, hard enough to solve with modern SAT solvers. I know that some of these solvers can work very well in some cases, failing miserably only, for example, on expressions with just one satisfying assignment. In this specific case, the assumption is that enough of the expressions only have one satisfying assignment (I seem to recall that this applies to a lot of boolean expressions).

## They should have sent a poet

June 13, 2014

My O(1) readers are probably restlessly wondering where I’ve been, why I have no more posts about the mathematics of toilets, and what’s up in general.
Well, the truth is, I did have a wonderful post on the mathematics of toilets (regarding putting the sit up or down in a mixed male/female environment), but have been beaten to the topic by another enthusiast.
The real deal though, is that the past few weeks have seen an investment of effort in, not science, but poetry (although between us, is there any difference?). And lo, just this week I came back from the International World Championship Poetry Slam in Paris.

To put it nicely, Poetry Slam is a spoken word combination of poetry, rap, and doom prophecy. Admittedly, my style is pretty much none of the three, but I still enjoy doing it, and have been performing in Israel for about a year. There are many, both here and abroad, who, with just a few words and tone of voice, can wreck you to tears and collapse your stomach in anguish; fill you with laughter; or light an otherwise gloomy day. I do not consider myself to be of that caliber, but last December I happened to (against 1/3 odds) win the National competition (with this amusing poem as a starter), and before I knew it was sortied off to France in order to pit my skills against the champions of the world.

With high probability, Paris is a really wonderful city. The rain was refreshing. The Love-Locked bridge collapsed. The cheese has fungi. The pollution is persistent. And to top it all off, the Mona Lisa winked at me (she never returned my calls though).
But really, the competition itself was great. The people were awesome (really, I was in awe); the crowds were supportive; but most importantly, the poetry was crushing (lmytfy). Finnish is like music to my ears.
All in all, I reached the finals and then placed 6th. But what can you expect from a mathematics major, really?

Here are some good English ones (not from Paris), to get you started (one for every season):