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 1 Bountied Hot Week Month

1

vote

0

answers

21

views

Relationship between SC and NL

cc.complexity-theory space-complexity

asked 2 hours ago Anony 11

2

votes

2

answers

93

views

Looking for some lecture videos on logic, models of computation and computational complexity/tcs fundamentals

cc.complexity-theory lo.logic soft-question machine-models first-order-logic

modified 23 hours ago Avi Tal 1,356

3

votes

3

answers

3k

views

Difference between self-information and entropy

it.information-theory shannon-entropy

modified yesterday Post169 141

0

votes

0

answers

41

views

Size of CNF Formula for Adjacency in Configuration Graph

cc.complexity-theory space-complexity cook-levin

modified yesterday Anon 31

3

votes

0

answers

57

views

Is there a standard interpretation of this quantity?

reference-request coding-theory

asked yesterday Mark 758

3

votes

0

answers

51

views

Formal proof of correctness of Levenshtein distance

edit-distance

asked 2 days ago Jacques Carette 1,450

1

vote

1

answer

86

views

Is there any relation between $\mathsf{PPP}\subseteq\mathsf{TFNP}$ and $\mathsf{UP}$?

cc.complexity-theory complexity-classes

answered 2 days ago Joshua Grochow 34k

5

votes

2

answers

379

views

Finite-State Automata over a real-valued alphabet

automata-theory

answered 2 days ago Ronen Brafman 21

0

votes

0

answers

40

views

Why is preservation not quantified over Gamma?

pl.programming-languages coq

asked 2 days ago Quinn Dougherty 11

3

votes

0

answers

55

views

Increasing Functions in Non-deterministic Time Hierarchy Theorems

cc.complexity-theory hierarchy-theorems time-hierarchy

asked 2 days ago Anon 31

1

vote

0

answers

41

views

Average-case randomized communication complexity in the small-advantage regime

lower-bounds communication-complexity

asked 2 days ago William Hoza 1,353

0

votes

0

answers

21

views

I need help with methods specific to DeWall's D&C DT algorithm to implement it

computational-geometry delaunay-triangulation

asked 2 days ago user173220 1

0

votes

0

answers

42

views

what is the LP gap of this particular non metric facility location problem in planar graphs?

planar-graphs integer-programming set-cover integrality-gap

modified Feb 3 at 20:05 Hao S 209

1

vote

2

answers

61

views

VC generalization bound extended to other types of target functions

machine-learning vc-dimension

answered Feb 3 at 19:37 Another Grad student 121

Browse more Questions

Theoretical Computer Science Stack Exchange works best with JavaScript enabled