most recent 30 from http://mathoverflow.net 2013-05-23T06:03:07Z http://mathoverflow.net/feeds/user/3028 http://www.creativecommons.org/licenses/by-nc/2.5/rdf http://mathoverflow.net/questions/15614/interesting-applications-of-max-flow-and-linear-programming Wilson 2010-02-17T19:26:55Z 2010-07-12T14:23:22Z

<p>Max-flow and linear programming are two big hammers in algorithm design: each are expressive enough to represent many poly-time solvable problems. Some problems are obvious applications of max-flow: like finding a maximum matching in a graph. What I'm looking for are examples of problems that can be solved via clever encodings as flow problems or LP problems -- ones that aren't obvious. I'm looking for questions at a level suitable for a homework problem for an advanced undergraduate or beginning graduate course in algorithms.</p> <p>Any ideas?</p>

http://mathoverflow.net/questions/28526/industry-government-jobs-for-mathematicians Wilson 2010-06-17T16:07:59Z 2010-06-18T01:28:48Z

<p>Suppose that you graduate with a good PhD in mathematics, but don't necessarily want to go into academia, with the post-doc years that this entails. Are there any other options for continuing to do "real math" professionally?</p> <p>For example, how about working at the NSA? I don't know much of what is done there -- is it research mathematics? Are there other similar organizations? Perhaps corporations that contract with the federal government? Companies like RSA?</p> <p>Other areas of industry? Is there research mathematics done in any sort of financial or tech company?</p> <p>I've made this a community wiki, since there aren't any right answers...</p>

http://mathoverflow.net/questions/17384/geometric-interpretation-of-singular-values Wilson 2010-03-07T15:32:35Z 2010-03-07T16:58:22Z

<p>The singular values of a matrix A can be viewed as describing the geometry of AB, where AB is the image of the euclidean ball under the linear transformation A. In particular, AB is an elipsoid, and the singular values of A describe the length of its major axes. </p> <p>More generally, what do the singular values of a matrix say about the geometry of the image of other objects? How about the unit L1 ball? This will be some polytope: is there some natural way to describe this shape in terms of singular values, or other properties of matrix A?</p>

http://mathoverflow.net/questions/11149/sample-from-uniform-distribution-vs-sample-from-random-distribution Wilson 2010-01-08T14:54:02Z 2010-01-24T17:43:02Z

<p>I could sample a set of m elements from the uniform distribution over a universe $U$ of n >> m elements. Alternately, I could select a random probability distribution $\mathcal{D}$, and sample $m$ elements from $\mathcal{D}$. </p> <p>EDIT (per Michael Lugo): When I say "select a random probability distribution", I mean select a point uniformly at random from the standard $n$-simplex: {${(x_1,\ldots,x_n) : x_i \geq 0, x_1+\ldots+x_n = 1}$}. </p> <p>Do these two methods lead to the same distribution over my sample? If not, how do they differ? If some event (my sample lies in some set of samples of size m) occurs with probability p using the second method, what can I say about its probability using the first method?</p>

http://mathoverflow.net/questions/11497/reference-for-elementary-and-cool-statistics-or-financial-math/11501#11501 Wilson 2010-01-12T04:08:49Z 2010-01-12T04:08:49Z

<p>"Efficient Algorithms for Universal Portfolios" <a href="http://jmlr.csail.mit.edu/papers/volume3/kalai02a/kalai02a.pdf" rel="nofollow">http://jmlr.csail.mit.edu/papers/volume3/kalai02a/kalai02a.pdf</a></p> <p>An algorithm for investing in a portfolio of stocks that guarantees you do almost as well as the best stock in hindsight. Very cool and not super complicated.</p>

http://mathoverflow.net/questions/11444/good-algorithm-for-finding-the-diameter-of-a-sparse-graph/11489#11489 Wilson 2010-01-12T01:43:30Z 2010-01-12T01:43:30Z

<p>It is a longstanding open problem whether it is possible to compute the shortest path between a particular pair of vertices in time less than known algorithms for computing all-pairs shortest path. So you are asking whether there is an algorithm for computing the maximum over the set of all shortest paths that runs faster than any known algorithm for computing any particular shortest path.</p> <p>I'm pretty sure the answer is no, but I can't off the top of my head think of a reduction to the single pair shortest path problem.</p>

http://mathoverflow.net/questions/10864/efficiently-sampling-points-from-an-integer-lattice/10878#10878 Wilson 2010-01-06T04:17:29Z 2010-01-06T04:17:29Z

<p>Yes, there is just one weight function w. </p>

http://mathoverflow.net/questions/29949/what-is-the-shortest-program-for-which-halting-is-unknown/29953#29953 Wilson 2010-06-29T21:17:54Z 2010-06-29T21:17:54Z

Also, there's the question of how long the bit representation is of the smallest n not known to halt.

http://mathoverflow.net/questions/29949/what-is-the-shortest-program-for-which-halting-is-unknown/29953#29953 Wilson 2010-06-29T21:16:54Z 2010-06-29T21:16:54Z

I guess you mean to make the function recursive? f(n) = f(n/2), f(n) = f(3n+1), etc. Also you need the base case. Otherwise this function is easily computable. :-)

http://mathoverflow.net/questions/28526/industry-government-jobs-for-mathematicians/28533#28533 Wilson 2010-06-17T16:50:31Z 2010-06-17T16:50:31Z

I agree that it seems there is little opportunity to publish outside of Academia -- this is why it is hard to learn what is done there. But I suppose that publishing is not a necessary condition for satisfying work, so long as there is a good internal community of mathematicians with whom to work.

http://mathoverflow.net/questions/28526/industry-government-jobs-for-mathematicians Wilson 2010-06-17T16:49:18Z 2010-06-17T16:49:18Z

Hi Ian, You are right. I am a US citizen, and so am interested also in opportunities only available to US citizens; of course other opportunities are also welcome, and it makes sense to distinguish the two types.

http://mathoverflow.net/questions/11444/good-algorithm-for-finding-the-diameter-of-a-sparse-graph/11489#11489 Wilson 2010-01-12T17:31:06Z 2010-01-12T17:31:06Z

Djikstra's algorithm does not work for negative edge weights; for this, you need Bellman Ford, which runs in time O(|V||E|) = O(|V|^3) for dense graphs. The best algorithm for the all-pairs shortest paths is Floyd-Warshall, which also runs in time O(|V|^3). Note that Johnson's algorithm is faster only on sparse graphs.

http://mathoverflow.net/questions/11149/sample-from-uniform-distribution-vs-sample-from-random-distribution Wilson 2010-01-08T16:24:26Z 2010-01-08T16:24:26Z

For concreteness, lets say we are selecting from the standard $n$-simplex.

http://mathoverflow.net/questions/11149/sample-from-uniform-distribution-vs-sample-from-random-distribution Wilson 2010-01-08T16:22:33Z 2010-01-08T16:22:33Z

Michael -- I'm not sure I understand. The positive orthant of the $\ell_1$ ball in 2 dimensions would correspond to the triangle bounded by the line segment (0,1) to (1,0) and the lines x=0 and y=0, not the unit square. I do see how selecting a point in this triangle and projecting onto the line induces a different distribution than directly selecting a point on the line. The difference should become small as n grows, however, right? In that we are likely to select a point close to the surface of the ball. An answer for either scenario would be appreciated.

http://mathoverflow.net/questions/11149/sample-from-uniform-distribution-vs-sample-from-random-distribution Wilson 2010-01-08T16:13:24Z 2010-01-08T16:13:24Z

Clarification to the above comment: In the second method, you choose a random distribution $\mathcal{D}$ only once, and then select $m$ elements independently from $\mathcal{D}$. You do not independently select a new distribution for each element.

http://mathoverflow.net/questions/11149/sample-from-uniform-distribution-vs-sample-from-random-distribution Wilson 2010-01-08T16:12:08Z 2010-01-08T16:12:08Z

Hi Mark -- yes, in both cases, the m elements are chosen independently. I'm not sure that I may as well assume $m=1$, however. If $m=1$, by symmetry, the two distributions must be identical. But for $m &gt; 1$, selecting a distribution and then selecting an independent sample from it may introduce correlations that do not exist when selecting independently from a uniform distribution.

http://mathoverflow.net/questions/11149/sample-from-uniform-distribution-vs-sample-from-random-distribution Wilson 2010-01-08T16:02:17Z 2010-01-08T16:02:17Z

Yes, thanks for the correction. I mean sample a point in the positive region of the $ell_1$-ball rescaled so that all coordinates sum to 1, which should be equivalent to picking a point from the standard $n$-simplex.