## You shall not bear false witness against your neighbor

### August 20, 2009

On the 5th of august the new leader of the iranian parliament swore in front of the Corano:

But can one swore if elections were cheated? How do I know? It is not me but statistics: page 6, figure 6 of this link you may see a graphic were in the seventh place three signs are not aligned with what we expected. What does that mean? In practice take the number of voters for candidate Karroubi, we will have 366 numbers (there are 366 area where to vote), now take the first digit of these numbers, statisticians know very well that the digit 1 should show up 30% of the times, digit 2 the 17%, digit 3 the 12% etc. 7 should show up the 6% of the time. In practice it appeared the 11%.

The probability this happened by chance are 0.02%

Or they cheated.

## Limits of Approximation Algorithms: PCPs and Unique Games (Part 1: PCPs)

### August 8, 2009

Three weeks ago I have been to a workshop entitled “Limits of approximation algorithms: PCPs and unique games“, the travel expenses were kindly covered by DIMACS. Really nice university in New Jersey. But, guys, New Jersey is not for those without a car.

I will give a rough explaination of the complicated, intricated, probabilistical, fouriertical, technicals but still fascinating concepts around here.

So what is a PCP? It is a Probabilistically Checkable Proof, that is a mathematical proof whose correcteness can be checked by looking at it in random places. Indeed it is something more, it is locally testable, that is we need few bits. And indeed only a constant number of bits, 3.

It does not look so new until here, we can just take a mathematical proof and convert it with some error correcting code trick and get an object with higher redundance. The technique used here is the Fourier transform on the boolean cube, wonderful and versatile tool. (Don’t lose the majority is stablest theorem, really cool)

On the other side we have the mighty NP, the class of problems whose solutions can be checked in polynomial time. This class is really powerful. For example one problem that is in NP is the one of satysfying all the formulas in a set $\{x_{i_1} \vee x_{i_2} \vee x_{i_3} | i1,i2,i3 \in [1,n], \x_{u}\in{\text{true},\text{false}}\}$, each formula is an OR of three variables, those can be also negative, of course. This problem is called MAX-3SAT. A solution can be checked in polynomial time. Finding it may require trying all the possibilities around.

Now imagine that we are more modest and we simply want to maximize a lot of these clauses, a substantial percentage of the maximum number of them satisfiable for an istance of the problem. One very simple algorithm is going random: try a lot of random assignments! If you think for a while to this algorithm you may see that the approximation of this algorithm is $\frac{7}{8}$, that is we can expect from this algorithm to have satisfied $\frac{7}{8}$ of the satisfiable clauses. Not so bad for a random typing monkey.

Ok, now it comes the hardness of approximation: we cannot get a polynomial time algorithm, for this problem, that does better than the random typing monkey! That is, if we have one that give us $\frac{7}{8} + \epsilon$ satisfied clauses then P would be equal to NP, and as a friend of mine says we would be like god, or we could just get 1’000’000 dollars.

Wonderful. Where is the PCP? Well a proof of Hastad that NP = PCP(3 queries, $log(n)$ random bits) implies the previous fact.

The main topic of the tutorial was the Unique Games Conjecture, see the part 2. For a clear explaination of all the stuff: Computational Complexity: A Modern Approach

## Slops Slops

### August 5, 2009

After my post about our women officer I found a confirmation about my suspects about Minister Mara Carfagna:

She is not youth because she is minister, she is minister because she is youth, and did sexual favors to Silvio Berlusconi.

## Pretty Women

### August 1, 2009

Props and Slops for the women chosen by Silvio Berlusconi for his governement. There are, from left to right or I should say from best to worst, Giorga Meloni, Maria Stella Gelmini, Mara Carfagna and Stefania Prestigiacomo:

Giorgia Meloni: minister of youth

Journalist and politician, this woman became minister at 31 and last year invited italian olympionics to boicot China olympiads for the bad decisions made by the chinese governement against Tibet. Props for her.

Maria Stella Gelmini: minister of public school

About her we do not know much, because she is so reserved. Personally I am not charmed by her because she does not have so much charisma:

Mara Carfagna: minister for the equal opportunities

Mara was born on 1977 and in her biography she can write a 6th place in the beauty context “Miss Italia”, she conducted for five years an italian program and in 2005 she did a calendar:

Maybe it is me but it looks weird that a woman with this expertise is an example for the “equal opportunities”. Why not choosing a business woman?

Stefania Prestigiacomo: Minister of the enviroment

Business woman she has been minister for the equal opportunities from 2001 to 2006, for sure more fit than Carfagna. For the enviroment she is a disaster: can she declare that nuclear energy is the cleanest possible???

47-th second

I would conclude this short presentation with 1 PROPS, 1 SO/SO and 2 SLOPS!