Avi Wigderson

You mentioned NP-Hard, NP-Complete, NP-EP.

I know there's other complexity classes.

Maybe you could give some more context on kind of the whole space of complexity classes.

You mentioned that these NP-complete problems, they kind of are all equivalent in some way.

What's the proof to equate a SAT solving problem to like a graph coloring problem or something like that?

Are they all similar in nature or are they kind of bespoke to the problem you're going to and from?

You mentioned time complexity and space complexity, and I think intuitively, like in software engineering, we often trade those off for each other.

Is there a general theory on that, on how these two trade off?

What's the trick?

If you could explain intuitively or is it too deep to explain?

So if you're counting arbitrarily large, that is information, and you're saying maybe the intuition is that information is encoded in the sequence of operations.

We talked about the equivalence between these NP-complete problems.

And then I know, in practice, a lot of people, to solve the other problems, they just use SAT solvers.

I would have thought that would be less efficient, though, because you got to kind of translate it and then you're doing it in almost like a different problem space.

We talked about all the different types of resources in an algorithm.

And in one of your talks, you said something where you consider randomness another resource for an algorithm.

What do you mean when you say randomness is a resource for an algorithm?

You mentioned a few times the quality of the randomness.

How do you quantify the quality of random bits?

In one of your lectures, actually, you mentioned that and you gave a good example.