Theoretical Computer Science Stack Exchange

6

votes

1

answer

89

views

Can Isorecursive types capture mutually recursive data types?

type-theory type-inference

modified 1 hour ago Andrej Bauer 22.4k

0

votes

0

answers

22

views

Partially persistent linked list data structure: would lookup of the first element at a specific version be O(|versions|) and not O(1)?

ds.data-structures

modified 3 hours ago Peeyush Kushwaha 101

3

votes

0

answers

21

views

Hard family for degree-$D$ MAX-3LIN

sat approximation-hardness linear-equations

modified 13 hours ago Abel Molina 1,319

11

votes

1

answer

213

views

+50

Deterministic error reduction, state-of-the-art?

reference-request randomness pseudorandomness expanders

answered 20 hours ago guest 11

22

votes

3

answers

4k

views

Is Magic: the Gathering Turing complete?

turing-machines card-games recreational

answered yesterday DerMolly 141

0

votes

0

answers

19

views

Two question regarding coreset construictions

reference-request approximation-algorithms randomness computational-geometry clustering

asked yesterday Sudipta Roy 106

0

votes

0

answers

42

views

Linear time algorithm for projective clustering

reference-request approximation-algorithms randomness computational-geometry clustering

modified yesterday Sudipta Roy 106

1

vote

1

answer

95

views

Count satisfying assignments of CNF formulas over all possible negation assignments

cc.complexity-theory approximation-algorithms sat counting-complexity

answered yesterday Emil Jeřábek 10.4k

17

votes

3

answers

757

views

Computing sum of sparse polynomials squared in O(n log n) time?

ds.algorithms algebra polynomials

answered 2 days ago Thomas Ahle 353

0

votes

0

answers

56

views

What is sequence unification?

lo.logic

asked 2 days ago Björn Lindqvist 229

16

votes

2

answers

1k

views

“Almost sorting” integers in linear time

reference-request time-complexity sorting

modified Jun 15 at 12:37 David 188

10

votes

1

answer

485

views

Complexity of convolution in the max/plus ring

algebra polynomials fft convolution

modified Jun 15 at 8:24 Thomas Ahle 353

1

vote

0

answers

88

views

Oracle separation between PH and PSPACE

oracles complexity

modified Jun 14 at 21:06 BlackHat18 9

6

votes

1

answer

310

views

Algebra and algebraic data types

ds.data-structures algebra

modified Jun 14 at 15:54 Giorgio Mossa 349

Stack Exchange Network

current community

your communities

more stack exchange communities

Explore Our Questions

Can Isorecursive types capture mutually recursive data types?

Partially persistent linked list data structure: would lookup of the first element at a specific version be O(|versions|) and not O(1)?

Hard family for degree-$D$ MAX-3LIN

Deterministic error reduction, state-of-the-art?

Is Magic: the Gathering Turing complete?

Two question regarding coreset construictions

Linear time algorithm for projective clustering

Count satisfying assignments of CNF formulas over all possible negation assignments

Computing sum of sparse polynomials squared in O(n log n) time?

What is sequence unification?

“Almost sorting” integers in linear time

Complexity of convolution in the max/plus ring

Oracle separation between PH and PSPACE

Algebra and algebraic data types

Hot Network Questions