Tom Gur

After 78 years, an exponential improvement for Ramsey numbers were found by Jie Ma, Wujie Shen, and Shengjie Xie. gilkalai.wordpress.com/2025/07/23/ama…

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! arxiv.org/pdf/2507.10426…

A Postdoctoral Position in Complexity Theory is available at Warwick. More information is available here: dcs.warwick.ac.uk/~igorcarb/posi… Please spread the word about it!

📅 You're invited! Save the date! Prof. Alex Lubotzky's Rothschild public lecture on "High Dimennsional Expanders in Pure Mathematics and Computer Science" on 9 July 2025 at 4 PM. 📍 INI, Seminar Room 1 #NewtonOGG2025 #IsaacNewtonInstitute #publiclecture #UniversityOfCambridge

Recently came across this fantastic talk by @ccanonne_ on deterministic amplification via expander graphs—elegant ideas, crystal-clear exposition. A real gem! youtube.com/watch?v=3AAUqW…

CCC’25 will take place August 5-8 at the Fields Institute in Toronto! Students/postdocs (from any institution) are eligible to apply for a travel allowance. For full consideration, please apply by June 20; awards to be announced on June 25. computationalcomplexity.org/travelAllowanc…

Natalie @nat_parham has some bold new ways of proving quantum circuit lower bounds, with fascinating connections to condensed matter physics and the natural proofs barrier from complexity theory. There are some really interesting questions to explore here.

Sylvester, Gallai and Friends: Discrete Geometry Meets Computational Complexity — a fantastic new talk by Avi Wigderson about Sylvester–Gallai theorems and their connections to Computer Science. youtu.be/VJ-d1jPc1YM?si…

Prakash Murali and I are seeking to jointly recruit a postdoctoral researcher (Dowling fellow) at Cambridge to conduct research in quantum algorithms, complexity, error correction, and architecture. Further details: jobs.cam.ac.uk/job/50485/ Deadline: 7 April 2025

On Wednesday (19 March) at 5pm UK time, I'll be giving an online talk at @TCS_plus about my recent work, "A Zero Knowledge PCP Theorem", joint with @_nickspoon and @JackOConnor111. See more details here: tcsplus.org

What are some recommended resources to get into algebraic complexity theory? Any recommendations for video lectures, lecture notes, surveys, or books would be much appreciated.

I've enjoyed this excellent exposition of the recent progress in the combinatorial list-size bounds of Folded Reed Solomon codes and multiplicity codes by Garg, @prahladh , Kumar, Saptharishi, and Shankar. A fascinating read. arxiv.org/pdf/2502.14358…

An exciting result has just appeared on arXiv, concerning the following simple-seeming problem: if A is a set of n positive integers, then how large a sum-free subset B must it contain? That means that if x, y and z belong to B, then x + y should not equal z. 🧵

Gil Cohen gave a fabulous mini-course on analytic approaches to spectral graph theory and Ramanujan graphs. Highly recommended! The lectures are available in the link below. youtube.com/playlist?list=…

Irit Dinur (@IritDinur), Venkat Guruswami (@venkatguruswami ) and I are organizing a 2-week program on HDX and Codes at ICTS-TIFR, Bengaluru, India (@ictstifr). See attached poster for more details and how to apply for the program. icts.res.in/program/HDXand…

What a fantastic initiative! Beyond funding/visa issues, this will also benefit people with family constraints, those concerned about reducing their carbon footprint, and many others. I'm looking forward to the online Junior-Senior Lunch.

Khanh and Eamonn are organising UK Crypto Day on 20 February at King's College London. Registration is free (and open) but required: uk-crypto-day.github.io/2025/02/20/uk-… Help us spread the word and see you there.