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

2 votes
1 answer
163 views

Maximize a special monotone submodular function - is it easier?

2 votes
2 answers
145 views

Seeking references on writing a long string $\ell$ as concatenation of shorter strings $s_1, s_2, s_3, ...$

1 vote
0 answers
40 views

Sorting multiple columns of a matrix

3 votes
1 answer
132 views

Maximal uniquely decodable codes

29 votes
2 answers
971 views

Polynomial method for complexity results

0 votes
0 answers
30 views

Multi-dimensional 0-1 Knapsack problem with a high number of dimensions

0 votes
0 answers
27 views

A question regarding the proof of Lévy–Steinitz theorem

12 votes
2 answers
3k views

Find all pairs of values that are close under Hamming distance

19 votes
2 answers
863 views

Axioms for Shortest Paths

0 votes
1 answer
87 views

On structure of graphs with average degree equal to maximum average degree

25 votes
6 answers
2k views

Graph families which have polynomial time algorithms for computing the chromatic number

25 votes
5 answers
9k views

What is the maximum number of stable marriages for an instance of the Stable Marriage Problem?

1 vote
0 answers
51 views

On Negami's planar cover cojecture

2 votes
0 answers
64 views

Does the standard 4/3 integrality gap for TSP example work for Euclidean TSP?

Browse more Questions