User Ian - Theoretical Computer Science Stack Exchange

Ian

Member for 13 years, 1 month
Last seen more than 12 years ago

14 Answers

Score Activity Newest

33 votes

The importance of Integrality Gap

answered Aug 23, 2010 at 9:08

25 votes

Can a computer simulate itself as part of a simulated world?

answered Nov 12, 2010 at 9:01

22 votes

Accepted

Is APX contained in NP?

answered Aug 19, 2010 at 5:11

18 votes

Kolmogorov complexity applications in computational complexity

answered Aug 19, 2010 at 0:41

17 votes

Are there alternatives to using polynomials in defining the different notions of efficient computation?

answered Aug 24, 2010 at 23:42

17 votes

Accepted

The structure of pathological instances for simplex algorithms

answered Oct 27, 2010 at 6:37

15 votes

what is easy for minor-excluded graphs?

answered Oct 23, 2010 at 6:11

12 votes

Truly random number generator: Turing computable?

answered Sep 13, 2010 at 21:20

10 votes

Accepted

Properties of Random Directed Graphs with Fixed Out-Degree

answered Sep 13, 2010 at 20:48

10 votes

Are there NP-complete problems with polynomial expected time solutions?

answered Aug 25, 2010 at 3:58

9 votes

Have any generalizations of maximum weight matching been studied?

answered Aug 30, 2010 at 8:19

5 votes

Accepted

A relaxed Steiner Tree Problem

answered Sep 8, 2010 at 1:41

5 votes

Major conjectures used to prove complexity lower bounds?

answered Aug 26, 2010 at 20:42

2 votes

Accepted

Finding islands of vertices in a network of roads containing one-way streets

answered Oct 16, 2010 at 21:56