Hottest Questions This Month

15

votes

7

answers

3k

views

In the neutral zone between polynomial and sub-exponential

cc.complexity-theory

modified Jun 24 at 7:03 Dominic van der Zypen 679

13

votes

3

answers

340

views

“Refined” list of open problems in TCS

answered Jun 24 at 11:28 Damiano Mazza 4,138

12

votes

2

answers

332

views

Complexity relative to the graph of the Busy-Beaver function

cc.complexity-theory computability

modified Jul 6 at 14:49 Denis 6,432

6

votes

2

answers

364

views

Implication of solving 3SUM problem of a certain size on the Exponential Time Hypothesis

cc.complexity-theory ds.algorithms time-complexity

answered Jul 11 at 15:44 Avi Tal 1,074

6

votes

2

answers

186

views

3SUM Complexity—A special(?) Case

cc.complexity-theory ds.algorithms time-complexity

answered Jul 12 at 1:25 Gary Hoppenworth 31

1

vote

1

answer

122

views

How come Wikipedia says that Random Turing Machines can provide uncomputable output?

computability turing-machines randomness

modified Jun 30 at 17:28 D.W. 9,113

3

votes

1

answer

145

views

Why would the term “dynamically typed” be considered a misnomer?

pl.programming-languages type-theory type-systems

modified Jun 27 at 21:31 Hermann Gruber 4,624

5

votes

1

answer

119

views

An efficient Beta-Equivalence algorithm?

lambda-calculus typed-lambda-calculus

modified 20 hours ago Damiano Mazza 4,138

2

votes

1

answer

141

views

Why do people bring real-life Quantum Computing to the discussion of the Church-Turing thesis?

fl.formal-languages grammars church-turing-thesis

answered Jun 29 at 16:08 Mark 498

4

votes

1

answer

170

views

Should one study undergrad TCS materials before taking grad-level ones? (soft question)

soft-question

answered Jun 28 at 19:46 Avi Tal 1,074

1

vote

1

answer

131

views

What is the complexity of this submatrix selection problem?

ds.algorithms linear-algebra

modified Jul 6 at 12:52 Neal Young 6,025

4

votes

1

answer

208

views

Can modern SAT-Solvers utilise the symmetry of First Order Logic?

sat first-order-logic

answered Jul 7 at 21:15 HolKann 121

5

votes

1

answer

71

views

Complexity of computing the union of H-polytopes in three dimensions

reference-request computational-geometry convex-geometry

answered Jun 29 at 9:33 Gamow 5,297

3

votes

1

answer

132

views

Are all RegExp solvable in O(n)?

complexity-classes regular-expressions

answered Jun 18 at 23:25 Armin 213

-1

votes

1

answer

97

views

What evidences are there that $PP$ is in $BQP$ and $PP$ is not in $BQP$?

cc.complexity-theory quantum-computing counting-complexity big-picture big-list

answered Jul 9 at 3:55 blademan9999 156

5

votes

1

answer

122

views

Good Survey paper for k-means/k-median/k-center/facility-location

reference-request approximation-algorithms approximation-hardness clustering

answered Jul 9 at 4:14 Inuyasha yagami 615

1

vote

1

answer

85

views

On the paper “Quantum Computing Hamiltonian cycles”

graph-theory np-hardness quantum-computing hamiltonian-paths

answered Jun 23 at 16:45 joro 1,817

5

votes

0

answers

169

views

Has there been any development of complexity theory for other Turing degrees than 0?

cc.complexity-theory computability

modified Jun 22 at 13:19 Gro-Tsen 273

0

votes

0

answers

180

views

Add edges to a DAG to maximize increase in number of connected vertices

ds.algorithms

modified Jun 21 at 11:17 A_Theory 45

1

vote

1

answer

108

views

What kind of computational model is the brain? [duplicate]

automata-theory computability turing-machines model-theory

answered Jun 26 at 5:41 Mahdi Cheraghchi 3,594

2

votes

1

answer

99

views

Who proved that a triangulation is 3-colourable implies its dual is bipartite

graph-theory planar-graphs graph-colouring ho.history-overview

modified Jul 1 at 10:59 Cyriac Antony 786

0

votes

1

answer

98

views

What are the worst-case and average-case time complexities of the greedy algorithm for the weighted set cover problem?

approximation-algorithms set-cover average-case-complexity analysis-of-algorithms complexity-theory

modified Jun 27 at 20:45 David Eppstein 48.6k

1

vote

1

answer

94

views

Google quantum supremacy experiment data

quantum-computing

answered Jun 17 at 14:54 smapers 505

4

votes

1

answer

73

views

Lengths of “all-accepted” words in Context Free languages

context-free

modified 19 hours ago Marzio De Biasi 21.4k

0

votes

1

answer

71

views

Minimizing the gaps with incremental capacity

ds.algorithms np-hardness dynamic-programming

modified Jul 6 at 2:56 Neal Young 6,025

4

votes

0

answers

135

views

Is full ownership inference possible?

type-theory

modified Jun 29 at 13:52 Olle Härstedt 145

0

votes

1

answer

95

views

Application of Yao's Minmax Principle for Adaptive Randomized Algorithms

lower-bounds gt.game-theory

answered Jul 3 at 4:11 Avi Tal 1,074

6

votes

0

answers

94

views

Enumerating homologies of disjoint paths

planar-graphs algebraic-topology disjoint-paths spanning-tree

modified Jul 2 at 6:16 kishlaya 191

4

votes

1

answer

94

views

Neighborly properties in a bipartite graph

graph-theory graph-algorithms np-hardness

modified yesterday Laakeri 896

-1

votes

2

answers

105

views

Understanding definition of #P

complexity-theory

answered Jul 9 at 3:12 Watercrystal 217

0

votes

0

answers

97

views

Can you diagnolize without mentioning simulation?

cc.complexity-theory turing-machines enumeration

modified Jun 24 at 19:01 mark 39

1

vote

1

answer

72

views

Data processing inequality for interaction information

it.information-theory

answered Jul 2 at 23:56 Peter Shor 22.7k

0

votes

0

answers

89

views

Where is the scientific contribution “attached” to: the algorithm or the article that describes it, or there are two constributions?

terminology writing

modified Jun 22 at 7:43 verbessern 1

4

votes

0

answers

89

views

Is there any efficient Network stable sort (not bubble sort)?

sorting sorting-network

modified Jun 30 at 13:42 user10556443 41

3

votes

0

answers

76

views

Are there enumerations of machines for all languages in 𝑃 such that there exists a simulator that can efficiently run all the machines enumerated?

cc.complexity-theory polynomial-time enumeration

modified Jun 24 at 1:53 mark 39

-2

votes

1

answer

59

views

Is there an official/academic name for the “current value” in a loop? [closed]

semantics

answered Jul 5 at 23:38 Tyler Hughes 26

-3

votes

0

answers

69

views

Is mathematical proof itself NP-hard?

cc.complexity-theory np-hardness complexity-classes proof-complexity

asked Jun 30 at 16:33 Atsina 103

0

votes

0

answers

69

views

Why is it difficult for GCT to prove super quadratic lower bound?

cc.complexity-theory lower-bounds

asked Jul 1 at 1:41 VS. 509

2

votes

0

answers

68

views

Tail bounds for sum of weighted Poisson random variables

bounds tail poisson

asked Jul 8 at 13:02 Chandra Chekuri 6,016

0

votes

0

answers

63

views

Complete problems for dtime

cc.complexity-theory

asked Jun 30 at 5:01 T.... 11k

2

votes

0

answers

63

views

Is there a fast algorithm for computing the Schmidt decomposition

ds.algorithms matrices

asked Jun 17 at 19:29 Juan 21

1

vote

0

answers

58

views

Quantum error correction and graph codes

graph-theory co.combinatorics quantum-computing coding-theory combinatorics

asked Jun 16 at 16:22 Root 183

3

votes

0

answers

57

views

Complexity of finding the mean of the subset with smallest variance

cc.complexity-theory optimization

asked Jul 11 at 16:50 Andrea 31

-2

votes

1

answer

70

views

Beta reduction and vacuous lambda abstraction [closed]

lambda-calculus typed-lambda-calculus

answered Jul 1 at 9:53 lemontree 114

1

vote

0

answers

54

views

Rewrite relations - proof of correctness

automata-theory regular-language regular-expressions term-rewriting-systems

modified Jun 25 at 11:21 Denis Kyashif 21

1

vote

0

answers

54

views

Constructing FOL formula for which counting is easy?

counting-complexity first-order-logic

modified Jul 10 at 8:55 SagarM 173

3

votes

0

answers

52

views

3-colourability of Eulerian maximal planar graph

graph-theory planar-graphs graph-colouring

modified Jun 22 at 9:57 Gamow 5,297

Top Questions

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