David Benson-Putnins
  • Member for 11 years, 10 months
  • Last seen more than a month ago
  • United States
3 answers
11 votes
1k views
Maximum singular value of a random $\pm 1$ matrix
Accepted answer
6 votes

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

View answer
1 answers
0 votes
539 views
finding missing edge in DAG which, when added, would create the longest cycle
Accepted answer
4 votes

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 ...

View answer
1 answers
4 votes
303 views
Sums of uniformly random vectors from the $n$-dimensional unit ball
3 votes

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 ...

View answer
1 answers
1 votes
208 views
Linear map of Zonotopes
2 votes

If $\mathcal{X}$ is the Minkowski sum of line segments $l_1,\ldots,l_k$, then $\mathcal{Y}$ is the Minkowski sum of line segments $Al_1,\ldots, Al_k$ (and hence a zonotope). As far as computing $C_y$ ...

View answer
2 answers
1 votes
352 views
Higher dimensional convex hull
Accepted answer
2 votes

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)$, ...

View answer
1 answers
0 votes
343 views
Counting integer points in a Minkowski sum
Accepted answer
2 votes

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 ...

View answer
1 answers
0 votes
2k views
Finding a Hamiltonian Circuit using Nearest-neighbor algorithm
Accepted answer
2 votes

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 ...

View answer
3 answers
0 votes
484 views
Approximating higher dimension step function
Accepted answer
0 votes

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 ...

View answer
36 answers
17 votes
3k views
Basic results with three or more hypotheses
0 votes

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$

View answer
3 answers
1 votes
251 views
Strategic vertex labeling
0 votes

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 ...

View answer
2 answers
5 votes
649 views
Binary codes with large distance
-3 votes

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 ...

View answer