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

15 votes
0 answers
222 views

Can we do integer addition in linear time?

19 votes
12 answers
3k views

Is there any book on the philosophical implications of Theoretical Computer Science?

5 votes
1 answer
140 views

Stronger "induction" principles than induction-recursion

10 votes
2 answers
732 views

Functional Completeness of 3-valued logic

9 votes
1 answer
168 views

What is known about reduction by "$P_1$ interprets $P_2$" for generalized programming languages?

3 votes
1 answer
123 views

Treewidth for hypergraphs that specify connectedness requirements

13 votes
1 answer
302 views

Is there a language of first-order logic such that every r.e. set is Turing-equivalent to some finitely axiomatizable theory in that language?

3 votes
0 answers
62 views

Exponential version of $CC^0$

3 votes
0 answers
67 views

Bounding the size of a power of a proper interval graph

85 votes
20 answers
10k views

Examples of "Unrelated" Mathematics Playing a Fundamental Role in TCS?

9 votes
1 answer
358 views

Metric graph theory database search algorithms

1 vote
2 answers
189 views

How much information does it take to specify, not each member of a group, but any one member?

3 votes
0 answers
88 views

Succinct problems over uniform computational models

12 votes
1 answer
340 views

A super-linear time problem in NL

Browse more Questions