User david benson-putnins - MathOverflow

Answer by David Benson-Putnins for Approximating higher dimension step function

2013-05-24T18:02:47Z

A first pass to get continuity: for $||s||\geq \epsilon$, $f(s) = s/||s||$. For $||s||<\epsilon$,

$f(s) = \frac{s}{||s||} (e^{1/\epsilon^2-1/||s||^2})$

If you want differentiability you just need to fiddle with the $< \epsilon$ function to have a derivative of 0 in the increasing $||s||$ direction at $||s||=\epsilon$ (I'm not quite motivated enough to figure it out)

Alternatively if you're willing to accept your function never quite being correct

$f(s) = e^{-\epsilon/||s||^2} \frac{s}{||s||}$

Answer by David Benson-Putnins for Basic results with three or more hypotheses

2013-05-16T17:24:08Z

Let $A\subset \mathbb{R}^d$ be (a)closed, (b) convex, and (c) contains the origin. Then $\left( A^{o} \right)^{o} = A$ where $o$ denotes the polar of $A$

Answer by David Benson-Putnins for Sums of uniformly random vectors from the $n$-dimensional unit ball

2013-05-16T00:37:48Z

EDIT: Woops just realized the vectors are drawn from the ball, not the sphere. But the measure of the ball is almost entirely concentrated at the sphere so the same result should apply with just slightly weaker asymptotics

This is a concentration of measure problem on the sphere for fixed $k$ and large $n$. The probability that $|\left< v_1, v_j \right>| \leq \epsilon$ for each fixed $j$ is larger than $1-2e^{-\epsilon^2 n/2}$. So the probability it holds for all $j$ is at least $1-2k e^{-\epsilon^2 n/2}$. The probability that it holds for all pairs of $i$ and $j$ $|\left< v_i, v_j \right>| \leq \epsilon$ is at least $1-2k^2 e^{-\epsilon^2 n/2}$. For any $k$, we can pick $\epsilon$ very small so that this condition implies that $v_1+...+v_k$ has norm almost $\sqrt{k}$ with very high probability if $n$ is large enough.

To nail down some more asymptotics, let $w= v_1+...+v_k$.

$\left< w, w \right> = k + \sum_{i\neq j} \left< v_i,v_j \right>$.

This means that with probability at least $1-2k^2 e^{-\epsilon^2 n/2}$ we have $k-k^2 \epsilon \leq||w||^2 \leq k+ k^2\epsilon$. Choose $\epsilon$ to get the desired level of resolution for large $n$. For example if $\epsilon = 1/k^3$, we get if $d< \sqrt{k-1/k}$ that $||w|| \geq d$ with probability larger than $1-2k^2 e^{-n/(2k^6)}$ and if $d > \sqrt{k+1/k}$ that $||w||\geq d$ with probability smaller than $2k^2 e^{-n/(2k^6)}$

Answer by David Benson-Putnins for Higher dimensional convex hull

2013-05-13T16:32:24Z

I think the answer is yes. First observe that $CH(P) \subset CH(S)\cap H$: if $x\in CH(P)$ then $x$ is written as a convex combination of things which are convex combinations of vertices of $CH(S)$, so is a convex combination of vertices of $CH(S)$.

Then we note that $CH(S)\cap H$ has as its vertices the points in $P$ corresponding to $E(v)$ (in general this is going to be all of $E(v)$ are, which are all contained in $P$ of course so $CH(S)\cap H \subset CH(P)$ and the two sets are equal, and we know the vertices of $CH(S)\cap H$

To see that $CH(S) \cap H$ has the correct vertices, the faces of $CH(S) \cap H$ correspond to faces of $CH(S)$ with their dimension dropped by at most 1 (if the face happens to be parallel to the hyperplane, then it will not drop in dimension). The edges in $E(v)$ cannot be parallel to the hyperplane because that means the hyperplane does not separate $v$ and the corresponding vertex on the other side of the edge

Answer by David Benson-Putnins for Strategic vertex labeling

2013-05-13T03:18:08Z

Some observations which are too long for a comment to simplify the problem. The edges that are do not connect to G' are irrelevant, as is every 0 vertex that is outside of G'. So we can throw those away. If a vertex in G' has some 1s and some -1s, then we know that if we make it a 1 we get the sum of the weights to the 1s - weights to (-1)s, and if we make the G' vertex a -1 we get negative that contributed to the sum. So we can throw away G entirely and we have a graph G' with weights $w_{ij} > 0$ for each edge, and weights $v_k$ of any sign for each vertex and we want to maximize

$ \sum_{i,j} w_{ij} l_i l_j + \sum_{k} v_k l_k$

This is resistant to a greedy algorithm attempt. For example suppose that I have twelvevertices, which I will label $a$ and $b_1,...b_{11}$. My objective is to pick each $l_j$ one at a time to maximize the sum given the other $l_j$s. I'll call the labels $l_a$ and $l_1,..,l_{11}$. If $v_a = 10$ and $v_j = -1$ for each $j$, and $w_{aj} = 1.001$ for each $j$, and there are no other edges, then the first thing you would do is assign $l_a = 1$. After that, assigning $l_j=1$ increases the sum by .001, and making it a $-1$ decreases it by .01, so you would make each $l_j = 1$ and the total sum would be 10.01.

But if I had instead assigned each vertex a $-1$ labeling, my total sum would be 11.01. Also the greedy algorithm solution of all 1s is resistant to changing a single vertex, so trying to solve this on a local level is probably impossible

Answer by David Benson-Putnins for Counting integer points in a Minkowski sum

2013-05-06T14:24:26Z

Proving this is actually problem 3 on page 164 of Integer Points in Polyhedra by Alexander Barvinok - the number of integer points is a polynomial in $t_1,...,t_k$ as long as they are non-negative integers.

Proof omitted at the moment because I'm too rusty to produce one

Answer by David Benson-Putnins for Finding a Hamiltonian Circuit using Nearest-neighbor algorithm

2012-05-12T05:57:47Z

The nearest neighbor algorithm as I understand it (repeatedly select a neighboring vertex that hasn't been visited yet and travel to that vertex) does not guarantee that you will find a circuit even if one exists. For example consider the graph with vertices A,B,C,D with edges AB, AC, AD, BC and CD (a complete graph on 4 vertices with edge BD removed). Starting at A, you travel to C. You can then travel to either B or D, at which point your only choice is to go back to A. So if you go from A to C, you can't complete the loop and construct a Hamiltonian circuit even though one exists.

Answer by David Benson-Putnins for Maximum Singular Value of a random +1/-1 matrix

2012-05-01T13:48:28Z

http://www-personal.umich.edu/~romanv/papers/non-asymptotic-rmt-plain.pdf Theorem 5.39 (page 23) gives a non-asymptotic upper bound on the largest singular value

Answer by David Benson-Putnins for finding missing edge in DAG which, when added, would create the longest cycle

2012-04-30T07:47:41Z

Actually your context tells us you are interested in a much simpler problem. Rather than finding the longest directed simple path in the graph, you are only interested in the longest directed simple path which ends at a specified vertex (the person who is using the app at that moment). So if you just construct a new graph which reverses the directions of the edges, and from that specified vertex do a DFS/BFS to find the longest directed simple path starting at that vertex, the endpoint of that path is the person who should be recommended as a person to 'thank'. In your search you can keep track of the k longest paths if you want to recommend multiple people for thanking

Answer by David Benson-Putnins for Binary codes with large distance

2010-01-31T14:49:20Z

Gama doesn't have to be negative, in fact if delta is smaller than 1/2 gamma will be positive. It's known for Hadamard codes that arbitrarily large codes exist, and it seems intuitive that if the distance between vectors should be smaller then large codes should exist still, but I don't have a proof

Comment by David Benson-Putnins

2013-05-24T22:28:28Z

wolframalpha.com/input/… It's differentiable at zero because $e^{-\epsilon/||s||^2}$ goes to zero so fast. By "never quite being correct" I meant there is no choice of s for which f(s) = s/||s|| exactly

Comment by David Benson-Putnins

2013-05-24T21:58:48Z

The second option is defined for all s in one shot, not piecewise.

Comment by David Benson-Putnins

2013-05-20T16:36:16Z

It seems like you should just post your specific polynomial

Comment by David Benson-Putnins

2013-05-14T03:58:38Z

Yuichiro, $p^c$ is the probability that the minimum cut gets removed (and the other edges do whatever), which necessarily disconnects the graph.

Comment by David Benson-Putnins

2013-05-13T17:51:17Z

If you think of CH(S) as being a polyhedron: A polyhedron P of dimension n has a face F of dimension d if there are n-d linearly independent inequalities for P which are active (have an equality at that point). So if we take P=CH(S), the edges are the places were n-1 inequalities are active. If we restrict to $CH(S)\cap H$, inequalities for $P$ correspond to inequalities for $CH(S)\cap H$ inside of $H$. The edge which originally had n-1 active inequalities still has n-1 active inequalities inside of $H$ as long as $H\cap edge$ is not equal to the whole edge

Comment by David Benson-Putnins

2013-05-13T16:17:39Z

The excluded dot isn't lying on an edge of the volume though, is it?

Comment by David Benson-Putnins

2013-05-13T02:42:22Z

Actually wait this makes the problem fairly trivial "the challenge is to relabel the 0s on the side of G′ in such way that product of labels on both sides maximizes the sum " If all I'm worried about is the sum over the boundary edges then I can pick each vertex independently as a 1 or a -1 to maximize the sum of its edge weights. It's only interesting if the internal edges of G' are included as well

Comment by David Benson-Putnins

2013-05-13T01:49:05Z

Dustin, I don't think it's correct anyway. The correct labeling of G' would be to just set every value to 1. Solving maxcut would be equivalent to minimizing the sum wouldn't it?

Comment by David Benson-Putnins

2013-05-12T18:29:03Z

Joseph this comment confused me a little.. from your original post I would have thought that G' had ALL the vertices with weight 0, but from the comment it sounds like G' only contains some of them, and some might be left in G. I'm not sure if it makes a difference in the problem since any leftover 0 vertices can just be ignored but I wanted to check which interpretation is correct

Comment by David Benson-Putnins

2013-05-11T20:07:41Z

Apparently wikipedia has a very broad definition of polytope en.wikipedia.org/wiki/Polytope But I have only seen polytope be used to mean that definition, which immediately implies that it is convex

Comment by David Benson-Putnins

2013-05-08T21:31:22Z

The number of colors that you are required to use is basically independent of N because of how little it affects the graph. Consider the following graph: I have a vertex in V1 connected to N vertices in V2. I also have a bunch of vertices in V1 which are connected to vertices in V2 that aren't from the original N. The number of colors required is essentially independent of N The number required can also be arbitrarily high. For the vertex set V2, for each pair of vertices put a vertex in V1 that connects to both of them. Then every vertex in V2 needs to be colored differently.

Comment by David Benson-Putnins

2013-05-06T21:45:21Z

When you say "2D lattice" you mean explicitly $\mathbb{Z}^2$?

Comment by David Benson-Putnins

2013-05-06T18:07:07Z

My impression was that there just happened to be some values a and b for which the first equation were true, not that it was true for all a and b. Zamoura, can you clarify this?

Comment by David Benson-Putnins

2013-05-06T14:52:30Z

I think this is false. For example pick u(x) = 0, c=-1, d=1 (it doesn't matter what a and b are). Then the claim is that $f(0) \geq \frac{1}{2} \int_{-1}^{1} f(x) dx$ which $f(x) = x^2$ shows is false

Comment by David Benson-Putnins

2012-05-04T20:10:34Z

Small typo.... the dimension of the input and output of X are the same but that doesn't jive with the nxm shape of X. More importantly I can't figure out what the properties of Q are supposed to be