Tom Gur (@TomGur) header
Tom Gur (@TomGur) profile picture

Tom Gur

@TomGur

Professor @Cambridge_Uni. My research is in Theoretical Computer Science and Quantum Computing.

 Cambridge, UK
cst.cam.ac.uk/people/tg508
Joined August 2019
  • Tweets743
  • Following339
  • Followers5.9K
94Media
Photo by Tom Gur (@TomGur)Photo by Tom Gur (@TomGur)Photo by Tom Gur (@TomGur)Photo by Tom Gur (@TomGur)Photo by Tom Gur (@TomGur)Photo by Tom Gur (@TomGur)Photo by Tom Gur (@TomGur)Photo by Tom Gur (@TomGur)Photo by Tom Gur (@TomGur)Photo by Tom Gur (@TomGur)
Tom Gur retweeted
Boaz Barak (@boazbaraktcs) profile picture
Boaz Barak
@boazbaraktcs4h
Talk by Dana Moshkovitz on the proof of the Unique Games Conjecture. scottaaronson.blog/?p=10232
Talk by Dana Moshkovitz: The Unique Games Conjecture – Proved (!!?)

Talk by Dana Moshkovitz: The Unique Games Conjecture – Proved (!!?)

In my “Mathocalypse” post, I mentioned that my wife Dana—who’s been working on Subhash Khot’s Unique Games Conjecture since ~2009, for the entire time I’ve known…

scottaaronson.blog
9
1
61
9,326
More maths, less ego. A lovely take by Erik Demaine. youtu.be/Gdc1yll04qI?is=js5V…
More Math, Less Ego (talk about AI and Math)

More Math, Less Ego (talk about AI and Math)

A talk by Erik Demaine presented live to an AI + Math group.Links...

youtube.com
2
10
1
57
5,487
Tom Gur retweeted
Lance Fortnow (@fortnow) profile picture
Lance Fortnow@fortnowOct 29
Impagliazzo, Paturi and Williams set up a site to discuss the ETH Refutation Discussion Blog: ethdiscussion.blog/2026/10/2… Paper Depository: drive.google.com/drive/folde…
ETH Refutation: Examination and Discussion

ETH Refutation: Examination and Discussion

Dear colleagues,OpenAI has informed us that it has obtained a claimed refutation of the Exponential Time Hypothesis and plans to release the supporting documents to the community. Our names may app…

ethdiscussion.blog
3
31
76
6,484
What a treat!
Ryan O'Donnell (@BooleanAnalysis) profile pictureRyan O'Donnell@BooleanAnalysisOct 29
I lectured on the "ETH false" (#3SAT in subexponential time) result in my grad complexity class at CMU today. Didn't have time in 80 mins to do the full proof, but I hope I got across the main plan, and some of the basic TCS ingredients going into it. youtu.be/_HlQGMcQWhA
ETH False

ETH False

Lecture 18 in Ryan O'Donnell's Graduate Computational Complexity co...

youtube.com
28
2,853
Hi all, I am hiring PhD student. Please have a look at the call and please also help me spread the word. candidate.hr-manager.net/App…
PhD positions in Algebraic Hardness and Applications (AHA) at IT University of Copenhagen

PhD positions in Algebraic Hardness and Applications (AHA) at IT University of Copenhagen

The IT University of Copenhagen invites highly motivated individuals to apply for a PhD position starting in September 1, 2027, or soon thereafter. We invite ap

candidate.hr-manager.net
3
49
169
25,796
Making some progress on simplifying the '#ETH false' proof, I think. In latest version, the key algebraic construction comes from elementary analysis of Boolean functions. cs.cmu.edu/~odonnell/some_et…
9
36
5
233
53,308
Interestingly, Claude has also refuted the exponential-time hypothesis. hexagonmath.org/2610.00577v1
A $2^{o(n)}$ Time Algorithm for 3-SAT

A $2^{o(n)}$ Time Algorithm for 3-SAT

We refute the Exponential Time Hypothesis (ETH) by presenting a deterministic algorithm for 3-SAT on n variables that runs in $2^{o(n)}$ time. Our algorithm in fact solves the harder problem #3-SAT,...

hexagonmath.org
17
27
1
275
15,866
We’re hiring in Cambridge CS! Assistant/Associate Professor position in AI and machine learning, including learning theory and related areas of theoretical computer science. Apply here: cam.ac.uk/jobs/university-as…
Image from Tom Gur (@TomGur)
2
50
3,080
An internal model at OpenAI has produced a claimed refutation of ETH! Russell Impagliazzo, Mohan Paturi, and I have been asked to help organize an open and independent examination of this claim. 1/4
299
753
541
7,395
3,726,212
This is a super exciting time for science, and EPFL is growing. Multiple faculty openings in areas I’m especially excited about: • Computer science — broad search • Security & privacy • Mathematics of learning • Ethics of technology — including alignment & algorithmic bias Please consider applying, and help us spread the word! 👇
1
13
88
7,226
Ben Green has written a very nice version of the proof that no Siegel zeros exist - only 5 pages, and self-contained elementary arguments: hexagonmath.org/pdf/2610.003…
4
20
1
158
14,084
I really like Raghu Meka's post about the barriers of perception. It is certainly thought-provoking and well worth a read. terrytao.wordpress.com/2026/…
The barriers of perception

The barriers of perception

[This is a guest post by Raghu Meka. This blog post was initially written in a different file format and converted using AI. — T.] “This problem has been tried by several famous mathema…

terrytao.wordpress.com
7
65
5,105
In our new work arxiv.org/abs/2610.04996 , we investigate the power of reverse-time evolution queries in quantum algorithms, with a focus on Hamiltonian property testing.
The power of time reversal in Hamiltonian property testing

The power of time reversal in Hamiltonian property testing

Quantum algorithms enable Heisenberg-limited scaling across many tasks in sensing and learning, achieving precision $\varepsilon$ using $O(1/\varepsilon)$ total evolution time. However, in...

arxiv.org
1
3
17
1,119
The what now?! arxiv.org/abs/2610.06783v1
Truly Subquadratic 3SUM and Truly Subcubic APSP via Triangles in...

Truly Subquadratic 3SUM and Truly Subcubic APSP via Triangles in...

We give the first polynomial improvements over the textbook algorithms for $3$SUM and All-Pairs Shortest Paths (APSP): we show how to deterministically solve $3$SUM on $n$ integers of polynomial...

arxiv.org
57
195
142
1,850
1,013,440
Postdoc position at Cambridge. Topics include classical and quantum complexity theory, sublinear algorithms, cryptography, learning theory, and connections to harmonic analysis & additive combinatorics. Apply by 1 December '26. cstheory-jobs.org/2026/09/29…
Postdoc at Cambridge (apply by December 1, 2026)

Postdoc at Cambridge (apply by December 1, 2026)

Postdoc position available in Tom Gur’s group at Cambridge on topics including (but not limited to) Classical and/or Quantum aspects of: Complexity, Sublinear Algorithms, Coding Theory, Cryptograph…

cstheory-jobs.org
8
49
3,290
For talk submissions, remember to register by 28 Sep (23:59 AoE)! Registration only requires a title, short abstract, authors, and topic selections, but do note the recommended cutoff for the arXiv submission and talk submission - read the details at qipconference.org/2027/call/
Image from QIP 2027 (@QIPConference)
1
6
3
16
6,595
Join us Tuesday, 9/29 for the first Richard M. Karp Distinguished Lecture of this academic year, featuring @BooleanAnalysis. simons.berkeley.edu/events/m…
Image from Simons Institute for the Theory of Computing (@SimonsInstitute)
7
27
2,408
Martin Hairer, one of the other members of AGMAI (the advisory group on mathematics and AI), has written a post on the Proofs and Prompts blog that will I hope clarify what our purpose is. The rest of the blog is highly recommended too. proofsandprompts.com/2026/09…
Why I agreed to join AGMAI

Why I agreed to join AGMAI

“There has been a lot of speculation regarding the ‘Advisory Group on Mathematics and Artifical Intelligence’ agmai.org since it was announced on Monday. In this short blog post, I would like to ex…

proofsandprompts.com
19
82
5
354
56,064
Tom Gur retweeted
Yupan Liu (@yupan_liu) profile picture
Yupan Liu@yupan_liuSep 18
For anyone interested in the proof of QMA=QMA_1, we now have a simpler and more natural construction in the second version (scirate.com/arxiv/2609.15926…). I'll sketch the proof in a few posts. 1/7
1
4
32
2,638
STOC 2027 Call for Papers is out: acm-stoc.org/stoc2027/stoc20… Note quite a lot of changes from previous STOC CfPs.
4
19
4
118
36,314
Load more