Scott_Aaronson2

Karma: 244

Scott_Aaronson2 14 Nov 2008 17:36 UTC
2 points
on: The Weighted Majority Algorithm
Will: Yeah, it’s ¹⁄₄, thanks. I somehow have a blind spot when it comes to constants. ;-)

Scott_Aaronson2 14 Nov 2008 16:43 UTC
7 points
on: The Weighted Majority Algorithm
Silas: Look, as soon you find a 1 bit, you’ve solved the problem with certainty. You have no remaining doubt about the answer. And the expected number of queries until you find a 1 bit is O(1) (or 2 to be exact). Why? Because with each query, your probability of finding a 1 bit is ¹⁄₂. Therefore, the probability that you need t or more queries is (1/2)^(t-1). So you get a geometric series that sums to 2.

(Note: I was careful to say you succeed with certainty after an expected number of queries independent of n—not that there’s a constant c such that you succeed with certainty after c queries, which would be a different claim!)

And yes, I absolutely assume that the adversary knows the algorithm, because your algorithm is a fixed piece of information! Once again, the point is not that the universe is out to get us—it’s that we’d like to succeed even if it is out to get us. In particular, we don’t want to assume that we know the probability distribution over inputs, and whether it might happen to be especially bad for our algorithm. Randomness is useful precisely for “smearing out” over the set of possible environments, when you’re completely ignorant about the environment.

If you’re not to think this way, the price you pay for Bayesian purity is to give up whole theory of randomized algorithms, with all the advances it’s led to even in deterministic algorithms; and to lack the conceptual tools even to ask basic questions like P versus BPP.

It feels strange to be explaining CS101 as if I were defending some embattled ideological claim—but it’s good to be reminded why it took people a long time to get these things right.

Scott_Aaronson2 14 Nov 2008 14:59 UTC
4 points
on: The Weighted Majority Algorithm
Silas: “Solve” = for a worst-case string (in both the deterministic and randomized cases). In the randomized case, just keep picking random bits and querying them. After O(1) queries, with high probability you’ll have queried either a 1 in the left half or a 1 in the right half, at which point you’re done.

As far as I know this problem doesn’t have a name. But it’s how (for example) you construct an oracle separating P from ZPP.

Scott_Aaronson2 14 Nov 2008 9:02 UTC
10 points
on: The Weighted Majority Algorithm
Don: When you fix the goalposts, make sure someone can’t kick the ball straight in! :-) Suppose you’re given an n-bit string, and you’re promised that exactly n/4 of the bits are 1, and they’re either all in the left half of the string or all in the right half. The problem is to decide which. It’s clear that any deterministic algorithm needs to examine at least n/4 + 1 of the bits to solve this problem. On the other hand, a randomized sampling algorithm can solve the problem with certainty after looking at only O(1) bits on average.

Eliezer: I often tell people that theoretical computer science is basically mathematicized paranoia, and that this is the reason why Israelis so dominate the field. You’re absolutely right: we do typically assume the environment is an adversarial superintelligence. But that’s not because we literally think it is one, it’s because we don’t presume to know which distribution over inputs the environment is going to throw at us. (That is, we lack the self-confidence to impose any particular prior on the inputs.) We do often assume that, if we generate random bits ourselves, then the environment isn’t going to magically take those bits into account when deciding which input to throw at us. (Indeed, if we like, we can easily generate the random bits after seeing the input—not that it should make a difference.)

Average-case analysis is also well-established and used a great deal. But in those cases where you can solve a problem without having to assume a particular distribution over inputs, why complicate things unnecessarily by making such an assumption? Who needs the risk?
What links here?
- Can noise have power? by lukeprog (23 May 2014 4:54 UTC; 19 points)

Scott_Aaronson2 14 Nov 2008 1:26 UTC
10 points
on: The Weighted Majority Algorithm
I am interested in what Scott Aaronson says to this.

I fear Eliezer will get annoyed with me again :), but R and Stephen basically nailed it. Randomness provably never helps in average-case complexity (i.e., where you fix the probability distribution over inputs) -- since given any ensemble of strategies, by convexity there must be at least one deterministic strategy in the ensemble that does at least as well as the average.

On the other hand, if you care about the worst-case running time, then there are settings (such as query complexity) where randomness provably does help. For example, suppose you’re given n bits, you’re promised that either n/3 or 2n/3 of the bits are 1′s, and your task is to decide which. Any deterministic strategy to solve this problem clearly requires looking at 2n/3 + 1 of the bits. On the other hand, a randomized sampling strategy only has to look at O(1) bits to succeed with high probability.

Whether randomness ever helps in worst-case polynomial-time computation is the P versus BPP question, which is in the same league as P versus NP. It’s conjectured that P=BPP (i.e., randomness never saves more than a polynomial). This is known to be true if really good pseudorandom generators exist, and such PRG’s can be constructed if certain problems that seem to require exponentially large circuits, really do require them (see this paper by Impagliazzo and Wigderson). But we don’t seem close to proving P=BPP unconditionally.
What links here?
- Can noise have power? by lukeprog (23 May 2014 4:54 UTC; 19 points)

Scott_Aaronson2 4 Nov 2008 18:15 UTC
2 points
on: Complexity and Intelligence
(the superscripts didn’t show up: that was N^googol and 2^N)

Scott_Aaronson2 4 Nov 2008 18:13 UTC
4 points
on: Complexity and Intelligence
Um, except that we also don’t know whether there are computations that can be checked in N time but only performed in Ngoogol time. The situation is qualitatively the same as for N versus 2N.

Scott_Aaronson2 4 Nov 2008 17:41 UTC
2 points
on: Complexity and Intelligence
Otherwise, of course a larger environment can outsmart you mathematically.

No, not of course. For example, suppose P were equal to PSPACE. Then even though a larger environment could fundamentally outsmart you mathematically (say by solving the halting problem), it couldn’t prove to you that it was doing so. In other words, the situation with polynomial-time computation would be more-or-less the same as it is with unlimited computation: superintelligent machines could only prove their superintelligence to other superintelligent machines.

That the situation with efficient computation appears to be different—i.e., that it appears superintelligent machines can indeed prove their superintelligence to fundamentally dumber machines—is (if true) a profound fact about the world that seems worth calling attention to. Sure, of course you can nullify it by assuming away all complexity considerations, but why? :-)

Scott_Aaronson2 4 Nov 2008 12:56 UTC
7 points
on: Complexity and Intelligence
In fact, it’s just bloody hard to fundamentally increase your ability to solve math problems in a way that “no closed system can do” just by opening the system. So far as I can tell, it basically requires that the environment be magic and that you be born with faith in this fact.

As Wei mentioned, P≠NP is basically the conjecture that this isn’t true: i.e., that you can exponentially increase your ability to solve math problems by your environment being magic and your not being born with faith in that fact. So for example, if your environment immediately inverted any one-way function, that would be evidence (no faith required) that your environment is not merely ‘slightly’ smarter than you are, but astoundingly smarter. In qualitative terms, I think it would be almost as astounding as if the environment solved the halting problem.

Scott_Aaronson2 16 Sep 2008 0:34 UTC
1 point
on: My Childhood Death Spiral
Carl: I’m not sure, but I’d certainly try such a pill were the effects reversible.

Scott_Aaronson2 15 Sep 2008 22:47 UTC
3 points
on: My Childhood Death Spiral
I don’t have a problem, my environment has a problem.

Eliezer, I’m in complete sympathy with that attitude. I’ve had only limited success so far at nerdifying the rest of the world, but I’ll keep at it!

Scott_Aaronson2 15 Sep 2008 22:36 UTC
7 points
on: My Childhood Death Spiral
Lara: As far as I can tell, there are four basic problems.

First, if adults constantly praise and reward you for solving math problems, writing stories, and so on, then you aren’t forced to develop interpersonal skills to the same extent most kids are. You have a separate source of self-worth, and it may be too late that you realize that source isn’t enough. (Incidentally, the sort of interpersonal skills I’m talking about often get conflated with caring for others’ welfare, which then leads to moral condemnation of nerds as egotistical and aloof. But the two qualities seem completely unrelated to me. As often as not, those who are most skilled at convincing others to go along with them also care about others the least.) Of course, the same might in principle be true for any unusual talent, including musical or athletic talent—except that the latter are understood and rewarded by one’s peer group in a way that intellectual skills aren’t.

Second, math, physics, and so on can simply be fun, independently of whatever self-worth one derives from them. In this they’re no different from tennis or basket weaving or any other activity that some people enjoy. The trouble, again, is that while math and physics are reasonably well-rewarded economically, they’re not rewarded socially. And therefore, deriving pleasure from them can have the same sorts of social implications as deriving pleasure from heroin.

Third, even if you manage to overcome these handicaps, other people won’t know you have, and will be guided by the reigning stereotypes. They might decide before talking to you that you couldn’t possibly have anything in common with them. Naturally, this sort of thing can be overcome given enough social skill, but it’s another obstacle.

The fourth problem is specific to technical fields (rather than literary ones), and is just the well-known gender imbalance in those fields.

Given all of this, what’s surprising is not that so many “intelligence-centric types” are unhappy, but rather that in spite of it many manage to live reasonably happy lives. That’s the interesting part! :-)

Scott_Aaronson2 15 Sep 2008 20:31 UTC
4 points
on: My Childhood Death Spiral
how much money (or other utility-bearing fruit) would you demand (or pay Scott) to take a drug which lowered your IQ by x pts?

Here’s the funny thing: given who I am now, I would not pay to have my IQ lowered, and indeed would pay good money to avoid having it lowered, or even to have it raised. But I would also pay to have been, since early childhood, the sort of person who didn’t have such an intelligence-centric set of priorities. I’m not transitive in my preferences; I don’t want to want what I want.

Scott_Aaronson2 15 Sep 2008 18:56 UTC
1 point
on: My Childhood Death Spiral
Eliezer, I don’t think there’s a necessary tradeoff between intelligence (the academic rather than interpersonal kind) and happiness at the far nerd end of the spectrum—just that the way society is currently organized, it seems to be both true and common knowledge that there is (cf. Lara Foster’s comment). Though despite the temptation, I can’t justify dwelling on this phenomenon for too long—any more than on physical appearance, parental wealth, or any other aspect of our lives that we might love to “choose wisely” but can’t. Unlike many other accidents of birth, one could even regard this one as “cosmically justified” if one saw intelligence as having a value of its own, independent from happiness. If you disagree, then yes, I might need a better argument than Pfffft.

Scott_Aaronson2 15 Sep 2008 17:50 UTC
1 point
on: My Childhood Death Spiral
We are the cards we are dealt, and intelligence is the unfairest of all those cards.

I completely agree with that statement, though my interpretation of it might be the opposite of Eliezer’s. From The Simpsons:

Lisa: Dad, as intelligence goes up, happiness often goes down. In fact, I made a graph! [She holds up a decreasing, concave upward graph on axes marked “intelligence” and “happiness”] Lisa: [sadly] I make a lot of graphs.

Scott_Aaronson2 7 Aug 2008 21:49 UTC
0 points
on: Hiroshima Day
Apparently many people just don’t have a mental bin for global risks to humanity, only counting up the casualties to their own tribe and country. Either that or they’re just short-term thinkers.

Eliezer, I certainly worry about global risks to humanity, but I also worry about the “paradoxes” of utilitarian ethics. E.g., would you advocate killing an innocent person if long-term considerations convinced you it would have an 0.00001% chance of saving the human race? I’m pretty sure most people wouldn’t, and if asked to give a reason, might say that they don’t trust anyone to estimate such small probabilities correctly.

Scott_Aaronson2 7 Aug 2008 5:15 UTC
8 points
on: Hiroshima Day
I would have exploded the first bomb over the ocean, and only then used it against cities if Japan still hadn’t surrendered. No matter how many arguments I read about this, I still can’t understand the downsides of that route, besides the cost of a ‘wasted bomb.’

But what’s just as tragic as the bomb having been used in anger, is that it wasn’t finished 2-3 years earlier—in which case it could have saved tens of millions of lives.

Scott_Aaronson2 31 Jul 2008 8:14 UTC
5 points
on: Humans in Funny Suits
What you seem to want is an intelligence that is non-human but still close enough to human that we can communicate with it. Although it’s not clear what we’d have to talk about, once we get past the Pythagorean theorem.

How about P vs. NP? :-)

Scott_Aaronson2 31 Jul 2008 0:50 UTC
3 points
0
on: Humans in Funny Suits
Can’t we imagine the SF writers reasoning that they’re never going to succeed anyway in creating “real aliens,” so they might as well abandon that goal from the outset and concentrate on telling a good story? Absent actual knowledge of alien intelligences, perhaps the best one can ever hope to do is to write “hypothetical humans”: beings that are postulated to differ from humans in just one or two important respects that the writer wants to explore. (A good example is the middle third of The Gods Themselves, which delves into the family dynamics of aliens with three sexes instead of two, and one of the best pieces of SF I’ve read—not that I’ve read a huge amount.) Of course, most SF (like Star Wars) doesn’t even do that, and is just about humans with magic powers, terrible dialogue, and funny ears. I guess Star Trek deserves credit for at least occasionally challenging its audience, insofar as that’s possible with mass-market movies and TV.

Scott_Aaronson2 14 Jun 2008 10:58 UTC
1 point
on: Possibility and Could-ness
The algorithm has to assume many different possible actions as having been taken, and extrapolate their consequences, and then choose an action whose consequences match the goal … The algorithm, therefore, cannot produce an output without extrapolating the consequences of itself producing many different outputs.

It seems like you need to talk about our “internal state space”, not our internal algorithms—since as you pointed out yourself, our internal algorithms might never enumerate many possibilities (jumping off a cliff while wearing a clown suit) that we still regard as possible. (Indeed, they won’t enumerate many possibilities at all, if they do anything even slightly clever like local search or dynamic programming.)

Otherwise, if you’re not willing to talk about a state space independent of algorithms that search through it, then your account of counterfactuals and free will would seem to be at the mercy of algorithmic efficiency! Are more choices “possible” for an exponential-time algorithm than for a polynomial-time one?