User Scott Aaronson

110 votes

10 answers

15k views

Analogues of P vs. NP in the history of mathematics

asked Mar 13, 2014 at 20:12

77 votes

8 answers

12k views

Succinctly naming big numbers: ZFC versus Busy-Beaver

asked Aug 6, 2010 at 0:57

54 votes

10 answers

8k views

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

asked Jul 11, 2010 at 23:48

46 votes

2 answers

8k views

"Closed-form" functions with half-exponential growth

asked Nov 9, 2010 at 18:51

45 votes

1 answer

6k views

Anti-concentration bound for permanents of Gaussian matrices?

asked Nov 12, 2010 at 13:01

44 votes

3 answers

5k views

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

asked Apr 24, 2011 at 20:16

40 votes

2 answers

4k views

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

asked Apr 23, 2014 at 18:10

35 votes

4 answers

5k views

Massive cancellations

asked Nov 25, 2014 at 1:18

31 votes

1 answer

7k views

"psi-epistemic theories" in 3 or more dimensions

asked Apr 30, 2012 at 0:23

29 votes

1 answer

1k views

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

asked Jul 31, 2012 at 15:05

28 votes

1 answer

794 views

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

asked Jun 26, 2014 at 14:58

27 votes

1 answer

2k views

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

asked May 6, 2014 at 17:44

27 votes

3 answers

4k views

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

asked May 22, 2013 at 2:03

23 votes

1 answer

5k views

Analogue of the Chebyshev polynomials over C?

asked Dec 14, 2009 at 21:31

23 votes

2 answers

880 views

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

asked May 21, 2017 at 13:34

20 votes

2 answers

1k views

Minimum number of variables on which a multivariate polynomial depends?

asked Mar 12, 2014 at 17:19

19 votes

0 answers

590 views

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

asked Apr 25, 2014 at 12:42

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}$?

asked Jun 18, 2012 at 12:18

19 votes

3 answers

5k views

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

asked Jun 8, 2011 at 6:19

19 votes

3 answers

1k views

Decomposing a finite group as a product of subsets

asked May 28, 2017 at 0:06

15 votes

0 answers

1k views

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

asked Oct 1, 2012 at 1:32

14 votes

3 answers

410 views

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

asked Mar 16, 2021 at 17:25

11 votes

1 answer

645 views

Real polynomial bounded at inverse-integer points

asked Jun 5, 2018 at 20:02

11 votes

0 answers

209 views

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

asked Aug 5, 2018 at 1:15

Stack Exchange Network

24 Questions

Analogues of P vs. NP in the history of mathematics

Succinctly naming big numbers: ZFC versus Busy-Beaver

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

"Closed-form" functions with half-exponential growth

Anti-concentration bound for permanents of Gaussian matrices?

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

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

Massive cancellations

"psi-epistemic theories" in 3 or more dimensions

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

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

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

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

Analogue of the Chebyshev polynomials over C?

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

Minimum number of variables on which a multivariate polynomial depends?

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

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

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

Decomposing a finite group as a product of subsets

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

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

Real polynomial bounded at inverse-integer points

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