frontpage.
newsnewestaskshowjobs

Open Source @Github

fp.

Outages reported at Bank of America, Chase, U.S. Bank, Wells Fargo and Zelle

https://apnews.com/article/bank-outage-chase-wells-fargo-truist-50fee2693c22f597fa6ca51a97ef2cda
306•samk3nny•1h ago•201 comments

Grazing sheep in fields with solar arrays

https://news.cornell.edu/stories/2026/10/sheep-grazing-solar-fields-offers-farmers-economic-ecolo...
125•PaulHoule•2h ago•104 comments

Jiff 1.0: A datetime library for Rust

https://burntsushi.net/jiff/
190•burntsushi•3h ago•45 comments

Software is breaking down at a systemic level

https://www.breck-mckye.com/blog/2026/11/software-is-breaking-down-at-a-systemic-level/
147•zero_shift•1h ago•100 comments

Frame – 31.5" color ePaper display

https://trmnl.com/blog/introducing-frame
124•geerlingguy•3h ago•65 comments

The Secret ThinkPad Powerbutton Code to Bring Dead Laptops Back to Life (2007)

https://masnick.com/posts/the-secret-thinkpad-powerbutton-code-to-bring-dead-laptops-back-to-life/
259•sammatilda•8h ago•103 comments

Aristotle Expands into Rust

https://www.harmonic.fun/news/aristotle-rust-verification/
52•maufl•2h ago•27 comments

Squircles

https://linebender.org/wiki/curves/squircle/
14•raphlinus•12h ago•5 comments

Michael Mann's 'Heat' Copyright Fight Turns on a Deal with Himself

https://copyrightlately.com/michael-mann-heat-copyright-termination/
40•speckx•2h ago•6 comments

How to Intercept HTTP/3 Traffic: QUIC and Qpack

https://interceptsuite.com/blog/intercept-http3-traffic-quic-qpack-explained/
10•anof-cyber•40m ago•0 comments

Jolt – Clojure that speaks C

https://jolt-lang.net/
48•michaelsbradley•3h ago•11 comments

Many of Amazon’s Black Friday and Cyber Monday “deals” offered no savings

http://groundworkcollaborative.org/news/amazons-decoy-deals-groundwork-investigation-reveals-near...
673•DeepLogin•6h ago•408 comments

How to make almost anything

https://pub.cba.mit.edu/863.26/site/
780•o4c•14h ago•130 comments

Giant Roadside Attractions Face Mounting Costs and an Uncertain Future

https://www.nytimes.com/2026/11/08/world/canada/roadside-attractions-giant-dinosaur.html
13•bookofjoe•6d ago•8 comments

Just 400 US Data Centers Use More Electricity Than Michigan

https://www.wired.com/story/data-centers-use-more-electricity-than-michigan/
55•Betelbuddy•2h ago•45 comments

Interpreting claims that a theorem is correct because it was checked in Lean

https://xenaproject.wordpress.com/2026/11/12/and-the-proof-is-checked-in-lean/
252•matt_d•12h ago•109 comments

Show HN: Fakemetrics.com – "build in public" like a superstar

https://fakemetrics.com/
30•tigranbs•2h ago•10 comments

OOS – an open operating system for the Rigol Scopes

https://www.eevblog.com/forum/testgear/oos-an-open-operating-system-for-the-rigol-scopes/
106•qwezxcrty•2d ago•35 comments

Smallest possible nopert polyhedra: the Septopert

https://github.com/tom7/noperts/blob/main/septopert.md
35•RebelPotato•2d ago•3 comments

A 512 KiB binary message teaching chess without a shared language

https://artemlegotin.com/golden-board/
34•legotin•5h ago•6 comments

Researchers track whole body movement with just a smartwatch

https://news.cornell.edu/stories/2026/11/researchers-track-whole-body-movement-just-smartwatch
186•PaulHoule•3d ago•62 comments

The Active Directory Era Is Finally Over

https://infisical.com/blog/active-directory-machine-identity
90•FinnLobsien•5h ago•58 comments

First phase of embedded assessments at OpenAI

https://openai.com/index/our-first-phase-of-embedded-assessments/
15•dvaplima•4h ago•4 comments

Psychic: Like fzf but learns from your actions

https://klauria.tech/psychic/
22•articulatepang•4h ago•6 comments

Winudf – DVD / BluRay driver for DOS, Windows 1.x – 3x / 95 / 98 / ME

https://github.com/ages2001/WINUDF
79•Oxodao•12h ago•12 comments

FBI says Artex AI open-source hacking tool used to breach networks

https://techcrunch.com/2026/11/16/fbi-says-artex-ai-open-source-hacking-tool-used-to-breach-netwo...
19•novateg•1h ago•0 comments

Nature-Based Sanitation. Cihuatlán: A Large-Scale Artificial Wetland

https://revista.unaminternacional.unam.mx/en/nota/12/saneamiento-basado-en-la-naturaleza-cihuatla...
19•bryanrasmussen•2d ago•14 comments

How Billions in Safe Insurance Money Is Being Bet on A.I. Debt

https://www.nytimes.com/2026/11/16/business/insurance-ai-debt.html
29•syllablehq•2h ago•4 comments

Universal XSS in uBlock Origin from website-driven element picker

https://iter.ca/post/ubo-uxss/
586•zaik•18h ago•164 comments

Some OLED MacBook Pro Owners Report Eye Strain and Dizziness

https://www.macrumors.com/2026/11/16/oled-macbook-pro-owners-report-eye-strain/
22•tosh•1h ago•1 comments
Open in hackernews

The Fastest Way yet to Color Graphs

https://www.quantamagazine.org/the-fastest-way-yet-to-color-graphs-20250512/
62•GavCo•1y ago

Comments

tonyarkles•1y ago
In case you haven't looked at the article, this is looking specifically at the Edge Coloring problem and not the more commonly known Vertex Coloring problem. Vertex Coloring is NP-complete unfortunately.
erikvanoosten•1y ago
You can convert edge coloring problems into vertex coloring problems and vice versa through a simple O(n) procedure.
meindnoch•1y ago
Wrong. You can convert edge-coloring problems into vertex-coloring problems of the so-called line graph: https://en.m.wikipedia.org/wiki/Line_graph

But the opposite is not true, because not every graph is a line graph of some other graph.

erikvanoosten•1y ago
Indeed. Thanks, I stand corrected.
tonyarkles•1y ago
Hrm... right. It's been a while. And it looks like both Vertex Coloring and Edge Coloring are both NP-complete (because of the O(n) procedure you're talking about and the ability to reduce both problems down to 3-SAT). I've started looking closer at the actual paper to try to figure out what's going on here. Thanks for the reminder, I miss getting to regularly work on this stuff.

Edit: thanks sibling reply for pointing out that it's not a bidirectional transform.

mauricioc•1y ago
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.

Syzygies•1y ago
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.

JohnKemeny•1y ago
phkahler•1y ago
Is this going to lead to faster compile times? Faster register allocation...
john-h-k•1y ago
Very few compilers actually use vertex coloring for register allocation
isaacimagine•1y ago
Totally. The hard part isn't coloring (you can use simple heuristics to get a decent register assignment), rather, it's figuring out which registers to spill (don't spill registers in hot loops! and a million other things!).
NooneAtAll3•1y ago
and this post isn't even about vertex coloring
DannyBee•1y ago
No.

In SSA, the graphs are chordal, so were already easily colorable (relatively).

Outside of SSA, this is not true, but the coloring is still not the hard part, it's the easy part.

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.

mockerell•1y ago
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.

JohnKemeny•1y ago
What about this statement:

No matter how large a car is, it is easy to figure out how much money you'll need to buy it. Simply look at the price tag.

(From: 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 ...)

mauricioc•1y ago
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.