tag:blogger.com,1999:blog-37222332019-01-17T15:07:23.988-05:00Computational ComplexityComputational Complexity and other fun stuff in math and computer science from Lance Fortnow and Bill GasarchLance Fortnowhttps://plus.google.com/101693130490639305932noreply@blogger.comBlogger2649125tag:blogger.com,1999:blog-3722233.post-85399943272700549732019-01-17T12:45:00.001-05:002019-01-17T12:45:43.150-05:00The Cost of Privacy<table align="center" cellpadding="0" cellspacing="0" class="tr-caption-container" style="margin-left: auto; margin-right: auto; text-align: center;"><tbody>
<tr><td style="text-align: center;"><a href="https://2.bp.blogspot.com/-8HqZkaSkvdw/XD82UgwmqHI/AAAAAAABmMQ/6zYMalG9fXUS5OF28uajL8MOiXo6igmaACLcBGAs/s1600/iphone.jpeg" imageanchor="1" style="margin-left: auto; margin-right: auto;"><img border="0" data-original-height="732" data-original-width="802" height="182" src="https://2.bp.blogspot.com/-8HqZkaSkvdw/XD82UgwmqHI/AAAAAAABmMQ/6zYMalG9fXUS5OF28uajL8MOiXo6igmaACLcBGAs/s200/iphone.jpeg" width="200" /></a></td></tr>
<tr><td class="tr-caption" style="text-align: center;">Billboard at 2019 CES</td></tr>
</tbody></table>
<br />Computer scientists tend to obsess about privacy and we've had a privacy/security debate for decades now. But now machine learning has really given us a whole new spin on what privacy protects and takes away.<br />
<div>
<br />
I take an open approach and basically allow Google to know everything about my life. Google knows where I've been--sometimes my Pixel asks me which store in a shopping center I visited and I give up that info. Google knows who I communicate with, what websites I visit, what music and movies I listen to and watch, all my photos, what temperature makes me comfortable and so on.<br />
<br />
What do I get? A Google ecosystem that knows me sometimes better than I know myself. Google works best when it learns and integrates. I get asked to download maps for trips Google knows I'm about to take. I have Google assistant throughout my house, in my phone, in my car and it tailor answers and sometimes even the questions that I need answers to. If anything I wish there was further integration, like Google Voice should ring my office phone only when I'm in the office.<br />
<br />
Georgia Tech now forces us to use Microsoft Exchange for email. Outlook is not a bad email program but its capabilities, especially for search, does not work as well and think of all that unused knowledge.<br />
<br />
I trust Google to keep my information safe, with a random password and 2-factor encryption and even if someone would manage to break in they would find I'm a pretty boring person with an unhealthy obsession of opera (the musical form not the browser).<br />
<br />
Doesn't work for everyone and companies should make it easy to keep your info secure. But I say go use your machine learning on me and find ways to make my life easier and more fun, and sure send me some targeted ads as payment. The Internets will find a way to discover you anyway, might as well take advantage. </div>
Lance Fortnowhttps://plus.google.com/101693130490639305932noreply@blogger.com1tag:blogger.com,1999:blog-3722233.post-48069660946837911662019-01-15T11:21:00.000-05:002019-01-15T18:27:17.378-05:00do we ever only care about the decision problem? I know of only one case of that(I had been thinking of this for a post then Lance's post on <a href="https://blog.computationalcomplexity.org/2019/01/search-versus-decision.html">search versus decision</a> inspired me to write up these thoughts.)<br />
<br />
When teaching NP-completeness we often say<br />
<br />
<i>The problem we really care about is, for example, given a weighted graph and two vertices s and t, find the optimal way to go from s to t while hitting every node. But its cleaner mathematically to look at the decision problem:</i><br />
<i><br /></i>
<i>{ (G,s,t,C) : there is a Ham Path from s to t that costs \le C }</i><br />
<i><br /></i>
<i>The search and decision are poly time equivalent, so its fine to just look at the decision. Indeed- if our interest in in lower bounds then clearly if Decision is hard then Find is Hard.</i><br />
<br />
But here are some questions about search vs decision in general, not just with regard to P vs NP.<br />
<br />
1) Is there ever a case where the real world actually cares about the decision version? I can think of just one- given a number is it PRIME is used in Crypto. The real world does not need the witness that its prime (or similar). They just want a prime. Any other cases?<br />
<br />
2) How far apart can search and decision be? NP-decision and NP-search they are poly equivalent. In other domains can they be very far apart? For example, is FINDING a k-clique or k-ind set in a graph on 2^{2k} vertices require roughly n^k steps (go through all k-sets) or can we do much better? I suspect this is unknown but would be delighted if a commenter tells me otherwise.<br />
<br />
<br />GASARCHhttp://www.blogger.com/profile/03615736448441925334noreply@blogger.com8tag:blogger.com,1999:blog-3722233.post-27278984935870293412019-01-09T08:10:00.000-05:002019-01-09T16:43:30.052-05:00Search versus DecisionShockingly I've never done a post on search versus decision, one of the more interesting dualities in complexity. In short: Decision: Is there a needle in the haystack? Search: Find the needle.<br />
<br />
In Satisfiability, or any other NP-complete problem, the two problems are essentially equivalent. If you can decided SAT you can find a solution (good homework problem) or even the best solution. Often people mix up the two, where people say finding the shortest Traveling Salesman Tour is NP-complete, <a href="https://blog.computationalcomplexity.org/2014/01/is-traveling-salesman-np-complete.html">usually</a> without getting into too much trouble.<br />
<br />
Decision is always at least as easy as search: If you have a solution you know there is one. What about the other direction? We can't actually prove search is hard without separating P and NP, but we have our conjectures.<br />
<br />
Sometimes both are easy. We can easily find the maximum weighted matching.<br />
<br />
Sometimes decision is easy and search is supposedly hard: Composite Numbers. The search version is factoring.<br />
<br />
Sometimes decision is trivial (i.e. they always exist) and search is still hard. Nash Equilibria. <a href="https://blog.computationalcomplexity.org/2006/05/dispersing-ramsey-graphs.html">Ramsey Graphs</a>.<br />
<br />
Often we ask whether search reduces to decision? If you have some oracle (magic black box) that answered decision questions, can you solve the search problem efficiently? SAT has this property, as does Matching (for trivial reasons). Nash Equilibrium and Composite Numbers likely don't.<br />
<br />
Graph Isomorphism does, i.e., given an oracle for graph isomorphism you can find the isomorphism (another good homework problem).<br />
<br />
There's also an interesting non-adaptive version. Given a SAT formula can you find an assignment with questions to a SAT oracle that all have to be asked at the same time?<br />
<br />
Here we get a probable yes. If the formula has one solution you can find it by asking for each bit of the solution. <a href="https://blog.computationalcomplexity.org/2006/09/favorite-theorems-unique-witnesses.html">Randomly you can reduce SAT to several formulas</a>, one of which is likely to have a single assignment that is also an assignment of the original formula. With standard hardness assumptions <a href="https://blog.computationalcomplexity.org/2006/07/full-derandomization.html">you can eliminate the randomness</a>.<br />
<br />
Is the same true for graph isomorphism? I think that's still open.Lance Fortnowhttps://plus.google.com/101693130490639305932noreply@blogger.com6tag:blogger.com,1999:blog-3722233.post-43550056253605099622019-01-06T16:35:00.000-05:002019-01-06T16:50:02.401-05:00When is a kilogram not a kilogram?A long long time ago the standards for meter's, kilograms, etc was an actual physical object.<br />
<br />
Those days are long gone of course. For example, the meter is defined is the length of the path traveled by light in 1/299,792,458 th of a second. Why such an odd number (can fractions be odd?)? Because they retrofitted it to what that the meter is. Rather than go to France and compare my stick to the one under a glass case I can just measure the speed of light. Oh. That sounds hard!<br />
<br />
It matters a bit since the weight of what was the standard kilogram did increase over time, though of course not by much. When did the measurements for stuff STOP being based on physical objects and was all done based on constants of the universe?<br />
<br />
The answer surprised me:<br />
<br />
On Nov 16, 2018 (yes, you read that light) they decided that by May 20, 2019, the Kilogram will be defined in terms of Plank's constant. I have not been able to find out how they will use Plank, maybe they don't know yet (they do and its known -- see the first comment) .With that, there are no more standards based on physical objects. Read about it <a href="https://www.wired.com/story/new-kilogram-definition-based-on-planck-constant/">here</a>.<br />
<br />
Why did it take so long? I honestly don't know and I am tossing that question out to my readers. You can leave serious or funny answers, and best if I can't tell which is which!<br />
<br />
<br />
<br />
<br />GASARCHhttp://www.blogger.com/profile/03615736448441925334noreply@blogger.com7tag:blogger.com,1999:blog-3722233.post-30279873989284285782019-01-03T00:04:00.000-05:002019-01-03T12:16:50.805-05:00Today is Thirdsday! Enjoy it while you can!Fellow Blogger James Propp has come up with a new Math holiday:<br />
<br />
<b>Thirsdsday!</b><br />
<br />
The day is Jan 3 (1-3 in America, though 3-1 in ... Everywhere else?) but only when Jan 3 is a Thursday.<br />
<br />
It is a day where we celebrate the magic of the number 1/3.<br />
<br />
0) For other math days to celebrate see <a href="https://stemjobs.com/math-holidays/">here</a><br />
<br />
1/3) James Propp's blog about Thirdsday on Monday Dec 31. Really ??? : <a href="https://mathenchant.wordpress.com/2018/12/31/introducing-thirdsday/#more-2632">here</a><br />
<br />
2/3) Evelyn Lamb blogged about Thirdsday on Tuesday Jan 1. Really ??? : <a href="https://blogs.scientificamerican.com/roots-of-unity/how-to-celebrate-thirdsday/">here</a><br />
<br />
3/3) Ben Orlin blogged about Thirsdsday on Wedensday Jan 2. Really??? <a href="https://mathwithbaddrawings.com/2019/01/02/thirdsday-the-holiday-thats-33-33-better-than-any-other/">here</a><br />
<br />
(Added ON Thirdsday: Matt Foreman has a video about Thirdsday: <a href="https://www.youtube.com/watch?v=NinrTW1Bx2Y&feature=youtu.be">here</a> and a blog post <a href="https://www.think-maths.co.uk/celebrating-thirdsday">here</a>)<br />
<br />
How come I'm the only one blogged about Thirdsday on Thursday Jan 3 ??? (Added later- not quite true anymore, Matt Foreman also waited until Thirdsday to post on Thirdsday).<br />
I asked Jim Propp about this. He said that he want to help prepare teachers and other eduators for the excitment of Thirdsday! If they already know the wonders of 1/3 they can prepare and lecture on it! Kudos to him! I assume that Evelyn and Ben are similar! Kudos to them! And Ben blogged ON Thirdsday so Kudos to him!<br />
<br />
2) Darling asked me `<i>is it a real day like Pi-Day?'</i> Is Pi-Day real? Is any Holiday real? All holidays are made up until they are accepted and become real. The distinction between <i>real holidays</i> and <i>made up holidays</i> is ... nonexistent. One can talk of <i>accepted </i>and <i>not-accepted</i> holidays. How long did Pi-day take to be accepted? This is prob not a well defined question.<br />
<br />
3) James Propp's and Evelyn Lamb's blog has many math properties of 1/3. One educational property: I think it is the first number that students see that is an infinite decimal. My favorite unbiased use of 1/3: The Cantor Set: Uncountable subset of [0,1] that has measure 0. Really!!! My favorite biased use: its important in Muffin Math. If m>s and you want to divide and distribute m muffins to s students, there is always a way to do this with smallest piece at least 1/3. (Usually you can do better but this is sometimes the best you can do.)<br />
<br />
4) When will the next Thirdsday come?<br />
<br />
2019: Jan 3 is a Thursday, so YES<br />
<br />
2020: Jan 3 is a Friday, so NO<br />
<br />
2021: Jan 3 is a Sunday (why no Saturday? Leap year. Great- it will come sooner!) so NO<br />
<br />
2022: Jan 3 is a Monday, so NO<br />
<br />
2023: Jan 3 is a Tuesday so NO<br />
<br />
2024: Jan 3 is a Wednesday so NO<br />
<br />
2025: Jan 3 is a Friday. WHAT! Why no Thirdsday? Darn leap year! So NO.<br />
<br />
2026: Jan 3 is a Saturday, so NO<br />
<br />
2027: Jan 3 is a Sunday so NO<br />
<br />
2028: Jan 3 is a Monday so NO<br />
<br />
2029: Jan 3 is a Wedensday (Why no Tuesday? Leap year), so NO<br />
<br />
2030: Jan 3 is a Thursday (Leap Year helped!), so YES FINALLY!<br />
<br />
(Exercise: find a formula: if 2019 was the first Thirdsday, find the year for TD(i), the ith Thirdsday.)<br />
<br />
So enjoy Thirdsday in 2019 when spellcheck still flags it.<br />
<br />
In 2030 it will be an accepted holiday and spellcheck will think it's fine.<br />
<br />
<br />
<br />
<br />
<br />
<br />
<br />
<br />
<br />
<br />GASARCHhttp://www.blogger.com/profile/03615736448441925334noreply@blogger.com3tag:blogger.com,1999:blog-3722233.post-21879084416510736962018-12-31T07:25:00.000-05:002018-12-31T07:25:47.068-05:00Complexity Year in Review 2018Result of the year goes to<br />
<blockquote class="tr_bq" style="text-align: center;">
<a href="https://eccc.weizmann.ac.il/report/2018/107/">Oracle Separation of BQP and PH</a> by Ran Raz and Avishay Tal</blockquote>
<div style="text-align: left;">
which we <a href="https://blog.computationalcomplexity.org/2018/06/bqp-not-in-polynomial-time-hierarchy-in.html">wrote about in June</a>. This work solves one of the original open questions in quantum complexity using tools from both quantum and classical circuit complexity. How often do we see oracle results with popular articles in <a href="https://www.quantamagazine.org/finally-a-problem-that-only-quantum-computers-will-ever-be-able-to-solve-20180621/">Quanta</a> (ignore the hyperbolic title), <a href="https://www.thehindu.com/sci-tech/science/quantum-computers-have-an-edge-over-classical-ones-says-the-oracle/article24420375.ece">The Hindu</a> and <a href="https://cacm.acm.org/magazines/2019/1/233514-quantum-leap/fulltext">CACM</a>?</div>
<div style="text-align: left;">
<br /></div>
<div style="text-align: left;">
Runner up goes to the <a href="https://eccc.weizmann.ac.il/report/2018/006/">solution</a> of the 2-to-2 Games Conjecture by Subhash Khot, Dor Minzer and Muli Safra early in 2018. Boaz Barak gave a nice <a href="https://windowsontheory.org/2018/01/10/unique-games-conjecture-halfway-there/">two</a> <a href="https://windowsontheory.org/2018/02/26/on-the-recent-proof-of-the-2-to-2-conjecture/">post</a> overview.</div>
<div style="text-align: left;">
<br /></div>
<div style="text-align: left;">
In last year's <a href="https://blog.computationalcomplexity.org/2017/12/complexity-year-in-review-2017.html">review</a> we talked about the magical breakthroughs of machine learning. This year we seemed to have moved beyond the magic to where machine learning has become a thing. We see the immense value of data and continue to struggle with the ethical challenges of collecting and acting on data, dominance of the big tech companies, training all these students who want to gain expertise in the area and trying to understand why ML works as well as it does. </div>
<div style="text-align: left;">
<br />
The big X-factor is <a href="https://blog.computationalcomplexity.org/2018/10/a-new-cold-war.html">China</a>. Will competition with China spur science literacy and funding in the US like the cold war with the Soviets did? Or will isolation with China limit scientific collaboration like the cold war with the Soviets did? </div>
<div style="text-align: left;">
<br />
The big tech surprise was the rise of electric scooters. Georgia Tech has embraced them and it is a quick way to get around campus.<br />
<br />
Some of the other questions I asked last year didn't have interesting answers: What will the Internet look like post-net neutrality? (too early to tell) How will the new tax code play out? (too early to tell) Where will Amazon put HQ2? (New York and DC--only surprise was picking two cities) What can quantum computers with 50 qbits accomplish? (still a good question) Will bitcoin move to $300K or 30 cents? (it dropped but still has real value)<br />
<br />
Thanks to our guest posters <a href="https://blog.computationalcomplexity.org/2018/10/a-new-aco-center-guest-post-by-vijay.html">Vijay Vazirani</a>, <a href="https://blog.computationalcomplexity.org/2018/12/guest-post-join-sigact.html">Samir Khuller and Robert Kleinberg</a>, and <a href="https://blog.computationalcomplexity.org/2018/09/the-tenure-system-is-broken-but-not-in.html">anonymous</a>.</div>
<div style="text-align: left;">
<br /></div>
<div style="text-align: left;">
We remember <a href="https://terrytao.wordpress.com/2018/12/29/jean-bourgain/">Jean Bourgain</a>, <a href="https://blog.computationalcomplexity.org/2018/12/remembering-george-h-w-bush.html">George H. W. Bush</a>, <a href="https://www.tehrantimes.com/news/431247/Iranian-scientist-Babak-Farzad-dies-of-terminal-cancer">Babak Farzad</a>, <a href="https://blog.computationalcomplexity.org/2018/03/stephen-hawking-1942-2018.html">Stephen Hawking</a>, <a href="https://blog.computationalcomplexity.org/2018/12/ker-i-ko-1950-2018.html">Ker-I Ko</a> and Stan Lee.</div>
<div style="text-align: left;">
<br /></div>
<div style="text-align: left;">
We end the year with craziness, the stock market is going through wild gyrations, we have a partial government shutdown including all of NSF and an uncertain political landscape with different parties leading the two houses of congress. We're still in the midst of a technological revolution and governments around the world try to figure how to regulate it. I find it hard to predict 2019 but it will not be quiet.</div>
Lance Fortnowhttps://plus.google.com/101693130490639305932noreply@blogger.com0tag:blogger.com,1999:blog-3722233.post-72788870120312758052018-12-26T08:31:00.002-05:002018-12-27T12:07:50.339-05:00Ker-I Ko (1950-2018)<div class="separator" style="clear: both; text-align: center;">
<a href="https://4.bp.blogspot.com/-WnVnzZNnJH8/XB6H3HQ9MdI/AAAAAAABlvo/-h_Y6N7q7Ls93g-5KRqxY2c7Bv_laZ-1gCLcBGAs/s1600/Ko.jpg" imageanchor="1" style="clear: left; float: left; margin-bottom: 1em; margin-right: 1em;"><img border="0" data-original-height="174" data-original-width="140" height="200" src="https://4.bp.blogspot.com/-WnVnzZNnJH8/XB6H3HQ9MdI/AAAAAAABlvo/-h_Y6N7q7Ls93g-5KRqxY2c7Bv_laZ-1gCLcBGAs/s200/Ko.jpg" width="160" /></a></div>
A few weeks ago as Bill and I prepared for our upcoming year in review post, we noted that we hadn't lost any theoretical computer scientists this year, at least none that we were aware of. Unfortunately we didn't make it through all of 2018 unscathed.<br />
<br />
Computational complexity theorist Ker-I Ko passed away peacefully from lung failure on December 13. <a href="https://people.cs.nctu.edu.tw/~kyko/" target="_blank">Ker-I Ko</a> spent most of his career at Stonybrook where he had recently retired to take on a professorship at National Chiao Tung University in Taiwan.<br />
<br />
I had only had a few brief meetings with Ko but I knew his work quite well. In his <a href="https://doi.org/10.1137/0218027" target="_blank">best known work</a>, Ko, in a solo paper, created an infinite series of oracles A<sub>1</sub>, A<sub>2</sub>, … such that relative to A<sub>k</sub>, the <a href="https://blog.computationalcomplexity.org/2005/06/favorite-theorems-polynomial-time.html" target="_blank">polynomial-time hierarchy</a> collapses to exactly the kth level, that is Σ<sub>k-1</sub> ≠ Σ<sub>k</sub> = Σ<sub>k+1</sub> = PH. Ko wielded the <a href="https://en.wikipedia.org/wiki/Switching_lemma" target="_blank">switching lemma</a> like a scalpel, pulling part the k-1st and kth levels while leaving enough room to encode the k+1st level. He actually gives two sets of oracles, one which collapses PH to PSPACE while collapsing the hierarchy to the kth level and one that separates PH from PSPACE. Even his oracle showing P=NP≠PSPACE wasn't trivial and I used it as <a href="https://blog.computationalcomplexity.org/2009/05/oracle-results-are-good-for-you.html" target="_blank">an example</a> of a hard to settle complexity question.<br />
<br />
Ko, with Tim Long and Ding-Zhu Du, <a href="https://doi.org/10.1016/0304-3975(86)90152-0" target="_blank">showed that</a> if P ≠ UP if and only if there exist two sets that were one-to-one length-increasing polynomial-time reducible to each other but not polynomial-time isomorphic. This paper played a large role in helping us understand the <a href="https://blog.computationalcomplexity.org/2003/03/berman-hartmanis-isomorphism.html" target="_blank">isomorphism conjecture</a>.<br />
<br />
Ko, with Pekka Orponen, Uwe Schöning and Osamu Watanabe, used Kolmogorov complexity to <a href="https://doi.org/10.1007/3-540-16486-3_99" target="_blank">measure the complexity of an instance of a problem</a>. The instance complexity of x in a set A is the smallest program that will correctly answer whether x is in A, and will not give an incorrect answer for any other y in A, though it can answer "I don't know" for y ≠ x.<br />
<br />
Ko also had several papers on complexity of real-valued functions and wrote several textbooks and manuscripts. A big loss for all of us in the complexity world.Lance Fortnowhttps://plus.google.com/101693130490639305932noreply@blogger.com6tag:blogger.com,1999:blog-3722233.post-23491020100556772432018-12-16T16:24:00.000-05:002018-12-16T16:24:54.857-05:00Guest post: Join SIGACT!This is a guest post by Samir Khuller and Robert Kleinberg.<br />
<br />
Dear friends,<br />
<br />
As our research community continues to grow and thrive, SIGACT membership has not grown apace. We respectfully urge you to join SIGACT! Membership is very cheap (and does not require ACM membership) – only $15 a year – and by joining you will be lending your support to the many activities that SIGACT undertakes on behalf of the theoretical computer science research community. These include:<br />
<br />
<ul>
<li>sponsoring STOC and other theory conferences such as SPAA and PODC, as well as co-sponsoring SODA;</li>
<li>awards such as the Knuth, Gödel, and Kanellakis Prizes, the SIGACT Distinguished Service Award, and the best student paper awards at STOC and SODA;</li>
<li>supporting the Women in Theory workshop;</li>
<li>representing the theoretical computer science community to the ACM and beyond.</li>
</ul>
<br />
In addition to these community benefits, membership comes with individual benefits including voting rights in SIGACT elections, reduced rate for membership in EATCS, reduced conference registration rates at SIGACT-sponsored conferences, access to SIGACT News and announcements sent on the SIGACT email list.<br />
<br />
SIG membership does not automatically renew when you renew your ACM membership, and we suspect this may be one reason for the decline in SIGACT membership. So the next time you renew your ACM membership, remember to also join SIGACT or renew your SIG membership! Better yet, why wait? If you’re not a SIGACT member, join right now- you can use this link: <a href="https://www.acm.org/special-interest-groups/join">here</a><br />
<br />
Please do your part to nurture this important resource for our community.<br />
<br />
Respectfully,<br />
<br />
The SIGACT Executive CommitteeGASARCHhttp://www.blogger.com/profile/03615736448441925334noreply@blogger.com0tag:blogger.com,1999:blog-3722233.post-25364674459964251702018-12-13T09:53:00.000-05:002018-12-22T11:21:22.229-05:00Inverting Onto FunctionsHere's an open question that goes back to a <a href="https://doi.org/10.1016/S0890-5401(03)00119-6">2003 paper</a> that I wrote with Steve Fenner, John Rogers and Ashish Naik. The <a href="https://doi.org/10.1109/CCC.1996.507683">conference paper</a> goes back to 1996.<br />
<br />
In that paper we discuss two hypothesis we badly called Q and Q' and it still remains open whether the two hypotheses are equivalent.<br />
<br />
Q has a number of equivalent definitions, including<br />
<br />
<ul>
<li>For all NP machines M that accepting all strings, there is polynomial-time computable function f such that f(x) is an accepting path of M(x) for all x.</li>
<li>For every onto honest polynomial-time computable function g there is a polynomial-time computable function f such that f finds an inverse of g, more precisely g(f(g(x))) = g(x) for all x.</li>
<li><a href="https://en.wikipedia.org/wiki/TFNP">TFNP</a> is computable in FP.</li>
</ul>
<div>
For lots more equivalences see <a href="https://lance.fortnow.com/papers/files/q.pdf">the paper</a>. </div>
<div>
<br /></div>
<div>
Q' is the bit version of Q. For example</div>
<br />
<ul>
<li>For all NP machines M that accepting all strings, there is polynomial-time computable function f such that f(x) outputs the first bit of an accepting path of M(x) for all x.</li>
<li>For every onto honest polynomial-time computable function g there is a polynomial-time computable function f such that f finds the first bit of an inverse of g, more precisely for all x there is a y such that g(y) = x and f(x) is the first bit of y.</li>
</ul>
<div>
Now Q implies Q', if you can find an accepting path of M(x) you can just read off the first bit. Does Q' imply Q? </div>
<div>
<br /></div>
<div>
If P = NP you can find solutions using self-reductions. For Q' self-reduction gets stuck because as you start filling in bits you may lose the "onto" promise. </div>
<div>
<br /></div>
<div>
On the other hand we don't even know any relativized worlds where Q' is true and Q is false. So either prove that Q' implies Q or show a relativized world where Q' is true and Q is false.</div>
<div>
<br /></div>
<div>
How often can I dole out 22-year old open problems that don't require deep complexity to understand. Can't promise what techniques you'll need to solve it.</div>
Lance Fortnowhttps://plus.google.com/101693130490639305932noreply@blogger.com9tag:blogger.com,1999:blog-3722233.post-30602887920371643482018-12-10T00:42:00.000-05:002018-12-12T20:47:56.511-05:00Super Asymmetry on The Big Bang Theory: How Realistic?The TV show <b>The Big Bang Theory</b> portrays academia so I am naturally curious how realistic it is. I have posted about this before (see <a href="https://blog.computationalcomplexity.org/2014/04/the-big-bang-theory-hits-close-to-home.html">here</a>) in the context of whether actual things they say about physics are true. Today I post about a recent arc where Amy and Sheldon are working on Super asymmetry.<br />
<br />
<br />
SPOILER ALERT<br />
<br />
1) The name: Super Asymmetry. Its not a field but it could be. I assume its about particle physics but I'm not sure they ever say this. A fine name!<br />
<br />
2) Amy is a neurobiologist (this was flagged as not being word, but I think it is) working with Sheldon on a physical theory that I would assume requires hard math. Physics is hard! So I wonder how realistic this is. Actually, more important than being hard is that you need a lot of background knowledge. So the questions of interest is: Can an amateur still help in a discovery of a new physical theory? This may depend on the definitions of <b>amateur, discovery, new, and physical.</b> Alone I would doubt it. But with help from Sheldon, I can believe it. Still, making new discoveries in an old field is hard.<br />
<br />
3) Amy and Sheldon first had the idea for super asymmetry on their honeymoon. Most married couples have other things to do on their honeymoon. (I did ask my darling to prove the primes were infinite on our wedding day before I married her. She was nervous so couldn't do it, but normally she could. I know a mathematician who made her spouse memorize the definition of a Banach Space before they got married, and recite it to her on their wedding day before they got married.)<br />
<br />
4) After they do most of the work they THEN go track down references. This seems stupid but not unrealistic. You can get excited about a theory and work on it at breakneck speed and not want to slow down to check references. But see next point.<br />
<br />
5) Sheldon was counting on this for a Nobel Prize. I would think you would check refs before even thinking in those terms.<br />
<br />
6) An article in Russian was found that proved the theory could not work. There are a few things wrong with this:<br />
<br />
a) The article used the exact same phrase ``Super Asymmetry'' - that seems unlikely.<br />
<br />
b) They seemed to not READ the article, just the first page, and then say. DARN, all that work down the tubes.<br />
<br />
c) They seemed to not even try to say `OKAY, they did BLAH, we did BLAH BLAH, how do they compare and contrast' (ADDED LATER- I just saw the episode afterwards. They probably DO have something after all. They should have listened to my advice before going into a funk.)<br />
<br />
d) If they did all of that work I am sure SOMETHING can be recovered from it.<br />
<br />
7) This is not really a post about The Big Bang Theory. I want to know more about your experiences with research: have you worked on a problem and found out it didn't work or was already done, or something like that. And what happened?<br />
<br />
<br />GASARCHhttp://www.blogger.com/profile/03615736448441925334noreply@blogger.com6tag:blogger.com,1999:blog-3722233.post-20558265192626374932018-12-05T09:03:00.000-05:002018-12-05T09:03:18.760-05:00Remembering George H. W. Bush<div class="separator" style="clear: both; text-align: center;">
<a href="https://upload.wikimedia.org/wikipedia/commons/e/e8/George_H._W._Bush%2C_Vice_President_of_the_United_States%2C_official_portrait.jpg" imageanchor="1" style="clear: left; float: left; margin-bottom: 1em; margin-right: 1em;"><img border="0" data-original-height="800" data-original-width="636" height="200" src="https://upload.wikimedia.org/wikipedia/commons/e/e8/George_H._W._Bush%2C_Vice_President_of_the_United_States%2C_official_portrait.jpg" width="158" /></a></div>
Today is the national day of mourning for George Herbert Walker Bush, one of the best presidents for <a href="https://twitter.com/FYIscipolicy/status/1068867105867644928">science and computing</a>. He created PCAST, the President's Council of Advisors on Science and Technology. Bush signed the <a href="https://en.wikipedia.org/wiki/High_Performance_Computing_Act_of_1991">High Performance Computing Act</a> (introduced by Al Gore), that powered computing research and the Internet through the massive growth of the 90's. His administration started the Human Genome Project and the US Global Change Research Program. He appointed the first and so far only <a href="https://www.nsf.gov/about/history/bios/wemassey.jsp">African-American NSF Director</a>.<br />
<br />
Bush also started the the short-lived Presidential Faculty Fellows program. As a member of the first class of fellows I got invited to a ceremony in the Rose Garden in June of 1992. I didn't actually get to shake hands with President Bush; in that busy election year we had a joint ceremony with some high school award winners and the National Medal of Technology <a href="https://www.uspto.gov/learning-and-resources/ip-programs-and-awards/national-medal-technology-and-innovation/recipients/1992">recipients</a> that included Bill Gates and Joseph Woodland, who invented the bar code scanner used at supermarkets. George Bush famously <a href="https://www.nytimes.com/1992/02/05/us/bush-encounters-the-supermarket-amazed.html">may</a> or <a href="https://www.snopes.com/fact-check/bush-scanner-demonstration/">may not</a> have been amazed by this technology a few months earlier at a grocers convention and had no issues joking about it when introducing Woodland.<br />
<br />
Sipping lemonade on the White House lawn is not an experience one soon forgets. And I guess I haven't twenty-six years later. Thanks President Bush and God speed.<br />
<br />
<br />Lance Fortnowhttps://plus.google.com/101693130490639305932noreply@blogger.com1tag:blogger.com,1999:blog-3722233.post-9343978322026196452018-12-02T16:28:00.001-05:002018-12-04T13:07:26.016-05:00George HW Bush passed away- some non-partisan math commentsGeorge HW Bush passed away recently. When he was alive there were 5 living ex presidents. Now there are 4. What is the max and min number of ex presidents? This we will answer. What is the prob of having many living ex-presidents?<br />
<br />
What is the max number of ex-presidents alive at the same time? List the times this has happened. Your answer should be a list of statements of the following form:<br />
<br />
Shortly after X took office there were Y ex-presidents: Z(1), Z(2), ... , Z(Y).<br />
<br />
I leave a little white space in case you want to try to figure it out, though the point of this post is not to quiz you.<br />
<br />
<br />
<br />
<br />
<br />
<br />
<br />
<br />
<br />
<br />
<br />
<br />
<br />
<br />
<br />
<br />
ANSWER: The max number of ex-presidents alive at the<br />
same time is five. This has happened four times.<br />
<br />
--------------------------------------------<br />
ONE: In 1861 just after Lincoln took office there were five living ex-presidents:<br />
Martin van Buren (died in 1862), John Tyler (died in 1862), Millard Fillmore (died in 1874), Franklin Pierce (died in 1869), James Buchanan (died in 1868).<br />
<br />
Key factors: (1) Between 1836 and 1860 there were no 2-term presidents, (2) Martin van Buren lived a long time after being president.<br />
<br />
TWO: In 1993 just after Clinton took office there were five living ex-presidents:<br />
Richard M. Nixon (died in 1994), Gerald Ford (died in 2006), Jimmy Carter (still alive as of Dec 2018), Ronald Reagan (died in 2004), George HW Bush (died in 2018).<br />
<br />
Key factors: (1) Nixon, Ford, Carter, Bush Sr were the equivalent of 4 one-terms, and (2) Reagan lived a long time after being president.<br />
<br />
THREE: In 2001 just after George W. Bush took office there were five living ex-presidents:<br />
Gerald Ford (died in 2006), Jimmy Carter (still alive as of Dec 2018), Ronald Reagan (died in 2004), George Bush (died in 2018). Bill Clinton (still alive as of Dec 2018).<br />
<br />
Key factors: (1) Ford, Carter, Bush Sr. were effectively 3 one-terms, and (2) Reagan lived a long time after being president.<br />
<br />
FOUR: In 2017 just after Donald Trump took office there were five living ex-presidents:<br />
Jimmy Carter (still alive as of Dec 2018), George HW Bush (died in 2018). Bill Clinton (still alive as of Dec 2018). George W Bush (still alive as of Dec 2018). Barack Obama (still alive as of Dec 2018).<br />
<div>
<br /></div>
Key factors: (1) Carter, Bush were both one-termers, (2) Clinton and W are relatively young for presidents and in good health, and (3) Carter and Bush Sr. lived a long time (Carter is still living!)<br />
<br />
------------------------------------<br />
<br />
I want to see this record broken! I want to see 6 living ex presidents! (Darling asks why I want to see that. Its a good question which I will partially address later.) Hence I want to see Donald Trump impeached or resign or leave office! I was hoping it would would happen before one of Carter, Bush Sr, Clinton, W, Obama died. Oh well.<br />
<br />
So now what? Is it possible that we will see 6 living ex-presidents in our lifetime. Factors: prez longevity, prez age, one-term vs two-term, and since I am asking about in OUR lifetime, our longevity.<br />
<br />
Lets assume that neither The Donald nor any other president resigns or gets impeached or leaves office before their term is up. We assume that the presidents after Trump are Alice, Bob, Carol.<br />
<br />
<b>Scenarios:</b><br />
<br />
ONE: Donald Trump loses to Alice in 2020, Alice loses to Bob in 2024. None of the ex presidents dies before 2025. Then we would have, in the first day of the Bob presidency, which would be in 2025, 6 living ex presidents: Carter, Clinton, W, Obama, Trump, Alice.<br />
<br />
This needs Carter to live to be about 100 (the others are much younger). Possible!<br />
<br />
TWO: Donald Trump loses to Alice in 2020, Alice loses to Bob in 2024 . Bob loses to Carol in 2028. Carter passes away before 2025 but the other ex presidents are alive in 2029. Then we would have, in the first day of the Carol presidency, which would be in 2029, 6 living ex presidents:Clinton, W, Obama, Trump, Alice, Bob.<br />
<div>
<br /></div>
<br />
This needs W, Clinton, Trump to live to be about 83 and Obama to live to be 72. Possible!<br />
<br />
I'll stop here, but you can make up your own SCENARIO THREE which requires some people to live to 87.<br />
<br />
Scenario ONE seems unlikely. TWO and THREE are plausible; however, there is another factor. I am assuming a long string of one-termers (that was flagged as not-a-word. Oh well.) Lately incumbency has a big advantage: Clinton, W, Obama were all two-termers. Incumbency is powerful for two reasons that reinforce each other:<br />
<br />
The incumbent can DO things, can LOOK presidential.<br />
<br />
Since the incumbent has these advantages people are scared to run against him or her.<br />
<br />
--------------------------------------<br />
<b>Math problem</b>: What is the probability that we will see 6 living ex presidents by 2029? To solve this you would need to know<br />
<br />
Longevity statistics. But of what group? by Age? by profession? of ex-presidents? That seems to narrow for good statistics.<br />
<br />
Incumency statistics. How likely is it for a Prez to be re-elected? Again, too small a sample size. And Trump seems like an outlier. I suspect that if Jeb or Hillary were president they would get re-elected because of the incumbency advantage. But Trump is so unusual that it might not hold. One thing in his favor: it is unlikely there will be a challenge from his own party. One thing in his disfavor would be a third party challenge. But ENOUGH. My point is that it would be hard to do good stats here.<br />
<br />
-------------------------------------<br />
<br />
<br />
So why do I care about seeing 6 living ex-presidents in my lifetime? I have a reason but its not a good reason.<br />
<br />
Early in the Nixon Presidency LBJ died. I noticed that there were ZERO living ex-presidents. I knew that LBJ was dead, and JFK was dead, and I suspected (correctly) that Eisenhower and Truman were dead, and I knew FDR was dead. Before that we have Hoover and others who were of course dead. I was SO PROUD of myself for KNOWING this (to be fair I was 12 years old). This sparked my interest in presidents and especially in the question of most/least living ex-prez.<br />
<br />
Now for the obvious question on the other end of the spectrum:<br />
<br />
What is the min number of ex-presidents alive at the same time? And when did it occur (list all times)<br />
<br />
White space for those who want to try to figure it out or look it up.<br />
<br />
<br />
<br />
<br />
<br />
<br />
<br />
<br />
<br />
<br />
<br />
<br />
<br />
<br />
<br />
<br />
<br />
<br />
<br />
<br />
<br />
<br />
<br />
<br />
ANSWER: Zero. This happened six times.<br />
<br />
ONE: When George Washington was president there obviously were zero living ex-presidents.<br />
<br />
TWO: Shortly after John Adams became president George Washington died. At that time there were zero ex-presidents.<br />
<br />
THREE: During Ulysses S Grant's term Andrew Johnson, the prior president died. Lincoln was dead by assassination and all prior presidents were dead of old age or similar (e.g., James Buchanan died at the age of 77, Franklin Pierce (an ancestor of Barbara Bush (nee Pierce) was 65 and died of cirrhosis of the liver, from alcoholism.)<br />
<br />
FOUR: During Theodore Roosevelt's term Grover Cleveland died, and all other ex-presidents were dead. Recall that the prior prez, McKinley, had been assassinated.<br />
<br />
FIVE: During Herbert Hoover's term, following Calvin Coolidge's death (Hoover's predecessor), there were no ex-presidents. This partially explains why Coolidge didn't run- he had health problems. Note that Harding died in office.<br />
<br />
SIX: During Nixon's term, in 1973, Lyndon Johnson died. At that time there were zero ex-presidents. This was because Lyndon Johnson died young (65), Kennedy was assassinated, Eisenhower was old while president.<br />
<br />
<br />
NOTE: I would have thought that since FDR served so long and died in office either during FDR's term or Harry Truman's term there would be a time with no living ex-presidents. Early in FDR's term there was only one living ex-president: Hebert Hoover. However, he didn't die until 1964. Hence he lived through the presidencies of FDR, Truman, Eisenhower, Kennedy, and part of Johnson's. This is NOT the most presidents an ex-president has lived through after they step down. That honor might go to Carter who has lived through the presidencies of Reagan, Bush Sr, Clinton, W, Obama, and, as of this writing, a few years of Trump. I have not checked if this is a record but I will once Carter passes away.<br />
<br />
NOTE: In most of the cases above a recent president had died prematurely. Grant- Lincoln, Roosevelt- McKinley, Hoover- Coolidge, Nixon- Johnson and Kennedy.)<br />
<br />
NOT: Since Obama, W, and Clinton are all relatively young, and presidents dying in office is now very rare (the last one was JFK in 1963) I doubt this will happen again. But politics and history can surprise you.<br />
<div>
<br /></div>
<br />
<br />
<br />
<br />
<br />
<br />
<br />GASARCHhttp://www.blogger.com/profile/03615736448441925334noreply@blogger.com4tag:blogger.com,1999:blog-3722233.post-76439594473462379462018-11-28T13:27:00.000-05:002018-11-28T13:27:33.644-05:00LOGCFL Venkat Style<a href="http://2.bp.blogspot.com/-8z80agwTYFc/W_2yfnwcSeI/AAAAAAABkkI/suMTF6i4KIw_eXiovd2e0iY7qTx4PCGOACK4BGAYYCw/s1600/Venkat_V3A2528.jpg" imageanchor="1" style="clear: right; float: right; margin-bottom: 1em; margin-left: 1em;"><img border="0" height="133" src="https://2.bp.blogspot.com/-8z80agwTYFc/W_2yfnwcSeI/AAAAAAABkkI/suMTF6i4KIw_eXiovd2e0iY7qTx4PCGOACK4BGAYYCw/s200/Venkat_V3A2528.jpg" width="200" /></a>H. Venkateswaran, a much loved professor in the School of Computer Science at Georgia Tech and a fellow computational complexity theorist, is retiring at the end of December. In honor of Venkat I'd like talk about my <a href="https://doi.org/10.1016/0022-0000(91)90020-6">favorite paper</a> of his, relating LOGCFL to semi-unbounded circuits.<br />
<br />
Let's start with context-free languages. Even if you never took a theoretical computer science course, you probably saw them in elementary school.<br />
<br />
<div class="separator" style="clear: both; text-align: center;">
<a href="https://1.bp.blogspot.com/-YrhZOme8LU0/W_1SmeVPD4I/AAAAAAABkjA/YEpK6cBnhWgNryw6gI08Oa6elL8EtfH6gCLcBGAs/s1600/ch08-tree-4.png" imageanchor="1" style="margin-left: 1em; margin-right: 1em;"><img border="0" data-original-height="225" data-original-width="336" height="214" src="https://1.bp.blogspot.com/-YrhZOme8LU0/W_1SmeVPD4I/AAAAAAABkjA/YEpK6cBnhWgNryw6gI08Oa6elL8EtfH6gCLcBGAs/s320/ch08-tree-4.png" width="320" /></a></div>
<br />
A context-free language is a series of rules like S-> NP VP or N->man. The <i>context-free</i> part comes from the fact that a noun phrase (NP) produces the same sentence fragments wherever it appears. CFLs have a rich theory--there have been <a href="https://books.google.com/books?id=ZO9LAAAAMAAJ">whole textbooks</a> devoted to the topics.<br />
<br />
LOGCFL are the set of problems that are reducible to context-free languages with a small-space reduction. Formally, A is in LOGCFL if there is a CFL B and a log-space computable function f such that for all x, x is in A if and only if f(x) is in B.<br />
<br />
Venkat showed that LOGCFLs are equivalent to semi-unbounded circuits, log-depth circuits with unbounded OR gates but bounded AND gates, the class now called SAC<sup>1</sup> (technically the equivalence holds for log-space uniform SAC<sup>1</sup> but that's not important). His proof goes through various models of alternating Turing machines and push-down automata.<br />
<br />
Context-free languages are not closed under complement, for example 0<sup>n</sup>1<sup>n</sup>0<sup>n</sup> is not context-free but its complement is. Somewhat surprisingly Borodin, Cook, Dymond, Ruzzo and Tompa <a href="https://doi.org/10.1137/0218038">showed</a> that LOGCFL is closed under complement, combining the <a href="https://blog.computationalcomplexity.org/2003/06/foundations-of-complexity-lesson-19.html">Immerman-Szelepcsényi</a> inductive counting technique with Venkat's circuit characterization of LOGCFL.<br />
<br />
The Borodin result implies that you whether you have bounded ORs and unbounded ANDs, or bounded ANDs and unbounded ORs, you compute the same class.<br />
<br />
Enjoy your retirement Venkat. We'll miss you!Lance Fortnowhttps://plus.google.com/101693130490639305932noreply@blogger.com2tag:blogger.com,1999:blog-3722233.post-57196645362203809192018-11-26T00:54:00.000-05:002018-11-26T11:21:28.917-05:00If 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.<br />
<br />
<br />
<i>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><br />
<i><br /></i>
I thought it was Erdos but I could not find any connection between him and the saying. I did find something that indicates he<i> did not </i>say it:<br />
<br />
An Erdos problem that pays different amounts of money for the conjecture being true of false:<br />
<br />
--------------------------------------------------------------------------------<br />
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.<br />
<br />
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)<br />
<br />
Prove or disprove that<br />
t(n,H)=O(n^{3/2})<br />
t(n,H)=O(n^{3/2})<br />
if and only if H does not contain a subgraph each vertex of which has degree >2<br />
<br />
Bibliography<br />
1<span style="white-space: pre;"> </span>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.<br />
----------------------------------------------------------------------------------------<br />
<br />
A while back there was a $1,000,000 prize for PROVING Goldbach's conjecture (the prize had a deadline which is past). See <a href="https://www.math.tugraz.at/~elsholtz/WWW/papers/papers14faber.html">here</a>. 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.<br />
<br />
ANYWAY- if someone knows the source of the quote, please let me know.GASARCHhttp://www.blogger.com/profile/03615736448441925334noreply@blogger.com7tag:blogger.com,1999:blog-3722233.post-45820471243335961022018-11-20T00:43:00.000-05:002018-11-20T00:43:15.716-05:00Is Secret sharing REALLY REALLY REALLY used?Since I am teaching Cryptography this semester I am teaching things people REALLY REALLY REALLY (RRR) use. For some topics this is RRR true, like RSA (that it is used to transmit a private key that is then used is FINE.)<br />
<br />
I was wondering if Information-Theoretic Secret Sharing is RRR used. I am asking non-cynically and non-rhetorically. So I want to be taken seriously AND literally.<br />
<br />
I Googled and got some answers but could not verify them.<br />
<br />
1) At this site: <a href="https://cstheory.stackexchange.com/questions/899/what-are-some-examples-of-secret-sharing-schemes-actually-being-used-in-real-wor">here</a> we can read<br />
<br />
<i>Every modern HSM (hardware secure module, for crypto applications) uses Shamir's secret sharing</i>.<br />
<br />
I tried to verify this but was unable to.<br />
<br />
I also read<br />
<br />
<i>The DNSSEC root key is 5-out-of-7 shared see, e.g</i>., <a href="https://www.popsci.com/technology/article/2010-07/order-seven-cyber-guardians-around-world-now-hold-keys-internet">here</a> or <a href="https://www.cloudflare.com/dns/dnssec/root-signing-ceremony/">here</a><br />
<br />
The link leads to a story about how there are 7 people and if any 5 get together they can shut down the internet. The story does not say they use secret sharing.<br />
<br />
2) Threshold cryptography (see <a href="https://en.wikipedia.org/wiki/Threshold_cryptosystem">here</a>) would seem to use it, but is Threshold crypto used? There is a startup who is trying to use it: see <a href="https://sepior.com/thresholdsig/">here</a>. I don't count that as RRR since they don't have customers yet. Not sure what the threshold is for whether I count it.<br />
<br />
3) Some papers mention that secret sharing COULD be used if you want to make sure nuclear missiles are not launched unless x out of y people say so. But I doubt it really is used. If so this might be very hard to verify.<br />
<br />
4) Shamir's secret sharing scheme is pretty simple and does not have big constants so if there is a need it really could be used. But is there a need?<br />
<br />
I am not quite sure what I count as proof that someone RRR using it. A random person at a random website just saying that HSM uses it does not seem convincing. A Wikipedia article saying its being used I would find convincing (should I? Until recently Wikipedia couldn't even get my year of birth straight, see <a href="https://blog.computationalcomplexity.org/2018/09/still-typecasting-from-dagstuhl.html">here</a>)<br />
<br />
If some companies website said they used Shamir's Secret Sharing I would believe that-- but a companies website is not likely to say that. NOT for reasons of company secrets but because its not what most customers go to the website to find.<br />
<br />
SO- if someone RRR knows that Secret Sharing is RRR being used then please leave a comment.GASARCHhttp://www.blogger.com/profile/03615736448441925334noreply@blogger.com12tag:blogger.com,1999:blog-3722233.post-31954434542673336172018-11-15T11:59:00.000-05:002018-11-15T11:59:21.457-05:00Simons and AmazonI'm spending this week at the Simons Institute in smokey Berkeley, California. This fall Simons has a program in <a href="https://simons.berkeley.edu/programs/complexity2018">Lower Bounds in Computational Complexity</a>. Scroll down that page and you'll see the rather strong collection of participants that are spending much of the fall at the Institute.<br />
<br />
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.<br />
<br />
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 <a href="https://simons.berkeley.edu/events/game-theory-in-auction-and-blockchain">Game Theory in Auction and Blockchain</a> 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.<br />
<br />
Simons started as a <a href="https://blog.computationalcomplexity.org/2010/08/new-institute-for-theory-of-computing.html">competition</a> 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".Lance Fortnowhttps://plus.google.com/101693130490639305932noreply@blogger.com2tag:blogger.com,1999:blog-3722233.post-23264207058293476932018-11-12T12:02:00.002-05:002018-11-13T20:33:34.405-05:00And the winner is again, Harambe: A pre election poll of my class that was truly a referenum on the PrezI had meant to post this before the election but I didn't quite time it right. Oh well.<br />
<br />
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 <a href="https://blog.computationalcomplexity.org/2016/11/and-winner-is-harambe.html">2016</a> , <a href="https://blog.computationalcomplexity.org/2012/11/random-thoughts-on-election.html">2012</a>, <a href="https://blog.computationalcomplexity.org/2012/11/random-thoughts-on-election.html">2008</a>) 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:<br />
<br />
1) Who did you vote for in 2016?<br />
<br />
2) Knowing what you know now, who would have have voted for in 2016?<br />
<br />
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.<br />
<br />
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.<br />
<br />
4 voted Trump and now wish they voted differently: Harmabe, Clinton, Nobody, Gasarch<br />
<br />
Only 12 people had voted for Trump in 2016 and of those 4<br />
regret it. While I can see wanting Clinton, Nobody, or Gasarch,<br />
I'm surprised someone wanted Harmabe. Is he even a citizen?<br />
<br />
5 voted Clinton and now wish they voted differently: 2-Johnson, Trump, Kanye, Gasarch.<br />
<div>
<br /></div>
<div>
<div>
<br /></div>
<div>
Since Clinton hasn't done anything to merit rejection since the election,</div>
<div>
I deduce these people are more going TOWARDS the one they picked rather</div>
<div>
than AWAY from her. Trump has been Prez and has done stuff, so Clinton/Trump</div>
<div>
makes sense -- the student's opinion is that Trump is doing better</div>
<div>
than expected. Gary Johnson hasn't done anything to merit a change towards</div>
<div>
him, so thats a puzzler. Kanye, similar. As for Gasarch, if the reasoning</div>
<div>
is `he's doing a good job teaching crypto, lets make him president' doesn't</div>
<div>
really work since he's not doing THAT good a job. If it was Ramsey theory</div>
<div>
then I could see it.</div>
<div>
<br /></div>
<div>
Misc:</div>
<div>
1 Underwood(House of Cards)/Satan (For those tired of picking the LESSER of two evils)</div>
<div>
1 Stein/Clinton</div>
<div>
1 Johnson/Clinton</div>
<div>
1 Kruskal/Gasarch (some people can't tell them apart)</div>
<div>
<br /></div>
<div>
The two who went to Clinton I interpret as thinking Trump is worse</div>
<div>
than expected.<br />
<br />
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.</div>
<div>
<br /></div>
<div>
MY OPINON: FORTNOW in 2020!</div>
<div>
<br /></div>
<div>
------------------------------------------------------</div>
<div>
<br /></div>
<div>
61 students did the poll.</div>
<div>
<br /></div>
<div>
-----------------------------</div>
<div>
Stayed the same:</div>
</div>
<div>
<br /></div>
<div>
<div>
-----------------------------</div>
<div>
Stayed the same:</div>
<div>
<br /></div>
<div>
28 Clinton/Clinton</div>
<div>
8 Trump/Trump</div>
<div>
4 Stein/Stein</div>
<div>
3 Johnson/Johnson</div>
<div>
1 Kasich/Kasich</div>
<div>
1 Sanders/Sanders</div>
<div>
1 Jerry White/Jerry White (Socialist Party)</div>
<div>
1 Bofa/Bofa (this is a joke)</div>
<div>
1 Thomas Adam Kirkman/Thomas Adam Kirkman (prez on TV show Designated Survivor)</div>
<div>
<br /></div>
<div>
48 do not regret their vote.</div>
<div>
<br /></div>
<div>
-------------------------</div>
<div>
Trump/XXX</div>
<div>
<br /></div>
<div>
1 Trump/Harmabe (Harambe is the Gorilla who got shot in a zoo.)</div>
<div>
1 Trump/Clinton</div>
<div>
1 Trump/Nobody</div>
<div>
1 Trump/Gasarch (Gasarch would prove the problems of government are unsolvable rather than solve them)</div>
<div>
<br /></div>
<div>
FOUR people voted Trump and now regret it.</div>
<div>
<br /></div>
<div>
------------</div>
<div>
Clinton/XXX</div>
<div>
<br /></div>
<div>
2 Clinton/Johnson</div>
<div>
1 Clinton/Trump</div>
<div>
1 Clinton/Kanye</div>
<div>
1 Clinton/Gasarch</div>
</div>
<div>
<br /></div>
<div>
<div>
<br /></div>
<div>
FIVE people voted Clinton and now regret it.</div>
<div>
<br /></div>
<div>
-------------</div>
<div>
MISC changed</div>
<div>
<br /></div>
<div>
1 Underwood(House of Cards)/Satan (For those tired of picking the LESSER of two evils)</div>
<div>
1 Stein/Clinton</div>
<div>
1 Johnson/Clinton</div>
<div>
1 Kruskal/Gasarch (some people can't tell them apart)</div>
<div>
<br /></div>
<div>
TWO people who voted third party now would have voted Clinton.</div>
<div>
I interpret this as not-liking-Trump since I don't think Clinton</div>
<div>
has done anything since the election to make anyone thing better</div>
<div>
or worse of her, while as Trump as president has done enough</div>
<div>
to change people's opinions of him.</div>
</div>
<div>
<br /></div>
GASARCHhttp://www.blogger.com/profile/03615736448441925334noreply@blogger.com2tag:blogger.com,1999:blog-3722233.post-19159326095928826342018-11-08T09:00:00.000-05:002018-11-08T09:00:18.792-05:00The Data Transformation of UniversitiesWith all the news about elections, caravans, shootings and attorney generals, maybe you missed the various stories about real transformations at our top universities.<br />
<br />
On October 15 MIT announced the <a href="http://news.mit.edu/2018/mit-reshapes-itself-stephen-schwarzman-college-of-computing-1015">Stephen A. Schwarzman College of Computing</a>. 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.<br />
<blockquote class="tr_bq">
“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. </blockquote>
Two weeks later the University of California at Berkeley <a href="https://news.berkeley.edu/2018/11/01/berkeley-inaugurates-division-of-data-science-and-information-connecting-teaching-and-research-from-all-corners-of-campus/">announced a Division of Data Science</a> to be led by an associate provost reporting directly to the provost (like a dean).<br />
<blockquote class="tr_bq">
“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.”</blockquote>
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.<br />
<br />
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 <a href="https://codatechsquare.com/">CODA building</a> that will open next year in Midtown Atlanta (sounds impressive when I write it down).<br />
<br />
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) <a href="https://datascience.columbia.edu/data-science-week-brought-together-nation%E2%80%99s-leading-data-scientists">held a summit</a> of academic data science leadership. The <a href="https://datascience.columbia.edu/files/seasdepts/idse/Data_Science_Leadership_Summit_Summary_Report.pdf">report</a> shows we have much to do.<br />
<br />
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.Lance Fortnowhttps://plus.google.com/101693130490639305932noreply@blogger.com0tag:blogger.com,1999:blog-3722233.post-69404162627771556962018-11-05T19:01:00.000-05:002018-11-05T19:01:09.773-05:00Is Fuzzy Sets Common Knowledge? How about Napier as inventing (or something) logs?<b>Darling:</b> Bill, help me with this crossword puzzle. 6 letter word that begins with N, clue is log man<br />
<br />
<b>Bill:</b> Napier<br />
<br />
<b>Darling</b>: Who was that?<br />
<br />
<b>Bill: </b>A famous lumberjack<br />
<br />
<b>Darling:</b> Give me a serious answer<br />
<br />
<b>Bill:</b> 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.<br />
<br />
<b>Darling</b>: I said give me a serious answer. That is rather obscure and would not be in a crossword puzzle.<br />
<br />
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.<br />
<br />
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)<br />
<br />
<i>In 1965 Lotfi Zadeh introduced this type of set with no clear boundaries leading to the same type of ``logic''</i><br />
<i><br /></i>
1) I suspect that all my readers know that the correct response is `Fuzzy' (or formally `What is Fuzzy')<br />
<br />
2) Why is this in Philosophy? There IS an entry of it in the Stanford Enc of Phil (see <a href="https://plato.stanford.edu/entries/logic-fuzzy/">here</a>). Some Philosophers work on Logic, but do they work on Fuzzy Logic? The wikipedia page for Fuzzy Logic (see <a href="https://en.wikipedia.org/wiki/Fuzzy_logic">here</a>) has only one mention of phil and its to the Stanford Enc of Phil chapter.<br />
<br />
3) (more my point) Is Fuzzy Logic so well known as to be an easy question on Jeop? See next point<br />
<br />
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.<br />
<br />
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.GASARCHhttp://www.blogger.com/profile/03615736448441925334noreply@blogger.com3tag:blogger.com,1999:blog-3722233.post-56856710219290774382018-11-01T06:33:00.000-04:002018-11-01T16:38:00.834-04:00P = NP Need Not Give a SAT AlgorithmIn <a href="https://blog.computationalcomplexity.org/2018/10/if-pnp-then-we-have-alg-for-sat.html">Bill's post</a> 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.<br />
<br />
Bill links to a TCS Stack Exchange <a href="https://cstheory.stackexchange.com/a/41753/550">answer</a> 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.<br />
<br />
<pre style="background-color: #eff0f1; border: 0px; box-sizing: inherit; color: #242729; font-family: Consolas, Menlo, Monaco, "Lucida Console", "Liberation Mono", "DejaVu Sans Mono", "Bitstream Vera Sans Mono", "Courier New", monospace, sans-serif; font-size: 13px; font-stretch: inherit; font-variant-east-asian: inherit; font-variant-numeric: inherit; line-height: inherit; margin-bottom: 1em; max-height: 600px; overflow-wrap: normal; overflow: auto; padding: 5px; vertical-align: baseline; width: auto;"><code style="border: 0px; box-sizing: inherit; font-family: Consolas, Menlo, Monaco, "Lucida Console", "Liberation Mono", "DejaVu Sans Mono", "Bitstream Vera Sans Mono", "Courier New", monospace, sans-serif; font-stretch: inherit; font-style: inherit; font-variant: inherit; font-weight: inherit; line-height: inherit; margin: 0px; padding: 0px; vertical-align: baseline; white-space: inherit;">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.</code></pre>
<br />
This proof relativizes: There is a fixed relativizing Turing machine M such that for all A, if P<sup>A</sup> = NP<sup>A</sup> then L(M<sup>A</sup>) runs in polynomial time and differs from SAT<sup>A</sup> on only a finite number of strings. SAT<sup>A</sup> is a relativizable form of SAT with a built in relations that answer whether a sequence of variables encode an string in A. SAT<sup>A</sup> is NP<sup>A</sup>-complete for all A.<br />
<br />
The following shows any proof that a fixed algorithm can compute all of SAT correctly if P = NP cannot relativize.<br />
<br />
<b>Theorem: </b>For every deterministic Turing machine M, there is an A such that P<sup>A</sup> = NP<sup>A</sup> and either M<sup>A </sup>does not compute SAT<sup>A</sup> correctly on all inputs or M<sup>A </sup>takes at least exponential time.<br />
<br />
<b>Proof:</b><br />
<br />
Define B = {0x | x in TQBF}. TQBF is the PSPACE-complete problem containing all the true quantified Boolean formula. P<sup>TQBF</sup> = PSPACE = NP<sup>TQBF</sup> and thus P<sup>B</sup> = NP<sup>B</sup>.
<br />
<br />
Let φ<sub>n</sub> be the formula that is true if there exists a string z of length n such that 1z is in A. Let n be the smallest n such that M<sup>B</sup>(φ<sub>n</sub>) takes less than 2<sup>n</sup> computational steps. If no such n exists let A = B and we are done.
<br />
<br />
If M<sup>B</sup>(φ<sub>n</sub>) accepts we are done by letting A=B since B has no string beginning with 1.
<br />
<br />
If M<sup>B</sup>(φ<sub>n</sub>) rejects and uses less than 2<sup>n</sup> steps there must be some z such that M<sup>B</sup>(φ<sub>n</sub>) did not query 1z. Let A = B ∪ {1z}.<br />
<br />
M<sup>A</sup>(φ<sub>n</sub>) still rejects but now φ<sub>n</sub> is in SAT<sup>A</sup>. Also P<sup>A</sup> = NP<sup>A</sup> since adding a single string to an oracle won't affect whether two classes collapse.Lance Fortnowhttps://plus.google.com/101693130490639305932noreply@blogger.com12tag:blogger.com,1999:blog-3722233.post-35931160950457486932018-10-29T00:08:00.000-04:002018-10-29T00:08:03.856-04:00If 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:<br />
<br />
<i> P=NP but the proof will be nonconstructive and have a large constant.</i><br />
<br />
Large constant could happen.<br />
<br />
If by nonconstructive they mean not practical, then yes, that could happen.<br />
<br />
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 <b>except for a finite number of formulas</b> (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 <b>finite number of formulas </b>is why the people above may still be right. But only a finite number- seems like a weak kind of nonconstructive.<br />
<br />
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 <b>finite exception</b> 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:<br />
<br />
<i>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.</i><br />
<br />
<br />
Not sure how to define insane.<br />
<br />
Three pointers:<br />
<br />
Stack Exchange TCS: <a href="https://cstheory.stackexchange.com/questions/41751/algorithm-whose-running-time-depends-on-p-vs-np">here</a><br />
<br />
Wikipedia: <a href="https://en.wikipedia.org/wiki/P_versus_NP_problem#Polynomial-time_algorithms">here</a><br />
<br />
My slides (also include factoring result): <a href="https://www.cs.umd.edu/users/gasarch/BLOGPAPERS/pnpconst.pdf">here</a><br />
<br />
<b>Question: </b>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).<br />
<br />
<b>Question</b>: 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?<br />
<b><br /></b>
GASARCHhttp://www.blogger.com/profile/03615736448441925334noreply@blogger.com14tag:blogger.com,1999:blog-3722233.post-9322305857474822072018-10-25T07:24:00.000-04:002018-10-25T07:24:55.178-04:00Good Results Made MeaninglessSometimes 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.<br />
<br />
Let me give two examples.<br />
<br />
In STOC 1995 Nisan and Ta-Shma showed that <a href="https://doi.org/10.1145/225058.225101">Symmetric logspace is closed under complement</a>. Their proof worked quite differently from the 1988 Immerman-Szelepcsenyi <a href="https://blog.computationalcomplexity.org/2003/06/foundations-of-complexity-lesson-19.html">nondeterministic logpsace closed under complement</a> 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.<br />
<br />
Ten years later Omer Reingold <a href="https://blog.computationalcomplexity.org/2014/02/favorite-theorems-connecting-in-log.html">showed</a> 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.<br />
<br />
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 <a href="https://doi.org/10.1145/12130.12162">randomly generate certified primes</a>, primes with proofs of primeness. Adleman and Huang <a href="https://doi.org/10.1145/28395.28445">later showed</a> that one can randomly find a proof of primeness for any prime.<br />
<br />
In 2002, Agrawal, Kayal and Saxena showed <a href="https://www.jstor.org/stable/3597229">Primes in P</a>, 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".Lance Fortnowhttps://plus.google.com/101693130490639305932noreply@blogger.com4tag:blogger.com,1999:blog-3722233.post-70636174670510323172018-10-22T20:33:00.000-04:002018-10-22T20:46:26.893-04:00 Please Don't call them Guidance CounselorsAs 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<br />
<br />
Allie Downey<br />
<strike>Guidance</strike> School Counselor<br />
<br />
This piqued my interest so I emailed her asking why the cross out.<br />
<br />
She was delighted to answer! Here is her email:<br />
<br />
T<i>hank 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 <a href="http://sccounselor.blogspot.com/2011/10/school-counselor-yes-vs-guidance.html">here</a></i><br />
<i><br /></i>
<i>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><br />
<br />
I asked her further about the difference and here is what she said:<br />
<br />
<i>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.</i><br />
<br />GASARCHhttp://www.blogger.com/profile/03615736448441925334noreply@blogger.com3tag:blogger.com,1999:blog-3722233.post-34614803865808228082018-10-18T09:23:00.001-04:002018-10-18T09:23:50.796-04:00A New Cold War?Imagine the following not-so-unrealistic scenario: The US-China trade war deepens <a href="https://www.wsj.com/articles/mike-pence-announces-cold-war-ii-1539039480">leading to a cold war</a>. The US <a href="https://www.businessinsider.com/trump-admin-considered-banning-chinese-students-to-keep-out-spies-2018-10">blocks all Chinese citizens</a> from graduate school in the US. Visas between the two countries <a href="https://thehill.com/policy/international/389809-trump-administration-to-tighten-restrictions-on-some-chinese-visas">become hard to get</a>. The Chinese <a href="https://www.nytimes.com/2018/10/15/opinion/internet-google-china-balkanization.html?rref=collection%2Fsectioncollection%2Fopinion-editorials">close off their Internet</a> to the West.<br />
<blockquote class="tr_bq">
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.</blockquote>
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?<br />
<br />
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 <a href="https://www.history.com/topics/inventions/invention-of-the-internet">thank the cold war for the internet</a>). 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 (<a href="https://blog.computationalcomplexity.org/2005/04/favorite-theorems-np-completeness.html">Cook/Levin</a>, <a href="https://blog.computationalcomplexity.org/2016/09/boris-trakhtenbrot-1921-2016.html">Borodin/Trakhtenbrot</a>, <a href="https://blog.computationalcomplexity.org/2003/06/foundations-of-complexity-lesson-19.html">Immerman/Szelepcsényi</a>).<br />
<br />
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 <a href="https://doi.org/10.1016/S0169-7552(98)00110-X">working together</a> to give us Google.<br />
<br />
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.<br />
<br />
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 <a href="https://www.cnn.com/2018/09/30/tech/quantum-computing-china/index.html">quantum computing</a> and <a href="https://www.nytimes.com/2018/09/22/opinion/sunday/ai-china-united-states.html">machine learning</a> 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.<br />
<br />
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.Lance Fortnowhttps://plus.google.com/101693130490639305932noreply@blogger.com2tag:blogger.com,1999:blog-3722233.post-70740883289960102462018-10-14T22:52:00.000-04:002018-10-14T22:52:07.623-04:00Practical consequences of RH ?When it seemed like Riemann Hypothesis (RH) might be solved (see Lipton-Regan blog entry on RH <a href="https://rjlipton.wordpress.com/2018/09/26/reading-into-atiyahs-proof/">here</a> 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.<br />
<br />
<i>Ajeet:</i> So Bill, now that RH has been solved should I take my credit cards off of Amazon?<br />
<br />
<i>Bill:</i> 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.<br />
<br />
<i>Ajeet</i>: What are my thoughts and why are they wrong?<br />
<br />
<i>Bill</i>: What am I a mind-reader?<br />
<br />
<i>Ajeet</i>: Aren't you?<br />
<br />
<i>Bill: </i>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.<br />
<br />
<i>Ajeet:</i> It just isn't my day.<br />
<br />
<i>Bill: </i>Any day you are enlightened is your day. Okay, here are the thoughts you have<br />
<br />
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.<br />
<br />
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<br />
<br />
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:<br />
<br />
RH--> factoring easy, and<br />
<br />
The proof does not give you the algorithm, and<br />
<br />
if you had a proof or RH then you COULD get the algorithm (though not in a few hours).<br />
<br />
I doubt this is the case.<br />
<br />
<i>Ajeet: </i>So are there any practical consequences of RH?<br />
<br />
<i>Bill</i>: Would you call better bounds on the error term of the prime number theory practical.<br />
<br />
<i>Ajeet</i>: YES!<br />
<br />
<i>Bill:</i> GREAT! For more on RH see <a href="http://empslocal.ex.ac.uk/people/staff/mrwatkin/zeta/riemannhyp.htm#q8">here</a>GASARCHhttp://www.blogger.com/profile/03615736448441925334noreply@blogger.com3