To Life, to Science and to Innovations

ICS2011 at ITCS, Tsinghua University, Beijing, China

The title of this post “To life, to Science and to Innovations” was Silvio Micali’s toast at the second conference on Innovations in Computer Science and Silvio’s words have a good chance of becomeing the official toast of this emerging event.  ICS2011 which took place in Beijing was a very interesting conference, and ITCS at Tsinghua University is a great research institute. I completely share the sentiments and excitements of Noam Nisan’s (who is freezing with me against the background of the forbidden city in the picture below) about ITCS from this post from June 2009.

My talk entitled “Influence and Noise” was meant to be (to the horror of some friends, perhaps as much horror as was elicited by my outfit) even more non-technical than the talk shown at this post. I tried to avoid formulas at all costs. (But formulas are fairly efficient, I must say. Explaining things in words is lengthier.) The planned five parts of the talk were: I. Cause and influence, II. Choice, power, and manipulation, III. Randomness, IV Noise and V Computational complexity. This was too ambitious and I ended in the middle of IV.  Here are the slides. (Additional verbal explanation is needed for quite a few slides.)

In the last evening of the meeting after Bernard Chazelle and Amy Yuexuan Wang sang a Chinese song together, it was time for a new innovation: singing TCS-oriented songs. Clearly, the Rolling Stones’ “I Can Get No Satisfaction” refers to 3-SAT and the $NP \ne P$ problem and, twenty years after our first public appearance, Bernard and I sang this song adding background voices “because P is not equal to NP”.  Then Peter Bro Miltersen joined us for “when I will be $2^6$“.

Aaronson and Arkhipov’s Result on Hierarchy Collapse

Scott Aaronson gave a thought-provoking lecture in our Theory seminar three weeks ago.  (Actually, this was eleven months ago.) The slides are here . The lecture discussed two results regarding the computational power of quantum computers. One result from this paper gives an oracle-evidence that there are problems in BQP outside the polynomial hierarchy.  The method is based on “magnification” of results on bounded depth circuits. (It is related to the Linial-Nisan conjecture.)

The second result that we are going to discuss in this post (along with some of my provoked thoughts) is a recent result of Scott Aaronson and Alex Arkhipov which asserts that if  the power of quantum computers can be simulated by digital computers  then the polynomial hierarchy collapses.  More precisely, their result asserts that if sampling  probability distribution created by quantum computers (this is abbreviated as QSAMPLE) is in P then the polynomial hieararchy collapses to its third level.

The beautiful and important paper of Aaronson and Arkhipov is now out. Its main point of view is related to what I describe in the sixth section about “photon machines”. Update: Let me mention related idependent results by Michael J. Bremner, Richard Jozsa, Dan J. Shepherd in the paper entitled: “Classical simulation of commuting quantum computations implies collapse of the polynomial hierarchy“.

Here is the plan for this post

1) The polynomial hierarchy and results about hierarchy collapse

2) The Aaronson Arkhipov (AA) theorem and its proof

3) Two problems posed by AA

4) Does fault tolerance allow QSAMPLE (on the nose)? (Answer: yes)

5) Is there a quantum analog to Aaronson and Arkhipov’s result and what is the computational power of quantum computers?

6) Three Two competing scenarios

7) Aaronson and Arkhipov photon machines and the complexity class BOSONSAMPLING.

Octonions to the Rescue

Xavier Dahan and Jean-Pierre Tillich’s Octonion-based Ramanujan Graphs with High Girth.

Update (February 2012): Non associative computations can be trickier than we expect. Unfortunately, the paper by Dahan and Tillich turned out to be incorrect.

Update: There is more to be told about the background of the new exciting paper. In particular, I would like to tell you more about regular graphs with high girth. (I started below.) The Ramanujan graphs story is, of course, also fascinating so at the very least I should give good links.

Michael Atiyah‘s lecture at IAS physics last Friday was entertaining, educational and quite provocative.

The talk started with the following thesis: There are four fundamental forces of nature and there are four division rings over the reals. The real numbers, complex numbers, Quaternions and the Octonions. Atiyah expects that the Octonions will play a major role in physics and will allow a theory which accounts for gravitation. He described some specific steps in this direction and related ideas and connections. At the end of the talk,  Atiyah’s thesis looked more plausible than in the beginning. His concluding line was: “you can regard what I say as nonsense, or you can claim that you know it already, but you cannot make these two claims together.” In any case, it looks that the people in the audience were rather impressed by and sympathetic to the Octonionic ideas of this wise energetic scientific tycoon.

The same day I received an email from Nati Linial. The subject was: “a good topic for your blog” and the email contained just a single link.
http://arxiv.org/PS_cache/arxiv/pdf/1011/1011.2642v1.pdf

Nati is my older academic brother and often I regard our relations as similar to typical relations between older and younger (biological) brothers. When he tells me what to do I often rebel, but usually at the end I do as he says and most of the times he is right.

So I waited a couple of hours before looking at the link. Indeed,  1011.2642v1.pdf is a great paper. It uses Octonions in place of Quaternions for the construction of Ramanujan graphs and describes a wonderful breakthrough in creating small graphs with large girth. Peter Sarnak’s initial reaction to the new paper was: “wow”.

Here is a link to a paper entitled “Octonions” by John Baez, that appeared in Bull. AMS.

Some background:

Let $G$ be a $k$-regular graph with girth $g$ where $g$ is an odd integer. Continue reading

Subexponential Lower Bound for Randomized Pivot Rules!

Oliver Friedmann, Thomas Dueholm Hansen, and Uri Zwick have managed to prove subexponential lower bounds of the form $2^{n^{\alpha}}$ for the following two basic randomized pivot rules for the simplex algorithm! This is the first result of its kind and deciding if this is possible was an open problem for several decades. Here is a link to the paper.

Update: Oliver Friedmann have managed to use similar methods to find similar lower bounds also for Zadeh’s deterministic pivot rule. See this paper.

We can regard the simplex algorithm as starting from an arbitrary vertex of the feasible polytope and repeatedly moving to a neighboring vertex with a higher value of the objective function according to some pivot rule.

The pivot rules considered in the paper are

RANDOM EDGE– Choose an improving pivoting step uniformly at random.

RANDOM FACET– Choose at random a facet containing your vertex and apply the algorithm in that facet.

Drunken Time and Drunken Computation

The problem

We are used to computer programs or models for computations that perform at time $i$ step $U_i$, $i=1,2,\dots,N$.  Suppose that time is drunk, so instead of running these steps in their correct order, we apply at time $i$ step $\pi(i)$, where $\pi$ is a random permutation which is substantially correlated with the identity permutation.  What then is our computational power?

Noise Stability and Threshold Circuits

The purpose of this post is to describe an old conjecture (or guesses, see this post) by Itai Benjamini, Oded Schramm and myself (taken from this paper) on noise stability of threshold functions. I will start by formulating the conjectures and a little later I will explain further the notions I am using.

The conjectures

Conjecture 1:  Let $f$ be a monotone Boolean function described by  monotone threshold circuits of size M and depth D. Then $f$ is  stable to (1/t)-noise where $t=(\log M)^{100D}$.

Conjecture 2:   Let $f$ be a monotone Boolean function described by  a threshold circuits of size M and depth D. Then $f$ is  stable to (1/t)-noise where $t=(\log M)^{100D}$.

The constant 100 in the exponent is, of course, negotiable. In fact, replacing $100D$ with any  function of $D$ will be sufficient for the applications we have in mind. The best we can hope for is that the conjectures are true if  $t$ behaves like  $t=(\log M)^{D-1}$.

Conjecture 1 is plausible but it looks difficult. The stronger Conjecture 2 while tempting is quite reckless. Note that the conjectures differ “only” in the location of the word “monotone”. Continue reading

Michael Schapira: Internet Routing, Distributed Computation, Game Dynamics and Mechanism Design II

This post is authored by Michael Schapira. (It is the second in a series of two posts.)

In thse two post, I outline work on Internet routing and sketch important areas for future work, both on routing itself and, more broadly, on mechanism design, game theory and distributed computation.

A brief reminder from post 1:

The Internet comprises administrative domains known as Autonomous Systems (ASes), which vary in size, from large (multi)national networks to small networks servicing schools or small businesses. The task of establishing routes between ASes, called interdomain routing, is currently handled by the Border Gateway Protocol (BGP)—the core routing protocol of the Internet. BGP is one of the most critical pieces of the Internet’s infrastructure and can be regarded as the glue that holds the Internet together.

We brefly mentioned two main challenges in this area. The first is the quest for network stability, and the second was giving  agents incentives to “behave well”. We will discuss here these challenges in more detail.

Challenge I: The Quest for Network Stability

Informally, a “stable state’’ is a global routing state that, once reached by BGP, remains unchanged. Formally, a stable state is an assignment of routes R1,…,Rn to the n source nodes (d is assigned the “empty route’’ Rd=Ø) such that for every node i (1) there is a node j such that Ri=(i,j)Rj, where (i,j) Rj is the route that has (i,j) as a first link and then follows Rj to d; and (2) for every node j such that Ri≠(i,j)Rj, and (i,j)Rj is simple, it holds that Ri >i (i,j)Rj.

Translation, Machine Translation, and a Crowded Seminar

I gave in several places a talk entitled “Analytic and Probabilistic Properties of Boolean Functions.” This is a fairly large area so the talks can differ quite a bit. The lecture at the NYU CS theory seminar was described over a Chinese blog entitled (according to the automatic translation) “Notes from Math Library”.  The posting is in Chinese and I used Google translation which gave me this:

Gil Kalai’s Seminar

Hebrew University of Jerusalem last Thursday, and Yale University professor Gil Kalai come Courant Institute speaking seminar. You may have some recollection of the name, because I have a Notes from “Test Your Intuition” in reference to his blog “Combinatorics and More”.

Usually during the same period of the “theory seminar”, where more than 15 people are already rare, but this time Prof. Kalai speaking seminar attracted 38 people to come. Usually there is space left in the room suddenly a full-house, there are several people sitting listening to underground.

Prof. Kalai gave a three guess one of the more accessible and interesting, you can talk about here…

and here is a small expert from the Hebrew translation:

בדרך כלל בתקופה המקבילה של סמינר “תיאוריה”, שבו יותר מ -15 אנשים כבר נדיר, אבל הפעם פרופ ‘קלעי מדבר הסמינר נמשך 38 אנשים לבוא. בדרך כלל יש מקום השמאלי בחדר פתאום הבית מלא, יש כמה אנשים יושבים האזנה תת קרקעית.

פרופ ‘נתן קלעי שלוש משער אחד נגיש יותר ומעניין, אתה יכול לדבר על זה כאן.

Perhaps you can look at the Chinese version and test how good the translations are.  One thing that I liked about the English translation is that it refers to my conjectures as “guesses”. Certainly, this shows that the Google-translation involves deep understanding. (Here is a blog description of a similar lecture at LA.)  One of the “guesses” refers to old conjectures by Itai Benjamini, Oded Schramm and myself about noise stability of monotone Boolean functions in TC0. I will discuss these conjectures in a later post.

So what are these people listening to the talk  “underground” about? I will explain just after the dividing line.  Continue reading