tag:blogger.com,1999:blog-3722233Thu, 18 Oct 2018 10:09:27 +0000typecastfocs metacommentsComputational ComplexityComputational Complexity and other fun stuff in math and computer science from Lance Fortnow and Bill Gasarchhttps://blog.computationalcomplexity.org/noreply@blogger.com (Lance Fortnow)Blogger2625125tag:blogger.com,1999:blog-3722233.post-7074088328996010246Mon, 15 Oct 2018 02:52:00 +00002018-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>https://blog.computationalcomplexity.org/2018/10/practical-consequences-of-rh.htmlnoreply@blogger.com (GASARCH)2tag:blogger.com,1999:blog-3722233.post-7062984698333972332Thu, 11 Oct 2018 13:27:00 +00002018-10-11T09:27:49.449-04:002018 Fall Jobs PostAs 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.<br />
<blockquote class="twitter-tweet" data-lang="en">
<div dir="ltr" lang="en">
I said this last year and it's time to say it again:<br />
to save time and energy, will the CS departments NOT hiring faculty this year please speak up?</div>
— John Regehr (@johnregehr) <a href="https://twitter.com/johnregehr/status/1045481991456534528?ref_src=twsrc%5Etfw">September 28, 2018</a></blockquote>
For computer science faculty positions best to look at the ads from the <a href="http://www.cra.org/ads/">CRA</a> and the <a href="http://jobs.acm.org/">ACM</a>. For theoretical computer science specific postdoc and faculty positions check out <a href="https://cstheory-jobs.org/">TCS Jobs</a> and <a href="http://dmatheorynet.blogspot.com/">Theory Announcements</a>. If you have jobs to announce, please post to the above and/or feel free to leave a comment on this post.<br />
<br />
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.<br />
<br />
And (selfish plug) Georgia Tech is <a href="https://www.scs.gatech.edu/content/cs-faculty-hiring">looking to hire in theory this year</a>.<br />
<br />
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.<br />
<br />
Above all have fun! In this computational and data driven world we live in, there is a great job out there for you.<br />
<script async="" charset="utf-8" src="https://platform.twitter.com/widgets.js"></script>
https://blog.computationalcomplexity.org/2018/10/2018-fall-jobs-post.htmlnoreply@blogger.com (Lance Fortnow)0tag:blogger.com,1999:blog-3722233.post-9180528921566812115Mon, 08 Oct 2018 23:55:00 +00002018-10-08T19:55:48.558-04:00A New ACO Center (guest post by Vijay Vazirani)Guest Post by Vijay Vazirani<br />
<br />
A New ACO Center!<br />
<br />
Last week, I helped launch an <a href="http://sites.uci.edu/acoi/">ACO Center</a> (Algorithms, Combinatorics and Optimization) at my wonderful new home, UC Irvine. There are only two other such centers, at <a href="http://aco.math.cmu.edu/">CMU</a> and <a href="http://www.aco.gatech.edu/">Georgia Tech</a> (29 and 27 years old, respectively). My personal belief is that there will be more in the future. Let me justify.<br />
<br />
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 <a href="https://www.springer.com/us/book/9783540653677">my book on the topi</a>c 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 <a href="https://www.cambridge.org/us/academic/subjects/computer-science/algorithmics-complexity-computer-algebra-and-computational-g/algorithmic-game-theory?format=HB&isbn=9780521872829">co-edited book</a> 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.<br />
<div>
<br /></div>
<div>
<div>
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 <a href="https://www.imbs.uci.edu/">Institute for Mathematical Behavioral Sciences</a>) 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 <a href="http://sites.uci.edu/acoi/">Center website</a> has further details about its vision and activities.</div>
<div>
<br /></div>
<div>
<div>
Many universities are in a massive hiring mode today (especially in CS), e.g., UCI <a href="https://strategicplan.uci.edu/pillar-1.php">plans to hire 250</a> 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.</div>
<div>
<br /></div>
<div>
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.</div>
</div>
</div>
https://blog.computationalcomplexity.org/2018/10/a-new-aco-center-guest-post-by-vijay.htmlnoreply@blogger.com (GASARCH)1tag:blogger.com,1999:blog-3722233.post-2531434175117112501Sat, 06 Oct 2018 18:14:00 +00002018-10-06T14:14:19.722-04:00John Sidles, Mike Roman, Matt Howell, please email me/hard to get emails of peopleJohn Sidles, Mike Roman, Matt Howell : please email me. at gasarch@cs.umd.edu (my usual email)<br />
<br />
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!<br />
<br />
When you do I will tell you whats up and why I decline to say here what this is about.<br />
<br />
For my other readers -- it is nothing controversial.<br />
<br />
<br />
How hard is it to find people's emails on the web?<br />
<br />
Sometimes it takes less than 5 minutes<br />
<br />
Sometimes it is impossible.<br />
<br />
Sometimes I get it by asking someone else who knows, or knows who to ask... etc.<br />
<br />
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.)<br />
<br />
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.<br />
<br />
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.https://blog.computationalcomplexity.org/2018/10/john-sidles-mike-roman-matt-howell.htmlnoreply@blogger.com (GASARCH)0tag:blogger.com,1999:blog-3722233.post-7429761312632790568Fri, 05 Oct 2018 01:47:00 +00002018-10-04T21:47:12.808-04:00Google added years to my lifeIf you google<br />
<br />
gasarch<br />
<br />
you used to get the following: <a href="http://www.cs.umd.edu/~gasarch/BLOGPAPERS/bill68.png">here</a><br />
<br />
Please go there and notice how old they say I am.<br />
<br />
Okay, you are back. You may have noticed that they say I am 68. Gee, I don't feel 68 (I feel younger).<br />
<br />
I have no idea how Google got my age wrong.<br />
<br />
0) I found about this when I saw my age in an article about the Muffin problem. The article is <a href="https://www.nrc.nl/nieuws/2018/09/14/hoe-vijf-muffins-tot-een-diep-wiskundig-vraagstuk-leidden-a1616534">here</a>. 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.<br />
<br />
1) My age was not on my Wikipedia page. Nor was my birth year.<br />
<br />
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!)<br />
<br />
3) Google thinks I published with Hilbert (see <a href="https://scholar.google.com/citations?user=SVRgMwEAAAAJ&hl=en">here</a> or <a href="https://blog.computationalcomplexity.org/2017/05/google-scholar-thinks-my-hilbert-number.html">here</a>) 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<br />
him then, then I would now be 80. Not 68. So that is not the answer.<br />
(Side question- are any of Hilbert's co-authors still alive?)<br />
<br />
Seriously, if anyone has any ideas why Google had it wrong, let me now<br />
<br />
4) Lance was outraged at this and hence put my birth year on my Wikipedia page thinking that<br />
would fix it. (I was not outraged, just amused.)<br />
<br />
5) It was taken off my page since Lance couldn't prove it.<br />
<br />
6) Lance and I mentioned my age in a blog post and that was proof enough. So our blog is a primary<br />
source. We should use this sparingly -- with great power comes great responsibility. (See <a href="https://www.youtube.com/watch?v=fj7c3vBZ7jA">here</a> for more on that theme)<br />
<br />
7) Other weird internet stuff: What does it take to get a Wikipedia Page? A Nobel Prize in Physics<br />
helps. See: <a href="https://www.thedailybeast.com/nobel-laureate-donna-strickland-judged-not-famous-enough-for-wikipedia-page-before-win-report">here</a>.<br />
<br />
<br />https://blog.computationalcomplexity.org/2018/10/google-added-years-to-my-life.htmlnoreply@blogger.com (GASARCH)4tag:blogger.com,1999:blog-3722233.post-4491418763182334686Mon, 01 Oct 2018 21:06:00 +00002018-10-02T09:52:39.676-04:00Muffin Math<b>Lance: </b>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.<br />
<br />
<b>Bill: </b>Always a good idea.<br />
<br />
<b>Lance: </b>First the exciting news, Nitin Saxena won the <a href="http://ssbprize.gov.in/">Shanti Swarup Bhatnagar prize</a> for 2018, <br />
<table cellpadding="0" cellspacing="0" class="tr-caption-container" style="float: right; margin-left: 1em; text-align: right;"><tbody>
<tr><td style="text-align: center;"><a href="https://1.bp.blogspot.com/-SaGHaelCUQU/W7KK8Yy3mtI/AAAAAAABjjQ/6Qw1qL8YAz4gXTfMv9qvqD-EU9sXhDMEgCKgBGAs/s1600/IMG_20180926_180801.jpg" imageanchor="1" style="clear: right; margin-bottom: 1em; margin-left: auto; margin-right: auto;"><img border="0" data-original-height="1600" data-original-width="1200" height="200" src="https://1.bp.blogspot.com/-SaGHaelCUQU/W7KK8Yy3mtI/AAAAAAABjjQ/6Qw1qL8YAz4gXTfMv9qvqD-EU9sXhDMEgCKgBGAs/s200/IMG_20180926_180801.jpg" width="150" /></a></td></tr>
<tr><td class="tr-caption" style="text-align: center;">Nitin Saxena</td></tr>
</tbody></table>
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.<br />
<br />
<b>Bill: </b>That's really impressive. He was only two-years old when AKS had log-depth sorting networks.<br />
<br />
<b>Lance: </b>Bill, you moron. You're thinking of <a href="https://doi.org/10.1145/800061.808726">Ajtai-Komlós-Szemerédi</a>. I'm talking Agrawal-Kayal-Saxena <a href="http://annals.math.princeton.edu/2004/160-2/p12">Primes in P</a>, topic of my <a href="https://blog.computationalcomplexity.org/2002/08/this-has-been-exciting-summer-for.html">second ever blog post</a>. 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.<br />
<br />
<b>Bill: </b>Well congrats to Nitin. Moving on, let's talk math.<br />
<br />
<b>Lance: </b>We're at Dagstuhl so we have to call it computer science.<br />
<br />
<b>Bill: </b>Ronen Shaltiel gave a great but depressing talk, <a href="https://eccc.weizmann.ac.il/report/2018/061/">Indistinguishability by adaptive procedures with advice, and lower bounds on hardness amplification proofs</a>.<br />
<br />
<b>Lance: </b>Nobody sings the <a href="https://www.youtube.com/watch?v=aDunXIMNE7A">Dagstuhl Blues</a>.<br />
<br />
<b>Bill: </b>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.<br />
<br />
<b>Lance: </b>But we have not hardness results there? Where are you going with this?<br />
<br />
<b>Bill: </b>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.<br />
<br />
<b>Lance: </b>Not as much as the sprained ankle that made me miss that talk. My turn to pick a favorite talk. I loved Michael Forbes <a href="https://doi.org/10.1145/3188745.3188792">Hitting Sets for the Closure of Small Circuits</a>. 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 <a href="https://arxiv.org/abs/1304.6333">GCT approach</a> to lower bounds.<br />
<br />
<b>Bill: </b>What lower bounds is this aiming to solve?<br />
<br />
<b>Lance: </b>Showing the computation difference between the determinant and the permanent.<br />
<br />
<b>Josh Alman: </b>You've left out the most exciting part of the conference.<br />
<br />
<b>Bill and Lance: </b>So Josh, what was that?<br />
<br />
<b>Josh Alman: </b>The world debut debut performance of Stud Muffin and Smilin' Sam singing "<a href="https://www.youtube.com/watch?v=4xQFlsK7jKg">Do You Work on Muffin Math?</a>"<br />
<br />
<br />
<div class="separator" style="clear: both; text-align: center;">
<iframe allowfullscreen="" class="YOUTUBE-iframe-video" data-thumbnail-src="https://i.ytimg.com/vi/4xQFlsK7jKg/0.jpg" frameborder="0" height="266" src="https://www.youtube.com/embed/4xQFlsK7jKg?feature=player_embedded" width="320"></iframe></div>
<br />
<b>Lance: </b>That awesome duo looks familiar Bill. Where I have seen them before?<br />
<br />
<b>Bill: </b>That Sam can really tickle the ivories.<br />
<br />
<b>Lance: </b>And Stud was definitely in the room.<br />
<br />
<b>Bill: </b>On that note, take us out.<br />
<br />
<b>Lance: </b>In a complex world, keep it simple.https://blog.computationalcomplexity.org/2018/10/muffin-math.htmlnoreply@blogger.com (Lance Fortnow)1tag:blogger.com,1999:blog-3722233.post-3228966270379272028Thu, 27 Sep 2018 06:44:00 +00002018-09-27T07:16:59.382-04:00Still Typecasting from Dagstuhl<b>Lance: </b>Bill, in our <a href="https://blog.computationalcomplexity.org/2018/09/lance-and-bill-go-to-dagstuhl-riemann.html">typecast</a> earlier this week I said you were older than me. But 68? You don't look day over 66.<br />
<br />
<b>Bill: </b>Neither do you. But seriously, why do you think I'm 68?<br />
<a href="https://4.bp.blogspot.com/-10m0C7mFATw/W6txToo4KEI/AAAAAAABjfs/SbBYpREG8cgjgrBVykJ9DOCf_Qh7_jl3ACLcBGAs/s1600/Bill%2B68.1.png" imageanchor="1" style="clear: right; float: right; margin-bottom: 1em; margin-left: 1em;"><img border="0" data-original-height="1025" data-original-width="1600" height="203" src="https://4.bp.blogspot.com/-10m0C7mFATw/W6txToo4KEI/AAAAAAABjfs/SbBYpREG8cgjgrBVykJ9DOCf_Qh7_jl3ACLcBGAs/s320/Bill%2B68.1.png" width="320" /></a><br />
<b>Lance: </b>I just Google'd "How old is Bill Gasarch?"<br />
<br />
<b>Bill: </b>Don't believe everything you read on the Internet. I'm really 58.<br />
<br />
<b>Lance: </b>Prove it.<br />
<br />
<b>Bill: </b>Here's my driver's license.<br />
<br />
<b>Lance: </b>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?<br />
<br />
<a href="https://1.bp.blogspot.com/-aDqlcNz7t_c/W6t0rVdIZcI/AAAAAAABjgI/qILWfsOs0TQwiLCLncADxRvLpXYfWGquwCKgBGAs/s1600/IMG_20180925_120039.jpg" imageanchor="1" style="clear: right; float: right; margin-bottom: 1em; margin-left: 1em;"><img border="0" data-original-height="1600" data-original-width="1115" height="200" src="https://1.bp.blogspot.com/-aDqlcNz7t_c/W6t0rVdIZcI/AAAAAAABjgI/qILWfsOs0TQwiLCLncADxRvLpXYfWGquwCKgBGAs/s200/IMG_20180925_120039.jpg" width="138" /></a><b>Bill: </b>Yes, because they pay my salary. Back to Dagstuhl. Let's talk about <a href="https://docs.google.com/document/d/1CPf_ocNIQJuhsnwG_6HKqaUDP8U-Pt7V8pJRLq6vvRw/edit?usp=sharing">the talks</a>. 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.<br />
<br />
<b>Lance: </b>You mean realistic. Though I'd guess more like 10-20 years. I wouldn't even be surprised if NL (nondeterministic log space) = L.<br />
<br />
<b>Arpita Korwar: </b>I say 10-15 years.<br />
<br />
<b>Bill: </b>Can we put that in the blog?<br />
<br />
<b>Lance: </b>Too late. Bill I heard you were the stud muffin this week.<br />
<br />
<b>Bill: </b>Yes, I talked about the <a href="https://blog.computationalcomplexity.org/2018/06/the-muffin-problem.html">muffin problem</a>. Got a problem with that?<br />
<br />
<b>Lance: </b>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.<br />
<br />
<b>Bill: </b>I can't believe you actually listened to the talk and didn't fall asleep.<br />
<br />
<b>Lance: </b>zzzzzz. Did you say something?<br />
<br />
<b>Bill: </b>Never mind. Eric Allender talked about the <a href="http://dx.doi.org/10.4230/LIPIcs.ITCS.2018.20">minimum circuit-size problem</a>: 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).<br />
<br />
<b>Lance: </b>Do you think EXP = ZPP?<br />
<br />
<b>Bill: </b>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 <a href="https://blog.computationalcomplexity.org/2018/09/still-typecasting-from-dagstuhl.html?showComment=1538032720983#c1629526917930788998">comment</a>. 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.<br />
<br />
<b>Lance: </b>Reminds me of the Kolmogorov random strings that are hard for the halting for Turing reductions but not under many-one reductions.<br />
<br />
<b>Bill: </b>Everything reminds you of the Kolmogorov strings.<br />
<br />
<b>Lance: </b>As they should.<br />
<br />
<b>Bill: </b>I liked Michal Koucký's talk on <a href="http://dx.doi.org/10.4230/LIPIcs.ESA.2018.12">Gray codes</a>.<br />
<br />
<b>Lance: </b>Shouldn't that be grey codes. We're not in the UK.<br />
<br />
<b>Bill: </b>It's the color you moron. It's named after Frank Gray.<br />
<br />
<b>Lance: </b>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.<br />
<br />
<b>Bill: </b>I never put Lance and sports in the same sentence before.<br />
<br />
<b>Lance: </b>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.<br />
<br />
<b>Bill: </b>Which contrasts Raskin's <a href="http://dx.doi.org/10.4230/LIPIcs.ICALP.2017.88">2017 paper</a> that shows with a binary alphabet you need to query at least half the bits.<br />
<br />
<b>Lance: </b>Hey you stole my line.<br />
<br />
<b>Bill: </b>That's not possible. You are editing this. I think this typecast has gone long enough. Take us out.<br />
<br />
<b>Lance: </b>In a complex world, best to keep it simple.https://blog.computationalcomplexity.org/2018/09/still-typecasting-from-dagstuhl.htmlnoreply@blogger.com (Lance Fortnow)4tag:blogger.com,1999:blog-3722233.post-4546994761118452429Tue, 25 Sep 2018 06:32:00 +00002018-09-27T00:39:13.199-04:00Lance and Bill go to Dagstuhl: The Riemann Edition<b>Lance: </b>Welcome to our typecast directly from Dagstuhl in Southwestern Germany for the 2018 edition of the seminar on <a href="https://www.dagstuhl.de/en/program/calendar/semhp/?semnr=18391">Algebraic Methods in Computation Complexity</a>. Say hi Bill.<br />
<br />
<b>Bill: </b>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.<br />
<br />
<b>Lance: </b>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 <a href="https://www.youtube.com/watch?v=jXugkzFW5qY">video</a>, some <a href="https://twitter.com/mpoessel/status/1044131977950109696">twitter</a> <a href="https://twitter.com/aperiodical/status/1044132699605274624">threads</a> and the <a href="https://drive.google.com/file/d/17NBICP6OcUSucrXKNWvzLmrQpfUrEKuY/view">paper</a>.<br />
<br />
<b>Bill: </b>Too bad. When I first heard about the claim I was optimistic because (1) László Babai <a href="http://people.cs.uchicago.edu/~laci/update.html">proved</a> 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)<br />
<br />
<b>Lance: </b>I'll be too busy writing the great American novel. Before we leave this topic, don't forget about the rest of the <a href="https://www.heidelberg-laureate-forum.org/event_2018/">Laureate Forum</a>, loads of great talks from famous mathematicians and computer scientists. Why didn't they invite you Bill?<br />
<br />
<b>Bill: </b>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.<br />
<br />
<b>Josh: </b>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.<br />
<br />
<b>Bill: </b>So Josh, what do you have to say about matrix multiplication. Is is quadratic time yet?<br />
<br />
<b>Josh: </b>Not yet and <a href="https://arxiv.org/abs/1712.07246">we show</a> all the current technique will fail.<br />
<br />
<b>Bill: </b>Wouldn't Chris Umans disagree?<br />
<br />
<b>Kathryn Fenner: </b>You shouldn't pick on Canadians [Ed note: Josh is from Toronto]. Pick on students from your own country.<br />
<br />
<b>Josh: </b>(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.<br />
<br />
<b>Chris: </b>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.<br />
<br />
<b>Lance: </b>Thanks Chris. Josh, what are your impressions of Dagstuhl so far?<br />
<br />
<b>Josh: </b>I like the sun and grass. I wish it was easier to get here.<br />
<br />
<b>Lance: </b>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 <a href="https://www.dagstuhl.de/en/program/calendar/semhp/?semnr=9206">first Dagstuhl</a> back in February of 1992.<br />
<br />
<b>Josh: </b>Two months before I was born.<br />
<br />
<b>Lance: </b>Way to make me feel old.<br />
<br />
<b>Bill: </b>You are old.<br />
<br />
<b>Lance: </b>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.<br />
<br />
<b>Bill: </b>What did I sleep through this morning before Josh's talk?<br />
<br />
<b>Lance: </b>Amnon Ta-Shma talked about his <a href="http://www.cs.tau.ac.il/~amnon/Papers/T.STOC17.pdf">STOC 2017 best paper</a> and Noga Ron-Zewi showed some <a href="https://sites.google.com/site/nogaronzewi1/main.pdf">new results</a> on constructive list-decoding.<br />
<br />
<b>Bill: </b>Let's do this again later in the week. Lance, takes us out.<br />
<br />
<b>Lance: </b>In a complex world, best to keep it simple.https://blog.computationalcomplexity.org/2018/09/lance-and-bill-go-to-dagstuhl-riemann.htmlnoreply@blogger.com (Lance Fortnow)3tag:blogger.com,1999:blog-3722233.post-1443716079788493732Thu, 20 Sep 2018 12:19:00 +00002018-09-20T08:19:28.031-04:00Why wasn't email built securely?Recently I talked with Ehsan Hoque, one of the authors of the <a href="https://acm-fca.org/2018/03/29/negativeimpacts/">ACM Future of Computing Academy</a> report that suggested "Peer reviewers should require that papers and proposals rigorously consider all reasonable broader impacts, both positive and negative." which I had <a href="https://blog.computationalcomplexity.org/2018/05/broader-impacts-redefined.html">satirized</a> last May.<br />
<br />
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?<br />
<br />
Email goes back to the 60's but I did get involved on the early side when I <a href="https://blog.computationalcomplexity.org/2011/06/creating-email-system-at-cornell.html">wrote</a> an email system for Cornell in the early 80's. So let me take a crack at answering that question.<br />
<br />
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.<br />
<br />
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.<br />
<br />
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.<br />
<br />
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.https://blog.computationalcomplexity.org/2018/09/why-wasnt-email-built-securely.htmlnoreply@blogger.com (Lance Fortnow)7tag:blogger.com,1999:blog-3722233.post-1400950914749406777Mon, 17 Sep 2018 04:23:00 +00002018-09-18T20:16:12.198-04:00What is a Physicist? A Mathematician? A Computer Scientist? Scott Aaronson recently won the Tomassoni-Chisesi Prize in Physics (yeah Scott!).<br />
In his post (<a href="https://www.scottaaronson.com/blog/?p=3955">here</a>) about it he makes a passing comment:<br />
<div>
<br /></div>
<div>
<i>I'm of course not a physicist</i></div>
<div>
<i><br /></i></div>
<div>
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:<br />
<br />
Is X a Y?<br />
<br />
(We will also consider why we care, if we do.)<br />
<br />
Some criteria below. Note that I may say thinks like `Dijkstra is obviously a computer scientist'<br />
but this is cheating since my point is that it may be hard to tell these things (though I think he is).</div>
<div>
<br /></div>
<div>
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')<br />
<br />
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.<br />
<br />
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.<br />
<br />
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<br />
<br />
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 <a href="https://blog.computationalcomplexity.org/2012/06/ketchup-problem.html#comment-form">the Ketchup problem</a> that does not make him a mathematician.<br />
<br />
6) What X is working on right now. Fine but might change. And some work is hard to classify.<br />
<br />
7) If you win an award in X, then you are an X. Some exceptions<br />
<br />
Scott is a computer scientist who won the Tomassoni-Chisesi Physics Prize<br />
<br />
Ed Witten is a Physicist who won the Fields Medal (Math)<br />
<br />
John Nash is a mathematician who won a Nobel prize in Economics.<br />
<br />
I want to make a full circle- so if you know other X won a prize in Y then leave a comment and<br />
we'll see what kind of graph we get. Bipartite with people on one side and fields on the other.<br />
<br />
8) What they can teach? Helpful in terms of hiring when you want to fill teaching needs.<br />
<br />
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.<br />
<br />
<br /></div>
https://blog.computationalcomplexity.org/2018/09/what-is-physicist-mathematician.htmlnoreply@blogger.com (GASARCH)9tag:blogger.com,1999:blog-3722233.post-1145574781456662669Thu, 13 Sep 2018 12:08:00 +00002018-09-13T08:08:01.012-04:00P = NP and CancerOften 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.<br />
<br />
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:<br />
<ol>
<li>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.</li>
<li>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.</li>
<li>Use P = NP to find the protein sequence that the circuit from #2 will output the shape from #1.</li>
</ol>
We'll need an truly efficient algorithm for NP problems for this to work. A n<sup>50</sup> algorithm for SAT won't do the job. All this steps may happen whether or not P = NP but we'll need some new smart algorithmic ideas.<div>
<br /><div>
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". <ul>
</ul>
</div>
</div>
https://blog.computationalcomplexity.org/2018/09/p-np-and-cancer.htmlnoreply@blogger.com (Lance Fortnow)16tag:blogger.com,1999:blog-3722233.post-5181058559426562177Tue, 11 Sep 2018 16:11:00 +00002018-09-11T13:48:35.347-04:00The Tenure system is broken but not in the way that you think (Anon Guest Post)<br />
This is an ANON guest post. Even I don't know who it is! They emailed me asking if they<br />
could post on this topic, I said I would need to see the post. I did and it was fine.<br />
<br />
-----------------------------------------------------------------------------------------------------------------<br />
I have written many tenure/promotion letters before. But this summer, I was especially inundated with requests. Thinking about my past experiences with such letters, I started to question their value.<br />
<br />
For those unfamiliar with the process, let me explain. When someone is applying for a research job, they typically need to have recommendation letters sent on their behalf. Once someone is hired in<br />
a tenure-track position, they then need to get additional letters each time they are promoted (in the US, this will typically occur when someone is granted tenure and again when they are promoted to full<br />
professor).<br />
<br />
Now, I know from experience that recommendation letters are scrutinized very carefully, and often contain useful nuggets of information. I am not questioning the value of such letters (though<br />
they may have other problems). I am focusing here only on tenure/promotion letters.<br />
<br />
Let me fill in a bit more detail about the tenure/promotion process,since it was a mystery to me before I started an academic position. (I should note that everything I say here is based only on how things are<br />
done at my institution; I expect it does not differ much at other US universities, but it may be different in other countries.) First, the department makes a decision as to whether to put forward someone's<br />
case for promotion. If they do, then a package is prepared that includes, among other things, the external recommendation letters I am talking about. After reviewing the candidate's package, the department holds an official vote; if positive, then the package is reviewed and<br />
voted on by higher levels of administration until it is approved by the president of the university.<br />
<br />
The external letters appear very important, and they are certainly discussed when the department votes on the candidate's case. However, I am not aware of any cases (in computer science) where someone who was put forward for tenure was denied tenure. (In contrast, I am aware of a very small number cases where a department declined to put someone forward for tenure. In such cases, no letters are ever<br />
requested.) Perhaps more frustrating, this seems to be the case even when there are negative letters. In fact, I have written what I consider to be "negative" letters in the past only to see the candidate still get tenure.(To be clear, by academic standards a negative letter does not mean saying anything bad, it just means not effusively praising the candidate.) This makes be believe that these letters are simply being used as "checkboxes" rather than real sources of information to take into account during the decision-making process. Essentially, once a department has decided to put someone forward for promotion, they have effectively also decided to vote in favor of their promotion.<br />
<br />
Letters take a long time to write, especially tenure/promotion letters, and especially when you are not intimately familiar with someone's work (even if they are in the same field). But if they are<br />
basically ignored, maybe we can all save ourselves some time and just write boilerplate letters (in favor of tenure) instead?<br />
￼<br />
￼<span style="white-space: pre;"> </span><br />
￼https://blog.computationalcomplexity.org/2018/09/the-tenure-system-is-broken-but-not-in.htmlnoreply@blogger.com (GASARCH)5tag:blogger.com,1999:blog-3722233.post-8190535592855353285Thu, 06 Sep 2018 13:01:00 +00002018-09-06T09:01:09.223-04:00Are Conferences Discriminatory? Glencora Borradaile wrote a <a href="http://blogs.oregonstate.edu/glencora/2018/07/02/discrimination-and-the-conference-publication-system/">blog post</a> in June about how conferences discriminate.<br />
<blockquote class="tr_bq">
Let me spell it out. In order to really succeed in most areas of computer science, you need to publish conference papers and this, for the most part, means attendance at those conferences. But because of the institutional discrimination of border control laws and the individual discrimination that individuals face and the structural discrimination that others face, computer science discriminates based on nationality, gender identity, disability, and family status, just to name a few aspects of identity.</blockquote>
Suresh Venkatasubramanian follows up with a <a href="https://twitter.com/geomblog/status/1015267584432721921">tweet storm</a> (his words) echoing Glencora's points.<br />
<blockquote class="twitter-tweet" data-conversation="none" data-lang="en">
<div dir="ltr" lang="en">
Is there structural (i.e not intentional or institutional) bias in how conferences operate? I.e is there a systematic and persistent disadvantage to certain groups from how conferences are structured? If we consider location, and groups = non-US people, then yes.</div>
— Suresh Venkatasubramanian (@geomblog) <a href="https://twitter.com/geomblog/status/1015267585460334592?ref_src=twsrc%5Etfw">July 6, 2018</a></blockquote>
<script async="" charset="utf-8" src="https://platform.twitter.com/widgets.js"></script>
Ryan Williams had a <a href="https://twitter.com/rrwilliams/status/1015642178243256322">twitter thread</a> defending conferences.<br />
<blockquote class="twitter-tweet" data-conversation="none" data-lang="en">
<div dir="ltr" lang="en">
Because of where I live and work, I can collaborate with and see talks by many more people than the average person in my field. To me, conferences serve as a way of *leveling* that field, giving a venue where people from all over can benefit similarly.</div>
— R. Ryan Williams (@rrwilliams) <a href="https://twitter.com/rrwilliams/status/1015642195733303298?ref_src=twsrc%5Etfw">July 7, 2018</a></blockquote>
Not much difference these day between blog posts, tweet storms and twitter threads and I recommend you read through them all.<br />
<br />
Much as I think conferences <a href="https://cacm.acm.org/magazines/2009/8/34492/fulltext">should not serve as publication venues</a>, they do and should play a major role in connecting people within the community. We should do our best to mitigate the real concerns of Glencora and Suresh, create an environment that everyone feels comfortable, have travel support and child care to make it easier and have meetings in different countries so those with visa issues can still attend at times. But we cannot eliminate the conference without eliminating the community. Personal interactions matter.<br />
<script async="" charset="utf-8" src="https://platform.twitter.com/widgets.js"></script>
https://blog.computationalcomplexity.org/2018/09/are-conferences-discriminatory.htmlnoreply@blogger.com (Lance Fortnow)8tag:blogger.com,1999:blog-3722233.post-3039314567814802636Tue, 04 Sep 2018 02:46:00 +00002018-09-04T08:35:06.843-04:00The Rule of Threes/AstrologyOn Aug 16, 2018 Aretha Franklin died. A famous singer.<br />
<br />
On Aug 18 2018 Kofi Anan died. A famous politician.<br />
<br />
On Aug 25, 2018 John McCain died. A famous politician.<br />
<br />
On Aug 26, 2018 Neil Simon died, a famous playwright.<br />
<br />
For 12 famous people who died between Aug 5 and Aug 26 see <a href="http://www.tributes.com/celebrity/deaths/today">here</a> (be careful- there are a few more on the list who died in August but a different year).<br />
<br />
One could group those 12 into four sets of three and claim the<i> rule of threes</i> that celebrities die in threes. There was an episode of <i>30 Rock</i> where two celebrities had died and Tracy Jordan (a celeb) tried to kill a third one so he would not be a victim of the<i> rule of threes</i>. (see the short video clip: <a href="https://vimeo.com/151801153">here</a>.)<br />
<br />
How would one actually test the rule of threes? We would need to define the rule carefully. I have below a well defined rule, with parameters you can set, and from that you could do data collection (this could be a project for a student though you would surely prove there is no such rule).<br />
<br />
<ol>
<li>Decide on a definite time frame: T days. The deaths only count if they are within T days.</li>
<li>Define celebrity. This may be the hardest part. I'll start with they must have a Wikipedia page of length W and they must have over H hits on Google. This may be hard to discern for people with common names or alternative spellings. You might also look into Friends on Facebook and Followers on Twitter. A big problem with all of this is that if you want to do a study of old data, before there was Google, Wikipedia, Facebook, and Twitter, you will need other criteria (ask your grandparents what it was like in those days).</li>
<li>Decide whether or not to have a cutoff on age. You may decide that when Katherine Hepburn, Bob Hope, and Strom Thurmond died less than a month apart, at the ages of 96, 100, 100 this doesn't qualify. Hence you may say that the celebrities who die must be younger than Y years.</li>
</ol>
<br />
I doubt anybody will ever do the experiment--- those that believe its true (are there really such people?) have no interest in defining it carefully or testing it. And people who don't believe would not bother, partially because so few people believe it that its not worth debunking. But I wonder if a well thought out experiment might reveal something interesting. Also contrast the data to all deaths and see if there is a difference. For example, you might find that more celebs die in August then would be expected based on when all people die. Or that celebs live longer. Or shorter. Actually with enough <a href="https://en.wikipedia.org/wiki/Data_dredging">p-hacking</a> I am sure you could find something. But would you find something meaningful?<br />
<br />
Astrology is in the same category- people who believe (there ARE such people!) could do well defined experiments but have no interest in doing so. I doubt they would find anything of interest if they did. Here there are enough people who believe it in to be worth debunking, but would a well designed science experiment convince them that astrology does not have predictive powers? Has such been done?<br />
<br />
<br />
I once DID do such an experiment to disprove a wild theory. In 2003 a cab driver once told me (1) there is no Gold in Fort Know, and Ian Fleming was trying to tell us this in the book Goldfinger, (2) Reagan was shot since he was going to tell, (3) a small cohort of billionaires runs the world. I challenged him-- if that is the case then how come in 1992 Bill Clinton beat George Bush, who was surely the billionaires pick. He responded that Bill Clinton was a Rhodes Scholar and hence he is in-the-club. I challenged him- OKAY, predict who will get the Democratic Nomination in 2004. This was a well defined experiment (though only one data point) He would give me a prediction and I could test it. He smiled and said <i>Wesley Clark was a Rhode Scholar.</i> Oh well.<br />
<br />https://blog.computationalcomplexity.org/2018/09/the-rule-of-threesastology.htmlnoreply@blogger.com (GASARCH)8tag:blogger.com,1999:blog-3722233.post-1498140012370196567Thu, 30 Aug 2018 13:25:00 +00002018-08-30T09:25:44.291-04:00What is Data Science?The <a href="https://simons.berkeley.edu/">Simons Institute</a> at Berkeley has two semester long programs this fall, <a href="https://simons.berkeley.edu/programs/complexity2018">Lower Bounds on Computational Complexity</a> and <a href="https://simons.berkeley.edu/programs/datascience2018">Foundations of Data Science</a>. The beginning of each program features a "boot camp" to get people up to speed in the field, <a href="https://simons.berkeley.edu/workshops/schedule/6596">complexity</a> last week and <a href="https://simons.berkeley.edu/workshops/schedule/6680">data science</a> this week. Check out the links for great videos on the current state of the art.<br />
<div>
<br /></div>
<div>
Data Science is one of those terms you see everywhere but not well understood. Is the the same as machine learning? Data analytics? Those pieces only play a part of the field.<br />
<br /></div>
<div>
Emmanuel Candès, a Stanford statistician, gave a great description during his keynote talk at the recent <a href="http://acm-stoc.org/stoc2018/">STOC theoryfest</a>. I'll try to paraphrase.</div>
<div>
<br /></div>
<div>
The basic scientific method works as follows: You make an hypothesis consistent with the world as you know it. Design an experiment that would distinguish your hypothesis from the current models that we have. Run the experiment and accept, reject or refine your hypothesis as appropriate. Repeat.</div>
<div>
The <a href="https://home.cern/topics/higgs-boson">Higgs Boson</a> followed this model as a recent example.<br />
<br />
Technological Advances have given us a different paradigm.<br />
<ol>
<li>Our ability to generate data has greatly increased whether it be from sensors, DNA, telescopes, computer simulations, social media and oh so many other sources.</li>
<li>Our ability to store, communicate and compress this data saves us from having to throw most of it away.</li>
<li>Our ability to analyze data through machine learning, streaming and other analysis tools has greatly increased with new algorithms, faster computers and specialized hardware.</li>
</ol>
</div>
<div>
All this data does not lend itself well to manually creating hypotheses to test. So we use the automated analysis tools, like ML, to create models of the data and use other data for testing those hypotheses. Data science is this process writ large.<br />
<br />
We are in the very early stages of data science and face many challenges. Candès talked about one challenge: how to prevent false claims that arise from the data not unrelated to the current <a href="https://www.nature.com/news/1-500-scientists-lift-the-lid-on-reproducibility-1.19970">reproducibility crisis</a> in science.<br />
<br />
We have other scientific issues. How can we vouch for the data itself and what about errors in the data? Many of the tools remain adhoc, how can we get theoretical guarantees? Not to mention the various ethical, legal, security, privacy and fairness issues that vary in different disciplines and nations.<br />
<br />
We sit at a time of exciting change in the very nature of research itself, but how can we get it right when we still don't know all the ways we get it wrong. </div>
https://blog.computationalcomplexity.org/2018/08/what-is-data-science.htmlnoreply@blogger.com (Lance Fortnow)0tag:blogger.com,1999:blog-3722233.post-5599223705654002765Mon, 27 Aug 2018 22:36:00 +00002018-08-27T18:36:34.800-04:00Is Trivium (the Stream Cipher) used?This Fall I am teaching the senior course in Crypto at UMCP. Its a nice change of pace for me since REAL people REALLY use this stuff! Contrast to last Spring when I taught<br />
<br />
<i>Ramsey Theory and its `Applications'</i><br />
<br />
There is one topic in the Crypto course that LOOKS really useful but I can't tell if it IS being used, so I inquire of my readers. (I will probably come across others topics like that in the future.)<br />
<br />
A Secure Stream Cipher is (informally) a way to, given a seed and optionally an Init Vector (IV), generate bits that look random. Alice and Bob communicate the seed either in person or over a private channel or perhaps by using RSA (or some other public key system) and they then both effectively have a very long string of random bits. They send the IV in the clear. They can then do one-time-pad (really a psuedo-one-time-pad). There are other uses for random-looking bits as well.<br />
<br />
So what is needed is a Secure Stream Cipher. <i>Trivium</i> seems to be one such. According to <a href="http://www.thefullwiki.org/Trivium_(cipher)">the Trivium wiki</a><br />
<br />
<i>It was submitted to the Profile II (hardware) of the eSTREAM compeition by its authors Christophe De Canniere and Bart Preneel, and has been selected as part of the portfolio for low area hardware ciphers (Profile 2) by the eSTREAM project. It is not patented.</i><br />
<i><br /></i>
According to these papers: <a href="http://www.ecrypt.eu.org/stream/p3ciphers/trivium/trivium_p3.pdf">here</a> and <a href="http://www.ecrypt.eu.org/stream/papersdir/2006/021.pdf">here</a>, and the Wikipedia entry, <a href="https://en.wikipedia.org/wiki/Trivium_(cipher)">here</a> the following are true:<br />
<br />
1) Trivium takes an 80 bits seed and an 80 bit IV<br />
<br />
2) The implementation is simple and is already in hardware. Around 3000 logic gates.<br />
<br />
3) There are reasons to think its random-looking but no rigorous proof.<br />
<br />
4) So far it has not been broken, though its not clear how many people have tried. Thats goes to my question-- how widely used it is it?<br />
<br />
5) Trivium need 1152 steps in the init phase. If it only does 799 then <a href="https://en.wikipedia.org/wiki/Cube_attack">The Cube Attack</a> can break it in 2^68 which is better than the naive algorithm of trying every key and IV (2^160) but still not feasible.<br />
<br />
6) Trivium is also <a href="https://en.wikipedia.org/wiki/Trivium_(band)">An American Metal Band</a> and a <a href="https://en.wikipedia.org/wiki/Trivium">Medieval theory of education</a>. Its a good name for a band. See my post <a href="https://blog.computationalcomplexity.org/search?q=red+cliques">What Rock Band Name Would you Choose</a>? for fictional good names for bands with a math or theoretical cs connection.<br />
<br />
OKAY, back to the main topic:<br />
<br />
SO my questions:<br />
<br />
Is Trivium used?<br />
<br />
If so then by whom and for what (for the psuedo 1-time pad?) ?<br />
<br />
If not then why not (e.g., some of of my points above are incorrect)? and should it be instead<br />
of what is being used?<br />
<div>
<br /></div>
<br />
<br />
<br />https://blog.computationalcomplexity.org/2018/08/is-trivium-stream-cipher-used.htmlnoreply@blogger.com (GASARCH)5tag:blogger.com,1999:blog-3722233.post-5929613958480345298Sun, 26 Aug 2018 12:57:00 +00002018-08-26T08:57:06.961-04:00Katherine Johnson (1918-)<a href="https://www.nasa.gov/sites/default/files/styles/side_image/public/thumbnails/image/26646856911_ca242812ee_o_1.jpg?itok=NQu4uW0H" imageanchor="1" style="clear: right; float: right; margin-bottom: 1em; margin-left: 1em;"><img border="0" data-original-height="483" data-original-width="320" height="320" src="https://www.nasa.gov/sites/default/files/styles/side_image/public/thumbnails/image/26646856911_ca242812ee_o_1.jpg?itok=NQu4uW0H" width="211" /></a><a href="https://www.nasa.gov/content/katherine-johnson-biography">Katherine Johnson</a> is celebrating her 100th birthday today. This is the first centenary post we've done for a living person.<br />
<br />
The movie <a href="https://www.imdb.com/title/tt4846340/">Hidden Figures</a> made her story famous: In 1952, she joined NACA, the predecessor of NASA, in the all-black West Area Computing section of the Langley lab in Virginia. During the "space race" of the 50's and 60's she worked on trajectory analysis for the early human spaceflights. In 1960, she was the first woman to co-author a <a href="https://ntrs.nasa.gov/archive/nasa/casi.ntrs.nasa.gov/19980227091.pdf">technical report</a> for NASA on placing satellites over a specific latitude and longitude.<br />
<br />
The West Area Computing section had human computers working on the critical calculations for air and space travel. Soon NASA started moving that work to IBM machines but much as we don't fully trust machine learning today, humans didn't initially trust these computers. John Glenn's first orbital mission required complex calculations to track his flight. He insisted on Katherine Johnson working out the computations herself, which she did. "If she says they're good then I'm ready to go".<br />
<br />
In 2015, then President Obama awarded Katherine Johnson the highest US civilian honor, the Presidential Medal of Freedom.https://blog.computationalcomplexity.org/2018/08/katherine-johnson-1918.htmlnoreply@blogger.com (Lance Fortnow)0tag:blogger.com,1999:blog-3722233.post-3538208001969555413Thu, 23 Aug 2018 13:23:00 +00002018-08-23T09:23:51.543-04:00The Zero-One Law for Random Oracles<a href="https://blog.computationalcomplexity.org/2015/04/ph-infinite-under-random-oracle.html">A couple of years ago</a>, Rossman, Servedio and Tan showed that the polynomial-time hierarchy is infinite relative to a random oracle. That is if you choose each string independently to be in or out of an oracle R with probability one, the polynomial-time hierarchy will be infinite relative to R with probability one. This is one in the measure theory sense, there are oracles where it is false, it is just that those oracles will occur with zero probability.<br />
<br />
There are still a few open questions for random oracles, such as whether P = BQP, quantum and classical computing can solve the same problems efficiently.. We suspect that P is different than BQP relative to a random oracle because otherwise BQP would be the same as BPP unrelativized (and thus factoring is easy), but we have no proof. Could it be possible that this problem has no simple resolution, that P = BQP holds with probability 1/2 relative to a random oracle, or some other probability strictly between 0 and 1? As it turns out no.<br />
<br />
Some statements do hold with intermediate probabilities. The sentence "0101 in R" holds with probability 1/2. Even for a fixed machine M, questions like "M<sup>R</sup> accepts an infinite language" could hold with probability say 3/8.<br />
<br />
But statements like P = BQP relative to R can't happen with intermediate probability. That's due to the <a href="https://en.wikipedia.org/wiki/Kolmogorov%27s_zero%E2%80%93one_law#Examples">Kolmogorov zero-one law</a>. If you have a subset of oracles that are closed under finite differences, that set must occur with probability zero or one. Every statement about complexity classes has that property because we can hard wire finite differences of the oracle into the machine description without increasing the running time. It will change the machine but not the complexity class. So P = BQP holds with probability zero or one even though we can't tell which one yet.<br />
<br />
The Kolmogorov zero-one law gives us a consistent look at complexity classes. Since the countable union of zero probability events still has probability zero, every finitely-described statement about complexity classes that hold with probability one, all simultaneously hold with probability one. While this random world <a href="https://doi.org/10.1016/S0022-0000(05)80084-4">does not match</a> the unrelativized one, it does give us a relativized world where we can explore the different possible relationships between complexity classes.https://blog.computationalcomplexity.org/2018/08/the-zero-one-law-for-random-oracles.htmlnoreply@blogger.com (Lance Fortnow)1tag:blogger.com,1999:blog-3722233.post-4363069041026174846Mon, 20 Aug 2018 04:09:00 +00002018-08-21T11:51:27.385-04:00Fractional Problems: 2.1-colorable, 2.8-SATSome graphs are 2-colorable, some graphs are 3-colorable, some graphs are...Does it make sense to say that a graph is 2.1-colorable? It does!(Source_ Factional Graph Theory by Schneinerman and Ullman-- I saw a talk on this by Jim Propp a long time ago.)<br />
<br />
Def 1: A graph is (a,b)-colorable (with a \ge b) if you can assign to every vertex a set of b numbers from {1,...,a} such that if u and v are adjacent then the set of numbers are disjoint. Note that k-colorable is (k,1)-colorable. Let chi_b(G) be the least a such that G is (a,b)-col.<br />
The fractional chrom num of G is lim_{b-->infinity} chi_b(G)/b.<br />
<br />
Def 3: We restate the ordinary Chrom Number problem as an integer program (and NOT by using that<br />
Chrom Num \le SAT \le IP). In fact, our Int Prog will be LARGE. For every ind set I of G we have a 0-1 valued var x_I which will be 1 iff x_I is all one color. We want to minimize \Sum_I x_I with the constraint that, for every vertex v in the graph. sum_{v in I} x_I \ge 1, so every vertex is colored.<br />
: Fractional Chrom number is what you get if you relax the above IP to an LP with x_I in [0,1] instead of {0,1}.<br />
<br />
Defs 1 and 2 turn out to be equiv. The wikipedia entry on Fractional Chromatic Number (see <a href="https://en.wikipedia.org/wiki/Fractional_coloring">here</a>) is pretty good and has some applications to real world things.<br />
<br />
QUESTION: 2-col is in P, 3-col is NPC. What about, say, 2.1-col. It turns out that, for every c>2, c-col is NPC. <br />
<br />
Open question (which Jim Propp used to begin his lecture): Every planar graph is 5-col has an EASY proof. Every planar graph is 4-col has a HARD (or at least tedious) proof. Is there a nice proof that every planar graph is (say) 4.5-colorable? The answer is Yes, Every planar graph is 4.5 colorable. I blogged on it <a href="https://blog.computationalcomplexity.org/2015/10/a-human-readable-proof-that-every.html">here</a>.<br />
<br />
Are there other fractional problems related to NPC problems. YES- at a Dagstuhl there was a paper on (2+epsilon)-SAT. (by Austrin, Guruswami, Hastad) (see <a href="http://eccc.hpi-web.de/report/2013/159/">here).</a><br />
<br />
What is fractional SAT? Lets recall ordinary k-SAT: every clause has k literals and you need to make at least one of them true. What if you wanted to make at least 2 of them true? (a/b)-SAT is if every clause has exactly b literals and you want an assignment that makes at least a in each clause true.<br />
<br />
GOOD NEWS: for all epsilon, (2+epsilon) is NP-complete. Its not so much good that its true, but its good that its known.<br />
<br />
BAD NEWS: The proof is hard, uses lots of tools.<br />
<br />
ODD NEWS: The speaker said that they PROVED there was no easy proof.<br />
<br />
I think its worth having your students try to DEFINE these terms on their own. The NPC proofs may be over their heads (they may be over my head), but the definitions are nice and the students might be able to derive them.<br />
<br />
QUESTION: Do other NPC problems have Fractional versions? I would think yes. This could lead to a host of open problems OR perhaps they have already been asked. If you know of any, please comment.https://blog.computationalcomplexity.org/2018/08/fractional-problems-21-colorable-28-sat.htmlnoreply@blogger.com (GASARCH)3tag:blogger.com,1999:blog-3722233.post-8405648690074998060Thu, 16 Aug 2018 17:38:00 +00002018-08-17T07:22:51.078-04:00How valuable is a Fields Medal? (Johan Hastad won the Knuth Prize! The below post was written before I knew that but has a mild connection to it. See <a href="https://www.acm.org/media-center/2018/august/knuth-prize-2018">here</a> for more info on the Hastad winning it, or see Lance's tweet, or see Boaz's blog post <a href="https://windowsontheory.org/2018/08/16/johan-hastad-wins-knuth-prize/">here</a>. There will prob be other blogs about it as well. ADDED LATER: Lipton and Regan have a post on this <a href="https://rjlipton.wordpress.com/2018/08/16/winner-of-2018-knuth-prize-is/">here</a>.)<br />
<br />
<br />
<br />
<br />
The Fields Medal was recently awarded to<br />
<br />
Caucher Birkar<br />
<br />
Alessio Figalli<br />
<br />
Peter Scholze<br />
<br />
Akshay Benkatesh<br />
<br />
I was going to try to give one sentence about what they did, but Wikipedia does a better job than I ever could so I point there: <a href="https://en.wikipedia.org/wiki/Fields_Medal#Fields_medalists">here</a>. Terry Tao also has some comments on the Fields Medal <a href="https://terrytao.wordpress.com/2018/08/01/birkar-figalli-scholze-venkatesh/">here</a>. So does Doron Zeilberger <a href="http://sites.math.rutgers.edu/~zeilberg/Opinion168.html">here</a>.<br />
<br />
How much is a Fields medal worth?<br />
<br />
1) The winners get $15,000 each.<br />
<br />
2) Winning a Fields medal gets one a higher salary and the ability to change schools, so the $15,000 might not be the main monetary part. All Field Medalists are under 40 so the salary increases and such last for a much longer time then (say) a Nobel prize given for life achievements to someone much older. So you may rather win a Fields' medal when you are 39 than a Nobel when you are 70. The Abel prize is around 740,000 dollars and (I think) given for lifetime achievement so again, a Fields Prize may be better. (See <a href="https://en.wikipedia.org/wiki/Abel_Prize">here</a> for more on the Abel Prize). Which would I prefer to win? I would be delighted if that was my dilemma.<br />
<br />
3) I am sure that none of the four winners went into math because of the allure of the $15,000 Fields Medal.<br />
<br />
4) The title of this post is ambiguous. It can also be read as<br />
<br />
<i>how valuable is the actual medal?</i><br />
<i><br /></i>
The answer is $4000, much more than I would have thought. I only know this since it was recently stolen, see <a href="https://www.washingtonpost.com/news/worldviews/wp/2018/08/02/winner-of-top-mathematics-prize-has-medal-stolen-from-him-minutes-later/?utm_term=.5381b2018b53">here</a>.<br />
<br />
This raises a linguistic question. The four people above can say<br />
<br />
I WON a Fields Medal<br />
<br />
The thief can say<br />
<br />
I HAVE a Fields Medal<br />
<br />
and hope that people don't quite realize that he didn't earn it.<br />
<br />
(The article about the theft says the Fields medal is $11,500 dollars. Do they deduct the cost of the Medal itself? Or is the article wrong?)<br />
<i><br /></i>
<i><br /></i>https://blog.computationalcomplexity.org/2018/08/how-valuable-is-fields-medal.htmlnoreply@blogger.com (GASARCH)6tag:blogger.com,1999:blog-3722233.post-7186234639816352314Tue, 14 Aug 2018 13:45:00 +00002018-08-14T09:45:41.206-04:00While I Was AwayAfter the <a href="https://blog.computationalcomplexity.org/2018/07/complexity-in-oxford.html" target="_blank">Oxford Workshop</a> I enjoyed a two-week family vacation in Spain, where there was no rain in the plain, just <a href="https://www.nytimes.com/2018/08/04/world/europe/europe-heat-wave.html" target="_blank">very hot</a> up to 106℉. The old Spanish cities knew how to optimize for shade and breeze, more than I can say for Oxford.<br />
<br />
<div class="separator" style="clear: both; text-align: center;">
</div>
<a href="https://1.bp.blogspot.com/-l592asXXNA8/W3Lcyp4RjqI/AAAAAAABi7w/5OFMt-r-T4882fbTM6GDD4pNJgyzt-UDgCLcBGAs/s1600/nevanlinna.jpg" imageanchor="1" style="clear: right; float: right; margin-bottom: 1em; margin-left: 1em;"><img border="0" data-original-height="388" data-original-width="640" height="193" src="https://1.bp.blogspot.com/-l592asXXNA8/W3Lcyp4RjqI/AAAAAAABi7w/5OFMt-r-T4882fbTM6GDD4pNJgyzt-UDgCLcBGAs/s320/nevanlinna.jpg" width="320" /></a>Meanwhile in a more moderate Brazilian climate, the <a href="https://www.icm2018.org/portal/en/home" target="_blank">International Congress of Mathematicians</a> awarded their medals, including the Rolf Nevanlinna Prize to <a href="https://www.mathunion.org/imu-awards/rolf-nevanlinna-prize/rolf-nevanlinna-prize-2018" target="_blank">Constantinos Daskalakis</a> in a year with several very strong candidates. The Nevanlinna prize gets awarded every four years to a researcher under 40 for contributions to mathematical aspects of information sciences. Costis was the then-student author of the 2004 <a href="https://blog.computationalcomplexity.org/2014/05/favorite-theorems-equilibrium.html" target="_blank">Nash Equilbrium is PPAD-complete</a> result and has gone on to be a leader in the algorithmic game theory community.<br />
<br />
The ICM also distributes the Fields Medal, the highest honor in mathematics. <a href="https://www.nytimes.com/2018/08/01/science/fields-medals-mathematics.html" target="_blank">Much ado</a> is given to Peter Scholze who received the award this year at the age of thirty though remember that Alexander Razborov received his Nevanlinna prize at the age of 27 in 1990. Caucher Birkar also received the Fields Medal at the more standard age of 40 but had it for only a few minutes before it was literally <a href="https://www.nytimes.com/2018/08/02/world/europe/fields-medal-theft-caucher-birkar.html" target="_blank">stolen away</a>.<br />
<br />
I didn't realize how much I appreciate the convenience of Uber and Lyft until I had to get around cities where they don't exist. Meanwhile New York <a href="https://www.nytimes.com/2018/08/08/nyregion/uber-vote-city-council-cap.html" target="_blank">started to limit</a> ride-sharing vehicles and I arrived in Madrid to a taxi strike protesting Uber in that city. The Yin and Yang of technology.<br />
<br />https://blog.computationalcomplexity.org/2018/08/while-i-was-away.htmlnoreply@blogger.com (Lance Fortnow)1tag:blogger.com,1999:blog-3722233.post-6775816584620815277Wed, 08 Aug 2018 03:37:00 +00002018-08-08T09:11:45.032-04:00The Future of TCS Workshop, celebrating V Vazirani 60th, now online<br />
<div style="background-color: white; color: #222222; font-family: arial, sans-serif; font-size: 12.8px;">
On June 29, 2018, a workshop was held, in conjunction with STOC 2018, to celebrate the accomplishments of Vijay Vazirani on the <span style="font-size: 12.8px;">occasion of his 60th birthday, organized by his PhD students, Aranyak Mehta, Naveen Garg and Samir Khuller. </span><span style="font-size: 12.8px;">The workshop was called "TCS: Looking into the Future" and true to the title, it was precisely that! In front of a large, enthusiastic </span><span style="font-size: 12.8px;">audience, left over from STOC, the star-studded lineup of speakers outlined some of the most avant-garde, far out ideas </span><span style="font-size: 12.8px;">on the future of computing. Fortunately, this exciting and highly thought-provoking set of talks was recorded for posterity </span><span style="font-size: 12.8px;">and is available for all to view </span><a href="https://www.cs.umd.edu/users/samir/stoc2018/" style="font-size: 12.8px;">her</a><span style="font-size: 12.8px;">e</span><br />
<span style="font-size: 12.8px;">THE LAST WORD `here' IS THE LINK to the website which has links to the four talks.</span></div>
<div style="background-color: white; color: #222222; font-family: arial, sans-serif; font-size: 12.8px;">
<blockquote style="font-size: 12.8px;" type="cite">
<div style="word-wrap: break-word;">
<div style="font-family: Menlo; font-size: 14px; margin: 0px;">
The speakers were:<span class="m_4037453103701832362gmail-m_5420954052706171597Apple-tab-span" style="white-space: pre-wrap;"> </span></div>
<div style="font-family: Menlo; font-size: 14px; margin: 0px; min-height: 16px;">
<blockquote style="font-family: arial, sans-serif; font-size: 12.8px;" type="cite">
<div style="word-wrap: break-word;">
<div style="font-family: Menlo; font-size: 14px; margin: 0px;">
Len Adleman, Manuel Blum, <span style="color: #500050;">Richard Karp, </span><span style="color: #500050;">Leonard<span style="white-space: pre-wrap;"> </span></span><span style="color: #500050;">Schulman, </span><span style="color: #500050;">Umesh Vazirani.</span></div>
</div>
</blockquote>
</div>
</div>
</blockquote>
<br />
1) I URGE you to all WATCH those talks!<br />
<br />
2) I really like it when talks are available on line after the fact so even if you didn't go (I didn't) you can still see the talks later.<br />
<br />
3) So many talks to watch, so little time, alas!<br />
<br />
4) Sorry for the white background for this post- that happens sometimes. NO comments on it please.<br />
<br />
<br />
<br />
<br /></div>
https://blog.computationalcomplexity.org/2018/08/the-future-of-tcs-workshop-celebrating.htmlnoreply@blogger.com (GASARCH)5tag:blogger.com,1999:blog-3722233.post-7489278706488122204Wed, 01 Aug 2018 20:50:00 +00002018-08-02T10:48:06.333-04:00Three trick questions in Formal Lang TheoryThere are three questions I ask in my Formal Lang Theory class that even the very best students get wrong. Two I knew were trick quesions, the other I was surprised by<br />
<br />
1) If w is a string then SUBSEQ(w) is all strings you can form by replacing some symbols in w<br />
with empty string. SUBSEQ(L) is defined in the obv way.<br />
<br />
I ask the following in class (not on an exam). TRUE or FALSE and WHY and we'll discuss<br />
If L is regular then SUBSEQ(L) is regular<br />
If L is context free then SUBSEQ(L) is context free<br />
If L is decidable then SUBSEQ(L) is decidable<br />
If L is c.e. (used to be called r.e.) then SUBSEQ(L) is c.e.<br />
<br />
The students pretty much get and prove that 1,2, and 4 are TRUE. They all think 3 is false.<br />
But is true. For a strange reason<br />
<br />
If L is ANY lang whatsoever then SUBSEQ(L) is regular. Comes from wqo theory. For more on this see a blog post I did when I was a guest blogger (it shows- the typeface is terrible) <a href="https://blog.computationalcomplexity.org/2006/01/theorem-that-should-be-better-known.html">here</a><br />
<br />
2) How many states does and NFA need for { a^n : n \ne 1000} (or similar large numbers). ALL of the students think it takes about 1000 states. They are wrong: <a href="https://blog.computationalcomplexity.org/2018/04/challenge-about-nfa-for-ay-yne-1000.html">here</a><br />
<br />
The two above I know people get wrong. The third one surprised me, yet every year the good students get it wrong<br />
<br />
3) BILL: We showed that<br />
a) 2-colorablility is in P, hence of course planar 2-colorability is in P<br />
b) 3-colorability is NP-complete<br />
c) 4-colorabilty of Planar graphs is in P<br />
<br />
SO what about 3-colorability of planar graphs?<br />
<br />
My very best student said the following last spring:<br />
<br />
Planar 2-col is in P<br />
<br />
Planar 4-col is in P<br />
<br />
so I would guess that Planar 3-col is in P.<br />
<br />
In prior years others made the same mistake. My opinion of these students is NOT lowered, but I am surprised they make that guess. Of course, once you KNOW something you have a hard time recovering the state of mind of NOT knowing it, so my being surprised says more about my having drunk the Kool aid then their thought patterns.<br />
<br />
<br />https://blog.computationalcomplexity.org/2018/08/three-trick-questions-in-formal-lang.htmlnoreply@blogger.com (GASARCH)8tag:blogger.com,1999:blog-3722233.post-7485569213345579704Fri, 27 Jul 2018 09:20:00 +00002018-07-27T05:21:15.764-04:00Complexity in OxfordOxford, England is in the middle of a heat wave and it handles high temperatures about as well as Atlanta handles snow. But that can't stop the complexity and a <a href="http://www.claymath.org/events/complexity-theory">wonderful workshop</a> this past week. It's my first trip to Oxford since I came <a href="https://blog.computationalcomplexity.org/2013/10/celebrating-maths-in-oxford.html">five years ago</a> to celebrate the opening of the Andrew Wiles building, a building that hosted this weeks' workshop as well.<br />
<br />
We also got a chance to see old math and physics texts. Here's Euclid's algorithm from an old printing of Euclid's Elements.<br />
<br />
<div class="separator" style="clear: both; text-align: center;">
<a href="https://2.bp.blogspot.com/-rYrGEM8V3eY/W1rjLLvLq2I/AAAAAAABhwA/ymX4vFZZjiYxNdQxWZGNEFy-X3C9GXo2wCKgBGAs/s1600/IMG_20180725_145610.jpg" imageanchor="1" style="margin-left: 1em; margin-right: 1em;"><img border="0" data-original-height="1600" data-original-width="1200" height="320" src="https://2.bp.blogspot.com/-rYrGEM8V3eY/W1rjLLvLq2I/AAAAAAABhwA/ymX4vFZZjiYxNdQxWZGNEFy-X3C9GXo2wCKgBGAs/s320/IMG_20180725_145610.jpg" width="240" /></a></div>
<br />
<div>
<br /></div>
<div>
Unlike a research conference, this workshop had several talks that gave a broader overview of several directions in complexity with a different theme each day.<br />
<br />
A few highlights of the many great talks.</div>
<div>
<br /></div>
<div>
Sasha Razborov gave a nice discussion of proof systems that help us understand what makes circuit bounds hard to prove. </div>
<div>
<br /></div>
<div>
Tuesday was a day for pseudorandomness, finding simple distributions that certain structure can't distinguish from random. Ryan O'Donnell talked about fooling polytopes (ANDs of weighted threshold functions). Avishay Tal talked about his <a href="https://blog.computationalcomplexity.org/2018/06/bqp-not-in-polynomial-time-hierarchy-in.html">new oracle with Ran Raz</a>, viewing it in this lens as a distribution that the low-depth circuit can't distinguish but quantum can. I talked about some simple extensions to Raz-Tal and the possibilities of using their techniques to show that you can't <a href="https://blog.computationalcomplexity.org/2005/12/pulling-out-quantumness.html">pull out quantumness</a> in relativized worlds.</div>
<div>
<br /></div>
<div>
Toni Pitassi talked about lifting--creating a tight connection between decision tree and </div>
<div>
complexity bounds to export lower bounds from one model to the other. Yuval Ishai talked about the continued symbiosis between complexity and theoretical cryptography.</div>
<div>
<br /></div>
<div>
Ryan Williams talked about his approach of using circuit satisfiability algorithms to prove lower bounds that led to his famed <a href="https://blog.computationalcomplexity.org/2010/11/breakthrough-circuit-lower-bound.html">NEXP not in ACC<sup>0</sup></a> result. He has had considerable recent progress including <a href="https://eccc.weizmann.ac.il/report/2017/188/">his recent work</a> with Cody Murray getting reducing NEXP to nondeterministic quasipolynomial time.<br />
<br />
Great to get away and just think complexity for a week. Seeing my former students Rahul Santhanam and Josh Grochow all grown up. And realizing I've become that old professor who regales (or bores) telling complexity stories from long ago. </div>
https://blog.computationalcomplexity.org/2018/07/complexity-in-oxford.htmlnoreply@blogger.com (Lance Fortnow)1tag:blogger.com,1999:blog-3722233.post-8298995692495359819Wed, 25 Jul 2018 13:16:00 +00002018-07-25T09:16:08.474-04:00Need EASY approaches to getting unif random from non-random sourcesTeaching crypto for the first time next semester I am looking into lots of stuff I always meant to look into but now I have to. NOT a complaint- good to be forced to expand my horizons (within TCS).<br />
<br />
I"m also finding out that the web is great for easy and hard stuff but not so good for medium stuff.<br />
<br />
Here is what I want to know so I am reaching out to my readers.<br />
<br />
KNOWN: you want to generate a unif rand seq of 0's and 1's. The bits you can generate are Independent (yeah) but biased (boo). So here is what you do: generate 2 at a time and<br />
<br />
if see 00 then DO NOT USE<br />
<br />
if see 11 then DO NOT USE<br />
<br />
if see 01 then generate 0<br />
<br />
if see 10 then generate 1<br />
<br />
KNOWN: You can do similar things if you have 00, 01, 10, 11 independent. And also if you have 000, 001, blah blah , 111 independent.<br />
<br />
I tried looking up if there is a better way and I came across some complicated papers. I need material for a senior course. So, are there INTERMEDIARY results Suitable for a classroom, on better ways to us an imperfect source to get unif rand?<br />
<br />
<br />
<br />
<br />
<br />https://blog.computationalcomplexity.org/2018/07/need-easy-approaches-to-getting-unif.htmlnoreply@blogger.com (GASARCH)11