Tom Gur
@tomgur.bsky.social
Professor of Computer Science at Cambridge.
Pinned
Tom Gur
@tomgur.bsky.social
· Oct 7
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...
Application deadline: 15 December 2025. Contact me for informal inquiries. See more details and apply here:
www.cst.cam.ac.uk/assistantass...
Reposted by Tom Gur
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).
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).
November 25, 2025 at 4:16 PM
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).
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).
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/...
eccc.weizmann.ac.il/report/2025/...
November 24, 2025 at 7:00 PM
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/...
eccc.weizmann.ac.il/report/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
This meeting focuses on Quantum Low-Depth Complexity, with talks, tutorials, and open discussions.
Details: qcow.cs.ox.ac.uk
QCOW
Department of Computer Science - People: Sergii Strelchuk - QCOW
qcow.cs.ox.ac.uk
November 20, 2025 at 7:46 PM
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
This meeting focuses on Quantum Low-Depth Complexity, with talks, tutorials, and open discussions.
Details: qcow.cs.ox.ac.uk
Reposted by Tom Gur
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 🇦🇺
Join us at @sydney.edu.au! Deadline ⏰ December 1 🇦🇺
The School of #ComputerScience at #USyd is hiring! Multiple continuing (≡ tenure-track) positions in all areas, with particular focus on the ones listed below.
Women and candidates from underrepresented groups are encouraged to apply.
⏰ Apply by Dec 1: usyd.wd105.myworkdayjobs.com/en-GB/USYD_E...
Women and candidates from underrepresented groups are encouraged to apply.
⏰ Apply by Dec 1: usyd.wd105.myworkdayjobs.com/en-GB/USYD_E...
November 14, 2025 at 10:41 PM
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 🇦🇺
Join us at @sydney.edu.au! Deadline ⏰ December 1 🇦🇺
Reposted by Tom Gur
The list of accepted papers for #QIP2026 is now online at qip2026.lu.lv/programme/ac...
Accepted papers
qip2026.lu.lv
November 11, 2025 at 1:28 PM
The list of accepted papers for #QIP2026 is now online at qip2026.lu.lv/programme/ac...
Reposted by Tom Gur
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/tot/tot26.html
Computational Complexity Conference
computationalcomplexity.org
November 10, 2025 at 5:36 PM
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/tot/tot26.html
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.
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.
October 20, 2025 at 8:15 PM
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.
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.
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...
Application deadline: 15 December 2025. Contact me for informal inquiries. See more details and apply here:
www.cst.cam.ac.uk/assistantass...
October 7, 2025 at 11:38 AM
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...
Application deadline: 15 December 2025. Contact me for informal inquiries. See more details and apply here:
www.cst.cam.ac.uk/assistantass...
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
arxiv.org/pdf/2509.02338
September 3, 2025 at 8:48 AM
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
arxiv.org/pdf/2509.02338
Reposted by Tom Gur
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
Submission deadline: Sep 4 (abstracts), Sep 6 (papers)
itcs-conf.org
ITCS 2025 Call for Papers
ITCS 2025 CFP
itcs-conf.org
August 24, 2025 at 10:33 PM
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
Submission deadline: Sep 4 (abstracts), Sep 6 (papers)
itcs-conf.org
Paul is a phenomenal researcher, and Oxford is lots of fun. Highly recommended!
Job advert, #hiring :
1-year postdoc research position, CS Dept, Oxford University
Keywords: game theory, optimisation, machine learning
Project details and further links:
www.cs.ox.ac.uk/people/paul....
1-year postdoc research position, CS Dept, Oxford University
Keywords: game theory, optimisation, machine learning
Project details and further links:
www.cs.ox.ac.uk/people/paul....
Research project OGTML, Paul Goldberg
Paul Goldberg's home page.
www.cs.ox.ac.uk
August 19, 2025 at 3:56 PM
Paul is a phenomenal researcher, and Oxford is lots of fun. Highly recommended!
Reposted by Tom Gur
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
qip2026.lu.lv
August 6, 2025 at 12:44 AM
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
qip2026.lu.lv
Reposted by Tom Gur
#Quantum #QIP2025
The team @qip2025.bsky.social has uploaded the QIPv2025 talks
www.youtube.com/@QIP2025
Enjoy rewatching your favorites!
The team @qip2025.bsky.social has uploaded the QIPv2025 talks
www.youtube.com/@QIP2025
Enjoy rewatching your favorites!
QIP2025
www.youtube.com
July 27, 2025 at 11:02 PM
#Quantum #QIP2025
The team @qip2025.bsky.social has uploaded the QIPv2025 talks
www.youtube.com/@QIP2025
Enjoy rewatching your favorites!
The team @qip2025.bsky.social has uploaded the QIPv2025 talks
www.youtube.com/@QIP2025
Enjoy rewatching your favorites!
Reposted by Tom Gur
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...
www.let-all.com/blog/2025/07...
July 21, 2025 at 4:02 PM
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...
www.let-all.com/blog/2025/07...
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/pdf/2507.104...
arxiv.org
July 19, 2025 at 11:28 AM
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/pdf/2507.104...
Reposted by Tom Gur
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/abs/2507.11536
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...
arxiv.org
July 16, 2025 at 11:06 AM
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/abs/2507.11536
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...
www.youtube.com/watch?v=3AAU...
Clément Canonne: What is deterministic amplification?
YouTube video by Sydney Mathematical Research Institute - SMRI
www.youtube.com
June 27, 2025 at 10:45 AM
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...
www.youtube.com/watch?v=3AAU...
Reposted by Tom Gur
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/call-nominat...
(Intent-to-nominate letters due by July 31.)
cs.unibocconi.eu
June 9, 2025 at 12:46 PM
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/call-nominat...
(Intent-to-nominate letters due by July 31.)
Reposted by Tom Gur
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...
Paper: doi.org/10.4007/anna...
Favorite Theorems Blog Post: blog.computationalco...
June 7, 2025 at 10:59 PM
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...
Paper: doi.org/10.4007/anna...
Favorite Theorems Blog Post: blog.computationalco...
Reposted by Tom Gur
#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...
(Initiative led by @iwmertz.bsky.social, Ninad Rajgopal, and @h4n1in.bsky.social)
acm-stoc.org/stoc2025/cal...
June 4, 2025 at 12:26 AM
#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...
(Initiative led by @iwmertz.bsky.social, Ninad Rajgopal, and @h4n1in.bsky.social)
acm-stoc.org/stoc2025/cal...
Reposted by Tom Gur
📢 Our sixth and last TCS+ talk of the season will be Wednesday, June 4 (10amPT, 1pm ET, 19:00 CEST): Irit Dinur, from the IAS, will tell us about "Agreement Tests: Local Consistency, Global Structure"!
RSVP to receive the link (available one day prior to the talk):
forms.gle/GJt74TequURy... #TCSSky
RSVP to receive the link (available one day prior to the talk):
forms.gle/GJt74TequURy... #TCSSky
TCS+ RSVP: Irit Dinur (2025/06/04)
Title: Agreement Tests: Local Consistency, Global Structure
forms.gle
May 28, 2025 at 11:28 PM
📢 Our sixth and last TCS+ talk of the season will be Wednesday, June 4 (10amPT, 1pm ET, 19:00 CEST): Irit Dinur, from the IAS, will tell us about "Agreement Tests: Local Consistency, Global Structure"!
RSVP to receive the link (available one day prior to the talk):
forms.gle/GJt74TequURy... #TCSSky
RSVP to receive the link (available one day prior to the talk):
forms.gle/GJt74TequURy... #TCSSky
Reposted by Tom Gur
Teaser: our last TCS+ of the season will be next week, with Irit Dinur (IAS) on "Agreement Tests: Local Consistency, Global Structure." What a way to conclude the semester!
[More details coming soon to a BlueSky near you]
[More details coming soon to a BlueSky near you]
May 27, 2025 at 9:43 PM
Teaser: our last TCS+ of the season will be next week, with Irit Dinur (IAS) on "Agreement Tests: Local Consistency, Global Structure." What a way to conclude the semester!
[More details coming soon to a BlueSky near you]
[More details coming soon to a BlueSky near you]
Reposted by Tom Gur
We have an open rolling advert for QEC researchers at Riverlane. And now also have a single post to fill for an (error-corrected) algorithms researcher
apply.workable.com/riverlane/j/...
apply.workable.com/riverlane/j/...
Quantum Algorithms Researcher - Riverlane
Cambridge, UK | Full-time or Part-time | Permanent | HybridSalary: £55,000 to £80,000 DOEThe salary range for this role is broad as we are able to consider varying levels of experience. Any offe...
apply.workable.com
May 24, 2025 at 12:06 AM
We have an open rolling advert for QEC researchers at Riverlane. And now also have a single post to fill for an (error-corrected) algorithms researcher
apply.workable.com/riverlane/j/...
apply.workable.com/riverlane/j/...
This is such a good one-sentence (albeit a long one…) explanation of quantum computing!
This!
I like to say,
"Let p|A denote distribution p conditioned on event A.
Imagine a world where the laws of probability are the same, except (p|A)|B need not equal (p|B)|A.
Except you don't have to imagine, because it's literally our world!
Now explore probabilistic algorithms in this world."
I like to say,
"Let p|A denote distribution p conditioned on event A.
Imagine a world where the laws of probability are the same, except (p|A)|B need not equal (p|B)|A.
Except you don't have to imagine, because it's literally our world!
Now explore probabilistic algorithms in this world."
May 17, 2025 at 11:56 AM
This is such a good one-sentence (albeit a long one…) explanation of quantum computing!
Reposted by Tom Gur
The recordings of two courses from the school Complexity as a Kaleydoscope are out: www.carmin.tv/en/c/1642
Antonina's lectures are great, and I was surprised how much I learned from Richard's lectures on Quantum Complexity theory (since I work on the field). I strongly recommend them
Antonina's lectures are great, and I was surprised how much I learned from Richard's lectures on Quantum Complexity theory (since I work on the field). I strongly recommend them
Complexity as a kaleidoscope / Le kaleidoscope de la complexité | Tag | Carmin.tv
www.carmin.tv
April 15, 2025 at 11:56 AM
The recordings of two courses from the school Complexity as a Kaleydoscope are out: www.carmin.tv/en/c/1642
Antonina's lectures are great, and I was surprised how much I learned from Richard's lectures on Quantum Complexity theory (since I work on the field). I strongly recommend them
Antonina's lectures are great, and I was surprised how much I learned from Richard's lectures on Quantum Complexity theory (since I work on the field). I strongly recommend them