The New York Public Library sells a magnet printed with words by the American author Fran Lebowitz: “Think before you speak. Read before you think.”...
Greetings from the land of the Ohlone. As the year draws to a close, I am grateful for all of you who make up our brilliant, innovative, open-minded...
Three researchers have figured out how to craft a proof that spreads out information while keeping it perfectly secret.
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.
Some of the richest and most lasting mathematical ideas come about when two distinct fields come together and pay close attention to their intersections. That was the goal of the workshop on Structural Results held at the Simons Institute in July 2023, in which extremal combinatorists and theoretical computer scientists specializing in complexity convened to talk about the overlap between their two fields.
The Simons Institute’s ninth Industry Day was our largest to date, with over 150 attendees from the Institute, the broader UC Berkeley campus, our partner and sponsor companies, and beyond. The event, which took place on November 2, was designed to facilitate knowledge-sharing among industry and academic scientists, and to highlight the importance of industry partners in supporting research in the foundations of computing.