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
1 vote
0 answers
21 views

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

user avatar
actcon
  • 11
3 votes
0 answers
27 views

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

user avatar
micrus
  • 31
7 votes
1 answer
972 views

Are there survey papers in theoretical computer science?

user avatar
Rodrigo de Azevedo
  • 233
0 votes
0 answers
29 views

Short UNSAT Certificates for X3SAT

user avatar
Russell Easterly
  • 499
0 votes
0 answers
39 views

Complexity of the distance between the average vector of two subsets

user avatar
mathworker21
  • 222
2 votes
0 answers
63 views

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

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

Direct fpt reduction from Weighted 3SAT to Weighted 2SAT

user avatar
Noel Arteche
  • 469
4 votes
0 answers
61 views

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

user avatar
embie27
  • 41
1 vote
1 answer
35 views

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

user avatar
davidbuzatto
  • 126
0 votes
0 answers
41 views

Did anyone ever adapted TCS data structure results (e.g. vEB trees) into Governance structures?

user avatar
Jeremy
  • 2,391
-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)?

user avatar
Majid Zohrehbandian
  • 1
0 votes
0 answers
31 views

Defining a process without internal events

user avatar
dandy
  • 1
2 votes
1 answer
120 views

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

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

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

user avatar
Yuval Filmus
  • 14.1k
6 votes
0 answers
101 views

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

user avatar
Gil Kalai
  • 5,933
0 votes
0 answers
39 views

Perfect simulation of classical dynamical systems

user avatar
TheDorkSide
  • 1
0 votes
0 answers
63 views

Simplify or bound using Big-O notation

user avatar
wanderer
  • 89
1 vote
1 answer
200 views

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

user avatar
wonderinghuh
  • 197
1 vote
0 answers
99 views

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

user avatar
hellothere
  • 11
0 votes
0 answers
42 views

Does for every k $\Sigma _k exists Sigma_k complete issue [closed]

user avatar
Dali Parkinson
  • 1
0 votes
1 answer
66 views

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

user avatar
Dan Doel
  • 566
1 vote
0 answers
42 views
+50

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

user avatar
Root
  • 295
0 votes
0 answers
19 views

Round Robin Algorithm ( Process scheduling)

user avatar
OUSSAMA ABBOU
  • 1
-2 votes
0 answers
13 views

relevance of a large prime number in polynomial rolling hash function

user avatar
kratos
  • 1
2 votes
0 answers
47 views

Pebble games and conversions to bounded width circuits

user avatar
Hiroki Morizumi
  • 689
0 votes
0 answers
84 views

Separation oracle for breaking cycles in directed graph

user avatar
reservoir
  • 89
-1 votes
0 answers
37 views

What is the bit complexity for Unitary Matrix multiplication?

user avatar
Doddy Pal
  • 1
1 vote
2 answers
102 views

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

user avatar
Silverstalon
  • 13
2 votes
0 answers
81 views

Natural proofs and size of propositional formulas

user avatar
Reijo Jaakkola
  • 736
13 votes
0 answers
460 views

New quantum algorithm for approximating permanent

user avatar
Hhan
  • 261
-2 votes
0 answers
43 views

Myhill Nerode equivalence classes [closed]

user avatar
FuryAndMike
  • 1
3 votes
1 answer
153 views

Complexity of matrix diagonalization

user avatar
Geoffrey Irving
  • 3,211
5 votes
1 answer
157 views

Establishing competing memory limits for pushdown automata

user avatar
a3nm
  • 7,350
0 votes
0 answers
32 views

Is there an MMSNP formula for 3-colouring?

user avatar
Cyriac Antony
  • 1,603
3 votes
0 answers
123 views

Nested dissection for singular matrices

user avatar
Chao Xu
  • 4,256
2 votes
0 answers
75 views

Nondeterministic polynomial time languages with linearly bounded certificates

user avatar
Alberto
  • 91
5 votes
0 answers
74 views

Complexity of approximating boolean functions with circuits

user avatar
Igor Ferst
  • 51
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
6 votes
2 answers
223 views

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

user avatar
Andreas ZUERCHER
  • 101
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
0 votes
1 answer
53 views

Parameterized complexity of Hitting Set with slightly bigger parameter

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

Vidick's proof of parallel DI-QKD

user avatar
Noel
  • 101
0 votes
0 answers
73 views

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

user avatar
Cyriac Antony
  • 1,603
3 votes
1 answer
77 views

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

user avatar
Emil Jeřábek
  • 14.7k

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.