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) = g(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.

LOGCFL Venkat Style

H. Venkateswaran, a much loved professor in the School of Computer Science at Georgia Tech and a fellow computational complexity theorist, is retiring at the end of December. In honor of Venkat I'd like talk about my favorite paper of his, relating LOGCFL to semi-unbounded circuits.

Let's start with context-free languages. Even if you never took a theoretical computer science course, you probably saw them in elementary school.

A context-free language is a series of rules like S-> NP VP or N->man. The context-free part comes from the fact that a noun phrase (NP) produces the same sentence fragments wherever it appears. CFLs have a rich theory--there have been whole textbooks devoted to the topics.

LOGCFL are the set of problems that are reducible to context-free languages with a small-space reduction. Formally, A is in LOGCFL if there is a CFL B and a log-space computable function f such that for all x, x is in A if and only if f(x) is in B.

Venkat showed that LOGCFLs are equivalent to semi-unbounded circuits, log-depth circuits with unbounded OR gates but bounded AND gates, the class now called SAC¹ (technically the equivalence holds for log-space uniform SAC¹ but that's not important). His proof goes through various models of alternating Turing machines and push-down automata.

Context-free languages are not closed under complement, for example 0ⁿ1ⁿ0ⁿ is not context-free but its complement is. Somewhat surprisingly Borodin, Cook, Dymond, Ruzzo and Tompa showed that LOGCFL is closed under complement, combining the Immerman-Szelepcsényi inductive counting technique with Venkat's circuit characterization of LOGCFL.

The Borodin result implies that you whether you have bounded ORs and unbounded ANDs, or bounded ANDs and unbounded ORs, you compute the same class.

Enjoy your retirement Venkat. We'll miss you!

If you think a theorem is true then spend half your time trying to prove its true, and half trying to prove its false.

There is a quote I recall but not who said it.  I have not been able to find it on the web.


If you think a theorem is true then spend half of your time trying to prove that its true, and half trying to prove that its false.

I thought it was Erdos but I could not find any connection between him and the saying. I did find something that indicates he did not say it:

An Erdos problem that pays different amounts of money for the conjecture being true of false:

--------------------------------------------------------------------------------
For a finite family F of graphs, let t(n,F) denote the smallest integer m that every graph on n vertices and m edges must contain a member of F as a subgraph.

A problem on Turán numbers for graphs with degree constraints} (proposed by Erdös and Simonovits [1]. $250 for a proof and $100 for a counterexample)

Prove or disprove that
t(n,H)=O(n^{3/2})
t(n,H)=O(n^{3/2})
if and only if H does not contain a subgraph each vertex of which has degree >2

Bibliography
1 P. Erdös, Some of my old and new combinatorial problems, Paths, flows, and VLSI-layout (Bonn, 1988), Algorithms Combin., 9, 35-45, Springer, Berlin, 1990.
----------------------------------------------------------------------------------------

A while back there was a $1,000,000 prize for PROVING Goldbach's conjecture (the prize had a deadline which is past). See here. However, the article does not say what you win for a counterexample. I suspect nothing. Is this fair? (1) YES- proving Goldbach would be hard, where as if its false just finding the counterexample likely won't require hard math, (2) NO- HEY, they resolved it, so there, (3) Have a panel look at the solution and decide if it has merit.

ANYWAY- if someone knows the source of the quote, please let me know.

Is Secret sharing REALLY REALLY REALLY used?

Since I am teaching Cryptography this semester I am teaching things people REALLY REALLY REALLY (RRR) use. For some topics this is RRR true, like RSA (that it is used to transmit a private key that is then used is FINE.)

I was wondering if Information-Theoretic Secret Sharing is RRR used. I am asking non-cynically and non-rhetorically. So I want to be taken seriously AND literally.

  I Googled and got some answers but could not verify them.

1) At this site: here we can read

Every modern HSM (hardware secure module, for crypto applications) uses Shamir's secret sharing.

I tried to verify this but was unable to.

I also read

The DNSSEC root key is 5-out-of-7 shared see, e.g., here or here

The link leads to a story about how there are 7 people and if any 5 get together they can shut down the internet. The story does not say they use secret sharing.

2) Threshold cryptography (see here) would seem to use it, but is Threshold crypto used? There is a startup who is trying to use it: see here. I don't count that as RRR since they don't have customers yet. Not sure what the threshold is for whether I count it.

3) Some papers mention that secret sharing COULD be used if you want to make sure nuclear missiles are not launched unless x out of y people say so. But I doubt it really is used. If so this might be very hard to verify.

4) Shamir's secret sharing scheme is pretty simple and does not have big constants so if there is a need it really could be used. But is there a need?

I am not quite sure what I count as proof that someone RRR  using it. A random person at a random website just saying that HSM uses it does not seem convincing. A Wikipedia article saying its being used I would find convincing (should I? Until recently Wikipedia couldn't even get my year of birth straight, see here)

If some companies website said they used Shamir's Secret Sharing I would believe that-- but a companies website is not likely to say that. NOT for reasons of company secrets but because its not what most customers go to the website to find.

SO- if someone RRR knows that Secret Sharing is RRR being used then please leave a comment.