Hottest Questions Today

2

votes

1

answer

19

views

Finding the single-crossing embedding of a single-crossing graph

answered 3 hours ago Tim 451

0

votes

0

answers

13

views

Is p-dimensional matching with (p−1)n edges NP-hard? What about 3n edges?

asked 3 hours ago Ernie Vigelan 1

4

votes

2

answers

168

views

What's the categorical semantics of definitional equality?

type-theory dependent-type semantics

modified yesterday András Kovács 999

3

votes

0

answers

65

views

An NP-hard Hidden Subgroup Problem

cc.complexity-theory np-hardness hiddensubgroupproblem

modified yesterday Shaull 4,795

3

votes

0

answers

60

views

Problem in the paper “Stable Minimum Space Partitioning in Linear Time”

ds.algorithms space-complexity

modified 2 days ago Emil Jeřábek 13.4k

0

votes

0

answers

51

views

What is few-shots extrapolation? [migrated]

machine-learning

modified Jul 26 at 16:05 user253751 101

0

votes

0

answers

11

views

Linear auto-encoders and PCA with unequal input-output

semidefinite-programming

asked Jul 26 at 15:55 qwerty43 1

0

votes

1

answer

81

views

An (unusual?) risk bound

machine-learning lg.learning st.statistics pac-learning

modified 8 hours ago Emil Jeřábek 13.4k

0

votes

0

answers

75

views

Interpreatation of if..then in terms of recursive function? [closed]

recursive

asked Jul 23 at 15:46 EarthIsNotFlat 9

4

votes

1

answer

126

views

Does this notion of entropy have a name?

reference-request it.information-theory shannon-entropy

answered Jul 22 at 20:34 Mahdi Cheraghchi 3,876

16

votes

4

answers

4k

views

Reviewing a paper and found a better solution

soft-question paper-review

answered Jul 13 at 10:31 Thomas Ahle 768

0

votes

0

answers

35

views

Permutation compositions with $n$-cycles [closed]

gr.group-theory

asked Jul 23 at 12:40 withhighprob 345

1

vote

0

answers

69

views

“Search and Replace” Edit Distances

edit distance levenshtein plagiarism

asked Jul 21 at 18:16 Jeremy 2,341

-3

votes

0

answers

117

views

BPP version of a problem related to #P completeness

cc.complexity-theory counting-complexity randomness

asked Jul 21 at 1:58 PP vs BPP 1

0

votes

1

answer

94

views

Does an upper bound on the integrality gap imply an approximation algorithm with the same ratio?

co.combinatorics approximation-algorithms optimization linear-programming

answered Jul 18 at 3:36 Chandra Chekuri 6,325

0

votes

0

answers

98

views

Characterization of sublinear time [closed]

cc.complexity-theory complexity-classes time-complexity

asked Jul 19 at 16:31 abrahimladha 65

6

votes

3

answers

1k

views

How does type theory change how one thinks about programming?

pl.programming-languages type-theory dependent-type

answered Jul 12 at 17:03 Corbin 123

-1

votes

0

answers

47

views

Concentration bounds for hypergeometric distribution

pr.probability randomized-algorithms randomness

asked Jul 19 at 19:36 Sudipta Roy 169

1

vote

1

answer

100

views

Communication complexity of reconstructing a random bit-string of length $n$

reference-request communication-complexity

answered Jul 16 at 3:45 D.W. 9,903

1

vote

0

answers

80

views

Where does “Quine's Method” in propositional logic originate?

lo.logic

modified Jul 17 at 1:34 Joshua Crotts 11

2

votes

2

answers

219

views

How to acknowledge answers of TCS in the paper?

soft-question

modified Jul 8 at 9:45 Aryeh 9,492

-1

votes

0

answers

60

views

A variant of “hypergeometric” distribution

pr.probability randomized-algorithms

asked Jul 17 at 1:16 Sudipta Roy 169

2

votes

1

answer

118

views

Minimum cut with size bounds $k\leq |S| \leq |V|-k$

cc.complexity-theory max-flow-min-cut max-cut

modified Jul 16 at 16:18 Mohammad Al-Turkistany 20.3k

2

votes

1

answer

138

views

Coloring intersection graph of squares

graph-theory graph-algorithms np-hardness graph-colouring interval-graphs

modified Jul 14 at 10:24 Saeed 3,410

1

vote

1

answer

156

views

Can you embed a Turing Machine into the Pi calculus with just one replication operator?

process-algebra pi-calculus

answered Jul 15 at 1:49 Timothy 31

10

votes

1

answer

208

views

Succinctness of regular expressions with empty word

reference-request regular-expressions

modified Jul 9 at 10:40 Hermann Gruber 5,214

0

votes

0

answers

50

views

Examples of SDP constant approximation algorithms on minimisation problems

approximation-algorithms optimization semidefinite-programming

modified Jul 15 at 20:28 Rodrigo de Azevedo 227

3

votes

1

answer

113

views

Fixed points of fixed-point combinator?

lambda-calculus fixed-points

answered Jul 10 at 20:46 Damiano Mazza 4,488

5

votes

1

answer

242

views

Is coRE closed under concatenation?

computability turing-machines

answered Jul 6 at 15:35 Denis 7,240

-1

votes

0

answers

82

views

Expected number of node visits during random walk

graph-theory graph-algorithms markov-chains random-walks

modified Jul 13 at 20:07 user12878817821 1

1

vote

0

answers

63

views

What is this structure? (monad with a kind of partial inverse comonad)

monad comonad

modified Jul 14 at 21:22 user175348 111

5

votes

1

answer

118

views

Commutative operation benefits

algebra compilers term-rewriting-systems

answered Jul 9 at 1:38 Robert Andrews 578

-1

votes

0

answers

49

views

Expected node probability after finite random walk

graph-theory markov-chains random-walks network-modeling

modified Jul 14 at 4:22 user12878817821 1

-2

votes

0

answers

67

views

Solving Feedback vertex set using dynamic programming on nice tree decomposition

parameterized-complexity treewidth dynamic-programming

modified Jul 11 at 20:22 Hermann Gruber 5,214

-3

votes

0

answers

63

views

Would this type of circular reference problem be in P or NP?

cc.complexity-theory np polynomial-time

asked Jul 11 at 9:22 Anders Gustafson 95

5

votes

0

answers

215

views

$\#$P hardness of computing weighted sum of degree $2$ polynomials

cc.complexity-theory counting-complexity approximation-hardness polynomials finite-fields

modified Jul 10 at 18:21 AngryLion 51

1

vote

0

answers

48

views

Failing to understand a lemma regarding Robust Low Rank Approximation

approximation-algorithms randomized-algorithms clustering

asked Jul 11 at 21:44 Sudipta Roy 169

2

votes

0

answers

77

views

Result showing that DTIME[T] is strictly contained in random-access NTIME[T]

cc.complexity-theory nondeterminism

asked Jul 9 at 23:15 exfret 623

5

votes

1

answer

92

views

$\eta$-reduction not locally confluent on well-typed terms

type-theory lambda-calculus

modified Jul 1 at 10:14 Neel Krishnaswami 31k

1

vote

1

answer

55

views

Treewidth of monotone graph classes with bounded cliquewidth

treewidth graph-classes monotone cliquewidth

modified Jul 23 at 10:04 Community♦ 1

3

votes

1

answer

180

views

$\rho OPT + k$ approximation for bin packing (Unpublished result of David P. Williamson)

np-hardness approximation-algorithms packing extremal-combinatorics chernoff-bound

modified Jul 22 at 1:00 Community♦ 1

2

votes

2

answers

145

views

What is the point of the eliminator for the unit type?

type-theory

modified Jul 4 at 15:20 ice1000 725

2

votes

0

answers

62

views

Complexity of (Graph) Ramsey Theorem in Sum-of-Squares Proof System

reference-request sum-of-squares ramsey-theory

asked Jul 8 at 13:02 Occams_Trimmer 161

-2

votes

0

answers

38

views

How hard is this special 3-partition problem?

np-hardness co.combinatorics np-complete proofs partition-problem

asked Jul 10 at 6:39 Rise of Kingdom 53

-1

votes

0

answers

31

views

Simple Reduction from ILP to slightly modified Integer Minimisation Problems?

cc.complexity-theory linear-programming reductions

asked Jul 9 at 10:35 Isaac 1

Top Questions

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