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.

Simons and Amazon

I'm spending this week at the Simons Institute in smokey Berkeley, California. This fall Simons has a program in Lower Bounds in Computational Complexity. Scroll down that page and you'll see the rather strong collection of participants that are spending much of the fall at the Institute.

I purposely chose a week without a workshop--I'd rather talk to people than sit in talks. My former PhD student Rahul Santhanam is hosting me and we are having some fun discussions about the minimum circuit-size problems, pseudorandom generators and white vs black box algorithms. I've grown a little rusty in complexity during my years as department chair and have to work to keep up with Rahul. The student has become the master.

Even a quiet week at Simons is not that quiet. Every night seems to have a theme: trivia, board games, pub night, music night. I participated in a discussion with the "journalist in residence" on how to make lower bounds interesting to the general public. As part of a Turing awardee lecture series, Andy Yao gave a talk on Game Theory in Auction and Blockchain which included some reminiscing of Yao's golden time in Berkeley back in the early 80's when he helped lay the mathematical foundations of modern cryptography.

Simons started as a competition and, while I was on team Chicago, I have to admit Berkeley has done a wonderful job with the institute. We've just seen the results from another competition, with Amazon splitting their "second headquarters" between Northern Virginia and Queens, missing an awesome opportunity in Atlanta (not that I'm biased). Not surprised about the DC area, but pretty surprised about separating the HQ into two locations, neither planned to reach the level of activity of HQ1 in Seattle. Amazon stated that they didn't think they could find the tech talent to fill 50,000 positions in a single city. So much for "build it and they will come".

And the winner is again, Harambe: A pre election poll of my class that was truly a referenum on the Prez

I had meant to post this before the election but I didn't quite time it right. Oh well.

It has been said that this midterm election (more than others) was a referendum on the prez.  Every prez election year I have my students (or someone's students) vote (Secret Ballot of course) for president. ((see 2016 , 2012, 2008) This year, for the first time, I had a midterm election, though rather than ask them which Maryland people they would vote for, I made it truly a referendum on Trump by asking two questions:

1) Who did you vote for in 2016?

2) Knowing what you know now, who would have have voted for in 2016?

Full Disclosure: I am in the Clinton/Clinton Camp. However, this is an information-post not an opinion-post, so my vote is not relevant nor was it counted.

I give the full results at the end of the post; however, I will summarize the most interesting data: the change-mind people and my thoughts.

4 voted Trump and now wish they voted differently: Harmabe, Clinton, Nobody, Gasarch

Only 12 people had voted for Trump in 2016 and of those 4
regret it. While I can see wanting Clinton, Nobody, or Gasarch,
I'm surprised someone wanted Harmabe. Is he even a citizen?

5 voted Clinton and now wish they voted differently: 2-Johnson, Trump, Kanye, Gasarch.

Since Clinton hasn't done anything to merit rejection since the election,

I deduce these people are more going TOWARDS the one they picked rather

than AWAY from her. Trump has been Prez and has done stuff, so Clinton/Trump

makes sense -- the student's opinion is that Trump is doing better

than expected. Gary Johnson hasn't done anything to merit a change towards

him, so thats a puzzler.  Kanye, similar. As for Gasarch, if the reasoning

is `he's doing a good job teaching crypto, lets make him president' doesn't

really work since he's not doing THAT good a job. If it was Ramsey theory

then I could see it.

Misc:

1 Underwood(House of Cards)/Satan (For those tired of picking the LESSER of two evils)

1 Stein/Clinton

1 Johnson/Clinton

1 Kruskal/Gasarch (some people can't tell them apart)

The two who went to Clinton I interpret as thinking Trump is worse

than expected.

ALSO: Hillary had 28 Hillary/Hillary. Hence Trump had the largest percentage of people who regret voting for him, but still only 1/3. And the numbers are to small to make much of them.

MY OPINON: FORTNOW in 2020!

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

61 students did the poll.

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

Stayed the same:

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

Stayed the same:

28 Clinton/Clinton

8 Trump/Trump

4 Stein/Stein

3 Johnson/Johnson

1 Kasich/Kasich

1 Sanders/Sanders

1 Jerry White/Jerry White (Socialist Party)

1 Bofa/Bofa (this is a joke)

1 Thomas Adam Kirkman/Thomas Adam Kirkman (prez on TV show Designated Survivor)

48 do not regret their vote.

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

Trump/XXX

1 Trump/Harmabe (Harambe is the Gorilla who got shot in a zoo.)

1 Trump/Clinton

1 Trump/Nobody

1 Trump/Gasarch (Gasarch would prove the problems of government are unsolvable rather than solve them)

FOUR people voted Trump and now regret it.

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

Clinton/XXX

2 Clinton/Johnson

1 Clinton/Trump

1 Clinton/Kanye

1 Clinton/Gasarch

FIVE people voted Clinton and now regret it.

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

MISC changed

1 Underwood(House of Cards)/Satan (For those tired of picking the LESSER of two evils)

1 Stein/Clinton

1 Johnson/Clinton

1 Kruskal/Gasarch (some people can't tell them apart)

TWO people who voted third party now would have voted Clinton.

I interpret this as not-liking-Trump since I don't think Clinton

has done anything since the election to make anyone thing better

or worse of her, while as Trump as president has done enough

to change people's opinions of him.

The Data Transformation of Universities

With all the news about elections, caravans, shootings and attorney generals, maybe you missed the various stories about real transformations at our top universities.

On October 15 MIT announced the Stephen A. Schwarzman College of Computing. Schwarzmann donated $350 million to the effort as part of an expected billion-dollar commitment that will pay for a new building and fifty new faculty.

“As computing reshapes our world, MIT intends to help make sure it does so for the good of all,” says MIT President L. Rafael Reif. “In keeping with the scope of this challenge, we are reshaping MIT. The MIT Schwarzman College of Computing will constitute both a global center for computing research and education, and an intellectual foundry for powerful new AI tools. Just as important, the College will equip students and researchers in any discipline to use computing and AI to advance their disciplines and vice-versa, as well as to think critically about the human impact of their work. 

Two weeks later the University of California at Berkeley announced a Division of Data Science to be led by an associate provost reporting directly to the provost (like a dean).

“Berkeley’s powerful research engine, coupled with its deep commitment to equity and diversity, creates a strong bedrock from which to build the future foundations of this fast-changing field while ensuring that its applications and impacts serve to benefit society as a whole,” said Paul Alivisatos, executive vice chancellor and provost. “The division’s broad scope and its facilitation of new cross-disciplinary work will uniquely position Berkeley to lead in our data-rich age. It will simultaneously allow a new discipline to emerge and strengthen existing ones.”

Sorry Berkeley, you are anything but unique. Every major research university is trying to build up expertise in computing and data science given the demands of students, industry and researchers across nearly all academic disciplines who need help and guidance in collecting, managing, analyzing and interpreting data.

Here at Georgia Tech, where we've had a College of Computing since 1990, we recently started an Interdisciplinary Research Institute in Data Science and Engineering and a Interdisciplinary Research Center in Machine Learning both to be housed in a twenty-one story CODA building that will open next year in Midtown Atlanta (sounds impressive when I write it down).

I could go on for pages on how other universities are rethinking and transforming themselves. Earlier this year Columbia (who hired Jeannette Wing to run their data science institute) held a summit of academic data science leadership. The report shows we have much to do.

The real secret is that none of us have really figured it out, how to meet the escalating needs for computing and data and integrating it across campus. We aim at a moving target problem as we sit just at the beginning of the data revolution that will reshape society. The future looks rocky, scary and fun.

Is Fuzzy Sets Common Knowledge? How about Napier as inventing (or something) logs?

Darling: Bill, help me with this crossword puzzle. 6 letter word that begins with N, clue is log man

Bill: Napier

Darling: Who was that?

Bill: A famous lumberjack

Darling: Give me a serious answer

Bill: Okay. He is said to have invented logarithms. Like most things in math its not quite clear who gets the credit, but he was involved with logarithms early on.

Darling: I said give me a serious answer. That is rather obscure and would not be in a crossword puzzle.

While darling is wrong about the answer being wrong she is right about it being obscure. How would your typical crossword puzzler know the answer? Perhaps Napier appears in a lot of crosswords since it has lots of vowels, so they just word-associate `log man' to `Napier'  But in any case this does seem odd for a crossword puzzle.

In the quiz show Jeopardy, in round two, the following was an $800 question under philosophy (the questions are 400,800,1200,1600,2000, so 800 is supposed to be easy)

In 1965 Lotfi Zadeh introduced this type of set with no clear boundaries leading to the same type of ``logic''

1) I suspect that all my readers know that the correct response is `Fuzzy' (or formally `What is Fuzzy')

2) Why is this in Philosophy? There IS an entry of it in the Stanford Enc of Phil (see here). Some Philosophers work on Logic, but do they work on Fuzzy Logic? The wikipedia page for Fuzzy Logic (see here) has only one mention of phil and its to the Stanford Enc of Phil chapter.

3) (more my point) Is Fuzzy Logic so well known as to be an easy question on Jeop? See next point

4) Can someone get this one right WITHOUT knowing ever having heard of Fuzzy Logic. I suspect yes and, indeed, the contestant DID get it right and I think she had never heard of Fuzzy Logic. While I can't be sure one tell is that when a contestant says `what is fuzzy logic' and it actually sounds like a question, then they are partially guessing.

Anyway, I am surprised that this obscure bit of math made it into an easy question on Jeop. But since the contestant got it right, it was appropriate.

P = NP Need Not Give a SAT Algorithm

In Bill's post earlier this week, he asks if there is a fixed algorithm such that if P = NP, this algorithm will correctly compute satisfiability on all inputs. While I believe this statement is true because P ≠ NP, I would like to argue we won't prove it anytime soon.

Bill links to a TCS Stack Exchange answer by Marzio De Biasi giving a fixed algorithm that would get SAT correct except on a finite number of inputs if P = NP. Here is Marzio's algorithm.

Input: x   (boolean formula)
Find the minimum i such that
  1) |M_i| < log(log(|x|))  [ M_1,M_2,... is a standard fixed TM enumeration] 
  2) and  M_i solves SAT correctly 
       on all formulas |y| < log(log(|x|))
          halting in no more than |y|^|M_i| steps
          [ checkable in polynomial time w.r.t. |x| ]
  if such i exists simulate M_i on input x 
      until it stops and accept/reject according to its output
      or until it reaches 2^|x| steps and in this case reject;
  if such i doesn't exist loop for 2^|x| steps and reject.

This proof relativizes: There is a fixed relativizing Turing machine M such that for all A, if P^A = NP^A then L(M^A) runs in polynomial time and differs from SAT^A on only a finite number of strings. SAT^A is a relativizable form of SAT with a built in relations that answer whether a sequence of variables encode an string in A. SAT^A is NP^A-complete for all A.

The following shows any proof that a fixed algorithm can compute all of SAT correctly if P = NP cannot relativize.

Theorem: For every deterministic Turing machine M, there is an A such that P^A = NP^A and either M^A does not compute SAT^A correctly on all inputs or M^A takes at least exponential time.

Proof:

Define B = {0x | x in TQBF}. TQBF is the PSPACE-complete problem containing all the true quantified Boolean formula. P^TQBF = PSPACE = NP^TQBF and thus P^B = NP^B.

Let φ_n be the formula that is true if there exists a string z of length n such that 1z is in A. Let n be the smallest n such that M^B(φ_n) takes less than 2ⁿ computational steps. If no such n exists let A = B and we are done.

If M^B(φ_n) accepts we are done by letting A=B since B has no string beginning with 1.

If M^B(φ_n) rejects and uses less than 2ⁿ steps there must be some z such that M^B(φ_n) did not query 1z. Let A = B ∪ {1z}.

M^A(φ_n) still rejects but now φ_n is in SAT^A. Also P^A = NP^A since adding a single string to an oracle won't affect whether two classes collapse.