Theoretical Computer Science Stack Exchange

1

vote

1

answer

17

views

Is there hypothesis classes that are hard to learn but easy to test

machine-learning property-testing pac-learning

modified 2 hours ago Paul 73

-1

votes

0

answers

19

views

Distance vector vs Link state routing

network-modeling

asked 11 hours ago user9355495 1

3

votes

1

answer

262

views

Indications that strengthen the conjecture: NEXP ⊊ EXP^NP

complexity-classes oracles nexp

modified 19 hours ago Community♦ 1

3

votes

0

answers

76

views

Distinguishing a biased coin with a small set of tests

property-testing

asked yesterday Chris Jones 156

6

votes

2

answers

145

views

Is uniform convergence faster for low-entropy distributions?

pr.probability vc-dimension shannon-entropy sample-complexity

modified yesterday Thomas 2,128

1

vote

1

answer

51

views

Strong Normalization of Extended Calculus of Constructions (CC with cumulative universes)

type-theory dependent-type

answered yesterday cody 10.8k

7

votes

1

answer

164

views

Can a totality checker be used to guarantee a proof on the calculus of constructions + inductive types is correct?

type-theory lambda-calculus

modified yesterday cody 10.8k

0

votes

0

answers

32

views

Is this a knapsack problem?

optimization

asked yesterday dineshdileep 104

0

votes

1

answer

70

views

Subset Sum Problem and hard looking instances that are not really hard

co.combinatorics np-hardness np-complete subset-sum

answered yesterday Jeffrey Shallit 6,284

9

votes

2

answers

5k

views

Time complexity of Held-Karp algorithm for TSP

ds.algorithms tsp exp-time-algorithms

answered 2 days ago dimathe47 1

3

votes

1

answer

50

views

Distinguising between the cases of low or high cover number

approximation-hardness

answered 2 days ago Sasho Nikolov 16.1k

4

votes

1

answer

90

views

Applications of Christol theorem

co.combinatorics automata-theory

answered Dec 8 at 18:44 Jeffrey Shallit 6,284

5

votes

0

answers

117

views

Evaluation of an arithmetic formula where the time depends on the length of the arguments of gates

ds.algorithms arithmetic-circuits

modified Dec 8 at 8:17 Emil Jeřábek 10.4k

18

votes

0

answers

546

views

Identifying Reducible/Irreducible polynomials over $Z[x]$

open-problem algebraic-complexity

modified Dec 8 at 5:15 Phylliida 634

Stack Exchange Network

current community

your communities

more stack exchange communities

Explore Our Questions

Is there hypothesis classes that are hard to learn but easy to test

Distance vector vs Link state routing

Indications that strengthen the conjecture: NEXP ⊊ EXP^NP

Distinguishing a biased coin with a small set of tests

Is uniform convergence faster for low-entropy distributions?

Strong Normalization of Extended Calculus of Constructions (CC with cumulative universes)

Can a totality checker be used to guarantee a proof on the calculus of constructions + inductive types is correct?

Is this a knapsack problem?

Subset Sum Problem and hard looking instances that are not really hard

Time complexity of Held-Karp algorithm for TSP

Distinguising between the cases of low or high cover number

Applications of Christol theorem

Evaluation of an arithmetic formula where the time depends on the length of the arguments of gates

Identifying Reducible/Irreducible polynomials over $Z[x]$

Visit Chat

Hot Network Questions