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 (unless NP = RP) with

respect to AP polynomial time reductions. 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”