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

10

votes

1

answer

55

views

Is the exponent in the rectangular matrix multiplication convex?

ds.algorithms time-complexity matrix-product

modified 5 hours ago user2316602 409

0

votes

1

answer

53

views

Knapsack problem with dependent weight and profits among the items

ds.algorithms optimization

modified Feb 22 at 16:02 Community♦ 1

9

votes

1

answer

177

views

Is the Triangle Finding decision problem in $coNTIME(\tilde{O}(n^2))$?

cc.complexity-theory ds.algorithms graph-algorithms time-complexity nondeterminism

modified Feb 19 at 19:22 Michael Wehar 4,703

4

votes

1

answer

119

views

Is $GCT$ necessarily a negative result program?

cc.complexity-theory ds.algorithms big-picture algebraic-complexity symmetry

answered Feb 19 at 4:16 Joshua Grochow 34.1k

3

votes

2

answers

510

views

Algorithms for graph generation given parameters

ds.algorithms graph-theory graph-algorithms big-list

modified Feb 18 at 14:13 Matthieu Latapy 281

6

votes

2

answers

272

views

Is there a fast algorithm to quickly evaluate $a^{b^c}$ mod $n$?

ds.algorithms cr.crypto-security nt.number-theory comp-number-theory

modified Feb 16 at 18:34 Bhaskar13 29

10

votes

1

answer

297

views

Is subtractive dithering the optimal algorithm for sending a real number using one bit?

ds.algorithms approximation-algorithms it.information-theory coding-theory encoding

modified Feb 14 at 2:42 zeb 341

4

votes

2

answers

188

views

Is there a linear time algorithm for integer multiplication verification?

ds.algorithms randomized-algorithms

modified Feb 9 at 9:37 Bruno 4,330

-1

votes

0

answers

31

views

Nontrivial Time Complexity for Implicit Deep Copy

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

modified Feb 7 at 1:28 user61302 1

11

votes

1

answer

1k

views

Count $k$-hop neighborhood for every vertex

ds.algorithms graph-algorithms randomized-algorithms

modified Feb 1 at 23:03 Community♦ 1

36

votes

5

answers

2k

views

Integer multiplication when one integer is fixed

cc.complexity-theory ds.algorithms circuit-complexity algebraic-complexity arithmetic-circuits

modified Jan 26 at 5:40 1.. 11.7k

10

votes

0

answers

2k

views

Which algorithm can do a stable in-place binary partition with only O(N) moves?

ds.algorithms space-bounded

modified Jan 16 at 21:10 AShelly 201

2

votes

1

answer

137

views

Obtaining Sets of Ancestors Quickly in a Directed Acyclic Graphs

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

modified Jan 11 at 10:01 Community♦ 1

10

votes

4

answers

3k

views

Proof of Levenshtein distance

ds.algorithms proofs edit-distance

answered Jan 11 at 1:23 usul 6,664

Browse more Questions

Theoretical Computer Science Stack Exchange works best with JavaScript enabled