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

16 votes
2 answers
1k views

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

4 votes
2 answers
519 views

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

6 votes
2 answers
404 views

Error in Robson's proof about separating strings?

5 votes
1 answer
384 views

Relation between ACC^0 and DTIME

16 votes
0 answers
1k views

Are theoretical computer science conferences losing touch with reality?

7 votes
1 answer
318 views

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

2 votes
1 answer
277 views

Deciding finiteness of regular language is NL-complete?

3 votes
1 answer
344 views

Intuition on Lupanov's Upper Bound on Circuit Size

3 votes
2 answers
251 views

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

5 votes
1 answer
130 views

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

10 votes
0 answers
203 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?

2 votes
2 answers
428 views

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

2 votes
1 answer
168 views

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

4 votes
1 answer
101 views

Lower bound for constant degree monotone arithmetic circuits

0 votes
1 answer
97 views

Confusion about lower bounds and upper bounds in learning theory

4 votes
1 answer
105 views

High-dimensional expanders through the lens of algebraic topology

3 votes
1 answer
133 views

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

2 votes
2 answers
77 views

Learning with zero inductive bias

1 vote
1 answer
97 views

Balanced set coloring

1 vote
1 answer
122 views

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

4 votes
0 answers
113 views

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

1 vote
1 answer
78 views

Learning arithmetic series

-3 votes
1 answer
98 views

Can one do descriptive complexity theory using abstract state machines?

0 votes
0 answers
97 views

Assume `P != NP`, does it imply that one-way functions exist?

0 votes
0 answers
92 views

Relationships between problem symmetry and its complexity

4 votes
0 answers
91 views

$\log^\star n$ is somewhat common in runtimes. Does the superroot ever make an appearance?

0 votes
1 answer
112 views

Computational power of probabilistic automata

6 votes
0 answers
62 views

Updating (minimal) DFA incrementally

-1 votes
0 answers
75 views

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

-2 votes
1 answer
58 views

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

4 votes
0 answers
72 views

Name for a cyclic path in a graph that visits every vertex while minimizing the maximum number of times a given vertex is revisited?

0 votes
1 answer
56 views

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

4 votes
0 answers
70 views

distinguishments between query complexity of membership oracles and standard time complexity

2 votes
0 answers
65 views

Enforcing general position in $2d$ linear programming

-1 votes
0 answers
63 views

What are you favorite techniques at finding lower bounds?

1 vote
0 answers
63 views

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

1 vote
0 answers
62 views

Known Variant of Set Cover?

-1 votes
1 answer
61 views

Unable to understand the Sample complexity of PAC learning

2 votes
0 answers
55 views

Does PAC learnable imply agnostic PAC learnable for binary classification tasks?

2 votes
0 answers
53 views

Many-one equivalence of sets that differ finitely

-1 votes
0 answers
49 views

Average case complexity of decision version of NP-hard problem

1 vote
0 answers
47 views

Relation Between Different Definitions of Information Distance

2 votes
0 answers
47 views

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

-1 votes
0 answers
44 views

d-regular graphs and edge expanders

2 votes
0 answers
42 views

Variable opening in locally-nameless representation

2 votes
0 answers
42 views

Geometric Set Cover Problem and Union Complexity

-2 votes
0 answers
42 views

Greedy rounding technique


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