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 Hot Week Month

1

vote

0

answers

22

views

How to deal with the time to minimize a function in a given interval?

ds.algorithms time-complexity polynomial-time

asked Jan 8 at 8:53 Mengfan Ma 451

6

votes

1

answer

277

views

Complexity of optimal elimination for a planar tensor network

ds.algorithms reference-request graph-theory graph-algorithms planar-graphs

modified Jan 6 at 16:06 Yaroslav Bulatov 4,611

1

vote

1

answer

162

views

2-Center problem with forbidden pairs

ds.algorithms approximation-algorithms

answered Jan 4 at 14:40 Neal Young 7,598

0

votes

1

answer

63

views

Is a grid graph a vertex-minor of a complete graph?

ds.algorithms graph-theory graph-algorithms planar-graphs

answered Dec 29 '21 at 11:14 Laakeri 1,298

0

votes

0

answers

45

views

Fastest algorithm to compute maximum number of boxes that can fit inside each other

ds.algorithms graph-algorithms

asked Dec 22 '21 at 23:58 user3508551 600

4

votes

1

answer

1k

views

Knapsack with dependent profits (pairs of items)

ds.algorithms optimization

modified Dec 19 '21 at 14:01 CommunityBot 1

14

votes

2

answers

519

views

OR-circuit complexity of a dense linear operator

ds.algorithms circuit-complexity upper-bounds

modified Dec 16 '21 at 9:59 Stasys 6,555

0

votes

0

answers

84

views

optimization on graph edges selection

ds.algorithms graph-theory graph-algorithms optimization

asked Dec 13 '21 at 19:57 Ramon 1

9

votes

2

answers

2k

views

Reducing #SAT to #MONOTONE-2SAT

cc.complexity-theory ds.algorithms complexity-classes sat

modified Dec 12 '21 at 17:27 daniel pehoushek 95

56

votes

7

answers

4k

views

For which problems in P is it easier to verify the result than to find it?

cc.complexity-theory ds.algorithms reference-request

modified Dec 10 '21 at 19:41 daniel pehoushek 95

-1

votes

1

answer

102

views

Algorithm for finding traffic equilibrium

ds.algorithms graph-theory gt.game-theory

modified Dec 9 '21 at 17:58 Artem Kaznatcheev♦ 10k

10

votes

0

answers

121

views

Fastest Known Algorithm to Count Acyclic Orientations in a Graph

cc.complexity-theory ds.algorithms graph-algorithms counting-complexity exp-time-algorithms

modified Nov 24 '21 at 9:02 Dominic Cerisano 115

17

votes

2

answers

417

views

similar matrices

ds.algorithms time-complexity linear-algebra matrices graph-isomorphism

modified Nov 19 '21 at 8:15 Joshua Grochow 35k

20

votes

1

answer

409

views

What are the best possible time/error tradeoffs for approximate solution of linear programs?

ds.algorithms approximation-algorithms online-learning linear-programming

modified Nov 13 '21 at 21:28 Neal Young 7,598

Browse more Questions

Theoretical Computer Science Stack Exchange works best with JavaScript enabled