326 reputation
110
bio website cs.uiuc.edu
location Urbana, IL
age
visits member for 4 years, 5 months
seen Dec 20 at 16:19

No, I am a meat popsicle.


Jun
9
comment maximum flow ford-fulkerson analysis
No, if (a,b) is in E, then both (a,b) and (b,a) are in E'. In particular, E' is always a superset of E. On the other hand, $|E'| \le 2|E|$, so $O(E') = O(E)$.
May
31
comment How does one give a mathematical talk?
It. Is. Not. Possible. To. Speak. Too. Slowly.
May
29
comment Where/What are good sources to learn about the history of computation?
That said, I think the question is much too broad. Do you mean computing devices (starting with Stone Age tally sticks, or even fingers), or algorithms (starting perhaps with techniques that were already centuries old when they were described in the Rhind Papryus), or applications (starting perhaps with agriculture)?
May
29
comment Where/What are good sources to learn about the history of computation?
@Gigili: Cross-posting is generally discouraged; migration might be a better option if the question doesn't get good answers here. See this discussion at meta.cstheory.
May
24
awarded  Organizer
May
24
revised Determining position at some point in time
add computational-geometry tag
May
24
suggested approved edit on Determining position at some point in time
May
24
comment Determining position at some point in time
Hint: This should have the computational-geometry tag.
May
21
comment Variety vs. Manifold
Even in French, a red herring is neither necessarily red nor necessarily a fish. (And no, @Galoisfan, the phrases "algebraic variety" and "algebraic manifold" are not synonyms, even in English; read the answer again!)
May
20
comment Expected Number of Convex Layers and the expected size of a layer for different distributions
Well, that's just a back of the envelope estimate. It might be good for intuition, but I wouldn't trust it to give a precise bound, especially after several iterations.
May
19
awarded  Yearling
May
19
comment Expected Number of Convex Layers and the expected size of a layer for different distributions
But $P_1$ is not uniformly distributed in a square; it's uniformly distributed in $conv(P)$, which has $\Theta(\log n)$ sides in expectation. So the right back-of-the-envelope estimate for the complexity of the convex hull of $P_1$ is $\Theta(\log^2 n)$. More generally, deeper layers are "rounder", and boundary effects matter less.
May
19
answered Given a victory condition and a set strategy, what are the chances of winning on a given turn in a game of Magic: The Gathering?
May
17
comment Can every nonsingular $n\times n$ matrix with real entries be made singular by changing exactly one entry?
@ZevChonoles: Yes, much better. (You can't make the identity matrix singular by changing an off-diagonal entry, for precisely this reason.)
May
17
comment Can every nonsingular $n\times n$ matrix with real entries be made singular by changing exactly one entry?
But what if the coefficient of $a_{k\ell}$ is zero? Equivalently, what if the function $f$ such that $\det(A) = f(a_{k\ell})$ is actually constant?
May
17
answered Applications of parity formula on connected planar graph
May
17
comment Applications of parity formula on connected planar graph
"Proof: 3 ≠ 19."
May
15
comment Examples of mathematical induction
@OldPro: Induction proofs are just proofs by contradiction where you prove that the smallest counterexample doesn't exist.
May
14
comment Mathematical toys?
Also the Towers of Hanoi.
May
13
comment How to evaluate Θ, or O and Ω from function
J.D.'s comment proves the upper bounds ($O(\cdots)$) but ignores the matching lower bounds ($\Omega(\cdots)$). Half the terms in the sum are at least $n/2$, so the sum is at least $n^2/4 = \Omega(n^2)$. Since we already know the sum is $O(n^2)$, we conclude that it is also $\Theta(n^2)$. Similarly, half the terms in the sum $\ln n + \ln (n-1) + \cdots + \ln 1$ are at least $\ln (n/2) = \ln n - \ln 2$, so $\ln n! \ge (n/2)\ln (n/2) = (n\ln n)/2 - n (\ln 2)/2 = \Omega(n\log n)$. Since we already know that $\ln n! = O(n\log n)$, we conclude that $\ln n! = \Theta(n\log n)$.