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

3

votes

0

answers

13

views

Complexity of Encoding a Matroid Flow Problem in a Matrix

cc.complexity-theory ds.algorithms graph-theory linear-algebra max-flow-min-cut

asked 9 hours ago Naysh 365

0

votes

0

answers

83

views

Algorithms and approximations for optimal offline binary tree operations

ds.algorithms approximation-algorithms optimization binary-trees

modified Sep 19 at 16:13 Mario Carneiro 133

17

votes

0

answers

189

views

In an $m$ by $n$ Boolean matrix, can you find a square block whose four corners are ones in $O(m \cdot n)$ time?

ds.algorithms matrices computational-geometry search-problem boolean-matrix

modified Sep 18 at 19:44 Michael Wehar 4,339

0

votes

1

answer

43

views

Algorithm to calculate coordinated radio frequencies

ds.algorithms

answered Sep 15 at 5:33 D.W. 9,268

5

votes

1

answer

75

views

Generate cut $(A,B)$ in edge-colored graph $(V,E_1 \cup E_2)$ such that there are more red than white crossings, i.e $|E_1(A,B)| > |E_2(A,B)|$

ds.algorithms graph-theory graph-algorithms linear-programming enumeration

modified Sep 9 at 17:25 Neal Young 6,499

4

votes

0

answers

285

views

Deciding whether $2^k+m$ is prime

ds.algorithms pspace

modified Sep 2 at 23:28 Travis Wells 149

1

vote

0

answers

44

views

Reference request: algorithm meta-analyses

ds.algorithms reference-request

asked Sep 1 at 21:50 ShyPerson 350

4

votes

1

answer

910

views

Knapsack with dependent profits (pairs of items)

ds.algorithms optimization

modified Aug 26 at 11:04 Community♦ 1

21

votes

2

answers

3k

views

computing the minimal NFA for a DFA

ds.algorithms reference-request fl.formal-languages automata-theory optimization

answered Aug 26 at 2:17 Joshua Wise 101

115

votes

18

answers

8k

views

Examples of the price of abstraction?

ds.algorithms reference-request big-list lower-bounds

answered Aug 23 at 22:20 sdcvvc 1,241

3

votes

1

answer

171

views

How can I optimize my brute-force solution to this problem?

ds.algorithms

modified Aug 18 at 19:06 D.W. 9,268

3

votes

1

answer

120

views

Maximum subarray problem with weights

ds.algorithms

modified Aug 17 at 14:25 Neal Young 6,499

3

votes

0

answers

93

views

On solving Planar Circuit SAT

ds.algorithms circuit-complexity sat counting-complexity circuit-depth

modified Aug 13 at 16:46 Giorgio Camerani 6,349

3

votes

1

answer

123

views

Polynomial evaluation at all different points

ds.algorithms

answered Aug 13 at 4:15 Mahdi Cheraghchi 3,746

Browse more Questions

Theoretical Computer Science Stack Exchange works best with JavaScript enabled