Hottest Questions Today

1

vote

1

answer

16

views

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

modified 1 hour ago Paul 73

-1

votes

0

answers

19

views

Distance vector vs Link state routing

network-modeling

asked 10 hours ago user9355495 1

3

votes

0

answers

76

views

Distinguishing a biased coin with a small set of tests

property-testing

asked yesterday Chris Jones 156

5

votes

2

answers

165

views

Is getting post-doc difficult in theoretical computer science with few published papers? [on hold]

soft-question

modified yesterday Emil Jeřábek 10.4k

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

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

1

vote

1

answer

50

views

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

type-theory dependent-type

answered yesterday cody 10.8k

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

0

votes

0

answers

14

views

Partial Recursive Functions of Kleene [on hold]

function recursive

asked 2 days ago Keker 1

2

votes

1

answer

263

views

Is there a counterexample to this work?

reference-request linear-programming p-vs-np integer-programming complexity

modified Dec 6 at 14:45 Emil Jeřábek 10.4k

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

4

votes

1

answer

90

views

Applications of Christol theorem

co.combinatorics automata-theory

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

-2

votes

0

answers

25

views

Turing machine with semi infinite tape - Prove by construction [on hold]

turing-machines

asked Dec 7 at 23:12 Francisco Hanna 1

-3

votes

0

answers

71

views

Difficulty Grasping Asymptotic Notation in CLRS Algorithms Book [on hold]

ds.algorithms time-complexity

asked Dec 6 at 23:49 Noah Stebbins 4

1

vote

1

answer

68

views

Is balanced Hamiltonian cycle NP complete on maximal plane graphs?

cc.complexity-theory graph-theory np-complete planar-graphs hamiltonian-paths

modified Dec 6 at 19:08 Lorenzo 254

2

votes

1

answer

87

views

Is there a gap between weak learning and PAC-learning?

machine-learning lg.learning

modified Dec 5 at 11:07 Aryeh 5,439

0

votes

0

answers

29

views

What is the right term/theory for prediction of Binary Variables based upon their continuous value?

reference-request optimization linear-programming integer-programming

asked Dec 6 at 8:31 Deepak Mishra 101

-1

votes

0

answers

80

views

What kinds of algorithm have running time $O(\log n/ \log \log n)$in most of the cases? [closed]

cc.complexity-theory speed-up

asked Dec 4 at 7:23 user9414424 6

7

votes

2

answers

302

views

Are all turing machines paths predictable?

automata-theory turing-machines halting-problem

modified Dec 3 at 17:52 Marzio De Biasi 18.2k

1

vote

1

answer

67

views

Pulling a graph across a partition

graph-theory graph-algorithms co.combinatorics

answered Dec 2 at 4:39 daniello 2,636

-1

votes

1

answer

67

views

When is extra vertex required in arbitrage detection using Bellman Ford?

graph-algorithms shortest-path

answered Dec 3 at 15:56 Sandeep Silwal 127

-2

votes

1

answer

163

views

Graduate school for CS theory?

soft-question career

modified Nov 30 at 21:19 someone111 11

1

vote

0

answers

34

views

A categorized (?) list of functional pearls in JFP and ICFP

reference-request big-list functional-programming

asked Dec 3 at 23:17 xuq01 527

-3

votes

0

answers

31

views

Map Reduce and Sorting [closed]

dc.distributed-comp

asked Dec 3 at 23:07 hadoopguy123 1

-1

votes

0

answers

45

views

Find optimum of a neural network computationally

ne.neural-evol function

asked Dec 2 at 12:16 Max Mustermann Junior 1

9

votes

0

answers

72

views

Are there cascade decompositions of machines that are more general than finite automata?

fl.formal-languages automata-theory algebra

asked Nov 30 at 20:45 Taylor Dohmen 101

1

vote

0

answers

86

views

Solving the Halting problem for most inputs [closed]

computability turing-machines halting-problem

asked Nov 30 at 17:12 Asvin 112

2

votes

1

answer

63

views

Find shortest prefix to generate original string by overlapping

ds.algorithms string-matching string-search

answered Nov 30 at 11:19 Jeffrey Shallit 6,284

16

votes

1

answer

571

views

The TOC Blog Aggregator is Offline

soft-question

modified Nov 24 at 6:38 Bjørn Kjos-Hanssen♦ 3,524

1

vote

0

answers

55

views

Complexity of enumerating over promise problems and circuits?

cc.complexity-theory complexity-classes quantum-computing promise-problems enumeration

modified Dec 1 at 13:33 user138901 45

8

votes

2

answers

208

views

Hereditary substitution with a universe hierarchy

reference-request lo.logic pl.programming-languages type-theory lambda-calculus

modified Nov 23 at 15:57 András Kovács 176

1

vote

1

answer

67

views

Cryptography protocols using graph problem instances

graph-theory soft-question cr.crypto-security

answered Nov 29 at 16:38 Adam Smith 898

1

vote

0

answers

73

views

Impartial Combinatorial Games as a core of the final undergraduate project

application-of-theory combinatorial-game-theory project-topic

modified Dec 1 at 18:59 Abdulkader 9

1

vote

1

answer

113

views

Does every online algorithm has an offline counterpart?

online-algorithms

answered Dec 3 at 15:37 Sandeep Silwal 127

-1

votes

0

answers

28

views

Do new algorithms or better machine learning methods have a better chance of making an impact on protein analysis in bioinformatics?

ds.algorithms soft-question bioinformatics

asked Dec 1 at 17:11 nish2575 156

20

votes

1

answer

1k

views

Number of words of length n in a context-free language

fl.formal-languages context-free

modified Nov 14 at 13:00 Gamow 3,834

3

votes

0

answers

70

views

Do features always induce a metric?

machine-learning lg.learning metric-spaces

asked Nov 29 at 17:56 Aryeh 5,439

6

votes

1

answer

98

views

Time complexity of derivative-based regex matchers

regular-expressions

modified Nov 27 at 13:35 Neel Krishnaswami 26.4k

-1

votes

0

answers

49

views

how to calculate inverse of entropy?

it.information-theory shannon-entropy entropy

modified Nov 30 at 9:57 user1285170 6

11

votes

1

answer

222

views

Is DSPACE(n) = DSPACE(1.5n)?

cc.complexity-theory complexity-classes

modified Nov 23 at 10:24 domotorp 8,729

0

votes

0

answers

63

views

What is the formal statement of the dining philosopher's problem? [migrated]

concurrency

modified Nov 30 at 0:32 Bjørn Kjos-Hanssen♦ 3,524

1

vote

1

answer

368

views

Possible to do Complexity theory with only counting and Pigeonhole

cc.complexity-theory reference-request big-picture big-list proofs

modified Nov 21 at 12:42 Brout 4,035

1

vote

0

answers

44

views

Ordering tours in a Euclidean TSP according to (strictly) increasing length

tsp

modified Dec 1 at 18:52 axplusbu 6

1

vote

0

answers

40

views

how to achieve a topological sort of an given sequence with minimum swaps

np-hardness sorting

asked Nov 29 at 15:28 user51340 6

0

votes

0

answers

59

views

Function theory and functonal analysis in Computer science

soft-question

asked Nov 28 at 11:11 butskhrikidze 9

6

votes

1

answer

154

views

Does Max Planar 3-SAT admit a PTAS?

reference-request complexity-classes approximation-algorithms approximation-hardness planar-graphs

answered Nov 20 at 15:14 Gamow 3,834

Top Questions

Looking for more? Browse the complete list of questions, or popular tags. Help us answer unanswered questions.