Hacker News Board Hacker News, browsed like a classic message board
Live data from Hacker News

k-Coloring is Faster than Computing the Chromatic Number

arxiv.org

Post reply on HN
Print view View original

21–25 of 25 posts

Re: k-Coloring is Faster than Computing the Chromatic Number

#21

Post by emil-lp »

yablak wrote: post #20
emil-lp wrote: post #16

Earlier quoted context omitted.

A small tip: if you want to do this trick, with an exponential F, you probably want a linear search rather than a binary search. If your k << N then F(N/2) is going to eat up all of the running time of ΣF(i).

Is it faster to start by doubling?

It depends on F, but usually, if F is like 2^n, then a single F(i) for a too large i, is slower than computing F(j) for all j This is illustrated by the fact that there are more leaves in a complete binary tree than all the other nodes summed.

Re: k-Coloring is Faster than Computing the Chromatic Number

#22

Post by aleph_minus_one »

LegionMammal978 wrote: post #13
aleph_minus_one wrote: post #11

Earlier quoted context omitted.

> The Bipartite graph class is also a bit silly in this case, since it's by definition the 2-colorable graphs Be a little bit careful here: another common textbook definitions of bipartite graphs are: - a graph is bipartite iff it has no odd circle. - (for people who are into algebraic/spectral graph theory :-) ) a graph is bipartite iff its spectrum is symmetric. I personally like the latter two definitions because…

One curiosity that in the case of infinite graphs, "no odd cycles" doesn't imply "2-colorable" without the axiom of choice for families of 2-element sets [0]. It's somewhat similar to how in the definition of a well-founded relation, "no infinite descending chains" doesn't imply "every nonempty subset has a minimal element" without dependent choice. (One of my recent projects has been trying to prove the existence of…

This is a really cool fact. :-)

Re: k-Coloring is Faster than Computing the Chromatic Number

#23

Post by gus_massa »

airstrike wrote: post #18
gus_massa wrote: post #12

Earlier quoted context omitted.

> whereas LLM mistakes are somewhat random, like the carwash problem At least in math problems, AI mistakes generally occur more frequently given the difficulty of the task. The carwash problem is very undespecified. The question should be something like " I am American. I live in a single family home in a suburb. Each member of my family has their own car. All the cars are parked during the night at home. My boss do…

You're picking on the specifics of the carwash problem rather than acknowledging countless other similar problems exist. The original one was strawberry, but that got RL'd away

The strawberry problem is a translation/encoding problem, not a context problem. To be more efficient and cheap, the implementations use tokens, that is very-slightly-similar to translate it to Japanese: イチゴには「r」がいくつありますか？

(I don't speak Japanese, I used autotranslation, so it may be wrong.)

There are no "r" in the token of strawberry.

Re: k-Coloring is Faster than Computing the Chromatic Number

#24

Post by airstrike »

gus_massa wrote: post #23
airstrike wrote: post #18

Earlier quoted context omitted.

You're picking on the specifics of the carwash problem rather than acknowledging countless other similar problems exist. The original one was strawberry, but that got RL'd away

The strawberry problem is a translation/encoding problem, not a context problem. To be more efficient and cheap, the implementations use tokens, that is very-slightly-similar to translate it to Japanese: イチゴには「r」がいくつありますか？ (I don't speak Japanese, I used autotranslation, so it may be wrong.) There are no "r" in the token of strawberry.

And yet, if models could indeed reason, that would not be an issue. You're arguing my point.

Re: k-Coloring is Faster than Computing the Chromatic Number

#25

Post by yndoendo »

aleph_minus_one wrote: post #17
yndoendo wrote: post #7

Earlier quoted context omitted.

I worded a questions similar to this with a person in the finance industry. He was very receptive of AI since it is one of the easiest ways to grow stock portfolio. Say you have two assistant employees. One that reads the reports and one that uses AI to summarize the content. You are sitting in a high value meeting. You only can have one assistant with you in the meeting. Which one would you pick, the persons that re…

> Say you have two assistant employees. One that reads the reports and one that uses AI to summarize the content. You are sitting in a high value meeting. You only can have one assistant with you in the meeting. Which one would you pick, the persons that read the reports or the person who only used AI? I would take the person who only used AI. Why? Your fictional problem has the silent assumption that if you are in a…

There was no time frame from reading the report and AI summary to having to apply the report is stated. It could be one hour to 30 days in between or more.

There was no statement if the meeting was scheduled or impromptu. Client(s) might have saw you in public or at an event. Or at a trade show and there the report only applies to the single client versus to many clients.

There was no statement of report ownership. All parties might have access to it.

There is a chance that AI lied / hallucinated the summary. Only to know would be taking time to read the report and validate it.

AI only consumption has shown to reduce retention of information compared to reading the core content.

Ever have someone tell you why they want AI? I have, it was because they do not want to read the reports.

Post reply on HN