For the edge-coloring problem, the optimal number of colors needed to properly color the edges of G is always either Delta(G) (the maximum degree of G) or Delta(G) + 1, but deciding which one is the true optimum is an NP-complete problem.
Nevertheless, you can always properly edge-color a graph with Delta(G) + 1 colors. Finding such a coloring could in principle be slow, though: the original proof that Delta(G) + 1 colors is always doable amounted to a O(e(G) * v(G)) algorithm, where e(G) and v(G) denote the number of edges and vertices of G, respectively. This is polynomial, but nowhere near linear. What the paper in question shows is how, given any graph G, to find an edge coloring using Delta(G) + 1 colors in O(e(G) * log(Delta(G))) time, which is linear time if the maximum degree is a constant.
Yes. The article ran through this point as follows:
"In 1964, a mathematician named Vadim Vizing proved a shocking result: No matter how large a graph is, it’s easy to figure out how many colors you’ll need to color it. Simply look for the maximum number of lines (or edges) connected to a single point (or vertex), and add 1."
I keep wondering why I ever read Quanta Magazine. It takes a pretty generous reading of "need" to make this a correct statement.
Not really. Coloring a graph is almost always talking about proper coloring, meaning that things that objects that are related receive different colors.
If you read the introduction, you'll also read that the goal is to "color each of your lines and require that for every point, no two lines connected to it have the same color."
Ps. "How many colors a graph needs" is a very well established term in computer science and graph theory.
I think the comment referred to the phrase „a graph needs X (colors or whatever)“. For me, this can be read two ways: 1. „a graph always needs at least X colors“ or 2. „a graph always needs at most X colors“.
Personally, I would interpret this as option 1 (and so did the comment above I assume). In that case, the statement is wrong. But I’d prefer to specify „at most/ at least“ anyways.
Or even better, use actual vocabulary. „For every graph there exists a coloring with X colors.“ or „any graph can be coloured using X colors“.
PS: I also agree with the sentiment about quanta magazine. It’s hard to get some actual information from their articles if you know the topic.
Parent's point is that sometimes (but not always) the store is perfectly fine selling you a car for $1 less than what the "price tag" of Delta(G)+1 dollars asks for, so "need" is a bit inaccurate.
As you point out, 'icônes' is French for 'icons'; the name is probably related to the fact that the site is built using Vite. Was NES capitalized in the title earlier?
> Of course, the classic response is "get a better MUA you luser"
Git is distributed and allows you to work efficiently with poor connectivity, having full history available at any time, which is a big accessibility point for people with limited connectivity (and also helps people working while traveling, for example). If you do have any email client, you get all of this as well, plus arbitrarily powerful, low-latency filtering and searching. I recommend Greg KH's "Patches carved into stone tablets" talk [0].
Despite your "luser" strawman, people advocating for client-side MUAs mean well and have a point. Try replacing "webmail" by "Notepad" and "client-side MUA" by "emacs/vim" to see how your argument sounds. You probably spend a decent amount of time interacting with email, and the investment in setting up a fast, flexible and powerful environment (preferably reusing your text editor for composing messages) for doing so pays for itself soon.
> Try replacing "webmail" by "Notepad" and "client-side MUA" by "emacs/vim" to see how your argument sounds.
As it happens, I'm the kind of masochist who uses Sublime Text with no plugins for most of my programming (and literal Notepad for most of my note-taking on Windows), so I find value in letting people stick to their familiar workflow, even if some might see that workflow as somewhere between 'grossly inferior' and 'literally unusable'.
The nice thing with remote Git repos is that you don't need to care at all about how they work internally: you can speak to them using the same Git client (or GUI wrapper, alternative Git-compatible client, etc.) that you use for everything else. Of course, many people would prefer not to use Git at all, but it's a necessary evil to have some client if you want source control, and it doesn't take much work to set up. (At this point, I've installed several source-control tools that I don't really use nor have to worry about.)
But setting up an MUA solely for a git-send-email based workflow is several steps beyond that. E.g., some of the Linux maintainers demand inline patches, which physically cannot be done through many webmail services. So you're left with the slog of finding the right incantations for git-send-email (or an MUA you don't need for anything else) to provide the right credentials to an obscure SMTP proxy. And then you have to worry about how well-protected those credentials are, unless you have some sort of keyring or 2FA integration.
> You probably spend a decent amount of time interacting with email, and the investment in setting up a fast, flexible and powerful environment (preferably reusing your text editor for composing messages) for doing so pays for itself soon.
I'm a bit curious, how well do these tools handle HTML email? Webmail services come with WYSIWYG editors that I make liberal use of for formatted text. There's a big overlap between the "email patches are great!" and "HTML email is the worst!" crowds, but I'd be surprised if HTML email is totally anathema to today's MUAs.
> As it happens, I'm the kind of masochist who uses Sublime Text without any plugins for most of my programming, so I find value in letting people stick to their familiar workflow, even if some might see that workflow as somewhere between 'grossly inferior' and 'literally unusable'.
I definitely think there are upsides to not tweaking your text editor config endlessly, so I understand your point :) What I meant with "vim/emacs" is mostly that sometimes you really want to automate a text editing task, and then it's really convenient to have a programmable text editor. It's also very much a case of [0].
> I'm a bit curious, how well do these tools handle HTML email?
In my case, I use mu4e in emacs to read my mail. Very basic HTML works by default via emacs's native HTML renderer (see, e.g., [1] for old screenshots). That's my preferred solution because I like the keyboard consistency (it's just an emacs buffer) and because there is a command to view the email in an external browser if needed, but it is also possible to render HTML email accurately in emacs by embedding a webkit widget [2]. As for writing, you can write in Org mode format (emacs markdown, if you will) and it gets converted to HTML on send.
> As for how to move forward, (...) Either Linus takes the pull, and whatever Christoph says is irrelevant, or he doesn't, and R4L dies. Everything else is a waste of everyone's time and energy.
It does look like maintainers should have a "disagree and commit" mentality at some point, whatever decision they end up making.
I thought Rust in Linux was evaluated, discussed and agreed upon years ago. The fact that there are people still trying to sabotage it shows that they don't follow the "disagree and commit" principle.
They are more like "disagree and make the others lives a living hell until they bend to my will".
> I thought Rust in Linux was evaluated, discussed and agreed upon years ago.
I've seen Linus talk about it in one of his public chats with Dirk Hohndel as an interesting experiment that might succeed or fail, or that's the impression I got. I'm not sure everyone else got that memo.
It is not some million dollar RSUs getting vested by year end either way. A lot of them working for the love of craft and prestige. If they can just rollover on a technical disagreement then corporate office job is more suitable than open source OS kernel.
The Linux kernel is most definitely not developed for free by some college student in their bedroom for the most part. It's Intel and Red Hat and similar.
"R4L dies" is hyperbolic nonsense. There are many ways/places to integrate Rust in the kernel, even for wrappers. It's not like "I think this code should be someone else" automatically means the death of Rust.
Marcan goes full nuclear every other time someone disagrees with him. He's very much the "if it's not my preferred way then we might as well not do it at all"-type of engineer (many of us have worked with those people).
People can just include their own dma.rs in driver/.../mydriver/
Whether that's a good or bad approach is besides the point. It's what was suggested as an alternative, and clearly it's something that would work. "You can't use DMA from Rust" is just not true.
If it was a good approach, the C folks would have copied around C files instead of having common core code. They did not do that though, because it'd be counter productive due to increasing maintenance burden.
Everyone knows it would increase maintenance burden, decrease reliability, and increase the amount of apparent churn of rust code in the linux kernel.
Everyone knows you could start the crude way today and refactor the duplication later after it proves itself, if you actually wanted to proceed rather than throw fits.
And after that driver is in use for a while and a million users all depend on it because it works so good, other developers will all on their own start asking "why are we diing this this stupid way? I think the original argument is no longer valid, or we can see now that it never was valid. We should revisit that."
Or as more rust devs work on more modules that each need some similar redundant boilerplate, a larger number of individual devs who each ask the same "hey, can we please get at least this level of concession to have a shim somewhere we can interface with instead of all this fragile tight coupling?" When that grows to become a respectful request from many, including users, instead of a disrespectful demand from a few, you get a different result.
But that is step 2. The opportunity for step 2 sometimes simply will not exist without first going through a step 1.
You want in? Yes but the terms are shitty. Yeah, so, you don't want in? It's obviously OK with most of the kernel devs if the rust devs decide this is not rewarding and go away. They are not eagerly welcoming to this particular development. And they don't have to be. How welcoming would rust developers be to c developers demanding to rewrite cargo in c? Go work on redox and make it so great it takes over and replaces linux by simply being the better choice while being equally free and at least as well managed and clearly visioned.
I don't know the better way to ask this question, so I'm just going to ask it:
"Congratulations, you're right, and nobody cares."
Now what? Just complain that the kernel isn't hospitable to Rust, and hope 15 years from now we're all using some Linux-compatible kernel built ground-up in Rust?
I genuinely want to know where you go from this position.
I am trying to explain why someone would say this.
I think Rust in Linux makes sense, but honestly, Rust doesn’t need Linux to be successful, and I barely use Linux personally. If they decide Rust for Linux is not a thing, that’s for the folks who work on and care about Linux to deal with. This isn’t my fight, I am just observing.
I’ve been primarily a Windows user for many years now, but I do use some WSL. My main OS is already shipping Rust, and in the actual kernel, without all of this wailing and gnashing of teeth. (That said I respect the approach Linux is taking here, I don't think it's inherently bad.)
Oh, and honestly, what I believe is happening here is just that, from Linus's perspective, folks should know that because this isn't in Hellwig's part of the tree, his NACK doesn't actually matter, and he'll just end up pulling this patch in anyway. There's no need to intervene because there isn't actually obstruction going on. The internet is just going wild about this drama because they fundamentally misunderstand how kernel development works, and because people are slinging mud on the LKML. That's why he only commented on Hector's behavior.
I can see that perspective, though I would prefer a different management style, but that's also why (among other reasons) I don't care to contribute to the kernel.
> Every additional bit that the another language creeps in drastically reduces the maintainability of the kernel as an integrated project. The only reason Linux managed to survive so long is by not having internal boundaries, and adding another language complely breaks this. You might not like my answer, but I will do
everything I can do to stop this.
Volume 4, Fascicle 7 was officially released this week! The latest draft ("prefascicle", dated December 2024) is available at https://www-cs-faculty.stanford.edu/~knuth/fasc7a.ps.gz. As Knuth says, the contents "agree fairly well with the contents of the first paperback printing of Volume 4, Fascicle 7, except for parts of the index. As usual, the prefascicle is 'frozen' and will not be maintained, while the paperback will gradually improve with time."
The real scandal here is the pressure to remove a maintainer based on vague "code of conduct violation grounds" when the supposed "violation" is just expressing an technical preference on code he maintains. Shamelessly weaponizing a code of conduct like this should be a code of conduct violation in itself.
(I am a big proponent of language interop as an alternative to big rewrites. But opinions differ, and my opinion is worth nothing because I'm not a maintainer of the relevant code.)
exactly. using terms like "cancer" or "viral" as a technical analogy is blunt, but is a purely technical argument/opinion, which everyone is free to have and express.
passive aggressive threats (and that is exactly what they are) are not a technical discussion. you can be polite or blunt. you can be nasty or you can be good. but don't confuse polite for for good or blunt for nasty - some of the nastiest meanest behavior is packaged in a nice and polite delivery.
it seems like to me that the rust team fundamentally doesn't understand their role and position. they're showing up to a house that somebody else built and instead of saying "how can i help", they are saying "i have this cool thing, can we add it to your house so we can play too". at first, being bohemian open-source people, the kernel guys say "sure". but then it becomes problematic because it isn't free or easy and there are impacts. and they never asked for it in the first place.
100% the best thing for them to do is go build their own house. why do they even want rust in a 40 million SLOC "C" project? go create a kernel in rust. they could even leverage existing Linux drivers or other components. then it's their house to do what they want, the way they want. figure out how to box up "unsafe" "legacy" filesystems and drivers in their own rust ecosystem.
> The real scandal here is the pressure to remove a maintainer based on vague "code of conduct violation grounds" when the supposed "violation" is just expressing an technical preference on code he maintains.
Definitely not what is happening here. btw what the point of CoC if it's not enforced? I'm not saying this person needs to be removed, but someone needs to talk to a person that says "You might not like my answer, but I will do
everything I can do to stop this." in regard to R4L just based on personal preferences.
Part of "being nice" is accepting that people aren't perfect and just dealing with that, within limits of reason of course. "Assume good faith" and all of that. The phrasing of "cancer" wasn't brilliant, but also really not that bad – certainly not bad enough to warrant removal from the Linux project. That's pretty draconian.
Code of Conduct is not about demanding absolute perfection and then selectively using it as a cudgel to beat people you disagree with. Doubly so since Hector's behaviour over the years has frequently been less than stellar, including in that very thread where he calls Hellwig's comments "distractions orchestrated by a subset of saboteur maintainers who are trying to demoralize you until you give up".[1] Yikes!
Using "cancer" to describe "it will spread everywhere and it will become unmaintainable" is not great, but at the core still a technical disagreement. Outright dismissing people's technical opinions and ascribing malicious motivations as part of a cabal is a mean-spirited and nasty personal attack, and essentially just an insult.
And it's really not "sabotage" to disagree or to be against something and being upfront about it. If that's "sabotage" then anyone saying "I don't think we should go ahead with this" is guilty of "sabotage".
For it to be technical disagreement, there should be _anything_ to back it up. All I've heard is "another language would spread and become unmaintainable" is one, that's just emotions. There is nothing technical about his reasoning on why he doesn't want those patches to land.
> If that's "sabotage" then anyone saying "I don't think we should go ahead with this" is guilty of "sabotage".
Sabotage part is saying "I will do anything to stop rust from landing in Linux code base" (paraphrasing). Calling in cancer just unprofessional and rude, but that's another story...which probably also violates CoC.
"Suffers"? No. But "makes the code harder to work on from my perspective"? Well, some people think that it will. And the Rust people are agreeing with that in the very email thread: their solution is "you don't need to write Rust, we can work together on this". Whether that's a good solution is the point of disagreement.
And of course "I don't want Rust landing in Linux code base" is not the same as "I don't want Rust added to this subsystem, I think it should live somewhere else".
The function defined in the video is "Given a pair of points A and B on the curve, output (x, y, z), where (x, y) is the midpoint and z is the length of the segment connecting A and B", and the pictures are of its image, not its graph. But if you define it visually, then it's very natural to misunderstand it the way you did, since the picture looks a lot like a function graph of a function which takes midpoints (instead of pairs of points) and returns the distance corresponding to that midpoint (which is not well-defined, as you pointed out). If this happens, the viewer is then completely lost, since the rest of the video is dedicated to explaining that the domain of this function is a Möbius strip when you consider it to consist of unordered pairs of points {A, B} (as one should).
Ultimately, if you don't have a 100% formal version of a given statement, some people will find a interpretation different from the intended one (and this is independent of how clever the audience is!). I think 3Blue1Brown knows this and is experimenting with alternate formats; the video is also available as an interactive blog post (https://www.3blue1brown.com/lessons/inscribed-rect-v2) which explicitly defines the function as "f(A, B) = (x, y, z)" and explains what the variables are.
The fact that "given a large enough audience (even of very smart people), there will be different interpretations of any given informal explanation" is a key challenge in teaching mathematics, since it is very unpredictable. In interactive contexts it is possible to interrupt a lecture and ask questions, but it still provides an incentive to focus on formalism, which can leave less time for explaining visualizations and intuition.
