Theoretical Computer Science Stack Exchange is a question and answer site for theoretical computer scientists and researchers in related fields. Join them; it only takes a minute:

Sign up

Here's how it works:

Anybody can ask a question
Anybody can answer
The best answers are voted up and rise to the top

Top Questions

active hot week month

0

votes

0

answers

13

views

Weighted Set Cover with Consecutive Ones Property

np-hardness set-cover

asked 1 hour ago mnmp 38

2

votes

2

answers

51

views

Is there a non-deterministic version of the complexity class PP?

cc.complexity-theory complexity-classes time-complexity

answered 54 mins ago Emil Jeřábek 10.3k

4

votes

1

answer

72

views

Is algorithmic information theory still evolving?

cc.complexity-theory it.information-theory

modified 12 hours ago Bjørn Kjos-Hanssen♦ 3,217

1

vote

0

answers

25

views

Average margin bounds for separable SVM

machine-learning lg.learning st.statistics svm

asked 18 hours ago Aryeh 4,936

4

votes

0

answers

45

views

Complexity of fractional SAT

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

asked yesterday Dmytro Taranovsky 1,355

4

votes

0

answers

102

views

Optimal set union tree

optimization tree binary-trees set-system

modified 16 hours ago AmeerJ 302

6

votes

1

answer

250

views

Proof techniques for showing that dependent type checking is decidable

reference-request pl.programming-languages type-theory dependent-type typed-lambda-calculus

modified 2 days ago Łukasz Lew 641

6

votes

0

answers

76

views

Relatively low ambitious frontiers

cc.complexity-theory soft-question quantum-computing

asked Oct 12 at 7:37 Avi Tal 336

-1

votes

0

answers

60

views

Quantum attack on classical hash functions [on hold]

quantum-computing hash-function

modified 2 days ago user1936752 99

-1

votes

0

answers

25

views

Recovering full ordering from partial ordering [on hold]

partial-order total-ordering

asked Oct 11 at 22:19 Daniel 490

-1

votes

0

answers

26

views

What is the correspondence between the category theory and the tree structure? [on hold]

ct.category-theory

asked Oct 11 at 17:02 ruby_object 99

1

vote

1

answer

43

views

Sample complexity for learning Boltzmann Distribution parameters

machine-learning sample-complexity pac-learning

answered Oct 10 at 14:37 Aryeh 4,936

1

vote

0

answers

136

views

Automated theorem proving PhD

soft-question

asked Oct 9 at 8:33 mip 9

-2

votes

0

answers

51

views

Equivalence relations with DFAs [closed]

dfa equivalence

asked Oct 9 at 22:18 ucdsmiles1010 1

0

votes

0

answers

27

views

Efficient topological sorting of the cartesian product of DAGs

graph-algorithms directed-acyclic-graph

asked Oct 9 at 17:58 Maxou 1

4

votes

1

answer

153

views

Boolean circuits which correspond to L/poly

cc.complexity-theory reference-request complexity-classes circuit-complexity space-bounded

modified Oct 8 at 8:11 Jan Johannsen 3,790

-2

votes

0

answers

50

views

$L_1= \{\langle M\rangle \mid $ there exists $x \in \Sigma^*$ such that for every $y \in L(M), xy \notin L(M)\}.$ [closed]

fl.formal-languages decidability undecidability

asked Oct 8 at 16:38 Mk Utkarsh 1

6

votes

0

answers

153

views

How many different proofs are there of parity is not in AC0?

cc.complexity-theory circuit-complexity circuit-depth parity ac0

modified Oct 9 at 19:08 Hermann Gruber 3,755

-1

votes

0

answers

117

views

Is there a $O(n\frac{\log{n}}{\log{k}})$ sorting algorithm? [closed]

ds.algorithms sorting

modified Oct 7 at 15:46 Bhishmaraj 3

-2

votes

0

answers

34

views

Does anybody know worth reading papers on “How computers (software's) can help in eradicating corruption at every place”? [closed]

machine-learning cr.crypto-security pr.probability randomized-algorithms ai.artificial-intel

asked Oct 8 at 10:12 bhagwanparge 100

9

votes

4

answers

232

views

Example where equivalence is easy but finding class representative is not

cc.complexity-theory

answered Sep 29 at 23:13 Joshua Grochow 29.9k

2

votes

3

answers

156

views

Is it reasonable to allow the type of a λ/∀-bound variable to refer to itself?

type-theory calculus-of-constructions

answered Oct 1 at 14:04 Stefan 188

-3

votes

0

answers

39

views

Is bounded-error quantum polynomial time (BQP) class can be polynomially solved on machine with discrete ontology?

quantum-computing

asked Oct 6 at 18:06 Peter Zagubisalo 1

-2

votes

0

answers

42

views

Notations used in type theory and in particular in “Practical foundations for programming languages” [closed]

type-theory notation

asked Oct 6 at 13:27 Vincent 176

6

votes

2

answers

224

views

Algorithm for identifying unprovable statements

ds.algorithms computability

modified Oct 1 at 8:56 Ted 234

8

votes

0

answers

208

views

L/quasipoly vs NL/poly

cc.complexity-theory

modified Oct 4 at 2:27 Hiroki Morizumi 409

1

vote

1

answer

55

views

Color shifting in a bipartite graph

graph-algorithms graph-colouring scheduling bipartite-graphs

answered Oct 3 at 23:43 Mikhail Rudoy 1,923

0

votes

0

answers

40

views

Function that maps non-linear distribution to normal distribution while maintaining distance

machine-learning st.statistics

modified Oct 5 at 18:10 Bjørn Kjos-Hanssen♦ 3,217

3

votes

1

answer

93

views

Does a non-constructive proof of bounds of a computable asymptotic complexity, with impossible fix, exist?

cc.complexity-theory time-complexity

modified Oct 4 at 7:25 Jan Johannsen 3,790

7

votes

1

answer

171

views

TIME(n) versus TIME(nlogn)

cc.complexity-theory time-complexity

answered Sep 29 at 16:52 Dmytro Taranovsky 1,355

-3

votes

0

answers

40

views

Is the complement of an unambiguous context-free language (UCFL) context-free? [closed]

fl.formal-languages context-free

asked Oct 4 at 10:19 Lorenzo 100

8

votes

1

answer

286

views

Is it a bad idea to critique someone's paper in my first publication?

soft-question research-practice conferences journals

modified Sep 23 at 17:17 user3508551 167

2

votes

0

answers

25

views

Heuristics for exact #3COLORING close to the 3-colorability threshold

counting-complexity graph-colouring

asked Oct 3 at 15:24 delete000 360

2

votes

0

answers

72

views

Counting the maximum number of paths of length $n$ that differ in at least $k$ edges

graph-algorithms np-hardness approximation-algorithms

modified Oct 4 at 1:44 user3508551 167

6

votes

3

answers

177

views

Why/when do we ever need transfinite loop variants?

lo.logic computability pl.programming-languages program-verification

answered Sep 17 at 23:22 Dan Doel 276

2

votes

1

answer

91

views

Circuit complexity of group actions

circuit-complexity gr.group-theory

answered Sep 29 at 22:01 Joshua Grochow 29.9k

3

votes

2

answers

141

views

How can AIC converge in the limit when even 2 parameter models can have infinite VC dimension?

machine-learning it.information-theory lg.learning st.statistics vc-dimension

modified Sep 28 at 5:25 Andy 23

6

votes

0

answers

88

views

Efficient quantum algorithm for CLASSICAL FFT

cc.complexity-theory quantum-computing

modified Sep 29 at 18:43 Bassem Khoury 31

6

votes

0

answers

84

views

What's the difference between Moggi's computational metalanguage and Moggi's lambda calculus?

reference-request typed-lambda-calculus monad

asked Sep 29 at 7:02 Potter 31

0

votes

0

answers

27

views

How should a reduction to the Cardinality Constrained Quadratic Knapsack Problem work?

cc.complexity-theory np-hardness reductions

modified Oct 2 at 1:57 Arthur M 4

8

votes

2

answers

236

views

Non-Orthogonal Vectors Problem

cc.complexity-theory ds.algorithms linear-algebra polynomial-time boolean-matrix

modified Sep 18 at 21:54 Michael Wehar 2,514

2

votes

1

answer

148

views

Is there a difference between incompleteness and unknowable? [closed]

computability

modified Sep 22 at 7:48 Andrej Bauer 21k

4

votes

2

answers

134

views

What does the category of RDF models look like in Institution Theory?

modified Oct 1 at 10:29 Henry Story 121

8

votes

1

answer

137

views

How small can be a layered boolean circuit for a function with circuit complexity $s$?

circuit-complexity circuits

modified Sep 28 at 19:53 Geoffroy Couteau 263

3

votes

1

answer

93

views

Integer programming: enforce the constraint that a subgraph contains at most $k$ connected components?

integer-programming

modified Oct 2 at 9:17 Mark 148

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

Theoretical Computer Science Stack Exchange works best with JavaScript enabled