User diego de estrada - MathOverflow most recent 30 from http://mathoverflow.net 2013-05-23T15:16:34Z http://mathoverflow.net/feeds/user/961 http://www.creativecommons.org/licenses/by-nc/2.5/rdf http://mathoverflow.net/questions/90123/np-hardness-of-a-graph-partition-problem/90298#90298 Answer by Diego de Estrada for NP-hardness of a graph partition problem? Diego de Estrada 2012-03-05T18:29:56Z 2012-03-05T18:29:56Z <p>My answer to the same question posted in cstheory got accepted by the OP, it's here: <a href="http://cstheory.stackexchange.com/a/10528/168" rel="nofollow">http://cstheory.stackexchange.com/a/10528/168</a></p> http://mathoverflow.net/questions/13638/which-popular-games-are-the-most-mathematical/67150#67150 Answer by Diego de Estrada for Which popular games are the most mathematical? Diego de Estrada 2011-06-07T15:49:24Z 2011-06-07T16:31:30Z <p><a href="http://en.wikipedia.org/wiki/Bulls_and_cows" rel="nofollow">Bulls and cows</a> and its modern variant <a href="http://en.wikipedia.org/wiki/Mastermind_%28board_game%29" rel="nofollow">Mastermind</a>, for which Don Knuth demonstrated that the codebreaker can win in at most five moves. Playing this game with pencil and paper (in a way where both players are codemakers and codebreakers) can be very fun.</p> http://mathoverflow.net/questions/13638/which-popular-games-are-the-most-mathematical/67156#67156 Answer by Diego de Estrada for Which popular games are the most mathematical? Diego de Estrada 2011-06-07T16:28:30Z 2011-06-07T16:28:30Z <p><a href="http://en.wikipedia.org/wiki/Khet_%28game%29" rel="nofollow">Khet</a> is a great new game awarded by Mensa. There is even a master thesis dedicated to it: <a href="http://www.personeel.unimaas.nl/Uiterwijk/Theses/MSc/Nijssen_thesis.pdf" rel="nofollow">http://www.personeel.unimaas.nl/Uiterwijk/Theses/MSc/Nijssen_thesis.pdf</a></p> http://mathoverflow.net/questions/13638/which-popular-games-are-the-most-mathematical/67155#67155 Answer by Diego de Estrada for Which popular games are the most mathematical? Diego de Estrada 2011-06-07T16:16:56Z 2011-06-07T16:16:56Z <p>There is a popular game in current cellphones called Pixelated (in BlackBerry) or Flood-It (in iPhone) that has a very interesting analysis (its generalization is equivalent to the Shortest superstring problem): <a href="http://arxiv.org/abs/1001.4420" rel="nofollow">http://arxiv.org/abs/1001.4420</a> http://www.cs.bris.ac.uk/Research/Algorithms/BAD10/Slides/Jalsenius.pdf</p> http://mathoverflow.net/questions/2245/determining-the-space-complexity-of-van-emde-boas-trees Determining the space complexity of van Emde Boas trees Diego de Estrada 2009-10-24T04:03:55Z 2011-06-06T20:44:53Z <p>We call S(u) the space complexity of the vEB tree holding elements in the range 0 to u-1, and suppose without loss of generality that u is of the form 2<sup>2<sup>k</sup></sup>.</p> <p>It's easy to get the recurrence S(u<sup>2</sup>) = (1+u) S(u) + &Theta;(u). (In Wikipedia's article the last term is O(1), but it's wrong because we must count the space for the array.)</p> <p>Van Emde Boas gave in [1] the trivial bound S(u) = O(u log log u), and later in [2] he found a clever way to combine the data structure with other one so that to reach space complexity O(u), while mantaining the O(log log u) time bounds.</p> <p>But modern references present the original data structure and state without proof that the space complexity is O(u). For instance, the very recent 3rd edition of "Introduction to algorithms" by Cormen et al. leaves it as an exercise.</p> <p>I tried with some friends to [dis]prove the O(u) bound without luck.</p> <p>[1] <a href="http://www.springerlink.com/content/h63507n460256241/" rel="nofollow">http://www.springerlink.com/content/h63507n460256241/</a></p> <p>[2] <a href="http://www.cs.ust.hk/mjg_lib/Library/VAN77.PDF" rel="nofollow">http://www.cs.ust.hk/mjg_lib/Library/VAN77.PDF</a></p> http://mathoverflow.net/questions/11540/what-are-the-most-attractive-turing-undecidable-problems-in-mathematics/55809#55809 Answer by Diego de Estrada for What are the most attractive Turing undecidable problems in mathematics? Diego de Estrada 2011-02-18T01:02:36Z 2011-02-18T01:02:36Z <p><a href="http://en.wikipedia.org/wiki/Richardson%2527s_theorem" rel="nofollow">Richardson's theorem</a> says that it is undecidable to tell whether an expression $E$ satisfies $E=0$, where $E$ is generated by $\mathbb{Q}\cup\{\pi,\ln 2,x\}$ and the composition of operations in $\{+,-,\times,\sin,\exp, \mathrm{abs}\}$.</p> <p>(I thought this deserves its own answer, even if it's given as a comment on <a href="http://mathoverflow.net/questions/11540/what-are-the-most-attractive-turing-undecidable-problems-in-mathematics/11555#11555" rel="nofollow">this other answer</a>.)</p> http://mathoverflow.net/questions/50822/reasonable-random-matrices-to-test-numerical-algorithms/54906#54906 Answer by Diego de Estrada for Reasonable "Random" matrices to test numerical algorithms Diego de Estrada 2011-02-09T17:26:10Z 2011-02-10T15:51:20Z <p>One way to generate random matrices while constraining it, is to generate its LU decomposition first. That way you can restrict it to be symmetric ($L=U^T$) and gives you the control over its spectrum.</p> <p>In [S.M. Rump. A Class of Arbitrarily Ill-conditioned Floating-Point Matrices. SIAM J. Matrix Anal. Appl. (SIMAX), 12(4):645-653, 1991] there is a related method for generating very ill-conditioned matrices.</p> http://mathoverflow.net/questions/44524/minimum-tiling-of-a-rectangle-by-squares Minimum tiling of a rectangle by squares Diego de Estrada 2010-11-02T07:22:06Z 2010-11-02T07:22:06Z <p>Given the $n\times m$ rectangle, I want to compute the minimum number of integer-sided squares needed to tile it (possibly of different sizes). Is there an efficient way to calculate this?</p> http://mathoverflow.net/questions/20423/how-to-compute-the-rook-polynomial-of-a-ferrers-board How to compute the rook polynomial of a Ferrers board? Diego de Estrada 2010-04-05T21:38:35Z 2010-07-20T00:10:06Z <p>Given a Ferrers board of shape $(b_1,\ldots,b_m)$, we define $r_k$ as number of ways to place $k$ non-attacking rooks (as in Chess). In section 2.4 of Stanley's Enumerative Combinatorics (vol. 1) it's shown the identity: $$\sum_k r_k (x)_{m-k} = \prod_i (x+s_i)$$ where $s_i = b_i-i+1$, but I don't know if I can invert this formula or make an efficient algorithm to compute the $r_k$'s.</p> <p>If this isn't possible, I would be satisfied if I can compute them efficiently in the following shapes:</p> <p>$(2,2,4,4,\ldots,2n-2,2n-2,2n)$</p> <p>$(2,2,4,4,\ldots,2n,2n)$</p> <p>$(1,1,3,3,\ldots,2n-1,2n-1,2n+1)$</p> http://mathoverflow.net/questions/20423/how-to-compute-the-rook-polynomial-of-a-ferrers-board/22561#22561 Answer by Diego de Estrada for How to compute the rook polynomial of a Ferrers board? Diego de Estrada 2010-04-26T05:40:34Z 2010-04-26T05:47:27Z <p>Although the closed formula is what I wanted, a dynamic programming approach behaves better algorithmically:</p> <p>Define $M_{i,j}$ as the number of ways to place $j$ non-attacking rooks on the Ferrers board of shape $(b_1,\ldots,b_i)$. So we want $M_{m,k}$, which can be computed using the relations: $M_{i,0}=1$, $M_{0,j}=0$ if $j>0$, and if $i,j>0$: $$M_{i,j} = M_{i-1,j} + (b_i-j+1) M_{i-1,j-1}.$$</p> http://mathoverflow.net/questions/21877/minimum-cover-of-partitions-of-a-set Minimum cover of partitions of a set Diego de Estrada 2010-04-19T19:16:22Z 2010-04-20T04:50:36Z <p>Given $n,k\in\mathbb{N}$ where $k\leq n$, I want to compute the minimum subset of the set of partitions of $N$={$1,\ldots,n$}, satisfying these properties:</p> <ol> <li>Each block of every partition has at most $k$ elements.</li> <li>Every pair of elements of $N$ is in the same block in exactly one partition.</li> </ol> <p>Anyone has a clue?</p> http://mathoverflow.net/questions/18100/theorems-with-unexpected-conclusions/21137#21137 Answer by Diego de Estrada for Theorems with unexpected conclusions Diego de Estrada 2010-04-12T18:26:59Z 2010-04-12T18:26:59Z <p>I was very surprised when I first saw that the product of all primes $p$ such that $p-1|2n,$ is the denominator of Bernoulli number $B_{2n}$.</p> http://mathoverflow.net/questions/3559/colloquial-catchy-statements-encoding-serious-mathematics/3950#3950 Answer by Diego de Estrada for Colloquial catchy statements encoding serious mathematics Diego de Estrada 2009-11-03T16:21:39Z 2009-11-03T16:21:39Z <blockquote> <p>All primes are odd except 2, which is the oddest of all.</p> </blockquote> <p>This <a href="http://mathoverflow.net/questions/915/is-there-a-high-concept-explanation-for-why-characteristic-2-is-special" rel="nofollow">has been discussed before</a>. The quote is from "Concrete Mathematics," but it's a rephrasal of one of J.H. Conway in "The book of numbers."</p> http://mathoverflow.net/questions/1083/do-good-math-jokes-exist/2537#2537 Answer by Diego de Estrada for Do good math jokes exist? Diego de Estrada 2009-10-26T00:10:53Z 2009-10-26T00:17:41Z <p>If we can formalize the property of "being a good math joke" good enough to construct a Turing Machine that checks it, then I think we can conclude they don't exist.</p> <p>The reason is that in that case we can construct a Turing Machine (say of length N) that checks each possible string, and stops only if a good math joke was found. The <a href="http://en.wikipedia.org/wiki/Busy%5Fbeaver" rel="nofollow">busy beaver function</a> on N establishes an upper bound for the number of strings the machine needs to check until we can conclude that it wouldn't halt (and therefore no good math jokes exist).</p> <p>Based on empirical evidence, it may be possible that all those cases have already been checked (with negative answer), which implies my thesis.</p> <p>(I'm being ironical, I like much of the jokes posted in here :P)</p> http://mathoverflow.net/questions/22/can-n2-have-only-digits-0-and-1-other-than-n10k/2441#2441 Answer by Diego de Estrada for Can N^2 have only digits 0 and 1, other than N=10^k? Diego de Estrada 2009-10-25T08:18:22Z 2009-10-25T09:30:24Z <p>This reminds me of the first problem Knuth proposed for the "Aha" Sessions (1985): find all positive integers N such that the decimal digits of N and N<sup>2</sup> are both in nondecreasing order from left to right.</p> <p>The report is here: <a href="http://www-cs-faculty.stanford.edu/~knuth/papers/cs1055.pdf" rel="nofollow">http://www-cs-faculty.stanford.edu/~knuth/papers/cs1055.pdf</a> and the videos available in <a href="http://scpd.stanford.edu/knuth/index.jsp" rel="nofollow">http://scpd.stanford.edu/knuth/index.jsp</a></p> <p>Maybe it just doesn't help, but I think some of the analysis could (like the discovery of pumping lemmas).</p> http://mathoverflow.net/questions/563/is-the-diagonal-of-a-regular-language-always-context-free/1864#1864 Answer by Diego de Estrada for Is the "diagonal" of a regular language always context-free? Diego de Estrada 2009-10-22T11:45:54Z 2009-10-22T16:22:31Z <p>It's unnecessary to assume that L is unambiguous: a regular language always is, because there exists a DFA that accepts it.</p> <p>Following Richard's notation, it is easy to construct a DPDA for K, so it is a DCF language (a subset of the unambiguous CFLs). Looking at the construction that proves that the intersection of a CFL and a regular language is CF, we can see that the same property is also preserved for DCFLs, because no step in the construction would produce non-determinism if it isn't already.</p> <p>So we can conclude that L'=K&cap;L is a DCFL, and in particular unambiguous.</p> http://mathoverflow.net/questions/769/exhibit-an-explicit-bijection-between-irreducible-polynomials-over-finite-fields/1800#1800 Answer by Diego de Estrada for Exhibit an explicit bijection between irreducible polynomials over finite fields and Lyndon words. Diego de Estrada 2009-10-22T03:53:30Z 2009-10-22T03:53:30Z <p>In Reutenauer's "Free Lie Algebras", section 7.6.2:</p> <p>A direct bijection between primitive necklaces of length n over F and the set of irreducible polynomials of degree n in F[x] may be described as follows: let K be the field with q<sup>n</sup> elements; it is a vector space of dimension n over F, so there exists in K an element &theta; such that the set {&theta;, &theta;<sup>q</sup>, ..., &theta;<sup>q<sup>n-1</sup></sup>} is a linear basis of K over F. </p> <p>With each word w = a<sub>0</sub>...a<sub>n-1</sub> of length n on the alphabet F, associate the element &beta; of K given by &beta; = a<sub>0</sub>&theta; + a<sub>1</sub>&theta;<sup>q</sup> + ... + a<sub>n-1</sub> &theta;<sup>q<sup>n-1</sup></sup>. It is easily shown that to conjugate words w, w' correspond conjugate elements &beta;, &beta;' in the field extension K/F, and that w \mapsto &beta; is a bijection. Hence, to a primitive conjugation class corresponds a conjugation class of cardinality n in K; to the latter corresponds a unique irreducible polynomial of degree n in F[x]. This gives the desired bijection.</p> http://mathoverflow.net/questions/2272/pseudorandom-generators/3651#3651 Comment by Diego de Estrada Diego de Estrada 2010-10-21T03:39:16Z 2010-10-21T03:39:16Z One detail: there is a particular poly-time computable function that is one-way iff they exist. See <a href="http://www.cs.cornell.edu/courses/cs687/2006fa/lectures/lecture5.pdf" rel="nofollow">cs.cornell.edu/courses/cs687/2006fa/lectures/&hellip;</a> http://mathoverflow.net/questions/1058/when-does-cantor-bernstein-hold/1101#1101 Comment by Diego de Estrada Diego de Estrada 2010-10-03T12:42:07Z 2010-10-03T12:42:07Z How does this categorical argument work in the case of computable sets? (Myhill isomorphism theorem) http://mathoverflow.net/questions/36105/nonasymptotic-complexity-results Comment by Diego de Estrada Diego de Estrada 2010-08-19T18:26:44Z 2010-08-19T18:26:44Z Probably this question will be best addressed at cstheory.stackexchange.com. I recall that kind of result, but almost certainly it is not in the book Algebraic Complexity Theory by B&#252;rgisser et al. http://mathoverflow.net/questions/32824/structure-theorems-for-turing-decidable-languages Comment by Diego de Estrada Diego de Estrada 2010-08-04T18:12:56Z 2010-08-04T18:12:56Z Perhaps you want &quot;structure theorems&quot; more like Myhill-Nerode's for Regular languages and Chomsky-Sch&#252;tzenberger's for Context-free languages. http://mathoverflow.net/questions/20604/are-rings-really-more-fundamental-objects-than-semi-rings/20612#20612 Comment by Diego de Estrada Diego de Estrada 2010-04-26T07:04:49Z 2010-04-26T07:04:49Z I like your observation about modelling optimization problems, can you provide some reference? http://mathoverflow.net/questions/20423/how-to-compute-the-rook-polynomial-of-a-ferrers-board/20464#20464 Comment by Diego de Estrada Diego de Estrada 2010-04-06T03:27:13Z 2010-04-06T03:27:13Z Thank you very much, Qiaochu! http://mathoverflow.net/questions/20423/how-to-compute-the-rook-polynomial-of-a-ferrers-board Comment by Diego de Estrada Diego de Estrada 2010-04-06T00:45:25Z 2010-04-06T00:45:25Z @dan, this is the sequence for the first shape: <a href="http://www.research.att.com/~njas/sequences/A088960" rel="nofollow">research.att.com/~njas/sequences/A088960</a> (number of configurations of $k$ non-attacking bishops on the white squares of an $n\times n$ chessboard, for $n$ even.) The other two are the same with odd $n$, one on black squares and the other on white squares. http://mathoverflow.net/questions/2806/how-can-we-count-lines-in-an-n-x-n-rectangular-array/2810#2810 Comment by Diego de Estrada Diego de Estrada 2009-10-27T15:48:46Z 2009-10-27T15:48:46Z Maybe you misunderstood my N,S,W,E tags (i.e. with N-S I mean the lines that intersect the square at the top &amp; bottom sides, not the slope.) http://mathoverflow.net/questions/2245/determining-the-space-complexity-of-van-emde-boas-trees Comment by Diego de Estrada Diego de Estrada 2009-10-24T07:36:46Z 2009-10-24T07:36:46Z Great advice, thank you! (here tough I'm happy I got a quick and excellent answer, but for the next time) http://mathoverflow.net/questions/2245/determining-the-space-complexity-of-van-emde-boas-trees/2251#2251 Comment by Diego de Estrada Diego de Estrada 2009-10-24T06:58:49Z 2009-10-24T06:58:49Z I'm quite embarrased to know it was so easy. Thanks!