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".
Thursday, November 15, 2018
Monday, November 12, 2018
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.
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.
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.
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.
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.
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.
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.
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 MA does not compute SATA correctly on all inputs or MA 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. 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 MB(φn) takes less than 2n computational steps. If no such n exists let A = B and we are done.
If MB(φn) accepts we are done by letting A=B since B has no string beginning with 1.
If MB(φn) rejects and uses less than 2n steps there must be some z such that MB(φn) did not query 1z. Let A = B ∪ {1z}.
MA(φn) 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.
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 MA does not compute SATA correctly on all inputs or MA 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. 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 MB(φn) takes less than 2n computational steps. If no such n exists let A = B and we are done.
If MB(φn) accepts we are done by letting A=B since B has no string beginning with 1.
If MB(φn) rejects and uses less than 2n steps there must be some z such that MB(φn) did not query 1z. Let A = B ∪ {1z}.
MA(φn) 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.
Sunday, October 28, 2018
If P=NP then we HAVE an alg for SAT.
I am writing up the result of my survey of peoples opinion of P vs NP (it will be in a SIGACT News, in Lane's Complexity Column, in 2019.) Some people wrote:
P=NP but the proof will be nonconstructive and have a large constant.
Large constant could happen.
If by nonconstructive they mean not practical, then yes, that could happen.
The following does not quite show it can't happen but it does give one pause: an old result of Levin's shows that there is a program you could write NOW such that if P=NP then this program decides SAT except for a finite number of formulas (all of which are NOT in SAT) and can be proven to work in poly time (I will later give three pointers to proofs). The finite number of formulas is why the people above may still be right. But only a finite number- seems like a weak kind of nonconstructive.
Since I am teaching crypto I wondered about Factoring. An old result of Gasarch (I proved it this morning -- I am sure it is already known) shows that there is a program you could write NOW such that if Factoring is in P then this program factors a number ALWAYS (none of this finite exception crap) and can be proven to work in poly time. Even so, the algorithm is insane. If someone thought that factoring in P might be nonconstructive, my construction disproves it in such an absurd way that the notion that factoring could be in P nonconstructively should be taken seriously but not literally. There should be a way to say formally:
I believe that FACTORING is in P but any poly-time algorithm is insane (not even looking at the constants) and hence could never be implemented.
Not sure how to define insane.
Three pointers:
Stack Exchange TCS: here
Wikipedia: here
My slides (also include factoring result): here
Question: Can the SAT result be improved to be an algorithm that is ALWAYS right? Is there a way to show that it can't be (unless, say P=NP).
Question: What can be said about Graph Isomphism in this context? The proof for SAT is easily adpated to this case (all we used about SAT was that it was self-reducible). But can we get our GI algorithm to never make a mistake?
P=NP but the proof will be nonconstructive and have a large constant.
Large constant could happen.
If by nonconstructive they mean not practical, then yes, that could happen.
The following does not quite show it can't happen but it does give one pause: an old result of Levin's shows that there is a program you could write NOW such that if P=NP then this program decides SAT except for a finite number of formulas (all of which are NOT in SAT) and can be proven to work in poly time (I will later give three pointers to proofs). The finite number of formulas is why the people above may still be right. But only a finite number- seems like a weak kind of nonconstructive.
Since I am teaching crypto I wondered about Factoring. An old result of Gasarch (I proved it this morning -- I am sure it is already known) shows that there is a program you could write NOW such that if Factoring is in P then this program factors a number ALWAYS (none of this finite exception crap) and can be proven to work in poly time. Even so, the algorithm is insane. If someone thought that factoring in P might be nonconstructive, my construction disproves it in such an absurd way that the notion that factoring could be in P nonconstructively should be taken seriously but not literally. There should be a way to say formally:
I believe that FACTORING is in P but any poly-time algorithm is insane (not even looking at the constants) and hence could never be implemented.
Not sure how to define insane.
Three pointers:
Stack Exchange TCS: here
Wikipedia: here
My slides (also include factoring result): here
Question: Can the SAT result be improved to be an algorithm that is ALWAYS right? Is there a way to show that it can't be (unless, say P=NP).
Question: What can be said about Graph Isomphism in this context? The proof for SAT is easily adpated to this case (all we used about SAT was that it was self-reducible). But can we get our GI algorithm to never make a mistake?
Thursday, October 25, 2018
Good Results Made Meaningless
Sometimes you see a beautiful theorem A that you love to talk about. Then another beautiful theorem B comes around, making the first one meaningless since B trivially implies A. Not just a mere extension of A but B had a completely different proof of something much stronger. People will forget all about A--why bother when you have B? Too bad because A was such a nice breakthrough in its time.
Let me give two examples.
In STOC 1995 Nisan and Ta-Shma showed that Symmetric logspace is closed under complement. Their proof worked quite differently from the 1988 Immerman-Szelepcsenyi nondeterministic logpsace closed under complement construction. Nisan and Ta-Shma created monotone circuits out of undirected graphs and used these monotone circuits to create sorting networks to count the number of connected components of the graph.
Ten years later Omer Reingold showed that symmetric logspace was the same as deterministic logspace making the Nisan-Ta-Shma result an trivial corollary. Reingold's proof used walks on expander graphs and the Nisan-Ta-Shma construction was lost to history.
In the late 80's we had several randomized algorithms for testing primality but they didn't usually give a proof that the number was prime. A nice result of Goldwasser and Kilian gave a way to randomly generate certified primes, primes with proofs of primeness. Adleman and Huang later showed that one can randomly find a proof of primeness for any prime.
In 2002, Agrawal, Kayal and Saxena showed Primes in P, i.e., primes no longer needed a proof of primeness. As Joe Kilian said to me at the time, "there goes my best chance at a Gödel Prize".
Let me give two examples.
In STOC 1995 Nisan and Ta-Shma showed that Symmetric logspace is closed under complement. Their proof worked quite differently from the 1988 Immerman-Szelepcsenyi nondeterministic logpsace closed under complement construction. Nisan and Ta-Shma created monotone circuits out of undirected graphs and used these monotone circuits to create sorting networks to count the number of connected components of the graph.
Ten years later Omer Reingold showed that symmetric logspace was the same as deterministic logspace making the Nisan-Ta-Shma result an trivial corollary. Reingold's proof used walks on expander graphs and the Nisan-Ta-Shma construction was lost to history.
In the late 80's we had several randomized algorithms for testing primality but they didn't usually give a proof that the number was prime. A nice result of Goldwasser and Kilian gave a way to randomly generate certified primes, primes with proofs of primeness. Adleman and Huang later showed that one can randomly find a proof of primeness for any prime.
In 2002, Agrawal, Kayal and Saxena showed Primes in P, i.e., primes no longer needed a proof of primeness. As Joe Kilian said to me at the time, "there goes my best chance at a Gödel Prize".
Monday, October 22, 2018
Please Don't call them Guidance Counselors
As I mentor many HS students I was recently in email contact with the HS contact for projects and I noticed that the sign off was
Allie Downey
Guidance School Counselor
This piqued my interest so I emailed her asking why the cross out.
She was delighted to answer! Here is her email:
Thank you, but “Guidance Counselor” is an outdated term. It is from a time before there was the American School Counselor Association, before the profession required at least a Masters degree, and before there was a nationally recognized comprehensive school counseling program. Guidance is a service; school counseling is a program. This is a great website that explains it even better here
Thank you for taking the time to ask. Anyone in the profession today prefers the term School Counselor and I always appreciate when people inquire.
I asked her further about the difference and here is what she said:
Everyone in a young person’s life offers guidance in some fashion. School counselors still provide guidance classroom lessons (such as bully prevention and character development), but we do so much more. We help students develop their academic abilities and study skills. We assist them and their families in college and career planning. We teach coping skills so students can guide themselves. We ask questions to help these young adults discover the answers on their own. We help students learn how to advocate for themselves. We console. We mediate. We learn and adapt with changing climates. We work with families, faculty, and community members to make sure school is a safe place for students to learn and grow. And this is all before the lunch bell. It is an amazing profession and I am proud to call myself a school counselor.
Allie Downey
This piqued my interest so I emailed her asking why the cross out.
She was delighted to answer! Here is her email:
Thank you, but “Guidance Counselor” is an outdated term. It is from a time before there was the American School Counselor Association, before the profession required at least a Masters degree, and before there was a nationally recognized comprehensive school counseling program. Guidance is a service; school counseling is a program. This is a great website that explains it even better here
Thank you for taking the time to ask. Anyone in the profession today prefers the term School Counselor and I always appreciate when people inquire.
I asked her further about the difference and here is what she said:
Everyone in a young person’s life offers guidance in some fashion. School counselors still provide guidance classroom lessons (such as bully prevention and character development), but we do so much more. We help students develop their academic abilities and study skills. We assist them and their families in college and career planning. We teach coping skills so students can guide themselves. We ask questions to help these young adults discover the answers on their own. We help students learn how to advocate for themselves. We console. We mediate. We learn and adapt with changing climates. We work with families, faculty, and community members to make sure school is a safe place for students to learn and grow. And this is all before the lunch bell. It is an amazing profession and I am proud to call myself a school counselor.
Thursday, October 18, 2018
A New Cold War?
Imagine the following not-so-unrealistic scenario: The US-China trade war deepens leading to a cold war. The US blocks all Chinese citizens from graduate school in the US. Visas between the two countries become hard to get. The Chinese close off their Internet to the West.
Let's go back to the original cold war between the Soviet Union and the US roughly from 1947-1991. We didn't have a significant internet back then (though we can thank the cold war for the internet). One had to assume that the government read mail to/from USSR. Travel to and from the USSR and the Eastern block to the west was difficult. Academic research did cross over but only in dribs and drabs and we saw two almost distinct academic cultures emerge, often with duplication of effort (Cook/Levin, Borodin/Trakhtenbrot, Immerman/Szelepcsényi).
Beyond the limited communication came the lack of collaboration. Science works best with open discussion, sharing of ideas and collaborating with each other. It took a Russian and an American working together to give us Google.
No cold war in this age can completely cut off ideas flowing between countries but it can truly hamper knowledge growth. We can't count on US superiority with China already ahead of us in areas like high-speed trains, renewable energy and mobile payments.
The cold war did have an upside to science: The competition between the East and the West pushed research growth and funding on both sides. We already see arguments for quantum computing and machine learning by the necessity of staying ahead of the Chinese. But science funding should not be driven by fear but by curiosity and its indisputable long-term effects on our economy.
We must keep the flow of information and people open if we want science and technology to flourish to its fullest, from students through senior researchers. Don't let a new cold war bring us back to the days of separate communities, which will fail to produce the breakthroughs we will never know about.
If things continue along this path, the next decade may see the internet relegated to little more than just another front on the new cold war.I wouldn't have thought it in our hyperconnected age but we are in spitting distance of going back to the 60's. What would this all mean for science and computing?
Let's go back to the original cold war between the Soviet Union and the US roughly from 1947-1991. We didn't have a significant internet back then (though we can thank the cold war for the internet). One had to assume that the government read mail to/from USSR. Travel to and from the USSR and the Eastern block to the west was difficult. Academic research did cross over but only in dribs and drabs and we saw two almost distinct academic cultures emerge, often with duplication of effort (Cook/Levin, Borodin/Trakhtenbrot, Immerman/Szelepcsényi).
Beyond the limited communication came the lack of collaboration. Science works best with open discussion, sharing of ideas and collaborating with each other. It took a Russian and an American working together to give us Google.
No cold war in this age can completely cut off ideas flowing between countries but it can truly hamper knowledge growth. We can't count on US superiority with China already ahead of us in areas like high-speed trains, renewable energy and mobile payments.
The cold war did have an upside to science: The competition between the East and the West pushed research growth and funding on both sides. We already see arguments for quantum computing and machine learning by the necessity of staying ahead of the Chinese. But science funding should not be driven by fear but by curiosity and its indisputable long-term effects on our economy.
We must keep the flow of information and people open if we want science and technology to flourish to its fullest, from students through senior researchers. Don't let a new cold war bring us back to the days of separate communities, which will fail to produce the breakthroughs we will never know about.
Sunday, October 14, 2018
Practical consequences of RH ?
When it seemed like Riemann Hypothesis (RH) might be solved (see Lipton-Regan blog entry on RH here and what it points to for more info) I had the following email exchange with Ajeet Gary (not Gary Ajeet, though I will keep his name in mind for when I want to string together names like George Washington, Washington Irving, Irving Berlin, with the goal of getting back to the beginning) who is an awesome ugrad at UMCP majoring in Math and CS.
Ajeet: So Bill, now that RH has been solved should I take my credit cards off of Amazon?
Bill: I doubt RH has been solved. And I think you are thinking that from RH you can prove that factoring is in P. That is not known and likely not true.
Ajeet: What are my thoughts and why are they wrong?
Bill: What am I a mind-reader?
Ajeet: Aren't you?
Bill: Oh, Yes, you are right, I am. Here is what you are confusing this with and why, even if you were right you would be wrong.
Ajeet: It just isn't my day.
Bill: Any day you are enlightened is your day. Okay, here are the thoughts you have
a) From the Extended RH (a generalization of RH) you can prove that PRIMES are in P. (This algorithm is slow and not used. PRIMES has a fast algorithm in RP that people do use. Primes was eventually proven to be in P anyway, though again that is a slow algorithm). Note- even though we do not know if ERH is true, one could still RUN the algorithm that it depends on. ERH is only used to prove that the algorithm is in P.
b) There was an episode of Numb3rs where they claimed (1) RH implies Factoring in P-- not likely but not absurd (2) from the proof of RH you could get a FAST algorithm for factoring in a few hours (absurd). I say absurd for two reasons: (i) Going from basic research to application takes a long time, and (ii) See next thought
c) If (RH --> factoring easy) then almost surely the proof would present an algorithm (that can be run even if RH has not been proven) and then a proof that RH --> the algorithm's run time is poly. But I wonder -- is it possible that:
RH--> factoring easy, and
The proof does not give you the algorithm, and
if you had a proof or RH then you COULD get the algorithm (though not in a few hours).
I doubt this is the case.
Ajeet: So are there any practical consequences of RH?
Bill: Would you call better bounds on the error term of the prime number theory practical.
Ajeet: YES!
Bill: GREAT! For more on RH see here
Ajeet: So Bill, now that RH has been solved should I take my credit cards off of Amazon?
Bill: I doubt RH has been solved. And I think you are thinking that from RH you can prove that factoring is in P. That is not known and likely not true.
Ajeet: What are my thoughts and why are they wrong?
Bill: What am I a mind-reader?
Ajeet: Aren't you?
Bill: Oh, Yes, you are right, I am. Here is what you are confusing this with and why, even if you were right you would be wrong.
Ajeet: It just isn't my day.
Bill: Any day you are enlightened is your day. Okay, here are the thoughts you have
a) From the Extended RH (a generalization of RH) you can prove that PRIMES are in P. (This algorithm is slow and not used. PRIMES has a fast algorithm in RP that people do use. Primes was eventually proven to be in P anyway, though again that is a slow algorithm). Note- even though we do not know if ERH is true, one could still RUN the algorithm that it depends on. ERH is only used to prove that the algorithm is in P.
b) There was an episode of Numb3rs where they claimed (1) RH implies Factoring in P-- not likely but not absurd (2) from the proof of RH you could get a FAST algorithm for factoring in a few hours (absurd). I say absurd for two reasons: (i) Going from basic research to application takes a long time, and (ii) See next thought
c) If (RH --> factoring easy) then almost surely the proof would present an algorithm (that can be run even if RH has not been proven) and then a proof that RH --> the algorithm's run time is poly. But I wonder -- is it possible that:
RH--> factoring easy, and
The proof does not give you the algorithm, and
if you had a proof or RH then you COULD get the algorithm (though not in a few hours).
I doubt this is the case.
Ajeet: So are there any practical consequences of RH?
Bill: Would you call better bounds on the error term of the prime number theory practical.
Ajeet: YES!
Bill: GREAT! For more on RH see here
Thursday, October 11, 2018
2018 Fall Jobs Post
As we do every year at this time, we help you find that perfect academic job. So who's hiring in CS this year? Perhaps we should instead follow the advice of John Regehr.
Even if you don't see an ad, almost surely your favorite university is looking to hire computer scientists. Check out their website or email someone at the department.
And (selfish plug) Georgia Tech is looking to hire in theory this year.
Some generally good advice: Make sure you have strong letter writers who know your research well, best if one or two of them come from outside your university. Put all your papers and materials on your website and make sure your Google Scholar page is accurate. Put effort into your job talk and remember you need to sell you research to non-theorists. Good if you can connect to other areas especially machine learning, data science or cybersecurity. Quantum seems hot this year.
Above all have fun! In this computational and data driven world we live in, there is a great job out there for you.
For computer science faculty positions best to look at the ads from the CRA and the ACM. For theoretical computer science specific postdoc and faculty positions check out TCS Jobs and Theory Announcements. If you have jobs to announce, please post to the above and/or feel free to leave a comment on this post.I said this last year and it's time to say it again:— John Regehr (@johnregehr) September 28, 2018
to save time and energy, will the CS departments NOT hiring faculty this year please speak up?
Even if you don't see an ad, almost surely your favorite university is looking to hire computer scientists. Check out their website or email someone at the department.
And (selfish plug) Georgia Tech is looking to hire in theory this year.
Some generally good advice: Make sure you have strong letter writers who know your research well, best if one or two of them come from outside your university. Put all your papers and materials on your website and make sure your Google Scholar page is accurate. Put effort into your job talk and remember you need to sell you research to non-theorists. Good if you can connect to other areas especially machine learning, data science or cybersecurity. Quantum seems hot this year.
Above all have fun! In this computational and data driven world we live in, there is a great job out there for you.
Monday, October 08, 2018
A New ACO Center (guest post by Vijay Vazirani)
Guest Post by Vijay Vazirani
A New ACO Center!
Last week, I helped launch an ACO Center (Algorithms, Combinatorics and Optimization) at my wonderful new home, UC Irvine. There are only two other such centers, at CMU and Georgia Tech (29 and 27 years old, respectively). My personal belief is that there will be more in the future. Let me justify.
When I joined Georgia Tech in 1995, my research was centered around approximation algorithms, a topic that resonated with its ACO Center. I was able to build on this interest in numerous ways: by offering new versions of courses on this topic as new results emerged, attracting to GT, for the first time, a large number of top theory PhD students who went on to produce stellar results and start impressive careers of their own. Course notes accumulated over the years eventually lead my book on the topic in 2001. Right after that, I switched to algorithmic game theory, and again ACO became the center of that activity, this time resulting in a co-edited book which had a huge impact on the growth of this area. In short, ACO gave me a lot! In turn, I believed in it and I worked for it wholeheartedly.
A New ACO Center!
Last week, I helped launch an ACO Center (Algorithms, Combinatorics and Optimization) at my wonderful new home, UC Irvine. There are only two other such centers, at CMU and Georgia Tech (29 and 27 years old, respectively). My personal belief is that there will be more in the future. Let me justify.
When I joined Georgia Tech in 1995, my research was centered around approximation algorithms, a topic that resonated with its ACO Center. I was able to build on this interest in numerous ways: by offering new versions of courses on this topic as new results emerged, attracting to GT, for the first time, a large number of top theory PhD students who went on to produce stellar results and start impressive careers of their own. Course notes accumulated over the years eventually lead my book on the topic in 2001. Right after that, I switched to algorithmic game theory, and again ACO became the center of that activity, this time resulting in a co-edited book which had a huge impact on the growth of this area. In short, ACO gave me a lot! In turn, I believed in it and I worked for it wholeheartedly.
I still believe in ACO and I feel it is very much relevant in today’s research world. Similar to the other two ACOs, our Center at UCI also exploits the natural synergies among TCS researchers from the CS Department, probability and combinatorics researchers from the Math Department, and optimization researchers from the Business School. Additionally, our Center has grown well beyond these boundaries to include a highly diverse collection of faculty (e.g., from the prestigious Institute for Mathematical Behavioral Sciences) whose common agenda is to utilize the “algorithmic way of thinking”, which is set to revolutionize the sciences and engineering over the course of this century, just as mathematics did in the last. The Center website has further details about its vision and activities.
Many universities are in a massive hiring mode today (especially in CS), e.g., UCI plans to hire 250 new faculty over the next five years. Centers such as ours present the opportunity of hiring in a more meaningful manner around big themes. They can also be instrumental in attracting not only top students but also top faculty.
A center of excellence such as GT’s ACO does not simply spring up by itself; it requires massive planning, hard work, good taste and able leadership. For the last, I will forever be indebted to Robin Thomas for his highly academic, big vision, classy leadership style which was the main reason ACO remained such a high quality program for so long. Moving forward, will we stay with three ACO Centers or will there be more? I believe the latter, but only time will tell.
Saturday, October 06, 2018
John Sidles, Mike Roman, Matt Howell, please email me/hard to get emails of people
John Sidles, Mike Roman, Matt Howell : please email me. at gasarch@cs.umd.edu (my usual email)
I need to ask you about some comments you left on the blog a while back (or emailed me -- I forget which, but I can't find your emails if you did email me). I need you to contact me SOON!
When you do I will tell you whats up and why I decline to say here what this is about.
For my other readers -- it is nothing controversial.
How hard is it to find people's emails on the web?
Sometimes it takes less than 5 minutes
Sometimes it is impossible.
Sometimes I get it by asking someone else who knows, or knows who to ask... etc.
It is rare that more time on the web helps. I do not think I ever spend more than 5 minutes and then found it. I have sometimes used linked-in. I don't have a Facebook account (I was going to put in a link to the latest Facebook privacy breach, but (1) by the time you read this they may have had another one, (2) you all know about it, and (3) when I typed in `Facebook Scandal' to Google I got the Facebook page for the TV show Scandal.)
Should people make their emails public? I can see why one does not want to. The old saying is that if you owe people money you want to be hard to find, but if people owe you money you want to be easy to find.
Contrast email to what people DO put online. A few years ago I needed someone's email address. I found his website. From his website I found out the exact day he lost his virginity. Okay... Didn't need to know that. But I still could not find his email address. I later asked someone who asked someone etc. and got it. But I was struck by what was private and public. This is NOT a complaint (though I wish it was easier to fine email addresses) just an observation.
I need to ask you about some comments you left on the blog a while back (or emailed me -- I forget which, but I can't find your emails if you did email me). I need you to contact me SOON!
When you do I will tell you whats up and why I decline to say here what this is about.
For my other readers -- it is nothing controversial.
How hard is it to find people's emails on the web?
Sometimes it takes less than 5 minutes
Sometimes it is impossible.
Sometimes I get it by asking someone else who knows, or knows who to ask... etc.
It is rare that more time on the web helps. I do not think I ever spend more than 5 minutes and then found it. I have sometimes used linked-in. I don't have a Facebook account (I was going to put in a link to the latest Facebook privacy breach, but (1) by the time you read this they may have had another one, (2) you all know about it, and (3) when I typed in `Facebook Scandal' to Google I got the Facebook page for the TV show Scandal.)
Should people make their emails public? I can see why one does not want to. The old saying is that if you owe people money you want to be hard to find, but if people owe you money you want to be easy to find.
Contrast email to what people DO put online. A few years ago I needed someone's email address. I found his website. From his website I found out the exact day he lost his virginity. Okay... Didn't need to know that. But I still could not find his email address. I later asked someone who asked someone etc. and got it. But I was struck by what was private and public. This is NOT a complaint (though I wish it was easier to fine email addresses) just an observation.
Thursday, October 04, 2018
Google added years to my life
If you google
gasarch
you used to get the following: here
Please go there and notice how old they say I am.
Okay, you are back. You may have noticed that they say I am 68. Gee, I don't feel 68 (I feel younger).
I have no idea how Google got my age wrong.
0) I found about this when I saw my age in an article about the Muffin problem. The article is here. I had been in contact with the author earlier so it was easy to contact him, assure him that I appreciate his throwing scammers and spammers off of my trail by giving me the wrong age, but I wondered why he chose 68. He then apologized (which was not needed) and pointed me to the google thing.
1) My age was not on my Wikipedia page. Nor was my birth year.
2) I do not recall every telling Google my age -- but then again, Google knows what I search for and perhaps deduced an incorrect age from that (I've been watching a very old Western, Maverick, lately, which may have fooled them. So my plan is working!)
3) Google thinks I published with Hilbert (see here or here) so that would make them think I am 68 years old. Hmm, still to young. If I was a 10-year old math genius in 1938 (Hilbert died in 1943 but since I am not a 68 year old math genius I chose numbers to make it easy) and published with
him then, then I would now be 80. Not 68. So that is not the answer.
(Side question- are any of Hilbert's co-authors still alive?)
Seriously, if anyone has any ideas why Google had it wrong, let me now
4) Lance was outraged at this and hence put my birth year on my Wikipedia page thinking that
would fix it. (I was not outraged, just amused.)
5) It was taken off my page since Lance couldn't prove it.
6) Lance and I mentioned my age in a blog post and that was proof enough. So our blog is a primary
source. We should use this sparingly -- with great power comes great responsibility. (See here for more on that theme)
7) Other weird internet stuff: What does it take to get a Wikipedia Page? A Nobel Prize in Physics
helps. See: here.
gasarch
you used to get the following: here
Please go there and notice how old they say I am.
Okay, you are back. You may have noticed that they say I am 68. Gee, I don't feel 68 (I feel younger).
I have no idea how Google got my age wrong.
0) I found about this when I saw my age in an article about the Muffin problem. The article is here. I had been in contact with the author earlier so it was easy to contact him, assure him that I appreciate his throwing scammers and spammers off of my trail by giving me the wrong age, but I wondered why he chose 68. He then apologized (which was not needed) and pointed me to the google thing.
1) My age was not on my Wikipedia page. Nor was my birth year.
2) I do not recall every telling Google my age -- but then again, Google knows what I search for and perhaps deduced an incorrect age from that (I've been watching a very old Western, Maverick, lately, which may have fooled them. So my plan is working!)
3) Google thinks I published with Hilbert (see here or here) so that would make them think I am 68 years old. Hmm, still to young. If I was a 10-year old math genius in 1938 (Hilbert died in 1943 but since I am not a 68 year old math genius I chose numbers to make it easy) and published with
him then, then I would now be 80. Not 68. So that is not the answer.
(Side question- are any of Hilbert's co-authors still alive?)
Seriously, if anyone has any ideas why Google had it wrong, let me now
4) Lance was outraged at this and hence put my birth year on my Wikipedia page thinking that
would fix it. (I was not outraged, just amused.)
5) It was taken off my page since Lance couldn't prove it.
6) Lance and I mentioned my age in a blog post and that was proof enough. So our blog is a primary
source. We should use this sparingly -- with great power comes great responsibility. (See here for more on that theme)
7) Other weird internet stuff: What does it take to get a Wikipedia Page? A Nobel Prize in Physics
helps. See: here.
Monday, October 01, 2018
Muffin Math
Lance: It's Friday afternoon and the Dagstuhl workshop has ended. We have some time before we need take off so how about one final typecast.
Bill: Always a good idea.
Lance: First the exciting news, Nitin Saxena won the Shanti Swarup Bhatnagar prize for 2018,
according to the many Indians at Dagstuhl, the most prestigious science prize in the country. The awards were announced on Wednesday during the workshop. He's the S in AKS.
Bill: That's really impressive. He was only two-years old when AKS had log-depth sorting networks.
Lance: Bill, you moron. You're thinking of Ajtai-Komlós-Szemerédi. I'm talking Agrawal-Kayal-Saxena Primes in P, topic of my second ever blog post. Nitin, an undergrad at that time, didn't just sit on his laurels--he has had awesome results on algebraic circuit complexity that truly justify this prize.
Bill: Well congrats to Nitin. Moving on, let's talk math.
Lance: We're at Dagstuhl so we have to call it computer science.
Bill: Ronen Shaltiel gave a great but depressing talk, Indistinguishability by adaptive procedures with advice, and lower bounds on hardness amplification proofs.
Lance: Nobody sings the Dagstuhl Blues.
Bill: Suppose you had a hard function and want to covert it to a harder function, known in the biz as hardness amplification. For constant depth circuits we have hardness results but no known process for amplification. For larger classes, like constant depth circuits with threshold gates, we do know ways to amplify.
Lance: But we have not hardness results there? Where are you going with this?
Bill: Ronen put it nicely, "We can only amplify hardness where we don't have it". Ronen and his colleagues proved results along those lines. Lance, does that depress you.
Lance: Not as much as the sprained ankle that made me miss that talk. My turn to pick a favorite talk. I loved Michael Forbes Hitting Sets for the Closure of Small Circuits. You take algebraic circuits with a parameter epsilon and take the limit as epsilon goes to zero. Forbes and Amir Shpilka show a PSPACE algorithm to find small sets containing non-zeros of these functions. These kinds of functions are studied in the GCT approach to lower bounds.
Bill: What lower bounds is this aiming to solve?
Lance: Showing the computation difference between the determinant and the permanent.
Josh Alman: You've left out the most exciting part of the conference.
Bill and Lance: So Josh, what was that?
Josh Alman: The world debut debut performance of Stud Muffin and Smilin' Sam singing "Do You Work on Muffin Math?"
Lance: That awesome duo looks familiar Bill. Where I have seen them before?
Bill: That Sam can really tickle the ivories.
Lance: And Stud was definitely in the room.
Bill: On that note, take us out.
Lance: In a complex world, keep it simple.
Bill: Always a good idea.
Lance: First the exciting news, Nitin Saxena won the Shanti Swarup Bhatnagar prize for 2018,
 |
| Nitin Saxena |
Bill: That's really impressive. He was only two-years old when AKS had log-depth sorting networks.
Lance: Bill, you moron. You're thinking of Ajtai-Komlós-Szemerédi. I'm talking Agrawal-Kayal-Saxena Primes in P, topic of my second ever blog post. Nitin, an undergrad at that time, didn't just sit on his laurels--he has had awesome results on algebraic circuit complexity that truly justify this prize.
Bill: Well congrats to Nitin. Moving on, let's talk math.
Lance: We're at Dagstuhl so we have to call it computer science.
Bill: Ronen Shaltiel gave a great but depressing talk, Indistinguishability by adaptive procedures with advice, and lower bounds on hardness amplification proofs.
Lance: Nobody sings the Dagstuhl Blues.
Bill: Suppose you had a hard function and want to covert it to a harder function, known in the biz as hardness amplification. For constant depth circuits we have hardness results but no known process for amplification. For larger classes, like constant depth circuits with threshold gates, we do know ways to amplify.
Lance: But we have not hardness results there? Where are you going with this?
Bill: Ronen put it nicely, "We can only amplify hardness where we don't have it". Ronen and his colleagues proved results along those lines. Lance, does that depress you.
Lance: Not as much as the sprained ankle that made me miss that talk. My turn to pick a favorite talk. I loved Michael Forbes Hitting Sets for the Closure of Small Circuits. You take algebraic circuits with a parameter epsilon and take the limit as epsilon goes to zero. Forbes and Amir Shpilka show a PSPACE algorithm to find small sets containing non-zeros of these functions. These kinds of functions are studied in the GCT approach to lower bounds.
Bill: What lower bounds is this aiming to solve?
Lance: Showing the computation difference between the determinant and the permanent.
Josh Alman: You've left out the most exciting part of the conference.
Bill and Lance: So Josh, what was that?
Josh Alman: The world debut debut performance of Stud Muffin and Smilin' Sam singing "Do You Work on Muffin Math?"
Lance: That awesome duo looks familiar Bill. Where I have seen them before?
Bill: That Sam can really tickle the ivories.
Lance: And Stud was definitely in the room.
Bill: On that note, take us out.
Lance: In a complex world, keep it simple.
Thursday, September 27, 2018
Still Typecasting from Dagstuhl
Lance: Bill, in our typecast earlier this week I said you were older than me. But 68? You don't look day over 66.
Bill: Neither do you. But seriously, why do you think I'm 68?
Lance: I just Google'd "How old is Bill Gasarch?"
Bill: Don't believe everything you read on the Internet. I'm really 58.
Lance: Prove it.
Bill: Here's my driver's license.
Lance: Bill you don't drive. And it literally says "NOT A DRIVER'S LICENSE" on the back. But it is an official State of Maryland Identification card stating that you were born in 1959. Are you saying I should trust the state of Maryland over Google?
Bill: Yes, because they pay my salary. Back to Dagstuhl. Let's talk about the talks. William Hoza gave a nice talk about hitting sets for L (deterministic small space) vs RL (randomized small space) but when I asked him when will we prove L = RL he said not for fifty years. Grad students are not supposed to be that pessimistic.
Lance: You mean realistic. Though I'd guess more like 10-20 years. I wouldn't even be surprised if NL (nondeterministic log space) = L.
Arpita Korwar: I say 10-15 years.
Bill: Can we put that in the blog?
Lance: Too late. Bill I heard you were the stud muffin this week.
Bill: Yes, I talked about the muffin problem. Got a problem with that?
Lance: Needed milk. I saw this talk two years ago and now you have cool theorems. Who would've thought if you have 24 muffins and 11 people you can allocate 24/11 muffins and the smallest piece is 19/44, and that's the best possible for maximizing the smallest piece.
Bill: I can't believe you actually listened to the talk and didn't fall asleep.
Lance: zzzzzz. Did you say something?
Bill: Never mind. Eric Allender talked about the minimum circuit-size problem: Given a truth-table of a function f is there a circuit for f less that a given size w. The problem is frustrated, just consider the following theorem: if MCSP is NP-complete then EXP does not equal ZPP (exponential time in zero-error probabilistic polynomial-time).
Lance: Do you think EXP = ZPP?
Bill: No, the result only tells us it will be hard to prove MSCP is NP-complete without informing us whether or not it is NP-complete. Allender did show that under projections it isn't NP-complete (Editor's Note: I should have said log-time projections see Eric's comment. SAT and all your favorite NP-complete problems are complete under log-time projections). MSCP might be complete under poly-time reductions but not under weaker reductions.
Lance: Reminds me of the Kolmogorov random strings that are hard for the halting for Turing reductions but not under many-one reductions.
Bill: Everything reminds you of the Kolmogorov strings.
Lance: As they should.
Bill: I liked Michal KouckĂ˝'s talk on Gray codes.
Lance: Shouldn't that be grey codes. We're not in the UK.
Bill: It's the color you moron. It's named after Frank Gray.
Lance: You are smarter than you look, not bad for a 68 year old. I missed KouckĂ˝'s talk due to a sports injury, but he did catch me up later.
Bill: I never put Lance and sports in the same sentence before.
Lance: And I never put Bill and driving together. It's a new day for everything. KouckĂ˝ showed how to easily compute the next element in the Gray code querying few bits as long as the alphabet size is of size 3.
Bill: Which contrasts Raskin's 2017 paper that shows with a binary alphabet you need to query at least half the bits.
Lance: Hey you stole my line.
Bill: That's not possible. You are editing this. I think this typecast has gone long enough. Take us out.
Lance: In a complex world, best to keep it simple.
Bill: Neither do you. But seriously, why do you think I'm 68?
Lance: I just Google'd "How old is Bill Gasarch?"
Bill: Don't believe everything you read on the Internet. I'm really 58.
Lance: Prove it.
Bill: Here's my driver's license.
Lance: Bill you don't drive. And it literally says "NOT A DRIVER'S LICENSE" on the back. But it is an official State of Maryland Identification card stating that you were born in 1959. Are you saying I should trust the state of Maryland over Google?
Bill: Yes, because they pay my salary. Back to Dagstuhl. Let's talk about the talks. William Hoza gave a nice talk about hitting sets for L (deterministic small space) vs RL (randomized small space) but when I asked him when will we prove L = RL he said not for fifty years. Grad students are not supposed to be that pessimistic.Lance: You mean realistic. Though I'd guess more like 10-20 years. I wouldn't even be surprised if NL (nondeterministic log space) = L.
Arpita Korwar: I say 10-15 years.
Bill: Can we put that in the blog?
Lance: Too late. Bill I heard you were the stud muffin this week.
Bill: Yes, I talked about the muffin problem. Got a problem with that?
Lance: Needed milk. I saw this talk two years ago and now you have cool theorems. Who would've thought if you have 24 muffins and 11 people you can allocate 24/11 muffins and the smallest piece is 19/44, and that's the best possible for maximizing the smallest piece.
Bill: I can't believe you actually listened to the talk and didn't fall asleep.
Lance: zzzzzz. Did you say something?
Bill: Never mind. Eric Allender talked about the minimum circuit-size problem: Given a truth-table of a function f is there a circuit for f less that a given size w. The problem is frustrated, just consider the following theorem: if MCSP is NP-complete then EXP does not equal ZPP (exponential time in zero-error probabilistic polynomial-time).
Lance: Do you think EXP = ZPP?
Bill: No, the result only tells us it will be hard to prove MSCP is NP-complete without informing us whether or not it is NP-complete. Allender did show that under projections it isn't NP-complete (Editor's Note: I should have said log-time projections see Eric's comment. SAT and all your favorite NP-complete problems are complete under log-time projections). MSCP might be complete under poly-time reductions but not under weaker reductions.
Lance: Reminds me of the Kolmogorov random strings that are hard for the halting for Turing reductions but not under many-one reductions.
Bill: Everything reminds you of the Kolmogorov strings.
Lance: As they should.
Bill: I liked Michal KouckĂ˝'s talk on Gray codes.
Lance: Shouldn't that be grey codes. We're not in the UK.
Bill: It's the color you moron. It's named after Frank Gray.
Lance: You are smarter than you look, not bad for a 68 year old. I missed KouckĂ˝'s talk due to a sports injury, but he did catch me up later.
Bill: I never put Lance and sports in the same sentence before.
Lance: And I never put Bill and driving together. It's a new day for everything. KouckĂ˝ showed how to easily compute the next element in the Gray code querying few bits as long as the alphabet size is of size 3.
Bill: Which contrasts Raskin's 2017 paper that shows with a binary alphabet you need to query at least half the bits.
Lance: Hey you stole my line.
Bill: That's not possible. You are editing this. I think this typecast has gone long enough. Take us out.
Lance: In a complex world, best to keep it simple.
Tuesday, September 25, 2018
Lance and Bill go to Dagstuhl: The Riemann Edition
Lance: Welcome to our typecast directly from Dagstuhl in Southwestern Germany for the 2018 edition of the seminar on Algebraic Methods in Computation Complexity. Say hi Bill.
Bill: Hi Bill. So Lance are you disappointed we didn't go to Heisenberg for the Michael Atiyah talk claiming a solution to the Riemann Hypothesis.
Lance: I knew how fast I was going but I got lost going to Heisenberg. I think you mean the Heidelberg Laureate Forum a 100 miles from here. From what I heard we didn't miss much. For those who care here is the video, some twitter threads and the paper.
Bill: Too bad. When I first heard about the claim I was optimistic because (1) László Babai proved that graph isomorphism is in quasipolynomial-time at the age of 65 and (2) since Atiyah was retired he had all this time to work on it. Imagine Lance if you were retired and didn't have to teach or do administration, could you solve P vs NP? (This gets an LOL from Nutan Limaye)
Lance: I'll be too busy writing the great American novel. Before we leave this topic, don't forget about the rest of the Laureate Forum, loads of great talks from famous mathematicians and computer scientists. Why didn't they invite you Bill?
Bill: They did but I rather be at Dagstuhl with you to hear about lower bounds on matrix multiplication from Josh Alman. Oh, hi Josh I didn't see you there.
Josh: Happy to be here, it's my first Dagstuhl. I'm flying around the world from Boston via China to get here. Though my friends say it's not around the world if you stay in the Northern hemisphere. They are a lot of fun at parties. But not as much fun as matrix multiplication.
Bill: So Josh, what do you have to say about matrix multiplication. Is is quadratic time yet?
Josh: Not yet and we show all the current technique will fail.
Bill: Wouldn't Chris Umans disagree?
Kathryn Fenner: You shouldn't pick on Canadians [Ed note: Josh is from Toronto]. Pick on students from your own country.
Josh: (diplomatically) I think Chris Umans has a broader notion of what counts as known methods. There are some groups that aren't ruled out but we don't know how to use them.
Chris: Very well put. The distinction is between powers of a fixed group versus families of groups like symmetric groups. The later one seems like the best place to look.
Lance: Thanks Chris. Josh, what are your impressions of Dagstuhl so far?
Josh: I like the sun and grass. I wish it was easier to get here.
Lance: This is only the first day. You haven't even found the music room yet, past the white room, past the billiard room where Mr. Green was murdered with the candlestick. Oh hi Fred Green. Luckily Dr. Green is still alive. I remember my first Dagstuhl back in February of 1992.
Josh: Two months before I was born.
Lance: Way to make me feel old.
Bill: You are old.
Lance: You are older. Believe it or not six from that original 1992 meeting are here again this week: The two of us, Eric Allender, Vikaurum Arvind, Uwe Schöning and Jacobo Torán. Amazing how accents show up as we talk.
Bill: What did I sleep through this morning before Josh's talk?
Lance: Amnon Ta-Shma talked about his STOC 2017 best paper and Noga Ron-Zewi showed some new results on constructive list-decoding.
Bill: Let's do this again later in the week. Lance, takes us out.
Lance: In a complex world, best to keep it simple.
Bill: Hi Bill. So Lance are you disappointed we didn't go to Heisenberg for the Michael Atiyah talk claiming a solution to the Riemann Hypothesis.
Lance: I knew how fast I was going but I got lost going to Heisenberg. I think you mean the Heidelberg Laureate Forum a 100 miles from here. From what I heard we didn't miss much. For those who care here is the video, some twitter threads and the paper.
Bill: Too bad. When I first heard about the claim I was optimistic because (1) László Babai proved that graph isomorphism is in quasipolynomial-time at the age of 65 and (2) since Atiyah was retired he had all this time to work on it. Imagine Lance if you were retired and didn't have to teach or do administration, could you solve P vs NP? (This gets an LOL from Nutan Limaye)
Lance: I'll be too busy writing the great American novel. Before we leave this topic, don't forget about the rest of the Laureate Forum, loads of great talks from famous mathematicians and computer scientists. Why didn't they invite you Bill?
Bill: They did but I rather be at Dagstuhl with you to hear about lower bounds on matrix multiplication from Josh Alman. Oh, hi Josh I didn't see you there.
Josh: Happy to be here, it's my first Dagstuhl. I'm flying around the world from Boston via China to get here. Though my friends say it's not around the world if you stay in the Northern hemisphere. They are a lot of fun at parties. But not as much fun as matrix multiplication.
Bill: So Josh, what do you have to say about matrix multiplication. Is is quadratic time yet?
Josh: Not yet and we show all the current technique will fail.
Bill: Wouldn't Chris Umans disagree?
Kathryn Fenner: You shouldn't pick on Canadians [Ed note: Josh is from Toronto]. Pick on students from your own country.
Josh: (diplomatically) I think Chris Umans has a broader notion of what counts as known methods. There are some groups that aren't ruled out but we don't know how to use them.
Chris: Very well put. The distinction is between powers of a fixed group versus families of groups like symmetric groups. The later one seems like the best place to look.
Lance: Thanks Chris. Josh, what are your impressions of Dagstuhl so far?
Josh: I like the sun and grass. I wish it was easier to get here.
Lance: This is only the first day. You haven't even found the music room yet, past the white room, past the billiard room where Mr. Green was murdered with the candlestick. Oh hi Fred Green. Luckily Dr. Green is still alive. I remember my first Dagstuhl back in February of 1992.
Josh: Two months before I was born.
Lance: Way to make me feel old.
Bill: You are old.
Lance: You are older. Believe it or not six from that original 1992 meeting are here again this week: The two of us, Eric Allender, Vikaurum Arvind, Uwe Schöning and Jacobo Torán. Amazing how accents show up as we talk.
Bill: What did I sleep through this morning before Josh's talk?
Lance: Amnon Ta-Shma talked about his STOC 2017 best paper and Noga Ron-Zewi showed some new results on constructive list-decoding.
Bill: Let's do this again later in the week. Lance, takes us out.
Lance: In a complex world, best to keep it simple.
Thursday, September 20, 2018
Why wasn't email built securely?
Recently I talked with Ehsan Hoque, one of the authors of the ACM Future of Computing Academy report that suggested "Peer reviewers should require that papers and proposals rigorously consider all reasonable broader impacts, both positive and negative." which I had satirized last May.
Ehsan said that "if email had sender authentication built in from the beginning then we wouldn't have the phishing problems we have today". Leaving aside whether this statement is fully true, why didn't we put sender authentication and encryption in the first email systems?
Email goes back to the 60's but I did get involved on the early side when I wrote an email system for Cornell in the early 80's. So let me take a crack at answering that question.
Of course there are the technical reasons. RSA was invented just a few years earlier and there were no production systems and the digital signatures needed for authentication were just a theory back then. The amount of overhead needed for encryption in time and bandwidth would have stopped email in its tracks back then.
But it's not like we said we wish we could have added encryption to email if we had the resources. BITNET which Cornell used and the ARPANET gateway only connected with other universities, government agencies and maybe some industrial research labs. We generally trusted each other and didn't expect anyone to fake email for the purpose of getting passwords. It's not like these emails could have links to fake login pages. We had no web back then.
But we did all receive an email from a law firm offering green card help. My first spam message. We had a mild panic but little did we guess that spam would nearly take down email at the turn of the century. Nor would we have guessed the solution would come from machine learning which kills nearly all spam and much of the phishing emails today.
I don't disagree with the report that we shouldn't think about the negative broader impacts, but the true impacts negative and positive are nearly impossible to predict. Computer Science works best when we experiment with ideas, get things working and fix problems as they arise. We can't let the fear of the future prevent us from getting there.
Ehsan said that "if email had sender authentication built in from the beginning then we wouldn't have the phishing problems we have today". Leaving aside whether this statement is fully true, why didn't we put sender authentication and encryption in the first email systems?
Email goes back to the 60's but I did get involved on the early side when I wrote an email system for Cornell in the early 80's. So let me take a crack at answering that question.
Of course there are the technical reasons. RSA was invented just a few years earlier and there were no production systems and the digital signatures needed for authentication were just a theory back then. The amount of overhead needed for encryption in time and bandwidth would have stopped email in its tracks back then.
But it's not like we said we wish we could have added encryption to email if we had the resources. BITNET which Cornell used and the ARPANET gateway only connected with other universities, government agencies and maybe some industrial research labs. We generally trusted each other and didn't expect anyone to fake email for the purpose of getting passwords. It's not like these emails could have links to fake login pages. We had no web back then.
But we did all receive an email from a law firm offering green card help. My first spam message. We had a mild panic but little did we guess that spam would nearly take down email at the turn of the century. Nor would we have guessed the solution would come from machine learning which kills nearly all spam and much of the phishing emails today.
I don't disagree with the report that we shouldn't think about the negative broader impacts, but the true impacts negative and positive are nearly impossible to predict. Computer Science works best when we experiment with ideas, get things working and fix problems as they arise. We can't let the fear of the future prevent us from getting there.
Sunday, September 16, 2018
What is a Physicist? A Mathematician? A Computer Scientist?
Scott Aaronson recently won the Tomassoni-Chisesi Prize in Physics (yeah Scott!).
In his post (here) about it he makes a passing comment:
In his post (here) about it he makes a passing comment:
I'm of course not a physicist
I won't disagree (does that mean I agree? Darn Logic!) but it raises the question of how we identify ourselves. How to answer the question:
Is X a Y?
(We will also consider why we care, if we do.)
Some criteria below. Note that I may say thinks like `Dijkstra is obviously a computer scientist'
but this is cheating since my point is that it may be hard to tell these things (though I think he is).
Is X a Y?
(We will also consider why we care, if we do.)
Some criteria below. Note that I may say thinks like `Dijkstra is obviously a computer scientist'
but this is cheating since my point is that it may be hard to tell these things (though I think he is).
1) If X in a Y-dept then X is a Y. While often true, there are some problems: MIT CS is housed in Mathematics, some people change fields. Readers- if you know someone who is in dept X but really does Y, leave a comment. (CORRECTION- I really don't know how MIT is structured. I do know that the Math Dept has several people who I think of as Computer Scientists: Bonnie Burger, Michael Goemans, Tom Leighton, Peter Shor, Michael Sipser. There may be others as well. The point being that I would not say `Sipers is a mathematician because he is in the MIT Math Dept')
2) If X got their degree in Y then they are Y. Again, people can change fields. Also, some of the older people in our field got degrees in Physics or Math since there was no CS (I am thinking Dijkstra-Physics, Knuth-Math). Even more recently there are cases. Andrew Child's degree is in Physics, but he did quantum computing. Readers- if you know someone who got there degree in X but is now donig Y, leave a comment.
3) Look at X's motivation. If Donald Knuth does hard math but he does it to better analyze algorithms, then he is a computer scientist. One problem -- some people don't know their own motivations, or it can be hard to tell. And people can get distracted into another field.
4) What does X call himself? Of course people can be wrong. The cranks he email me their proofs that R(5) is 40 (its not) think the are mathematicians. They are not- or are they? see next point
5) What X is interested in, ind. of if they are good at it or even know any. Not quite right- if an 8 year old Bill Gasarch is interested in the Ketchup problem that does not make him a mathematician.
6) What X is working on right now. Fine but might change. And some work is hard to classify.
7) If you win an award in X, then you are an X. Some exceptions
Scott is a computer scientist who won the Tomassoni-Chisesi Physics Prize
Ed Witten is a Physicist who won the Fields Medal (Math)
John Nash is a mathematician who won a Nobel prize in Economics.
I want to make a full circle- so if you know other X won a prize in Y then leave a comment and
we'll see what kind of graph we get. Bipartite with people on one side and fields on the other.
8) What they can teach? Helpful in terms of hiring when you want to fill teaching needs.
Does any of this matter? We use terms like `mathematician' `physicist' `computer scientist' as shorthand for what someone is working on, so its good to know we have it right.
2) If X got their degree in Y then they are Y. Again, people can change fields. Also, some of the older people in our field got degrees in Physics or Math since there was no CS (I am thinking Dijkstra-Physics, Knuth-Math). Even more recently there are cases. Andrew Child's degree is in Physics, but he did quantum computing. Readers- if you know someone who got there degree in X but is now donig Y, leave a comment.
3) Look at X's motivation. If Donald Knuth does hard math but he does it to better analyze algorithms, then he is a computer scientist. One problem -- some people don't know their own motivations, or it can be hard to tell. And people can get distracted into another field.
4) What does X call himself? Of course people can be wrong. The cranks he email me their proofs that R(5) is 40 (its not) think the are mathematicians. They are not- or are they? see next point
5) What X is interested in, ind. of if they are good at it or even know any. Not quite right- if an 8 year old Bill Gasarch is interested in the Ketchup problem that does not make him a mathematician.
6) What X is working on right now. Fine but might change. And some work is hard to classify.
7) If you win an award in X, then you are an X. Some exceptions
Scott is a computer scientist who won the Tomassoni-Chisesi Physics Prize
Ed Witten is a Physicist who won the Fields Medal (Math)
John Nash is a mathematician who won a Nobel prize in Economics.
I want to make a full circle- so if you know other X won a prize in Y then leave a comment and
we'll see what kind of graph we get. Bipartite with people on one side and fields on the other.
8) What they can teach? Helpful in terms of hiring when you want to fill teaching needs.
Does any of this matter? We use terms like `mathematician' `physicist' `computer scientist' as shorthand for what someone is working on, so its good to know we have it right.
Thursday, September 13, 2018
P = NP and Cancer
Often when the question comes to what happens if P = NP, one typically hears the response that it kills public-key cryptography. And it does. But that gives the impression that given the choice we would rather not have P = NP. Quite the opposite, P = NP would greatly benefit humanity from solving AI (by finding the smallest circuit consistent with the data) and curing cancer. I've said this before but never explained why.
Of course I don't have a mathematical proof that P = NP cures cancer. Nor would an efficient algorithm for SAT immediately give a cancer cure. But it could work as follows:
Of course I don't have a mathematical proof that P = NP cures cancer. Nor would an efficient algorithm for SAT immediately give a cancer cure. But it could work as follows:
- We need an appropriately shaped protein that would inhibit the cancer cells for a specific individual without harming the healthy cells. P = NP would help find these shapes perhaps just the DNA of the person and the type of cancer.
- At this point we don't understand the process that takes a ACGT protein sequence and describes that shape that it forms. But it must be a simple process because it happens quickly. So we can use P = NP to find a small circuit that describes this process.
- Use P = NP to find the protein sequence that the circuit from #2 will output the shape from #1.
Please note this is just a thought exercise since I strongly believe that P ≠ NP. I do not want to give false hope to those with friends and loved ones with the disease. If you want to cure cancer your first step should not be "Prove P = NP".
Subscribe to:
Posts (Atom)