Hottest Questions This Month

4

votes

2

answers

207

views

Density of semantics in syntax

answered Feb 26 at 15:58 Noam Zeilberger 4,141

4

votes

1

answer

138

views

Is $UL\neq PSPACE$ known?

space-complexity hierarchy-theorems

answered Feb 25 at 6:39 William Hoza 1,488

12

votes

2

answers

143

views

Is the exponent in the rectangular matrix multiplication convex?

ds.algorithms time-complexity matrix-product

modified Feb 27 at 15:58 Emil Jeřábek 12.8k

10

votes

1

answer

129

views

It is known that $L \subsetneq PH$?

oracles polynomial-hierarchy logspace

answered Feb 19 at 14:16 Ryan Williams 25.7k

8

votes

2

answers

185

views

Are there analogous works to PPSZ algorithm for #P?

sat counting-complexity

answered Feb 20 at 18:34 Giorgio Camerani 6,515

9

votes

1

answer

179

views

Is the Triangle Finding decision problem in $coNTIME(\tilde{O}(n^2))$?

cc.complexity-theory ds.algorithms graph-algorithms time-complexity nondeterminism

modified Feb 19 at 19:22 Michael Wehar 4,693

6

votes

1

answer

157

views

Impredicativity + large eliminations (with no excluded middle) in Coq

dependent-type coq

answered Mar 4 at 15:46 Stefan 332

5

votes

1

answer

176

views

Where is $MA$ more relevant than $\exists BPP$?

complexity-classes promise-problems probabilistic-complexity

answered Feb 8 at 9:19 Emil Jeřábek 12.8k

4

votes

1

answer

127

views

Is $GCT$ necessarily a negative result program?

cc.complexity-theory ds.algorithms big-picture algebraic-complexity symmetry

answered Feb 19 at 4:16 Joshua Grochow 34.1k

2

votes

2

answers

93

views

Partitioning a connected polygon into connected pieces of equal area

cg.comp-geom partition-problem polygon

answered Feb 24 at 7:55 David Eppstein 49.3k

6

votes

1

answer

93

views

Random Cerny Conjecture

graph-theory automata-theory dfa random-walks

answered Mar 1 at 21:45 domotorp 13.2k

0

votes

2

answers

117

views

Minimum number of triangles required to cover a complete graph?

graph-theory covering-problems vertex-cover

answered Feb 24 at 16:33 Peter Shor 23k

5

votes

1

answer

85

views

Is the Mendler-encoding in System-F adequate?

type-systems typed-lambda-calculus encoding

answered Mar 2 at 3:38 Dan Doel 511

3

votes

1

answer

103

views

$ACC^0$ implementation of a boolean function

circuit-complexity boolean-functions

answered Mar 1 at 8:35 Kristoffer Arnsfelt Hansen 4,015

1

vote

1

answer

123

views

Effect of self loops on mixing time?

graph-theory pr.probability markov-chains random-walks

answered Feb 12 at 23:59 Yuval Peres 336

3

votes

1

answer

105

views

A stronger Flow Decomposition Theorem?

graph-theory graph-algorithms network-modeling flow-problems

modified Feb 21 at 11:15 Kristoffer Arnsfelt Hansen 4,015

0

votes

1

answer

129

views

Comparing SAT to MCSP reduction class separations and faster SAT class separations?

cc.complexity-theory complexity-classes sat lower-bounds logspace

answered Feb 12 at 14:27 Ryan Williams 25.7k

3

votes

0

answers

197

views

Are CCS and CSP still worth studying?

pl.programming-languages concurrency

modified Feb 23 at 15:48 Lev Reyzin♦ 11.5k

1

vote

2

answers

71

views

Name of this graph partitioning problem? (related to coloring)

reference-request graph-theory graph-algorithms graph-colouring partition-problem

answered Mar 1 at 9:46 Jukka Suomela 11.1k

4

votes

1

answer

111

views

Is this variant of bitwise cyclic tag Turing-complete?

computability pl.programming-languages universal-computation

answered 2 days ago ais523 121

1

vote

1

answer

137

views

Pursuing Theoretical Computer Science after CS major

cc.complexity-theory quantum-computing

modified Feb 18 at 16:19 Brandon Miles 3

0

votes

1

answer

93

views

A sorting algorithm that uses the minimum comparasions possible

sorting

answered Feb 10 at 16:08 user3209423940248 206

3

votes

1

answer

117

views

How to solve an unification problem on $\mathbb{N}$?

decidability logic-programming

answered Feb 11 at 8:57 임기정 41

7

votes

0

answers

116

views

A variant of transfer learning

reference-request machine-learning

modified Feb 26 at 13:33 Aryeh 8,931

3

votes

1

answer

112

views

What is the best simulation of majority utilizing $\bmod\{2,3,\dots,p\}$ gates?

cc.complexity-theory complexity-classes lower-bounds big-picture ac0

answered Feb 22 at 3:49 Jake 159

4

votes

0

answers

139

views

The graph of problem reductions

cc.complexity-theory complexity-classes soft-question reductions big-list

modified Feb 14 at 21:31 Matthieu Latapy 323

4

votes

0

answers

132

views

What logic do refinement types correspond to?

type-theory dependent-type automated-theorem-proving curry-howard

asked Feb 12 at 12:29 oquechy 41

4

votes

0

answers

125

views

Is this problem in P? Given a bipartite graph, find a minimum cardinality set of edges which intersect every vertex cover

ds.algorithms graph-algorithms np-hardness

modified Mar 4 at 2:05 Karagounis Z 167

-2

votes

1

answer

75

views

Set cover with small subsets [closed]

np-hardness set-cover

answered Feb 15 at 6:31 user3209423940248 206

2

votes

0

answers

116

views

Understanding the Physical Church-Turing thesis and its implications

physics church-turing-thesis

modified Feb 22 at 21:26 Aidan Rocke 287

1

vote

1

answer

89

views

An invariance theorem for algorithmically random data in statistical learning

reference-request machine-learning kolmogorov-complexity

modified Feb 22 at 12:23 Aidan Rocke 287

3

votes

0

answers

107

views

PSPACE-complete under NP reduction

cc.complexity-theory pspace

modified Feb 11 at 10:12 Denis 6,695

5

votes

0

answers

107

views

Does k-Median problem become any easier when L = C?

clustering metric-spaces

modified Feb 25 at 13:55 Hugo Manet 101

1

vote

0

answers

106

views

What is the difference between a model of computation and a programming language?

computability pl.programming-languages concurrency universal-computation

asked Feb 17 at 18:21 Tim 1

0

votes

0

answers

105

views

Bigger collapse and Savitch's theorem?

cc.complexity-theory space-complexity

modified Feb 26 at 15:46 1.. 11.6k

3

votes

1

answer

48

views

Problem conditions to use Laplacian solvers

graph-theory graph-algorithms linear-algebra matrices sparse-matrix

modified Feb 20 at 15:32 Mah 133

2

votes

1

answer

75

views

NP-Completeness of Finding Minimum Automaton, in Gold's paper

automata-theory regular-language minimization

modified Feb 14 at 19:44 Makketronix 146

4

votes

0

answers

89

views

Relationship between SC and NL

cc.complexity-theory space-complexity

asked Feb 6 at 17:29 Anony 41

-2

votes

0

answers

84

views

Are there computable functions of quantum time complexity strictly above polynomial?

cc.complexity-theory quantum-computing time-complexity

asked Mar 2 at 23:12 porton 105

2

votes

0

answers

83

views

Tenth Hilbert problem on interval arithmetic

decidability

modified Feb 9 at 18:58 gigabytes 922

2

votes

0

answers

77

views

The many strengths of PageRank

asked Feb 8 at 7:10 Matthieu Latapy 323

4

votes

0

answers

75

views

Trading treewidth for depth in Boolean circuits

reference-request circuit-complexity treewidth

modified Feb 28 at 13:49 Occams_Trimmer 141

1

vote

0

answers

74

views

On the equivalence of incompressibility and incompleteness in machine learning

machine-learning it.information-theory kolmogorov-complexity

modified Feb 21 at 12:25 Aidan Rocke 287

0

votes

1

answer

56

views

What would be the performance properties of a comb or shell sort where the gap sequence is the prime numbers?

sorting

answered Feb 18 at 23:02 Simply Beautiful Art 111

2

votes

1

answer

55

views

random sampling DAGs via nilpotent matrix sampling

graph-theory directed-acyclic-graph

answered Feb 20 at 12:28 thibo 131

2

votes

0

answers

70

views

Consequences of an $o(\log n)$-approximation algorithm for a $\mathsf{\log\text{-}APX}$ hard problem

complexity-classes approximation-hardness

asked Feb 22 at 22:00 Lamine 1,074

1

vote

0

answers

69

views

Algorithms for finding unique solutions of NP-complete problems

cc.complexity-theory search-problem unique-solution

modified Feb 17 at 19:35 Mohammad Al-Turkistany 20.1k

0

votes

0

answers

69

views

What is the best reduction we know from flavors of $SAT$ to $MCSP$?

cc.complexity-theory complexity-classes circuit-complexity lower-bounds reductions

modified Feb 10 at 8:48 1.. 11.6k

Top Questions

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