Hottest Questions This Month

32

votes

4

answers

3k

views

Single author papers against my advisor's will?

soft-question advice-request

modified Apr 17 at 0:34 Anonymous 19

22

votes

2

answers

1k

views

Languages that we cannot (dis)prove to be Context-Free

modified Apr 7 at 17:10 Marzio De Biasi 18.6k

6

votes

2

answers

515

views

What logic correponds via Curry-Howard to a Monad?

lo.logic functional-programming ct.category-theory monad comonad

answered Apr 10 at 15:08 Henry Story 183

10

votes

1

answer

443

views

What is the “question” that programming language theory is trying to answer?

soft-question pl.programming-languages lambda-calculus big-picture combinatory-logic

modified Apr 16 at 9:31 Martin Berger 9,341

8

votes

2

answers

161

views

Intuition Behind Strict Positivity?

reference-request pl.programming-languages type-theory type-systems dependent-type

answered Apr 3 at 6:55 Henning Basold 181

3

votes

1

answer

145

views

Are Turing machines still useful as model of computation?

ho.history-overview

answered Apr 5 at 17:03 jmite 973

0

votes

1

answer

132

views

Does Hadwiger conjecture imply that NP = coNP?

cc.complexity-theory graph-theory

answered Apr 3 at 10:52 Michael Lampis 2,394

16

votes

1

answer

125

views

Is the Set of all Primitive Words a Prime Language?

fl.formal-languages

answered 18 hours ago Klaus Draeger 2,240

0

votes

1

answer

130

views

Number of simple paths between two vertices in a DAG

reference-request graph-theory directed-acyclic-graph shortest-path

answered Apr 10 at 20:25 David Eppstein 45.4k

3

votes

1

answer

135

views

String theory based computations

complexity-classes quantum-computing

answered Apr 12 at 11:19 Peter Shor 21.1k

4

votes

2

answers

157

views

If I know pretty well '(a,b)', I know pretty well 'a', or 'b', or 'a xor b'

cr.crypto-security pr.probability probabilistic-computation

answered Apr 7 at 23:52 usul 5,309

5

votes

1

answer

119

views

Is there a relation between BBH (black box hypothesis) and SETH (strong exponential time hypothesis)?

complexity-classes time-complexity p-vs-np

answered Apr 20 at 20:35 Ryan Williams 22.8k

3

votes

2

answers

134

views

Compactness of domino tilings

co.combinatorics lo.logic computability automata-theory

modified Apr 1 at 6:59 Emil Jeřábek 10.6k

5

votes

1

answer

144

views

Is there a notion of “inevitable reduction?”

reductions semantics term-rewriting-systems

answered Apr 18 at 16:11 cody 11.4k

11

votes

1

answer

296

views

Can one efficiently uniformly sample a neighbor of a vertex in the graph of a polytope?

reference-request np-hardness counting-complexity linear-programming polytope

modified 2 days ago Lorenzo 393

15

votes

0

answers

217

views

Perfect matching of monotone Boolean function with null Euler characteristic

boolean-functions matching monotone

modified Apr 15 at 2:49 Willard Zhan 123

6

votes

1

answer

131

views

Minimum cost cut with discount - what is the complexity?

graph-theory graph-algorithms

modified Apr 5 at 16:29 Chao Xu 3,069

8

votes

1

answer

99

views

Turing Machines as Coalgebras

automata-theory turing-machines algebra automated-theorem-proving

answered yesterday Henning Basold 181

3

votes

1

answer

125

views

How small can extension complexity be?

cc.complexity-theory linear-programming

modified Mar 30 at 16:46 Sasho Nikolov 16.5k

2

votes

1

answer

94

views

Estimating inner product over $[r]^d$

reference-request communication-complexity

modified Apr 11 at 7:24 Clement C. 2,218

3

votes

2

answers

90

views

Data structure for radial orderings of points on the plane

ds.data-structures computational-geometry

modified Apr 2 at 17:33 Chao Xu 3,069

0

votes

1

answer

69

views

Densest k subgraph problem for outerplanar graphs?

graph-theory graph-algorithms planar-graphs

modified Apr 21 at 0:40 ChimiSeanGa 14

5

votes

1

answer

111

views

What will go wrong if a recursive record type has a negative eta rule?

type-theory dependent-type

answered Mar 30 at 21:46 Jesper 211

8

votes

1

answer

127

views

A conjecture related to the Cerny conjecture - counterexample/reference request

fl.formal-languages automata-theory open-problem dfa synchronization

answered Apr 9 at 2:43 Kaarel Hänni 51

6

votes

0

answers

143

views

Largest “non-disturbing” subset in a graph

graph-algorithms

modified Apr 12 at 7:29 Egor Skriptunoff 131

2

votes

1

answer

49

views

Can Isorecursive types capture mutually recursive data types?

type-theory type-inference

answered Apr 9 at 9:07 Andrej Bauer 22k

5

votes

1

answer

119

views

Analogue of $k$-wise independence for other distributions than uniform

reference-request k-wise-independence

modified Apr 11 at 11:04 Clement C. 2,218

0

votes

1

answer

72

views

Are both safety and liveness properties closed under finite intersection?

model-checking temporal-logic

answered Apr 14 at 12:36 Kai 800

6

votes

0

answers

118

views

NP-hardness proof of selecting the ''fittest'' topological sequence of a DAG

np-hardness partial-order topological-graph-theory

modified Apr 17 at 6:51 user51340 39

2

votes

2

answers

114

views

Why can we (apparently) implement CFG parsers only using (N)DFAs?

fl.formal-languages automata-theory context-free grammars parsing

modified 11 hours ago codeandkey 1

3

votes

0

answers

146

views

In light of Raz and Tal's results, what can we say about whether there's a BQP problem for each level of the polynomial hierarchy?

quantum-computing polynomial-hierarchy

modified Apr 14 at 14:42 Mark S 427

2

votes

1

answer

81

views

Robustness to non-uniform randomness vs. one-sidedness

randomized-algorithms randomness property-testing

modified Apr 4 at 20:15 D.W. 7,601

0

votes

1

answer

80

views

Vehicle scheduling

reference-request optimization

answered 2 days ago Chao Xu 3,069

-1

votes

2

answers

62

views

Machine Learning Algorithm To Fill Data Holes

approximation-algorithms machine-learning ai.artificial-intel

answered Apr 18 at 19:48 Anonymous 11

0

votes

0

answers

106

views

Canonical complete problem for $\mathrm{FP}^{\Sigma^p_2}$

cc.complexity-theory complexity-classes polynomial-hierarchy

modified Apr 1 at 15:41 mnajib 6

1

vote

1

answer

47

views

Longest stack-sortable subsequence

ds.algorithms dynamic-programming

answered yesterday David Eppstein 45.4k

4

votes

0

answers

95

views

Arranging letters to make a word in a regular language

cc.complexity-theory ds.algorithms fl.formal-languages regular-language

modified Mar 27 at 9:19 a3nm 3,555

1

vote

1

answer

57

views

Complexity status of the Edge Deletion problem to bounded degree graphs

cc.complexity-theory reference-request graph-algorithms

answered Mar 30 at 13:49 Gamow 4,172

3

votes

0

answers

89

views

What can be some bachelor thesis ideas in Quantum random walks?

quantum-computing project-topic quantum-walk

modified Apr 21 at 21:44 Blue 46

2

votes

0

answers

82

views

Shortest s-t path when is allowed to ignore k weights

ds.algorithms graph-theory graph-algorithms

asked Apr 2 at 20:15 hqztrue 67

4

votes

0

answers

82

views

Is there a history-independent rope data structure?

ds.data-structures

asked Mar 26 at 18:42 Jon Harrop 295

-1

votes

0

answers

76

views

What is the minimum number of bits required to encode $m$ numbers [closed]

it.information-theory automated-theorem-proving

modified Apr 16 at 8:55 user51340 39

2

votes

0

answers

73

views

Finding 3SUM witness when promised a solution

ds.algorithms np-hardness time-complexity

asked Mar 30 at 16:24 karmanaut 480

-1

votes

0

answers

71

views

Is there a pseudorandom number generator that, given infinite memory, has no period?

turing-machines pseudorandom-generators

asked Apr 15 at 17:18 Lennart 1

3

votes

0

answers

70

views

Counting quotient graphs, but not exactly

cc.complexity-theory reference-request graph-theory

modified Apr 17 at 21:37 M.Monet 322

1

vote

0

answers

67

views

Entropy bounds on solutions to problems in BPP and other complexity classes based on entropy demands

cc.complexity-theory ds.algorithms reference-request lower-bounds shannon-entropy

modified Mar 27 at 7:01 Jake 641

1

vote

0

answers

67

views

Is Combinatory Logic (CL) still relevant for programming language theory?

soft-question lambda-calculus big-picture combinatory-logic

asked Apr 17 at 0:28 PhD 2,544

4

votes

0

answers

66

views

$\exists \mathbb R$ and IP

cc.complexity-theory interactive-proofs existential-theory-of-the-reals

asked Apr 21 at 21:44 domotorp 9,182

Top Questions

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