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

-1

votes

0

answers

8

views

What is the formal definition of a data structure?

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

modified 3 hours ago Guest 1

1

vote

1

answer

136

views

Potentially stronger form of non-$ETH$

ds.algorithms sat

modified Jan 13 at 2:01 Community♦ 1

-1

votes

0

answers

43

views

Parallel Tractability

ds.algorithms complexity-classes dc.parallel-comp

modified Jan 9 at 4:36 Ar1Bis 1

3

votes

1

answer

127

views

Convex polygons inclusion relation

ds.algorithms computational-geometry polygon convex-hull

modified Jan 8 at 20:16 David Eppstein 47.5k

18

votes

3

answers

480

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

79

views

Isomorphic subforest problem

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

modified Jan 3 at 2:39 Zachary Hunter 315

15

votes

3

answers

1k

views

Checking formulas with two quantifiers ($\forall \exists$) - 2QBF

ds.algorithms lo.logic sat boolean-functions

modified Jan 1 at 18:42 Pushpa 209

13

votes

2

answers

857

views

NP-hard problems with very fast exponential-time algorithms

ds.algorithms reference-request exp-time-algorithms

modified Dec 31 '19 at 2:43 Neal Young 4,888

4

votes

1

answer

754

views

Knapsack with dependent profits (pairs of items)

ds.algorithms optimization

modified Dec 30 '19 at 10:00 Community♦ 1

6

votes

2

answers

675

views

Complexity of transforming a balanced bipartite graph into regular graph?

ds.algorithms reference-request graph-algorithms

modified Dec 14 '19 at 17:55 Mohammad Al-Turkistany 19.5k

2

votes

0

answers

96

views

Matrix multiplication when one matrix is fixed

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

modified Dec 9 '19 at 1:16 T.... 10.8k

6

votes

1

answer

215

views

What is the fastest known algorithm for computing a 1.99-approximation of Vertex Cover?

ds.algorithms graph-algorithms approximation-algorithms exp-time-algorithms

modified Dec 6 '19 at 1:25 R B 9,025

9

votes

0

answers

128

views

What are some examples of algorithmic applications of noncommutative rational identity testing?

cc.complexity-theory ds.algorithms graph-algorithms polynomials algebraic-complexity

modified Dec 2 '19 at 17:21 Naysh 223

3

votes

3

answers

1k

views

Is it possible to generate a collision free hash function from an equality function?

ds.algorithms functional-programming hash-function

modified Nov 27 '19 at 16:32 Radu GRIGore 4,531

Browse more Questions

Theoretical Computer Science Stack Exchange works best with JavaScript enabled