For instance, I asked ChatGPT to implement the greedy peeling algorithm for densest subgraph (a.k.a. Charikar's algorithm). The output was correct but the algorithm did not run in linear time. Then I prompted it to add the data structures for making it run in linear time and it just failed. - ThreadSky

About ThreadSky

stefanresearch.bsky.social • 9 days ago

For instance, I asked ChatGPT to implement the greedy peeling algorithm for densest subgraph (a.k.a. Charikar's algorithm). The output was correct but the algorithm did not run in linear time. Then I prompted it to add the data structures for making it run in linear time and it just failed.

Comments

blubball.bsky.social•9 days ago

I think your expectations are not low enough.

bellecguill.bsky.social•9 days ago

Which version? Here is the output of Claude Sonnet 3.5:
https://claude.site/artifacts/d9c4a5f0-42c4-4852-a5a7-bef059201837

I did not play much with the prompt.

stefanresearch.bsky.social•9 days ago

Did you run this? To me, it seems like its output is wrong and also it is also very slow. I think the issue is that stores a lot of outdated information on the heaps. ChatGPT also tried doing things with heaps, but one has to use linked lists to get a good implementation.

austinlbuchanan.bsky.social•9 days ago

Is this the same as a minimum degree ordering (a la k-core and degeneracy)? If so, have you tried array-based implementations? From what @totalunimodular.bsky.social has told me, they’re faster than linked list ones due to fewer cache misses. Appendix A1 discusses this: https://par.nsf.gov/servlets/purl/10250666

stefanresearch.bsky.social•9 days ago

Yes, it is the same. I did not know about the array-based implementations, I will have a look at some point, this is interesting. My main point, however, was that I was surprised that ChatGPT could not come up with a linear-time algorithm for this problem, despite my prompting.

bellecguill.bsky.social•8 days ago

No I did not try

Posting Rules

Be respectful to others
No spam or self-promotion
Stay on topic
Follow Bluesky's terms of service

Comments

Posting Rules

Reply