user avatar
user avatar
user avatar
David Harris
  • Member for 11 years, 2 months
  • Last seen more than a month ago
11 votes
Accepted

Is there a randomized complexity class analogous to $\mathsf{P/Poly}$?

6 votes

Complexity of linear programming

2 votes

Decision version of matrix multiplication problem

3 votes

Find the remainder of a large fixed polynomial when divided by a small unknown polynomial

2 votes

Maximum Independent Set using Maximal MIS

4 votes
Accepted

Is a turing machine with random number generator more powerful?

2 votes

Example where equivalence is easy but finding class representative is hard

9 votes

Why are NPI problems not all of the same complexity?

1 vote

Decidability of transcendental numbers

32 votes
Accepted

Finite automata that accept binary strings divisible by n

4 votes

What are some problems where we know we have an optimal algorithm?

6 votes

Using negative results to prove positive results in computability theory

16 votes
Accepted

Is every busy beaver strictly monotonic asymptotically?

1 vote

Recursively enumerable, non-recursive language without using Gödel's number

4 votes

Advice for Graduate School in Computer Science

4 votes

Pairwise independent gaussians

4 votes

Theoretical Applications for Approximation Algorithms

4 votes

How to analyze a randomized recursive algorithm?

10 votes
Accepted

On the need for a self-correcting function in the PCP theorem

10 votes

Boolean as subtype of integer

1 vote

Upper bound of an optimization problem

5 votes

Programming languages for efficient computation

4 votes

Many-one reductions vs. Turing reductions to define NPC

9 votes

If an abstract machine can simulate itself, does that make it Turing complete?

10 votes

Graduate studies (PhD) in CS Theory vs. Applied Math

3 votes

Any Graph is a Model (! or ?)

1 vote

shortest path & max flow

5 votes
Accepted

Solving a Min/Max equation set

0 votes

is "spaghetti sort" really O(n) (even as a thought experiment) ?

0 votes

Learning with "taciturn" oracles