Symmetry

Yesterday at the Simon institute there was a fun talk about The edge of physics by its author, Anil Ananthaswamy. To divulgate the theory of computation isn’t as easy, since you can’t talk about mega experiments done at the South Pole or massive telescopes built on top of mountains.  (It would also be a lot easier if we could resolve P vs. NP.)  For some inspiration we can look at books related to mathematics.  Here I would like to recommend Symmetry, by Marcus du Sautoy.  I enjoyed very much reading and re-reading this book, much more than his previous book The music of the primes, which I don’t really recommend.  Symmetry is a gripping history of group theory.  The purpose isn’t so much explaining the math as making you excited about the historical developments of the theory and the people that worked and are working on it.

Advertisements

I am looking for students

If you are applying for a PhD in theoretical computer science, you may want to check out my homepage, to see what my team and I are up to, the theory group at Northeastern University, and where we stand in the rankings. (For a discussion of csrankings see this previous post.) If you think there is a match write my name on the application.

shoving marijuana down the throats of Newton’s residents

Congratulations to the marijuana industry and the Newton MA administration for rigging the elections and pouring > $70K into a campaign strategist who lives in a neighboring city where recreational pot shops are banned, thereby snatching a narrow victory and shoving marijuana down the throats of Newton’s residents. When the pot shops open, owned by people who live in the same neighboring city which does not have them, I’ll have a toast to you with a marijuana drink.

Well, I think I am taking a break from politics, at least until I have a stronger financial backing. I have a bigger impact on society with my research.

Just coincidence?

Proving lower bounds is one of the greatest intellectual challenges of our time. Something that strikes me is when people reach the same bounds from seemingly different angles.  Two recent examples:

What does this mean?  Again, the only things that matter are those that you can prove.  Still, here are some options:

  • Lower bounds are true, and provable with the bag of tricks people are using.  The above is just coincidence. Given the above examples (and others) I find this possibility quite bizarre. To illustrate the bizarre in a bizarre way, imagine a graph where one edge is a trick from the bag, and each node is a bound. Why should different paths lead to the same sink, over and over again?
  • Lower bounds are true, but you need to use a different bag of tricks. My impression is that two types of results are available here.  The first is for “infinitary” proof systems, and includes famous results like the Paris-Harrington theorem. The second is for “finitary” proof systems, and includes results like Razborov’s proof that superpolynomial lower bounds cannot be proved in Res(k). What I really would like is a survey that explains what these and all other relevant proof systems are and can do, and what would it mean to either strengthen the proof system or make the unprovable statement closer to the state-of-the-art. (I don’t even have the excuse of not having a background in logic.  I took classes both in Italy and in the USA.  In Italy I went to a summer school in logic, and took the logic class in the math department.  It was a rather tough class, one of the last offerings before the teacher was forced to water it down.  If I remember correctly, it lasted an entire year (though now it seems a lot).  As in the European tradition, at least of the time, instruction was mostly one-way: you’d sit there for hours each week and just swallow this avalanche of material. At the very end, there was an oral exam where you sit with the instructor — face-to-face — and they mostly ask you to repeat random bits of the lectures.  But for the bright student some simple original problems are also asked — to be solved on the spot.  So there is substantial focus on memorization, a word which has acquired a negative connotation, some of which I sympathize with.  However a 30-minute oral exam does have its benefits, and on certain aspects I’d argue it can’t quite be replaced by written exams, let alone take-home.  But I digress.)
  • Lower bounds are false. That is, all “simple” functions have say n^3 formula size.  You can prove this using computational checkpoints, a notion which in hindsight isn’t too complicated, but alas has not yet been invented.  To me, this remains the more likely option.

What do you think?

How to rig an election

After the historic signature collection there was a pitched battle to decide which questions to put on the ballot.  Alas, the battle resulted in somewhat of a defeat for the residents of Newton.  The councilors of Newton saw it fit to put two conflicting questions on the ballot, and to resolve the conflict by stipulating that if both questions pass, the one with the highest number of yes votes will prevail. As explained below, this forces residents to strategize, take a risk, and in a way answer questions against their true preference — a well-known, and bad, situation in election theory.

The two questions are:

  • Question 1:  Shall the City adopt the following general ordinance?
    All recreational marijuana retail establishments shall be prohibited from operating in the City of NewtonCouncilors unanimously approved the inclusion of this question on the ballot.
  • Question 2:  Shall the City adopt the following zoning ordinance?
    The number of recreational marijuana retail establishments shall be not fewer than two (2) nor more than four (4). Councilors approved the inclusion of this question on the ballot by a vote of 11 to 10.

Yes, the motion to put Question 2 on the ballot passed by 1 vote. Each of those 11 councilors can go home feeling satisfied that they bear full responsibility for ignoring the clear preference of their constituents.  It doesn’t matter what the chief of the Newton police says, or what the former head of the Newton-Wellsely hospital says, or what any of the other dozens of high-profile people say, or that you collected thousands of signatures.  Those 11 councilors know what’s best for Newton. (Oh, and by the way, the upper bound is meaningless and can be easily increased. )

Before they convened to deliberate I sent them this message:

  • If you want to put another question on the ballot besides a simple YES/NO question, then you should first collect 7,000 signatures.

I doubt they could have even collected 70 for Question 2.

But the real problem is the rule I mentioned before, that if both questions have a majority of yes votes, the one with the highest number of yes votes will prevail.  To illustrate, consider the following realistic scenario.  Suppose that a resident of Newton loathes recreational marijuana establishments.  When they go to the ballot, they obviously vote yes on Question 1.  What should they do about Question 2?  If Question 1 loses, they are better off if Question 2 wins.  Suppose they also vote yes on 2, and that 99% of Newton residents behaves this way. Then it’s enough that a merry 1% band of business(wo)men vote no on Question 1 and yes on Question 2, and they harness all the votes that people cast to their own advantage.

There do exist fair ways of having both questions on the ballot, but this isn’t one. The current setup forces people who really want to ban recreational marijuana to strategize by voting no on question 2, and risk that if Question 1 loses, they end up with unlimited recreational stores.

Maybe it’s a little hard to understand this in terms of marijuana.  Consider the following scenario:

  1. Question 1: Do you want to ban torture?
  2. Question 2: Do you want to limit the amount of torture that can be inflicted upon you?
  3. Default: Unlimited torture can be inflicted upon you.
  4. If both Questions 1 and 2 have majority Yes, the one with the highest number of yes prevails.

It is not going to be easy, but it seems that in the upcoming campaign we will have to convince people to answer ‘NO’ to question 2.

 

 

 

bounded independence plus noise fools space

There are many classes of functions on n bits that we know are fooled by bounded independence, including small-depth circuits, halfspaces, etc. (See this previous post.)

On the other hand the simple parity function is not fooled. It’s easy to see that you require independence at least n-1. However, if you just perturb the bits with a little noise N, then parity will be fooled. You can find other examples of functions that are not fooled by bounded independence alone, but are if you just perturb the bits a little.

In [3] we proved that any distribution with independence about n^{2/3} fools space-bounded algorithms, if you perturb it with noise. We asked, both in the paper and many people, if the independence could be lowered. Forbes and Kelley have recently proved [2] that the independence can be lowered all the way to O(\log n), which is tight [1]. Shockingly, their proof is nearly identical to [3]!

This exciting result has several interesting consequences. First, we now have almost the same generators for space-bounded computation in a fixed order as we do for any order. Moreover, the proof greatly simplifies a number of works in the literature. And finally, an approach in [4] to prove limitations for the sum of small-bias generators won’t work for space (possibly justifying some optimism in the power of the sum of small-bias generators).

My understanding of all this area is inseparable from the collaboration I have had with Chin Ho Lee, with whom I co-authored all the papers I have on this topic.

The proof

Let f:\{0,1\}^{n}\to \{0,1\} be a function. We want to show that it is fooled by D+E, where D has independence k, E is the noise vector of i.i.d. bits coming up 1 with probability say 1/4, and + is bit-wise XOR.

The approach in [3] is to decompose f as the sum of a function L with Fourier degree k, and a sum of t functions H_{i}=h_{i}\cdot g_{i} where h_{i} has no Fourier coefficient of degree less than k, and h_{i} and g_{i} are bounded. The function L is immediately fooled by D, and it is shown in [3] that each H_{i} is fooled as well.

To explain the decomposition it is best to think of f as the product of \ell :=n/k functions f_{i} on k bits, on disjoint inputs. The decomposition in [3] is as follows: repeatedly decompose each f_{i} in low-degree f_{L} and high-degree f_{H}. To illustrate:

\begin{aligned} f_{1}f_{2}f_{3} & =f_{1}f_{2}(f_{3H}+f_{3L})=f_{1}f_{2}f_{3H}+f_{1}(f_{2H}+f_{2L})f_{3L}=\ldots \\ = & f_{1H}f_{2L}f_{3L}+f_{1}f_{2H}f_{3L}+f_{1}f_{2}f_{3H}+f_{1L}f_{2L}f_{3L}\\ = & H_{1}+H_{2}+H_{3}+L. \end{aligned}

This works, but the problem is that even if each time f_{iL} has degree 1, the function L increases the degree by at least 1 per decomposition; and so we can afford at most k decompositions.

The decomposition in [2] is instead: pick L to be the degree k part of f, and H_{i} are all the Fourier coefficients which are non-zero in the inputs to f_{i} and whose degree in the inputs of f_{1},\ldots ,f_{i} is \ge k. The functions H_{i} can be written as h_{i}\cdot g_{i}, where h_{i} is the high-degree part of f_{1}\cdots f_{i} and h_{i} is f_{i+1}\cdots f_{\ell }.

Once you have this decomposition you can apply the same lemmas in [3] to get improved bounds. To handle space-bounded computation they extend this argument to matrix-valued functions.

What’s next

In [3] we asked for tight “bounded independence plus noise” results for any model, and the question remains. In particular, what about high-degree polynomials modulo 2?

References

[1]   Ravi Boppana, Johan Håstad, Chin Ho Lee, and Emanuele Viola. Bounded independence vs. moduli. In Workshop on Randomization and Computation (RANDOM), 2016.

[2]   Michael A. Forbes and Zander Kelley. Pseudorandom generators for read-once branching programs, in any order. In IEEE Symp. on Foundations of Computer Science (FOCS), 2018.

[3]   Elad Haramaty, Chin Ho Lee, and Emanuele Viola. Bounded independence plus noise fools products. SIAM J. on Computing, 47(2):295–615, 2018.

[4]   Chin Ho Lee and Emanuele Viola. Some limitations of the sum of small-bias distributions. Theory of Computing, 13, 2017.

 

 

Environmental obstacles

Former EPA chief’s resignation confession-of-faith letter according to Breitbart (a website I didn’t know but that I started consulting semi-regularly):

Mr. President,

It has been an honor to serve you in the Cabinet as Administrator of the EPA. Truly your confidence in me has blessed me personally and enabled me to advance your agenda beyond what anyone anticipated at the beginning of your administration. Your current steadfastness and resolute commitment to get results for the American people both with regard to improved environmental obstacles and historical regulatory reform is a fact occurring at an unprecedented pace and I thank you for the opportunity to serve you and the American people in helping to achieve those ends. That is why it is hard for me to advise you I am stepping down as administrator of the EPA as of July 6. It is extremely difficult for me to cease serving you in this role, first because I count it as a blessing to be serving you in any capacity, but also because of the transformative work that is occurring; however, the unrelenting attacks on me personally, my family are unprecedented and have taken a sizable toll on all of us. My desire in service to you has always been to bless you as you make important decisions for the American people. I believe you are serving as president today because of God’s providence. I believe that same providence brought me in to your service. I pray as I have served you that I have blessed you and enabled you to effectively lead the American people. Thank you again Mr. President for the honor of serving you and I wish you Godspeed in all that you put your hand to.

Elsewhere

Mr. President,

It has been an honor to serve you in the Cabinet as Administrator of the EPA. Truly, your confidence in me has blessed me personally and enabled me to advance your agenda beyond what anyone anticipated at the beginning of your Administration. Your courage, steadfastness and resolute commitment to get results for the American people, both with regard to improved environmental outcomes as well as historical regulatory reform, is in fact occurring at an unprecedented pace and I thank you for the opportunity to serve you and the American people in helping achieve those ends.

That is why it is hard for me to advise you I am stepping down as Administrator of the EPA effective as of July 6. It is extremely difficult for me to cease serving you in this role first because I count it a blessing to be serving you in any capacity, but also, because of the transformative work that is occurring. However, the unrelenting attacks on me personally, my family, are unprecedented and have taken a sizable toll on all of us.

My desire in service to you has always been to bless you as you make important decisions for the American people. I believe you are serving as President today because of God’s providence. I believe that same providence brought me into your service. I pray as I have served you that I have blessed you and enabled you to effectively lead the American people. Thank you again Mr. President for the honor of serving you and I wish you Godspeed in all that you put your hand to.

The letter also makes me think that I should have added “to worship God” to this list.

The EPA chief is approved by Congress. So if you care about your health get ready for November.  If you’ll be traveling start looking into absentee voting for your state.

NEWTON MUST NOT BECOME THE HUB OF MARIJUANA

If you are a resident of Newton, MA, sign this petition.

In 2016 Massachusetts voters voted to legalize Marijuana. Except they didn’t know what they were voting for! In Colorado and Washington, the question of legalization and commercialization were completely separate. The marijuana industry apparently learned from that and rigged the Massachusetts ballot question so that a voter legalizing marijuana would also be mandating communities to open marijuana stores. For Newton, MA, this means at least 8 stores. When voters were recently polled, it became clear that the vast majority did not know that this was at stake, and that the majority of them in fact does not want to open marijuana stores in their communities. For example, when I voted I didn’t know that this was at stake. Read the official Massachusetts document to inform voters, see especially the summary on pages 12-13. There is no hint that a community would be mandated by state law to open marijuana stores unless it goes through an additional legislative crusade. Instead it says that communities can choose. I think I even read the summary back then.

Now to avoid opening stores in Newton, MA, we need a new ballot question. The City Council could have put this question on the ballot easily, but a few days ago decided that it won’t by a vote of 13 to 8. You can find the list of names of councilors and how they voted here.

Note that the council was not deciding whether or not to open stores, it was just deciding whether or not we should have a question about this on the ballot.

Instead now we are stuck doing things the hard way. To put this question on the ballot, we need to collect 6000 signatures, or 9000 if the city is completely uncooperative, a possibility which now unfortunately cannot be dismissed.

However we must do it, for the alternative is too awful. Most of the surrounding towns (Wellesley, Weston, Needham, Dedham, etc.) have already opted out. So if Newton opens stores, it basically becomes the hub for west suburban marijuana users, at least some of whom would drive under the influence of marijuana (conveniently undetectable). Proposed store locations include sites on the way to elementary schools, and there is an amusing proposal to open a marijuana store in a prime Newton Center Location, after Peet’s Coffee moves out (they lost the bid for renewal of the lease). The owners of the space admit that people have asked them for a small grocery store instead, but they think that a marijuana store would bring more traffic and business to Newton Center. I told them to open a gym instead. That too would bring traffic and business, but in addition it would have other benefits that cannabis does not have.