user avatar
user avatar
user avatar
usul
  • Member for 10 years, 6 months
  • Last seen this week
22 votes
Accepted

Did Alan Turing's student Robin Gandy assert that Charles Babbage had no notion of a universal computing machine?

22 votes
Accepted

Implications of proving NP=RP on complexity theory

20 votes

Examples of successful derandomization from BPP to P

19 votes
Accepted

Is it enough for linear program constraints to be satisfied in expectation?

18 votes
Accepted

Is BPP vs. P a real problem after we know BPP lies in P/poly?

16 votes

Suppose $\mathbf{P} = \mathbf{BQP}$. Then what is randomness? Would it even exist at all?

16 votes
Accepted

Are vertex colourings--in a sense--edge colourings?

15 votes
Accepted

What is a natural problem in theory of computation?

14 votes
Accepted

White elephant gift exchanges: mechanisms for fair division

13 votes
Accepted

Why economists should care about computational complexity

13 votes

Does Memcomputing really solve an NP-complete problem?

12 votes

What is theoretical computer science?

12 votes

Arguments for/against Kolmogorov's conjecture about the circuit complexity of P

12 votes
Accepted

if I were to define a new complexity class how should I start?

10 votes
Accepted

Can limit of hard languages be easy?

10 votes

Is there a non-deterministic version of the complexity class PP?

10 votes
Accepted

What's the complexity of counting odd nodes in graph?

10 votes

Misunderstanding the Church-Turing thesis?

10 votes
Accepted

Find research partner (profession and beginner)

9 votes

Why exactly are complexity theorists interested in closed timelike curves?

9 votes

Using Kolmogorov complexity as input "size"

8 votes

Sum of products of all combinations?

8 votes

Candidates for One-Way Function

8 votes
Accepted

How to be formal while writing papers?

7 votes
Accepted

When studying the computational complexity of functions $\{0, 1\}^\ast \to \{0, 1\}^\ast$, is it enough to restrict to $\{0, 1\}^\ast \to \{0, 1\}$?

7 votes

Collection of failed attempts to solve X

7 votes
Accepted

Would a proof assuming a physical law be considered sufficient?

7 votes

How much would a SAT oracle help speeding up polynomial time algorithms?

7 votes

Examples of $\Sigma_2^p$ complete problems?

7 votes

Searching for the first item satisfying property with penalty for every test