FOCS 2015

This is an odd-numbered year, and FOCS is back in Berkeley. The conference, whose early registration deadline is coming up, will be held on October 18-20 at the Double Tree hotel near the Berkeley marina, the same location of FOCS 2013, and it will be preceded by a day-long conference in honor of Dick Karp’s 80th birthday.

Early registration closes next Friday, so make sure that you register before then.

The weekend before FOCS there will be the Treasure Island Music Festival; Treasure Island is halfway along the Bay Bridge between Oakland and San Francisco, and from the Island there are beautiful views of the Bay Area.

After FOCS, there is a South Asian Film Festival in San Francisco.

If you arrive on Friday the 16th and you want to spend an afternoon in San Francisco, at the end of the day you can find your way to the De Young Museum in Golden Gate park, which stays open until 8:30pm on Fridays, and it has live music and a bar in the lobby from 5:30 to 8:30.

Did I mention that the early registration deadline is coming up? Don’t forget to register.

On Berkeley and Recycling

For the past few days, I have been getting emails that are the Platonic ideal of the U.C. Berkeley administration.

Today, there was a one-hour presentation on recycling and composting at Soda Hall, the computer science building. This is worth saying once more: a one hour presentation on putting glass, metal, and certain plastics in one container, clean paper in another, and compostable material in a third one. We received an email announcement, then an invitation to add the event to our calendar, then two remainders.

But what if one cannot make it? Not to worry! There will be a second one hour presentation on recycling, for those who missed the first one, and for those that were so enthralled by the first one that they want to spend one more hour being told about recycling.

Meanwhile, I have been trying since February to get a desk, a conference table and a bookshelf for my office in Soda Hall. So far I got the desk.

I asked Christos what he thought about the two one-hour presentations on recycling, and he said it reminded him of a passage from a famous essay by Michael Chabon:

Passersby feel empowered-indeed, they feel duty-bound-to criticize your parking technique, your failure to sort your recycling into brown paper and white, your resource-hogging four-wheel-drive vehicle, your use of a pinch-collar to keep your dog from straining at the leash.

Sometimes I think that when the administration started hearing about MOOCs, they must have started to dream about a future with no professors, because the students all take MOOCs, and no students on campus, because they all take the MOOCs from their home, and the campus would just be filled by Assistant Chancellors of this and that, giving each other training workshops. And this would be like the episode of Get Smart in which Max infiltrates a criminal gang until he finds out that everybody is an infiltrator and there is no criminal left.


Happy Qi Xi festival, everybody. This is the “Chinese Valentine’s day,” which falls on July 7th on the lunar calendar, which this year is August 20th. The festivity relates to a story that, like many Chinese stories, is a pretty long story.

The gist of it is that the (seventh) daughter of a goddess at some point came to earth to live as a mortal and met a cowboy (as in, a guy whose job is to herd cows). The two fell in love, got married, had two children (I told you, it’s a long story) and they were pretty happy, until the goddess mom realized what happened.

As is mothers-in-law’s wont, she did not approve, and she recalled the daughter to heaven, where she is now the star Vega. The guy was desperate, but then one of his cows suggested that he kills it, and then use its skin to fly to heaven (don’t ask) and reunite with his wife.

He does so, and it works, so that he is now the star Altair, but then the mom-in-law found out again. So she created a river, the Milky Way, to separate them once more. And now they are forever separated, except that, every year, magpies (which are a kind of crows) fly to heaven and use their bodies to create a bridge over the Milky Way, so that the two lovers can use it to meet. And this happens on the 7th day and the 7th month of the year.

What a difference thirty years make

From the majority opinions of two rulings of the Supreme Court of the United States.

Bowers v. Hardwick (1986):

The Constitution does not confer a fundamental right upon homosexuals to engage in sodomy. […] to claim that a right to engage in such conduct is “deeply rooted in this Nation’s history and tradition” or “implicit in the concept of ordered liberty” is, at best, facetious.

Obergefell v. Hodges (2015)

[Same-sex couples] ask for equal dignity in the eyes of the law. The Constitution grants them that right. The Constitution […] does not permit the State to bar same-sex couples from marriage on the same terms as accorded to couples of the opposite sex.

Two recent papers by Cui Peng

Cui Peng of Renmin University in Beijing has recently released two preprints, one claiming a proof of P=NP and one claiming a refutation of the Unique Games Conjecture; I will call them the “NP paper” and the “UG paper,” respectively.

Of all the papers I have seen claiming a resolution of the P versus NP problem, and, believe me, I have seen a lot of them, these are by far the most legit. On Scott Aronson’s checklist of signs that a claimed mathematical breakthrough is wrong, they score only two.

Unfortunately, both papers violate known impossibility results.

The two papers follow a similar approach: a certain constraint satisfaction problem is proved to be approximation resistant (under the assumption that P{\neq}NP, or under the UGC, depending on the paper) and then a Semidefinite Programming approximation algorithm is developed that breaks approximation resistance. (Recall that a constraint satisfaction problem is approximation resistant if there is no polynomial time algorithm that has a worst-case approximation ratio better than the algorithm that picks a random assignment.)

In both papers, the approximation algorithm is by Host, and it is based on a semidefinite programming relaxation studied by Charikar and Wirth.

The reason why the results cannot be correct is that, in both cases, if the hardness result is correct, then it implies an integrality gap for the Charikar-Wirth relaxation, which makes it unsuitable to break the approximation resistance as claimed.

Suppose that we have a constraint satisfaction problem in which every constraint is satisfied by a {p} fraction of assignment. Then for such a problem to not be approximation resistant, we have to devise an algorithm that, for some fixed positive {\delta>0}, returns a solution whose cost (the number of constraints that it satisfies) is at least {p+\delta} times the optimum. The analysis of such an algorithm needs to include some technique to prove upper bounds for the true optimum; this is because if you are given an instance in which the optimum satisfies at most a {p+o(1)} fraction of constraints, as is the case for a random instance, then the algorithm will satisfy at most a {p+o(1)} fraction of constraints, but then the execution of the algorithm and the proof of correctness will give a (polynomial-time computable and polynomial-time checkable) certificate that the optimum satisfies at most a {(p+o(1))/(p+\delta) < 1 - \delta + o(1)} fraction of constraints.

For algorithms that are based on relaxations, such certificates came from the relaxation itself: one shows that the algorithm satisfies a number of constraints that is at least {p+\delta} times the optimum of the relaxation, and the optimum of the relaxation is at least the optimum of the constraint satisfaction problem. But if there are instances for which the optimum is {p+o(1)} and the optimum of the relaxation is {1-o(1)}, then one cannot use such a relaxation to design an algorithm that breaks approximation-resistance. (Because on, such instances, the algorithm will not be able to satisfy a number of constraint equal to {p+\delta} times the optimum of the relaxation.)

In the UG paper, the approximation resistance relies on a result of Austrin and Håstad. Like all UGC-based inapproximability results that I am aware of, the hardness results of Austrin and Håstad are based on a long code test. A major result of Raghavendra is that for every constraint satisfaction problem one can write a certain SDP relaxation such that the integrality gap of the relaxation is equal to the ratio between soundness and completeness in the best possible long code test that uses predicates from the constraint satisfaction problem. In particular, in Section 7.7 of his thesis, Prasad shows that if you have a long code test with soundness {c} and completeness {s} for a constraint satisfaction problem, then for every {\epsilon > 0} there is an instance of the problem in which no solution satisfies more than {s+\epsilon} fraction of constraints, but there is a feasible SDP solution whose cost is at least a {c-\epsilon} fraction of the number of constraints. The SDP relaxation of Charikar and Wirth is the same as the one studied by Prasad. This means that if you prove, via a long code test, that a certain problem is approximation resistant, then you also show that the SDP relaxation of Charikar and Wirth cannot be used to break approximation resistance.

The NP paper adopts a technique introduced by Siu On Chan to prove inapproximability results by starting from a version of the PCP theorem and then applying a “hardness amplification” reduction. Tulsiani proves that if one proves a hardness-of-approximation result via a “local” approximation-reduction from Max 3LIN, then the hardness-of-approximation result is matched by an integrality gap for Lasserre SDP relaxations up to a super-constant number of rounds. The technical sense in which the reduction has to be “local” is as follows. A reduction from Max 3LIN (the same holds for other problems, but we focus on starting from Max 3LIN for concreteness) to another constraint satisfaction problems has two parameters: a “completeness” parameter {c} and a “soundness” parameter {s}, and its properties are that:

  • (Completeness Condition) the reduction maps instances of 3LIN in which the optimum is {1-o(1)} to instances of the target problem in which the optimum is at least {c-o(1)};
  • (Soundness Condition) the reduction maps instances of 3LIN in which the optimum is {1/2 +o(1)} to instances of the target problem in which the optimum is at most {s+o(1)}.

Since we know that it’s NP-hard to distinguish Max 3LIN instances in which the optimum is {1-o(1)} from instances in which the optimum is {1/2 +o(1)}, such a reduction shows that, in the target problem, it is NP-hard to distinguish instances in which the optimum is {c-o(1)} from instances in which the optimum is {s+o(1)}. The locality condition studied by Tulsiani is that the Completeness Condition is established by describing a mapping from solutions satisfying a {1-o(1)} fractions of the Max 3LIN constraints to solutions satisfying a {c-o(1)} fraction of the target problem constraints, and the assignment to each variable of the target problem can be computed by looking at a sublinear (in the size of the Max 3LIN instance) number of Max 3LIN variables. Reductions that follows the Chan methodology are local in the above sense. This means that if one proves that a problem is approximation-resistant using the Chan methodology starting from the PCP theorem, then one has a local reduction from Max 3LIN to the problem with completeness {1-o(1)} and soundness {p+o(1)}, where, as before, {p} is the fraction of constraints of the target problem satisfied by a random assignment. In turn, this implies that not just the Charikar-Wirth relaxation, but that, for all relaxations obtained in a constant number of rounds of Lasserre relaxations, there are instances of the target problem that have optimum {p+o(1)} and SDP optimum {1-o(1)}, so that the approximation resistance cannot be broken using such SDP relaxations.

How many theoreticians does it take to approximate Max 3LIN?

Sufficiently many to start a soccer team.

Some constraint satisfaction problems are approximation resistant, in the sense that, unless P=NP, there is no polynomial time algorithm that achieves a better approximation ratio than the trivial algorithm that picks a random assignment. For example, a random assignment satisfies (on average) a {\frac 78} fraction of the clauses of a given Max 3SAT instance, and, for every {\epsilon >0}, it is NP-hard to achieve approximation {\frac 78 + \epsilon}. Max 3LIN is the variant of Max 3SAT in which every constraint is a XOR instead of an OR of variables; it is another example of an approximation resistant problem, because a random assignment satisfies (on average) half of the constraints, and approximation {\frac 12 + \epsilon} is NP-hard for every {\epsilon >0}. (These, and more, hardness of approximation results were proved by Håstad in 1997, in a paper with a notably understated title.)

In 2000, Håstad proved that if we restrict constraint satisfaction problems to instances in which every variable occurs in (at most) a fixed constant number of constraints, then the problem is never approximation resistant. If we have a constraint satisfaction problem in which each constraint is satisfied with probability {p} by a random assignment, and each variable appears in at most {D} constraint, then there is a simple polynomial time algorithm that achieves an approximation ratio {p + \Omega\left( \frac 1 D \right)}. The following year, I showed that if we have a constraint satisfaction problem that is NP-hard to approximate within a factor of {r}, then it is also NP-hard to approximate within a factor {r + \frac c{\sqrt D}}, where {c} is a constant (whose value depends on the specific constraint satisfaction problem), when restricted to instances in which every variable occurs at most {D} times.

Thus, for example, if we restrict to instances in which every variable occurs in at most {D} constraints, Max 3SAT can be approximated within a factor {\frac 78 + \frac{c_1}{D}} but not {\frac 78 + \frac{c_2}{\sqrt D}}, and Max 3LIN can be approximated within a factor {\frac 12 + \frac {c_3}{D}} but not {\frac 12 + \frac{c_4}{\sqrt D}} in polynomial time, unless {P=NP}, where {c_1,c_2,c_3,c_4} are constants.

Last Fall, Prasad Raghavendra and I worked for a while on the problem of bridging this gap. The difficulty with Max 3SAT is that there are instances derived from Max Cut such that every variable occurs in at most {D} clauses, there is no “trivial contradiction” (such as 8 clauses over the same 3 variables, which have a fixed contribution to the cost function and can be eliminated without loss of generality), and every assignment satisfies at most {\frac 78 + \frac {O(1)}{D}} clauses. If we want an approximation ratio {\frac 78 + \Omega(D^{-1/2})}, we need our algorithm to certify that such instances are unsatisfiable. It is probably possible to show that there are simple LP or SDP relaxations of Max 3SAT such that a polynomial time algorithm can find assignments that satisfies a number of clauses which is at least a {\frac 78 + \Omega(D^{-1/2})} times the optimum of the relaxation, but we could not find any way to reason about it, and we gave up. Also, we wrongly assumed that there was the same issue with Max 3LIN.

Meanwhile, Farhi, Goldstone and Gutmann, who had successfully developed a quantum algorithm to approximate Max Cut on bounded degree graphs, were looking for another problem to tackle, and asked Madhu Sudan what was known about NP-hard and Unique Games-hard problems on bounded degree instances. They were particularly interested in Max 3SAT in bounded-degree instances. Madhu referred them to me, Sam Gutmann happened to be in the Bay Area, and so we met in November and I pointed them to the known literature and suggested that they should try Max 3LIN instead.

A month later, I heard back from them, and they had a {\frac 12 + \Omega \left( \frac 1 {D^{3/4}} \right)} approximate algorithm for Max 3LIN. That sounded amazing, so I went looking into the paper for the section in which they discuss their upper bound technique, and there is none. They show that, for every instance that does not have trivial contradictions (meaning two constraints that are the negation of each other), there is an assignment that satisfies a {\frac 12 + \Omega ( D^{-3/4})} fraction of constraints, and they describe a distribution that, on average, satisfies at least as many. The distribution is samplable by a quantum computer, so the approximation, in their paper, is achieved by a quantum algorithm.

After realizing that we had been wrong all along on the need for non-trivial upper bounds for Max 3LIN, Prasad and I tried to find a way to replicate the result of Farhi et al. with a classical algorithm, and we found a way to satisfy a {\frac 12 + \Omega(D^{-1/2})} fraction of constraints in instances of constraint satisfaction problems “without triangles” (a result of this form is also in the paper of Farhi et al.), and then a {\frac 12 + \Omega(D^{-1/2})} fraction of constraints in all Max 3LIN instances.

The day before submitting our paper to ICALP (from which it would have been rejected without consideration anyways), I saw a comment by Boaz Barak on Scott Aronson’s blog announcing the same results, so we got in contact with Boaz, who welcomed us to the club of people who had, meanwhile, gotten those results, which also included Ankur Moitra, Ryan O’Donnell, Oded Regev, David Steurer, Aravindan Vijayaraghavan, David Witmer, and John Wright. Later, Johan Håstad also discovered the same results. If you kept count, that’s eleven theoreticians.

The paper is now online (with only 10 authors, Johan may write posted a separate note); we show that a {\frac 12 + \Omega(D^{-1/2})} fraction of constraints can be satisfied in all Max kLIN instances, with odd {k}, and a {\Omega(D^{-1/2})} advantage over the random assignment can be achieved in all “triangle-free” instances of constraint satisfaction problems. It remains an open problem to improve Håstad’s {\frac 78 + O(D^{-1})} approximation for Max 3SAT.

The argument for Max 3LIN is very simple. Khot and Naor prove that, given a Max 3LIN instance {I}, one can construct a bipartite Max 3LIN instance {I'} such that an assignment satisfying a {\frac 12 + \epsilon} fraction of constraints in {I'} can be easily converted into an assignment satisfying a {\frac 12 + \Omega(\epsilon)} fraction of constraints of {I}; furthermore, if every variable occurs in at most {D} constraints of {I}, then every variable occurs in at most {2D} constraints of {I'}.

An instance is bipartite if we can partition the set of variables into two subsets {X} and {Y}, such that each constraint involves two variables from {X} and one variable from {Y}. The reduction creates two new variables {x_i} and {y_i} for each variable {z_i} of {I}; every constraint {z_i \oplus z_j \oplus z_k = b} of {I} is replaced by the three constraints

\displaystyle  x_i \oplus x_j \oplus y_k = b

\displaystyle  x_i \oplus y_j \oplus x_k = b

\displaystyle  y_i \oplus x_j \oplus x_k = b

Given an assignment to the {X} and {Y} variables that satisfies a {\frac 12 + \epsilon} fraction of the constraints of {I'}, Khot and Naor show that either {X}, or {Y}, or an assignment obtained by choosing {z_i} to be {x_i} with probability {1/2} or {y_i} with probability {1/2}, satisfies at least a {\frac 12 + \Omega(\epsilon)} fraction of constraints of {I}.

It remains to show that, given a bipartite instance of Max 3LIN in which every variable occurs in at most {D} constraints (and which does not contain two equations such that one is the negation of the other), we can find an assignment that satisfies a {\frac 12 + \Omega( D^{-1/2})} fraction of constraints.

The idea is to first pick the {X} variables at random, and then to pick the {Y} variables greedily given the choice of the {X} variables.

When we pick the {X} variables at random, the instance reduces to a series of constraints of the form {y_i = b}. Each variable {y_i} belongs to (at most, but let’s assume exactly, which is actually the worst case for the analysis) {D} such constraints; on average, half of those constraints will be {y_i = 0} and half will be {y_i = 1}. If the fixings of clauses of {y_i} were mutually independent (which would be the case in “triangle-free” instances), then we would expect that the difference between 0s and 1s be about {\sqrt D}, so the greedy fixing has a {\Omega(D^{-1/2})} advantage over the random assignment.

In general instances, although we do not have mutual independence, we do have pairwise independence and “almost four-wise independence.” Fix a variable {y_i}, and let us call {E} the set of pairs {\{ j,k \}} such that constraint {y_i \oplus x_j \oplus x_k = b_{j,k}} is part of the instance, for some {b_{j,k}}, and let us call {R_{j,k}} the random variable which is {1} if {x_j \oplus x_k \oplus b_{j,k}=0} and {-1} otherwise, for a random choice of the {X} variables. We want to argue that, with constant probability, {|\sum_{j,k} R_{j,k}| \geq \Omega(\sqrt D)}.

First, we see that the {R_{j,k}} are unbiased, and they are pairwise independent, so {\mathop{\mathbb E} ( \sum_{j,k} R_{j,k})^2 = D}. The fourth moment of {\sum_{j,k} R_{j,k}} is {3D^2 - 2D} plus the number of 4-cycles in the graph that has vertices {x_j} and the edges in {E}. Now, {E} contains {D} edges, a four-cycle is completely described by the first and third edge of the cycle, so the fourth moment is {O(D^2)}. Finally, it is a standard fact that if we have a sum of {D} unbiased {+/- 1} random variables, and the second moment of their sum is {\Omega(D)} and the fourth moment of their sum is {O(D^2)}, then the absolute value of the sum is, on average (and with constant probability) {\Omega(\sqrt D)}.

The algorithm for general CSPs on triangle-free instances is similarly based on the idea or randomly fixing some variables and then greedily fixing the remaining variables. Without the reduction to the “bipartite” case, which does not hold for problems like Max 3SAT, it is more technically involved to argue the advantage over the random assignment.

Is there a polynomial time algorithm that achieves a {\frac 78 + \Omega(D^{-1/2})} approximation ratio for Max 3SAT in instances such that each variable occurs at most {D} times? This remains an open question.

Mystery solved!

This interesting article in today’s NYT tells the story of the fad of Tibetan mastiffs as high-end pets in China.

It is an appealing story about social changes, new riches, inequalities, and so on, but it also, finally, explains why I could never find in San Francisco hot pot that tasted like in Beijing:

Instead, earlier this year Nibble and 20 more unlucky mastiffs found themselves stuffed into metal chicken crates and packed onto a truck with 150 other dogs. If not for a band of Beijing animal rights activists who literally threw themselves in front of the truck, Nibble and the rest would have ended up at a slaughterhouse in northeast China where, at roughly $5 a head, they would have been rendered into hot pot ingredients, imitation leather and the lining for winter gloves.

(Emphasis added)

I almost fell for it

This year, the chair of ICALP decided to play an April Fool’s prank three weeks early, and I received the following message:

“Dear author, we regret to inform you that the margins in your submission are too small, and hence we are rejecting it without review”

I was almost fooled. In my defense, the second time that I applied for a position in Italy, the hiring committee judged all my publications to be non-existent, because the (multiple) copies I had sent them had not been authenticated by a notary. So I am trained not to consider it too strange that a paper could be evaluated based on the width of its margins (or the stamps on its pages) rather than on the content of its theorem.