« first day (139 days earlier)      last day (433 days later) » 

8:57 AM
4
A: What computational problems would be good proof-of-work problems for cryptocurrency mining?

Joseph Van NameHere is a recent paper, which has been received positively in the cryptocurrency community. I will expand on this paper here. While conventional hash functions do not allow one to construct very useful proof-of-work problems, if one replaces the hash function for the proof-of-work with a random...

 
9:10 AM
I remember that Joseph Van Name helped me with some technical problems in non-classical logic/lattice theory previously. Now he has an idea to influence hardware manufacturers in order to make the world a better place. I happen to work in that industry, and know how many technologies get killed just at the moment they reach alpha or beta stage. It is the moment were they have overcome the technical challenges, and would start to compete against existing solutions.
> Therefore, since reversible computation has this computational overhead and since reversible computers currently do not exist, chip manufacturers do not have much of an incentive to manufacture reversible computing devices. However, since RCO-POW problems are just as easily solved using nearly reversible computational devices, chip manufacturers will be motivated to produce energy efficient reversible devices to solve these RCO-POW problems.
 
9:25 AM
I recently had a "naive" idea for proving ALogTime != PH, or at least for better understanding why proving this is hard. Actually, I start to understand why it is hard to prove now. Theorem 8 in Complexity of Input-Driven Pushdown Automata and the remarks on later research show that ALogTime (=uniform NC^1) in indeed powerful!
The paper P. W. Dymond, “Input-driven languages are in log n depth”, Information Processing Letters, 26 (1988), 247–250 which finally proved that it is really powerful is not available online, but the paper by S. Buss which developed the required technique for showing this is online, and it is actually the same paper which gave me my "naive" idea in the first place. Now I guessed that already TC^0 is quite powerful, and it is!
In fact, showing ALogTime != PH receives so little attention, since we cannot even prove uniform-TC^0 != PH. Now I learned that MULTIPLICATION is in TC^0, and DIVISION is in TC^0 too. But if TC^0 and NC^1 are really so powerful, shouldn't we theorists try to influence the hardware manufacturers to develop architectures which really allow to benefit from that power?
And maybe TC^1 will turn out to be so close to NL that having hardware with extremely good support for NC^1 and TC^1 algorithms will allow to solve all practically occurring NL problems in extremely short time? Of course, it would be a strange step, in making computers which are even stupider and still even faster than current computers. But the potential actually appears to me to be quite real!
 

« first day (139 days earlier)      last day (433 days later) »