Elfarouk Harb 🌱

Quant Researcher. Previously Software Engineer @Google, Quant Trader @citsecurities, and PhD in Theoretical Computer Science @UofIllinois

[Elfarouk Harb 🌱 @ElfaroukHarb]

For the record, I (strongly) believe P \neq NP. I think this is mostly a communication problem: the informal framings we've used to convey what P vs NP means are failing badly right now. That's not evidence either way. It says more about how flawed our intuition, and the way we communicate it, is, even with researchers outside the area.

[Elfarouk Harb 🌱 @ElfaroukHarb]

Related: when I TA'd algorithms in Fall 2022, I polled the class on P vs NP, framing it with Avi Wigderson’s question of whether intuition can be “mechanized”, or whether solving a problem feels "polynomially close" in effort to verifying a solution. Exactly one student believed P=NP.

I asked again when I taught in early and late 2025. Nearly a third of the class raised their hands.

I suspect many students growing up with AI will eventually wonder why we were ever stuck on math problems that AI now solves in seconds.

[Aran Nayebi @aran_nayebi]

With sub-n log n FFT (130), subcubic APSP & subquadratic 3SUM, today has shaken my belief that humans were ever good at algorithms.

At this rate, I've updated to maybe P = NP after all, via some clever SAT algorithm GPT-8 discovers running in n^c time for c ~ 10^6. 🙈

[Elfarouk Harb 🌱 @ElfaroukHarb]

Not CS473. It was CS374 in the complexity part and I later asked a similar question in my own course CS498AE (to a smaller group of students). In CS374 in ~2025, around a third (not half) raised their hand.

I wasn't asking about P vs NP formally. I was asking about their intuition: does finding a solution to a (say) HW/Exam problem feel "polynomially close" in effort to verifying or understanding a solution, that we give them? Can search be mechanized? For most this was their first real encounter with complexity classes, which is why I like it. It shows how many people "feel" P = NP before they've been trained out of it (i.e. us sharing why most researchers believe P \neq NP).

[Elfarouk Harb 🌱 @ElfaroukHarb]

@alex8chan I can’t believe an Econ prof is writing this unironically.

[Elfarouk Harb 🌱 @ElfaroukHarb]

@joeintheory I'm curious if over the last year and a half, you believed it to be true or false? Seems prior to this people were divided?

[Elfarouk Harb 🌱 @ElfaroukHarb]

Holy fuck. Just based on a cursory look, major ones seem:

Unique Games Conjecture proved

L = RL = BPL

Matrix multiplication with ω ≤ 9/4, insane jump from the current best ~2.37

Ω(n³) permanent vs. determinant lower bound

FFT and integer multiplication faster than nlogn

Almost-linear time maximum matching and edit distance approximation

[OpenAI @OpenAI]

We’re releasing a broad range of new mathematical results produced by an internal frontier model.

We’ve been consulting with the independent Advisory Group on Mathematics and Artificial Intelligence at the Institute for Advanced Study, and we have drawn on their advice and public recommendations to inform how we release these results.

https://t.co/7N6TPlft1P

[𝖬𝖺𝗁𝖽𝗂 𝖢𝗁. (bluesky:@mahdi.ch) @mahdi_tcs_]

The what now?!
https://t.co/xHsLmQJkff

[Elfarouk Harb 🌱 @ElfaroukHarb]

@meta_x_ai @mandylu Yeah, an inverse IQ test. -1sd for passing, -2sd if you're proud of it

[Elfarouk Harb 🌱 @ElfaroukHarb]

Maybe I'm missing something, but what's the point of autoformalization if AI gets astronomically better than us at proving and checking proofs?

Any examples were autoformalization caught an error that a few GPT-6 Astra agents red-teaming the manuscript wouldn't have caught?

[Elfarouk Harb 🌱 @ElfaroukHarb]

@vussyviz @alz_zyd_ What *isn’t* wrong with Rudin?

[divesh aggarwal @diveshaggarwal]

"The competition was fierce and we were only able to accept 287 out of 1181 submissions. This means that many strong submissions that met the high bar for SODA were finally not selected."

This attitude will need to be fixed. Anything that meets the bar has to be accepted.

[Elfarouk Harb 🌱 @ElfaroukHarb]

@B1ar2n3a Happening to literally everyone.

[Elfarouk Harb 🌱 @ElfaroukHarb]

I hope the optimists are right, but I've seen too much ego and dishonesty in this field to expect it.

Mark my words: the next STOC PC will be picking from a pile of AI results, and anyone not using AI will be at a massive disadvantage. And the STOC after that will be mostly useless, because by then the jig will be up.

[Elfarouk Harb 🌱 @ElfaroukHarb]

I hope the optimists are right, but I've seen too much ego and dishonesty in this field to expect it.

Mark my words: the next STOC PC will be picking from a pile of AI results, and anyone not using AI will be at a massive disadvantage. And the STOC after that will be mostly useless, because by then the jig will be up.

[Elfarouk Harb 🌱 @ElfaroukHarb]

@Pooyahat @TaliaRinger I did read it. You said you hope it's a transitional phase, which I took to mean you'd like the field to shift toward truth over ego. My question is what makes you optimistic, when TCS has been obsessed with hierarchy/publishing first long before AI came along??

[Elfarouk Harb 🌱 @ElfaroukHarb]

@_TarunKathuria The rumor is that the full UGC has been resolved, not just the 4 to 1 games conjecture.

[Elfarouk Harb 🌱 @ElfaroukHarb]

@ramdas1998 @_TarunKathuria Full UGC is resolved