Theoretical Computer Science Stack Exchange is a question and answer site for theoretical computer scientists and researchers in related fields. It only takes a minute to sign up.

Sign up to join this community

Anybody can ask a question

Anybody can answer

The best answers are voted up and rise to the top

Explore our Questions

Ask Question

more tags

Active 1 Bountied Hot Week Month

0

votes

0

answers

9

views

Is there a primal-dual algorithm for the Tree Augmentation Problem or the Cactus Augmentation Problem?

reference-request graph-theory graph-algorithms approximation-algorithms optimization

asked 8 hours ago Karagounis Z 473

-1

votes

0

answers

33

views

The parameterized complexity of proper edge-colored spanning tree

parameterized-complexity treewidth

modified 10 hours ago zhukui bai 1

11

votes

6

answers

17k

views

What is the best text of computation theory/theory of computation?

reference-request soft-question computability books

modified 21 hours ago Sridhar Ratnakumar 101

1

vote

0

answers

36

views

What is the expected treewidth of a large-treewidth graph intersected with Erdos-Renyi graph?

graph-theory treewidth

asked yesterday Artur Riazanov 299

11

votes

1

answer

1k

views

What are the current best known upper and lower bounds on the (un)satisfiability threshold for random k-sat and/or 3-sat?

cc.complexity-theory sat lower-bounds upper-bounds phase-transition

modified yesterday András Salamon 18.5k

38

votes

2

answers

2k

views

Multiplying n polynomials of degree 1

ds.algorithms reference-request open-problem polynomials

modified yesterday Jan Johannsen 4,482

8

votes

0

answers

129

views

Can exponential-size depth-2 $CC^0[m]$ circuits with generalized $MOD_m$ gates compute arbitrary functions from $Z/mZ$ to $Z/2Z$?

circuit-complexity universal-computation

modified yesterday Jake 442

-1

votes

0

answers

37

views

Constructing boolean formula for graph coloring problem

graph-theory graph-colouring

modified yesterday Andy 99

3

votes

1

answer

89

views

star height of star-free languages

fl.formal-languages regular-language regular-expressions monoid

modified 2 days ago Denis 7,410

0

votes

0

answers

34

views

k-Median Problem With Restricted Centers

approximation-algorithms clustering

asked 2 days ago Inuyasha Yagami 1,307

1

vote

1

answer

93

views

Generalization bound for parameters rather than loss functions

machine-learning lg.learning st.statistics vc-dimension pac-learning

modified Oct 18 at 10:00 CommunityBot 1

-3

votes

0

answers

37

views

Permutation Graphs is Chordal?

graph-theory graph-isomorphism graph-colouring

asked Oct 18 at 8:42 R.hatam 15

9

votes

0

answers

101

views

Complexity of NFA to DFA minimization with binary threshold

automata-theory minimization

asked Oct 17 at 8:12 Shaull 5,057

3

votes

0

answers

124

views

Any problems for which we know the complexity, but no algorithms with the same time?

proofs complexity

asked Oct 17 at 0:19 MinusPi 49

Browse more Questions

Theoretical Computer Science Stack Exchange works best with JavaScript enabled