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

-1 votes
1 answer
46 views

Flow of value lower bounded by $X$

1 vote
2 answers
66 views

Examples of promise search problems that are easier than their non-promise variants?

2 votes
0 answers
112 views

Open problem on *Finite Memory Clocks* by Tom Cover

1 vote
0 answers
77 views

Is there a better-than-brute-force algorithm for finding a largest subrelation that is a non-strict partial order?

-1 votes
1 answer
100 views

Need more explaination on this 'generality'

0 votes
0 answers
96 views

In the Schönhage-Strassen algorithm for integer multiplication, when we calculate the product of two n-bit integers, why do we do so modulo 2^n + 1?

39 votes
9 answers
4k views

Efficient and simple randomized algorithms where determinism is difficult

4 votes
1 answer
1k views

Knapsack with dependent profits (pairs of items)

1 vote
0 answers
42 views

Are there good analogues to Sparsest Cut/Balanced cut for vertex separators instead of edges cuts?

3 votes
1 answer
135 views

Do Knuth-Morris-Pratt and Booth’s LCS algorithm work in linear time on lists of lists of integers?

1 vote
1 answer
91 views

Do reasonably competitive 3SAT algorithms ever have shrinking run-time distributions when measured as a probability density function?

2 votes
0 answers
74 views

Finding Hamilton cycles in random graphs

10 votes
3 answers
968 views

Choosing random permutations in "strict" polynomial time

3 votes
0 answers
79 views

Linear time in-place stable sort

Browse more Questions