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

8 votes
1 answer
1k views

Are there survey papers in theoretical computer science?

6 votes
2 answers
225 views

How to show that the median cannot be maintained in $O(1)$ time?

1 vote
1 answer
206 views

Are there 'poision-pill' research questions in TCS?

13 votes
0 answers
474 views

New quantum algorithm for approximating permanent

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, ...$

5 votes
1 answer
158 views

Establishing competing memory limits for pushdown automata

3 votes
1 answer
192 views

Does double majoring with math in undergrad help one grasp TCS topics more easier?

2 votes
1 answer
183 views

Upper bound for VCdim of $H$ in terms of subgraph$(F)$, where $H := \{S(f) | f \in F\}$, with $S(f) := \{(x,y) \in X \times \{\pm 1\} | yf(x) \le 1\}$

1 vote
2 answers
105 views

How to find the size of an ϵ-net of a vector space?

2 votes
1 answer
125 views

Complexity of the Complete (3,2) SAT problem?

3 votes
1 answer
153 views

Complexity of matrix diagonalization

4 votes
1 answer
107 views

What are the application of Scott-Topology in theoretical computer science?

6 votes
0 answers
115 views

Computing permanents when we are promised that the value of the permanent is large

0 votes
1 answer
68 views

Can you always throw away the types when evaluating lambda expressions?

-3 votes
0 answers
130 views

For VCP and fixed value k, what's the result if we prove optimal value > (n/2)+(n/k) or we can produce a feasible objective value < (kn)/(k+1)?

3 votes
1 answer
77 views

$\mathrm{AC}^0$ upper bound for Hamming weight

3 votes
0 answers
123 views

Nested dissection for singular matrices

2 votes
1 answer
123 views

Sample complexity lower bound to learn the mode (the value with the highest probability) of a distribution with finite support

1 vote
0 answers
104 views

proof that 2-SAT is P-hard [closed]

4 votes
1 answer
77 views

Tensor network contraction "bubbling": why are some approaches more computationally efficient than others (question from a beginner)

5 votes
0 answers
74 views

Complexity of approximating boolean functions with circuits

0 votes
0 answers
87 views

Separation oracle for breaking cycles in directed graph

2 votes
0 answers
84 views

Natural proofs and size of propositional formulas

0 votes
0 answers
75 views

Does NP-completeness in one graph class imply not NP-intermediate in another graph class?

2 votes
0 answers
75 views

Nondeterministic polynomial time languages with linearly bounded certificates

2 votes
0 answers
73 views

Reference for complete problems for $FNP^{NP}$

0 votes
0 answers
71 views

Complexity of the distance between the average vector of two subsets

1 vote
1 answer
43 views

Operations on Sentential Decision Diagrams

0 votes
1 answer
53 views

Parameterized complexity of Hitting Set with slightly bigger parameter

0 votes
0 answers
64 views

Simplify or bound using Big-O notation

4 votes
0 answers
63 views

Are there classes for that FO-model checking is FPT on hypergraphs?

2 votes
0 answers
59 views

Does advice reduce depth?

0 votes
0 answers
59 views

Vidick's proof of parallel DI-QKD

2 votes
0 answers
57 views

Is k-ACYCLIC COLOURABLITY in CSP?

-2 votes
0 answers
56 views

VC-dimension of an infinite set of functions

2 votes
0 answers
55 views

From formal models to programs - Model Checking

3 votes
0 answers
55 views

Is there a standard way to "point" at subterms in a lambda expression?

0 votes
0 answers
54 views

Algorithms with advices of huge precomputed data

1 vote
1 answer
41 views

CFG - How can I describe a language that dictates a word and its opposite?

1 vote
0 answers
52 views

Code indistinguishability assumption for Code based cryptography (in special cases)

0 votes
0 answers
51 views

Does the the equivalence of Total variation distance formulas assumes that the two distributions are symmetrical?

0 votes
0 answers
49 views

Short UNSAT Certificates for X3SAT

2 votes
0 answers
48 views

Pebble games and conversions to bounded width circuits

1 vote
0 answers
47 views

Cheapest Insertion is $2$-approximation for TSP

-1 votes
0 answers
47 views

How to prove a problem does not have an approximation algorithm?

0 votes
0 answers
46 views

Converting a rational star-connected expression to an NFA

0 votes
0 answers
46 views

Are there more learnable but undecidable cases except the halting problem


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