Hottest Questions This Month

9

votes

2

answers

2k

views

“Almost all objects have property P” vs. “It is easy to test whether an object has property P”

cc.complexity-theory pr.probability

answered Jan 21 at 1:01 Acccumulation 223

18

votes

3

answers

493

views

Examples of the value of proofs for algorithms

modified Jan 3 at 18:48 Hermann Gruber 4,299

6

votes

1

answer

345

views

Does the MIP* = RE proof work for limited provers?

interactive-proofs

modified 2 days ago Henry Yuen 3,628

5

votes

1

answer

108

views

Known property? Maximum radius of connected induced subgraph

graph-theory

answered Jan 20 at 13:13 C Komus 729

0

votes

1

answer

163

views

Does two-sided error have more capability than one-sided error?

cc.complexity-theory randomness exp-time-algorithms

answered Jan 11 at 3:38 J.G 436

5

votes

1

answer

183

views

Applications of Barendregt–Geuvers–Klop conjecture

type-theory lambda-calculus

answered Jan 3 at 15:10 cody 12k

5

votes

1

answer

177

views

Latest word on cross validation?

machine-learning lg.learning pac-learning

answered Jan 6 at 8:19 Vitaly 881

4

votes

1

answer

168

views

+100

Are there problems that can be solved in time $2^{n-q^c}$ with $q$ qubits?

cc.complexity-theory quantum-computing tradeoff speed-up

modified yesterday Emil Jeřábek supports Monica 11.2k

2

votes

1

answer

200

views

Prime factorisation of decidable problems

turing-machines kolmogorov-complexity

modified Jan 1 at 11:57 Aidan Rocke 225

6

votes

1

answer

69

views

Determining if a word of specific length exists that is not accepted by a NFA

np-hardness time-complexity nondeterminism nfa

modified Jan 19 at 19:20 D.W. 8,806

3

votes

1

answer

130

views

Convex polygons inclusion relation

ds.algorithms computational-geometry polygon convex-hull

modified Jan 8 at 20:16 David Eppstein 47.5k

0

votes

1

answer

68

views

Is Hamiltonian cycle fixed parameter tractable with parameter clique cover?

cc.complexity-theory graph-theory graph-algorithms

answered 2 days ago Michael Lampis 2,889

3

votes

1

answer

82

views

Meet of integer partitions

partition-problem partial-order

answered Dec 29 '19 at 2:28 Antti Röyskö 551

1

vote

1

answer

122

views

Kolmogorov Complexity of the composition of two computable functions

reference-request kolmogorov-complexity

modified Jan 9 at 10:18 Aryeh 8,048

2

votes

0

answers

172

views

Fast algorithms for evaluating functions with high Kolmogorov complexity

reference-request time-complexity dc.parallel-comp kolmogorov-complexity

modified Jan 16 at 15:20 Aidan Rocke 225

-2

votes

1

answer

91

views

Minimum vertex cover and odd cycles

graph-theory graph-algorithms

answered Jan 15 at 11:04 Laakeri 482

-3

votes

1

answer

84

views

Is this a good definition of computability? [closed]

computability halting-problem formal-modeling church-turing-thesis

modified Jan 16 at 16:40 Shaull 3,931

0

votes

1

answer

65

views

Max flow with restriction of individual flows

max-flow-min-cut max-flow

modified 2 days ago user3508551 287

2

votes

1

answer

82

views

How to choose good diagonals when partitioning an orthogonal polygon into rectangles?

graph-algorithms computational-geometry

modified Jan 11 at 21:50 Thomas Kalinowski 1,026

-2

votes

0

answers

101

views

Proof strategy to show that an algorithm cannot be implemented using just hereditarily terminating procedures

lo.logic pl.programming-languages

modified Dec 30 '19 at 17:21 pyon 487

2

votes

0

answers

95

views

Witness verifiable quantum advantage

cc.complexity-theory quantum-computing ce.computational-finance

asked Dec 29 '19 at 8:33 domotorp 12.4k

1

vote

1

answer

56

views

Data structures for embedded simplicial complexes

ds.data-structures computational-geometry topology

answered Jan 6 at 16:13 gdamiand 136

0

votes

1

answer

70

views

Is the counting version of 1-in-3 Sat #P-complete?

cc.complexity-theory np-hardness counting-complexity

modified Jan 20 at 18:04 Gamow 4,647

2

votes

0

answers

83

views

What is the difference between ${\bf P ^{\bf FewP}}$ and ${\bf UP ^{\bf FewP}}$?

complexity-classes

asked Jan 7 at 15:53 Theodore Payton 21

2

votes

0

answers

83

views

How fast can we perform DFT on a Log-RAM computer?

cc.complexity-theory machine-models

modified Jan 7 at 3:58 Matt Groff 2,041

2

votes

0

answers

83

views

Equational Theories for Type Systems

reference-request pl.programming-languages type-theory

modified Jan 15 at 17:44 Apoorv Ingle 131

2

votes

1

answer

50

views

Does distance-2 coloring fit in Telle and Proskurowski 's algorithm for partial-k trees?

graph-algorithms graph-colouring treewidth

answered 2 days ago M. kanté 966

-1

votes

0

answers

82

views

Finding solution of LP with maximum number of integral values [closed]

ds.algorithms optimization linear-programming convex-optimization

asked Jan 12 at 10:59 user2316602 281

3

votes

0

answers

82

views

Isomorphic subforest problem

cc.complexity-theory ds.algorithms reference-request graph-theory

modified Jan 3 at 2:39 Zachary Hunter 315

3

votes

0

answers

74

views

In quantum money schemes, how is the list of serial numbers provided?

quantum-information

modified Jan 2 at 7:06 Nick Decroos 3

1

vote

0

answers

73

views

Fast Computation of First k Eigenvectors of Graph Laplacian

reference-request graph-theory spectral-graph-theory

modified Jan 15 at 10:47 Arpit Merchant 41

0

votes

0

answers

72

views

NP-Hard Knapsack Instances

np-hardness optimization

asked Jan 18 at 23:54 FiB 141

4

votes

0

answers

70

views

Strong data-processing inequality: bound $TV(T_{\#}P_0,T_{\#}P_1)$ if $\|T(x)-x\|_\infty \le \varepsilon;\forall x \in \mathbb R^p$

pr.probability it.information-theory st.statistics upper-bounds

asked Dec 25 '19 at 14:31 dohmatob 141

-3

votes

0

answers

66

views

How can I prove that a specific structure $\Pi_2$ problem is $\Pi_2$-complete?

cc.complexity-theory polynomial-hierarchy

modified Jan 10 at 10:06 MATH_LI 1

-3

votes

0

answers

64

views

What is the statistical query model? [closed]

machine-learning

asked Jan 4 at 2:14 Ben 1

3

votes

0

answers

61

views

Set:Set or Negative Inductives in a Total Language?

pl.programming-languages type-theory lambda-calculus type-systems dependent-type

modified 16 hours ago Blaisorblade 1,827

-1

votes

0

answers

59

views

What is the formal definition of a data structure?

ds.algorithms ds.data-structures turing-machines formal-modeling definitions

modified Jan 18 at 7:48 Guest 19

-3

votes

0

answers

58

views

Violating the hierarchy theorems mildly

cc.complexity-theory complexity-classes big-picture hierarchy-theorems time-hierarchy

asked Jan 15 at 8:09 T.... 10.8k

-1

votes

0

answers

56

views

What is Undefined Behaviour mapped to with Curry-Howard Correspondence?

proof-theory curry-howard

asked Jan 9 at 11:56 anonymous 1

-2

votes

0

answers

52

views

Undecidable problem involving two TMs [closed]

turing-machines undecidability

asked Jan 18 at 14:56 macao421 11

-1

votes

0

answers

51

views

Is checking time-bounded Kolmogorov complexity of a string claiming to be the shortest string in a certain amount of time EXPTIME?

kolmogorov-complexity exp-time-algorithms

modified Jan 11 at 22:44 Number File 99

4

votes

0

answers

45

views

Computing 3D viewpoint of a set of non-intersecting segments

computational-geometry

modified Jan 15 at 11:36 Shaull 3,931

-1

votes

0

answers

44

views

Parallel Tractability

ds.algorithms complexity-classes dc.parallel-comp

modified Jan 9 at 4:36 Ar1Bis 1

0

votes

0

answers

44

views

Complexity of multi-objective optimization problems

np-hardness optimization time-complexity np-complete complexity

asked Dec 31 '19 at 1:32 Iago Carvalho 175

3

votes

0

answers

41

views

Gradient descent step size for strongly convex functions

optimization convex-optimization

asked Dec 31 '19 at 18:39 Zuza 131

-1

votes

0

answers

40

views

How to determine if two functions give identical outputs given the same input?

formal-systems logical-relations computational-mathematics

asked Dec 30 '19 at 22:51 user55690 1

-2

votes

0

answers

40

views

Y-Combinator implementation, simply typed lambda calculus [closed]

lambda-calculus type-systems typed-lambda-calculus fixpoint

asked Jan 14 at 19:46 Oeto_101 1

Top Questions

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