FOCS Last Day

Last (but surely not least) day at FOCS 09!

Jan Vondrak talked about some nice results that unify previous query complexity approaches in proving lower bounds for submodular function maximization. For a general class of functions he proves that good approximations require an exponential number of queries to the value oracle. This duplicates known inapproximability results, and also implies new bounds in two particular problems.

Another interesting work was presented by Heiko Roeglin who proved bounds on the size of Pareto-optimal sets in the context multiobjective optimization. In the general case it is almost always possible to find instances of problems with exponentially large Pareto sets. This renders any approach based on analyzing Pareto sets unfeasible. However, in many real world applications, it turns out that these sets are typically small. Roglin and Shang-Hua Teng give a possible theoretical explanation for this, in the framework of smoothed analysis, proving that the expected number of Pareto-optimal solutions is polynomially bounded.

To conclude the 50th of FOCS, Ryan Williams gave a much appreciated talk on new approaches in boolean matrix multiplication. The aim of the paper was to come up with a more efficient combinatorial algorithm for Boolean matrix multiplication. Ryan and Nikhil Bansal succeed in this direction by connecting Boolean matrix multiplication and the triangle removal lemma. Their approach gives the first improvement on general upper bounds for this problem in 40 years!