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

Top Questions

5 votes
2 answers
233 views

Find odd-ranked numbers from a list

0 votes
1 answer
25 views

Formulation of Tarski-style universes in LF

3 votes
1 answer
30 views

Is there an established name for this kind of upper bound?

1 vote
0 answers
19 views

Examples for Real-time vs Linear time

4 votes
1 answer
388 views

Is classical lambda calculus grammar an `LL(k)` one?

1 vote
0 answers
25 views

Maximum degree of the Sum of Squares certificate of a non-negative degree d polynomial on the boolean hypercube

2 votes
0 answers
41 views

Efficiently checking that points lie on a polynomial

0 votes
0 answers
51 views

$NP \subseteq PSPACE$ proof clarification on enumeration of all solutions

2 votes
0 answers
47 views

Why do some problems seem to admit a richer family of algorithms than others?

10 votes
12 answers
4k views

Theoretical Computer Science vs other Sciences?

1 vote
1 answer
87 views

Communication complexity of equality on graphs

0 votes
1 answer
49 views

Finding an $\epsilon$-concentrated collection with size in terms of spectral $1$-norm

1 vote
1 answer
52 views

If boolean function $f$ is computable by a k-CNF and an l-DNF then it can be computed by a decision tree of depth at most kl

1 vote
0 answers
45 views

Why does splitting $n$ bit integers into chunks of size $\log(n)$ specifically, help in multiplying them

7 votes
3 answers
903 views

Yet another constructive (Coq) proof that `nat -> nat -> nat` is not bijective. How to explain it to myself?

2 votes
1 answer
45 views

Balls in monochromatic bins

0 votes
0 answers
44 views

Learning Parities via Gradient Descent

0 votes
0 answers
25 views

Complexity of XOR-Knapsack

0 votes
0 answers
28 views

Reduction of Monotone-1-in-3-SAT to Cubic-Monotone-1-in-3-SAT

6 votes
0 answers
115 views

Consistent Sampling a Random Walk

-1 votes
0 answers
41 views

Probability of node being infected at time t=10 in SIR model

-2 votes
0 answers
56 views

Is every decidable language Turing-recognizable? Please read body for more details

2 votes
1 answer
89 views

doubt in the proof of reducing any arithmetic circuit to log(d) depth, where d is the degree of the polynomial it is computing

1 vote
3 answers
216 views

Turing Machines and Logic

0 votes
0 answers
104 views

Is it known that P $\neq$ NP implies BQP $\neq$ NP?

0 votes
0 answers
33 views

Why $Rank(C)< R(k,d)$ for Depth 3 Balckbox PIT Algorithm implies $C$ is zero

0 votes
1 answer
169 views

Construction of a collection of subsets of $\{1,2,\ldots,n\}$ with certain properties

9 votes
1 answer
372 views

Is it NP-hard to find an order on a set of strings so that the concatenation is a given string?

2 votes
0 answers
71 views

What kind of solver should I use for this hypergraph problem?

1 vote
0 answers
45 views

Is there a calculus or formalism for measuring set relations between algorithm outputs?

6 votes
0 answers
119 views

Consequences of $P^{NP[o(n)]} = P^{NP}$

4 votes
0 answers
69 views

Circuit computing Longest Increasing Sub-sequence (LIS)

3 votes
2 answers
144 views

Worst-case complexity of computing a certain non-standard dot product + algorithms realizing this complexity

3 votes
0 answers
36 views

Can you compute Shannon expansion of a Boolean formula more efficiently by using a QBF solver?

6 votes
0 answers
67 views

Cycle packing with degree condition

1 vote
0 answers
28 views

Non-uniform advice skews runtime

4 votes
0 answers
57 views

Equivalent Characterizations of Semilinear Sets

6 votes
0 answers
150 views

Are exponential lower bounds known against $MOD_6 \circ MOD_3$ circuits computing $OR$?

4 votes
2 answers
157 views

NP-hardness: (planar) directed feedback vertex set problem with bounded degree

1 vote
0 answers
251 views

Did I discover a new data structure?

0 votes
1 answer
54 views

Complexity of Exact Cover problem if containing a Set Cover means there is an Exact Cover

2 votes
0 answers
29 views

Tape reduction, tape compression and time compression

3 votes
1 answer
104 views

Complexity of sampling a clique uniformly at random

-1 votes
0 answers
40 views

Do modular exponentiation and extended GCD have any $Logspace$ relation between them?

4 votes
1 answer
161 views

A question about decision tree complexity

2 votes
0 answers
74 views

Extending fagin’s theorem for #P (for arbitary structure)

0 votes
0 answers
121 views

What's the connection between branchwidth and treewidth

9 votes
2 answers
208 views

Defining regular language classes with disjoint union


Looking for more? Browse the complete list of questions, or popular tags. Help us answer unanswered questions.