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

0 votes
0 answers
28 views

Short UNSAT Certificates for X3SAT

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?

2 votes
0 answers
63 views

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

7 votes
1 answer
972 views

Are there survey papers in theoretical computer science?

0 votes
0 answers
39 views

Complexity of the distance between the average vector of two subsets

3 votes
1 answer
181 views

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

0 votes
0 answers
24 views

Direct fpt reduction from Weighted 3SAT to Weighted 2SAT

21 votes
2 answers
7k views

Oracle Construction for Grover's Algorithm

4 votes
0 answers
61 views

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

4 votes
1 answer
95 views

Deciding almost prime numbers

-1 votes
1 answer
54 views

Easy verifier for Shortest Vector

0 votes
1 answer
30 views

Decomposing outer product or general rank factorization over $\Bbb F_q$

0 votes
1 answer
54 views

Factoring random selfreducibility analogy from discrete logarithm

1 vote
1 answer
35 views

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

2 votes
1 answer
120 views

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

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

12 votes
1 answer
1k views

Is anyone aware of a counter-example to the Dharwadker-Tevet Graph Isomorphism algorithm?

0 votes
0 answers
39 views

Perfect simulation of classical dynamical systems

0 votes
0 answers
62 views

Simplify or bound using Big-O notation

6 votes
0 answers
101 views

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

0 votes
0 answers
42 views

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

2 votes
1 answer
163 views

Maximize a special monotone submodular function - is it easier?

1 vote
0 answers
98 views

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

-2 votes
0 answers
13 views

relevance of a large prime number in polynomial rolling hash function

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)

1 vote
1 answer
200 views

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

0 votes
1 answer
66 views

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

2 votes
0 answers
47 views

Pebble games and conversions to bounded width circuits

8 votes
2 answers
510 views

Complexity of the $(3,2)_s$ SAT problem?

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?

5 votes
1 answer
157 views

Establishing competing memory limits for pushdown automata

9 votes
2 answers
343 views

Is uniform convergence faster for low-entropy distributions?

4 votes
1 answer
113 views

Do there exists reversible gate sets of intermediate growth?

3 votes
1 answer
928 views

Subexponential hardness assumption

4 votes
1 answer
77 views

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

2 votes
0 answers
81 views

Natural proofs and size of propositional formulas

-2 votes
0 answers
43 views

Myhill Nerode equivalence classes [closed]

0 votes
0 answers
32 views

Is there an MMSNP formula for 3-colouring?

3 votes
1 answer
153 views

Constructing Orbits of the Automorphism of a Graph Group in Bliss


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