Theoretical Computer Science Stack Exchange

-1 votes

1 answer

46 views

Flow of value lower bounded by $X$

J..y B..y

2,570

answered Sep 12 at 11:22

1 vote

2 answers

66 views

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

Emil Jeřábek

14.9k

answered Sep 11 at 8:42

2 votes

0 answers

112 views

Open problem on Finite Memory Clocks by Tom Cover

Simone Borghi

1

modified Aug 31 at 7:19

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?

Galen

111

modified Aug 26 at 13:58

-1 votes

1 answer

100 views

Need more explaination on this 'generality'

J..y B..y

2,570

answered Aug 22 at 11:47

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?

Martin Berger

10.4k

modified Aug 22 at 9:32

39 votes

9 answers

4k views

Efficient and simple randomized algorithms where determinism is difficult

Mohammad Al-Turkistany

20.6k

answered Aug 18 at 17:05

4 votes

1 answer

1k views

Knapsack with dependent profits (pairs of items)

CommunityBot

1

modified Aug 16 at 15:06

1 vote

0 answers

42 views

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

Julien Codsi

11

modified Aug 15 at 13:55

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?

David Eppstein

50.3k

answered Aug 10 at 19:31

1 vote

1 answer

91 views

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

CommunityBot

1

modified Aug 10 at 19:04

2 votes

0 answers

74 views

Finding Hamilton cycles in random graphs

Dmytro Taranovsky

2,362

modified Jul 29 at 16:51

10 votes

3 answers

968 views

Choosing random permutations in "strict" polynomial time

Glorfindel

323

modified Jul 24 at 13:36

3 votes

0 answers

79 views

Linear time in-place stable sort

Dmytro Taranovsky

2,362

asked Jul 20 at 13:55

Stack Exchange Network

Explore our questions

Flow of value lower bounded by $X$

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

Open problem on Finite Memory Clocks by Tom Cover

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

Need more explaination on this 'generality'

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?

Efficient and simple randomized algorithms where determinism is difficult

Knapsack with dependent profits (pairs of items)

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

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

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

Finding Hamilton cycles in random graphs

Choosing random permutations in "strict" polynomial time

Linear time in-place stable sort

Hot Network Questions