Sign in

Tom Gur

@tomgur.bsky.social
1.1K followers 175 following 83 posts

Professor of Computer Science at Cambridge.

PostsRepliesMedia
Reposted by Tom Gur
Clément Canonne @ccanonne.github.io · 22h
If you're in #TheoreticalCS and on the postdoc job market, now or soon: this opportunity to work with Tom Gur (@tomgur.bsky.social) on "cutting-edge research on the interplay of theoretical computer science, mathematics, and quantum mechanics" sounds amazing: www.cam.ac.uk/jobs/researc...
cam.ac.uk
Research Assistant/Associate in Theoretical Computer Science (Fixed Term)
Fixed-term: The funds for this post are available for 1 year.
1195
Tom Gur @tomgur.bsky.social · 15/09/2026
Goldreich’s short take on AI proofs is thought-provoking (and the Borges reference is quite on point). www.wisdom.weizmann.ac.il/~oded/on-pro...
wisdom.weizmann.ac.il
On AI replacing Mathematicians
0215
Reposted by Tom Gur
Ryan O'Donnell @booleananalysis.bsky.social · 10/09/2026
Am teaching grad complexity theory at CMU; about 1/3 of the lectures will be new (vs. last time), 'modern' results. Videos are going onto www.youtube.com/@ComplexityT... which will later also feature student videos. We did Williams (/Cook-Mertz/Shalunov) TIME(t) in SPACE(~√t) today.
youtube.com
Complexity Theory At Carnegie Mellon
05717
Reposted by Tom Gur
CompSciOxford @compscioxford.bsky.social · 01/09/2026
Recruiting: We're hiring two Associate Professorships or Professorships of Computer Science (with Tutorial Fellowships) to start on 1 September 2027 as part of the University of Oxford’s @ox.ac.uk expansion in Computer Science. Details & applications: my.corehr.com/pls/uoxrecru...
A salmon pink graphic with the Department of Computer Science logo at the top left and text reading 'We’re hiring: Two Associate Professorships or Professorships of Computer Science (with Tutorial Fellowships). Full time and permanent upon completion of a successful review. 30S: Combined salary £57,986 - £77,366 + substantial additional benefits. Application Deadline: 12:00 16 December 2026. @compscioxford #CompSciOxford'. There are also lines and dots pointing to the text that look like a computer board.
063
Reposted by Tom Gur
Clément Canonne @ccanonne.github.io · 01/08/2026
TCS+, the longest-running theoretical #computerscience seminar, will soon resume for the Fall. Let us know what you'd like to hear about (results, speakers, topics), and any suggestions you may have! sites.google.com/view/tcsplus... #TCSSky @tcsplus.bsky.social
sites.google.com
TCS+ - Suggest a talk
Suggest a talk
13011
Reposted by Tom Gur
International Association for Quantum Information @iaqi.bsky.social · 30/07/2026
Let's have a community discussion about the impact of LLMs on quantum information research, and how to react to it as a research community! 👩‍🔬⚛️🤖 🏛️ Head over to the IAQI forum 👇 discuss.iaqi.org/t/quantum-in... 🦋 Please share widely!
discuss.iaqi.org
Quantum Information Processing research in the age of AI
Dear colleagues, Over the past weeks there have been more and more results in which AI models played a crucial role, not only in mathematics and theoretical computer science, but right at the heart o...
2157
Reposted by Tom Gur
Clément Canonne @ccanonne.github.io · 12/06/2026
The website and registration link for WoLA 2026, the Workshop on Local Algorithms, is up! Registration is free, and the workshop will take place on August 16-18 at Boston University. Details and registration: www.local-algorithms.com/WOLA2026/
local-algorithms.com
Workshop on Local Algorithms - WOLA 2026
055
Reposted by Tom Gur
Paul Goldberg @paulwgoldberg.bsky.social · 11/06/2026
5-year postdoctoral research fellowship in theoretical Computer Science (also 4 other research fields), a nice opportunity! Needs PhD to be awarded between 1/Aug/24 and 1/Oct/27. Please share with whoever may be suitable! www.asc.ox.ac.uk/post-doctora...
asc.ox.ac.uk
Post-Doctoral Research Fellowships | All Souls College
088
Tom Gur @tomgur.bsky.social · 29/05/2026
Oded Goldreich posted a very insightful digest of the interactive proofs of proximity paper by Rothblum, Vadhan, and Wigderson. This is one of my favourite TCS papers, and Oded's new exposition makes it even easier to appreciate its beauty and elegance. eccc.weizmann.ac.il/report/2026/...
eccc.weizmann.ac.il
ECCC - TR26-088
080
Tom Gur @tomgur.bsky.social · 27/05/2026
Splendid news for TCS@Cambridge: Anuj Dawar @anujdawar.bsky.social has been elected Fellow of the Royal Society. A wonderful recognition for a towering figure in logic and computational complexity. Many congratulations, Anuj! www.cst.cam.ac.uk/news/royal-s...
cst.cam.ac.uk
Royal Society Fellowships honour two Computer Scientists | Department of Computer Science and Technology
The Royal Society has today honoured our colleagues Professors Anuj Dawar and Srinivasan Keshav by electing them as Fellows. Many congratulations to them both!
170
Reposted by Tom Gur
Timothy Gowers @wtgowers.bsky.social · 20/05/2026
OpenAI's claim that this is a central conjecture in discrete geometry is not an exaggeration. This will I think be looked back on as the first time that AI solved a major mathematics problem (defined as a problem that all experts in some subfield had thought about). openai.com/index/model-...
openai.com
An OpenAI model has disproved a central conjecture in discrete geometry
An OpenAI model solved the 80-year-old unit distance problem, disproving a major conjecture in discrete geometry and marking a milestone in AI-driven mathematics.
17652191
Tom Gur @tomgur.bsky.social · 10/05/2026
Superb exposition. Highly recommended!
082
Reposted by Tom Gur
Clément Canonne @ccanonne.github.io · 08/05/2026
Congratulations to Scott Aaronson, awarded the inaugural Luca Trevisan Award for Expository Work in Theoretical Computer Science "for his sustained and high-impact inspirational efforts to explain and promote our field to broad audiences"! Read the commendation: sigact.org/prizes/trevi... #TCSSky
sigact.org
ACM SIGACT - Trevisan Award
1372
Reposted by Tom Gur
Clément Canonne @ccanonne.github.io · 13/04/2026
How did I miss this?! A recent (2025) survey by Rocco Servedio on PAC learning and its variants, and recent results in these learning models: arxiv.org/abs/2511.08791 (Anything by Rocco is worth reading!)
arxiv.org
The Probably Approximately Correct Learning Model in Computational Learning Theory
This survey paper gives an overview of various known results on learning classes of Boolean functions in Valiant's Probably Approximately Correct (PAC) learning model and its commonly studied variants...
1368
Tom Gur @tomgur.bsky.social · 07/04/2026
Excited about this new paper: it subsumes the quadratic Goldreich-Levin [BC26] and algorithmic PFR [ACDG26] papers, and makes explicit a connection between quadratic Fourier analysis and symplectic geometry, as speculated by Green and Tao. arxiv.org/abs/2604.04547
0211
Tom Gur @tomgur.bsky.social · 04/04/2026
Submissions are now open for RANDOM 2026: easychair.org/conferences/... Call for papers: randomconference.com/random-2026-... RANDOM 2026 will be held in Boston, MA, on August 19–21, 2026, together with APPROX 2026. We look forward to your submissions!
easychair.org
Log in to EasyChair for RANDOM 2026
042
Reposted by Tom Gur
TCS+ @tcsplus.bsky.social · 02/04/2026
📢 Our next TCS+ talk of the season will be Wednesday, April 8 (10am PT, 1pm ET, 19:00 CEST): Rahul Ilango, from MIT, will tell us about Gödel in Cryptography! RSVP to receive the link (available one day prior to the talk): docs.google.com/forms/d/e/1F...
docs.google.com
TCS+ RSVP: Rahul Ilango (2026/04/08)
Gödel in Cryptography: Zero-Knowledge Proofs With No Interaction, No Setup, and Perfect Soundness
074
Tom Gur @tomgur.bsky.social · 02/04/2026
Postdoc position in Cambridge with the amazing Anuj Dawar!
030
Reposted by Tom Gur
Timothy Gowers @wtgowers.bsky.social · 20/03/2026
I've created a couple of mathematical games, both based on word problems in groups or semigroups. One of them could lead to a Polymath project if enough people are interested in it, as it is connected with an open problem. More details in the linked blog post.
gowers.wordpress.com
Group and semigroup puzzles and a possible Polymath project
An Artin-Tits group is a group with a finite set of generators $latex a_1,\dots a_k$ in which every relation is of the form $latex (ab)^r=(ba)^r$ or $latex (ab)^ra=(ba)^rb$ for some positive intege…
14312
Tom Gur @tomgur.bsky.social · 18/03/2026
Happy days! A perfect excuse to share my favourite quantum cryptography origin story, as recounted in Brassard’s paper: arxiv.org/pdf/quant-ph...
0202
Tom Gur @tomgur.bsky.social · 13/03/2026
A quantum computer here at Cambridge!
080
Tom Gur @tomgur.bsky.social · 28/02/2026
I’ve been enjoying Dor Minzer’s new survey “The Lens of Abelian Embeddings”. It gives a clear, additive-combinatorics-flavoured perspective on inverse theorems for k-wise correlations, with applications in discrete maths/TCS and plenty of open problems. arxiv.org/abs/2602.22183
arxiv.org
The Lens of Abelian Embeddings
We discuss a recent line of research investigating inverse theorems with respect to general k-wise correlations, and explain how such correlations arise in different contexts in mathematics. We outlin...
041
Tom Gur @tomgur.bsky.social · 25/02/2026
Postdoc position in Cambridge with Julia Wolf: Julia is a phenomenal researcher and a wonderful collaborator. She is advertising a 2-year postdoc in additive combinatorics and model theory. Closing date: 16 March. Details: jobs.ac.uk/job/DQP803/postdoctoral-research-associate-fixed-term
jobs.ac.uk
Postdoctoral Research Associate (Fixed Term) at University of Cambridge
Explore an exciting academic career as a Postdoctoral Research Associate (Fixed Term). Don't miss out on other academic jobs. Click to apply and explore more opportunities.
033
Tom Gur @tomgur.bsky.social · 22/02/2026
The 2nd Quantum Cambridge–Oxford–Warwick (QCOW) Workshop will take place at Warwick on April 23–24. Theme: Quantum Learning Theory. The programme will feature tutorials and accessible in-depth talks on recent advances by leading experts. Speakers/updates: qcow.cs.ox.ac.uk/
qcow.cs.ox.ac.uk
QCOW
Department of Computer Science - People: Sergii Strelchuk - QCOW
0164
Reposted by Tom Gur
Clément Canonne @ccanonne.github.io · 13/02/2026
The list of accepted papers at #STOC2026 is out: acm-stoc.org/stoc2026/acc... Congratulations to all authors!
acm-stoc.org
STOC 2026 - 58th ACM Symposium on Theory of Computing
0279
Reposted by Tom Gur
Clément Canonne @ccanonne.github.io · 08/02/2026
Theoretical CS community! I have a small favor to ask. If you ever used, read, watched some of the (excellent IMO) exposition content by Ryan O'Donnell, would you mind filling this very short survey, and maybe say how useful to you it was? 📝 forms.gle/xrvc2mLRbMqK... Please spread this! #TCSSky
2176
Reposted by Tom Gur
National Academy of Sciences @nasonline.org · 22/01/2026
Congrats to Irit Dveer Dinur of the Institute for Advanced Study & Weizmann Insitute, #NASmember Subhash Khot of New York University, Guy Kindler of @hebrewuniversity.bsky.social, Dor Minzer of @mit.edu, and Muli Safra of Tel Aviv University, winners of the 2026 Michael and Sheila Held Prize! (1/2)
163
Tom Gur @tomgur.bsky.social · 20/01/2026
ICALP 2026 CFP is out. This year it’ll be at Royal Holloway (London area), July 7–10, 2026. Abstract registration: Feb 3 Paper deadline: Feb 6 Details: icalppodcspaa2026.cs.rhul.ac.uk/icalp/
icalppodcspaa2026.cs.rhul.ac.uk
ICALP
The 53rd EATCS International Colloquium on Automata, Languages, and Programming (ICALP) will take place between 7–10 July, 2026.
044
Tom Gur @tomgur.bsky.social · 16/12/2025
New paper with the brilliant Dor Minzer, Guy Weissenberg, and Kai Zhe Zheng: we show a separation between RLDCs and LDCs via HDX-based PCPs. This one is special to me; it answers a question Oded Goldreich posed to me in my 1st PhD year, and it’s been on my mind ever since. arxiv.org/pdf/2512.129...
1181
Tom Gur @tomgur.bsky.social · 01/12/2025
Reminder: Two weeks left to apply for the Assistant/Associate Professor positions in Theoretical Computer Science at Cambridge. Application deadline: 15 December 2025. Details and application portal: cst.cam.ac.uk/assistantass...
cst.cam.ac.uk
065
Reposted by Tom Gur
Ryan O'Donnell @booleananalysis.bsky.social · 25/11/2025
Wow! Yuansi Chen resolves 1 of the 2 remaining $1000 Talagrand problems (michel.talagrand.net/prizes/prize... ): If you take any f : {-1,+1}ⁿ → ℝ⁺ and apply the noise operator T_{.99}, the resulting function g = T_{.99} f satisfies a better-than-Markov inequality. That is, Pr[g > t E[g]] < o(1/t).
michel.talagrand.net
2444
Tom Gur @tomgur.bsky.social · 24/11/2025
A new paper with the brilliant Guy Goldberg and Sidhant Saraogi (now on the job market!). We prove nearly tight lower bounds for relaxed LDCs via a new combinatorial notion of relaxed sunflowers with pseudorandom structure, obtained from new spread lemmas. eccc.weizmann.ac.il/report/2025/...
0100
Tom Gur @tomgur.bsky.social · 20/11/2025
Join us for the first Quantum Cambridge–Oxford–Warwick Colloquium (Quantum COW, if you insist...), 11–12 December 2025 at the University of Oxford. This meeting focuses on Quantum Low-Depth Complexity, with talks, tutorials, and open discussions. Details: qcow.cs.ox.ac.uk
qcow.cs.ox.ac.uk
QCOW
Department of Computer Science - People: Sergii Strelchuk - QCOW
1181
Reposted by Tom Gur
Clément Canonne @ccanonne.github.io · 14/11/2025
Reminder: the School of Computer Science at #USyd is hiring across the board, equiv. tenure-track positions! Join us at @sydney.edu.au! Deadline ⏰ December 1 🇦🇺
1118
Reposted by Tom Gur
Felix Leditzky 🏳️‍🌈🏳️‍⚧️ @felixled.bsky.social · 11/11/2025
The list of accepted papers for #QIP2026 is now online at qip2026.lu.lv/programme/ac...
qip2026.lu.lv
Accepted papers
1189
Reposted by Tom Gur
𝖬𝖺𝗁𝖽𝗂 𝖢𝗁𝖾𝗋𝖺𝗀𝗁𝖼𝗁𝗂 @mahdi.ch · 10/11/2025
The inaugural Computational Complexity Conference Test of Time Award seeks nominations (deadline Monday, March 2, 2026). Help us select an awesome paper for this award! computationalcomplexity.org/tot/tot26.html
computationalcomplexity.org
Computational Complexity Conference
043
Tom Gur @tomgur.bsky.social · 20/10/2025
I’m looking for postdocs and PhD students to join my group at Cambridge! Topics include: Classical & Quantum Complexity, Sublinear Algorithms, Coding Theory, Cryptography, Learning Theory, and their interplay with Fourier Analysis & Additive Combinatorics. To apply or inquire, email me your CV.
03311
Tom Gur @tomgur.bsky.social · 07/10/2025
Cambridge is recruiting Assistant/Associate Professors in Theoretical Computer Science. #TCS #AcademicJobs Application deadline: 15 December 2025. Contact me for informal inquiries. See more details and apply here: www.cst.cam.ac.uk/assistantass...
1209
Tom Gur @tomgur.bsky.social · 03/09/2025
New arXiv preprint: we show algorithmic versions of the polynomial Freiman–Ruzsa (PFR) theorem of Gowers, Green, Manners, and Tao. Interestingly, our proof draws on quantum information and stabilizer learning algorithms, which we dequantize into classical algorithms. arxiv.org/pdf/2509.02338
2273
Reposted by Tom Gur
Clément Canonne @ccanonne.github.io · 24/08/2025
The submission server for #ITCS2026 (which will take place at Bocconi University, Milan, in January 2026) is open! Submission deadline: Sep 4 (abstracts), Sep 6 (papers) itcs-conf.org
itcs-conf.org
ITCS 2025 Call for Papers
ITCS 2025 CFP
1124
Tom Gur @tomgur.bsky.social · 19/08/2025
Paul is a phenomenal researcher, and Oxford is lots of fun. Highly recommended!
140
Reposted by Tom Gur
Robin Kothari @robinkothari.bsky.social · 06/08/2025
The QIP 2026 call for papers is out! QIP 2026 will be held in Riga, Latvia from January 24–30, 2026. See you there! qip2026.lu.lv
02815
Reposted by Tom Gur
kenbrownquantum.bsky.social @kenbrownquantum.bsky.social · 28/07/2025
#Quantum #QIP2025 The team @qip2025.bsky.social has uploaded the QIPv2025 talks www.youtube.com/@QIP2025 Enjoy rewatching your favorites!
youtube.com
QIP2025
23511
Reposted by Tom Gur
let-all.com @let-all.com · 21/07/2025
New post on the Learning Theory Alliance blog, by Arsen Vasilyan. This covers the recently introduced testable learning paradigm of Rubinfeld and Vasilyan, from their STOC 2023 paper. A great chance to catch up on all the exciting work that's happened in this area! www.let-all.com/blog/2025/07...
0175
Tom Gur @tomgur.bsky.social · 19/07/2025
Hirahara, Illango, and Loff posted on the arXiv a lovely result, showing that determining the communication complexity of a function f is NP-hard. A fundamental question first asked by Yao in '79. The proof is very clean and elegant. A fun read for the weekend! arxiv.org/pdf/2507.104...
arxiv.org
0303
Reposted by Tom Gur
John Watrous @johnwatrous.bsky.social · 16/07/2025
After 3 1/2 years of work my course on quantum computing is finally finished — the "Director's Cut" of Understanding Quantum Information and Computation is now available. arxiv.org/abs/2507.11536
arxiv.org
Understanding Quantum Information and Computation
This is a course on the theory of quantum computing. It consists of 16 lessons, each with a video and written component, covering the basics of quantum information, quantum algorithms (including query...
515334
Tom Gur @tomgur.bsky.social · 27/06/2025
Recently came across this fantastic talk by @ccanonne.github.io on deterministic amplification via expander graphs—elegant ideas, crystal-clear exposition. A real gem! www.youtube.com/watch?v=3AAU...
youtube.com
Clément Canonne: What is deterministic amplification?
YouTube video by Sydney Mathematical Research Institute - SMRI
1142
Reposted by Tom Gur
Ryan O'Donnell @booleananalysis.bsky.social · 09/06/2025
Spread the word: there is a new prize in Theoretical Computer Science in honor of Luca Trevisan-- cs.unibocconi.eu/call-nominat... (Intent-to-nominate letters due by July 31.)
cs.unibocconi.eu
14718
Reposted by Tom Gur
Lance Fortnow @lance.fortnow.com · 07/06/2025
The 2025 Gödel Prize is given to Eshan Chattopadhyay and David Zuckerman, “Explicit two-source extractors and resilient functions”. Paper: doi.org/10.4007/anna... Favorite Theorems Blog Post: blog.computationalco...
0348
Reposted by Tom Gur
Clément Canonne @ccanonne.github.io · 04/06/2025
#STOC2025 "will feature an online poster session, designed to engage both in-person attendees and members of the broader community who are unable to attend the conference physically." (Initiative led by @iwmertz.bsky.social, Ninad Rajgopal, and @h4n1in.bsky.social) acm-stoc.org/stoc2025/cal...
acm-stoc.org
STOC 2025 Online Poster Session
0113