22 de julio de 2010

Número de sumas de subconjuntos

Estuve probando un poco de MathOverflow y realmente me sorprendió lo rápido en que las personas leen y responden a tus preguntas. La pregunta que hice fue sobre el número de soluciones para sumas de subconjuntos (subset sums). Sea Fq un campo finito con característica p tal que p < q (i.e. no es un campo primo). Sea D Fq un subconjunto con |D| = n. El problema de la suma de subconjuntos consiste en encontrar un subconjunto no vacío {x1,,xk}⊆ D tal que x1 + ...  xk = s dado s Fq. Cuántas soluciones aproximadamente permite el problema para un conjunto dado D? Que pasa si seleccionamos D en forma aleatoria?

La respuesta que obtuve fue la siguiente (la versión escrita aquí está mas desarrollada): Tenemos n elementos de los cuales k tienen que sumar s, entonces tenemos \begin{pmatrix} n\\ k \end{pmatrix} candidatos. Sea D = {a1,,an} y definamos la variable aleatoria X como la suma de k elementos de D, i.e. X = ax1 + ... + axk. Las variables xi son índices. Tenemos asi que Pr(X = 0) = P(X = 1) =\dots= P(X = s) = \dotsP(X = q - 1) = \frac{1}{q}. Por lo tanto el número aproximado de soluciones que suman s es claramente . Bien sencillito.

Para el caso D aleatorio supongamos que tenemos una solución x1 + ... + xk. Para una D aleatoria con |D| = n la probabilidad p de que todas las xi en la solución esten presentes en D es


.


El numerador es así porque para la solución dada solo combinamos los elementos que son diferentes a cada xi. Entonces p es igual para cada solución. Considerando que el número total de soluciones para todo el campo es (cf. párrafo de arriba), haciendo cuentas el valor esperado es




.


Claramente ambas respuestas deben de coincidir porque en el fondo para responder la primera pregunta hacemos uso de índice aleatorios.

Obs: Esta entrada la escribí usando TtH y el Online LaTeX Equation Editor en modo de prueba. La conclusión es utilizar TtH, y lo que no pueda convertir a html, hacerlo con el editor de ecuaciones.

11 de julio de 2010

Theory Overflow

Para las personas interesadas en computación teórica existe un sitio web que está comenzando a promoverse para establecer discusiones sobre el tema. Temas que van desde computación cuántica, complejidad computacional, lógica, lenguajes de programación, etc. Todos por supuesto temas teóricos.

El problema está en que antes de volverse totalmente activo y ser aceptado por los administradores, debe de tener el suficiente apoyo de personas que firmen con su nombre y se comprometen a participar.

Si alguien está interesado puede hacer click en el enlace de abajo, inscribirse y darle en "commit".

Theory OverFlow

Muchos investigadores exitosos en el área ya están inscriptos y dispuestos a interactuar en el sitio. Esto puede ser muy beneficioso para que estudiantes puedan hacer preguntas y esperar que expertos les respondan.

Existe un sitio similar, pero es sobre matemáticas en general: MathOverFlow. Si hay personas interesadas también pueden unirse ahí. La diferencia está en que Theory OverFlow es estrictamente computación teórica.

2 de julio de 2010

Papers de FOCS 2010

Ya salió la lista de papers aceptados en FOCS 2010. Shiva Kintali realizó un gran trabajo creando una lista de los papers con enlaces a ArXiv en su blog.

Hay solo uno relacionado con computación cuántica, y luego de leer el resumen parece muy interesante.

An efficient test for product states, with applications to quantum Merlin-Arthur games. Aram W. Harrow and Ashley Montanaro. [ArXiv].

Otro que me llamó la atención es

New Constructive Aspects of the Lovasz Local Lemma. Bernhard Haeupler, Barna Saha and Aravind Srinivasan. [ArXiv].