Wednesday, November 28, 2018

LOGCFL Venkat Style








Enjoy your retirement Venkat. We'll miss you!

Monday, November 26, 2018

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
if and only if H does not contain a subgraph each vertex of which has degree >2

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.

Tuesday, November 20, 2018

Is Secret sharing REALLY REALLY REALLY used?



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

1) At this site: here we can read


I tried to verify this but was unable to.

I also read









Thursday, November 15, 2018

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".

Monday, November 12, 2018




1) Who did you vote for in 2016?





I'm surprised someone wanted Harmabe. Is he even a citizen?


Since Clinton hasn't done anything to merit rejection since the election,
then I could see it.

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

than expected.




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)

48 do not regret their vote.


1 Trump/Clinton
1 Trump/Nobody

FOUR people voted Trump and now regret it.


2 Clinton/Johnson
1 Clinton/Trump
1 Clinton/Kanye
1 Clinton/Gasarch

FIVE people voted Clinton and now regret it.

MISC changed

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.
has done anything since the election to make anyone thing better
to change people's opinions of him.

Thursday, November 08, 2018

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.

Monday, November 05, 2018

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.

Thursday, November 01, 2018

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 PA = NPA then L(MA) runs in polynomial time and differs from SATA on only a finite number of strings. SATA is a relativizable form of SAT with a built in relations that answer whether a sequence of variables encode an string in A. SATA is NPA-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 PA = NPA and either Mdoes not compute SATA correctly on all inputs or Mtakes at least exponential time.


Define B = {0x | x in TQBF}. TQBF is the PSPACE-complete problem containing all the true quantified Boolean formula. PTQBF = PSPACE = NPTQBF and thus PB = NPB.

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 MBn) takes less than 2n computational steps. If no such n exists let A = B and we are done.

If MBn) accepts we are done by letting A=B since B has no string beginning with 1.

If MBn) rejects and uses less than 2n steps there must be some z such that MBn) did not query 1z. Let A = B ∪ {1z}.

MAn) still rejects but now φn is in SATA. Also PA = NPA since adding a single string to an oracle won't affect whether two classes collapse.