Hottest Questions This Month

19

votes

1

answer

1k

views

Has parameterized complexity led to better algorithms?

answered Oct 2 at 11:42 Christian Komusiewicz 1,510

7

votes

1

answer

227

views

Complexity Theory Consequences of $\mathsf{NP} = \mathsf{QP}$

cc.complexity-theory

answered Oct 1 at 19:57 Emil Jeřábek 12.1k

8

votes

1

answer

165

views

On the usage of Arora and Barak's main lemma in their proof of the PCP theorem

cc.complexity-theory

modified Oct 15 at 22:13 Andrew Kelley 183

3

votes

1

answer

218

views

Can the halting problem be solved probabilistically? [closed]

randomized-algorithms derandomization decidability halting-problem

modified Oct 20 at 12:15 Emil Jeřábek 12.1k

3

votes

1

answer

108

views

Number of maximal cliques in a ($2C_4$, $C_5$, $P_5$)-free graph

reference-request graph-theory clique

modified Oct 12 at 23:57 padawan 93

7

votes

1

answer

284

views

How fast is an equivalent 2-tape TM compared to a $O(n^2)$ 1-tape TM?

turing-machines universal-turing-machines

modified Oct 8 at 13:43 Marzio De Biasi 21.6k

5

votes

1

answer

171

views

Is there an equivalent to VC-dimension for density estimation as opposed to classification?

machine-learning lg.learning st.statistics vc-dimension

modified Oct 22 at 8:21 Aryeh 8,544

5

votes

1

answer

67

views

Series-parallel DAG characterization

graph-theory

modified Oct 2 at 8:31 Emil Jeřábek 12.1k

2

votes

1

answer

101

views

What graphs on $\mathbb{N}$ can be encoded as regular languages?

complexity-classes fl.formal-languages pl.programming-languages regular-language regular-expressions

answered Oct 21 at 2:39 isaacg 710

3

votes

1

answer

205

views

Two different graph densities: $|E|/|V|$ and $|E|/(|V|-1)$

graph-theory

modified Oct 15 at 0:08 Chao Xu 4,104

5

votes

1

answer

60

views

Upperbound for max degree of k-tree completion

graph-theory

modified Oct 9 at 6:52 daniello 2,991

2

votes

1

answer

95

views

Complexity of type inference in the simply typed lambda calculus

complexity-classes typed-lambda-calculus

answered Oct 2 at 7:21 Noam Zeilberger 4,073

1

vote

1

answer

120

views

Which are the best universities for a DPhil/PhD in proof theory and automated reasoning?

soft-question career

answered Oct 15 at 23:04 Bartosz Bednarczyk 502

2

votes

1

answer

132

views

Is modal $\mu$-calculus “equivalent” to bisimulation?

modified Oct 16 at 23:09 Denis 6,557

1

vote

1

answer

76

views

Phonology and lambda calculus

pl.programming-languages lambda-calculus functional-programming

modified Oct 17 at 16:15 lemontree 116

2

votes

1

answer

56

views

Is the reduction from a parametrized proplem to the problem kernel just a kind of Karp reduction (polynomial-time reduction)?

parameterized-complexity kernelization

answered Oct 18 at 0:30 daniello 2,991

3

votes

1

answer

86

views

Decomposing Single Crossing Minor Free graphs

graph-theory

answered Oct 1 at 3:30 daniello 2,991

6

votes

1

answer

106

views

The number of clauses in an unsatisfiable CNF

reference-request graph-theory sat

answered 10 hours ago Christian Komusiewicz 1,510

0

votes

1

answer

105

views

VC dimension for balanced binary decision trees

machine-learning vc-dimension

modified Oct 18 at 7:54 Aryeh 8,544

1

vote

1

answer

101

views

Face-splitting product of two Vandermonde matrices: When is is invertible?

linear-algebra matrix-product

modified Oct 7 at 16:00 J.G 610

3

votes

0

answers

162

views

Are Julia sets (theoretically) Turing-complete?

universal-turing-machines

modified Oct 5 at 6:00 Emil Jeřábek 12.1k

7

votes

0

answers

122

views

Reference for computing the rank of a matrix in polynomial time

cc.complexity-theory reference-request linear-algebra matrices

modified Oct 7 at 14:50 Emil Jeřábek 12.1k

4

votes

0

answers

153

views

Alternative exponential definition of Kolmogorov complexity

lo.logic kolmogorov-complexity

modified Sep 30 at 23:10 Jori 41

-2

votes

1

answer

114

views

+50

How to calculate complexity in a high dimensional space?

cc.complexity-theory optimization machine-learning computational-geometry high-dimensional-geometry

modified Oct 22 at 16:30 user2827214 55

4

votes

1

answer

88

views

Box stacking problem, and variants

dynamic-programming

answered Oct 20 at 4:38 Sariel Har-Peled 9,278

1

vote

0

answers

119

views

Is there an oracle that separates $PH$ from counting classes?

counting-complexity oracles

modified Oct 2 at 8:07 Jan Johannsen 4,479

0

votes

0

answers

110

views

Open problems/Conjunctures in non-uniform complexity if proved would imply P=NP

cc.complexity-theory circuit-complexity

asked Sep 30 at 20:13 user60088 17

3

votes

0

answers

100

views

Fine-grained hardness results on exact computation of matrix multiplication output size

np-hardness approximation-hardness

modified 1 hour ago karmanaut 983

2

votes

1

answer

75

views

Sum-of-Squares Certificates

max-cut sum-of-squares

answered Sep 29 at 22:03 J.G 610

0

votes

1

answer

45

views

Is every countable, finite-branching LTS bisimilar to a tree?

lo.logic model-checking temporal-logic process-algebra mu-calculus

modified Oct 16 at 23:07 Denis 6,557

1

vote

0

answers

92

views

Functional abbreviation for Inst expression in Turing's 1936 paper

lo.logic computability turing-machines

modified Oct 22 at 21:34 Ajax 111

1

vote

0

answers

91

views

reordering a DAG with the minimum changes

np-hardness directed-acyclic-graph topological-sorting

modified Oct 19 at 3:31 2016310588 33

4

votes

0

answers

86

views

A possible error in the semantic chapter of the ISO standard for the Z specification notation

formal-methods denotational-semantics

modified Oct 8 at 18:58 Evan Aad 247

0

votes

1

answer

65

views

Time complexity of finding chain decomposition of partially ordered set

partial-order

answered Oct 16 at 18:56 Gabriel Istrate 131

2

votes

0

answers

82

views

Is there a competitive algorithm for this online scheduling problem to minimize the truncated gaps?

ds.algorithms online-algorithms

modified Oct 12 at 8:35 zdm 275

1

vote

1

answer

29

views

Best approximations of Minimum Dominating Sets in chordal graphs

graph-algorithms approximation-algorithms approximation-hardness

modified Oct 16 at 17:58 daniello 2,991

2

votes

1

answer

60

views

A conjecture on 4-coloring maximal planar graphs

graph-theory planar-graphs graph-colouring

answered Oct 15 at 6:35 Cyriac Antony 941

1

vote

0

answers

76

views

Looking for an online community specializing in the Z specification language, where I can ask questions

reference-request formal-methods

asked Oct 7 at 8:05 Evan Aad 247

1

vote

0

answers

74

views

$\mathit{FO}[+,\times]$ seems more powerful than $\mathit{DLOGTIME}$-uniform $\mathit{AC}^0$?

lo.logic uniformity ac0

modified Oct 23 at 7:54 Emil Jeřábek 12.1k

-3

votes

0

answers

67

views

Are there practical alternatives to the ellipsoid method?

linear-programming

asked Sep 28 at 4:36 user3508551 313

0

votes

0

answers

65

views

Efficient sampling of primes

randomized-algorithms sampling

asked Oct 14 at 22:49 Mahdi Cheraghchi 3,786

1

vote

1

answer

39

views

Separating DAGs using separators consisting of lists of nodes and all ancestors

ds.algorithms graph-theory graph-algorithms ds.data-structures directed-acyclic-graph

answered 15 hours ago daniello 2,991

0

votes

0

answers

62

views

Unambiguous Problems and Classes over Reals

cc.complexity-theory complexity-classes computing-over-reals

modified Oct 21 at 1:07 user3483902 893

8

votes

0

answers

61

views

Forbidden Subgraph Characterization for Graphs with few Maximal Cliques

graph-theory graph-algorithms graph-classes

modified Oct 10 at 23:41 daniello 2,991

1

vote

0

answers

61

views

How does complexity of a counting problem influence wether it admits a closed form formula or not?

counting-complexity first-order-logic

modified Oct 22 at 14:56 SagarM 311

-1

votes

0

answers

58

views

The third method to improve the performance of continued fraction method in Nielsen & Chuang

quantum-computing

modified Oct 9 at 9:20 zhu qinlin 1

0

votes

0

answers

57

views

Is there any second-order logic finite satisfiability checker?

finite-model-theory

asked Oct 17 at 18:50 441Juggler 1

Top Questions

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