As a TCS/scheduling person, this one is definitely of lesser importance than UGC, but it has been an open problem since the book of Garey and Johnson in 1979:
A Polynomial-Time Algorithm for Three-Machine Unit-Job Scheduling [1]
Since some people talk about small numbers that pop up in integer multiplication results, here a completely different number appears:
Theorem 1.1. Let an explicitly listed finite directed acyclic graph specify the precedence constraints on n >= 1 nonpreemptive unit-length jobs on three identical machines. There is a uniform deterministic algorithm that constructs a feasible schedule of minimum makespan. Given also an integer deadline 1 <= T <= n, it decides feasibility exactly and returns a schedule whenever the answer is affirmative. Both tasks can be performed in O((L + 2)^150020) steps on a deterministic multitape Turing machine, where L is the total binary input length.
That is some crazy exponent -- plus an interestingly old computational model to boot; not something that is natural to most of us. I have no capacity to check its correctness today, but I hope it is true purely for the exponent.
The largest I've seen [1] is an exponent of 10^12, which I suppose still counts as polynomial time.
I'm sure all of these super small or large constants will improve over time, but it's still amusing. It is entertaining to see the exponents directly rather than have them hidden as n^c or epsilon or O(1).
To be fair, there is a pretty strong correlation between a problem being in BPP and being efficiently solvable in practice.
There are some exceptions of course (graph isomorphism was solved in practice when the best theoretical algorithms were still exponential) but in general once people find a n^100000 algorithm it soon turns into a n^3 algorithm with reasonable coefficients.
The runtime looks very weird. The +2 can and should be dropped. This reduces my confidence that the bound is tight. Who knows how the model came up with that expression.
Keep in mind that GPU iteration cycles are slowing down significantly for some time now, so "a GPU from 2020" can actually mean NVIDIA RTX 3090 with 24 GB VRAM, one of the best cards you can buy in 2026 for local LLM use; in fact buying one used is probably the best choice right now, because newer generation RTXes are crazy expensive.
My GPUS are Rtx3090s with 24GB ram. You guessed correctly.
I do not enjoy the fact those cards cost more than their msrp 6 years later, but there is a much more important consideration than money (which also makes sense, but about that later). It is the fact soon people will not be able to do my job without AI at all. Even now if I didn't use it I think I'd be out competed very quickly.
And having the ability to run it locally, using a really useful, not toy model is very useful. It makes you independent from Anthropic deciding to ban your account for example.
As for money, it is an open secret the biggest cost of coding agents use is input tokens not generation. I tend to use about 1.3B input tokens per week on claude code with only 7-8M out. Out if this 80% is cached. And the cache is pretty restrictive. You have 5min cache and 1h cache. If you don't keep reading over that time your cache expires on the cloud. Then your 500k context counts as 500k input in its entirety.
And the numbers I mentioned would cost thousands of USD a week at API prices.
But when you control inference, you can keep your cache for as long as you want and save it to disk.
I tend to have up to 10 coding agent sessions open at a time. Some are used once a week. I never use more than 5 at the same moment. Having 15 full contexts cached in RAM basically moves my local cache utilisation to 95%+
Basically I think the AI companies will soon require us to pay the real price for the inference. I prefer to be ready.
I have two. I paid <$1000 for each, before this craziness started. They work, sure, but 48GB of VRAM is just not enough to use a local LLM like a cloud model.
> It doesn't seem humanly possible to produce >2 "high SNR" papers per month.
The situation right now is pretty crazy, for example this established TCS professor [1] has at least 4 arXiv submissions co-authored by him in September [2]. This includes the recent breakthrough on the matroid secretary problem, which has a pretty interesting AI story of its own, if you haven't seen it yet [3].
Of course prolific professors can work around this by working with younger researchers who upload the work, but this just makes the rate limit a solo author bottleneck, which feels a bit weird.
[3]: Concurrent Discovery Disclosure: The proof of the main result in this manuscript was obtained in a conversation with ChatGPT-6 Astra on Tuesday, September 15, 2026 at 1:02 AM PDT. We then prepared this manuscript for public release, with the intent of uploading it on the morning of Thursday, September 17, 2026. In the early morning hours of September 17, while finalizing the submission, we discovered the manuscript of Abdi, Banihashem, Hajiaghayi, and Mittal, uploaded on September 16, 2026, which contains the same result via an essentially identical approach. We are sharing our manuscript nonetheless in case our exposition is of independent utility to the community, and we hope this experience stimulates broader discussion about concurrent discovery in the AI era. (From https://arxiv.org/abs/2609.20797 .)
I don't see what we lose if lead authors are forced to submit work themselves instead of going through the PI's account.
But yes, it'd be nice if arxiv also rate-limited co-author submissions with some higher number to discourage the most flagrant PI co-authorship abuses.
The situation is pretty crazy, but it just means the bar for publishable results will go up. Theoretical computer science is a field built around conferences. The number of papers that can be published in reputable conferences ultimately depends on the size of the community and the willingness and ability of its members to attend those conferences.
> Having a baby does not give up anything. It is a win-win.
I had a son recently -- everything indeed went fine, but my wife and I did read up on both the risks and the permanent changes to women's bodies that having a child brings. Among other things, a C-section is not recommended an unlimited number of times, and it is classified as a surgical procedure for a reason.
You can pay somebody to get a biological child that you cannot have, but at the same time you are paying them to carry some risk for you within their bodies and possibly undergo surgery for you. I am not anti-surrogacy myself, but it just is not that simple as a win-win.
My point is not about risk, my point is about giving up something which you cannot get back. Most surrogacy pregnancies don’t need C-sections and are normal uncomplicated births. The surrogate receives money + other benefits and can continue to live a normal healthy life with no change to her wellbeing after she gives birth.
If you are talking about risk, many transactions in life carry some risk. Your Uber Eats driver risks his life getting in the car or motorbike to bring you your Chipotle burrito. An oil rig worker daily risks heavy machinery injury in exchange for money. We accept that consenting adults are capable of accepting some risk.
Additionally: agencies do everything they can to mitigate medical risks as well. Intended parents are required to purchase good medical insurance for the surrogate if they don’t have any.
That's a bit too simplistic -- if there is a small group that really pushes things forward in a big way, then maybe not, but if this result builds upon decades of prior work, then Cook and Levin might be equally or even slightly more famous than the solver group after the dust settles.
But it is a moot point anyway. Cook and Levin are very well known already in TCS, and credit is not directly enumerable like money, so "more than a lot of credit" doesn't make too much sense.
For this problem in particular, asking the right kind of question was really important for the field and led to a lot of discoveries even before it will be answered.
> If the answer is "no one really", entropy will overwhelm your codebase sooner or later. Otherwise, you need to read the code
I think about this on the regular -- I know the answer is currently "you own the code, so you have to understand it", but to unlock the true productivity multiplier, in the future, the answer has to be "no one really".
I think about it using the concepts from my job (academia) -- to actually have PhD student-level intelligence means that you have to trust that it does a good enough job that you can focus on other stuff. Professors often bring the correct ideas or intuitions, but they have to trust the PhD student to write the code and/or fill in the gaps in the proofs -- they can advise them on the high-level issues during a consultation, but that's about it.
I am pretty bad at working in the current LLM workflow -- it is tough for me to focus on reading a TCS paper for review, keeping all the details and invariants in my head, but every 5-10 minutes go to my PC, completely switch contexts/projects, read the code and think about the LLM's comments, suggest the next step, and then go back to reading.
As a TCS assistant professor from Eastern Europe, I always am a little jealous of the biggest names in math having such an easy access to the expensive, long thinking models.
Paying for Pro from any of my current academic budgets is completely ouf of the field of reality here -- all budgets tend to have restricted uses and software payments fit into very few categories. Effectively, I'd have to ask for a brand new grant and hope the grant rules allow for large software payments and I won't encounter an anti-AI reviewer; such a thing would take one year at least.
As a nail to the coffin, I was "denied" all Claude Opus recently as part of Microsoft's clampdown on individual (and academic) use of Copilot.
(Chagpt 5.5 Plus does not seem sufficient for any deeper investigations into new research topics, I've tried.)
While this sounds generous (and in some ways it is), it does not address the general point that GP is making. That is, the systematic disadvantage which large parts of humanity have w.r.t. to access to the tools. You could say they can't drive a Lambhorgini either, but that also doesn't solve the problem.
An aside: It was a very nice gesture and completely unexpected by me, so even if it doesn't work out, it made my day. I personally believe that kind gestures have a lot of power.
Back on topic: There is a real danger of the gap between rich and poor universities significantly widening in all fields if the rich can afford Pro level models, or even hardware that can run their own comparable models, and this being fiscally inaccessible to the rest.
One can sweep this under the rug by blaming the educational funding but this just shoots down all discussion. Even if GDP of a country goes up by a lot -- such as Poland -- it takes time before any budget benefit trickles to the education budget, and with some governments it might never do.
I believe Microsoft et al do have the most power here to boost affordable access to AI for researchers on a large scale; the fact that they cut some too expensive models (Opus, 5.5) from their academic benefits package is a grim omen. I do realize they would like universities to pay them also, and ultimately the universities should do that -- but then we are back at the institutional level of the problem.
Its a problem of the individual institutions and countries. The budget required for AI tools currently is negligible compared to other university expenses. We don't need to call everything a systemic disadvantage when the disadvantaged (at the institution level) have agency here.
Can you tell me what is the budget necessary to supply AI tools capable of substantial research assistance to all academic staff at a university?
You seem to have a good estimate in your head; I definitely do not.
From personal experience, ChatGPT 5.5 (the Plus tier) is excellent for programming tasks and also for various teaching related tasks but I have not observed the research benefits that Tim Gowers has when I asked it questions in my area of expertise. So the costs are definitely higher than a few dozen $ a month per PhD/professor.
You might be right that universities should immediately spring into action and demand funding for research level AI resources and hardware. One thing you might be mistaken in is that public universities are unfortunately very inflexible institutions; one reason for this is that they have a large internal leadership structure AND they are funded by the state, so even if the entire university agrees on something, the funding is at the whim of the ministry of education and thus the current political leadership.
> Can you tell me what is the budget necessary to supply AI tools capable of substantial research assistance to all academic staff at a university?
I think the GP meant that *if the tools provide substantial benefit* to staff, their costs can be compared to salaries and other large expenses of the university. The $100/month subscription costs less than your office space.
Which is good, since public money is tax money, so it better be spent wisely and not just thrown at the latest hype without thinking properly about it. It's a feature that public spending moves slowly, we should all be thankful for it.
> The budget required for AI tools currently is negligible compared to other university expenses.
Is it? Do you have any idea what the salary of a mid-tier university researcher in an Eastern European country is? Or in Africa or south-east Asia? With sota LLM pricing you easily get into the same order of magnitude, so essentially labour cost would double for researchers at such universies. Not "negligible" at all.
I feel like this is one of the most advantaged times in history in terms of regular citizens having access to cutting edge tools.
Looking online it seems like the low end estimate might be $30k a year for such math researchers? And ChatGPT pro or whatever you want will run $100 a month, and should be coverable by grants. I’m quite sure matlab alone cost more in the past
> While this sounds generous (and in some ways it is), it does not address the general point that GP is making. That is, the systematic disadvantage which large parts of humanity have w.r.t. to access to the tools. You could say they can't drive a Lambhorgini either, but that also doesn't solve the problem.
This was also the case historically, when being at certain universities, with better professors, better scope of works available at the library, etc, would necessarily provide systematic advantage.
This is the reality of progress. It is always unevely distrubuted.
I do think the open source side of model development is a substantial counter to the pessimism here.
I mean, I don't think OpenAI should be wading into the policies and practices of foreign institutions and governments. Look at all the blowback we see from the collision of Anthropic or OpenAI and the US government.
At present, the tools are available for whomever wants to buy them. Not OpenAI's fault that parent comment's government and/or institutions policies haven't been updated to allow for their purchase and use.
I'd argue that the OpenAI dude/dudettes level of generosity is appropriate given the circumstances.
You know what, I'm ashamed that I didn't think of this. I'll sponsor three months. Email in my hn profile. I don't understand the math in the article, but I'd love to help you make progress in it.
I will leave the contact up for a bit longer if people want to get in touch and share their experience with the research gap of the models -- or anything, really -- but I do not think there is any need of further support. Like I said elsewhere, the offer of support made my day and the gesture is enough.
At my university, everyone had to pay their AI subscriptions out of their own pocket, until a communal AI service was introduced recently. It took 2 years to set up and only serves gpt-oss-120b, so everyone is still using other services. But at least some admin can scatter the word "AI" all over the university's website now and has an excuse to reject any requests for AI subscriptions because "we already have AI".
It’s a classic example of the best positioned people being in the best position to keep reaping all the rewards.
There’s the example of a poor person and a rich person buying boots. The poor person’s boots wear out and have to be replaced while the rich persons boots last for many years due to higher quality craftsmanship. Over years, the poor person’s boots wear will pay may for boots.
I know the example, but as a counter-argument: often more expensive boots are not more durable. It’s about spending time to learn to spot the quality.
Of course if you are really poor, then you have to take expensive shortcuts, but for most people that shouldn’t be the case. Learning to do more with less money isn’t as bad as many people think. It’s also good for the brain to be a bit more creative.
> Learning to do more with less money isn’t as bad as many people think.
We are wading into philosophy here, but I believe this analogy doesn't track in this case -- my suspicion from this blog post and others is that already today, the Pro level thinking models are a positive multiplier to your research output similar to how the models one level lower are a multiplier to one's programming output.
Maybe one can someday use the cheaper models similar to how you can use cheaper models than Opus/5.5 and still be nearly as productive as a programmer -- but I am trying and failing doing exactly that for research questions.
here I think it's less about "poverty" (non-US acedemic budgets are still high, though not in the same sphere), but it's about having red tape when it comes to software. My experience doing a PhD in Japan was: Everything you can touch was basically a free for all - including $500 keyboards and $10k Mac Pros, especially if you are a valued researcher. But software, oh man, how can we prove receipt of goods to accounting...
OpenRouter lets you pay by the token only (no subscription), has all the frontier models (including Opus 4.7, GPT-5.5) and most of the others, and if you use it sparingly it usually turns out to be quite cheap.
API pricing for Claude is about an order of magnitude more expensive than subscriptions (numbers: https://she-llac.com/claude-limits). But it may be worth it with DeepSeek V4 Pro, which is currently on discount.
Depends very much on usage! If you connect it to tools like Cursor, etc. then yes a subscription is probably cheaper -- although, you'd have to subscribe to each provider if you want to use them all.
But if you ask questions occasionally, (and don't resend, for example, your whole codebase with each request), then the API feels really cheap, even for the frontier models.
My problem with pay-by-the-token is that it discourages me using the thing ("oh the prompt will cost me $0.1"), so I pay a subscription which I'm pretty sure costs me about two-three times what I'd pay just for the api costs, but encourages me to use it more ("oh I have a subscription already, better make use of it").
I believe ChatGPT 5.5 Pro access is available for $100/month, is that an unrealistic level of expense for someone in your position and geography? Even if the university won't pay for it, it seems you'd like to use this tool for your own goals.
I'm not trying to shame here, just curious whether this is completely unattainable for most researchers in your area.
I fully understand your rant! I pay ~20€/month for the Pro account, as my university has a deal with Microsoft and only seems to recognize Copilot, so it’s very hard to use one own’s funding for paying something else.
Average European salary is around $4000/month, in eastern Europe is half of that. Median is probably lower than that. Makes me want to quit visiting places like reddit where everybody claims to be making 100k+/year
All salary discussions need a cost of living context. Yes in Europe you earn a bit less but the public services are much better than in the US and one emergency (r.g. healthcare) won't ruin you as it's mostly a public system.
I'll take a Euro salary and qualify life over a FIRE-typs salary and daily fear of falling into the abyss any day.
Given the topic and the fact llm providers charge global rates, the absolute take-home money is much more relevant. Even if you live like a king on $1000/mo, 5.5 pro is still $200.
Their loss if they don't move to regional pricing. AI will continue to remain an upper-management luxury then, and won't reach the mass adoption required to justify their outsized valuations.
Regional pricing makes sense for products that don’t have ongoing costs or where most of the input cost can be offset by local labor. You’re not buying server racks nor electricity at 1/3 of the price to serve poorer markets
That’s what most people spend on their phone and Internet connections per month in the US. That’s what the average American family spends on just five days of food.
People spend much more than that on just commuting to work if you can spend $200 a month to supercharge what you do at work and 1000x your productivity it’s a no-brainer.
From what money? Just pause the health insurance for a while? Stop paying the rent? No diapers for the kid?
Your entire story only makes sense if you have many hundreds of dollars/euros of entirely disposable income every month left, after all unavoidable expenses have been paid for. I understand that this holds for you and everyone you know but I’d like you to appreciate that for very many people it doesn’t.
37% of Americans would be unable to cover a 400 usd unexpected expense* without using one or more credit cards. 13% would flat out be unable to cover it. [1]
Are you honestly saying most families would be able to justify 200 usd a month for ChatGPT?
There is a significant gap between what academics are paid across European countries, and since most top universities here are public institutions, you are right -- Eastern European government employees tend to be on the poorer side.
There are several other philosophical arguments against what you propose but I do not wish to go down that route.
Bruh, $200/m for most people in the US is also a hard "no!". That's a lot of money. Plus Anthropic isn't doing good deals with orgs that spend less than 250k a month. It's ridiculous.
> Is the lock structuring here really deadlock safe? The model will tell you with complete confidence its code is perfect
Fully agree, in fact, this has literally happened to me a week ago -- ChatGPT was confidently incorrect about its simple lock structure for my multithreaded C++ program, and wrote paragraphs upon paragraphs about how it works, until I pressed it twice about a (real) possibility of some operations deadlocking, and then it folded.
> Every time a major announcement comes out saying so-and-so model is now a triple Ph.D programming triathlon winner, I try using it. Every time it’s the same - super fast code generation, until suddenly staggering hallucinations.
As an university assistant professor trying to keep up with AI while doing research/teaching as before, this also happens to me and I am dismayed by that. I am certain there are models out there that can solve IMO and generate research-grade papers, but the ones I can get easy access to as a customer routinely mess up stuff, including:
* Adding extra simplifications to a given combinatorial optimization problem, so that its dynamic programming approach works.
* Claiming some inequality is true but upon reflection it derived A >= B from A <= C and C <= B.
(This is all ChatGPT 5, thinking mode.)
You could fairly counterclaim that I need to get more funding (tough) or invest much more of my time and energy to get access to models closer to what Terrence Tao and other top people trying to apply AI in CS theory are currently using. But at least the models cheap enough for me to get access as a private person are not on par with what the same companies claim to achieve.
Hello, TCS assistant professor here: he is legitimately respected among his peers.
Of course, because I am a selfish person, I'd say I appreciate most his work on convex body chasing (see "Competitively chasing convex bodies" on the Wikipedia link), because it follows up on some of my work.
Objectively, you should check his conference submission record, it will be a huge number of A*/A CORE rank conferences, which means the best possible in TCS. Or the prizes section on Wikipedia.
I don't deny that his output is highly valued among AI researchers.
Provocative as my question may be, the point I wanted to make is that his most highly cited paper that I already mentioned is suspiciously very in line with the OpenAI narrative. I doubt if any of his GPT research is really independent. With great salary comes great responsibility.
> Realistically there's no reason government can't use open source software and open formats especially.
> Last time I had to fill out a government form in Canada (...)
Without any evidence, let me argue why maybe it shouldn't. In the past, a common opinion that I have heard is that open source is more secure because all the code is out in the open.
The recent xzutils backdoor attempt [1] kind of led me to believe it's not really true, it's only true if many good-actor eyeballs, which are willing to donate their time for public benefit, are on the code.
Almost all of the government's code that I interact with are web apps that are potential targets of foreign adversaries -- tax filing web apps, prescription + vaccination scheduling web apps, family benefit applications, and more. (This is not in Czechia, but close.)
Now, would I want to read that web app code? Not at all, I couldn't care less about it. However, foreign adversaries would love to immediately start analyzing it. Extracting the entire country's health data or tax data would be a goldmine.
And even though there probably are several people actively paid to maintain security of these systems, I feel that the foreign adversarial agents would be much more motivated (and better paid) than government employees/software developers.
You could make a opt-out for national-security purposes for the code, but I feel almost all the code a government works on would have such an impact when compromised.
(Disclaimer: I am a huge supporter of open source in general, contributed to the Linux ecosystem in the past and in my current job as an academic, almost everything I do is available out in the open in some way or another.)
Microsoft has literally been hacked multiple times by Russia in the last few years. Our government lost hundreds of thousands of CRA (tax agency) credentials to hackers and had to lock millions of accounts. Other agencies have also been breached.
Meanwhile the XZ backdoor was found in Sid, Arch and pre-releases of Fedora and openSuse. It never actually made it into any numbered release of Fedora, openSuse, Ubuntu, Debian, Red Hat or Suse distro. It's actually a pretty big win and the system worked as intended.
Open source and Linux are doing just fine security-wise.
Also, none of this has anything to do with using offline tools like a word processor to make documents.
>Meanwhile the XZ backdoor was found in Sid, Arch and pre-releases of Fedora and openSuse. It never actually made it into any numbered release of Fedora, openSuse, Ubuntu, Debian, Red Hat or Suse distro. It's actually a pretty big win and the system worked as intended.
I would maybe not go quite that far. That it got caught was mostly a confluence of lucky breaks and accidents. The second version of the exploit would likely have not been detected if not for the fact that the first version of the exploit had a couple of programming mistakes that attracted some attention to itself.
The entire thesis behind the open source security model is to have lots of eyes on the code/program, since more eyes = more likelihood of catching it. Even if you say it's accidental, let's say the odds of catching it are 0.00001. Repeat that enough times and you get 1.
It was caught before any distro released with it. The system worked.
If one of the Debian or Fedora developers had immediately caught on to what they were looking at when their attention was drawn to it by the failures, I would say the system worked. It's certainly true that open source saved the day here, but that's maybe different from saying "the system" worked. It easily could have gone unnoticed, or been noticed a few weeks later.
The xz backdoor was caught before anyone used it. This is typical of open source backdoors, but atypical of proprietary ones. History is full of proprietary software with backdoors which were discovered after years or decades of being actively used. Lotus notes, RSA corporation, Cisco routers, Juniper switches, Huawei everything.
We have more or less immutable history of every change leading to every release of open source software. Any backdoors you previously created under an identity could burn that identity forever. That history is not available for proprietary software. If someone adds a backdoor in proprietary software for two years and then removes it in later versions, it's totally likely it'll never be noticed.
Thinking that open source software is at greater risk of being backdoored is akin to thinking most trees in the world grow along the road, just because you drive everywhere and have never been inside a forest.
Every country already has a special government agency that deals with keeping stuff protected. In fact you tend to think the people who know most about this are in government, don't you?
And it's not like there haven't been vulnerabilities found in proprietary software, despite them paying people to keep things safe.
Crowdstrike is a recent example that comes to mind. I don't see how paying for CrowdStrike made it more secure or reliable.
I would also argue that you could take all the $$ paying for proprietary software and contribute it to people who are making the open source software, making the reliance on "free" eyeballs less of an issue.
A Polynomial-Time Algorithm for Three-Machine Unit-Job Scheduling [1]
Since some people talk about small numbers that pop up in integer multiplication results, here a completely different number appears:
Theorem 1.1. Let an explicitly listed finite directed acyclic graph specify the precedence constraints on n >= 1 nonpreemptive unit-length jobs on three identical machines. There is a uniform deterministic algorithm that constructs a feasible schedule of minimum makespan. Given also an integer deadline 1 <= T <= n, it decides feasibility exactly and returns a schedule whenever the answer is affirmative. Both tasks can be performed in O((L + 2)^150020) steps on a deterministic multitape Turing machine, where L is the total binary input length.
That is some crazy exponent -- plus an interestingly old computational model to boot; not something that is natural to most of us. I have no capacity to check its correctness today, but I hope it is true purely for the exponent.
[1]: https://github.com/openai/math/blob/main/preprints/A-polynom...
reply