bio | website | math.mit.edu/~shor |
---|---|---|
location | M.I.T., Cambridge, MA | |
age | 55 | |
visits | member for | 5 years, 4 months |
seen | 2 days ago | |
stats | profile views | 6,760 |
I'm a professor in the Mathematics Dept. at M.I.T. I mostly work on quantum computation, quantum information, and quantum complexity, but I am also interested in other areas of theoretical computer science and mathematics.
Jan 4 |
comment |
Transforming a binary matrix into triangular form using permutation matrices
This just had an answer which got deleted. Here's a simplification of it (definitely based on it). (a) prove that any row with a single 1 can serve as the first row. (b) use the following algorithm: choose a row with a single 1 for the first row. Delete the column that 1 is in. Then recurse. How do you prove any row with a single 1 can serve as the first row? Consider an $n \times n$ matrix $M$ with $M(i,j) = 1$ if $j \leq i$ except for row $i'$, which has exactly one $1$ in position $(i',j')$ with $j' \leq i'$. Cyclically permute the rows from $1$ to $i'$, and the columns from $1$ to $j'$. |
Dec 10 |
comment |
Can we cover the unit square by these rectangles?
@L Spice: It's rigorous. You find a subsequence in which the packing of the first $k$ rectangles converges to a fixed configuration. This fixed configuration (the one to which the first $k$ rectangles converges) is the one that doesn't change position when you take a subsubsequence of this subsequence. |
Dec 3 |
awarded | Yearling |
Jun 1 |
awarded | Nice Answer |
May 8 |
awarded | Notable Question |
May 8 |
revised |
Defining a canonical ordering of matrix rows/columns
added 178 characters in body |
Apr 6 |
comment |
What areas of pure mathematics research are best for a post-PhD transition to industry?
What do you mean coding theory is not pure math? Coding theory spans a spectrum from extremely pure math to extremely applied. Of course, you do run into the problem that pure coding theory is somewhat different from applied, but if you can find an advisor in the math department who does coding theory, I think this would be an excellent area. |
Jan 6 |
awarded | Enlightened |
Jan 6 |
awarded | Nice Answer |
Dec 3 |
awarded | Yearling |
Sep 30 |
awarded | Caucus |
Sep 18 |
comment |
point in polytope
It needn't actually double the number of constraints; you can replace the inequality $\lambda_i \geq 0$ by $\lambda_i - x \geq 0$, to get the same number of constraints and one more variable. I expect you'll still take a performance hit, but less of one. |
Sep 17 |
awarded | Enlightened |
Sep 17 |
awarded | Nice Answer |
Sep 17 |
answered | point in polytope |
Sep 13 |
revised |
Algorithm on winning strategy of Winner (Simplified card game)
fixed latex and grammar |
Aug 18 |
comment |
Constructing Steiner Triple Systems Algorithmically
Your nice answer makes me glad I bumped it (I fixed a broken link). |
Aug 18 |
awarded | Excavator |
Aug 18 |
revised |
Constructing Steiner Triple Systems Algorithmically
fixed broken link |
Jul 2 |
comment |
Largest graphs of girth at least 6
@Brendan: the reason I came upon this question was looking at sequence A072567 in the Online Encyclopedia of Integer Sequences. The $m$th term is the number of edges in the largest bipartite subgraph of $K_{m,m}$ (which is tangentially related to a quantum game I'm looking at). So after you've checked this table, if all your bipartite graphs for even $n$ are split $n/2,n/2$, you could easily extend this sequence. |