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

more tags

Active Hot Week Month

19

votes

2

answers

1k

views

Can we decide whether a permanent has a unique term?

cc.complexity-theory ds.algorithms matrices matching permanent

modified Feb 14 at 2:58 Neal Young 5,038

8

votes

0

answers

108

views

Is Gödel's speed-up theorem an instance of Blum's speedup theorem?

ds.algorithms speed-up

modified Feb 11 at 12:08 Arnaud Casteigts 192

0

votes

1

answer

110

views

Is it possible to sort by only knowing the sign of pairwise sums?

cc.complexity-theory ds.algorithms sorting

answered Feb 9 at 14:21 Dale 91

15

votes

2

answers

4k

views

What is the fastest algorithm to compute rank of a rectangular matrix?

ds.algorithms reference-request time-complexity linear-algebra matrices

modified Feb 6 at 1:12 Ainesh Bakshi 119

0

votes

0

answers

15

views

Why is it more efficient to merge larger runs higher in the tree than perform a balanced tree of merges in an unbalanced ping-pong merge?

ds.algorithms sorting db.databases

asked Feb 5 at 16:01 Aviral Srivastava 117

-1

votes

0

answers

47

views

Fastest way for boolean matrix computations

cc.complexity-theory ds.algorithms co.combinatorics complexity-classes time-complexity

asked Feb 4 at 14:08 Franc W 17

9

votes

5

answers

412

views

W[1]-hard problems with FPT time approximation algorithms

ds.algorithms approximation-algorithms parameterized-complexity fixed-parameter-tractable

modified Jan 29 at 17:06 Amir Nikabadi 51

3

votes

1

answer

315

views

Best parameterized algorithm for maximum clique

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

answered Jan 27 at 8:06 Laakeri 628

1

vote

1

answer

198

views

Potentially stronger form of non-$ETH$

ds.algorithms sat

modified Jan 26 at 16:55 narek Bojikian 211

2

votes

0

answers

42

views

Time Complexity for Nearest Neighbor Searches in kd-trees

ds.algorithms ds.data-structures cg.comp-geom near-neighbors

asked Jan 25 at 15:51 user1494080 121

-1

votes

0

answers

67

views

What is the formal definition of a data structure?

ds.algorithms ds.data-structures turing-machines formal-modeling definitions

modified Jan 18 at 7:48 Guest 19

3

votes

1

answer

133

views

Convex polygons inclusion relation

ds.algorithms computational-geometry polygon convex-hull

modified Jan 8 at 20:16 David Eppstein 47.7k

18

votes

3

answers

520

views

Examples of the value of proofs for algorithms

ds.algorithms proofs teaching

modified Jan 3 at 18:48 Hermann Gruber 4,299

3

votes

0

answers

87

views

Isomorphic subforest problem

cc.complexity-theory ds.algorithms reference-request graph-theory

modified Jan 3 at 2:39 Zachary Hunter 315

Browse more Questions

Theoretical Computer Science Stack Exchange works best with JavaScript enabled