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

Ask Question

more tags

Active Hot Week Month

3

votes

0

answers

60

views

Problem in the paper “Stable Minimum Space Partitioning in Linear Time”

ds.algorithms space-complexity

modified 2 days ago Emil Jeřábek 13.4k

120

votes

18

answers

9k

views

Examples of the price of abstraction?

ds.algorithms reference-request big-list lower-bounds

modified 2 days ago Oliphaunt - reinstate Monica 111

43

votes

6

answers

19k

views

Complexity of the simplex algorithm

ds.algorithms linear-programming simplex smoothed-analysis

answered Jul 26 at 17:18 learnPyt 1

57

votes

6

answers

3k

views

Theoretical explanations for practical success of SAT solvers?

cc.complexity-theory ds.algorithms sat big-picture heuristics

modified Jul 18 at 9:54 Claude Chaunier 101

1

vote

0

answers

70

views

Parametrization of context-sensitive language in polynomial time

cc.complexity-theory ds.algorithms fl.formal-languages

modified Jul 6 at 9:03 deryll 11

2

votes

2

answers

709

views

Difference between PRAM and machine model in dynamic multithreading

ds.algorithms

modified Jun 27 at 21:09 Magnus Lie Hetland 1,500

2

votes

0

answers

142

views

Theorem on non-decreasing probability of success of an algorithm

ds.algorithms pr.probability

modified Jun 23 at 14:44 fgrieu 109

0

votes

1

answer

51

views

How to build the tree with the “most different” solutions of a clustering?

ds.algorithms ds.data-structures clustering

modified Jun 22 at 20:41 Vincent 109

9

votes

3

answers

226

views

Sublinear Time Regular Expression Search

ds.algorithms ds.data-structures

modified Jun 22 at 11:18 xavierm02 521

1

vote

0

answers

136

views

Triangle detection hardness in regular graphs

ds.algorithms np-hardness lower-bounds

modified Jun 9 at 5:20 domotorp 13.2k

1

vote

2

answers

164

views

Finding the point that maximizes a linear function

ds.algorithms optimization ds.data-structures

modified May 30 at 10:37 Inuyasha Yagami 1,258

2

votes

1

answer

119

views

Do there exist two equivalent objective functions one of which can be approximated but another one cannot?

ds.algorithms co.combinatorics approximation-algorithms approximation-hardness integer-programming

modified May 28 at 19:10 Neal Young 6,972

3

votes

1

answer

337

views

How hard is this combinatorial optimisation problem?

ds.algorithms np-hardness co.combinatorics integer-programming proofs

modified May 21 at 8:41 Mikhail Rudoy 2,708

4

votes

0

answers

79

views

Flipping one bit to maximize BMM output

ds.algorithms graph-algorithms matrix-product

modified May 18 at 17:53 karmanaut 1,035

Browse more Questions

Theoretical Computer Science Stack Exchange works best with JavaScript enabled