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

1

vote

1

answer

18

views

Decomposition of safety and liveness properties

automata-theory linear-temporal-logic omega-language

answered 8 mins ago Shaull 4,258

2

votes

3

answers

3k

views

Difference between self-information and entropy

it.information-theory shannon-entropy

modified 53 mins ago kraka 1

0

votes

0

answers

4

views

Partition vertices of graph into two sets such that there are at least $k$ edges between sets

np-hardness max-cut

asked 2 hours ago Majstro 1

3

votes

1

answer

53

views

Structural normalization algorithm for the simply typed lambda calculus

reference-request type-theory lambda-calculus

answered 3 hours ago Stefan 257

0

votes

0

answers

13

views

VC generalization bound extended to other types of target functions

machine-learning vc-dimension

asked yesterday ste 101

9

votes

2

answers

6k

views

How can I find the second cheapest spanning tree?

graph-algorithms tree

modified yesterday Jan Johannsen 4,479

2

votes

1

answer

66

views

Complexity of Unknotting problems

reference-request ct.category-theory

answered yesterday Denis 6,615

2

votes

0

answers

36

views

Hessian of non differentiable convex function

reference-request approximation-algorithms convex-optimization

modified yesterday Sudipta Roy 143

6

votes

3

answers

295

views

$⊕P$-completeness of $⊕2SAT$

counting-complexity

answered yesterday Giorgio Camerani 6,489

4

votes

0

answers

36

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

asked 2 days ago R B 9,214

31

votes

12

answers

4k

views

Problems that started out with hopelessly intractable algorithms that have since been made extremely efficient

cc.complexity-theory ho.history-overview exp-time-algorithms

answered 2 days ago Joe Boy 71

9

votes

2

answers

794

views

Fastest known deterministic algorithm for the undirected Graph Isomorphism problem

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

modified 2 days ago Emil Jeřábek 12.7k

6

votes

1

answer

239

views

Reducing #SAT to MAJ-SAT

np

modified 2 days ago Mostowski Collapse 161

6

votes

1

answer

75

views

“Interesting” categories whose internal logic is a dependent-linear type theory

type-theory ct.category-theory dependent-type

modified 2 days ago Neel Krishnaswami 30.3k

Browse more Questions

Theoretical Computer Science Stack Exchange works best with JavaScript enabled