* . *
  • About
  • Advertise
  • Privacy & Policy
  • Contact
Sunday, June 29, 2025
Earth-News
  • Home
  • Business
  • Entertainment
    Susquehanna Raises Penn Entertainment Inc. (PENN) Price Target. – Yahoo Finance

    Susquehanna Raises Price Target for Penn Entertainment Inc. (PENN)

    George Lopez is coming to Spokane – KXLY.com

    George Lopez is coming to Spokane – KXLY.com

    Netflix unveils Dallas immersive venue for fans of hit shows like ‘Squid Game,’ ‘Stranger Things’ – Houston Chronicle

    Step Inside Netflix’s New Dallas Immersive Experience Featuring Hits Like ‘Squid Game’ and ‘Stranger Things

    ‘Puttin’ on the Ritz’: Civic Players bring ‘Young Frankenstein’ to life – Yahoo

    Civic Players Deliver a Hilarious and Unforgettable Performance of ‘Young Frankenstein

    ‘Wheel of Fortune’: Amputee Wins $60,000 After Breaking Incredible ‘Curse’ – Hastings Tribune

    Wheel of Fortune’ Amputee Breaks Incredible ‘Curse’ to Win $60,000!

    North Star Sports & Entertainment Network: Coming soon – KTTC News

    North Star Sports & Entertainment Network: Coming soon – KTTC News

  • General
  • Health
  • News

    Cracking the Code: Why China’s Economic Challenges Aren’t Shaking Markets, Unlike America’s” – Bloomberg

    Trump’s Narrow Window to Spread the Truth About Harris

    Trump’s Narrow Window to Spread the Truth About Harris

    Israel-Gaza war live updates: Hamas leader Ismail Haniyeh assassinated in Iran, group says

    Israel-Gaza war live updates: Hamas leader Ismail Haniyeh assassinated in Iran, group says

    PAP Boss to Niger Delta Youths, Stay Away from the Protest

    PAP Boss to Niger Delta Youths, Stay Away from the Protest

    Court Restricts Protests In Lagos To Freedom, Peace Park

    Court Restricts Protests In Lagos To Freedom, Peace Park

    Fans React to Jazz Jennings’ Inspiring Weight Loss Journey

    Fans React to Jazz Jennings’ Inspiring Weight Loss Journey

    Trending Tags

    • Trump Inauguration
    • United Stated
    • White House
    • Market Stories
    • Election Results
  • Science
  • Sports
  • Technology
    Naples restaurant owner prepares for hurricane season with new flood technology – Fox4Now.com

    Naples restaurant owner prepares for hurricane season with new flood technology – Fox4Now.com

    Emerging Memory and Storage Technology Market Analysis Report 2025-2034 | AI and HPC Boom Fuels Surging Demand for Fast, Low-Power Memory Devices – Yahoo Finance

    How AI and HPC Are Driving Explosive Growth in Fast, Low-Power Memory Technologies Through 2034

    Ostin Technology (OST): Volatility’s Warning or Contrarian Opportunity? – AInvest

    Ostin Technology (OST): Navigating Market Volatility – Red Flag or Hidden Opportunity?

    St. Francis Medical Center brings advanced robotic surgery technology to Northeast Louisiana – KNOE

    St. Francis Medical Center brings advanced robotic surgery technology to Northeast Louisiana – KNOE

    Wayve Expands Engineering Leadership to Power Next-Gen Autonomous Driving Technology – Silicon Canals

    Wayve Boosts Engineering Leadership to Accelerate Next-Gen Autonomous Driving Innovation

    Frontdoor Announces Tech Expert Dr. Bala Ganesh as Chief Technology Officer – Business Wire

    Frontdoor Appoints Tech Visionary Dr. Bala Ganesh as New Chief Technology Officer

    Trending Tags

    • Nintendo Switch
    • CES 2017
    • Playstation 4 Pro
    • Mark Zuckerberg
No Result
View All Result
  • Home
  • Business
  • Entertainment
    Susquehanna Raises Penn Entertainment Inc. (PENN) Price Target. – Yahoo Finance

    Susquehanna Raises Price Target for Penn Entertainment Inc. (PENN)

    George Lopez is coming to Spokane – KXLY.com

    George Lopez is coming to Spokane – KXLY.com

    Netflix unveils Dallas immersive venue for fans of hit shows like ‘Squid Game,’ ‘Stranger Things’ – Houston Chronicle

    Step Inside Netflix’s New Dallas Immersive Experience Featuring Hits Like ‘Squid Game’ and ‘Stranger Things

    ‘Puttin’ on the Ritz’: Civic Players bring ‘Young Frankenstein’ to life – Yahoo

    Civic Players Deliver a Hilarious and Unforgettable Performance of ‘Young Frankenstein

    ‘Wheel of Fortune’: Amputee Wins $60,000 After Breaking Incredible ‘Curse’ – Hastings Tribune

    Wheel of Fortune’ Amputee Breaks Incredible ‘Curse’ to Win $60,000!

    North Star Sports & Entertainment Network: Coming soon – KTTC News

    North Star Sports & Entertainment Network: Coming soon – KTTC News

  • General
  • Health
  • News

    Cracking the Code: Why China’s Economic Challenges Aren’t Shaking Markets, Unlike America’s” – Bloomberg

    Trump’s Narrow Window to Spread the Truth About Harris

    Trump’s Narrow Window to Spread the Truth About Harris

    Israel-Gaza war live updates: Hamas leader Ismail Haniyeh assassinated in Iran, group says

    Israel-Gaza war live updates: Hamas leader Ismail Haniyeh assassinated in Iran, group says

    PAP Boss to Niger Delta Youths, Stay Away from the Protest

    PAP Boss to Niger Delta Youths, Stay Away from the Protest

    Court Restricts Protests In Lagos To Freedom, Peace Park

    Court Restricts Protests In Lagos To Freedom, Peace Park

    Fans React to Jazz Jennings’ Inspiring Weight Loss Journey

    Fans React to Jazz Jennings’ Inspiring Weight Loss Journey

    Trending Tags

    • Trump Inauguration
    • United Stated
    • White House
    • Market Stories
    • Election Results
  • Science
  • Sports
  • Technology
    Naples restaurant owner prepares for hurricane season with new flood technology – Fox4Now.com

    Naples restaurant owner prepares for hurricane season with new flood technology – Fox4Now.com

    Emerging Memory and Storage Technology Market Analysis Report 2025-2034 | AI and HPC Boom Fuels Surging Demand for Fast, Low-Power Memory Devices – Yahoo Finance

    How AI and HPC Are Driving Explosive Growth in Fast, Low-Power Memory Technologies Through 2034

    Ostin Technology (OST): Volatility’s Warning or Contrarian Opportunity? – AInvest

    Ostin Technology (OST): Navigating Market Volatility – Red Flag or Hidden Opportunity?

    St. Francis Medical Center brings advanced robotic surgery technology to Northeast Louisiana – KNOE

    St. Francis Medical Center brings advanced robotic surgery technology to Northeast Louisiana – KNOE

    Wayve Expands Engineering Leadership to Power Next-Gen Autonomous Driving Technology – Silicon Canals

    Wayve Boosts Engineering Leadership to Accelerate Next-Gen Autonomous Driving Innovation

    Frontdoor Announces Tech Expert Dr. Bala Ganesh as Chief Technology Officer – Business Wire

    Frontdoor Appoints Tech Visionary Dr. Bala Ganesh as New Chief Technology Officer

    Trending Tags

    • Nintendo Switch
    • CES 2017
    • Playstation 4 Pro
    • Mark Zuckerberg
No Result
View All Result
Earth-News
No Result
View All Result
Home Science

The Researcher Who Explores Computation by Conjuring New Worlds

March 28, 2024
in Science
The Researcher Who Explores Computation by Conjuring New Worlds
Share on FacebookShare on Twitter

Russell Impagliazzo studies hard problems, the limits of cryptography, the nature of randomness and more.

Russel Impagliazzo wearing a dark shirt and sunglasses stands outside a tree-shaped building

Russell Impagliazzo, a computer scientist at the University of California, San Diego, uses his vivid imagination to study the difficulty of computational problems.

Jesse Aragon for Quanta Magazine

Introduction

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[m], Σ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 Impagliazzo to cut through this seeming chaos. For 40 years, Impagliazzo has worked at the forefront of computational complexity theory, the study of the intrinsic difficulty of different problems. The most famous open question in this field, called the P versus NP problem, asks whether many seemingly hard computational problems are actually easy — with the right algorithm. An answer would have far-reaching implications for science and the security of modern cryptography.

In the 1980s and 1990s, Impagliazzo played a leading role in unifying the theoretical foundations of cryptography. In 1995, he articulated the significance of these new developments in an iconic paper that reformulated possible solutions to P versus NP and a handful of related problems in the language of five hypothetical worlds we might inhabit, whimsically dubbed Algorithmica, Heuristica, Pessiland, Minicrypt and Cryptomania. Impagliazzo’s five worlds have inspired a generation of researchers, and they continue to guide research in the flourishing subfield of meta-complexity.

And these aren’t the only worlds he’s dreamed up. Impagliazzo has been a lifelong aficionado of tabletop role-playing games like Dungeons and Dragons, and he delights in inventing new sets of rules and new settings to explore. The same playful spirit animates his 30-year practice of improvisational comedy.

Impagliazzo also did foundational work elucidating the fundamental role of randomness in computation. In the late 1970s, computer scientists discovered that randomness could sometimes improve algorithms for solving inherently deterministic problems — a counterintuitive finding that perplexed researchers for years. Impagliazzo’s work with the complexity theorist Avi Wigderson and other researchers in the 1990s showed that if certain computational problems really are fundamentally hard, then it’s always possible to convert algorithms that use randomness into deterministic ones. And conversely, proving that randomness can be eliminated from any algorithm would also prove that truly hard problems exist.

Quanta spoke with Impagliazzo about the difference between hard problems and hard puzzles, consulting oracles, and the mathematical lessons of improv comedy. The interview has been condensed and edited for clarity.

Introduction

When did you first get interested in mathematics?

I was interested in math even before I really knew what it was. In third grade, my math grades started slipping because we were supposed to memorize our multiplication tables, and I refused. My mother said, “But Russell, you love math, why aren’t you doing this?” And I said, “That’s not math, that’s memorization. Real math doesn’t involve memorization.” All I’d learned at that point was arithmetic, so I’m not sure where I got the notion that math was about abstract concepts.

What about computer science? Parts of the field are very abstract, but they aren’t what most people first encounter.

In high school, I’d had a programming course in BASIC, but it was really hard to get anything done. The programs had to be transferred to paper tapes, which had to be run through this very old computer that often malfunctioned and ripped your paper in half. So I thought computer science was dreadfully dull.

I intended to study logic. But a lot of the concepts, when you tried to actually formalize them, involved computation and especially limits on computation. Questions like “How do we know things in mathematics are true?” and “How do we understand the difficulty of doing mathematics?” led to theoretical computer science, and complexity theory especially.

Some of your most famous work explores the connections between cryptography and computational complexity theory. Why are those two fields related?

When you’re setting up a cryptographic system, you need to distinguish between legitimate users — the people you want to grant access to — and everybody else. Computationally difficult problems give us a way to distinguish these groups based on what they know. But if you want knowing the answer to a problem to be a way of distinguishing two groups of people, you can’t just use any hard problem — you need a hard puzzle.

Russell Impagliazzo, in khakis and a dark shirt, stands on a path outside a building

In the 1990s, Impagliazzo and other researchers established a tight connection between proving problems hard and eliminating randomness from algorithms.

Jennifer Siegwart for Quanta Magazine

Introduction

What’s the difference between a problem and a puzzle?

In general, the person posing a problem might not know the answer. A puzzle is a problem designed with an answer in mind. So why do we need a puzzle? Because we need to be able to determine whether a person who supposedly solved it actually did. In everyday life, we use puzzles for amusement, but we also use them in classrooms to test whether people understood the material. This is what happens in cryptography: We’re using puzzles to test someone’s knowledge.

The difference between the five worlds is how they answer the questions “Are there hard problems?” and “Are there hard puzzles?”

How do those different answers play out?

In the first world, Algorithmica, no problems are hard. You don’t have to know how someone designed your problem: You can always solve it. Heuristica is saying, “Well, maybe a few problems are hard.” Then we get to Pessiland, where many problems are hard, but most puzzles aren’t. Almost any problem that I make up where I know the solution, you’re going to be able to solve it too. All of these worlds are bad for cryptography.

In Minicrypt, I can create puzzles that I know how to solve that are still really challenging for you. And finally, Cryptomania is a world in which two people can stand in a public location where an eavesdropper can hear and together create a puzzle that’s still hard for the eavesdropper.

What motivated you to write the five worlds paper?

At the time, it was known that different answers to the P versus NP question would have a big impact on what kind of problems we can solve and also what kind of security we can hope for, but the qualitative distinctions between different forms of easiness and hardness were not really clear.

There was a very insightful paper just a few years earlier that laid out the distinctions using many interrelated questions with like 20 possible answers. One reason why I wanted to write the five worlds paper was we had made a huge amount of progress in those few years. It would have been hard to find names for 20 possible worlds.

Russell Impagliazzo, in a dark shirt, gazes into the distance

Impagliazzo’s iconic 1995 paper reframed possible answers to the P versus NP problem as five hypothetical worlds.

Jennifer Siegwart for Quanta Magazine

Introduction

So why frame it that way, as different worlds with quirky names?

I had agreed to write this paper for a conference. I was staying up late at night trying to figure out what I was going to say, and somewhere around 1 a.m. the different worlds framing seemed like a good idea. And then I read it the next morning and it still seemed like an OK idea — it was a way to show how these ideas would actually influence the world without getting caught up in quantitative details. What makes me happiest about this paper is that I hear from people doing research in complexity that this was the paper that got them interested in the field as undergraduates.

Have researchers ruled out any of the five possible worlds?

We’re actually adding more — people have started talking about Obfustopia as a world of even stronger cryptographic tools. It is a little depressing that we made so much progress in the late 1980s and haven’t eliminated any worlds since then. But on the other hand, we know a lot more about the connections between worlds and have a much clearer picture of what each world would look like.

Hypothetical worlds also play another role in complexity theory, in proofs that assume the existence of “oracles.” So, first of all, what exactly is an oracle?

Imagine someone builds an ingenious device that can solve some problem without us knowing an algorithm for solving that problem. That’s what an oracle is. If we had such a miraculous device and we put it inside our computers, it could shift where the line is between what is computable and what is not computable.

Russell Impagliazzo, in khakis and a dark shirt, sits in a yellow room and types on a tablet

Impagliazzo loved abstract mathematics as a child, but he had a bad first experience with programming. “I thought computer science was dreadfully dull,” he said.

Jennifer Siegwart for Quanta Magazine

Introduction

Do researchers think these magic boxes could actually exist?

No, they probably do not exist. Early on, oracle results were somewhat controversial because they’re so hypothetical. But one way they can be very enlightening is when the oracle is used to model an ideal situation. Say you’re trying to show that A doesn’t necessarily imply B. You start with the setting where you have the most extreme A and show that that’s still not enough to guarantee B. If you can show that even if all the odds are in your favor you still can’t prove something, that’s really strong evidence that it’s going to be difficult to prove.

You’ve also discovered links between computational hardness and randomness. How does that connection work?

It’s really a way of saying that if you don’t understand something, then it might seem random. Suppose I say I’m thinking of a number between one and a thousand. If I pick the number at random, you have a one-in-a-thousand chance of guessing it. And if I ask — following Monty Python — “In miles per hour, what’s the average airspeed of a European swallow?” you’ve got about the same chance. It probably goes more than one mile an hour, and it probably doesn’t go more than a thousand miles per hour.

This is not actually random — it’s a deterministically answerable question. We could just measure all the swallows flying around, but it’s kind of hard to determine with limited resources, like not having a budget for measuring swallow speeds and not having an infinite supply of swallows.

So the insight is that hard problems whose solutions we don’t know can provide a source of “pseudorandom” numbers that look random.

Russell Impagliazzo, in khakis and a dark shirt, sits at a desk in a classroom

Doing improv comedy for 30 years has informed how Impagliazzo approaches his work. “It’s good practice for not being hypercritical about every thought you have,” he said.

Jennifer Siegwart for Quanta Magazine

Introduction

Speaking of Monty Python, I know you’ve been doing improv comedy for a long time now — how did you get started?

I started as an assistant professor in San Diego in 1991. And around ’94 or so, I thought, “I really don’t have much of a life outside of the department.” So I got the free weekly paper, and I looked through the list of clubs and activities. I eliminated everything except improv comedy — I thought it was at least plausible that I’d be OK at it. I met my wife in that beginner class.

What did she think?

She says I was really awful. When you’re a logician, you’re trained to always think about the nuance of every word. You don’t want to say something incorrect. Improv is great in that it reverses that: The point is not to say something perfect but to make up something quickly. It was the opposite of the rest of my life.

My now-wife took a break from the class, and when she returned a year later, I managed to impress her. That was 30 years ago. I still take the same class with the same instructor.

Has doing improv changed the way you approach your research?

It’s good practice for not being hypercritical about every thought you have. That’s especially helpful in collaborations. When doing work with other people, I used to say things like, “But that idea won’t work for the following reason. That’s not literally true.” In improv, you’re always supposed to accept what your partner says. And I think that’s a good attitude to have, especially when you’re doing research with students: Don’t dismiss something they say just because you know it’s incorrect. There are lots of good ideas that aren’t 100% correct.

Russell Impagliazzo, in khakis and a dark shirt, looks out a window

In his personal life, Impagliazzo explores hypothetical worlds through collaborative role-playing games.

Jennifer Siegwart for Quanta Magazine

Introduction

Like what?

When you’re trying to get intuition for a problem, one thing that helps is to start with some simplifying assumptions. Those assumptions are usually not true, but they can help you come up with a road map. Say, “If I had an elephant, I could get over the mountains. Of course, I don’t have an elephant. But if I did, here’s how I would do it.” And then you realize, “Well, maybe I don’t need an elephant for this step. A mule would be fine.”

What about your love of role-playing games — has that influenced your work at all?

It may not have influenced all my research, but it certainly did influence my five worlds paper. I’ve always had a general interest in fantasy and science fiction and coming up with different possible worlds — what would things be like if everything was different?

Why are role-playing games such a compelling way to explore hypothetical worlds?

People who are into speculative fiction have always invented worlds. Tolkien is most famous for it, and he had such a massive imagination that his world actually felt lived in. For those of us who aren’t as imaginative, the best way to achieve that is to invite people into your setting, and a game is a way of doing that. Now it’s not just my world. It may have started how I imagined it, but just like in any collaboration, because of everyone else’s contributions it’s evolved way past that.

Next article

Topologists Tackle the Trouble With Poll Placement

>>> Read full article>>>
Copyright for syndicated content belongs to the linked Source : Quanta Magazine – https://www.quantamagazine.org/the-researcher-who-explores-computation-by-conjuring-new-worlds-20240327/

Tags: exploresResearcherscience
Previous Post

Business confidence falls again, but retail expected to turn around

Next Post

Unlocking the Mysteries of Protein Folding With Advanced Microscopy

Naples restaurant owner prepares for hurricane season with new flood technology – Fox4Now.com

Naples restaurant owner prepares for hurricane season with new flood technology – Fox4Now.com

June 29, 2025
Fireworks sales support Folsom youth sports: ‘This is our biggest fundraiser’ – Sacramento Bee

Fireworks Sales Ignite Support for Folsom Youth Sports: “This Is Our Biggest Fundraiser

June 29, 2025
Murder, she measured: The impressive science behind Agatha Christie’s poisons – Big Think

Deadly Secrets Unveiled: The Fascinating Science Behind Agatha Christie’s Poisons

June 28, 2025
Science and social norms – Golf Course Management magazine

How Science is Revolutionizing Social Norms in Golf Course Management

June 28, 2025
Study Links Skipping Breakfast to Poor Diet and Lifestyle Habits in Teens – Olive Oil Times

Study Links Skipping Breakfast to Poor Diet and Lifestyle Habits in Teens – Olive Oil Times

June 28, 2025
What Worries the World – June 2025 – Ipsos

Top Global Concerns Shaping June 2025

June 28, 2025
Small business owners aren’t jumping for joy about the US economy – but they still aren’t jumping ship – The Guardian

Small Business Owners Hold Firm Amid Ongoing Uncertainty About the US Economy

June 28, 2025
U.S. uninsured rates could resurge if Trump’s budget bill passes – NPR

U.S. Uninsured Rates Could Surge if Trump’s Budget Bill Becomes Law

June 28, 2025
Emerging Memory and Storage Technology Market Analysis Report 2025-2034 | AI and HPC Boom Fuels Surging Demand for Fast, Low-Power Memory Devices – Yahoo Finance

How AI and HPC Are Driving Explosive Growth in Fast, Low-Power Memory Technologies Through 2034

June 28, 2025
Axios Event: Media execs are betting big on women’s sports – Axios

Axios Event: Media execs are betting big on women’s sports – Axios

June 28, 2025

Categories

Archives

June 2025
MTWTFSS
 1
2345678
9101112131415
16171819202122
23242526272829
30 
« May    
Earth-News.info

The Earth News is an independent English-language daily published Website from all around the World News

Browse by Category

  • Business (20,132)
  • Ecology (699)
  • Economy (722)
  • Entertainment (21,613)
  • General (15,611)
  • Health (9,761)
  • Lifestyle (727)
  • News (22,149)
  • People (723)
  • Politics (728)
  • Science (15,939)
  • Sports (21,219)
  • Technology (15,707)
  • World (702)

Recent News

Naples restaurant owner prepares for hurricane season with new flood technology – Fox4Now.com

Naples restaurant owner prepares for hurricane season with new flood technology – Fox4Now.com

June 29, 2025
Fireworks sales support Folsom youth sports: ‘This is our biggest fundraiser’ – Sacramento Bee

Fireworks Sales Ignite Support for Folsom Youth Sports: “This Is Our Biggest Fundraiser

June 29, 2025
  • About
  • Advertise
  • Privacy & Policy
  • Contact

© 2023 earth-news.info

No Result
View All Result

© 2023 earth-news.info

No Result
View All Result

© 2023 earth-news.info

Go to mobile version