Comment by varjag
5 days ago
I had my own programming question for a while, which all models from all vendors been robustly failing so far. It is a known problem with surprisingly few published implementations as it had never been a part of leetcode, Euler or typical homework assignments. Yesterday o3-pro cleared it, using a more obscure algorithm I never even heard of.
Can you provide the details? Sounds intriguing
The frustrating thing about private problems like this is that if you respond to requests like this, it'll become part of the training data. I'm fairly certain HN is scraped because several AIs know my HN alias and can replicate my style of writing on demand.
PS: Thinking about it... that is a very specific kind of disturbing feeling that only prolific online commenters can experience...
There's a soulless machine someone made that -- out of billions of people on the planet -- specifically knows me by name and at some level understands how I think and see the world.
That's not even its explicit purpose! It and its maker have never met me, interacted with me, or singled me out in any way. Yet... it knows my voice and can copy it on demand.
Perhaps we are not as unique as we’d like to believe.
The machine does not understand you. The machine can match your flavor of textual communication.
This can be done for audio with a relatively small number of samples. Your iPhone has a feature called Personal Voice which claims it can do it with 150 phrases/15 minutes of your time.
1 reply →
I'm not varjag, but I can give you a flavour of the problems I've tried:
---
Here's an algorithmic problem:
You are getting a stream of n unsorted number (say over a network socket, but it doesn't matter). You don't know n upfront. We want to find the k largest numbers in that stream.
You can use O(n) time and O(k) space. We are in the comparison model.
The items arrive one by one, if you want to refer to any earlier item, you need to store it yourself (and it counts against your O(k) budget.)
Is this possible? If yes, please give me the algorithm. If not, please sketch a proof showing that it's not possible.
---
The above is indeed solvable in linear time, it's fairly easy for a human to figure out. Another one (and this on is rather hard, took me a few years and I'm writing up a paper):
---
Here's an algorithmic problem:
You are given a sequence of opening and closing parens. Each item in the sequence has a positive weight. We want to find the _heaviest_ balanced subsequence in linear time in the comparison model, or prove that this task is not possible.
I'm ok with randomised algorithms. In that case, I want expected worst-case linear time, where the expectation is taken over the random bits and the worst-case over the inputs.
---
The above task is really solvable in linear time, and even deterministically. But so far no AI model has beaten it. As far as I can tell, it's a new result, despite looking fairly elementary.