Kyle Jones
  • Member for 10 years, 1 month
  • Last seen more than a week ago
  • Seattle, WA
6 answers
595 votes
122k views
774 bookmarks
What's new in purely functional data structures since Okasaki?
72 answers
480 votes
176k views
975 bookmarks
What papers should everyone read?
11 answers
256 votes
98k views
351 bookmarks
What is the enlightenment I'm supposed to attain after studying finite automata?
29 answers
137 votes
23k views
109 bookmarks
Problems Between P and NPC
18 answers
120 votes
9k views
63 bookmarks
Examples of the price of abstraction?
9 answers
92 votes
18k views
49 bookmarks
What would it mean to disprove Church-Turing thesis?
8 answers
71 votes
9k views
23 bookmarks
Are runtime bounds in P decidable? (answer: no)
13 answers
69 votes
8k views
52 bookmarks
Common false beliefs in theoretical computer science
7 answers
68 votes
4k views
31 bookmarks
Are $PSPACE$-complete problems inherently less tractable than $NP$-complete problems?
9 answers
57 votes
24k views
42 bookmarks
Explain P = NP problem to 10 year old
10 answers
56 votes
4k views
25 bookmarks
Provable statements about genetic algorithms
1 answers
53 votes
2k views
17 bookmarks
Is there a gap amplification type of result for the Graph Isomorphism Problem?
5 answers
47 votes
1k views
19 bookmarks
Are there Conservation Laws in Complexity Theory?
10 answers
44 votes
4k views
29 bookmarks
Kolmogorov complexity applications in computational complexity
22 answers
42 votes
5k views
28 bookmarks
What hierarchies and/or hierarchy theorems do you know?
5 answers
42 votes
1k views
11 bookmarks
The cozy neighborhoods of "P" and of "NP-hard"
2 answers
41 votes
2k views
9 bookmarks
Are the problems PRIMES, FACTORING known to be P-hard?
7 answers
41 votes
5k views
15 bookmarks
When does randomization speed up algorithms and it "shouldn't"?
7 answers
39 votes
7k views
18 bookmarks
What do we know about provably correct programs?
3 answers
37 votes
2k views
12 bookmarks
Techniques for showing that problem is in hardness "limbo"
3 answers
36 votes
2k views
11 bookmarks
NC = P consequences?
3 answers
36 votes
931 views
8 bookmarks
Why does randomness have stronger effect on reductions than on algorithms?
1 answers
35 votes
1k views
9 bookmarks
NP-Completeness of the decision problem for the generalized 15-puzzle
6 answers
34 votes
2k views
14 bookmarks
Why are so few natural candidates for NP-intermediate status?
7 answers
32 votes
10k views
25 bookmarks
Should we consider $\mathsf{P} \neq \mathsf{NP}$ a law of nature?
19 answers
31 votes
8k views
26 bookmarks
Beautiful results in TCS
4 answers
31 votes
4k views
9 bookmarks
Does a noisy version of Conway's game of life support universal computation?
3 answers
31 votes
3k views
10 bookmarks
coNP certificate for Graph Isomorphism
10 answers
30 votes
1k views
15 bookmarks
Current parallel models for computation
3 answers
30 votes
2k views
7 bookmarks
How many instances of 3-SAT are satisfiable?