Hottest Questions Today

0

votes

0

answers

17

views

Complexity of approximating a real function using queries

asked 9 hours ago Erel Segal-Halevi 1,480

1

vote

0

answers

25

views

Complexity of Set Difference

ds.algorithms ds.data-structures time-complexity

asked 21 hours ago tamalet 11

4

votes

1

answer

72

views

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

context-free

modified 18 hours ago Marzio De Biasi 21.4k

0

votes

0

answers

22

views

DAG generation from a subgraph

graph-theory graph-algorithms directed-acyclic-graph

asked yesterday cbro 189

4

votes

1

answer

94

views

Neighborly properties in a bipartite graph

graph-theory graph-algorithms np-hardness

modified yesterday Laakeri 896

0

votes

0

answers

31

views

What is the definition of “soundness” and “completeness” for one algorithm w.r.t. one problem?

definitions soundness

asked yesterday greps 41

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

-3

votes

1

answer

49

views

Diffie Hellman theory [closed]

gr.group-theory

answered 2 days ago Mark 498

5

votes

1

answer

119

views

An efficient Beta-Equivalence algorithm?

lambda-calculus typed-lambda-calculus

modified 19 hours ago Damiano Mazza 4,138

1

vote

0

answers

48

views

Uniquely 4-colorable Maximal Planar Graph Conjecture?

graph-theory planar-graphs graph-colouring

asked Jul 12 at 6:17 Cyriac Antony 786

6

votes

2

answers

184

views

3SUM Complexity—A special(?) Case

cc.complexity-theory ds.algorithms time-complexity

answered Jul 12 at 1:25 Gary Hoppenworth 31

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

-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

-1

votes

0

answers

27

views

Online to batch sample complexity. Conservative assumption on online algorithm needed?

machine-learning sample-complexity online-learning

asked Jul 10 at 17:48 Kom kom 1

-3

votes

0

answers

38

views

What exactly is automata theory and formal language? [closed]

fl.formal-languages automata-theory

asked Jul 10 at 6:21 Bisma 1

-1

votes

2

answers

104

views

Understanding definition of #P

complexity-theory

answered Jul 9 at 3:12 Watercrystal 217

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

30

votes

9

answers

3k

views

Any fundamental papers in TCS which were found to be incorrect/wrong later?

soft-question

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

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

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

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

1

vote

0

answers

33

views

Non-rigid isomorphic structures

cc.complexity-theory graph-theory quantum-computing query-complexity

asked Jul 8 at 8:54 Root 183

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

9

votes

3

answers

620

views

Number of connected components of a random nearest neighbor graph?

graph-theory random-graphs

modified Jul 8 at 13:16 Neal Young 6,025

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

-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

-1

votes

0

answers

30

views

Reduce a decision problem to an optimization problem

cc.complexity-theory graph-theory np-hardness reductions graph-colouring

asked Jul 6 at 12:46 BrianH 1

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

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

-1

votes

0

answers

16

views

Universal Generalisation Inference rule over array Proprties

automated-theorem-proving program-verification

asked Jul 6 at 13:40 smxadn23 1

-1

votes

0

answers

23

views

Any reason why Turing Machine would prevail on recursion theory? [migrated]

turing-machines recursion

asked Jul 5 at 17:26 Jérôme Verstrynge 241

5

votes

1

answer

121

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

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

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

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

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

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

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

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

-1

votes

0

answers

39

views

Applied Pi calculus: Evaluation context that distinguishes replication with different restrictions

process-algebra pi-calculus

asked Jul 2 at 21:26 BlockchainThomas 1

13

votes

3

answers

340

views

“Refined” list of open problems in TCS

reference-request big-list open-problem

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

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

1

answer

70

views

Beta reduction and vacuous lambda abstraction [closed]

lambda-calculus typed-lambda-calculus

answered Jul 1 at 9:53 lemontree 114

-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

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

0

answers

63

views

Complete problems for dtime

cc.complexity-theory

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

0

votes

0

answers

37

views

Self Generating Grammars - Does it have to be infinite recursion?

grammars

asked Jun 30 at 22:00 Novicegrammer 141

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

Top Questions

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