RANDOM + APPROX 2010

Today is raining. Usual.
It happens to me to be in Barcelona, Catalunya.
I am here because I am attending RANDOM + APPROX 2010, (13th Intl. Workshop
on Approximation Algorithms for Combinatorial Optimization Problems - APPROX 2010
14th Intl. Workshop on Randomization and Computation - RANDOM 2010… well, for the
record).
Yesterday, the first invited lecture, has been given by Leslie A Goldberg; title: Approximating
the Tutte polynomial of a graph.
The talk was very nice and covered many approximation results concerning the famous
polynomial. Something quite interesting is that, apart from some results in special cases
where the Tutte pol. admits a FPRAS, in many cases, like for binary matroids, the hardness
of the problem, in terms of optimization problems, is defined in a way that is essentially
the same used in game theory. In particular, as Nash equilibria is in PPAD and is moreover
complete in the class, Tutte (in some cases) is hard in \#RH\Pi_1 (unless NP = RP) with
respect to AP polynomial time reductions. \#RH\Pi_1 contains the problems that can be
expressed in terms of counting the number of models of a logical formula from a certain
syntactically restricted class which is also known as “restricted Krom SNP”. As PPAD,
this class descends from a semantic class of problems (classes in which properties are
defined over all possible inputs). These classes are unlikely to admit complete problems,
so syntactical restrictions are applied in order to find hardness results.

Today, Oded Goldreich has given a very vivid talk about pseudo random generators
and the problem of deciding whether P=BPP or not.
The talk was really really nice: Oded strongly supported his ideas on where is more
likely to find a proof for the inequality to hold or not. Essentially he thinks that it is not
using lower bounds that it will be possible to face the problem, but using some sort
of diagonalization. He also presented a recent result of his, stating that if BPP=P then
a suitable pseudo number generator must exist.
There is a bunch of interesting consequences associated with this result, but I need to
read the paper before writing anything about it!

Smart thing of the organizers to schedule the invited lectures in the second half of the
morning, so that also the lazier ones can stand a chance of getting something without
falling tremendously asleep (if attending the talk at all…).
Tomorrow is the last day, then I will be flying over the Pyrenees, passing by the Alps
and away form the mare nostrum again.

0 Responses to “RANDOM + APPROX 2010”


  1. No Comments

Leave a Reply

You must login to post a comment.