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

Finite automata that accept binary strings divisible by n

16 votes
Accepted

Is every busy beaver strictly monotonic asymptotically?

11 votes
Accepted

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

10 votes

Boolean as subtype of integer

10 votes
Accepted

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

10 votes

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

9 votes

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

9 votes

Why are NPI problems not all of the same complexity?

6 votes

Complexity of linear programming

6 votes

Using negative results to prove positive results in computability theory

5 votes

Programming languages for efficient computation

5 votes
Accepted

Solving a Min/Max equation set

4 votes

Many-one reductions vs. Turing reductions to define NPC

4 votes

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

4 votes

How to analyze a randomized recursive algorithm?

4 votes

Theoretical Applications for Approximation Algorithms

4 votes

Pairwise independent gaussians

4 votes

Advice for Graduate School in Computer Science

4 votes
Accepted

Is a turing machine with random number generator more powerful?

3 votes

Any Graph is a Model (! or ?)

3 votes

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

2 votes

Decision version of matrix multiplication problem

2 votes

Maximum Independent Set using Maximal MIS

2 votes

Example where equivalence is easy but finding class representative is hard

1 vote

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

1 vote

Decidability of transcendental numbers

1 vote

Upper bound of an optimization problem

1 vote

shortest path & max flow

0 votes

Learning with "taciturn" oracles

0 votes

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