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

6

votes

3

answers

180

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

9

votes

4

answers

233

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

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

3

votes

2

answers

296

views

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

cc.complexity-theory complexity-classes time-complexity

modified 15 hours ago Emil Jeřábek 10.4k

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

6

votes

1

answer

453

views

Number of 4 cycles

graph-theory graph-minor

modified 9 hours ago Peter Mortensen 105

8

votes

1

answer

290

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

6

votes

2

answers

226

views

Algorithm for identifying unprovable statements

ds.algorithms computability

modified Oct 1 at 8:56 Ted 234

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

6

votes

1

answer

270

views

Proof techniques for showing that dependent type checking is decidable

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

modified Oct 12 at 20:38 Łukasz Lew 641

5

votes

1

answer

137

views

Sets of solutions which it is hard to uniformly sample from, but easy to integrate functions over? (Or compute expectations over?)

counting-complexity randomness probabilistic-computation probabilistic-complexity

modified Sep 17 at 5:32 D.W. 7,341

7

votes

1

answer

175

views

TIME(n) versus TIME(nlogn)

cc.complexity-theory time-complexity

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

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

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

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

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

6

votes

1

answer

116

views

Is algorithmic information theory still evolving?

cc.complexity-theory it.information-theory

modified yesterday Bjørn Kjos-Hanssen♦ 3,227

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

0

answers

208

views

L/quasipoly vs NL/poly

cc.complexity-theory

modified Oct 4 at 2:27 Hiroki Morizumi 409

4

votes

1

answer

138

views

What is the etiquette of naming concepts after people?

soft-question terminology

answered Sep 23 at 21:46 Rob 121

6

votes

0

answers

156

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

5

votes

0

answers

111

views

Optimal set union tree

optimization tree binary-trees set-system

modified yesterday AmeerJ 307

1

vote

0

answers

138

views

Automated theorem proving PhD

soft-question

asked Oct 9 at 8:33 mip 9

9

votes

0

answers

96

views

Do Banach spaces and linear contraction maps form a model of ILL with an exponential?

lo.logic linear-algebra ct.category-theory topology linear-logic

modified Sep 19 at 14:21 Neel Krishnaswami 25.9k

3

votes

1

answer

94

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

-1

votes

0

answers

119

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

1

answer

92

views

Circuit complexity of group actions

circuit-complexity gr.group-theory

answered Sep 29 at 22:01 Joshua Grochow 29.9k

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

87

views

Relatively low ambitious frontiers

cc.complexity-theory soft-question quantum-computing

asked Oct 12 at 7:37 Avi Tal 336

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

5

votes

0

answers

74

views

Parsimonious Reduction from Unique-3SAT to NAE-3SAT

cc.complexity-theory counting-complexity

asked Sep 24 at 21:10 Sayan Bandyapadhyay 141

1

vote

1

answer

57

views

Color shifting in a bipartite graph

graph-algorithms graph-colouring scheduling bipartite-graphs

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

2

votes

0

answers

86

views

Complexity of solving a polynomial equation

time-complexity polynomials

asked Sep 26 at 9:51 Ludovic Zenohate Lagouardette 16

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

-2

votes

0

answers

68

views

Converting a propositional formula into an equisatisfiable CNF

cc.complexity-theory

asked Sep 26 at 3:43 HueHue 1

4

votes

0

answers

66

views

Complexity of fractional SAT

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

asked 2 days ago Dmytro Taranovsky 1,355

2

votes

1

answer

65

views

About a pre-processing step for primal–dual weighted set cover problem

approximation-algorithms set-cover

modified Sep 25 at 16:34 Neal Young 4,209

7

votes

0

answers

50

views

Complexity of deciding whether subspaces of Z_2^n cover every point 3*x times

cc.complexity-theory np-complete algebra algebraic-complexity covering-problems

asked Sep 25 at 15:57 user50712 36

3

votes

0

answers

64

views

How many arithmetic and max operations does it take to compute Dynnikov's action of the braid groups on $\mathbb{Z}^{2n}$?

circuit-complexity gr.group-theory arithmetic-circuits

modified Sep 22 at 2:14 35093731895230467514051 374

0

votes

0

answers

63

views

Partitioning directed graph

graph-theory graph-algorithms

modified Sep 21 at 9:02 Gil 1

-1

votes

0

answers

63

views

Quantum attack on classical hash functions [on hold]

quantum-computing hash-function

modified Oct 12 at 11:08 user1936752 99

1

vote

1

answer

48

views

Sample complexity for learning Boltzmann Distribution parameters

machine-learning sample-complexity pac-learning

answered Oct 10 at 14:37 Aryeh 4,936

0

votes

0

answers

56

views

Proving that a problem is coNP-complete [closed]

cc.complexity-theory np-hardness complexity-classes

asked Sep 25 at 14:23 RTK 82

-2

votes

0

answers

52

views

Equivalence relations with DFAs [closed]

dfa equivalence

asked Oct 9 at 22:18 ucdsmiles1010 1

-2

votes

0

answers

51

views

Is this proof system stronger than resolution?

lo.logic sat proof-complexity proof-theory resolution

modified Sep 19 at 22:36 RTK 82

-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

1

vote

1

answer

30

views

Soft Truth Values in the PSL model

lo.logic soft-question probabilistic-computation

answered Sep 20 at 14:30 Shaull 3,043

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