Scott Aaronson's user avatar
Scott Aaronson's user avatar
Scott Aaronson's user avatar
Scott Aaronson
  • Member for 14 years, 3 months
  • Last seen more than 3 years ago
106 votes
10 answers
14k views

Analogues of P vs. NP in the history of mathematics

74 votes
8 answers
12k views

Succinctly naming big numbers: ZFC versus Busy-Beaver

54 votes
10 answers
8k views

The "sensitivity" of 2-colorings of the d-dimensional integer lattice

45 votes
2 answers
8k views

"Closed-form" functions with half-exponential growth

45 votes
1 answer
5k views

Anti-concentration bound for permanents of Gaussian matrices?

43 votes
3 answers
5k views

"Simpler" statements equivalent to Con(PA) or Con(ZFC)?

40 votes
2 answers
3k views

Is there a computable ordinal encoding the proof strength of ZF? Is it knowable?

35 votes
4 answers
5k views

Massive cancellations

31 votes
1 answer
7k views

"psi-epistemic theories" in 3 or more dimensions

29 votes
1 answer
1k views

Can a string's sophistication be defined in an unsophisticated way?

28 votes
1 answer
2k views

Why isn't this a computable description of the ordinal of ZF?

28 votes
1 answer
783 views

Are there any nontrivial near-isometries of the $n$-dimensional cube?

27 votes
3 answers
4k views

Is deciding whether a Turing machine *provably* runs forever equivalent to the halting problem?

23 votes
2 answers
850 views

Possible behaviors of integer sequences that arise from powering nonnegative integer matrices

22 votes
1 answer
5k views

Analogue of the Chebyshev polynomials over C?

21 votes
2 answers
1k views

Minimum number of variables on which a multivariate polynomial depends?

19 votes
0 answers
575 views

Can Gentzen-style proofs give omega-consistency and beyond?

19 votes
3 answers
2k views

Can you cover the Boolean cube $\{0,1\}^n$ with $O(1)$ Hamming-balls each of radius $n/2-c\sqrt{n}$?

19 votes
3 answers
4k views

Pi1-sentence independent of ZF, ZF+Con(ZF), ZF+Con(ZF)+Con(ZF+Con(ZF)), etc.?

18 votes
3 answers
1k views

Decomposing a finite group as a product of subsets

15 votes
0 answers
1k views

A Kakeya-like problem: must a union of annuli fill the plane?

14 votes
3 answers
382 views

Exact coverability of $\mathbb{Z}_n$ by cyclic shifts of a given set -- easy? NP-complete?

11 votes
1 answer
616 views

Real polynomial bounded at inverse-integer points

11 votes
0 answers
200 views

Degree of 2-variable real polynomial that’s large on a square and small on a nearby “L”