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

0

answers

33

views

Structural normalization algorithm for the simply typed lambda calculus

reference-request type-theory lambda-calculus

asked 8 hours ago Couchy 113

0

votes

0

answers

12

views

VC generalization bound extended to other types of target functions

machine-learning vc-dimension

asked 10 hours ago ste 101

0

votes

0

answers

32

views

Packing non-rotatable arbitrary rectangles into a large rectangle of fixed size

optimization packing

modified 11 hours ago Elardus 1

9

votes

2

answers

6k

views

How can I find the second cheapest spanning tree?

graph-algorithms tree

modified 14 hours ago Jan Johannsen 4,479

2

votes

1

answer

51

views

Complexity of Unknotting problems

reference-request ct.category-theory

answered 17 hours ago Denis 6,595

2

votes

0

answers

34

views

Hessian of non differentiable convex function

reference-request approximation-algorithms convex-optimization

modified 21 hours ago Sudipta Roy 143

6

votes

3

answers

292

views

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

counting-complexity

answered yesterday Giorgio Camerani 6,489

3

votes

0

answers

28

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 yesterday R B 9,204

30

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 yesterday Joe Boy 71

9

votes

2

answers

791

views

Fastest known deterministic algorithm for the undirected Graph Isomorphism problem

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

modified yesterday Emil Jeřábek 12.7k

6

votes

1

answer

238

views

Reducing #SAT to MAJ-SAT

np

modified yesterday 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

0

votes

0

answers

16

views

are there approximation algorithms that use primal-dual with LP values and/or rounding?

co.combinatorics approximation-algorithms linear-programming primal-dual iterated-rounding

modified 2 days ago Hao S 189

1

vote

0

answers

52

views

Quantum complexity of TQBF with an untrusted oracle

quantum-computing interactive-proofs pspace

modified 2 days ago Geoffrey Irving 3,054

Browse more Questions

Theoretical Computer Science Stack Exchange works best with JavaScript enabled