This talk is about replacing bits with vectors. Goemans and Williamson did this for MAX-CUT and got the best known polynomial-time approximation algorithm. We wanted to know whether moving to vectors will help us prove certain communication complexity lower bounds (and hopefully circuit depth lower bounds too). Moving to vectors has a strong benefit (via duality, "short" lower bound proofs are guaranteed for all lower bounds) but one downside (some hard functions may become easy). To analyze this question we create two natural vector variants of communication protocols (both phrased as Semidefinite Programs), and we set out to prove lower bounds for the Equality function. Our results are as follows:
- The natural vector variant of the Pigeonhole Principle is true.
- Nevertheless in both of these communication variants Equality is actually easy to compute! (This implies that the circuit depth lower bounds are also not achievable.)
After this work we realized that a work of Austrin and Risse already show a no-go theorem: circuit depth lower bounds can not be achieved through semidefinite programs! Given this we will focus on the parts of our paper that are not covered by theirs: The Pigeonhole Principle variant, and results about the communication variants that are not directly linked to the circuit no-go theorem.
This is joint work with Pavel Dvorák and Bruno Loff.
