Lightnews — Scholar-powered news

Tom Gur @tomgur.bsky.social · 1d

A personal note: I might be biased, but Cambridge is a truly magical place. I couldn’t imagine a better place to live and work.

1 1 3

Tom Gur @tomgur.bsky.social · 1d

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...

1 9 19

Tom Gur @tomgur.bsky.social · Sep 8

The de-quantization behind this new work strongly relies on the earlier breakthrough of Jop Briët and Davi Castro-Silva (arxiv.org/abs/2505.13134) — their contributions were essential to making this possible.

A near-optimal Quadratic Goldreich-Levin algorithm

In this paper, we give a quadratic Goldreich-Levin algorithm that is close to optimal in the following ways. Given a bounded function $f$ on the Boolean hypercube $\mathbb{F}_2^n$ and any $\varepsilon...

arxiv.org

4

Tom Gur @tomgur.bsky.social · Sep 3

This was a really fun collaboration with the amazing Srinivasan Arunachalam, Davi Castro-Silva, and Arkopal Dutt. We suspect there is a fundamental connection between additive combinatorics and quantum computing, and it would be interesting to deepen our understanding of it.

4

Tom Gur @tomgur.bsky.social · Sep 3

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

2 3 26

Reposted by Tom Gur

Clément Canonne @ccanonne.github.io · Aug 24

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 2025 Call for Papers

ITCS 2025 CFP

itcs-conf.org

1 4 12

Tom Gur @tomgur.bsky.social · Aug 19

Paul is a phenomenal researcher, and Oxford is lots of fun. Highly recommended!

Paul Goldberg @paulwgoldberg.bsky.social · Aug 19

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....

Research project OGTML, Paul Goldberg

Paul Goldberg's home page.

www.cs.ox.ac.uk

1 4

Reposted by Tom Gur

Robin Kothari @robinkothari.bsky.social · Aug 6

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

15 27

Reposted by Tom Gur

kenbrownquantum.bsky.social @kenbrownquantum.bsky.social · Jul 27

#Quantum #QIP2025
The team @qip2025.bsky.social has uploaded the QIPv2025 talks

www.youtube.com/@QIP2025

Enjoy rewatching your favorites!

QIP2025

www.youtube.com

2 12 37

Reposted by Tom Gur

let-all.com @let-all.com · Jul 21

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...

5 17

Tom Gur @tomgur.bsky.social · Jul 19

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

3 30

Tom Gur @tomgur.bsky.social · Jul 18

This is great! (Reminds me a bit of Irit Dinur’s “Proofs are approximations of our understanding, which we can communicate to others”). I might borrow your analogy next time I teach complexity theory. Thanks for sharing!

1

Reposted by Tom Gur

John Watrous @johnwatrous.bsky.social · Jul 16

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

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

5 35 150

Tom Gur @tomgur.bsky.social · Jun 27

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...

Clément Canonne: What is deterministic amplification?

YouTube video by Sydney Mathematical Research Institute - SMRI

www.youtube.com

1 2 14

Tom Gur @tomgur.bsky.social · Jun 11

Excited to have Yiyi in Cambridge next year!

1

Reposted by Tom Gur

Ryan O'Donnell @booleananalysis.bsky.social · Jun 9

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

1 18 46

Reposted by Tom Gur

Lance Fortnow @lance.fortnow.com · Jun 7

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...

8 34

Reposted by Tom Gur

Clément Canonne @ccanonne.github.io · Jun 4

#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...

3 11

Reposted by Tom Gur

TCS+ @tcsplus.bsky.social · May 28

📢 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

TCS+ RSVP: Irit Dinur (2025/06/04)

Title: Agreement Tests: Local Consistency, Global Structure

forms.gle

4 3

Reposted by Tom Gur

TCS+ @tcsplus.bsky.social · May 27

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]

2 4

Reposted by Tom Gur

Earl Campbell @quantumearl.bsky.social · May 24

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/...

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

5 9

Tom Gur @tomgur.bsky.social · May 17

This is such a good one-sentence (albeit a long one…) explanation of quantum computing!

Ryan O'Donnell @booleananalysis.bsky.social · May 17

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."

5

Tom Gur @tomgur.bsky.social · May 14

Thanks, Clément! You are too kind!

2

Tom Gur @tomgur.bsky.social · Apr 24

Definitely exciting! It would be great to have a TCS+ talk about it

3

Reposted by Tom Gur

Alex Bredariol Grilo @abgrilo.bsky.social · Apr 15

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

Complexity as a kaleidoscope / Le kaleidoscope de la complexité | Tag | Carmin.tv

www.carmin.tv

1 1 17