News

Think about the last time you faced a problem you couldn’t solve. Say it was something practical, something that originally seemed small — a leaky faucet, for example. You’re about to give up and call a plumber, but first you want to see whether you’re close. Maybe it really is easy to fix the problem, and you just need to know where to look. Or maybe it’s far more difficult than you think. So now you’re trying to solve a new problem, a meta-problem: instead of fixing the leaky faucet, you’re trying to figure out how hard it will be to fix the leaky faucet. 

Greetings from Berkeley, where we are deep into a pair of interconnected research programs on Quantum Algorithms, Complexity, and Fault Tolerance and on Error-Correcting Codes: Theory and Practice.

Presented by John Wright (UC Berkeley), this boot camp talk offers an introduction to quantum codes, aimed at a general (not-necessarily-quantum) audience. Wright begins with a brief introduction to quantum computing, and then introduces the powerful family of quantum codes known as CSS codes.

Last month, our two closely related research programs on quantum computing and on error-correcting codes (ECC) held a joint boot camp. On the ECC side, one of the highlights was a three-part tutorial on Probabilistic and Combinatorial Methods, presented by Jonathan Mosheiff (Ben-Gurion University). We’re pleased to share Part I with you here.

I’ve temporarily moved to Berkeley, California, where I am the “science communicator in residence” at the Simons Institute, the world’s leading institute for collaborative research in theoretical computer science. One nano-collaboration is today’s puzzle – told to me by a computer scientist at Microsoft I befriended over tea. It’s about data centres – those warehouses containing endless rows of computers that store all our data.

I’m happy to be writing to you again from Berkeley, after a six-month sabbatical. This semester, we are hosting a pair of interrelated programs — on Quantum Algorithms, Complexity, and Fault Tolerance, and on Error-Correcting Codes: Theory and Practice. 

The rain in Berkeley is busy washing Calvin Lab for a shiny new semester at the Simons Institute. This is a good moment to reflect on some of the exciting happenings of the past semester. One subject very much in the air during the Data Structures and Optimization for Fast Algorithms program was recent progress on the classical question of computing a maximum st-flow in a directed graph.

At the recent workshop on Optimization and Algorithm Design, Adrian Vladu (IRIF) introduced a new algorithmic framework for discrepancy minimization based on regularization.

In 2023, computer scientists made progress on a new vector-driven approach to AI, fundamentally improved Shor’s algorithm for factoring large numbers, and examined the surprising and powerful behaviors that can emerge from large language models.

Greetings from Berkeley, where an exciting semester is drawing to a close. This week we say goodbye to the participants in our fall research programs on Logic and Algorithms in Database Theory and AI, and on Data Structures and Optimization for Fast Algorithms. We will resume activities early in the new year, with synergistic spring programs on Error-Correcting Codes and on Quantum Algorithms, Complexity, and Fault Tolerance.