Communication complexity lower bounds

I just discovered a spectacular survey article on communication complexity lower bounds. The paper is below.

Troy Lee and Adi Shraibman (2007) “Lower Bounds in Communication Complexity”,

Foundations and Trends® in Theoretical Computer Science: Vol. 3: No. 4, pp 263–399.

You can find a draft in Troy Lee's homepage.

Finished reading it, not with full details, but enough for understanding the bigger picture in the proof technique they use. Now I'm ready to read it for a second time, but this time going deeper into the details. First let's review the communication model. There are two players, Alice (A) and Bob (B), and they want to solve a problem together call it f which will be a boolean function. The input to f is divided between A and B, so in order to solve the problem they will need to communicate. The complexity is the minimum number of bits that need to be interchanged to solve the problem. The running time of A and B is not taken into account. All communication is defined by the communication matrix M, which is defined as M[x,y]=f(x,y), i.e. the rows and columns are indexed by the inputs to A and B, and each entry is the value of f. Changing the acceptance condition for the model we get a deterministic, randomized (two, one and zero-sided) or a nondeterministic model. If we allow the player to send qubits we get quantum. It can also be generalized to multiparty communication with all different flavors like the topology of communication, the way the parties access the input, etc.

Since communication complexity is more about lower bounds, all research is devoted to this. Upper bounds in this models are implied by upper bounds in the decision tree model. The general idea of proving lower bound is the following three steps procedure:

1. Embed the communication matrix onto the reals. This is done by a mapping from some operator norm to an euclidean norm.
2. Formulate the problem using the embedding as a maximization problem.
3. Give a witness for the objective function of the resulting program.

I would say that step 1 is the easiest because there is a lot of work done there, so you just need to choose the most fit for your problem. Although, there is still many open problems here to solve like the famous log-rank conjecture. The second step depends in the duality between the studied norms. The objective here is to avoid dealing with forall quantifiers (minimization), and solve the problem for existential quantufiers (maximization). This is because it's easier to just give a witness for the program, rather that showing that for all inputs the solution is optimal. The final step requires a witness for the resulting program. This could also be very difficult, because choosing a bad witness (one that is too far from the global optimum) could give a very weak or trivial lower bound. In the paper, the authors show how to choose a good witness for a particular case. Only for very few cases we know how to choose a good witness, and more research is needed in this part.

The paper ommits models like SMP (simultaneous message passing), unbounded-error protocols, and quantum communication with entanglement. The authors concentrate in lower bounds that can be stated in terms of a mathematical program by using norms. Still, they give a nice explanation on the corruption bound. This is an important technique because as noted by the authors it is the only lower bound technique that can separate quantum from randomized communication for total functions.

Back to blogging in spanglish

Following the momentum given by Alejandro, I will also start writing in english. Well, actually I will do it either in english or spanish. I don't think I'll do it at the same time, mostly due to my increasing lazyness in the last couple of months.

The last two months I was simply overloaded with work at school, from TA work, reports, msc thesis, etc etc. Now, I'm finishing the thesis (but surely my advisors are going to give something else to add), passed the qualifying exam, finished sending two grant proposals (and writing a third one), I feel that I can start writing some posts.

It pains me to say that although my native language is spanish, I feel more comfortable writing in english. In the last 5 years, I only wrote one technical paper in spanish, so I think it's only a matter of practice though.

Well, what happened the last 2 months? For me, what I already mentioned above, but in the academic/internet world some very interesting stuff happened. For example, the recent breakthrough in computational complexity by Ryan Williams, i.e. NEXP not included in ACC0 (paper here). NEXP is known as the exponential NP and ACC0 is the class of languages with polynomial size circuits with bounded fan-in and constant depth with mod gates. Although ACC0 is a very low class, and NEXP is waay above, this "was" a open problem for more than 20 years! This paper presented a real progress in circuit lower bounds after all this time.

Also, the CSTheory stackexchange site is blooming! I was very disconnected from here also, but seeing the questions and answers today I can see that a lot more of people joined.

Finally, the QIP2011 programme is out!. Many interesting talks, but one caught my eye. "Quantum One-Way Communication can be Exponentially Stronger Than Classical Communication" by Oded Regev (paper here). This has been an open problem for around 10 years, and is very much related to what I'm doing.

Empezando a bloggear en English

(Versión en español más abajo)
From now on, I will start posting both in English and in Spanish. Why? Well, the reason to continue blogging in Spanish is that I feel that all this years blogging (from 2005) allowed me to meet lot of people, mostly in Latin America, to interact with; people doing research in quantum computing or just interested in the topic. Thus I don't want to lose such an opportunity to continue interacting with those people. I am aware that most of them should know English, however, blogging in Spanish was the reason of why this blog became (modestly) popular.
So, why to start blogging in English then? Because I want also to join the large community of academic bloggers in the world, and the common language in academia around the world is English.

Just to start, a bit of history:
This blog, "Computación Cuántica" (Spanish for quantum computing) was started by me in 2005, when I started being interested by the topic, back in Argentina during my undergraduate studies. Last year Daniel Villagra, a Paraguayan researcher based in Japan, joined to the blog and started updating the blog as well. Most posts are about our research. I am working on lambda calculus, type theory and logics, for quantum computing, and Danny is working in complexity, algorithms and automata.
From now on, I will blog both in English and Spanish, however I don't know what Danny will do (is up to him, I didn't ask him yet (sorry for that)).
So, finally: WELCOME. I hope you enjoy our blog.

---

Desde ahora, voy a empezar a postear tanto en inglés como en español. Porqué? Bueno, la razón para continuar blogueando en español es que siento que todos estos años blogueando (desde 2005) me permitieron conocer mucha gente, principalmente en América Latina, con quienes interactuar; gente investigando en computación cuántica o simplemente interesada en el tema. Por lo tanto no quiero perder la oportunidad de continuar interactuando con esa gente. Ya sé que la mayoría debe saber inglés, sin embargo, bloguear en español es lo que hizo que este blog se vuelva (modestamente) popular.
Ahora, porqué comenzar a bloguear en inglés entonces? Porque quiero unirme a la gran comunidad de blogs académicos en el mundo, y el lenguaje común en la academia en el mundo es inglés.

Un poco de historia:
Este blog lo comencé en 2005, cuando empecé a interesarme en el tema, aún en Argentina, durante mis estudios de grado. El año pasado Daniel Villagra, un paraguayo en Japón, se unió al blog y comenzó a postear también. La mayoría de los posts son sobre nuestras investigaciones. Yo estoy trabajando en cálculo lambda, teoría de tipos y lógica, para computación cuántica y Danny está trabajando en complejidad, algoritmos y autómatas.
Desde ahora, voy a bloguear en inglés y español, sin embargo no sé lo que hará Danny (depende de él, no le he preguntado aún (perdón por eso)).
Así que, finalmente: BIENVENIDOS, espero que disfruten el blog.

Escalares y sumas, al arXiv // Scalars and sums, to arXiv

(English version below)
Ya está disponible el paper que escribimos con Barbara Petit sobre el análisis de las sumas en los cálculos algebraicos que presentamos en Types 2010. La semana pasada lo subimos al arXiv: http://arxiv.org/abs/1011.3542.

También la semana pasada con Pablo Arrighi actualizamos en el arXiv el paper sobre los escalares en los cálculos algebraicos. En este caso es un sistema de tipos que nos permite llevar de cierta manera una cuenta de 'la cantidad de un tipo' que participa en cada término. Acá dejo el link: http://arxiv.org/abs/0903.3741v4.

Ambos casos son análisis del lambda cálculo algebraico-lineal de Pablo Arrighi y Gilles Dowek, el cual fue pensado originalmente como un lambda cálculo cuántico, en el sentido de que permite encodear algoritmos cuánticos y está diseñado de tal manera de no permitir cloneo.

---

It is now available the paper we wrote with Barbara Petit about the analysis of sums in algebraic calculi, presented in Types 2010. Last week we uploaded it to arXiv: http://arxiv.org/abs/1011.3542.

Also last week with Pablo Arrighi we updated in the arXiv our paper about scalars in algebraic calculi. In this case it is a type system which allows us to take care of the 'amount of a type' that participates in each term. Here it is the link: http://arxiv.org/abs/0903.3741v4.

Both papers are analyses of the linear-algebraic lambda-calculus developed by Pablo Arrighi and Gilles Dowek, which was originally thought as a quantum lambda calculus, in the sense that it allows to encode quantum algorithms and it is designed to not allow clonning.