Hottest Questions This Month

16

votes

4

answers

4k

views

Reviewing a paper and found a better solution

answered Jul 13 at 10:31 Thomas Ahle 768

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

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

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

5

votes

1

answer

242

views

Is coRE closed under concatenation?

computability turing-machines

answered Jul 6 at 15:35 Denis 7,240

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

4

votes

2

answers

170

views

What's the categorical semantics of definitional equality?

type-theory dependent-type semantics

modified yesterday András Kovács 999

5

votes

1

answer

118

views

Commutative operation benefits

algebra compilers term-rewriting-systems

answered Jul 9 at 1:38 Robert Andrews 578

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

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

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

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

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

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

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

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

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

-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

0

answers

115

views

Is BigInteger-based Brainfuck Turing Complete?

computability pl.programming-languages turing-machines

modified Jun 30 at 8:09 Fabian 23

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

-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

0

votes

1

answer

82

views

An (unusual?) risk bound

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

modified 10 hours ago Emil Jeřábek 13.4k

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

0

votes

0

answers

79

views

How general cost function for $p = \log n$ is the $k$-center cost function?

clustering

modified Jul 5 at 16:04 Inuyasha Yagami 1,258

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

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

1

vote

0

answers

70

views

Parametrization of context-sensitive language in polynomial time

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

modified Jul 6 at 9:03 deryll 11

1

vote

0

answers

69

views

“Search and Replace” Edit Distances

edit distance levenshtein plagiarism

asked Jul 21 at 18:16 Jeremy 2,341

-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

66

views

An NP-hard Hidden Subgroup Problem

cc.complexity-theory np-hardness hiddensubgroupproblem

modified yesterday Shaull 4,795

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

-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

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

-1

votes

0

answers

61

views

A variant of “hypergeometric” distribution

pr.probability randomized-algorithms

asked Jul 17 at 1:16 Sudipta Roy 169

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

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

0

votes

0

answers

49

views

Bound on Set Cover size between multiple families

set-cover

asked Jul 1 at 15:38 SUGYANI MAHAPATRA 1

-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

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

-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

2

votes

1

answer

22

views

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

graph-theory graph-algorithms

answered 4 hours ago Tim 451

0

votes

0

answers

43

views

Low Rank Approximation of a hidden subset

reference-request approximation-algorithms clustering

modified Jul 2 at 9:36 Sudipta Roy 169

1

vote

0

answers

39

views

Modifying sets to minimize the distance among each pair of the mean value of sets

np-hardness approximation-algorithms optimization

modified Jul 7 at 2:49 Refrain 45

-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

Top Questions

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