randomness – Quanta Magazine

Computation Is All Around Us, and You Can See It if You Try

Lance Fortnow — Wed, 12 Jun 2024 13:26:12 +0000

In the movie Oppenheimer, Niels Bohr challenges the physicist early in his career: I can’t hear the algebra, but I feel the machine. I felt the machine even before I touched a computer. In the 1970s I awaited the arrival of my first one, a Radio Shack TRS-80, imagining how it would function. I wrote some simple programs on paper and could feel the machine I didn’t yet have processing each step.

Source

Avi Wigderson, Complexity Theory Pioneer, Wins Turing Award

Stephen Ornes — Wed, 10 Apr 2024 08:57:40 +0000

For more than 40 years, Avi Wigderson has studied problems. But as a computational complexity theorist, he doesn’t necessarily care about the answers to these problems. He often just wants to know if they’re solvable or not, and how to tell. “The situation is ridiculous,” said Wigderson, a computer scientist at the Institute for Advanced Study in Princeton, New Jersey. No matter how hard a...

Source

The Researcher Who Explores Computation by Conjuring New Worlds

Ben Brubaker — Wed, 27 Mar 2024 14:48:36 +0000

Imagine you’re on a quest to understand the very nature of computation. You’re deep in the wilderness, far from any paths, and inscrutable messages are carved into the trunks of trees all around you — BPP, AC0, Σ2P, YACC, and hundreds of others. The glyphs are trying to tell you something, but where to begin? You can’t even keep them all straight. Few researchers have done as much as Russell...

Source

Complexity Theory’s 50-Year Journey to the Limits of Knowledge

Ben Brubaker — Thu, 17 Aug 2023 16:00:21 +0000

In the first week of the fall semester in 2007, Marco Carmosino dragged himself to a math class required for all computer science majors at the University of Massachusetts, Amherst. Carmosino, a sophomore, was considering dropping out of college to design video games. Then the professor posed a simple question that would change the course of his life: How do you know math actually works?

Source

How Randomness Improves Algorithms

Ben Brubaker — Mon, 03 Apr 2023 14:10:52 +0000

Since the very first days of computer science — a field known for its methodical approach to problem-solving — randomness has played an important role. The first program to run on the world’s first general-purpose electronic computer used randomness to simulate nuclear processes. Similar approaches have since been used in astrophysics, climate science and economics. In all these cases...

Source