Hottest Questions This Month

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,824

16

votes

1

answer

562

views

The TOC Blog Aggregator is Offline

soft-question

modified Nov 24 at 6:38 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

8

votes

2

answers

205

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

2

votes

1

answer

227

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

11

votes

1

answer

221

views

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

cc.complexity-theory complexity-classes

modified Nov 23 at 10:24 domotorp 8,729

6

votes

1

answer

150

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,824

7

votes

2

answers

297

views

Are all turing machines paths predictable?

automata-theory turing-machines halting-problem

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

-2

votes

1

answer

157

views

Graduate school for CS theory?

soft-question career

modified Nov 30 at 21:19 someone111 11

6

votes

1

answer

95

views

Time complexity of derivative-based regex matchers

regular-expressions

modified Nov 27 at 13:35 Neel Krishnaswami 26.4k

2

votes

1

answer

83

views

Applications of Christol theorem

co.combinatorics automata-theory

answered yesterday Jeffrey Shallit 6,221

2

votes

1

answer

127

views

A least sized partition of a set under a distance metric

np-hardness computational-geometry

modified Nov 14 at 20:08 Mohsen Ghorbani 50

1

vote

1

answer

66

views

Pulling a graph across a partition

graph-theory graph-algorithms co.combinatorics

answered Dec 2 at 4:39 daniello 2,636

11

votes

0

answers

112

views

Can two-tape read-only Turing machines recognize any recursive language?

cc.complexity-theory computability counter-automata

modified Nov 22 at 9:19 domotorp 8,729

6

votes

1

answer

110

views

General Induction Principle

type-theory dependent-type automated-theorem-proving type-inference

answered Nov 23 at 22:46 MaiaVictor 1,337

9

votes

1

answer

81

views

Is there a method for proving non-regularity of string transformations?

fl.formal-languages

answered Nov 17 at 14:39 Shaull 3,063

2

votes

1

answer

92

views

Stochastic gradient methods and risk of neural nets

optimization machine-learning ai.artificial-intel stochastic-process

answered Nov 19 at 11:22 Aryeh 5,379

1

vote

1

answer

65

views

Cryptography protocols using graph problem instances

graph-theory soft-question cr.crypto-security

answered Nov 29 at 16:38 Adam Smith 898

2

votes

1

answer

82

views

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

machine-learning lg.learning

modified Dec 5 at 11:07 Aryeh 5,379

4

votes

1

answer

71

views

What is the current state of the art in black-box grammar induction?

lg.learning grammars context-free

modified Nov 29 at 16:05 Alexander Clark 56

1

vote

1

answer

110

views

Does every online algorithm has an offline counterpart?

online-algorithms

answered Dec 3 at 15:37 Sandeep Silwal 127

2

votes

0

answers

104

views

Crime prevention using graph theory and machine learning

graph-theory graph-algorithms machine-learning directed-acyclic-graph markov-chains

asked Nov 26 at 12:54 Tfovid 14

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,221

6

votes

0

answers

76

views

About assumptions needed to get convergence of stochastic gradient methods on non-convex objectives

machine-learning lg.learning pac-learning stochastic-process

modified Nov 25 at 5:19 gradstudent 689

9

votes

0

answers

71

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

3

votes

1

answer

42

views

Distinguising between the cases of low or high cover number

approximation-hardness

answered 21 hours ago Sasho Nikolov 16.1k

9

votes

0

answers

67

views

Results in denotational semantics from model theory?

lo.logic denotational-semantics

Nov 26 at 5:06 xuq01 527

-1

votes

1

answer

66

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

4

votes

0

answers

84

views

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

ds.algorithms arithmetic-circuits

modified yesterday Emil Jeřábek 10.4k

4

votes

0

answers

82

views

Naming an algorithm after a copyrighted object

soft-question

asked Nov 24 at 18:43 Aryeh 5,379

3

votes

0

answers

82

views

Why do most 0/1 matrices need linear arithmetic circuits of size $\Omega(n^2/\log(n))$?

lower-bounds arithmetic-circuits monotone

asked Nov 16 at 21:04 jedidreyfus 16

1

vote

0

answers

81

views

Solving the Halting problem for most inputs [closed]

computability turing-machines halting-problem

asked Nov 30 at 17:12 Asvin 112

2

votes

0

answers

79

views

Auction theory - Selling Multiple Items via Social Networks

combinatorial-game-theory mechanism-design

asked Nov 19 at 13:16 cmplx96 111

1

vote

1

answer

61

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

-1

votes

0

answers

76

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

2

votes

1

answer

57

views

Empirical Rademacher averages versus Hoeffdings bound

machine-learning pr.probability lg.learning epsilon-nets

answered Nov 17 at 18:47 Aryeh 5,379

1

vote

0

answers

71

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

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,379

-3

votes

0

answers

70

views

How to compute Girth of a graph using Integer Programming?

optimization linear-programming integer-programming

asked Nov 15 at 6:23 Mike 6

1

vote

1

answer

54

views

What forms of randomness are 'allowed' in FPRASs?

randomized-algorithms randomness

answered Nov 15 at 18:32 D.W. 7,336

4

votes

1

answer

53

views

Is uniform convergence faster for low-entropy distributions?

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

modified 5 hours ago Aryeh 5,379

-3

votes

0

answers

67

views

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

ds.algorithms time-complexity

asked Dec 6 at 23:49 Noah Stebbins 4

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

0

answers

59

views

Complexity class of approximating perfect match count

quantum-computing counting-complexity randomized-algorithms dc.parallel-comp permanent

asked Nov 10 at 13:38 Brout 4,035

0

votes

0

answers

59

views

Function theory and functonal analysis in Computer science

soft-question

asked Nov 28 at 11:11 butskhrikidze 9

1

vote

0

answers

54

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

-1

votes

0

answers

47

views

how to calculate inverse of entropy?

it.information-theory shannon-entropy entropy

modified Nov 30 at 9:57 user1285170 6

1

vote

0

answers

46

views

Why do k min-hashes, instead of one hash where we find the k minimum elements?

approximation-algorithms hash-function

modified Nov 25 at 5:13 Amir 444

Top Questions

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