Skip to main content
D.W.'s user avatar
D.W.'s user avatar
D.W.'s user avatar
D.W.
Moderator
  • Member for 12 years, 1 month
  • Last seen this week
128 votes
15 answers
16k views

How to fool the "try some test cases" heuristic: Algorithms that appear correct, but are actually incorrect

80 votes
3 answers
54k views

Express boolean logic operations in zero-one integer linear programming (ILP)

51 votes
6 answers
57k views

How to prove greedy algorithm is correct

35 votes
5 answers
9k views

Enumerate all non-isomorphic graphs of a certain size

33 votes
3 answers
7k views

Encoding 1-out-of-n constraint for SAT solvers

31 votes
3 answers
9k views

Teaching NP-completeness - Turing reductions vs Karp reductions

28 votes
2 answers
47k views

How to prove that a language is context-free?

22 votes
6 answers
2k views

Algorithm to test whether a language specified in algebraic form is context-free

22 votes
3 answers
2k views

Algorithm to minimize surface area, given volume

21 votes
4 answers
550 views

Complexity classes where $C^C = C$

20 votes
1 answer
2k views

Could min cut be easier than network flow?

19 votes
1 answer
3k views

When to use SAT vs Constraint Satisfaction?

15 votes
2 answers
2k views

MIN-2-XOR-SAT and MAX-2-XOR-SAT: are they NP-hard?

15 votes
3 answers
3k views

Cast to boolean, for integer linear programming

14 votes
0 answers
711 views

Test whether two languages are equal, when give in algebraic form

13 votes
3 answers
6k views

Closest pair of points between two sets, in 2D

12 votes
2 answers
2k views

Smallest DFA that accepts given strings and rejects other given strings

11 votes
1 answer
667 views

What do complexity classes look like, if we use Turing reductions?

11 votes
1 answer
2k views

Data structure for map on intervals

11 votes
1 answer
2k views

Algorithm to test whether a language is regular

10 votes
1 answer
200 views

Mathematical optimization on a noisy function

9 votes
3 answers
4k views

Kernelization trick, for neural networks

9 votes
0 answers
178 views

Boolean formula that agrees with most truth assignments

9 votes
1 answer
1k views

Given n strings, is one of them a substring of another?

9 votes
4 answers
3k views

Can element uniqueness be solved in deterministic linear time?

9 votes
1 answer
237 views

Verify correctness of quantifier elimination, using SAT

7 votes
2 answers
330 views

Automated lip-reading: inferring what someone is saying, based upon video of them speaking

7 votes
1 answer
145 views

Subsequence of one string but not of others

7 votes
2 answers
403 views

Integral solutions to circulation problem

6 votes
1 answer
68 views

Small world theorem for set constraints