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 1 Bountied Hot Week Month
8 votes
1 answer
1k views

Are there survey papers in theoretical computer science?

user avatar
Rodrigo de Azevedo
  • 233
6 votes
2 answers
225 views

How to show that the median cannot be maintained in $O(1)$ time?

user avatar
Andreas ZUERCHER
  • 101
1 vote
1 answer
206 views

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

user avatar
wonderinghuh
  • 197
13 votes
0 answers
474 views

New quantum algorithm for approximating permanent

user avatar
Hhan
  • 261
2 votes
2 answers
145 views

Seeking references on writing a long string $\ell$ as concatenation of shorter strings $s_1, s_2, s_3, ...$

user avatar
user66277
  • 116
5 votes
1 answer
158 views

Establishing competing memory limits for pushdown automata

user avatar
a3nm
  • 7,350
3 votes
1 answer
192 views

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

user avatar
Yuval Filmus
  • 14.1k
2 votes
1 answer
183 views

Upper bound for VCdim of $H$ in terms of subgraph$(F)$, where $H := \{S(f) | f \in F\}$, with $S(f) := \{(x,y) \in X \times \{\pm 1\} | yf(x) \le 1\}$

user avatar
Aryeh
  • 10k
1 vote
2 answers
105 views

How to find the size of an ϵ-net of a vector space?

user avatar
Silverstalon
  • 113
2 votes
1 answer
125 views

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

user avatar
Laakeri
  • 1,398
3 votes
1 answer
153 views

Complexity of matrix diagonalization

user avatar
Geoffrey Irving
  • 3,211
4 votes
1 answer
107 views

What are the application of Scott-Topology in theoretical computer science?

user avatar
Martin Berger
  • 10.2k
6 votes
0 answers
115 views

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

user avatar
Gil Kalai
  • 5,933
0 votes
1 answer
68 views

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

user avatar
Dan Doel
  • 566
-3 votes
0 answers
130 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)?

user avatar
Majid Zohrehbandian
  • 1
3 votes
1 answer
77 views

$\mathrm{AC}^0$ upper bound for Hamming weight

user avatar
Emil Jeřábek
  • 14.7k
3 votes
0 answers
123 views

Nested dissection for singular matrices

user avatar
Chao Xu
  • 4,256
2 votes
1 answer
123 views

Sample complexity lower bound to learn the mode (the value with the highest probability) of a distribution with finite support

user avatar
actcon
  • 23
1 vote
0 answers
104 views

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

user avatar
hellothere
  • 11
4 votes
1 answer
77 views

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

user avatar
Joshua Grochow
  • 35.6k
5 votes
0 answers
74 views

Complexity of approximating boolean functions with circuits

user avatar
Igor Ferst
  • 51
0 votes
0 answers
87 views

Separation oracle for breaking cycles in directed graph

user avatar
reservoir
  • 89
2 votes
0 answers
84 views

Natural proofs and size of propositional formulas

user avatar
Reijo Jaakkola
  • 736
0 votes
0 answers
75 views

Does NP-completeness in one graph class imply not NP-intermediate in another graph class?

user avatar
Cyriac Antony
  • 1,603
2 votes
0 answers
75 views

Nondeterministic polynomial time languages with linearly bounded certificates

user avatar
Alberto
  • 91
2 votes
0 answers
73 views

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

user avatar
Reijo Jaakkola
  • 736
0 votes
0 answers
71 views

Complexity of the distance between the average vector of two subsets

user avatar
mathworker21
  • 223
1 vote
1 answer
43 views

Operations on Sentential Decision Diagrams

user avatar
holf
  • 1,855
0 votes
1 answer
53 views

Parameterized complexity of Hitting Set with slightly bigger parameter

user avatar
daniello
  • 3,161
0 votes
0 answers
64 views

Simplify or bound using Big-O notation

user avatar
wanderer
  • 89
4 votes
0 answers
63 views

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

user avatar
embie27
  • 41
2 votes
0 answers
59 views

Does advice reduce depth?

user avatar
trillianhaze
  • 21
0 votes
0 answers
59 views

Vidick's proof of parallel DI-QKD

user avatar
Noel
  • 101
2 votes
0 answers
57 views

Is k-ACYCLIC COLOURABLITY in CSP?

user avatar
Cyriac Antony
  • 1,603
-2 votes
0 answers
56 views

VC-dimension of an infinite set of functions

user avatar
shai
  • 1
2 votes
0 answers
55 views

From formal models to programs - Model Checking

user avatar
user17302
  • 59
3 votes
0 answers
55 views

Is there a standard way to "point" at subterms in a lambda expression?

user avatar
azani
  • 133
0 votes
0 answers
54 views

Algorithms with advices of huge precomputed data

user avatar
Hiroki Morizumi
  • 689
1 vote
1 answer
41 views

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

user avatar
davidbuzatto
  • 126
1 vote
0 answers
52 views

Code indistinguishability assumption for Code based cryptography (in special cases)

user avatar
Root
  • 387
0 votes
0 answers
51 views

Does the the equivalence of Total variation distance formulas assumes that the two distributions are symmetrical?

user avatar
Alex
  • 1
0 votes
0 answers
49 views

Short UNSAT Certificates for X3SAT

user avatar
Russell Easterly
  • 499
2 votes
0 answers
48 views

Pebble games and conversions to bounded width circuits

user avatar
Hiroki Morizumi
  • 689
1 vote
0 answers
47 views

Cheapest Insertion is $2$-approximation for TSP

user avatar
Ioana Roman
  • 11
-1 votes
0 answers
47 views

How to prove a problem does not have an approximation algorithm?

user avatar
Shaan
  • 1
0 votes
0 answers
46 views

Converting a rational star-connected expression to an NFA

user avatar
jrwdupl-youtubeyahoocouk
  • 61
0 votes
0 answers
46 views

Are there more learnable but undecidable cases except the halting problem

user avatar
Mountain
  • 101

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.