5 ms·
How to store a permutation compactly (2022)
- adamnemecek 3y agoFor anyone who cares, Beneš network was invented by Václav Beneš, son of the former president of Czechoslovakia Edvard Beneš https://en.wikipedia.org/wiki/Edvard_Bene%C5%A1 https://en.wikipedia.org/wiki/Edvard_Bene%C5%A1
- throw_pm23 3y agoAlso known for the eponymous Beneš-decrees which collectively stripped ethnic minorities of certain basic rights, property, and citizenship after the war. https://en.wikipedia.org/wiki/Bene%C5%A1_decrees https://en.wikipedia.org/wiki/Bene%C5%A1_decrees
- xigoi 3y agoThose are from Edvard, not Václav.
- throw_pm23 3y agoSure, the GP mentioned Edvard.
- xigoi 3y agoThe word “also” in your comment implies that you're talking about the subject of the parent comment, which is Václav.
- throw_pm23 3y agoI meant it as continuing the sentence about Edvard, and in any case presidents are more likely to pass decrees than computer scientists. But anyway I see I stepped on a nerve with the comment.
- xigoi 3y ago> But anyway I see I stepped on a nerve with the comment. What? I just wanted to clarify your comment since it seemed to say the wrong thing.
- adamnemecek 3y agoRemind me which ethnicities were those? Also what was the relationship between members of those ethnicities and Nazis? Here's something to jog your memory https://en.wikipedia.org/wiki/1938_German_parliamentary_election_and_referendum#Sudetenland https://en.wikipedia.org/wiki/1938_German_parliamentary_elec...
- throw_pm23 3y agoWhichever they were, the concept of "collective sin" applied to an ethnic group is atrocious.
- adamnemecek 3y agoDude, 99 percent support for Hitler.
- defrost 3y agoHmm, Daniel Bernstein was only 24 when he bought the first of the Bernstein v. United States series to the courts. https://en.wikipedia.org/wiki/Bernstein_v._United_States https://en.wikipedia.org/wiki/Bernstein_v._United_States Nice work there. ( connection being Verified fast formulas for control bits for permutation networks by djb https://cr.yp.to/papers/controlbits-20200923.pdf https://cr.yp.to/papers/controlbits-20200923.pdf )
- deleted 3y ago[deleted]
- pxeger1 3y agoIt's interesting that the author feels the need to justify why this would be useful in practice. I can imagine this could be useful in many contexts - and regardless, I'd be content for this to just be a purely academic exercise.
- H8crilA 3y agoIf you're looking for a proof that the Benesh network can implement any permutation (of size 2^n): https://eng.libretexts.org/Bookshelves/Computer_Science/Programming_and_Computation_Fundamentals/Mathematics_for_Computer_Science_(Lehman_Leighton_and_Meyer)/02%3A_Structures/10%3A_Communication_Networks/10.09%3A_Benes_Network https://eng.libretexts.org/Bookshelves/Computer_Science/Prog... The proof is not super complicated, but it for sure isn't trivial.
- TontonNestor 3y agoThe author seems to think it's a simple exercise, but I agree with you, the proof that you linked, which uses graph coloring, and those in the Beneš or Waksman articles, which use Hall's theorem, are per se easy to understand, but rather hard to come up with.
- shiftingleft 3y ago> Chia replaces Nakamoto’s energy hungry proof-of-work consensus with an eco-friendly proof-of-space. Don't be fooled, proof-of-space will eat up SSDs like no tomorrow and you're still hoarding HDDs for little gain. Proofs of space prove that you're storing some useless data. Typically you use HDDs to store the useless data, but to prepare such a HDD you need an SSD. The setup process will perform so many writes that the SSD will be garbage very soon.
- CrampusDestrus 3y agoWhy can't they use Folding@Home as proof of something?
- div72 3y agoFor something to be used in PoW, it needs to be both hard to solve and easy to verify. Protein folding checks the first box but not the second. As an example, prime number calculations check the both boxes and there's Primecoin which bases its proof algorithm on prime chains. This only applies if you prefer to be trustless though. If you are willing shed a bit, you can trust Folding@Home's scoreboard data (and whoever supplies the data to you) to use it as a pseudo-"PoW" and run a proper proof algorithm beneath. (which is also done by a number of coins like Banano, Curecoin, Gridcoin. You can see their people on the leaderboard with weird names like x_ALL_x, x_GRC_x or just bunch of non-sensical alphanumeric characters.)
- irq-1 3y agoDo you know PoW could work with backup data? It would be great if people could have a little backup space for the price of some compute, instead of cash or "free" backup.
- Dylan16807 3y agoAre you looking for Sia and Storj? I would say Filecoin but very strange things are going on with that coin and I can't wrap my head around how you're supposed to actually store things.
- sacnoradhq 3y agoDan Boneh's intro cryptography course is excellent.[0] The closest to a Khan Academy "cryptography edition" one can find. 0. https://www.coursera.org/learn/crypto https://www.coursera.org/learn/crypto PS: I must be old because I can't get past the neologism of "crypto" abused to mean "cryptocurrency" rather than "cryptography."
- foobarbecue 3y agoI love that Chia doesn't have miners, it has "farmers."
- 0xFFOOFF 3y agoGod you guys post the most boring things.
- atesti 3y agoIs there any source code or ready to use library?