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

1 vote
0 answers
21 views

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

3 votes
0 answers
27 views

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

7 votes
1 answer
972 views

Are there survey papers in theoretical computer science?

0 votes
0 answers
29 views

Short UNSAT Certificates for X3SAT

0 votes
0 answers
39 views

Complexity of the distance between the average vector of two subsets

2 votes
0 answers
63 views

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

0 votes
0 answers
24 views

Direct fpt reduction from Weighted 3SAT to Weighted 2SAT

4 votes
0 answers
61 views

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

1 vote
1 answer
35 views

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

0 votes
0 answers
41 views

Did anyone ever adapted TCS data structure results (e.g. vEB trees) into Governance structures?

-3 votes
0 answers
121 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)?

0 votes
0 answers
31 views

Defining a process without internal events

2 votes
1 answer
120 views

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

3 votes
1 answer
181 views

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

6 votes
0 answers
101 views

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

0 votes
0 answers
39 views

Perfect simulation of classical dynamical systems

0 votes
0 answers
63 views

Simplify or bound using Big-O notation

1 vote
1 answer
200 views

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

1 vote
0 answers
99 views

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

0 votes
0 answers
42 views

Does for every k $\Sigma _k exists Sigma_k complete issue [closed]

0 votes
1 answer
66 views

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

1 vote
0 answers
42 views
+50

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

0 votes
0 answers
19 views

Round Robin Algorithm ( Process scheduling)

-2 votes
0 answers
13 views

relevance of a large prime number in polynomial rolling hash function

2 votes
0 answers
47 views

Pebble games and conversions to bounded width circuits

0 votes
0 answers
84 views

Separation oracle for breaking cycles in directed graph

-1 votes
0 answers
37 views

What is the bit complexity for Unitary Matrix multiplication?

1 vote
2 answers
102 views

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

2 votes
0 answers
81 views

Natural proofs and size of propositional formulas

13 votes
0 answers
460 views

New quantum algorithm for approximating permanent

-2 votes
0 answers
43 views

Myhill Nerode equivalence classes [closed]

3 votes
1 answer
153 views

Complexity of matrix diagonalization

5 votes
1 answer
157 views

Establishing competing memory limits for pushdown automata

0 votes
0 answers
32 views

Is there an MMSNP formula for 3-colouring?

3 votes
0 answers
123 views

Nested dissection for singular matrices

2 votes
0 answers
75 views

Nondeterministic polynomial time languages with linearly bounded certificates

5 votes
0 answers
74 views

Complexity of approximating boolean functions with circuits

4 votes
1 answer
77 views

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

6 votes
2 answers
223 views

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

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

0 votes
1 answer
53 views

Parameterized complexity of Hitting Set with slightly bigger parameter

0 votes
0 answers
58 views

Vidick's proof of parallel DI-QKD

0 votes
0 answers
73 views

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

3 votes
1 answer
77 views

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


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