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

8

votes

0

answers

149

views

On $\text{ETH}$ with $m$ as parameter: consequences of algorithm running in time $2^{\delta m}$ where $\delta \to 0$ as $k \to \infty$

cc.complexity-theory ds.algorithms sat exp-time-algorithms

modified 1 hour ago Giorgio Camerani 6,449

8

votes

1

answer

3k

views

What's the approximation factor of this Max k-Cut approximation?

ds.algorithms graph-algorithms approximation-algorithms max-cut

modified yesterday Saeed 3,373

4

votes

0

answers

94

views

Time complexity for a variant of edit distance

ds.algorithms edit-distance

modified Nov 23 at 9:24 Marzio De Biasi 21.6k

2

votes

0

answers

88

views

$k$-XOR collision free families

ds.algorithms co.combinatorics combinatorics extremal-combinatorics

modified Nov 21 at 0:12 R B 9,176

42

votes

7

answers

14k

views

Complexity of Finding the Eigendecomposition of a Matrix

ds.algorithms time-complexity matrices linear-algebra na.numerical-analysis

answered Nov 17 at 21:13 nikhil srivastava 11

2

votes

0

answers

50

views

Can we always find a graph with a given algebraic connectivity?

ds.algorithms graph-theory graph-algorithms spectral-graph-theory

asked Nov 17 at 4:44 HallaSurvivor 121

1

vote

0

answers

30

views

Dynamic permutation cycle data

ds.algorithms graph-theory permutations online-algorithms

asked Nov 16 at 19:43 Timothy 111

0

votes

0

answers

61

views

An extension to the student/college admissions Gale-Shapley algorithm

ds.algorithms

asked Nov 9 at 11:49 RDavey 101

4

votes

2

answers

498

views

Optimization Problem on a Directed Graph

ds.algorithms graph-algorithms optimization

modified Nov 9 at 2:06 Community♦ 1

2

votes

0

answers

115

views

Finding nodes with enough unique ancestors

ds.algorithms graph-theory graph-algorithms directed-acyclic-graph

modified Nov 9 at 0:12 user1246462 61

4

votes

0

answers

78

views

Computing and maintaining the minimum of a set $S$ of integers while allowing updates on $S$

ds.algorithms reference-request lower-bounds sorting ram-model

asked Nov 8 at 13:39 Louis 340

1

vote

1

answer

58

views

Separating DAGs using separators consisting of lists of nodes and all ancestors

ds.algorithms graph-theory graph-algorithms ds.data-structures directed-acyclic-graph

answered Oct 26 at 6:49 daniello 3,071

27

votes

5

answers

4k

views

Counting words accepted by a regular grammar

ds.algorithms co.combinatorics fl.formal-languages regular-language

answered Oct 24 at 15:19 joro 1,905

1

vote

0

answers

36

views

Remove cycles from a stochastic comparison matrix, while doing the least amount of editing

ds.algorithms graph-theory graph-algorithms matrices dynamic-programming

modified Oct 21 at 16:53 dohmatob 225

Browse more Questions

Theoretical Computer Science Stack Exchange works best with JavaScript enabled