--- Log opened Thu Dec 05 00:00:32 2013 01:01 < amiller> gmaxwell, what do you think of the transaction notation in the "mpc on bitcoin" paper 01:01 < amiller> is it easy to read? 01:02 < amiller> it's a pretty sound compromise between the current academic notation and how we're used to looking at them, i think 01:03 < amiller> i guess i should try writing something else out in that style 08:21 < jtimon> maaku I'm still on page 5, but this P = NP paper looks very good 08:22 < jtimon> I thought you believed this was possible since you tried it yourself 08:28 < fagmuffinz> jtimon, link? 08:28 < jtimon> supposid proof of P=NP : http://arxiv.org/pdf/1208.0954.pdf 08:28 < jtimon> dubious of a proof that's only 24 pages long 08:38 < t7> can you express the problem in coq or agda? 08:46 < _ingsoc> For a second I thought it was this guy: https://en.wikipedia.org/wiki/Sergei_Yakhontov 08:46 < _ingsoc> I would have been like, damn, that's badass. 08:52 < iddo> jtimon: it's not new, it's revised from 2012, see http://arxiv.org/abs/1208.0954 and http://www.win.tue.nl/~gwoegi/P-versus-NP.htm 08:53 < nsh> what was the problem in 2012? 08:53 < nsh> shouldn't a constructive proof of P=NP leads pretty directly to an efficient algorithms/reductions for All The Problems 08:54 < nsh> ? 08:54 < TD> huh 08:54 < TD> it's funny to see a list of papers along with claims "This paper proves P=NP" followed by "This paper proves P/=NP" 08:55 < nsh> yeah 08:55 < nsh> -- 08:55 < nsh> [Equal]: In September 2012, Sergey V. Yakhontov proved that P=NP. The proof is constructive, and explicitly gives a polynomial time deterministic algorithm that determines whether there exists a polynomial-length accepting computational path for a given non-deterministic single-tape Turing machine. The paper is available at http://arxiv.org/abs/1208.0954. 08:55 < nsh> (Thanks to Ricardo Mota Gomes for providing this link.) 08:55 < nsh> -- 08:55 < iddo> nsh: serious people stopped trying to look for problems in non-peer-reviewed papers like this, e.g. http://www.wisdom.weizmann.ac.il/~oded/p-vs-np.html 08:56 < nsh> (constructively determining the existence of something is not constructive) 08:56 < TD> isn't looking for problems rather what peer review means? 08:56 < sipa> nsh: there are classes above NP that would be unaffected (ExpTime, ...) 08:56 < nsh> sipa, right 08:56 < sipa> also, polynomial does not imply efficient by any real-world standard 08:56 < sipa> (assume it was polynomial in the 100th degree?) 08:58 < nsh> have there been many cases of polynomial algorithms being found but only with high exponents? 08:58 < nsh> i have the impression (but i don't know how reliable it is) that generally relatively efficient algorithms are found where they exist at all 08:58 < iddo> TD: yeah but they prefer (anonymous) submission to conference for peer review, instead of posting it publicly and confusing random people who come across false proofs 08:58 < nsh> confusion has some overlap with inspiration :) 08:58 < nsh> i don't mind 1000 quacks if there's one genius 08:59 < nsh> (the ratio is probably much higher in practice though) 09:01 < iddo> nsh: i think poly time algorithms for interesting problems are no more than a small const in exponent after optimizations, say n^6 or n^12 when n is the bit size 09:02 < nsh> right, i wonder why this is though... seems very... fortunate 09:02 < iddo> nsh: obviously you can have artificial problems like clique of size 1000 in an arbitrary graph, with poly time complexity of n^1000 09:02 < nsh> sure, there'll always be nasty cases. but it's a question of how they're distributed i suppose 09:26 < jtimon> so iddo, has the paper been proven wrong? 09:29 < iddo> jtimon: probably no one serious tried to look and refute it 09:29 < andytoshi> jtimon: this paper is a tangled structure of about 30 definitions and 10 nested algorithms which purports to be a program which proves the existence of a poly-time algo for a given NP problem 09:29 < andytoshi> (i think) 09:29 < andytoshi> nobody is going to peer-review that when it's just a random thing on the arxiv 09:29 < iddo> jtimon: is you google you can find explanations, e.g. http://www.scottaaronson.com/blog/?p=458 09:32 < pigeons> http://arxiv.org/abs/0711.0770 this one is clearer 09:32 < andytoshi> (iddo's link is a general "how to judge P vs NP papers without reading too closely" article) 09:36 < iddo> there was a claim that looked serious (involving a new tecnique of statistical physics) about 3 years ago, so Terence Tao and co. looked and demolished it within a few days after it became public: http://michaelnielsen.org/polymath1/index.php?title=Deolalikar's_P!%3DNP_paper 09:41 < t7> Terence Tao used to hang out in the go-lang irc channel :| 09:45 < andytoshi> does he not anymore? he seems to spend an impossible amount of time hanging out on the internet 09:45 < andytoshi> considering how much work he gets done.. 09:46 < t7> andytoshi i stopped using go a long time ago 09:54 < jtimon> pigeons you gave me a link about a physics unified theory 09:54 < pigeons> yeah sorry, bad joke 09:54 < jtimon> ah, ok 09:54 < jtimon> this one is clearer 09:54 < pigeons> i was trying to comment on the reliability of arxiv.org papers 09:54 < jtimon> I see 09:55 < pigeons> but if you have to explain the joke, it wasnt a very good one :) 09:55 < jtimon> but is there a critique to this concrete proposal? 09:56 < jtimon> although thank you for the link iddo 09:58 < jtimon> or it was just rewarded as "not enough serious" and not reviewd by anyone or something? 12:35 < maaku> jtimon: the paper has only been up for hours 12:36 < jtimon> oh, I see, so there's probably no critique yet 13:37 < zooko> Huh, there are two papers recently added to eprint.iacr.org with "proof of space" in their title. 13:37 < zooko> amiller: have you seen gmaxwell's argument that making mining-effort into a "dual purpose" operation isn't necessarily good? 13:38 < amiller> fwiw i am *not* in favor of "dual purpose" unless the dual purpose is intrinsic to the system itself somehow 13:38 < amiller> zooko, ^ 13:38 < amiller> that probably makes no sense i can try to elaborate though 13:41 * nsh nods 13:41 < gmaxwell> it makes sense to me. 13:42 < andytoshi> it makes sense to me 13:43 < amiller> ok :) 13:43 < andytoshi> though i'd have to think a bit about why you feel that way 13:43 < amiller> these two proofs of space papers are interesitng that they show up though http://eprint.iacr.org/2013/805 and http://eprint.iacr.org/2013/796 13:44 < amiller> i can't really figure out if they're better than gmaxwell's proof of storage 13:46 < nsh> eerily simlar works 13:46 < nsh> (per abstract, at leasts) 13:47 < amiller> oh, one of the auhtors of one of them is also on the Secure Multiparty Computation on Bitcoin paper 13:47 < zooko> amiller: that makes sense. 13:47 < amiller> university of warsaw seems to have a strong bitcoin research faction now... 13:47 < zooko> amiller: because of gmaxwell's argument about weakened incentives for correct consensus-building? 13:48 < amiller> zooko, yes that's the argument i have in mind and think is right 13:48 < zooko> ("consensus-building" ≈ mining) 13:48 < zooko> amiller: thanks. 13:51 < gmaxwell> amiller: I think the first paper there is basically isomorphic to my proposal with a lot of obfscuating language. 13:52 < gmaxwell> well not quite isomorphic. 13:53 < amiller> do we have a standard template form letter yet to send people who write papers and don't cite forums posts they should 13:53 * amiller wants to see whatever iddo sent the lottery paper auhtors 13:54 < _ingsoc> Lottery paper? 13:55 < amiller> _ingsoc, http://eprint.iacr.org/2013/784 summarized in this thread https://bitcointalk.org/index.php?topic=355174.0 13:56 < _ingsoc> Oh cool. Thank you. :) 14:10 < iddo> amiller: i pasted the link here yesterday: http://www.cs.technion.ac.il/~idddo/cointossBitcoin.pdf 14:10 < iddo> i asked them to reference this in their paper, but they haven't replied so far 19:23 < andytoshi> like, in 100 years? 19:24 < andytoshi> it's growing at well under 10gb/year 19:25 < andytoshi> the block limit is 1mb, let's suppose that each one takes 1mb on disk, and that the blocks come every 10 minutes 19:26 < andytoshi> that's 144 per day, 52560 per year 19:26 < andytoshi> 52.5 gb 19:26 < andytoshi> so 20 years minimum 19:26 < gmaxwell> nOgAnOo: Bitcoin already is decenteralized, so I'm confused by your question. 19:31 < phantomcircuit> gmaxwell, i think he means storage of old blocks 19:31 < gavinandresen> andytoshi: yes, but there is broad consensus that we will need to increase the max blocksize soon-ish. 19:33 < phantomcircuit> nOgAnOo, nobody is going to watch that 19:33 < gavinandresen> mmm. it is on youtube, it must be correct. 19:33 < phantomcircuit> you might as well have just asked us to stare at the wall for 5 minutes 19:33 < gavinandresen> nOgAnOo: there are lots of plans for how to scale up bitcoin while keeping it decentralized. 19:34 < gavinandresen> nOgAnOo: actually IMPLEMENTING them will take time, careful thought, etc. 19:34 < gavinandresen> In any case, scaling up is in the category of "good problem to have" 19:36 * andytoshi is actually watching the video.. 19:37 < andytoshi> "250 gigabytes within 2 years" 19:38 < phantomcircuit> andytoshi, otherwise known as "i pulled this number out of my ass" 19:38 < andytoshi> mmhmm 19:38 < andytoshi> after that it sorta crumbles from lies into incoherency 19:38 < andytoshi> to answer your question nOgAnOo, there is thought going into blockchain expansion, but no concrete plans 19:39 < andytoshi> and it's not even close to as urgent as that video claims 19:40 * nsh smiles 19:40 < andytoshi> nOgAnOo: if you listen to this channel you'll see links to research drifting by 19:40 < andytoshi> following them would involve a -lot- of background research i'm afraid 19:40 < jrmithdobbs> so you're a moron asking why you're a moron that doesn't understand a different moron, good show 19:40 < jrmithdobbs> good show indeed 19:41 < andytoshi> but you're not going to get a coherent picture of anything from youtubers 19:42 < phantomcircuit> lol 19:42 < jrmithdobbs> andytoshi: or "christian" researchers ... or any "religious sect" researchers, for that matter 19:43 < jrmithdobbs> andytoshi: "<3 19:43 < edulix> did I read christian researcher in bitcoin-wizards? makes sense, mixing different kind of magic 19:44 < andytoshi> jrmithdobbs: i recently moved to america, was caught off guard by the amount of "god bless"s that go on between strangers here 19:44 < andytoshi> so i give them all the benefit of the doubt 19:45 < amiller> gesundheit 19:45 < jrmithdobbs> andytoshi: where i grew up in texas and have developed a 7th sense for the bullshit and know exactly when to start mocking instead of attempting to teach 19:45 < jrmithdobbs> andytoshi: ;p 19:46 < andytoshi> well, i'm still learning ;) 19:46 < edulix> nOgAnOo: in the new world order, maybe vatican opens the next mtgox :p 19:51 < nsh> there are sci-fi precendents for this 19:52 < nsh> (deranged-seeming religious beliefs inspiring technological uptake from strange quarters) 19:52 < nsh> also historical precedents :) 19:52 < nsh> but the sci-fi ones are more fun 19:53 < jrmithdobbs> we don't need sci-fi examples, we've got luke! ;p 19:59 * nsh smiles 20:20 < amiller> i'm trying to think of how to explain what's significant about the choices made about how much deposits are needed for the lottery game 20:20 < amiller> in N player lottery game from this paper 20:20 < amiller> say each party puts in 1 coin 20:20 < amiller> the point is that one person is supposed to win N coins 20:20 < amiller> first just note that the expected utility is zero 20:21 < amiller> expected money payout anyway 20:21 < amiller> if the other party goes away you don't necessarily learn the result 20:21 < amiller> one of the parties i mean 20:22 < amiller> but who cares if he has already put in his money 20:22 < amiller> there's a sort of common problem in protocols like this where you show fairness is impossible 20:22 < amiller> suppose you *could* carry out the protocol fairly if someone doesn't send their message in time 20:23 < amiller> that means that last parties message is optional and he might as well not send it 20:23 < amiller> but then the second to last party's input must have mattered 20:23 < amiller> so you follow that back and either you already knew the outcome for the beginning, or someone's participation makes a difference whether it's fair or not 20:23 < amiller> and so the solution is to overcompensate 20:24 < amiller> each party places down a *security deposit*, in addition to their bet, that is used to patch over the lack of computational ability in case one party doesn't cooperate 20:25 < amiller> so the choice in this paper is to make each deposit equal to N(N-1) 20:25 < amiller> in other words, the deposit is one *whole jackpot for every player* 20:26 < amiller> that's a pretty extreme deposit 20:26 < amiller> but it is giving the pretty much best possible guarantee, which is pretty cool 20:40 < amiller> i think i can do better 20:40 < amiller> i think there's a way to improve on the total amount of liquidity needed in their scheme 20:41 < amiller> suppose you're willing to wait for t rounds 20:42 < amiller> the first party puts in N coins, the second party puts in N-1 coins, the third party puts in N-2 and so on 20:42 < amiller> and you release people from their obligations in rounds :o 20:44 < andytoshi> so if parties do not show up, the number of rounds is reduced? 20:50 < typex> tl;dr --- Log closed Fri Dec 06 00:00:35 2013