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
Theoretical Computer Science

Top Questions

Ask Question
Active Hot Week Month
16 votes
2 answers
1k views

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

Michael Lampis's user avatar
Michael Lampis
  • 3,416
4 votes
2 answers
519 views

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

Emil Jeřábek's user avatar
Emil Jeřábek
  • 16.9k
6 votes
2 answers
404 views

Error in Robson's proof about separating strings?

Hermann Gruber's user avatar
Hermann Gruber
  • 5,840
5 votes
1 answer
384 views

Relation between ACC^0 and DTIME

Ryan Williams's user avatar
Ryan Williams
  • 27.3k
16 votes
0 answers
1k views

Are theoretical computer science conferences losing touch with reality?

kodlu's user avatar
kodlu
  • 2,070
7 votes
1 answer
318 views

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

Emil Jeřábek's user avatar
Emil Jeřábek
  • 16.9k
2 votes
1 answer
277 views

Deciding finiteness of regular language is NL-complete?

Bartosz Bednarczyk's user avatar
Bartosz Bednarczyk
  • 1,310
3 votes
1 answer
344 views

Intuition on Lupanov's Upper Bound on Circuit Size

Vladimir Lysikov's user avatar
Vladimir Lysikov
  • 632
3 votes
2 answers
251 views

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

Vinicius dos Santos's user avatar
Vinicius dos Santos
  • 1,868
5 votes
1 answer
130 views

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

holf's user avatar
holf
  • 2,164
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?

Gro-Tsen's user avatar
Gro-Tsen
  • 599
2 votes
2 answers
428 views

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

Gro-Tsen's user avatar
Gro-Tsen
  • 599
2 votes
1 answer
168 views

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

D.W.'s user avatar
D.W.
  • 11.7k
4 votes
1 answer
101 views

Lower bound for constant degree monotone arithmetic circuits

Robert Andrews's user avatar
Robert Andrews
  • 743
0 votes
1 answer
97 views

Confusion about lower bounds and upper bounds in learning theory

Aryeh's user avatar
Aryeh
  • 10.3k
4 votes
1 answer
105 views

High-dimensional expanders through the lens of algebraic topology

Yuval Filmus's user avatar
Yuval Filmus
  • 14.3k
3 votes
1 answer
133 views

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

gadmm's user avatar
gadmm
  • 197
2 votes
2 answers
77 views

Learning with zero inductive bias

Aryeh's user avatar
Aryeh
  • 10.3k
1 vote
1 answer
97 views

Balanced set coloring

TheHolyJoker's user avatar
TheHolyJoker
  • 136
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?

Command Master's user avatar
Command Master
  • 464
4 votes
0 answers
113 views

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

Erel Segal-Halevi's user avatar
Erel Segal-Halevi
  • 2,086
1 vote
1 answer
78 views

Learning arithmetic series

Aryeh's user avatar
Aryeh
  • 10.3k
-3 votes
1 answer
98 views

Can one do descriptive complexity theory using abstract state machines?

uhbif19's user avatar
uhbif19
  • 295
0 votes
0 answers
97 views

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

Zazaeil's user avatar
Zazaeil
  • 212
0 votes
0 answers
92 views

Relationships between problem symmetry and its complexity

Ayoubayjx's user avatar
Ayoubayjx
  • 122
4 votes
0 answers
91 views

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

templatetypedef's user avatar
templatetypedef
  • 2,121
0 votes
1 answer
112 views

Computational power of probabilistic automata

Alfonso F R's user avatar
Alfonso F R
  • 27
6 votes
0 answers
62 views

Updating (minimal) DFA incrementally

gsv's user avatar
gsv
  • 421
-1 votes
0 answers
75 views

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

Arcade_TryHard's user avatar
Arcade_TryHard
  • 1
-2 votes
1 answer
58 views

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

Aryeh's user avatar
Aryeh
  • 10.3k
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?

mich's user avatar
mich
  • 429
0 votes
1 answer
56 views

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

Aryeh's user avatar
Aryeh
  • 10.3k
4 votes
0 answers
70 views

distinguishments between query complexity of membership oracles and standard time complexity

John's user avatar
John
  • 173
2 votes
0 answers
65 views

Enforcing general position in $2d$ linear programming

user3508551's user avatar
user3508551
  • 1,078
-1 votes
0 answers
63 views

What are you favorite techniques at finding lower bounds?

rivana's user avatar
rivana
  • 53
1 vote
0 answers
63 views

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

Habri's user avatar
Habri
  • 11
1 vote
0 answers
62 views

Known Variant of Set Cover?

Jan Reineke's user avatar
Jan Reineke
  • 11
-1 votes
1 answer
61 views

Unable to understand the Sample complexity of PAC learning

Ayoubayjx's user avatar
Ayoubayjx
  • 122
2 votes
0 answers
55 views

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

Tran Khanh's user avatar
Tran Khanh
  • 131
2 votes
0 answers
53 views

Many-one equivalence of sets that differ finitely

ijon's user avatar
ijon
  • 33
-1 votes
0 answers
49 views

Average case complexity of decision version of NP-hard problem

Subhra Mazumdar's user avatar
Subhra Mazumdar
  • 99
1 vote
0 answers
47 views

Relation Between Different Definitions of Information Distance

Ravi Deedwania's user avatar
Ravi Deedwania
  • 11
2 votes
0 answers
47 views

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

Johan Thiborg-Ericson's user avatar
Johan Thiborg-Ericson
  • 121
-1 votes
0 answers
44 views

d-regular graphs and edge expanders

math-nerd-in-cs's user avatar
math-nerd-in-cs
  • 1
2 votes
0 answers
42 views

Variable opening in locally-nameless representation

phdstudent's user avatar
phdstudent
  • 121
2 votes
0 answers
42 views

Geometric Set Cover Problem and Union Complexity

Arash Vaezi's user avatar
Arash Vaezi
  • 21
-2 votes
0 answers
42 views

Greedy rounding technique

LyLa's user avatar
LyLa
  • 1

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

Your privacy

By clicking “Accept all cookies”, you agree Stack Exchange can store cookies on your device and disclose information in accordance with our Cookie Policy.