Elle Najt
  • Member for 4 years, 11 months
  • Last seen more than a week ago
Sampling perfect matching uniformly at random
3 votes

If you assume that your graph is planar, then there is a polynomial time procedure for this sampling problem. First, the problem of counting the number of perfect matchings is in P for planar graphs. ...

View answer
Finding the dichotomy that maximizes information gain for a classifier?
Accepted answer
2 votes

As in the discussion, there are too many "features" for this to be in interesting question. In particular, letting $A = C^{-1}(1)$, the set of positive examples, then $H(C|A) = H(C|C) = 0$ so ...

View answer
Reducing a problem to the MST problem
1 votes

Hint: Add a new vertex to your graph.. Further hint:

View answer
Algorithms that must compute a global property?
1 votes

A silly example: Checking if a graph has more than m nodes. :-) Some more interesting examples: Checking if a graph is connected. Checking if a graph has an Eulerian cycle. A graph is Eulerian iff ...

View answer
Why there is no polynomially large sequence of polynomial large weights that derandomize the isolation lemma?
1 votes

I learned the following argument from Dieter van Melkebeek (but any mistakes are my own). I'm not sure that this is what Arvind and Mukhopadhyay had in mind, because the assumptions are not the same, ...

View answer