Print

Please login or register.
1 Hour 1 Day 1 Week 1 Month Forever
Login with username, password and session length

[soulnet]

Despite being on this forum for more than a year, I have never wrote an introduction here. And today, I find myself in need to communicate to everyone that I became a doctor. A real doctor, those that spend all time thinking problems nobody else understands and that have no impact in everyone else's life, not the kinds that saves life or those other mundane tasks.

Anyway, thanks for providing a way to keep being nerdy while resting from research.

For the math or CS inclined, if anyone would like to read the thesis, you are welcomed to ask for it. I am not expecting any responses on this, but after so much work, if I can get at least one or two people to read them besides the ones that are forced to, it would be nice.

So, to introduce myself, I am almost 30 years old now, almost-married (not legally married, but factually) recently graduated from my PhD in Computer Science, and addicted to IRL and online Dominion. I live in Argentina but I am considering a job offer that may make me move to the bay area in California, USA in a year or so.

[GeoLib]

Congratulations! What's your thesis on?

[soulnet]

Congratulations! What's your thesis on?

The title is "A computational perspective on normal numbers". Is theoretical results around normal numbers, specifically the amount of power required to compute, describe, compress and extract from them.

It is somewhere in the intersection of computability, logic, number theory and information theory.

[Ozle]

Well done Mr Net!!

Now, I've got this rash I want you to look at...

[soulnet]

Now, I've got this rash I want you to look at...

Please, send me the index codifying a Turing machine outputting an infinite binary word codifying your problem and I will see what I can do. In the meantime, take an aspirin, start a diet, drink more liquids, stop smoking, exercise and try to rest.

[Witherweaver]

Despite being on this forum for more than a year, I have never wrote an introduction here. And today, I find myself in need to communicate to everyone that I became a doctor. A real doctor, those that spend all time thinking problems nobody else understands and that have no impact in everyone else's life, not the kinds that saves life or those other mundane tasks.

Anyway, thanks for providing a way to keep being nerdy while resting from research.

For the math or CS inclined, if anyone would like to read the thesis, you are welcomed to ask for it. I am not expecting any responses on this, but after so much work, if I can get at least one or two people to read them besides the ones that are forced to, it would be nice.

So, to introduce myself, I am almost 30 years old now, almost-married (not legally married, but factually) recently graduated from my PhD in Computer Science, and addicted to IRL and online Dominion. I live in Argentina but I am considering a job offer that may make me move to the bay area in California, USA in a year or so.

So, story.  I got my PhD almost two years ago.  A couple months after defending, I was on a plane ride.  I've flown a decent amount of times before, but this was the first time in my life where someone had a medical issue and the stewardess got on the intercom and asked if there was a doctor on board.  My friend was on the flight a few rows back and I shot him a look, and he was mouthing "You gotta go up there!"

Anyway, congratulations!

[Ozle]

Now, I've got this rash I want you to look at...

Please, send me the index codifying a Turing machine outputting an infinite binary word codifying your problem and I will see what I can do. In the meantime, take an aspirin, start a diet, drink more liquids, stop smoking, exercise and try to rest.

Oh sorry no, it had nothing to do with your doctorate, I just like showing people my rash

[theory]

For the math or CS inclined, if anyone would like to read the thesis, you are welcomed to ask for it.

Please post it!  There are many people who lie about being doctors to get prescription pills and such and we must verify your status in order to continue your regular shipments of Percocet.

[soulnet]

Please post it!  There are many people who lie about being doctors to get prescription pills and such and we must verify your status in order to continue your regular shipments of Percocet.

Now that I graduated I don't need them anymore. Feel free to stop the shippings.

If any part of the post was for real, the thesis is here (all the actual content is in English, but the cover and part of the acknowledgements are in Spanish): http://www.dc.uba.ar/inv/tesis/doctorado/Tesis%20Heiber%202014/at_download/file

[florrat]

Interesting! I skimmed through parts of it, and after reading the abstract, I was interested in what you meant by "just above quadratic time." I assumed it would be something like n²log(n), but I had also seen the inverse the inverse Ackermann function α in some complexity bounds, so I also thought that something like n²α(n) would be possible. But seeing Theorem 3.3.3 it seems the bound is even stricter, right? Now I'm wondering whether the complexity bound on the algorithm I've heard earlier could also be improved in the same way from "inverse Ackermann function" to "any nondecreasing unbounded computable function." I'm not sure which algorithm it was, though, it had to do with graph theory (though probably that doesn't help much).

Also, this is the first times I've seen a "practical" complexity in the Borel hierarchy which was higher than Pi-0-3 or Sigma-0-3. But you didn't prove that absolute abnormality does not have a lower complexity than Pi-0-4, right?

After chapter 3 I couldn't understand the theorems anymore, then it became too computer-science-y for me (having a math background) (not that I want to give the impression that I've read or even tried to understand much of what you've done in the first chapters).

[soulnet]

Interesting! I skimmed through parts of it, and after reading the abstract, I was interested in what you meant by "just above quadratic time." I assumed it would be something like n²log(n), but I had also seen the inverse the inverse Ackermann function α in some complexity bounds, so I also thought that something like n²α(n) would be possible. But seeing Theorem 3.3.3 it seems the bound is even stricter, right? Now I'm wondering whether the complexity bound on the algorithm I've heard earlier could also be improved in the same way from "inverse Ackermann function" to "any nondecreasing unbounded computable function." I'm not sure which algorithm it was, though, it had to do with graph theory (though probably that doesn't help much).

Yes, it is n^2 times any nondecreasing unbounded computable function, so it is less than n^2 times Ackermann composed with itself k times. And the algorithm has nothing to do with graph theory, what made you think that?

Also, this is the first times I've seen a "practical" complexity in the Borel hierarchy which was higher than Pi-0-3 or Sigma-0-3. But you didn't prove that absolute abnormality does not have a lower complexity than Pi-0-4, right?

I did not, but it was proven in the meantime by my advisor and my other co-author on the subject while I was busy with other stuff. The proof is here:
http://www.dc.uba.ar/people/profesores/becher/bases.pdf

After chapter 3 I couldn't understand the theorems anymore, then it became too computer-science-y for me (having a math background) (not that I want to give the impression that I've read or even tried to understand much of what you've done in the first chapters).

It should be pretty understandable. Maybe the text, especially introductions, is CS oriented, but automata theory is really math, possibly more so than algorithms and complexity. Proofs look a lot like category theory, for instance.

[florrat]

Yes, it is n^2 times any nondecreasing unbounded computable function, so it is less than n^2 times Ackermann composed with itself k times. And the algorithm has nothing to do with graph theory, what made you think that?

That is indeed just above quadratic. Never even imagined before that there would be such small steps in the complexity hierarchy You just blew my mind. And clearly there are even smaller steps, like n^2 * inverse-busy-beaver-function(n), but I assume that such runtimes are not possible for algorithms (i.e. Turing machines)?

My comment about graph theory wasn't saying that it had anything to do with your algorithm. I was just rambling about some algorithm I've seen earlier, which had complexity O(n*α(n)) or O(n^2*α(n)) or something, and I was wondering whether that α could also be replaced by "any nondecreasing unbounded computable function", because I find it hard to imagine that there are actual practical algorithms which have such tiny differences in runtime. Or do you know of an (non-pathological) algorithm which is O(n^k*α(n)) but not O(n^k*f(n)) for some k and some nondecreasing unbounded computable function (and with non-pathological I mean some algorithm not specifically designed to have such a property. Clearly there are such algorithms, but are there such algorithms which are actually practical)?

I did not, but it was proven in the meantime by my advisor and my other co-author on the subject while I was busy with other stuff. The proof is here:
http://www.dc.uba.ar/people/profesores/becher/bases.pdf

Nice!

[soulnet]

That is indeed just above quadratic. Never even imagined before that there would be such small steps in the complexity hierarchy You just blew my mind. And clearly there are even smaller steps, like n^2 * inverse-busy-beaver-function(n), but I assume that such runtimes are not possible for algorithms (i.e. Turing machines)?

Time complexity function of a total computable function is a computable function because you can compute the runtime by simulating the TM (in short). I guess that means any algorithm that runs in time above n^2 is worse than some version of our algorithm (for each computable unbounded non-decreasing f, the algorithm is different). Thanks, I have never thought about it that way.

Or do you know of an (non-pathological) algorithm which is O(n^k*α(n)) but not O(n^k*f(n)) for some k and some nondecreasing unbounded computable function (and with non-pathological I mean some algorithm not specifically designed to have such a property. Clearly there are such algorithms, but are there such algorithms which are actually practical)?

Yes, inverse Ackerman is not really "just" a really slow-growing function. It arises "naturally". For instance, in runtimes of certain versions of union-find structure, which in turn affects the runtime of Kruskal algorithm to compute minimum spanning tree (maybe this is the graph algorithm you were talking about before?). Ok, this is definitely CS ground.

Caveat: For Kruskal algorithm to have ackerman function in its running time, you need to sort in linear time, which IS possible with non-usual but more correct complexity in terms of bitsize of input instead of complexity of RAM machines or complexity in terms of number of comparissons, which are both more or less equivalently wrong in general, though they are simpler and more practical for analysis of usual algorithms (i.e., when its reasonable to assume integers are bounded and you can do operations on them in constant time).

Note for the uninitiated: Unbounded constant makes sum or comparisson of integers to not be constant time, as it is usually assumed. Bounded integers makes sorting linear by just using bucket-sort. Of course, in practice, assuming unbounded integers with constant-time sum/comparisson is reasonable and assuming bucket-sorting an array of 64-bit integers is not, but theoretically, both are equivalent.

[Kirian]

The next time someone tells me about how much of a "math person" I am, I'm going to point them to this thread and say "This is about math, and I don't understand any of the words that are actually about math."

Congrats soulnet!

[sudgy]

The next time someone tells me about how much of a "math person" I am, I'm going to point them to this thread and say "This is about math, and I don't understand any of the words that are actually about math."

Congrats soulnet!

Me too...  For fun, I decided to look at the first technical post to see how far I could get into it.

Interesting! I skimmed through parts of it, and after reading the abstract [I think that was a section], I was interested in what you meant by "just above quadratic time." I assumed it would be something like n²log(n)[I know this is the speed of an algorithm, but I don't know quite how it's saying it.  I'm lost.] ...

[florrat]

Time complexity function of a total computable function is a computable function because you can compute the runtime by simulating the TM (in short). I guess that means any algorithm that runs in time above n^2 is worse than some version of our algorithm (for each computable unbounded non-decreasing f, the algorithm is different). Thanks, I have never thought about it that way.

Ah! That makes sense. I thought there might be some halting-like problems, but assuming the function is total that is of course no problem.

Yes, inverse Ackerman is not really "just" a really slow-growing function. It arises "naturally". For instance, in runtimes of certain versions of union-find structure, which in turn affects the runtime of Kruskal algorithm to compute minimum spanning tree (maybe this is the graph algorithm you were talking about before?). Ok, this is definitely CS ground.

Caveat: For Kruskal algorithm to have ackerman function in its running time, you need to sort in linear time, which IS possible with non-usual but more correct complexity in terms of bitsize of input instead of complexity of RAM machines or complexity in terms of number of comparissons, which are both more or less equivalently wrong in general, though they are simpler and more practical for analysis of usual algorithms (i.e., when its reasonable to assume integers are bounded and you can do operations on them in constant time).

Note for the uninitiated: Unbounded constant makes sum or comparisson of integers to not be constant time, as it is usually assumed. Bounded integers makes sorting linear by just using bucket-sort. Of course, in practice, assuming unbounded integers with constant-time sum/comparisson is reasonable and assuming bucket-sorting an array of 64-bit integers is not, but theoretically, both are equivalent.

Thanks for your answer. This was precisely the kind of answer I was looking for. The algorithm I was talking about was indeed (almost surely) Kruskal algorithm. I remember that he told i some early class that we used the bitsize as the size of the input (the class was rather high level, so we never formally defined Turing machines/input size and stuff like that), so that should be right. I didn't know that was the less conventional complexity measure.

Oh, and I forgot the most important part : congratulations with your graduation! I hope to join you in 4~5 years!

[soulnet]

The next time someone tells me about how much of a "math person" I am, I'm going to point them to this thread and say "This is about math, and I don't understand any of the words that are actually about math."

Well, if that disqualifies someone for being a math person, then nobody is one. Science in general is so atomized, nobody really understands even 10% of what's done in a given field.

Oh, and I forgot the most important part : congratulations with your graduation! I hope to join you in 4~5 years!

Thanks, and good luck with your own. But don't tell the rest of the mortals that drugs actually make you live longer, alcohol makes you invulnerable to car accidents and STDs make lettuce taste like chocolate. That is just for us academics to know and enjoy.

[soulnet]

BTW, in the party after the defense, my girlfriend and a couple of close friends prepared as a surprise some thematic songs. One was about procrastinating writing the thesis because of playing Dominion. If someone is interested, this are the lyrics. Of course, it is filled with inside jokes and names of people involved (my advisor, PhD board members, etc). And, it is in Spanish. Moreover, it is also filled with Argentinian slang, and some words I think are even particular to Buenos Aires and the surroundings. But, for those who may appreciate it, here it goes.

The music is from "Lunita Tucumana", an Argentinian folklore song from the north of the country. Here is a well known version:

Yo no le canto al Dominion
por divertido nomás
le canto porque él sabe
de todo mi investigar...
cartas en combinaciones
y maneras de jugar.

Benditas sus expansiones
pero sobre todo que esté en internet
si hoy anda bien el sitio
entraré entraré...
y a mi Dominion querido
jugaré jugaré.

En el juego hay decisiones
complicadas de tomar
también en mi día a día
si jugar o tipear...
ya me pongo a hacer la tesis
solo un partidito más.

Terrible esa witch maldita
me llenó de curses no hay nada que hacer
tengo que dejar el juego
de una vez de una vez...
si no me niega la beca
Conicet Conicet.

Ayer tuve un sueño raro
difícil de interpretar
trasheaba toda la tesis
ganaba victory cards...
la Becher contrabandeaba
un precioso talismán.

Hoy me levanté con pilas
me hice una tostada y le unté Casancrem
y a punto de abrir el Látex
derrapé derrapé…
Abrí el Dominion maldito
me cebé me cebé me cebé...
abrí el Dominion maldito
otra vez otra vez otra vez.

[florrat]

Procrastinating because of playing Dominion? Wonder what that feels like...

[MarkowKette]

congrats to your graduation!

having a short look into your thesis i remember why i always hated doing the computational stuff during my studies.
But as numbertheory is my second favourite subject i at least found a few things i could understand.