no, the article is talking about symmetric key crypto also. (i.e. one way functions). You're talking about cryptosystems that don't have proofs of security, or reductions to heuristical assumptions
1) It'd be really really awesome to show average-case hardness version of a natural problem (i.e. 3SAT on a natural distribution) from the worst-case hardness of that problem (i.e. 3SAT). I believe it's wide open in the context of building one-way functions.
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.
That's completely unrelated, the reliance there is because you want to be able to prove "any statement in NP" in zero knowledge. It then suffices to give a protocol for just 3-colorings, because "any statement in NP" can then be reduced to a 3-coloring.
Not sure it's misleading, he did write the word "technically", and anyone who knows what NP-complete is knows that NP-hard does not necessarily mean NP-complete. I am a cryptographer and the article is fine.
Also, do you have a citation for "We do know with absolute certainty that the decision problem for DLC is NP-Hard"
how do you know if an instance you picked is 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)
tit for tat makes the U.S. more like the CCP, and less like the version of the U.S. that stands for freedom and democracy (that I presume you want to live in).
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
Raft has a problem where, in the protocol description, sometimes I have no idea why some line is there, but if you take it out the protocol comes to a grinding halt... it's really a mumble jumble. It has good intuition, but the details are really messy, it's edge cases all the way down.
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.
I don’t see how you can read and understood Nielsen and Chuang in one sitting, unless you are already a quantum computation theorist. I also don’t see how reading what is essentially an algorithms textbook can lead you to develop an informed opinion about the state of quantum computer engineering…
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 think you're being a little selective in trying to show your point. Human-driven climate change is the biggest driver of ecological damage. Even the article you link to is based on a report that climate change is the biggest driver of desertification worldwide.
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.
fyi carbon emissions directly causes global warming and ocean acidification, so yes, mitigating carbon emissions IS very important to help your desertification, rainforests, kelp forests, and coral reefs
A blockchain (without all the bells and whistles) is definitionally equivalent to a state-machine or log replication system (but handling byzantine faults). (Each log entry is just a block).
Consensus protocol researcher here. For what it’s worth, I think that the plethora of blockchain research in the last 10 years has made consensus much easier to understand. Raft (in particular, with all of its subtleties) reads (and implements) like Greek in comparison.
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).
Not really; there are algorithms where many nodes propose proposals in parallel, but eventually only one of those proposals gets finalized (or they maintain only a partial ordering, not a full ordering). (See Bullshark and redbelly iirc)
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.