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 1 Bountied Hot Week Month

0

votes

0

answers

5

views

Is part of Lamport and Lynch's chapter on Distributed Computing (1989) out-dated?

reference-request dc.distributed-comp concurrency

asked 32 mins ago Tim 558

0

votes

0

answers

7

views

How to reduce k-IS instance to SAT formula

cc.complexity-theory reductions

asked 1 hour ago Beck38 1

1

vote

1

answer

46

views

Minimizing $L_2$ norm of a vector with two distinct entries

ds.algorithms cg.comp-geom

modified 3 hours ago Emil Jeřábek 12.1k

6

votes

1

answer

220

views

Time complexity for a variant of edit distance

ds.algorithms edit-distance

answered 4 hours ago Mikhail Rudoy 2,513

-1

votes

0

answers

15

views

Implement circular queue with stacks

ds.algorithms ds.data-structures queueing-theory

asked 4 hours ago ErroR 1

0

votes

0

answers

19

views

PKP Variant with some restrictions

decidability

asked 17 hours ago Erkan Turan 19

1

vote

0

answers

23

views

Post Correspondence Problem number of a's and b's correspondence variant

decidability

asked 18 hours ago Erkan Turan 19

0

votes

0

answers

24

views

Are generalized map involutions captured by GNN?

graph-theory computational-geometry

modified yesterday sAguinaga 101

4

votes

1

answer

85

views

Does replacing each vertex of $G$ by $H$ increase treewidth of $G$ by at most $\Delta(G)$?

graph-theory treewidth

answered yesterday Laakeri 1,014

2

votes

1

answer

81

views

CNF encoding of set cover - NExpTime-completness

complexity set-cover nexp succinct

answered yesterday Jean-Francois Raskin 21

1

vote

0

answers

46

views

Cover Time of Random Walks with Backtracking on Directed Graphs

randomized-algorithms random-walks

modified yesterday Springberg 556

5

votes

0

answers

43

views

Inferring the Kolmogorov complexity of a string from its substrings' complexity

co.combinatorics kolmogorov-complexity

modified yesterday Aryeh 8,709

1

vote

2

answers

83

views

Can concurrency models be compared in terms of some metrics?

reference-request pl.programming-languages dc.distributed-comp advice-request concurrency

modified yesterday Soleil - Mathieu Prévot 109

1

vote

0

answers

23

views

“Parity testing set” for disjoint pairs of sets

reference-request co.combinatorics extremal-combinatorics

asked 2 days ago Magnus Wahlström 781

Browse more Questions

Theoretical Computer Science Stack Exchange works best with JavaScript enabled