Research

The European Association for Theoretical Computer Science (EATCS) recently awarded Ryan Williams, MIT EECS professor and CSAIL member, with the 2024 Gödel Prize for his 2011 paper, “Non-Uniform ACC Circuit Lower Bounds.” Williams receives this honor for presenting a novel paradigm for a “rich two-way connection" between algorithmic techniques and lower-bound methods.

Most people agree that the spread of online misinformation is a serious problem. But there is much less consensus on what to do about it.

When water freezes, it transitions from a liquid phase to a solid phase, resulting in a drastic change in properties like density and volume. Phase transitions in water are so common most of us probably don’t even think about them, but phase transitions in novel materials or complex physical systems are an important area of study.

Imagine you and a friend are playing a game where your goal is to communicate secret messages to each other using only cryptic sentences. Your friend's job is to guess the secret message behind your sentences. Sometimes, you give clues directly, and other times, your friend has to guess the message by asking yes-or-no questions about the clues you've given. The challenge is that both of you want to make sure you're understanding each other correctly and agreeing on the secret message.