Vervious
2) Randomized polynomial-time algorithms don't exist for NP-hard problems unless P = NP (iirc).
I think you have the right intuition. The issue is that right now cryptography is built on top of relatively "fragile" "average-case hard" problems -- discrete log, lattice stuff, etc. They are hard by assumption and we really don't know how to study them. (I would bet on some of this stuff being broken in our lifetimes).
It'd be really nice to instead base cryptography on an assumption that we are much more confident in being true, i.e. worst-case hardness of 3SAT. (I mean, who is going to prove P=NP). There are two steps:
1) First, show cryptography from average-case hardness of a "more believable" problem.
2) Second, to show average-case hardness of that problem is implied by the worst-case hardness of an NP-complete problem.
(1) is sort of better studied now, with a line of work on meta-complexity. (2) I believe is wide open, as previously mentioned.
Anyways I'm not really an expert in this area, but it's really quite fascinating.
Also, do you have a citation for "We do know with absolute certainty that the decision problem for DLC is NP-Hard"
Another problem with your suggestion: Do we even know that a 1/polynomial sized fraction of 3-coloring instances are hard? (Else you'll never sample one). (NP-Hardness certainly does not give such a guarantee, even though it sounds weak)
if you want to live in an American version of china where instead of bytedance we have zuckagram, go for it. Chinese social media has vastly out-innovated American platforms and the Zuck/Musk response is to ban the competition rather than write a proper law regulating social media platforms
Whereas I think each line of pseudocode in Paxos is much more motivated.
In other words, if a philosopher had to design a crash-fault protocol from scratch, without having seen any before, I think 80% of the time it would look exactly like Paxos.
it’s like reading saying “I was curious about how computer software works so I ordered and read CLRS and I don’t think faster computers are anywhere on the horizon in 100 years…”
I agree with you that land management can mitigate desertification, the same way hunting invasive species can help protect native biodiversity.
This doesn't mean it's wrong to focus on climate change, and by extension, carbon emissions. If anything, they demonstrate that we should focus on climate change. It's like scaling an internet technology company: we want to build something small that has a massive impact.
Reducing carbon emissions will by far have a greater impact than trying to eradicate sea urchins from the pacific northwest. It is just as feasible as better land management. And for things like coral reef bleaching, which I'm personally very interested in, it's unclear if there's any other solution.
For a new beginner to consensus protocols, today, I would start them with Bitcoin, and then move onto Paxos/Tendermint/Simplex, and skip Raft entirely. (Simplex is my paper, a simplified version of PBFT).
The main issue is that someone has got to pick a final ordering. If there’s a universe of millions of possible orderings it seems that the most efficient way is to have a single node pick a single one.
This sounds a lot like the SEC dictating what can and can't be traded in the modern day. We can't trade something if there isn't an exchange for it.
If kale and gold are securities under the current interpretation of the howey test, then the howey test needs to be rewritten.
Plus, I don't think consumers should be protected from dogecoin --- no layman in their right mind invests in doge with the expectation of profit (from common enterprise). Bitcoin is more of a security than doge will ever be.
Certainly some papers are better written than others. But sometimes a blog post cannot replace a paper, unless it also goes into the depth and detail that formalism requires. (Then it becomes a 30 page blog post, where most people don't read past the intro.)
In cryptography, certainly a paper with formal definitions and proofs can be much more valuable than a corresponding blog post. It's a field where formalism is desired, if not necessary. Otherwise you can't check other people's "proofs", or even know what model you're working in.
I think, since people haven't come up with better formalisms, sometimes it's quite obtuse, which gets mistaken as "academic writing", when really it's a best effort to formalize.
But, when learning any cryptographic scheme, in order to understand what is going on, it is certainly necessary to learn the corresponding mathematical tools. Even to define what it means for a scheme to be secure requires a good grasp of probability (and negligible functions in the asymptotic regime).