Complexity Year in Review 2018

Result of the year goes to

Oracle Separation of BQP and PH by Ran Raz and Avishay Tal

which we wrote about in June. This work solves one of the original open questions in quantum complexity using tools from both quantum and classical circuit complexity. How often do we see oracle results with popular articles in Quanta (ignore the hyperbolic title), The Hindu and CACM?

Runner up goes to the solution of the 2-to-2 Games Conjecture by Subhash Khot, Dor Minzer and Muli Safra early in 2018. Boaz Barak gave a nice two post overview.

In last year's review we talked about the magical breakthroughs of machine learning. This year we seemed to have moved beyond the magic to where machine learning has become a thing. We see the immense value of data and continue to struggle with the ethical challenges of collecting and acting on data, dominance of the big tech companies, training all these students who want to gain expertise in the area and trying to understand why ML works as well as it does. 

The big X-factor is China. Will competition with China spur science literacy and funding in the US like the cold war with the Soviets did? Or will isolation with China limit scientific collaboration like the cold war with the Soviets did? 

The big tech surprise was the rise of electric scooters. Georgia Tech has embraced them and it is a quick way to get around campus.

Some of the other questions I asked last year didn't have interesting answers: What will the Internet look like post-net neutrality? (too early to tell) How will the new tax code play out? (too early to tell) Where will Amazon put HQ2? (New York and DC--only surprise was picking two cities) What can quantum computers with 50 qbits accomplish? (still a good question) Will bitcoin move to $300K or 30 cents? (it dropped but still has real value)

Thanks to our guest posters Vijay Vazirani, Samir Khuller and Robert Kleinberg, and anonymous.

We remember Jean Bourgain, George H. W. Bush, Babak Farzad, Stephen Hawking, Ker-I Ko and Stan Lee.

We end the year with craziness, the stock market is going through wild gyrations, we have a partial government shutdown including all of NSF and an uncertain political landscape with different parties leading the two houses of congress. We're still in the midst of a technological revolution and governments around the world try to figure how to regulate it. I find it hard to predict 2019 but it will not be quiet.

Ker-I Ko (1950-2018)

A few weeks ago as Bill and I prepared for our upcoming year in review post, we noted that we hadn't lost any theoretical computer scientists this year, at least none that we were aware of. Unfortunately we didn't make it through all of 2018 unscathed.

Computational complexity theorist Ker-I Ko passed away peacefully from lung failure on December 13. Ker-I Ko spent most of his career at Stonybrook where he had recently retired to take on a professorship at National Chiao Tung University in Taiwan.

I had only had a few brief meetings with Ko but I knew his work quite well. In his best known work, Ko, in a solo paper, created an infinite series of oracles A₁, A₂, … such that relative to A_k, the polynomial-time hierarchy collapses to exactly the kth level, that is Σ_k-1 ≠ Σ_k = Σ_k+1 = PH. Ko wielded the switching lemma like a scalpel, pulling part the k-1st and kth levels while leaving enough room to encode the k+1st level. He actually gives two sets of oracles, one which collapses PH to PSPACE while collapsing the hierarchy to the kth level and one that separates PH from PSPACE. Even his oracle showing P=NP≠PSPACE wasn't trivial and I used it as an example of a hard to settle complexity question.

Ko, with Tim Long and Ding-Zhu Du, showed that if P ≠ UP if and only if there exist two sets that were one-to-one length-increasing polynomial-time reducible to each other but not polynomial-time isomorphic. This paper played a large role in helping us understand the isomorphism conjecture.

Ko, with Pekka Orponen, Uwe Schöning and Osamu Watanabe, used Kolmogorov complexity to measure the complexity of an instance of a problem. The instance complexity of x in a set A is the smallest program that will correctly answer whether x is in A, and will not give an incorrect answer for any other y in A, though it can answer "I don't know" for y ≠ x.

Ko also had several papers on complexity of real-valued functions and wrote several textbooks and manuscripts. A big loss for all of us in the complexity world.

Guest post: Join SIGACT!

This is a guest post by Samir Khuller and Robert Kleinberg.

Dear friends,

As our research community continues to grow and thrive, SIGACT membership has not grown apace. We respectfully urge you to join SIGACT! Membership is very cheap (and does not require ACM membership) – only $15 a year – and by joining you will be lending your support to the many activities that SIGACT undertakes on behalf of the theoretical computer science research community. These include:

• sponsoring STOC and other theory conferences such as SPAA and PODC, as well as co-sponsoring SODA;
• awards such as the Knuth, Gödel, and Kanellakis Prizes, the SIGACT Distinguished Service Award, and the best student paper awards at STOC and SODA;
• supporting the Women in Theory workshop;
• representing the theoretical computer science community to the ACM and beyond.

In addition to these community benefits, membership comes with individual benefits including voting rights in SIGACT elections, reduced rate for membership in EATCS, reduced conference registration rates at SIGACT-sponsored conferences, access to SIGACT News and announcements sent on the SIGACT email list.

SIG membership does not automatically renew when you renew your ACM membership, and we suspect this may be one reason for the decline in SIGACT membership. So the next time you renew your ACM membership, remember to also join SIGACT or renew your SIG membership! Better yet, why wait? If you’re not a SIGACT member, join right now- you can use this link: here

Please do your part to nurture this important resource for our community.

Respectfully,

The SIGACT Executive Committee

Inverting Onto Functions

Here's an open question that goes back to a 2003 paper  that I wrote with Steve Fenner, John Rogers and Ashish Naik. The conference paper goes back to 1996.

In that paper we discuss two hypothesis we badly called Q and Q' and it still remains open whether the two hypotheses are equivalent.

Q has a number of equivalent definitions, including

• For all NP machines M that accepting all strings, there is polynomial-time computable function f such that f(x) is an accepting path of M(x) for all x.
• For every onto honest polynomial-time computable function g there is a polynomial-time computable function f such that f finds an inverse of g, more precisely g(f(g(x))) = g(x) for all x.
• TFNP is computable in FP.

For lots more equivalences see the paper. 

Q' is the bit version of Q. For example

• For all NP machines M that accepting all strings, there is polynomial-time computable function f such that f(x) outputs the first bit of an accepting path of M(x) for all x.
• For every onto honest polynomial-time computable function g there is a polynomial-time computable function f such that f finds the first bit of an inverse of g, more precisely for all x there is a y such that g(y) = x and f(x) is the first bit of y.

Now Q implies Q', if you can find an accepting path of M(x) you can just read off the first bit. Does Q' imply Q? 

If P = NP you can find solutions using self-reductions. For Q' self-reduction gets stuck because as you start filling in bits you may lose the "onto" promise. 

On the other hand we don't even know any relativized worlds where Q' is true and Q is false. So either prove that Q' implies Q or show a relativized world where Q' is true and Q is false.

How often can I dole out 22-year old open problems that don't require deep complexity to understand. Can't promise what techniques you'll need to solve it.

Super Asymmetry on The Big Bang Theory: How Realistic?

The TV show The Big Bang Theory portrays academia so I am naturally curious how realistic it is. I have posted about this before (see here) in the context of whether actual things they say about physics are true. Today I post about a recent arc where Amy and Sheldon are working on Super asymmetry.


SPOILER ALERT

1) The name: Super Asymmetry. Its not a field but it could be. I assume its about particle physics but I'm not sure they ever say this. A fine name!

2) Amy is a neurobiologist (this was flagged as not being word, but I think it  is) working with Sheldon on a physical theory that I would assume requires hard math.  Physics is hard! So I wonder how realistic this is. Actually, more important than being hard is that you need a lot of background knowledge. So the questions of interest is: Can an amateur still help in a discovery of a new physical theory? This may depend on the definitions of amateur, discovery, new, and physical.  Alone I would doubt it. But with help from Sheldon, I can believe it. Still, making new discoveries in an old field is hard.

3) Amy and Sheldon first had the idea for super asymmetry on their honeymoon. Most married couples have other things to do on their honeymoon. (I did ask my darling to prove the primes were infinite on our wedding day before I married her. She was nervous so couldn't do it, but normally she could. I know a mathematician who made her spouse memorize the definition of a Banach Space before they got married, and recite it to her on their wedding day before they got married.)

4) After they do most of the work they THEN go track down references. This seems stupid but not unrealistic. You can get excited about a theory and work on it at breakneck speed and not want to slow down to check references. But see next point.

5) Sheldon was counting on this for a Nobel Prize. I would think you would check refs before even thinking in those terms.

6) An article in Russian was found that proved the theory could not work. There are a few things wrong with this:

a) The article used the exact same phrase ``Super Asymmetry'' - that seems unlikely.

b) They seemed to not READ the article, just the first page, and then say. DARN, all that work down the tubes.

c) They seemed to not even try to say `OKAY, they did BLAH, we did BLAH BLAH, how do they compare and contrast' (ADDED LATER- I just saw the episode afterwards. They probably DO have something after all. They should have listened to my advice before going into a funk.)

d) If they did all of that work I am sure SOMETHING can be recovered from it.

7) This is not really a post about The Big Bang Theory. I want to know more about your experiences with research: have you worked on a problem and found out it didn't work or was already done, or something like that. And what happened?

Remembering George H. W. Bush

Today is the national day of mourning for George Herbert Walker Bush, one of the best presidents for science and computing. He created PCAST, the President's Council of Advisors on Science and Technology. Bush signed the High Performance Computing Act (introduced by Al Gore), that powered computing research and the Internet through the massive growth of the 90's. His administration started the Human Genome Project and the US Global Change Research Program. He appointed the first and so far only African-American NSF Director.

Bush also started the the short-lived Presidential Faculty Fellows program. As a member of the first class of fellows I got invited to a ceremony in the Rose Garden in June of 1992. I didn't actually get to shake hands with President Bush; in that busy election year we had a joint ceremony with some high school award winners and the National Medal of Technology recipients that included Bill Gates and Joseph Woodland, who invented the bar code scanner used at supermarkets. George Bush famously may or may not have been amazed by this technology a few months earlier at a grocers convention and had no issues joking about it when introducing Woodland.

Sipping lemonade on the White House lawn is not an experience one soon forgets. And I guess I haven't twenty-six years later. Thanks President Bush and God speed.

George HW Bush passed away- some non-partisan math comments

George HW Bush passed away recently. When he was alive there were 5 living ex presidents. Now there are 4. What is the max and min number of ex presidents? This we will answer. What is the prob of having many living ex-presidents?

What is the max number of ex-presidents alive at the same time? List the times this has happened. Your answer should be a list of statements of the following form:

 Shortly after X took office there were Y ex-presidents: Z(1), Z(2), ... , Z(Y).

I leave a little white space in case you want to try to figure it out, though the point of this post is not to quiz you.
















ANSWER: The max number of ex-presidents alive at the
same time is five. This has happened four times.

--------------------------------------------
ONE: In 1861 just after Lincoln took office there were five living ex-presidents:
Martin van Buren (died in 1862), John Tyler (died in 1862), Millard Fillmore (died in 1874), Franklin Pierce (died in 1869), James Buchanan (died in 1868).

Key factors: (1) Between 1836 and 1860 there were no 2-term presidents, (2) Martin van Buren lived a long time after being president.

TWO: In 1993 just after Clinton took office there were five living ex-presidents:
Richard M. Nixon (died in 1994), Gerald Ford (died in 2006), Jimmy Carter (still alive as of Dec 2018), Ronald Reagan (died in 2004), George HW Bush (died in 2018).

Key factors: (1) Nixon, Ford, Carter, Bush Sr were the equivalent of 4 one-terms, and (2) Reagan lived a long time after being president.

THREE: In 2001 just after George W. Bush took office there were five living ex-presidents:
Gerald Ford (died in 2006), Jimmy Carter (still alive as of Dec 2018), Ronald Reagan (died in 2004), George Bush (died in 2018).  Bill Clinton (still alive as of Dec 2018).

Key factors: (1) Ford, Carter, Bush Sr. were effectively 3 one-terms, and (2) Reagan lived a long time after being president.

FOUR: In 2017 just after Donald Trump took office there were five living ex-presidents:
Jimmy Carter (still alive as of Dec 2018), George  HW Bush (died in 2018).  Bill Clinton (still alive as of Dec 2018).  George W Bush (still alive as of Dec 2018).  Barack Obama (still alive as of Dec 2018).

Key factors: (1) Carter, Bush were both one-termers,  (2) Clinton and W are relatively young for presidents and in good health, and  (3) Carter and Bush Sr. lived  a long time (Carter is still living!)

------------------------------------

I want to see this record broken! I want to see 6 living ex presidents! (Darling asks why I want to see that. Its a good question which I will partially address later.) Hence I want to see Donald Trump impeached or resign or leave office!  I was hoping it would would happen before one of Carter, Bush Sr, Clinton, W, Obama died. Oh well.

So now what? Is it possible that we will see 6 living ex-presidents in our lifetime. Factors: prez longevity, prez age, one-term vs two-term, and since I am asking about in OUR lifetime, our longevity.

Lets assume that neither The Donald nor any other president resigns or gets impeached or leaves office before their term is up. We assume that the presidents after Trump are  Alice, Bob, Carol.

Scenarios:

ONE: Donald Trump loses to Alice in 2020, Alice loses to Bob in 2024. None of the ex presidents dies before 2025. Then we would have, in the first day of the Bob presidency, which would be  in  2025,  6 living ex presidents:  Carter, Clinton, W, Obama, Trump, Alice.

This needs Carter to live to be about 100 (the others are much younger). Possible!

TWO: Donald Trump loses  to Alice in 2020, Alice loses to Bob in 2024 . Bob loses to Carol in 2028. Carter passes away before 2025 but the other ex presidents are alive in 2029. Then we would have, in the first day of the Carol presidency, which would be in 2029, 6 living ex presidents:Clinton, W, Obama, Trump, Alice, Bob.

This needs W, Clinton, Trump  to live to be about 83 and Obama to live to be 72.  Possible!

I'll stop here, but you can make up your own SCENARIO THREE which requires some people to live to 87.

Scenario ONE seems unlikely. TWO and THREE are plausible; however, there is another factor. I am assuming a long string of one-termers (that was flagged as not-a-word. Oh well.)  Lately incumbency has a big advantage: Clinton, W, Obama were all two-termers. Incumbency is powerful for two reasons that reinforce each other:

The incumbent can DO things, can LOOK presidential.

Since the incumbent has these advantages people are scared to run against him or her.

--------------------------------------
Math problem: What is the probability that we will see 6 living ex presidents by 2029? To solve this you would need to know

Longevity statistics. But of what group? by Age? by profession? of ex-presidents? That seems to narrow for good statistics.

Incumency statistics. How likely is it for a Prez to be re-elected? Again, too small a sample size. And Trump seems like an outlier. I suspect that if Jeb or Hillary were president they would get re-elected because of the incumbency advantage. But Trump is so unusual that it might not hold. One thing in his favor: it is unlikely there will be a challenge from his own party. One thing in his disfavor would be a third party challenge. But ENOUGH. My point is that it would be hard to do good stats here.

-------------------------------------


So why do I care about seeing 6 living ex-presidents in my lifetime? I have a reason but its not a good reason.

Early in the Nixon Presidency LBJ died. I noticed that there were ZERO living ex-presidents. I knew that LBJ was dead, and JFK was dead, and I suspected (correctly) that Eisenhower and Truman were dead, and I knew FDR was dead. Before that we have Hoover and others who were of course dead. I was SO PROUD of myself for KNOWING this (to be fair I was 12 years old). This sparked my interest in presidents and especially in the question of most/least living ex-prez.

Now for the obvious question on the other end of the spectrum:

What is the min number of ex-presidents alive at the same time? And when did it occur (list all times)

White space for those who want to try to figure it out or look it up.
























ANSWER: Zero. This happened six times.

ONE: When George Washington was president there obviously were zero living ex-presidents.

TWO: Shortly after John Adams became president George Washington died. At that time there were zero ex-presidents.

THREE: During Ulysses S Grant's term Andrew Johnson, the prior president died. Lincoln was dead by assassination and all prior presidents were dead of old age  or similar (e.g., James Buchanan died at the age of 77, Franklin Pierce (an ancestor of Barbara Bush (nee Pierce) was 65 and died of cirrhosis of the liver, from alcoholism.)

FOUR: During Theodore Roosevelt's term Grover Cleveland died, and all other ex-presidents were dead.  Recall that the prior prez, McKinley, had been assassinated.

FIVE: During Herbert Hoover's term, following Calvin Coolidge's death (Hoover's predecessor), there were no ex-presidents.  This partially explains why Coolidge didn't run- he had health problems.  Note that Harding died in office.

SIX: During Nixon's term, in 1973, Lyndon Johnson died. At that time there were zero ex-presidents.  This was because Lyndon Johnson died young (65), Kennedy was assassinated, Eisenhower was old while president.


NOTE: I would have thought that since FDR served so long and died in office either during FDR's term or Harry Truman's term there would be a time with no living ex-presidents.  Early in FDR's term there was only one living ex-president: Hebert Hoover. However, he didn't die until 1964. Hence he lived through the presidencies of FDR, Truman, Eisenhower, Kennedy, and part of Johnson's.  This is NOT the most presidents an ex-president has lived through after they step down. That honor might go to Carter who has lived through the presidencies of Reagan, Bush Sr, Clinton, W, Obama, and, as of this writing, a few years of Trump.  I have not checked if this is a record but I will once Carter passes away.

NOTE: In most of the cases above a recent president had died prematurely. Grant- Lincoln, Roosevelt- McKinley, Hoover- Coolidge, Nixon- Johnson and Kennedy.)

NOT: Since Obama, W, and Clinton are all relatively young, and presidents dying in office is now very rare (the last one was JFK in 1963)   I doubt this will happen again. But politics and history can surprise you.