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

Explore our Questions

Ask Question

more tags

Active Hot Week Month

5

votes

3

answers

712

views

Is it right to ask a TCS researcher about the real life application of the problem she/he is working on?

soft-question

answered 25 mins ago usul 6,889

0

votes

0

answers

17

views

How does axiom K contradict univalence?

type-theory coq homotopy-type-theory

asked 7 hours ago Grant Jurgensen 1

0

votes

1

answer

64

views

Diophantine equations with bounds on variables

cc.complexity-theory reference-request

modified 10 hours ago GMB 2,073

0

votes

0

answers

36

views

Kolmogorov complexity with limited calculation time - edited

reference-request time-complexity kolmogorov-complexity

modified 11 hours ago Doriano Brogioli 11

-1

votes

0

answers

27

views

How exactly does derandomization of BPP imply lower bounds on NEXP

cc.complexity-theory derandomization

asked 12 hours ago PMercier 49

1

vote

0

answers

58

views

For what parameters is minimum distance hard?

np-hardness approximation-hardness np-complete coding-theory

modified yesterday Root 405

1

vote

0

answers

32

views

Is Kotlin's type system Turing complete?

type-systems genetic-programming

asked yesterday Nathan BeDell 603

3

votes

0

answers

119

views

Pagerank in directed acyclic graphs (DAG)

graph-theory graph-algorithms directed-acyclic-graph data-mining ni.networking-internet

modified yesterday Matthieu Latapy 593

0

votes

1

answer

32

views

Are perceptual hashes connected to audio/video compression?

hash-function

modified yesterday CommunityBot 1

0

votes

0

answers

22

views

Non-random errors with a Reed Solomon code

coding-theory

asked yesterday A. Nilsson 109

3

votes

1

answer

143

views

complexity class of a function - linear combinations and reductions (Fermionant, immanant, $GL_n$ representations)

cc.complexity-theory complexity-classes linear-algebra reductions

modified 2 days ago Teferi 31

-1

votes

1

answer

69

views

Is finding the shortest consistent term to fill a missing line in a truth table still NP-hard?

cc.complexity-theory np-hardness circuit-complexity minimization

answered 2 days ago Neal Young 7,252

0

votes

0

answers

44

views

EXPSPACE-complete problems involving numbers

cc.complexity-theory reference-request

asked 2 days ago gigabytes 970

2

votes

1

answer

79

views

Property testable in sublinear time in bounded degree graphs but not in general graphs

reference-request randomized-algorithms property-testing

modified 2 days ago Clement C. 4,073

Browse more Questions

Theoretical Computer Science Stack Exchange works best with JavaScript enabled