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

-1 votes
1 answer
59 views

Complexity of "opposite" version of a variant of #Positive-2-SAT

2 votes
0 answers
116 views

The $O(n^{1/r})$ upper bound of polynomial degree of OR over composite moduli

1 vote
2 answers
41 views

Is Maximum Independent Set polynomial-time solvable in $(p,1)$-colorable graphs for general $p$?

1 vote
1 answer
36 views

Are there pseudorandom sequences which cannot be learned by any ML model but which still fail the Diehard tests?

21 votes
0 answers
316 views

Can we do integer addition in linear time?

3 votes
1 answer
102 views

Most Matrices are Rigid

0 votes
0 answers
17 views

Linear modular equalities with $0/1$ solution

1 vote
0 answers
19 views

Bound on the treewidth of a graph from modular contraction

0 votes
1 answer
101 views

Formal differences between emulation and simulation?

0 votes
2 answers
118 views

How is runtime downcasting modeled in type theory?

0 votes
0 answers
33 views

Can the initial algebra of a 2-variable polynomial functor be computed on the diagonal?

0 votes
1 answer
139 views

An additive combinatoric probability question

3 votes
0 answers
84 views

How do we show directly coNP is in MIP?

0 votes
0 answers
56 views

Consequences of early-exiting BFS after reaching the target node in Dinic's algorithm

Browse more Questions