Theoretical Computer Science Stack Exchange is a question and answer site for theoretical computer scientists and researchers in related fields. It only takes a minute to sign up.

Sign up to join this community
Anybody can ask a question
Anybody can answer
The best answers are voted up and rise to the top

Explore our questions

4 votes
1 answer
138 views

Fast algorithms for time bounded Kolmogorov complexity

0 votes
0 answers
36 views

Do pseudo-random number generator test batteries have any theoretical grounding?

36 votes
7 answers
8k views

What's the simplest noncontroversial 2-state universal Turing machine?

1 vote
1 answer
75 views

Approximating the utilitarian welfare minus a constant

0 votes
1 answer
196 views

Is it known that P $\neq$ NP implies BQP $\neq$ NP?

5 votes
0 answers
65 views

Certifying the promise in hard promise problems

-1 votes
0 answers
46 views

Introduction to complexity calculation

2 votes
0 answers
41 views

Why is showing lower bounds for AM communication complexity difficult?

3 votes
1 answer
118 views

is SUBEXP contained within PSPACE?, NP?

55 votes
11 answers
16k views

Recent advances in computer science since 2010?

3 votes
0 answers
52 views

FPRAS to estimate the probability to get a cyclic subgraph of a directed graph

3 votes
1 answer
317 views

Dynamic transitive closure with immediate new reachability facts

3 votes
1 answer
70 views

Assignment problem for forming pairs of real numbers

1 vote
0 answers
59 views

Equivalence between GNFA and NFA/DFA

Browse more Questions