Coincidence?

“Art imitates life, but life imitates bad TV” (Woody Allen)

The mention for a major alumni award given by U.C. Berkeley is for excellence in achievement.

Meanwhile, in the episode “Brother, can you spare two dimes?”, Mr. Burns has to come up on the spot with the name for a fake awards, and he comes up with an award for outstanding achievement in the field of excellence.

 

(You’ll note that the dancers in the video are wearing gold and blue)

ما همه ایرانی

Many people are angry and heartbroken at the consequences (on themselves, their loved ones, their friends and coworkers) of the executive order that has banned refugees, as well as legal immigrants and green card holders, from certain countries from entering the US for the next few months. A common question is, what can we do? A few possibilities:

  • Donate to the ACLU. They have a long history of fighting for civil rights and, on Saturday, they immediately sprung into action and where able to get a stay on the ban, whose implications are still not clear.
    As you are contemplating donations, consider also supporting Planned Parenthood and the Southern Poverty Law Center. This is unrelated to the current refugees/immigrant crisis, but it is relevant to what will probably be future crises instigated by the current administration. (The SPLC does a great work in tracking and documenting hate groups.)
  • Sign this petition, which has received significant media coverage
  • Do what you can to make sure our professional societies produce a response. Both the outgoing and the incoming presidents of the AMS have signed the above petition, and I understand that the appropriate committee of the AMS  is considering making a statement. I don’t know if the ACM is planning a similar action, and if you have access to the ACM leadership, please lean on them to do so.
    (Edited to add: ACM put out a statement Monday morning, and so this the AMS.)
  • Call your representatives in congress, especially if you live in a state with Republican senators or in a district with a Republican representative. Don’t email: call and ask to speak with the staffer who is responsible for immigration matters.
  • Reach out to colleagues, students and staff who are affected by the executive order. If you have channels to do so, pressure campus leadership to cover their legal expenses, which could be substantial.

If you have other ideas, please share them in the comments.

Matrix Multiplication Not Yet Doable In Quadratic Time

Last night, a paper appeared on the arXiv titled A \Theta(n^2) time matrix multiplication algorithm.

At first look the paper seemed to score zero on Scott Aaronson’s list of Ten Signs a Claimed Mathematical Breakthrough is Wrong, and it came from a researcher who has worked extensively on the related problem of all-pairs shortest path, so it looked exciting. Unfortunately, it actually scores one on Scott’s list: it contradicts known impossibility results. (Thanks to Yuval Filmus for the references.)

The first step in the algorithm is to show how to compute the inner product of two 3^n-dimensional vectors using n^{O(1)} \cdot 2^n multiplication. This contradicts a lower bound due to Pan (see here the proof of a more general result) that computing the inner product of two N-dimensional vectors require at least N multiplications.

In addition, Raz has proved an \Omega (n^2 \log n) lower bound for matrix multiplication arithmetic circuits, and, to the best of my understanding, the paper’s claims imply an O(n^2) size arithmetic circuit. (Raz’s lower bound assumes that the circuit is not given access to large constants; as far as I can see, the formulas in Han’s paper do not require large constants.)

What’s New at the Simons Institute

This Thursday (December 15) is the deadline to apply for post-doctoral positions at the Simons Institute for the next academic year. In Fall 2017 we will run a single program, instead of two programs in parallel, on optimization. The program will be double the size of our typical programs, and will focus on the interplay between discrete and continuous methods in optimization. In Spring 2018 there will be a program on real-time decision-making and one on theoretical neuroscience.

In a few weeks, our Spring 2017 programs will start. The program on pseudorandomness will have a mix of complexity theorists and number theorists, and it will happen at the same time as a program on analytic number theory at MSRI. It will start with a series of lectures. It will start with a series of lectures in the third week of January. The program on foundations of machine learning has been much anticipated, and it will also start with a series of lectures, in the fourth week of January, which will bring to Berkeley at impressive collection of machine learning practitioners whose research is both applied and rigorous. All lectures will be streamed live, and I encourage you to set up viewing parties.

During the current semester, the Simons Institute had for the first time a journalist in residence. The inaugural resident journalist has been Erica Klarreich, that many of you probably know for her outstanding writing on mathematics and computer science for quanta magazine.

Next semester, our resident journalist will be Pulitzer-prize winner John Markoff, who just retired from the New York Times.

The vocabulary is political

Remember when the (GW) Bush administration decided that torture should be called “enhanced interrogation techniques,” and then the New York Times, like all other American news sources, started to call torture “enhanced interrogation techniques,” and people wrote angry letters to the public editor, and the public editor eventually wrote that if the White House decides that torture should not be called torture then calling torture torture is a political issues on which reporters should not take sides?

And Paul Krugman wrote a column in which he said that if the Bush administration declared that the Earth is flat, then the New York Times would have an article headlined “Roundness of Earth disputed,” in which it would make sure to have quotes both from round-Earther and flat-Earther?

Part of the reason for all this, as explained in this very good article in The Atlantic, is that political reporters (as opposed to political opinion writers) need access, that is, they need White House officials to talk to them, whether on the record or off the record. The ability to withhold access gives administration officials great leverage.

And so Myron Ebell, who works in a think-tank financed by the coal industry, and according to whom climate change is a vast conspiracy perpetrated by left-wing scientists, some of which scientists he has personally attacked, and who is being considered to lead the EPA, is now a climate contrarian, according to the New York Times.

Maybe soon enough, outside the opinion page, the New York Times will start calling racism “race realism.”

We need to occupy unsafe spaces

Today an atmosphere of grief pervaded Berkeley, and a series of emails came from higher and higher up the chain of command, culminating with one from Janet Napolitano, reaffirming the University of California’s commitment to its principles of inclusivity, diversity, and all things that are good. Here is an email from the Vice-Chancellor for Equity and Inclusion:

Dear Cal Students, Staff, and Faculty,

We know that the results of yesterday’s election have sparked fear and concern among many in our community; in particular our immigrant and undocumented communities, Muslim, African American, Chicanx/Latinx, LGBTQ+, Asian and Pacific Islander communities, survivors of sexual assault, people with disabilities, women, and many others. We are reaching out to you with a message of support. UC Berkeley leadership remains steadfast in our values and committed to the safety and well-being of all of our students, faculty, and staff. We condemn bigotry and hatred in all forms, and hold steadfast in our commitment to equity, access, and a campus that is safe, inclusive, and welcoming to all.

Various communities have organized the following community spaces and resources:

  • A community space for undocumented students tonight at 6:30pm in Chavez Room 105.
  • CLSD and CLPR are hosting space at the Shorb House, 2547 Channing Way from 12pm-5pm for students to come by. Faculty and staff will be there in community with our students for support.
  • MCC is holding a safe space for POC/Black students from 8pm-10pm this evening.
  • QTAP is hosting a QTOPC dinner in Anthony Hall at 6pm.
  • The Gender Equity Resource Center is open today, until 5pm, for those who wish for a quiet space for contemplation and community. GenEq is also hosting the following healing spaces:
    • Women’s Healing Space – Today, November 9th, 1pm-2:30pm
    • LGBTQ+ Healing Space – Today, November 9th, 2:30pm-4pm

Now, without discounting the value of having a good place to quietly sob with like-minded people, this strikes me as the message you would send after the Charleston shooting, or the Orlando shooting. This was not the act of one disturbed person. Sixty million Americans went to the trouble of going all the way to the polling place to vote for Trump, or of filling up their absentee ballot, and then mailing it in. That’s one in four adult Americans, a diverse coalition of white people: educated white people and less educated white people, male white people and female white people, religious white people and secular white people, and, one should note, even a few people who are not white. White people who thought it’s their constitutional right to discriminate against gay people, white people who think it’s ok to grab women by their pussy, and that you can get away with it if you are a star, white people who think muslims should not come to the US.

Our students will meet these people everywhere. They will be their neighbors, their coworkers, their bosses, and maybe their in-laws. When our students graduate, there will be no safe space.

And if there were, that is not where they should go. Because those sixty million people will not change their minds by talking among themselves.

But the oppressed cannot be left alone to speak out for themselves.

A feature of rape prevention programs is bystander intervention training: telling people how to recognize a situation in which someone is at risk of assault, and intervene.

We need white people to speak out against racism, christians to speak out for the religion freedom of non-christians, men to speak out against misogyny, straight people to speak out for LGBT people, Republicans to speak out against Trump.

And we need them to do this where it is not safe to do so, because otherwise all we have is angry people talking to the like-minded on the internet.

Edited to add a useful link

How Baggio Leung and Yau Wai-ching Lost their Legco Seat

If you can’t bear to think about tomorrow’s election, and what will happen to the ninth seat of the supreme court if the Republicans hold control of the Senate, and if you would rather hear about another country’s impending constitutional crisis, let me present you with the latest goings on in Hong Kong.

In 1997, Hong Kong was “handed over” back to China, with the agreement that it would retain a “high degree of autonomy” until 2047, and that there would be elections with universal suffrage by 2017. Hong Kong kept (and will keep until 2047) its own legal system and its own currency, Hong Kong citizens have their passport, and a mini-constitution, called “basic law” was drafted to outline the working of its own political system.

In the 1997 system, Hong Kong is governed by a Chief Executive, who is elected in a system that gives votes to constituencies such as business associations, as well, with a smaller weight, to popular vote. The Legislative Council (Legco) is similarly elected in a way in which some members reflect the public’s vote and other are appointed by business and trade groups. The system guarantees a pro-Beijing chief executive and a majority of pro-Beijing representatives in the Legco.

In 2012, legislature was passed that would have introduced “patriotic” (pro-PRC) propaganda in K-12 education. The move produced an uproar among student groups, which coalesced under the umbrella of the Scholarism student association, and which led to huge demonstrations, which in turn led the Hong Kong government to shelve the patriotic education initiative.

In 2014, a long-running process to decide how universal suffrage was going to be implemented in the 2017 Chief Executive election, yielded a proposal in which only Beijing-approved candidates could run for office, thus negating the purpose of having elections in the first place. A broad protest movement emerged, including both Scholarism students and veterans of the pro-democracy movement that had existed since 1997. Outrage at the police response to early protests led to large popular protests that turned the center of Hong Kong into an occupied zone, where thousands of people pitched tents and stayed for weeks.

Eventually the movement failed to win any concessions, the occupation ended, but a new generation of Hong Kong young people became involved in politics and in the pro-democracy movement like never before. Scholarism dissolved as a student group, and reformed as a political party called Demosisto, and a number of other pro-democracy parties arose, including Youngspiration, which has an explicit pro-autonomy platform.

In the last September election, Nathan Law Kwun-chung became the youngest person to win a seat in Legco, running for Demosisto, and two Younsgpiration members, Sixtus “Baggio” Leung Chung-hang and Yau Wai-ching, also won seats, among other pro-democracy representatives.

On October 4, Joshua Wong, the teenage former Scholarism leader and current Demosisto member, was detained in Thailand on his way to speak at a University in Bangkok, and deported back to Hong Kong, under pressure from China, highlighting how much the PRC feels threatened by the Hong Kong pro-democracy movement.

On October 12, the swearing-in ceremony of the elected Legco members took place. If you look at the video halfway down this article, you will see “Long Hair” Leung Kwok-Hung come to the lectern with a yellow umbrella, the symbol of the 2014 protests, and a copy of the election law, which he proceeds to shred; at the end of the video you see Nathan Law make a speech after his swearing-in, and, in the middle, there are Baggio Leung and Yau Wai-ching. They each approach the lectern with a banner that says “Hong Kong is not China,” and then recite the oath in English (the other option is do so in Cantonese). In the oath, legislators swear allegiance to the “Hong Kong Special Administrative Region of the People’s Republic of China,” and they both pronounce China as “Chee-na.” The officer presiding the swearing-in refuses the recognizes their oath as valid.

Here is where things get complicated. “Chee-na” is how the Japanese called China during WW2, and it is considered an offensive slur in the Mainland. Leung and Yau, apparently quite disingenuously, insist that they just have poor English pronunciation, and they have refused to apologize. Meanwhile, they have twice shown up at Legco meetings to repeat their swearing-in, which the presiding officer has refused to do. Instead, the government asked the Hong Kong supreme court to rule on whether by having “refused to take the oath” (a rather questionable interpretation of the event) Leung and Yau should vacate their seats.

So we come to the constitutional crisis: before the Hong Kong supreme court ruled on the matter, the legislative branch of the PRC stepped in yesterday, to rule against Leung and Yau, producing an interpretation of the basic law suggesting that all pro-autonomy legislators could be stripped of their post. They did so because the PRC legislature is indeed supposed to be the ultimate interpreter of the meaning of the basic law, but this is only the second time since 1997 that it has exercised this prerogative, and the first time that it has done for such an incendiary matter. This could be the beginning of the end of the autonomy of Hong Kong’s judiciary system, which so far was never doubted, as well as the end of the remaining semblance of democracy in Hong Kong’s political system.

Protests have already started.

Avi60: Zero Knowledge for all NP

1982 was the annus mirabilis of the foundations of cryptography. In their paper “probabilistic encryption,” Goldwasser and Micali introduced two rigorous definitions of security for encryption, which they proved to be equivalent. One definition required the distributions of encryptions of any two messages to be computationally indistinguishable (a concept they introduce in the paper), the other, which they call semantic security, is the property that whatever can be efficiently computed about a message given the cyphertext can also be efficiently computed without the cyphertext. Later the same year, Blum and Micali gave a rigorous definitions of security for pseudorandom generators, and Yao wrapped all these results in a more general framework requiring generic, rather than number-theoretic, assumptions.

The concept of semantic security inspired most subsequent definitions, and proofs, of security based on the concept of simulation. Instead of trying to specify a list of things than adversary should not be able to do, one defines an idealized model in which the adversary has no access to private and encrypted data, and one defines a given system to be secure if whatever an attacker can efficiently compute given the ability of eavesdrop (and possibly mount an active attack), can also be efficiently computed in the ideal model. One then proves a system to be secure by developing a simulator in the ideal model for every real-world adversary.

Together with Rackoff, Goldwasser and Micali took this idea one step further from encryption to interactive communication, and came up with the idea of Zero-Knowledge Proofs. A zero-knowledge proof is a probabilistic proof system in which a prover can convince a verifier, with high confidence, of the truth of a statement, with the additional property that there is a simulator that is able to sample from the distribution of verifier’s views of the interaction. Thus the verifier is convinced of the truth of the statement being proved, but gains no additional information. In their paper, Goldwasser, Micali and Rackoff introduce the concept and present a zero-knowledge proof for a conjecturally intractable number-theoretic problem. The paper was famously rejected several times, eventually appearing in 1985.

The following year, Goldreich, Micali and Avi Wigderson published a paper giving zero knowledge proof systems for all problems in NP. Their work made zero-knowdge proofs a key tool in the design of secure cryptosystem: it was now possible for a party to publish a commitment to a secret x and then, at any time, be able to prove that x has a certain property without releasing any additional information about x. This ability was a key ingredient in the development of secure multi-party computation in 1987, by the same authors.

So how does one prove in zero knowledge that, say, a graph is 3-colorable? (Once you have zero-knowledge proofs for one NP-complete problems, you immediately have them for all problems in NP.)

Suppose the prover and the verifier know a graph G and the prover knows a 3-coloring. A physical analog of the protocol (which can be implemented using the notion of commitment schemes) is the following: the prover randomizes the color labels, then takes |V| lockboxes, each labeled by a vertex, and puts a piece of paper with the color of vertex v in the lockbox labeled by v, for every v. The prover locks all the lockboxes, and sends them to the verifier. The verifier picks a random edge (u,v) and asks for the keys of the lockboxes for u and for v. If they contain different colors, the verifier accepts, otherwise it rejects.

The protocol is complete, in the sense that if the graph is 3-colorable and the parties follow the protocol, then the verifier accepts with probability 1.

The protocol is sound, in the sense that if the graph is not 3-colorable, then, no matter what the prover does, there will have to some edge (u,v) such that the lockboxes of u and v are the same, and the verifier has probability at least 1/|E| of picking such an edge and rejecting. Thus the verifier accepts with probability at most 1 - 1/|E|, which can be made negligibly small by repeating the protocol several times.

As per the zero-knowledge property, the view of the verifier is the choice of a random edge, two open lockboxes corresponding to the endpoints of the edge, containing two random different colors, and |V|-2 unopened lockboxes. A view with such a distribution can be easily sampled, and the same is true when the physical implementation is replaced by a commitment scheme. (Technically, this is argument only establishes honest-verifier zero knowledge, and a bit more work is needed to capture a more general property.)