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

1

vote

0

answers

25

views

Complexity of Set Difference

ds.algorithms ds.data-structures time-complexity

asked 21 hours ago tamalet 11

6

votes

2

answers

184

views

3SUM Complexity—A special(?) Case

cc.complexity-theory ds.algorithms time-complexity

answered Jul 12 at 1:25 Gary Hoppenworth 31

3

votes

2

answers

441

views

Optimization Problem on a Directed Graph

ds.algorithms graph-algorithms optimization

modified Jul 12 at 1:04 Community♦ 1

6

votes

2

answers

364

views

Implication of solving 3SUM problem of a certain size on the Exponential Time Hypothesis

cc.complexity-theory ds.algorithms time-complexity

answered Jul 11 at 15:44 Avi Tal 1,074

1

vote

1

answer

131

views

What is the complexity of this submatrix selection problem?

ds.algorithms linear-algebra

modified Jul 6 at 12:52 Neal Young 6,025

0

votes

1

answer

71

views

Minimizing the gaps with incremental capacity

ds.algorithms np-hardness dynamic-programming

modified Jul 6 at 2:56 Neal Young 6,025

-1

votes

1

answer

94

views

Required sample size to hit certain subset of a ground set

ds.algorithms pr.probability randomized-algorithms

modified Jun 30 at 19:02 Community♦ 1

0

votes

0

answers

180

views

Add edges to a DAG to maximize increase in number of connected vertices

ds.algorithms

modified Jun 21 at 11:17 A_Theory 45

2

votes

0

answers

63

views

Is there a fast algorithm for computing the Schmidt decomposition

ds.algorithms matrices

asked Jun 17 at 19:29 Juan 21

9

votes

2

answers

3k

views

What are good approximation algorithms for the subset sum problem so far?

ds.algorithms np-hardness approximation-algorithms approximation-hardness subset-sum

answered Jun 16 at 18:18 dohmatob 151

79

votes

2

answers

25k

views

What is the actual time complexity of Gaussian elimination?

cc.complexity-theory ds.algorithms reference-request linear-algebra

modified Jun 16 at 13:40 auspicious99 111

-1

votes

0

answers

33

views

Application of a Poisson inequality in the networks

ds.algorithms approximation-algorithms network-modeling

asked Jun 14 at 15:10 user124297 139

3

votes

3

answers

439

views

Best parameterized algorithm for maximum clique

ds.algorithms reference-request np-hardness fixed-parameter-tractable

answered Jun 5 at 20:33 Christian Komusiewicz 866

Browse more Questions

Theoretical Computer Science Stack Exchange works best with JavaScript enabled