User diego de estrada - MathOverflow

Answer by Diego de Estrada for NP-hardness of a graph partition problem?

2012-03-05T18:29:56Z

My answer to the same question posted in cstheory got accepted by the OP, it's here: http://cstheory.stackexchange.com/a/10528/168

Answer by Diego de Estrada for Which popular games are the most mathematical?

2011-06-07T15:49:24Z

Bulls and cows and its modern variant Mastermind, 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.

Answer by Diego de Estrada for Which popular games are the most mathematical?

2011-06-07T16:28:30Z

Khet is a great new game awarded by Mensa. There is even a master thesis dedicated to it: http://www.personeel.unimaas.nl/Uiterwijk/Theses/MSc/Nijssen_thesis.pdf

Answer by Diego de Estrada for Which popular games are the most mathematical?

2011-06-07T16:16:56Z

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): http://arxiv.org/abs/1001.4420 http://www.cs.bris.ac.uk/Research/Algorithms/BAD10/Slides/Jalsenius.pdf

Determining the space complexity of van Emde Boas trees

2009-10-24T04:03:55Z

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^{2^k}.

It's easy to get the recurrence S(u²) = (1+u) S(u) + Θ(u). (In Wikipedia's article the last term is O(1), but it's wrong because we must count the space for the array.)

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.

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.

I tried with some friends to [dis]prove the O(u) bound without luck.

[1] http://www.springerlink.com/content/h63507n460256241/

[2] http://www.cs.ust.hk/mjg_lib/Library/VAN77.PDF

Answer by Diego de Estrada for What are the most attractive Turing undecidable problems in mathematics?

2011-02-18T01:02:36Z

Richardson's theorem 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}\}$.

(I thought this deserves its own answer, even if it's given as a comment on this other answer.)

Answer by Diego de Estrada for Reasonable "Random" matrices to test numerical algorithms

2011-02-09T17:26:10Z

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.

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.

Minimum tiling of a rectangle by squares

2010-11-02T07:22:06Z

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?

How to compute the rook polynomial of a Ferrers board?

2010-04-05T21:38:35Z

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.

If this isn't possible, I would be satisfied if I can compute them efficiently in the following shapes:

$(2,2,4,4,\ldots,2n-2,2n-2,2n)$

$(2,2,4,4,\ldots,2n,2n)$

$(1,1,3,3,\ldots,2n-1,2n-1,2n+1)$

Answer by Diego de Estrada for How to compute the rook polynomial of a Ferrers board?

2010-04-26T05:40:34Z

Although the closed formula is what I wanted, a dynamic programming approach behaves better algorithmically:

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

Minimum cover of partitions of a set

2010-04-19T19:16:22Z

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:

Each block of every partition has at most $k$ elements.
Every pair of elements of $N$ is in the same block in exactly one partition.

Anyone has a clue?

Answer by Diego de Estrada for Theorems with unexpected conclusions

2010-04-12T18:26:59Z

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

Answer by Diego de Estrada for Colloquial catchy statements encoding serious mathematics

2009-11-03T16:21:39Z

All primes are odd except 2, which is the oddest of all.

This has been discussed before. The quote is from "Concrete Mathematics," but it's a rephrasal of one of J.H. Conway in "The book of numbers."

Answer by Diego de Estrada for Do good math jokes exist?

2009-10-26T00:10:53Z

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.

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 busy beaver function 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).

Based on empirical evidence, it may be possible that all those cases have already been checked (with negative answer), which implies my thesis.

(I'm being ironical, I like much of the jokes posted in here :P)

Answer by Diego de Estrada for Can N^2 have only digits 0 and 1, other than N=10^k?

2009-10-25T08:18:22Z

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² are both in nondecreasing order from left to right.

The report is here: http://www-cs-faculty.stanford.edu/~knuth/papers/cs1055.pdf and the videos available in http://scpd.stanford.edu/knuth/index.jsp

Maybe it just doesn't help, but I think some of the analysis could (like the discovery of pumping lemmas).

Answer by Diego de Estrada for Is the "diagonal" of a regular language always context-free?

2009-10-22T11:45:54Z

It's unnecessary to assume that L is unambiguous: a regular language always is, because there exists a DFA that accepts it.

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.

So we can conclude that L'=K∩L is a DCFL, and in particular unambiguous.

Answer by Diego de Estrada for Exhibit an explicit bijection between irreducible polynomials over finite fields and Lyndon words.

2009-10-22T03:53:30Z

In Reutenauer's "Free Lie Algebras", section 7.6.2:

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ⁿ elements; it is a vector space of dimension n over F, so there exists in K an element θ such that the set {θ, θ^q, ..., θ^{q^n-1}} is a linear basis of K over F.

With each word w = a₀...a_n-1 of length n on the alphabet F, associate the element β of K given by β = a₀θ + a₁θ^q + ... + a_n-1 θ^{q^n-1}. It is easily shown that to conjugate words w, w' correspond conjugate elements β, β' in the field extension K/F, and that w \mapsto β 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.

Comment by Diego de Estrada

2010-10-21T03:39:16Z

One detail: there is a particular poly-time computable function that is one-way iff they exist. See cs.cornell.edu/courses/cs687/2006fa/lectures/…

Comment by Diego de Estrada

2010-10-03T12:42:07Z

How does this categorical argument work in the case of computable sets? (Myhill isomorphism theorem)

Comment by Diego de Estrada

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ürgisser et al.

Comment by Diego de Estrada

2010-08-04T18:12:56Z

Perhaps you want "structure theorems" more like Myhill-Nerode's for Regular languages and Chomsky-Schützenberger's for Context-free languages.

Comment by Diego de Estrada

2010-04-26T07:04:49Z

I like your observation about modelling optimization problems, can you provide some reference?

Comment by Diego de Estrada

2010-04-06T03:27:13Z

Thank you very much, Qiaochu!

Comment by Diego de Estrada

2010-04-06T00:45:25Z

@dan, this is the sequence for the first shape: research.att.com/~njas/sequences/A088960 (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.

Comment by Diego de Estrada

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 & bottom sides, not the slope.)

Comment by Diego de Estrada

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)

Comment by Diego de Estrada

2009-10-24T06:58:49Z

I'm quite embarrased to know it was so easy. Thanks!