You want to know how long it takes to solve an optimization problem, in this case over convex, lipschitz functions. (The restriction to a spherical domain is not really a restriction, you can just change variables for any bounded domain.) Anyway, showing upper bounds on time complexity is "easy" because it's just the runtime of your algorithm. Showing (nontrivial) lower bounds is usually much harder because it requires constraining all algorithms.
This proof apparently shows that the lower bound time complexity is equal to the time complexity of an existing 30-year old algorithm: it requires Omega(d^2) function evaluations to solve over this class of functions.
My gut says likely implies that d is the minimal number of evaluations if you have a gradient oracle because you can approximate a gradient with d function evaluations, but I'm not sure how hard it is to make that rigorous.
I wonder how this compares to what we see happening with "juniors" in software development? In math research, do you also get the training for the profession from working on the low hanging fruits for a while, to then move to the medium-hanging, and later go on to work on previously unsolved stuff?
This isn't something which is unique to software development though. We're currently building enterprise AI apps that we can deploy into the AI agents working for anyone of our employees. The key thing we're currently seeing is that the people in a team who are the ones that everyone turn to for advice, are the only people who aren't in "danger". Even people who are great at their jobs are being outperformed by AI in many cases.
I think it'll be a massive challenge for our society in the coming years. Maybe we're even going to get to the point where the AI will also be capable of replacing a lot of the "domain experts". Right now that seems far out, but then, if you had asked me about AI four months ago I would've told you it was all hype.
Back in the before I had put such discipline into my prompting and supporting context.
Now I’m like, “look here and here and here are some tools, and /skill /skill okay go.”
Or “restate this request in your own words and enrich it as appropriate handling any gaps. Okay go”
A few months back this would be something every developer kind of did on their own. Maybe they shared skills, we certainly encouraged it and tried to do all the change management things, but nobody really had the same versions of the skills. Which was horrible in the deployment pipelines, something like the compliance documentation often had to go back and forth several times before it could be approved. Now it's just there, for everyone.
In a year or two, I expect a lot of these things to have become even more standardized. So that we don't even really have to build our own apps, but can simply use the ones in the catalog with minimal configuration (and that config will likely only be necessary because I'm from a tiny country that nobody will maintain standards for).
In math, a proof is a proof. We don't know if we can get there and so getting there is the hard part.
In software, we always know that we can solve the problem. So HOW to solve the problem is the hard part. Because the type of solution involves maintainability, which involves planning, LLMs suck at it. This leads to "LLM slop code" whereby the LLM creates ad-hoc convoluted logic with redundancies and no reuse of existing standard library batteries.
Unless you're a Grothendieck who gets mad at Deligne for not solving the Weil's conjecture "THE RIGHT WAY", software is fundamentally different than math in this respect.
So I'll say it again, AI will win a fields medal for before managing a McDonald's simply because there are enough big problems within arms reach than their current capacity to plan over time
Overall, this is an impressive proof of capability. But I wouldn't take that proof as anything more than what it is.
Of course money in this situation is a bit of a funny measurement, right, because if I was able to take the rest of the week off as soon as I had solved the one-week problem, then I would have no problem at all throwing even $100 worth of tokens at it, so I could enjoy a nice 4-day "mini-vacation".
How cheap "cheap" is, is indeed "in the eye of the beholder".
They will, however, get there as well either directly or as interfaces to models that do, and your core point stands.
This is basically what LLMs do on really hard tasks. Prompt it a million times on a really hard problem and it might output the correct answer once.
AI hasn’t even taken the class of jobs associated with customer service lmao
This is what the whole https://people.csail.mit.edu/brooks/papers/elephants.pdf is about.
You mistyped it.
Best I've come up with is we'll need to be adopted by technofeudlaist overlords to be our patrons like in the roman days
Continually progressing AI (combined with our current socioeconomic systems) throws a lot of uncertainty into our mid to long term future, but I don't think this is going to be what happens.
There are billions more of "us" than of "them", people don't respond well en masse to a drastic worsening of their societal status and "they" are lagging very far behind on building their robot armies.
If we poorly navigate this transition the outcome should be worrying them more than it worries us.
Reminds me of Wigner's Unreasonable effectiveness of mathematics in natural sciences [0].
[0]: https://en.wikipedia.org/wiki/The_Unreasonable_Effectiveness...
I don’t know if LLMs will kill the working-mathematicians but at least seem like that it doesn’t seem absurd to imagine LLMs will be good at math…
It's not that AI brings equality, but rather that the output varies depending on how much background knowledge you have. You could call it a stratification of input
I'm starting to feel like there's no place left for programmers like me who focus on quickly churning out MVPs.
The obvious baby’s first process is “plan -> execute” but as we learn about the strengths and weaknesses of LLMs you have to start unpacking that process into planning, prototyping, testing, validation, reviews, and tons of research. If you treat it like an extension of your brain that can automate some thought processes, it becomes a lot more powerful.
There are two ways to solve a problem. Either solve the problem, or deem it irrelevant.
The implication here is that, you, the human operator, clearly are just confused. The LLM knows best. You're just a stupid human. The LLM knows objective truth, you do not. You have concerns, questions, the LLM didn't understand your question "properly"? Do not worry, the LLM objectively knows the optimal course of action. It thought through the implications of what you said, took into account all possible data, and came to the objectively correct design for your software, your society, your life.
In some sense, this problem would have been a societal problem within the next several decades anyways, but it's been hyper-accelerated by AI.
And programming, as the programmer who created Eliza once said, is the act of becoming a legislator of your own universe. So even if there are black boxes, if you want to build a program that fits your own worldview, studying is essential.
Debuggers, testing techniques, testing layers
Essentially things that could be used to ground your ai back to reality and work good for humans too
Of course there is. The same way this was only possible as a result from the professor who prompted it with his specialized 10 page prompt and most importantly his deep knowledge of the problem space, the muscle memory and intuition you've built over the years is what will allow you to get more out of any AI than some guy who says "make a door dash clone" as the entire prompt
I've been realizing that there are more books tied to my background knowledge than I expected, but I'm not sure what will happen as AI advances further.
These days, I'm living for the fun of building my own personal wiki on my homepage
- Hasn't been peer reviewed yet, so take with a grain of salt. This applies to all claimed proofs, not just AI-generated ones. Even humans hallucinate proofs too!
- The prompt is on page 27 here[1]. It is ten pages of advanced mathematics priming the model in the right direction, apparently informed by a year of prior research. That doesn't invalidate the result if it is genuine, but it is worth noting that this wasn't a matter of "ChatGPT, solve this unsolved problem. Make no mistakes." and required substantial domain expertise and human research beforehand.
Sure. That is not even remotely the point I was getting at. Already we see the thread filling up with comments about how human skills are irrelevant, using a mathematics PhD applying his expert skills in a way that the people who are saying that could never have done to justify their inane conclusion.
The most interesting thing in research is finding new questions, that we understand and that we know why they are important. And that's something that humans need to do (by definition)
>So I wouldn't really say that this result is using or creating some fundamentally new techniques in convex geometry or optimization theory. What this means from my perspective is that if a result is attainable with existing techniques, modern AI methods will be able to solve those problems. I don't think researchers in math/TCS will be made obsolete, but I think it will instead no longer make sense to work on any low-hanging, or even medium-hanging (you know what I mean) fruit. We'll be needed for problems where actual novel approaches are needed.
While they’ll never have the same subjective experience as humans, what stops an LLM from applying similar lines of thought* in a manner that results in a novel conjecture?
They are prediction machines, and so are we in a way. We can give them nearly limitless resources to scale their predictive capabilities. We have billions of years of training baked in. They distill directly from our knowledge and can walk down paths that no human has before.
It’s silly to say they’ll never do anything novel.
At their current capabilities, it sounds like they are already capable of being a specific type is research assistant. What will that look like in 10-20 years?
You state this as a fact - are you aware the question is unresolved?
How's It Hanging, Brother?
Sure, it's not a breakthrough that opens new roads in mathematics- is this where the goalpost has moved now?
Oh wait, sorry, I do know why you're getting downvoted. Fear.