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
20 views

Randomized communication complexity of or-of-equalities

0 votes
0 answers
31 views

Partial linear spaces and partial projective planes

3 votes
1 answer
104 views

Do Knuth-Morris-Pratt and Booth’s LCS algorithm work in linear time on lists of lists of integers?

1 vote
1 answer
72 views

Do reasonably competitive 3SAT algorithms ever have shrinking run-time distributions when measured as a probability density function?

-1 votes
0 answers
41 views

Are there any unary algorithms that are really faster than binary ones?

0 votes
1 answer
59 views

Can one find any solution to this matrix problem in polynomial time?

0 votes
1 answer
162 views

Solving 3-SAT in O(n^6)?

2 votes
1 answer
67 views

Regularity Lemma for Multi-Relational Graphs?

3 votes
0 answers
65 views

What is the intuition behind P/qpoly=P/poly?

4 votes
0 answers
118 views
+400

Context Free Grammar For Complement Of { wwwww | ... } With Minimal Locality?

1 vote
0 answers
45 views

Why Multiple Clocks in Guarded Dependent Type Theories?

-1 votes
1 answer
60 views

Parameters: Twin cover and Vertex cover

-2 votes
0 answers
22 views

Comparing objects

0 votes
1 answer
104 views

Information theoretic arguments for complexity

Browse more Questions