Stack Exchange

Ian

top accounts reputation activity subscriptions

Top Questions

Consequences of existence of a strongly polynomial algorithm for linear programming?

ds.algorithms conditional-results linear-programming computing-over-reals simplex asked Oct 13, 2010 at 1:13

cstheory.stackexchange.com

Bounds on $E[f(x)]$ in terms of $f(E[x])$ other than Jensen's inequality?

randomness pr.probability randomized-algorithms asked Aug 27, 2010 at 18:45

cstheory.stackexchange.com

Alternate notion of complexity based on gap between brute-force and the best algorithm?

cc.complexity-theory asked Aug 19, 2010 at 20:26

cstheory.stackexchange.com

Top Answers

The importance of Integrality Gap

cstheory.stackexchange.com

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

cstheory.stackexchange.com

Is APX contained in NP?

cstheory.stackexchange.com

Kolmogorov complexity applications in computational complexity

cstheory.stackexchange.com

The structure of pathological instances for simplex algorithms

cstheory.stackexchange.com

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

cstheory.stackexchange.com

what is easy for minor-excluded graphs?

cstheory.stackexchange.com

Truly random number generator: Turing computable?

cstheory.stackexchange.com

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

cstheory.stackexchange.com

Properties of Random Directed Graphs with Fixed Out-Degree

cstheory.stackexchange.com

Have any generalizations of maximum weight matching been studied?

cstheory.stackexchange.com

Major conjectures used to prove complexity lower bounds?

cstheory.stackexchange.com

A relaxed Steiner Tree Problem

cstheory.stackexchange.com