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

0 votes
0 answers
29 views

Short UNSAT Certificates for X3SAT

4 votes
0 answers
61 views

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

0 votes
1 answer
30 views

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

2 votes
1 answer
120 views

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

-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
63 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

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?

3 votes
1 answer
928 views

Subexponential hardness assumption

2 votes
0 answers
75 views

Nondeterministic polynomial time languages with linearly bounded certificates

0 votes
1 answer
53 views

Parameterized complexity of Hitting Set with slightly bigger parameter

5 votes
0 answers
74 views

Complexity of approximating boolean functions with circuits

Browse more Questions