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

3

votes

1

answer

64

views

Is Barbara Liskov's claim that CLU was the first implemented language to provide linguistic support for data abstraction accurate?

pl.programming-languages ho.history-overview

answered 18 hours ago benrg 131

1

vote

0

answers

38

views

Asymptotic complexity lower bounds of proof checking

cc.complexity-theory time-complexity proof-complexity proof-theory

modified 21 hours ago Mario Carneiro 143

6

votes

1

answer

181

views

Uniformly sampling or counting connected graph partitions with any number of blocks

graph-algorithms np-hardness counting-complexity randomized-algorithms partition-problem

modified yesterday Community♦ 1

134

votes

29

answers

22k

views

Problems Between P and NPC

cc.complexity-theory np-hardness big-list np-intermediate

modified yesterday Clement C. 4,053

3

votes

1

answer

254

views

What are some "must-read" papers for someone getting into Quantum Cryptography?

quantum-computing cr.crypto-security quantum-information

modified yesterday Community♦ 1

0

votes

0

answers

37

views

How do we evalute the difference between a predicted value $\hat{v}$ and the true nash equlibrium value $v$

gt.game-theory approximation nash-equilibrium

modified 2 days ago dawen 131

2

votes

1

answer

70

views

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

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

answered 2 days ago Joshua Grochow 34.6k

1

vote

1

answer

48

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 Avi Tal 1,446

1

vote

1

answer

190

views

Is this a novel technique for determining whether or not two rotated rectangles collide?

ds.algorithms reference-request cg.comp-geom

modified 2 days ago Erick Weber 27

0

votes

0

answers

52

views

A Simpler Solution for a special case of the Set Cover problem

set-cover polygon

asked 2 days ago Arash Vaezi 1

8

votes

1

answer

190

views

Does Horn SAT (Horn formula in CNF) have an integral polytope?

cc.complexity-theory co.combinatorics sat matching polytope

modified Sep 14 at 19:44 Neal Young 7,147

0

votes

1

answer

91

views

Complexity for universal Counter Machine with {0,1}-valued registers

automata-theory time-complexity lower-bounds turing-machines counter-automata

answered Sep 14 at 16:57 D.W. 10.1k

6

votes

1

answer

148

views

Programming language supporting infinitary rewriting of regular term graphs?

functional-programming term-rewriting-systems

modified Sep 14 at 15:53 Jason Hemann 3

-2

votes

0

answers

25

views

Geometric Intersection Graphs Online Coloring

graph-algorithms graph-colouring online-algorithms books

asked Sep 14 at 13:22 R.hatam 17

Browse more Questions

Theoretical Computer Science Stack Exchange works best with JavaScript enabled