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
12 views

Nonlinear GAP similar to Min-GAP but with minimum quantities and without capacity

3 votes
0 answers
57 views

Are there any problems in $\mathsf{BPP}$ that are known to be $\mathsf{RP}$-hard or $\mathsf{coRP}$-hard?

0 votes
1 answer
206 views

Any analogues to Turing-Church thesis out there? [closed]

-2 votes
1 answer
86 views

Proof that DFS order is P-complete

5 votes
0 answers
121 views

Variation of (derandomized) Valiant-Vazirani

1 vote
0 answers
69 views

Is it possible to recover the set of derivation trees of a fact from its semiring provenance in Datalog?

0 votes
0 answers
49 views

Hardness for find the clause for statisfiable 3-SAT problems

8 votes
1 answer
403 views

What can we do with a generic oracle (as opposed to a random one)?

1 vote
0 answers
65 views

How often can a clause cause a conflict?

6 votes
2 answers
435 views

Error in Robson's proof about separating strings?

5 votes
1 answer
149 views

Can CDCL Algorithm Derived Conflict Clauses Always Be Obtained Through Resolution from an Unsatisfiable CNF Formula?

16 votes
2 answers
1k views

Is there a SETH (Strong Exponential Time Hypothesis) for CSP (Constraint Satisfaction Problem)?

1 vote
0 answers
39 views

Find the SVM kernel in detecting if a substring in a given string

-1 votes
0 answers
32 views

corresponding resoving and arbitary resolving

-1 votes
0 answers
82 views

Proof for Upper Bound on the Size of the Sum of Rational Numbers

2 votes
0 answers
54 views

Is the Category of $(* \to)^n *$-kinded types freely generated from the discrete graph with $n$ nodes?

0 votes
1 answer
103 views

Confusion about lower bounds and upper bounds in learning theory

4 votes
0 answers
122 views

Convex optimization: is it possible to find solutions that are exactly feasible and approximately optimal in polynomial time?

2 votes
0 answers
72 views

Enforcing general position in $2d$ linear programming

1 vote
1 answer
102 views

Known Variant of Set Cover?

2 votes
2 answers
434 views

Technical limitations of Turing machines due to the input and output encoding of values

1 vote
1 answer
126 views

Are there any algorithms that the brain is better at solving than a regular computer? How would these be found/verified?

2 votes
0 answers
59 views

Many-one equivalence of sets that differ finitely

0 votes
0 answers
41 views

Approximation ratio of randomized rounding for integral multi-commodity flow

4 votes
2 answers
522 views

Do we currently know a polynomial-size Frege proof for Tseitin formulas?

-2 votes
1 answer
61 views

What is really the difference between membership queries and "querying in i.i.d?

17 votes
0 answers
1k views

Are theoretical computer science conferences losing touch with reality?

4 votes
1 answer
142 views

Connection between strong normalization of the simply typed λ-calculus, and cut elimination for propositional logic

1 vote
1 answer
101 views

Balanced set coloring

3 votes
1 answer
169 views

What’s the complexity of this decision problem with bit shifting?

-2 votes
0 answers
46 views

d-regular graphs and edge expanders

0 votes
0 answers
92 views

Relationships between problem symmetry and its complexity

3 votes
1 answer
345 views

Intuition on Lupanov's Upper Bound on Circuit Size

2 votes
2 answers
81 views

Learning with zero inductive bias

-2 votes
0 answers
43 views

Greedy rounding technique

-1 votes
0 answers
64 views

What are you favorite techniques at finding lower bounds?

3 votes
2 answers
256 views

Where should I apply for MS in CS if I want to get admitted for Phd in TCS

4 votes
1 answer
103 views

Lower bound for constant degree monotone arithmetic circuits

-1 votes
0 answers
26 views

Finding an algorithm EF[1,1] and PO division for more than two agents

0 votes
1 answer
59 views

Learning positive half-lines (in $\mathbb{N}$)

-1 votes
0 answers
50 views

Average case complexity of decision version of NP-hard problem

1 vote
0 answers
64 views

Crafting ${NP}^{\#P}$-complete problems

6 votes
0 answers
64 views

Updating (minimal) DFA incrementally

1 vote
1 answer
78 views

Learning arithmetic series

10 votes
0 answers
204 views

Is there a text that discusses both the “lambda cube” of pure type theories and Martin-Löf's intuitionistic type theories, and compares them?

1 vote
0 answers
39 views

what are some Lower bound for finding large fourier coefficients of boolean function (above a threshold)?


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