tag:blogger.com,1999:blog-3722233Tue, 07 Apr 2020 04:40:33 +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)Blogger2745125tag:blogger.com,1999:blog-3722233.post-3272927110650993879Mon, 06 Apr 2020 21:36:00 +00002020-04-06T17:36:10.678-04:00Return of the VidcastBill and I just have a <a href="https://youtu.be/VTX3yiPri5c">discussion</a>, virtually of course.
<br /><br />
<iframe allow="accelerometer; autoplay; encrypted-media; gyroscope; picture-in-picture" allowfullscreen="" frameborder="0" height="315" src="https://www.youtube.com/embed/VTX3yiPri5c" width="560"></iframe><div><br /></div><div><br /></div>https://blog.computationalcomplexity.org/2020/04/return-of-vidcast.htmlnoreply@blogger.com (Lance Fortnow)0tag:blogger.com,1999:blog-3722233.post-6956243767390574114Thu, 02 Apr 2020 19:20:00 +00002020-04-02T15:20:01.307-04:00Let's Hear It for the Cloud<div>Since March 19th I have worked out of home. I've had virtual meetings, sometimes seven or eight a day, on Zoom, Bluejeans, Google Hangouts, Google Meet, Blackboard Collaborate Ultra and Microsoft Teams. I take notes on my iPad using Penultimate which syncs with Evernote. I store my files in Dropbox and collaborate in Google Drive. I communicate by Google Chat, Gmail, Facebook messenger and a dozen other platforms. I continue to tweet and occasionally post in this blog. </div><div><br /></div><div>A billion of my closest friends around the world are also working out of home and using the same and similar tools. Yet outside of some pretty minor issues, all of these services continue to work and work well. Little of this would have been possible fifteen years ago. </div><div><br /></div><div>As Amazon scaled up their web operations to handle their growing business in the early 2000's they realized they could sell computing services. AWS, Amazon Web Services, started in 2006. Microsoft Azure, Google and others followed. These sites powered smartphones and their apps that push heavy processing to the cloud, small startups who don't need to run their own servers, and companies like Zoom when they need to scale up quickly and scale down like Expedia when they don't need as much use. Amazon and Microsoft makes most of their profit on cloud services. Amazon can't get me toilet paper but they can make sure Blackboard continues to work when all of our classes move online. </div><div><br /></div><div>Just for fun I like to occasionally look over the large collection of <a href="https://aws.amazon.com/products">Amazon Cloud Products</a>. Transcribe an audio recording and translate to Portuguese, not a problem. </div><div><br /></div><div>The cloud can't allow all of us to work from home. We have many who still go to work including front-line health care workers putting their lives on the line. Many have lost their jobs. Then of course there are those sick with the virus, many of whom will never recover. We can't forget about the reason we stay indoors.</div><div><br /></div><div>But every now and then it's good to look back and see how a technology has changed our world in a very short time. If we had this virus in the 90's we'd still be having to go to work, or simply stop teaching and other activities all together.</div><div><br /></div><div>And how will our universities and other work spaces look like in the future now that we find we can work reasonably well from home and even better technologies develop? Only time will tell.</div><div><br /></div><div><br /></div><div><br /></div>https://blog.computationalcomplexity.org/2020/04/lets-hear-it-for-cloud.htmlnoreply@blogger.com (Lance Fortnow)0Chicago, IL, USA41.8781136 -87.629798213.567879763821153 -122.7860482 70.188347436178844 -52.473548199999996tag:blogger.com,1999:blog-3722233.post-4912143677920692930Tue, 31 Mar 2020 17:53:00 +00002020-03-31T14:53:16.185-04:00Length of Descriptions for DFA, NFA, CFG<br />
We will be looking at the size of descriptions<br />
<br />
For DFAs and NFAs this is the number of states.<br />
<br />
For CFG's we will assume they are in Chomsky Normal Form. So for this post CFG means CFG in Chomsky normal form. The length of a Chomsky Normal Form CFL is the number of rules.<br />
<br />
1) It is known there is a family of languages L_n such that<br />
<br />
DFA for L_n requires roughly 2^n states.<br />
<br />
NFA for L_n can be done with roughly n states.<br />
<br />
L_n = (a,b)^* a (a,b)^n<br />
<br />
Also note that there is a CFG for L_n with roughly n rules. (one can show this directly or by some theorem that goes from an NFA of size s to a CFG of size roughly s).<br />
<br />
So L_n shows there is an exp blowup between DFAs and NFA's<br />
<br />
2) It is known that there is a family of languages L_n such that<br />
<br />
DFA for L_n requires roughly 2^n states<br />
<br />
NFA for L_n requires roughly 2^n states<br />
<br />
CFG for L_n can be done with roughly n rules<br />
<br />
L_n = { a^{2^n} }<br />
<br />
So L_n shows there is an exp blowup between NFAs and CFGs.<br />
<br />
<br />
3) Is there a family of languages L_n such that<br />
<br />
NFA for L_n requires 2^{2^n} states<br />
<br />
CFG for L_n can be done with roughly n rules.<br />
<br />
The answer is not quite- and perhaps open. There is a set of family of languages L_n such that for infinitely many n he above holds. These languages have to do with Turing Machines. In fact, you can replace<br />
<br />
2^{2^n}} with any function f \le_T INF (so second level of undecidability).<br />
<br />
For this blog this is NOT what we are looking for. (For more on this angle see <a href="https://arxiv.org/pdf/1503.08847.pdf">here</a><br />
<br />
<br />
4) OPEN (I think) Is there a family of langs L_n such that for ALL n<br />
<br />
NFA for L_n requires 2^{2^n} (or some other fast growing function<br />
<br />
CFG for L_n can be done with roughly n states (we'll take n^{O(1)})<br />
<br />
5) OPEN (I think) Is there a family of langs L_n such that for ALL n<br />
(or even for just inf many n)<br />
<br />
DFA for L_n requires 2^{2^n}} states<br />
<br />
NFA for L_n requires 2^n states and can be done in 2^n<br />
<br />
CFG for L_n can be done with n rules.<br />
<br />
(we'll settle for not quite as drastic, but still want to see DFA, NFA, CFG all<br />
far apart).<br />
<br />
<br />
<br />
<br />
<br />
<br />
<br />https://blog.computationalcomplexity.org/2020/03/length-of-descriptions-for-dfa-nfa-cfg.htmlnoreply@blogger.com (GASARCH)2tag:blogger.com,1999:blog-3722233.post-655863126004196531Sat, 28 Mar 2020 15:40:00 +00002020-04-04T11:36:02.183-04:00Robin Thomas<div class="separator" style="clear: both; text-align: center;">
<a href="https://1.bp.blogspot.com/-i5UN1hxg7RI/Xn9uVPL8h1I/AAAAAAABygU/5THjPemeT9UhN3yQenJkO_3cM_c2Awi5QCLcBGAsYHQ/s1600/Thomas.jpg" imageanchor="1" style="clear: right; float: right; margin-bottom: 1em; margin-left: 1em;"><img border="0" data-original-height="540" data-original-width="360" height="200" src="https://1.bp.blogspot.com/-i5UN1hxg7RI/Xn9uVPL8h1I/AAAAAAABygU/5THjPemeT9UhN3yQenJkO_3cM_c2Awi5QCLcBGAsYHQ/s200/Thomas.jpg" width="133" /></a></div>
Graph Theorist and Georgia Tech Math Professor Robin Thomas passed away Thursday after his long battle with ALS. He was one of the giants of the field and a rare double winner of the Fulkerson Prize, for the six-color case of the <a href="https://en.wikipedia.org/wiki/Hadwiger_conjecture_(graph_theory)">Hadwiger Conjecture</a> and the proof of the <a href="https://en.wikipedia.org/wiki/Strong_perfect_graph_theorem">strong perfect graph theorem</a>.<br />
<br />
If you start with a graph G and either delete some vertices or merge vertices connected by an edge, you get a minor of G. The Hadwiger conjecture asks whether every graph that is not (k+1)-colorable graph has a clique of size k as a minor. Neil Robertson, Paul Seymour and Thomas proved the k=6 case in 1993 and still the k>6 cases remain open.<br />
<br />
A graph G is perfect if for G and all its induced subgraphs, the maximum clique size is equal to its chromatic number. In 2002 Maria Chudnovsky, Robertson, Seymour and Thomas showed that a graph G is not perfect if and only if either G or the complement of G has an induced odd cycle of length greater than 3.<br />
<br />
Robin Thomas was already confined to a wheelchair when I arrived at Georgia Tech in 2012. He was incredibly inspiring as he continued to teach and lead the Algorithms, Combinatorics and Optimization PhD program until quite recently. Our department <a href="https://youtu.be/e4FdY9eiWDs">did the ALS challenge</a> for him. In 2016 he <a href="https://provost.gatech.edu/updates/thomas-earns-top-faculty-honor">received</a> the Class of 1934 Distinguished Professor Award, the highest honor for a professor at Georgia Tech. He'll be terribly missed.https://blog.computationalcomplexity.org/2020/03/robin-thomas.htmlnoreply@blogger.com (Lance Fortnow)2tag:blogger.com,1999:blog-3722233.post-7044506782591278327Tue, 24 Mar 2020 04:01:00 +00002020-03-26T09:06:21.692-04:00What to do while ``stuck'' at home/Other thoughts on the virusLance had a great post on what to do while you are stuck at home, which is of course relevant to whats happening now. Lance's post is <a href="https://blog.computationalcomplexity.org/2020/03/what-to-do-while-stuck-at-home-part-i.html">here</a>.<br />
<br />
I will add to it, and then have other comments.<br />
<br />
1) In our current electronic society we can do a lot from home. Don't think of it as being `stuck at home'<br />
<br />
2) Lance points out that you should read a paper, read a textbook, etc. I of course agree and add some advice. Be Goldlocks!<br />
<br />
This paper is too hard (e.g., a text on quantum gravity)<br />
<br />
This paper is too easy (e.g., a discrete math textbook for a freshman course)<br />
<br />
This paper is just right (e.g., working out the large canonical Ramsey theorem)<br />
<br />
3) If you catch up on your TV viewing on your DVR then beware: you will see commercials for Bloomberg.<br />
<br />
4) DO NOT binge watch TV. You will hate yourself in the morning.<br />
<br />
5) Simons Inst Theory talks:<br />
<br />
<a href="https://simons.berkeley.edu/videos">https://simons.berkeley.edu/videos</a><br />
<br />
TCS+ talks<br />
<br />
<a href="https://sites.google.com/site/plustcs/past-talks">https://sites.google.com/site/plustcs/past-talks</a><br />
<br />
or<br />
<a href="https://sites.google.com/site/plustcs/">https://sites.google.com/site/plustcs/</a><br />
<br />
The Gathering for Gardner records all of their talks and puts the on you-tube<br />
so goto youtube and search for Gathering for Gardners. These are Goldilocks talks since they<br />
are easy but on stuff you prob don't know.<br />
<br />
6) Keep fit. I used to go on treadmill for 45 minutes a day, now I am doing an hour.<br />
<br />
7) Go for walks with a person who already shares your house, but avoid other people.<br />
<br />
8) Book reviews, surveys, orig articles, that you were putting off writing- now write them.<br />
but see next item.<br />
<br />
10) Catch up on your blog reading. My favorite was Scott Aaronson's blog post about Davos:<a href="https://www.scottaaronson.com/blog/?p=4536">here</a>. I also read every single comment. I hated myself in the morning. So that part may have been a mistake.<br />
<br />
OTHER THOUGHTS<br />
<br />
1) Do you really have more free time? No commuting, no teaching, but you still have the rest of your job, and perhaps it is harder if some things are easier at work. And calling relatives and friends to make sure they are okay, and just to talk, is a great thing to do, but its time consuming.<br />
<br />
2) I'm beginning to lose track of what day-of-the-week it is since I don't have school to keep me on track, and I only watch TV shows on DVR so I watching a show on a day does not mean I know what day it is.<br />
<br />
3) Avoid being price-gouged. The first few days that I tried to buy TP for my mom on amazon (I do this in normal times--- I order lots for my mom on amazon--- she is tech shy. She is also over 90.) her usual brand was out of stock, and the other brands were either higher quality so higher prices or just<br />
absurdly priced. She wisely said to wait a week. She was right- it was easy to get at the usual price.<br />
<br />
4) More generally, it seems like the shortages are people-created. For example, if in a store you see they are low on X, then you buy LOTS of X, and everyone does that, so then their really is a shortage of X. But I think thats calmed down some.<br />
<br />
5) It important to have a `we will recover from this, life will go on' attitude (while following the things ALL experts say- wash your hands a lot, drink lots of water, get lots of sleep, which is prob<br />
good advice anyway) and hence I will try to, for the next few weeks, blog on NORMAL things----Hilberts's 10th problem, Large Ramsey, etc.<br />
<br />
ADDED LATER- there is a very nice contrarian view in the comment by Steve, the first comment. You should read that!<br />
<br />
<br />
<br />
<br />
<br />
<br />
<br />https://blog.computationalcomplexity.org/2020/03/what-do-do-while-stuck-at-homeother.htmlnoreply@blogger.com (GASARCH)1tag:blogger.com,1999:blog-3722233.post-6639109407429165166Thu, 19 Mar 2020 13:45:00 +00002020-03-19T09:45:52.725-04:00What to do while stuck at home Part IFirst of all both the <a href="https://amturing.acm.org/">Turing award</a> and <a href="https://www.abelprize.no/seksjon/vis.html?tid=76020">Abel Prize</a> announced yesterday.<br />
<br />
As we start moving from the panic phase of the coronavirus to the boring phase, what kinds of things should you do or not do while stuck at home for the next two weeks to eighteen months.<br />
<br />
First of all still do your job. Teach your online classes. Try to do some research. Meet with your colleagues/students/advisor virtually (best with Zoom or something similar). Submit to conferences. What else? Use the situation for your advantage.<br />
<br />
<b>Attend virtual conferences: </b>Really attend. Pretend that you flew there and devote the entire day to going to virtual talks or chatting with other attendees in virtual hallways. I <a href="https://blog.computationalcomplexity.org/2020/03/the-importance-of-networking.html">said it wouldn't happen this way</a> last week so prove me wrong.<br />
<br />
<b>Create a Virtual Workshop: </b>Because you can. Invite people to give online talks. Open it up for all to listen. Find ways to discuss together.<br />
<br />
<b>Connect: </b>Make a virtual get-together with an old colleague or someone you've always wanted to meet. Researchers around the world will be holed up and happy to get some interactions.<br />
<br />
<b>Learn Something New: </b>Read a textbook. Take an online course in CS or something completely different. There are plenty.<br />
<br />
<b>Help Others Learn: </b>Start that book you've always wanted to write. Or just write a short survey article giving your view of a slice of the theory world. Create some videos or a podcast to explain stuff.<br />
<br />
<b>Pick up a hobby: </b>Something outside computer science just to keep your sanity.<br />
<b><br /></b>
<b>Watch some fun computer-related movies: </b>Her, Sneakers, The Computer wore Tennis Shoes, 2001, The Imitation Game, Hidden Figures, Colossus: The Forbin Project, Ex Machina. Add your own favorites in the comments.<br />
<br />
And on the other hand don't<br />
<br />
<b>Become an epidemiologist: </b>As a computer scientist you are an expert in networks, graph theory and exponential growth so you can create models that show we are grossly under preparing and/or overreacting to the virus and want to tell the world how you are right and the so-called "experts" are wrong. Please don't.<br />
<br />
<b>Prove P ≠ NP</b>: Trying to settle P v NP and failing is instructive. Trying to settle P v NP and thinking you succeeded is delusional.<br />
<br />
<b>Freak Out: </b>We will get past this virus and the world will recover.<br />
<br />
Bill will follow up with his own ideas in part II next week.https://blog.computationalcomplexity.org/2020/03/what-to-do-while-stuck-at-home-part-i.htmlnoreply@blogger.com (Lance Fortnow)4tag:blogger.com,1999:blog-3722233.post-3321636530900479641Tue, 17 Mar 2020 16:43:00 +00002020-03-18T16:57:49.342-04:00Richard Guy passed away at the age of 103Richard Guy passed away on March 9, 2020 at the age of 103. Before he died he was the worlds oldest living mathematician (see <a href="https://en.wikipedia.org/wiki/List_of_centenarians_(scientists_and_mathematicians)">here</a> for a list of centenarians who are famous scientists or mathematicians). He was also the oldest <i>active </i>mathematician-- he had a paper on arxiv (see <a href="https://arxiv.org/abs/1910.03379">here</a>) in October of 2019. (ADDED later since a commenter pointed it out to me--- a paper by Berlekamp and Guy posted in 2020: <a href="https://arxiv.org/abs/2002.03705">here</a>)<br />
<br />
I met him twice- once at a Gathering for Gardner, and once at an AMS meeting. I told him that Berlekamp-Conway-Guy had a great influence on me. He asked if it was a positive or negative influence. He also seemed to like my talk on The Muffin Problem, though he might have been being polite.<br />
<br />
<br />
I did a blog about Richard Guy on his 103rd birthday, so I recommend readers to go <a href="https://blog.computationalcomplexity.org/2019/09/richard-guy-is-102-years-old-today.html">there</a><br />
for more about him. One point I want to re-iterate:<br />
<br />
Richard Guy thought of himself of an amateur mathematician. If he means someone who does it for love of the subject then this is clearly true. If it is a measure of how good he is (the term `amateur' is sometimes used as an insult) then it is clearly false. If it means someone who does not have formal training than it is partially true.<br />
<br />
<br />
<br />
<br />https://blog.computationalcomplexity.org/2020/03/richard-guy-passed-away-at-age-of-103.htmlnoreply@blogger.com (GASARCH)4tag:blogger.com,1999:blog-3722233.post-7966517894480895355Thu, 12 Mar 2020 13:17:00 +00002020-03-12T09:17:00.482-04:00The Importance of NetworkingPeople skip conferences because of the coronavirus or for <a href="https://cacm.acm.org/magazines/2020/1/241717-publish-and-perish/fulltext">global</a> <a href="https://www.change.org/p/organizers-of-data-science-and-machine-learning-conferences-neurips-icml-aistats-iclr-uai-allow-remote-paper-poster-presentations-at-conferences?">warming</a> or just because conferences are too expensive and time consuming. I'm certainly <a href="https://cacm.acm.org/magazines/2009/8/34492-viewpoint-time-for-computer-science-to-grow-up/fulltext">no fan</a> of the current conference structure but I would never want to virtualize all of them. Even if we could completely recreate the conference experience in virtual reality, people would not hang out in the halls without the commitment of having made the physical trip. I made this point in a tweet with a depressing response.<br />
<blockquote class="twitter-tweet" data-partner="tweetdeck">
<div dir="ltr" lang="en">
At least in CS theory, I don't see any crucial importance. These days it's easy to follow the latest developments online. If you're interested in someone's work, you just email them and start a collaboration. Sooner or later networking in hallways may become a thing of the past.</div>
— Mahdi Cheraghchi (@cheraghchi) <a href="https://twitter.com/cheraghchi/status/1235792583516975104?ref_src=twsrc%5Etfw">March 6, 2020</a></blockquote>
<script async="" charset="utf-8" src="https://platform.twitter.com/widgets.js"></script>
<br />
<div>
I don't disagree with anything Mahdi says except for the "crucial importance". Great ideas come from chance encounters and random conversations. Many of my research papers would never have happened if not for a conversation had at a conference or on the plane or train rides that took me there. Harken Gilles Brassard's <a href="https://arxiv.org/abs/quant-ph/0604072">origin story</a> of quantum cryptography.<br />
<blockquote class="tr_bq">
One fine afternoon in late October 1979, I was swimming at the beach of a posh
hotel in San Juan, Puerto Rico. Imagine my surprise when this complete stranger
swims up to me and starts telling me, without apparent provocation on my part,
about Wiesner’s quantum banknotes! This was probably the most bizarre, and
certainly the most magical, moment in my professional life<sup>6</sup>. Within hours, we had
found ways to mesh Wiesner’s coding scheme with some of the then-new concepts
of public-key cryptography.... The ideas that Bennett and I tossed around on the beach that day resulted
in the first paper ever published on quantum cryptography, indeed the paper
in which the term “Quantum Cryptography” was coined. </blockquote>
And Footnote 6 read as follows.<br />
<blockquote class="tr_bq">
At the risk of taking some of the magic away, I must confess that it was not by accident that
Bennett and I were swimming at the same beach in Puerto Rico. We were both there for the
20th Annual IEEE Symposium on the Foundations of Computer Science. Bennett approached
me because I was scheduled to give a talk on relativized cryptography on the last day of the
Symposium and he thought I might be interested in Wiesner’s ideas. By an amazing coincidence,
on my way to San Juan, I had read Martin Gardner’s account of Bennett’s report on
Chaitin’s Omega, which had just appeared in the November 1979 “Mathematical Games” column
of Scientific American—so, I knew the name but I could not recognize Bennett in that swimmer
because I did not know what he looked like.</blockquote>
After we see a slate of conferences held virtually due to the virus, networking may indeed become a thing of the past. But we'll never know the research not done because of people who never connected.</div>
https://blog.computationalcomplexity.org/2020/03/the-importance-of-networking.htmlnoreply@blogger.com (Lance Fortnow)6tag:blogger.com,1999:blog-3722233.post-2996231259381150068Tue, 10 Mar 2020 11:42:00 +00002020-03-31T13:39:56.660-04:00Theorist Paul R Young passed awayIn the early days of theoretical computer science, say 1960-1990 the main tools used were logic.<br />
This made sense since, early on:<br />
<br />
a) Some of the basic notions like DTIME(T(n)), P, NP used Turing Machines in their definitions<br />
<br />
b) Some of the basic notions like reductions were modeled after similar concepts in<br />
computability theory.<br />
<br />
One of the people who did much work in the interface between Logic and TCS was Paul Young.<br />
He <a href="https://news.cs.washington.edu/2020/03/05/remembering-paul-young-1936-2019/">passed away</a> in December. Here are some highlights of his work:<br />
<br />
1) One of the first books that covered both computability and complexity:<br />
<br />
An Introduction to the general theory of Algorithms<br />
by Machtey and Young.<br />
<br />
2) In Computability theory all many-one complete sets are computably isomorphic. Berman and<br />
Hartmanis conjectured that the poly-many-one degree of the NP-complete sets was the same. This<br />
would mean that all NP-complete sets were poly-isom (all of the known ones are).<br />
<br />
Mahaney and Young in the paper<br />
<br />
<i>Reductions Among Polynomial Isomorphism Types</i><br />
<br />
showed that every many-one poly degree either has one degree or has an infinite number of<br />
degrees in a very complicated way.<br />
<br />
3) Recall that a <i>Cook Reduction from A to B </i>allows many queries to B, whereas a <i>Karp Reduction</i><br />
only allows one query and your answer must be the same sense as the query.<br />
Are there cases where a Cook reduction is faster? Yes, from the paper<br />
<br />
<i>Cook reducibility is faster than Karp Reducibility</i><br />
<br />
by Longpre and Young<br />
<br />
(The original title was going to be <i>Cook is Faster than Karp</i>, but it was changed since it invoked<br />
images of Cook and Karp in a footrace. Hmmm. Which one would be faster?)<br />
<br />
<br />
4) The <i>Boolean Hierarchy </i>is a hierarchy of iterations of NP sets. What if instead of starting with P<br />
one started with RP (Randomized Poly time). What an intriguing notion! To find out read<br />
<br />
<br />
<i>Generalized Boolean Hierarchies over RP</i><br />
<br />
by Alberto Bertoni, Danilo Bruschi, Deborah Joseph, Meera Sitharam, Paul Young<br />
<br />
5) There are <a href="https://scholar.google.com/citations?user=hYa6-bMAAAAJ">many more</a>, mostly on the theme of the interaction of logic and computer science.<br />
<br />
I saw him speak on some of these topics and was inspired by how much one could<br />
take notions of computability and translate them into complexity theory. The field has gone in a<br />
different direction since then (more combinatorial) but we still use many of the basic concepts<br />
like reducibility. As such we all owe a debit to Paul Young.https://blog.computationalcomplexity.org/2020/03/theorist-paul-r-young-passed-away.htmlnoreply@blogger.com (GASARCH)1tag:blogger.com,1999:blog-3722233.post-940496487994761300Thu, 05 Mar 2020 14:35:00 +00002020-03-05T09:35:14.185-05:00A New College of Computing at Illinois Tech<div class="separator" style="clear: both; text-align: center;">
<a href="https://1.bp.blogspot.com/-4o0elQGFp-c/XmAhjkpOpKI/AAAAAAABxio/I6qGUp1ot6UA8rJtL2GLvRDcZU3YEZhaQCLcBGAsYHQ/s1600/IllinoisTech_MiesCampus.jpg" imageanchor="1" style="margin-left: 1em; margin-right: 1em;"><img border="0" data-original-height="1067" data-original-width="1600" height="266" src="https://1.bp.blogspot.com/-4o0elQGFp-c/XmAhjkpOpKI/AAAAAAABxio/I6qGUp1ot6UA8rJtL2GLvRDcZU3YEZhaQCLcBGAsYHQ/s400/IllinoisTech_MiesCampus.jpg" width="400" /></a></div>
<br />
In 1890, Chicago South Side pastor Frank Gunsaulus gave a sermon where he said that with a million dollars he could build a school where students of all backgrounds could prepare for meaningful roles in a changing industrial society. One of the congregants, Philip Armour, came up to him after the service and told Gunsaulus that "if you give me five years of your time, I will give you the money." Thus was born the Armour Institute of Technology, the forerunner of the Illinois Institute of Technology.<br />
<br />
Today Illinois Tech enters a new chapter, <a href="https://www.iit.edu/news/illinois-tech-creates-college-computing-fuel-chicagos-tech-rise">announcing a College of Computing</a>, and I am honored to have been asked to serve as its inaugural dean. The college will take on a horizontal mission, to infuse computation and data science thinking throughout the curriculum in every discipline, while understanding the power, limitations and social implications of the technologies they create. We will significantly grow computing to produce the talent needed for a growing Chicago tech community. The college will develop an agile curriculum to continually reevaluate our offerings as computing technology continues to advance, and develop education as a life-long process where our alumni can always count on Illinois Tech to continually reskill to advance their careers.<br />
<br />
We will do it all by keeping the core principle of the original "million-dollar sermon," as important as ever, to prepare students of all backgrounds for meaningful roles in a changing technological society.<br />
<div>
<br /></div>
https://blog.computationalcomplexity.org/2020/03/a-new-college-of-computing-at-illinois.htmlnoreply@blogger.com (Lance Fortnow)1tag:blogger.com,1999:blog-3722233.post-4788940302272898721Mon, 02 Mar 2020 15:32:00 +00002020-03-03T09:29:07.142-05:00Logic examples for your Discrete Math class<div>
<br />
<br />
(I injured my hand about a month ago so I have had a hard time typing. That is why<br />
I have not blogged for a while. I'm better now but still slow. This is a post I prepared<br />
a while back.)<br />
<br />
<br />
<br />
Here are some examples of English and logic for your discrete math class. Or for mine anyway.<br />
<br />
<br /></div>
<div>
1) <i>A computer programmer leaves work and heads for home. Being the good spouse that he is, he calls his partner and asks if there's anything that needs to be picked up on the way.</i></div>
<div>
<i><br /></i></div>
<div>
<i>Yes, a gallon of milk and, oh, if they have <span class="il">eggs</span>, get a dozen.</i></div>
<div>
<i><br /></i></div>
<div>
<i>Later he arrives home and stumbles into the kitchen burdened with a dozen gallons of milk. His partner perplexed, asks him ``why in the world did you buy 12 gallons of milk?''</i></div>
<div>
<i><br /></i></div>
<div>
<i>What did he answer?</i></div>
<div>
<br /></div>
<div>
When I told this to my class one student said that he should answer:</div>
<div>
<br />
<i>I love you too Darling</i></div>
<div>
<br /></div>
<div>
while that is always a good thing to tell Darling, it is not the answer I had in mind.<br />
<br /></div>
<div>
The answer is <a href="https://www.cs.umd.edu/users/gasarch/BLOGPAPERS/eggs.txt">here</a>.</div>
<div>
<br /></div>
<div>
2) I saw a headline:</div>
<div>
<br /></div>
<div>
<i> Rise in faux-incest porn alarming</i></div>
<div>
<br /></div>
<div>
Give two different interpretations of this sentence. (Note- One you might agree with, the other you will likely disagree with.)<br />
<br />
My answer is <a href="https://www.cs.umd.edu/users/gasarch/BLOGPAPERS/faux.txt">here</a></div>
<div>
<br />
3) Recently someone was describing what I work on to someone else and he said the following wonderfully ambiguous sentence<br />
<br />
<i>Bill works on puzzles and games. He also work on cake cutting, to be fair.</i><br />
<br />
Give two different interpretations of this sentence. My answer is <a href="https://www.cs.umd.edu/users/gasarch/BLOGPAPERS/billcake.txt">here</a><br />
<br />
<br />
4) A common saying is<br />
<br />
<i> All that glitters is not gold</i><br />
<br />
What does this mean literally? What did they really mean to say? My answer is <a href="https://www.cs.umd.edu/users/gasarch/BLOGPAPERS/gold.txt">here.</a><br />
<br />
(I had originally thought this was a quote from the Led Zeppelin song <i>Stairway to Heaven</i>;<br />
however, an astute reader left a comment reminding me that, in that song, they actually<br />
say that there is a lady who believes <i>All that Glitters is Gold. </i>The song implies that she is incorrect, so really<br />
NOT(All that Glitters is Gold) which means (exists x)[x glitters but x is not gold] which actually<br />
IS what they meant to say. Yeah!)<br />
<br />
5)When the chess player Bobby Fisher died I saw in one article about him the sentence<br />
<i><br /></i>
<i> Bobby Fisher was a terrible anti-semite.</i><br />
<br />
<i></i>This can be interpreted two ways. What are they? Which one did the writer probably mean? My answer is <a href="https://www.cs.umd.edu/users/gasarch/BLOGPAPERS/fisher.txt">here</a><br />
<br />
6) When Donald Trump broke the Nuclear Treaty with Iran he said<br />
<br />
<i> Iran is the worse enabler of terrorist in the mideast</i><br />
<br />
This can be interpreted two ways. What are they? Which one did Trump mean? My answer is <a href="https://www.cs.umd.edu/users/gasarch/BLOGPAPERS/iran.txt">here.</a><br />
<br /></div>
<div>
<br />
7) I saw the headline (see <a href="https://www.dailykos.com/stories/2019/12/31/1905544/-There-was-actually-good-news-in-the-War-on-Women-in-2019-news-we-have-to-build-on-in-2020">here</a>)<br />
<br />
<i>There was actually good news in the War on Women in 2019, news we have to build on in 2020</i>.<br />
<br />
This can be interepreted in two ways. This one I leave to you, or read the article.<br />
<br />
<br />
<br />
<br /></div>
https://blog.computationalcomplexity.org/2020/03/logic-examples-for-your-discrete-math.htmlnoreply@blogger.com (GASARCH)5tag:blogger.com,1999:blog-3722233.post-1276607874189152226Sun, 16 Feb 2020 16:02:00 +00002020-02-16T11:02:32.333-05:00Pre-(Publish and Perish)<i>Guest post by Evangelos Georgiadis</i><br />
<div>
<br /></div>
Quite a few posts have recently focused on papers,publications and venues;
"optimal" venues for papers under different objective functions,e.g.
minimizing carbon footprint while maximizing community building, networking
as well as information sharing, see <a href="https://cacm.acm.org/magazines/2020/1/241717-publish-and-perish/fulltext">Moshe Vardi</a>.<br />
<br />
Here we would like to take a closer look at one of the key assumptions
-- the paper.
In order to generate a paper, one needs to come up with a result, something
novel, fresh or interesting to say.
The question that has baffled this author is what represents a conducive
or perhaps even optimal setting for generating papers.
Since papers come in different flavors ranging from "<a href="https://blog.computationalcomplexity.org/2009/11/innovation.html">solid technical papers to risky innovative ones</a>" the
settings
may vary; but ultimately, what would be interesting to investigate (or
for that matter crowdsource) is whether there is a common denominator
in terms of setting or environment, a necessary but not sufficient
condition (so to speak).
<br />
<br />
Here are some accounts of others which may be helpful as reference points.
<br />
<br />
Knuth's papers entitled "<a href="http://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.455.1434&rep=rep1&type=pdf">Semantics of context free grammar</a>" along with
"The analysis of algorithms" represent two instances that suggest research
institutes might not provide an optimal environment for idea generation.
<br />
<br />
As Knuth points out in "<a href="https://www-cs-faculty.stanford.edu/~knuth/cl.html">Selected Papers on Computer Languages</a>" (Chapter 18, p. 431):<br />
<blockquote class="tr_bq">
Perhaps new ideas emerge most often from hectic, disorganized
activity,
when a great many sources of stimulation are present at once --
when numerous
deadlines need to be met, and when other miscellaneous activities
like child-rearing
are also mixed into the agenda.</blockquote>
Knuth goes on to say, that it was challenging to do creative work in
office and that finding
a few hideaways provided some form of solution -- aka sitting under
'that' oak tree
near Lake Lagunita.
That said, the inspirational setting for getting into the zone for the
aforementioned two papers
were provided by (Californian) beaches. Hold that observation. Is this
not something we
have come across somewhere else ?
Fields medalist Stephen Smale in "<a href="http://math.berkeley.edu/~smale/biblio/chaos.ps">Chaos: Finding a Horseshoe on the Beaches of Rio</a>" suggests that some of his best work happened at his "beach office".
Whether beaches do provide
for a good setting remains to be shown; perhaps for very innovative
ideas, oceanic freedom is necessary.
That said, the author recalls (hopefully accurately enough) an account
by the young James H Simons,
who attended a conference in Japan in the early days.
Instead of choosing a spacious accommodation (which he was able to
afford), he restricted himself to the typically confined room type --
not only confined by space, but also pressured by time, young Simons was
able to generate an interesting result for that conference.
(This probably demonstrates that technical results don't necessarily
require 'oceanic freedom'.)<br />
<br />
Some meaningful probabilistic advice comes from the fat-tails department,
in "The Black Swan" by Nassim Taleb (on page 209) :
"Go to parties! If you're a scientist, you will chance upon a remark
that might spark a new research. "
<br />
<br />
Murray Gell-Mann provides an interesting collective account in his
Google Tech Talk entitled "On Getting Creative Ideas."
He <a href="https://youtu.be/3fSB6ut-cT0?t=118">recollects</a> a workshop he attended in 1969 in Aspen that focused on
the experience
of getting creative ideas, not just among mathematicians and theoretical
physicists but also poets and
artists. This account seems to
neglect the actual setting that might
nurture creative thought process, but provides interesting references to
people such as
Hermann von Helmholtz, who happened to have thought about this topic
and partitioned the process
in terms of "saturation, incubation and illumination".
<br />
<br />
For those interested in an account that focuses on the Eureka moments of
exclusively
mathematicians/theoretical physicists see Jacques Hadamard's book "<a href="https://www.amazon.com/Mathematicians-Mind-Jacques-Hadamard/dp/0691029318">The Mathematician's Mind</a>".
Hadamard
iterated on Helmholtz's 3 stage process and it's worth taking a look at
what he came up.
<br />
<br />
At last, what are good venues or workshops for generating papers ? Or
let's rephrase that a bit,
what type of atmosphere at venues fosters creativity -- what food for
thought to provide
participants and how to distribute that food for thought over a given day ?
Ryan R Williams proposed (as practiced by 34th Bellairs Winter Workshop
on Computational Geometry)
"... easy problems, informal atmosphere focusing exclusively
on thinking about problems in a cycle of down-time where
one meets in two intense sessions and have free time otherwise."
(This type of setting seems to resonate with the 3 stages of
"saturation, incubation and illumination".)
<br />
<br />
That said, most workshops including the Simons workshops don't seem to
follow such a recipe.
They are more geared towards the follow-up step, namely, communicating
what people have found,
rather than collaborating with them to tackle open problems.
Perhaps some re-evaluation might be required in how workshops are run.https://blog.computationalcomplexity.org/2020/02/pre-publish-and-perish.htmlnoreply@blogger.com (Lance Fortnow)2tag:blogger.com,1999:blog-3722233.post-7713902699906746351Thu, 23 Jan 2020 23:22:00 +00002020-01-23T18:22:05.544-05:00The World of PublishingBill is out for blogging for a couple of weeks on injured-reserve (he’ll be fine). I put together a quick blog post on what’s happening in the world of publications. <br />
<br />
The Trump administration has suggested requiring publishers to make all papers based on US federally-funded publicly available immediately instead of after one year. The Association of American Publishers sent an <a href="https://presspage-production-content.s3.amazonaws.com/uploads/1508/lettertothepresidentfrom140researchandpublishingorgs-2.pdf?10000">open letter</a>--how do we maintain the organizations and the people who work there if we give up a major revenue source. The ACM joined the letter which caused quite a backlash forcing the ACM to <a href="https://www.acm.org/articles/bulletins/2020/january/message-from-the-acm-president-regarding-open-access">explain itself</a>, write another <a href="https://www.acm.org/binaries/content/assets/about/acm-letter-to-ostp.pdf">letter</a>, and run some <a href="https://www.acm.org/articles/bulletins/2020/january/oa-webinars">webinars</a> about open access the last of which is tomorrow. In the end, this is leading to some good discussions about open access and the financial models of academic societies. <br />
<br />
The ACM also has a <a href="https://www.acm.org/publications/policies/author-name-changes">new policy</a>, three options for what happens when an author changes their name: Maintain separate identities, have the two identities link to each other, or retroactively change the name on all previous papers. I can see good reasons for all three options.<br />
<br />
Finally Moshe Vardi writes in his <a href="https://cacm.acm.org/magazines/2020/1/241717-publish-and-perish/fulltext">CACM column</a> about the ecological cost of conferences and suggests that conferences allow authors to (video)phone it in. Emmanuel Viola offers <a href="https://emanueleviola.wordpress.com/2020/01/01/publish-and-perish/">his own thoughts</a>. Most Conferences will continue to require authors to show up, with only occasional exceptions as needed, believing these policies will keep their conference healthy.<br />
<br />
Personally I believe conferences should exist because researchers want to attend, not because they have to. We still need conferences so our community can get together and I don’t believe we can do that via the Internet no matter how good the VR experience gets. But we can have more videos and less conferences and reduce the costs: time, financial and environmental.https://blog.computationalcomplexity.org/2020/01/the-world-of-publishing.htmlnoreply@blogger.com (Lance Fortnow)2tag:blogger.com,1999:blog-3722233.post-6568540622933428053Tue, 14 Jan 2020 23:41:00 +00002020-01-14T19:18:48.492-05:00Quantum Provers to Infinity and BeyondThe Internets are buzzing about the new paper <a href="https://arxiv.org/pdf/2001.04383">MIP* = RE</a> by Zhengfeng Ji, Anand Natarajan, Thomas Vidick, John Wright and Henry Yuen. See posts by <a href="https://www.scottaaronson.com/blog/?p=4512">Scott</a>, <a href="https://windowsontheory.org/2020/01/14/mipre-connes-embedding-conjecture-disproved/">Boaz</a>, not to mention a wonderful backstory by <a href="https://mycqstate.wordpress.com/2020/01/14/a-masters-project/">Vidick</a> himself and a <a href="https://twitter.com/henryquantum/status/1216936907814375424">tweet stream</a> by Yeun. I'm not an expert enough to verify or even try to explain the proof so I'll just give a brief overview of the result.<br />
<br />
For those not familiar with the classes, RE (recursively enumerable) is the simplest of all complexity classes, a language is in RE if there is some Turing machine M such that x is in L if and only if M on input x accepts. For x not in L, M on x can reject or run forever. The classic halting problem, the set of descriptions of Turing machines that halt on empty input, is RE-complete. To nitpick the notation, it should have been r.e. and even c.e. (computably enumerable), a more <a href="https://blog.computationalcomplexity.org/2004/02/is-it-recursive-computable-or.html">standard notation</a> these days. But given the importance of the result, we can give the authors a pass.<br />
<br />
MIP* is the set of things provable to a classically random polynomial-time verifier by two separated provers with an unlimited number of quantumly entangled qubits. Without the quantum entanglement, MIP = NEXP, nondeterministic exponential time, and last year Natarajan and Wright showed that MIP* could do at least exponentially better in their paper, <a href="https://arxiv.org/abs/1904.05870">NEEXP in MIP*</a>. NEEXP seems large but still only consists of computable sets. RE gets outside of the computable realm.<br />
<br />
I found the first paper more surprising, as it showed that quantum entanglement actually gets more, much more, than classical provers. The second paper does get a much stronger and tight result, and still highly surprising in its own right, as it requires disproving the <a href="https://en.wikipedia.org/wiki/Connes_embedding_problem">Connes' embedding conjecture</a>. In the end we may just consider this one result, as the second paper subsumes the first both in theorem and authors.<br />
<br />
We didn't award the <a href="https://blog.computationalcomplexity.org/2019/12/complexity-year-in-review-2019.html">2019 theorem of the year</a> to Natarajan and Wright, instead opting for a paper that had more, how should I say this, sensitivity. This new paper is certainly the front runner for the 2020 honors, albeit it is only mid-January.https://blog.computationalcomplexity.org/2020/01/quantum-provers-to-infinity-and-beyond.htmlnoreply@blogger.com (Lance Fortnow)2tag:blogger.com,1999:blog-3722233.post-3743356831833676109Tue, 14 Jan 2020 01:28:00 +00002020-01-13T20:28:38.812-05:00What would you do if you showed P=NP? I would reread Factor Man by Matt GinsbergLance has often said (and also in <a href="https://blog.computationalcomplexity.org/2020/01/silicon-valley-ethics.html">this</a>) that if P=NP that would be great for the world: much more efficient ways to build things, science could be done better, etc, and that is much more important than that modern crypto would no longer work. We now have the technology to do private key really well--- like a thumb drive that has a billion bits for 1-time pads.<br />
<br />
I agree that the world would be better off in some ways, I wonder how much damage would be done in the transition period from public to private key. Would the world recover enough to reap the benefits of P=NP?<br />
<br />
First think of what YOU would do if you showed P=NP (and lets assume your algorithm is either reasonable or could be made reasonable with some time and effort).<br />
<br />
The novel <i>Factor Man </i>is about what someone who has solved P=NP does. I won't tell you how it goes, but they deal with the issue intelligently. So if I solved P=NP then I would first re-read it, and think through if I would do that, or modify what is done, or what. Its a good start.<br />
<br />
I reviewed the book in SIGACT News or you can read my review <a href="https://www.cs.umd.edu/users/gasarch/BLOGPAPERS/factorman.pdf">here</a><br />
<br />
On a slightly diff note, here is the latest argument I've heard for why P=NP:<br />
<br />
Planar 2-coloring is in P<br />
<br />
Planar 4-coloring is in P<br />
<br />
So<br />
<br />
Planar 3-coloring should be in P.<br />
<br />
This was said by a very good math/cs ugrad at UMCP. I do not know if he was kidding.<br />
<br />
<br />https://blog.computationalcomplexity.org/2020/01/what-would-you-do-if-you-showed-pnp-i.htmlnoreply@blogger.com (GASARCH)2tag:blogger.com,1999:blog-3722233.post-6812304357684621341Thu, 09 Jan 2020 01:35:00 +00002020-01-08T20:35:05.834-05:00Silicon Valley Ethics<b>Spoiler Alert: </b>This post has details from the final episodes of the HBO television series <a href="https://en.wikipedia.org/wiki/Silicon_Valley_(TV_series)">Silicon Valley</a><br />
<br />
A few times I've gotten emails from people claiming they have shown P = NP and asking whether they should keep their algorithm a secret to protect the cryptography out there. My typical response is that they should use their algorithm to mine a few bitcoins and then get back to me.<br />
<br />
The fictional characters of Pied Piper faced this dilemma when they AI they created "developed a general solution to discrete log in polynomial time" with some nice complexity class diagrams in the background.<br />
<br />
<div class="separator" style="clear: both; text-align: center;">
<a href="https://1.bp.blogspot.com/-0wC_yidITsY/Xg9oKlfZkrI/AAAAAAABu-g/OhzquwGwXbUqNDSDmGlpkU66wrjOcW62QCKgBGAsYHg/s1600/IMG_20200101_200809.jpg" imageanchor="1" style="margin-left: 1em; margin-right: 1em;"><img border="0" data-original-height="1200" data-original-width="1600" height="240" src="https://1.bp.blogspot.com/-0wC_yidITsY/Xg9oKlfZkrI/AAAAAAABu-g/OhzquwGwXbUqNDSDmGlpkU66wrjOcW62QCKgBGAsYHg/s320/IMG_20200101_200809.jpg" width="320" /></a></div>
<br />
Pied Piper was about to roll out its new internet, a distributed network that communicated between cell phones based on a compression algorithm developed by Pied Piper's CEO. Rolling out the network would reveal even more advanced compression based on breaking discrete log. "If we cancel it or shut it down, then others will try to copy or reverse engineer everything that we've built ... Our launch has to fail, publicly and spectacularly."<br />
<br />
But here comes the P v NP dilemma: "And what about all the other stuff we're gonna do? I mean, give internet to underserved communities, students in the homework gap, refugees, genomic research. Pied Piper can help scientists cure cancer."<br />
<br />
I'd take broken encryption over cancer any day. You can still do encryption even if P = NP, one-time pads distributed via USB drives or quantum. And cancer sucks.<br />
<br />
They should have mined a few bitcoins.https://blog.computationalcomplexity.org/2020/01/silicon-valley-ethics.htmlnoreply@blogger.com (Lance Fortnow)3tag:blogger.com,1999:blog-3722233.post-8980814517027039027Mon, 06 Jan 2020 04:54:00 +00002020-01-06T21:37:42.245-05:00The Wikipedia Entry on NP-Intermediary Problems lists one of mine! I'm not bragging about it.I recently needed to look at what NP problems were possibly intermediary (neither in P nor NP-complete). So I went to Wikipedia and found <a href="https://en.wikipedia.org/wiki/NP-intermediate">this</a>.<br />
<br />
They had many problems, though some I had never heard of. Those that I had never heard of<br />
<br />
<i>should they be on the list?</i><br />
<i><br />
</i> That is, are they natural? That is hard to define rigorously, but I will take you through my train of thought as I read the first few:<br />
<br />
<b>Factoring Integers</b>. Yes, quite possibly intermediary: If its NPC then PH collapses, and, at least so far, does not seem to be in P. (the NPC--> PH collapse result: We take<br />
<br />
FACT = { (n,x) : n has a nontrivial factor ≤ x }<br />
<br />
FACT is clearly in NP:<br />
a complete factorization of n provides evidence that some nontrivial factor is \le x.<br />
<br />
FACT is clearly in coNP:<br />
a complete factorization of n provides evidence that no nontrivial factor is \le x<br />
<br />
so if FACT is NP-complete then SAT is in coNP.<br />
<br />
Factoring is clearly an important and well studied problem. It even has its own Wikipedia entry!<br />
<br />
<b>Discrete Log</b>. Similar to Factoring. And it is also an important and well studied problem. It even has its own Wikipedia Entry!<br />
<br />
<b>Isomorphism Problems</b> They list Group and Ring isomorphism. They don't list Graph, which is odd. (ADDED LATER- my bad, they do mention Graph Isom in the section on Graph Algorithms) Anyway, if Graph Isom is NPC then PH collapses, and, at least so far, there is no algorithm for Graph Isom in P. (I do not think it is know if Group Isom NPC means PH collapses, or if Ring Isom NPC means PH collapses---if you know of such a proof leave a comment and a pointer to it.)<br />
<br />
Graph Isomorphism is a well studied problem and seems important and natural (I don't know if Graph Isomorphism has any real applications they way that factoring and DL do). It even has its own Wikipedia entry! Group and Ring Isomorphism also seem important and natural. And they have their own Wikipedia entry!<br />
<br />
<b>Numbers in Boxes Problem </b>My first reaction-Gee, whats that? For the Factoring, DL, and Isomorphism they did not define the problem-- they gave pointers to the Wikipedia entries on them. For this one there was no Wikipedia entry. There was one reference. I went to it. <i>It was a blog entry of mine</i>! Here it is: <a href="https://blog.computationalcomplexity.org/2010/07/what-is-complexity-of-these-problems.html">her</a>e, and to save you time I'll say what it is:<br />
<br />
{ (1<sup>n</sup>,1<sup>k</sup>) : you can partition 1,...,n into k boxes so that no box has x,y,z with x + y = z }<br />
<br />
Is this problem important? Does it exist anywhere outside of my blog entry? Yes--- a special case of it was in <a href="https://www.amazon.com/Doctor-Eccos-Cyberpuzzles-Dennis-Shasha/dp/0393325415/ref=sr_1_2?keywords=Dr.+Ecco&qid=1577931523&s=books&sr=1-2">Dr. Ecco's Cyperpuzzles by Dennis Shasha</a> (note- Dennis was a classmate of mine in graduate school at Harvard). I think the case was to try to partition {1,...,100} as best you can. Actually I first saw the case of the problem in his book and then generalized it.<br />
<br />
The problem is sparse so if it was NP-complete then P = NP, very good evidence that its not NPC. And its been studied for thousands of years, with people looking for poly time algorithms (I think Pythagoras studied it) without success, so its almost surely not in P. OR that last sentence was complete nonsense. Indeed, I don't think anyone has studied the problem computationally, or, for that matter, at all. So the evidence that its not in P is... sparse.<br />
<br />
But its worse than that. One could devise MANY sparse problems that are, since spares, likely NOT NPC, and hardly studied, so as-of-now, not in P. Should those count? Only if (a) more people study them so there is an attempt to point to to get it into P, and (b) the problem is natural (which is hard to define).<br />
<br />
Note that I can vary the problem: x+2y=z (this relates to lower bounds on VDW numbers)<br />
or any other combination of x,y,z or more that I like.<br />
<br />
<br />
<br />
This raises a question:<br />
<br />
<b>When is a problem worthy of being put on lists of problems?</b><br />
<b><br />
</b> Here are some possibly criteria. One can take ANDS and ORS of them.<br />
<br />
1) The problem has a Wikipedia entry. This might fall victim to Goodhearts law: when a measure becomes a target, it ceases to be a measure. That is, I could make a Wikipedia entry on the Number-in-boxes problem and then say LOOK, its on Wikipedia!<br />
<br />
2) More than X people have worked on the problem for some value of X. But here is a reason this might not be a good criteria: look at the problem<br />
<br />
{ α : α is a reg expression that allows numbers (so a<sup>1000</sup> is fine, makes reg expressions VERY succint) such that L(α)=Σ<sup>*</sup> }<br />
<br />
This problem looks natural, and was proven by Meyer and Stockmeyer to be EXPSPACE complete.<br />
That is the only paper on this problem, yet the problem really does look natural, and the result is rightly celebrated as a natural problem that is provably not in P.<br />
<br />
3) When people in the field look at the problem they say YEAH, thats a good problem.<br />
<br />
4) The problem relates to other problems or other fields.<br />
<br />
I doubt the Number-in-boxes problem satisfies any of these criteria. The variant with x+2y=z relates to Ramsey Theory. Great.<br />
<br />
NOW, back to the list-- I won't go through any more on the list, but I note that for some of them the only reference seems to be a conversation on stack-exchange. Some of those end up referring to real papers so are more likely natural, but some do not.<br />
<br />
Having said that, is there any harm in the list having on it some problems that are not ... worthy? Is that even the right word to use?<br />
<br />
Note that I don't have strong opinions on any of these matters, I am just wondering what criteria Wikipedia, and other sources, uses, when they have lists of problems.<br />
<b><br />
</b> <b><br />
</b> <b><br />
</b> <b><br />
</b> https://blog.computationalcomplexity.org/2020/01/the-wikipedia-entry-on-np-intermediary.htmlnoreply@blogger.com (GASARCH)5tag:blogger.com,1999:blog-3722233.post-5060142193352763387Tue, 31 Dec 2019 18:02:00 +00002020-01-01T07:18:01.946-05:00Complexity Year in Review 2019Some great theorems this year including <a href="https://mycqstate.wordpress.com/2019/04/14/randomness-and-interaction-entanglement-ups-the-game/">non-deterministic double exponential time by quantumly entangled provers</a> and <a href="https://rjlipton.wordpress.com/2019/03/29/integer-multiplication-in-nlogn-time/">integer multiplication in O(n log n) time</a>. But the result of the year has to go to a paper that gave a <a href="https://blog.computationalcomplexity.org/2019/07/local-kid-makes-history.html">shockingly simple proof of a major longstanding conjecture</a>.<br />
<br />
<div style="text-align: center;">
<a href="https://arxiv.org/abs/1907.00847">Induced subgraphs of hypercubes and a proof of the Sensitivity Conjecture</a> by Hao Huang</div>
<div>
<br /></div>
<div>
Of course 2019 will be remembered in some circles for giving us Google's claims of quantum supremacy and all the quantum hype, deserved and otherwise, that goes with it.<br />
<br />
Personally Bill came out with his new book <a href="https://www.worldscientific.com/worldscibooks/10.1142/11261#t=toc">Problems with a Point; Exploring Math and Computer Science</a> co-authored with Clyde Kruskal (<a href="https://amzn.to/2s6IlPl">Amazon</a>, <a href="https://blog.computationalcomplexity.org/2019/02/problems-with-point-exploring-math-and.html">blog</a> <a href="https://blog.computationalcomplexity.org/2019/04/problems-with-point-not-plug-just-some.html">posts</a>). Lance <a href="https://www.iit.edu/news/lance-fortnow-designated-new-college-science-dean">became a dean</a>. </div>
<div>
<br /></div>
<div>
We remember <a href="https://www.nytimes.com/2019/01/11/obituaries/michael-atiyah-dead.html">Michael Atiyah</a>, <a href="https://blog.computationalcomplexity.org/2019/04/elwyn-berlekamp-died-april-9-2019.html">Elwyn Berlekamp</a>, <a href="https://blog.computationalcomplexity.org/2019/04/quiz-show-scandalsadmissions.html">Charles van Doren</a>, <a href="https://blog.computationalcomplexity.org/2019/06/ray-miller-one-of-our-founders-passes.html">Ray Miller</a>, <a href="https://www.lamsade.dauphine.fr/fr/actualites/detail-de-lactualite/article/deces-de-jerome-monnot-membre-du-laboratoire-lamsade.html">Jérôme Monnot</a> and <a href="https://news.stanford.edu/2019/04/24/nils-nilsson-pioneer-robotics-artificial-intelligence-dies-86/">Nils Nilsson</a>.</div>
<div>
<br /></div>
<div>
Thanks to guest posters <a href="https://blog.computationalcomplexity.org/2019/10/quantum-supremacy-guest-post-by-abhinav.html">Abhinav Deshpande</a>, <a href="https://blog.computationalcomplexity.org/2019/01/the-paradigm-shift-in-fintech.html">Evangelos Georgiadis</a>, <a href="https://blog.computationalcomplexity.org/2019/07/guest-post-by-samir-khuller-on.html">Samir Khuller</a>, <a href="https://blog.computationalcomplexity.org/2019/06/ray-miller-one-of-our-founders-passes.html">Ming Lin</a>, <a href="https://blog.computationalcomplexity.org/2019/07/answer-to-both-infinite-hats-problems.html">David</a> <a href="https://blog.computationalcomplexity.org/2019/07/fortran-is-underated.html">Marcus</a>, <a href="https://blog.computationalcomplexity.org/2019/06/ray-miller-one-of-our-founders-passes.html">Ben Shneiderman</a> and <a href="https://blog.computationalcomplexity.org/2019/04/cuckoo-cycles.html">John Tromp</a>.</div>
<div>
<br /></div>
<div>
As we move into the 2020s, we tend to look back and look forward. The 2010s will go down as the decade computing and data transformed society, for better and worse. Google turned 21 this year as its OG leadership stepped down. I turned 21 in 1984, but 1984 seems closer than ever.</div>
<div>
<br /></div>
<div>
Last year we ended the <a href="https://blog.computationalcomplexity.org/2018/12/complexity-year-in-review-2018.html">year in review</a> by </div>
<blockquote class="tr_bq">
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.</blockquote>
2019 was not quiet and we're about to head into an impeachment trial, Brexit and a critical US presidential election. The real challenges of the twenties will come from massive transformation from automation, climate change and deepening divisions in our society. How will academia cope with changing demographics, financial challenges and educating to manage the technological revolution?<br />
<br />
Let's all take a deep breath, roll up our sleeves and get the decade going.https://blog.computationalcomplexity.org/2019/12/complexity-year-in-review-2019.htmlnoreply@blogger.com (Lance Fortnow)3tag:blogger.com,1999:blog-3722233.post-7376087648863245436Thu, 12 Dec 2019 20:24:00 +00002019-12-17T08:45:36.741-05:00Why is there no all-encompassing term for a course on Models of Computation?In my <a href="https://blog.computationalcomplexity.org/2019/12/what-do-you-call-your-ugrad-non.html">last blog post</a> I asked my readers to leave comments saying what the name of the course that has some of Regular Languages, Context Free Languages Decideability, P, NP (any maybe other stuff) in it. I suspected there would be many different names and their were. I was able to put all but 6 into 4 equivalence classes. So that's 10 names. Thats a lot especially compared to<br />
<br />
(Introduction to) Algorithms<br />
<br />
and<br />
<br />
(Introduction to) Cryptography<br />
<br />
which I suspect have far fewer names. One commenter pointed out that the reason for the many different names is that there are many versions of the course. That's not quite an explanation since there are also many different versions of Cryptography---at UMCP crypto is cross listed in THREE departments (CS, Math, EE) and its taught by 6 or so different people who don't talk to each other (I am one of them). I think Algorithms is more uniform across colleges.<br />
<br />
I think that terms Algorithms and Cryptography are both rather broad and can accommodate many versions of the courses, whereas no term seems to be agreed upon to encompass the DFA etc course.<br />
Even saying DFA etc is not quite right since some of the courses spend little or even no time on DFA's.<br />
<br />
Below is a list of all the names I got and some comments. Note that some schools appear twice since they have two courses along these lines.<br />
<br />
-----------------------------------------<br />
TITLE: (Introduction to) Theory of Computation:<br />
<br />
Swarthmore: Theory of Computation<br />
<br />
UCSD: Theory of Computation<br />
<br />
Saint Michaels: Theory of Computation<br />
<br />
Univ of Washington: Introduction to the Theory of Computation<br />
<br />
Waterloo: Introduction to the Theory of Computing<br />
<br />
COMMENT: Theory of Computation could have been the term that encompasses all of these courses. I speculate that it didn't catch on since it sounds too much like computability theory which is only one part of the course.<br />
<br />
------------------------<br />
TITLE: Formal Languages and XXX<br />
<br />
CMU: Formal Languages, Automata, and Computability<br />
<br />
Florida Tech: Formal Languages and Automata Theory<br />
<br />
UC-Irvine: Formal Languages and Automata Theory<br />
<br />
Univ of Chicago: Introduction to Formal Languages<br />
<br />
University of Bucharest: Formal Language and Automata<br />
<br />
TU Darmstadt: Formal Foundations of CS I: Automata, Formal Languages, and Decidability<br />
<br />
TUK Germany: Formal Languages and Computability<br />
<br />
COMMENT: The title makes it sound like they don't cover P and NP. I do not know if thats true; however, I speculate that, it could never be the encompassing term.<br />
<br />
Spell Check things Automata and Computability are not words, but I've googled them and they seem to be words.<br />
<br />
--------------------------<br />
TITLE: Computability/Decidability and Complexity/Intractability<br />
<br />
Reed College: Computability and Complexity<br />
<br />
Caltech: Decidability and Intractability<br />
<br />
COMMENT: The title makes it sound like they don't cover regular or context free languages. I do not know if that's true; however, I speculate that, since the terms sound that way, they never caught on as the general term.<br />
<br />
Spellecheck thinks that neither Decidability nor Decideability is a word. Google seems to say that I should leave out the e, so I will.<br />
<br />
------------------------------<br />
TITLE: Blah MODELS Blah<br />
<br />
Tel-Aviv (a long time ago) Computational Models<br />
<br />
UIUC: Algorithms and Models of Computation (also has some algorithms in it)<br />
<br />
Waterloo: Models of Computation (enriched version)<br />
<br />
COMMENT: Models of Computation sounds like a good name for the course! Too bad it didn't catch on. It would also be able to withstand changes in the content like more on parallelism or more on communication complexity.<br />
<br />
------------------------------<br />
TITLE: MISC<br />
<br />
CMU: Great Ideas in Theoretical Computer Science<br />
<br />
UCLouvain (Belgium) Calculabilite (Computability)<br />
<br />
Moscow Inst. of Phy. and Tech.: Mathematical logic and Theory of Algorithms<br />
<br />
Portland State University: Computational Structures<br />
<br />
Germany: Informatik III (Not all of Germany)<br />
<br />
Univ of Chicago: Introduction to Complexity<br />
<br />
COMMENT: All of these terms are to narrow to have served as a general term.<br />
<div>
<br /></div>
<br />
<br />https://blog.computationalcomplexity.org/2019/12/why-is-there-no-all-encompassing-term.htmlnoreply@blogger.com (GASARCH)12tag:blogger.com,1999:blog-3722233.post-693865784966232415Mon, 09 Dec 2019 04:00:00 +00002019-12-08T23:00:44.425-05:00What do you call your ugrad non-algorithms theory course?I am in the process of reviewing<br />
<br />
<i> What can be computed: A Practical Guide to the Theory of Computation</i><br />
<i> by John MacCormick</i><br />
<br />
<br />
and I need YOUR help for the first SENTENCE. I began by saying<br />
<br />
<br />
This is a text book for a course on <i>Formal Language Theory</i><br />
<i><br /></i>
but then I realized that this is not what we call the course at UMCP. Then I got to thinking: what do other schools call it? I have the following so far:<br />
<br />
UMCP: Elementary Theory of Computation<br />
<br />
Harvard: Introduction to Theory of Computation<br />
<br />
MIT: Automata, Computability, and, Complexity<br />
<br />
Clark: Automata Theory<br />
<br />
(My spellcheck does not think Automata is a word. Also Computability. Usually I listen to my spellcheckers, but I checked and YES, I spelled them right.)<br />
<br />
For some other schools I either hit a place I needed an account, or I just got titles without a description so I could not be sure.<br />
<br />This is where YOU come in!<br />
<br />
Please leave comments with your school and the title of the course at your school that covers a reasonable overlap with: Regular Sets, Context Free Sets, Decidable and Undecidble and r.e. sets, P, NP, perhaps other complexity classes, and NP-completeness. Its FINE if your answer is one of the above ones, or one of the other comments--- I plan to later set this up as a pigeonhole principle problem.<br />
<br />
I suspect that courses in algorithms are called <i>Algorithms </i>or <i>Introduction to Algorithms.</i><br />
<i><br /></i>
I suspect that courses in cryptography are called <i>Cryptography </i><i> </i>or <i>Intro to Cryptography.</i><br />
<br />
<br />
Why does the non-algorithm, non-crypto theory course have more names?<br />
<br />
<br />
<br />
<br />
<i><br /></i>
<br />https://blog.computationalcomplexity.org/2019/12/what-do-you-call-your-ugrad-non.htmlnoreply@blogger.com (GASARCH)27tag:blogger.com,1999:blog-3722233.post-1485483742428466612Mon, 02 Dec 2019 23:01:00 +00002019-12-03T17:21:50.267-05:00Julia Robinson's 100th birthdayOn Dec 8, 1919 Julia Robinson was born, so today is close to her 100th birthday (she passed away at<br />
<div>
the age of 65 on July 30, 1985).</div>
<div>
<br /></div>
<div>
So time for some facts about her</div>
<div>
<br /></div>
<div>
1) She got her PhD from Tarski where she proved the undecidability of the theory of the rationals.</div>
<div>
<br /></div>
<div>
2) She is probably best known for her work on Hilbert's tenth problem (which we call H10)</div>
<div>
<br /></div>
<div>
In todays' terminology H10 would be stated as:</div>
<div>
<br />
Find an algorithm that will, given p in Z[x_1,...,x_n] determine if it has an integer solution.</div>
<div>
<br /></div>
<div>
Hilbert posed it to inspire deep research in Number Theory. There are some cases that are</div>
<div>
solvable (the topic of a later blog post) but the general problem is undecidable. This is not what Hilbert was aiming for. I wonder if he would be happy with the resolution.</div>
<div>
<br /></div>
<div>
The Davis-Putnam-Robinson paper showed that the decision problem for exponential diophantine equations was undecidable. It was published in 1961. The paper is <a href="https://www.jstor.org/stable/1970289?seq=1#metadata_info_tab_contents">here</a>. Martin Davis predicted that the proof that H10 was undecidable would be by a young Russian mathematician. He was proven correct when Yuri Matiyasevich supplied the missing piece needed to complete the proof. </div>
<div>
<br /></div>
<div>
I often read `H10 was resolved by Davis-Putnam-Robinson and Matiyasevich' or sometimes they put all four names in alphabetical order. I like that--- it really was a joint effort.</div>
<div>
<br /></div>
<div>
3) She was inducted (a proof by induction?) into the National Academy of Sciences in 1975.</div>
<div>
<br /></div>
<div>
4) She was elected to be president of the American Math Society in 1982. </div>
<div>
<br /></div>
<div>
5) She got a MacAuthor Fellowship prize in 1985 (Often called the MacAuthor Genius award.)</div>
<div>
At the time it was worth $60,000. Its now $625,000.</div>
<div>
<br /></div>
<div>
6) She also did work in Game Theory. Her paper An Iterative Method of Solving a Game, which is<br />
<a href="https://www.jstor.org/stable/1969530?seq=1#metadata_info_tab_contents">here</a>, is a proof from the book according to Paul Goldberg's comment on this post.</div>
<div>
<br /></div>
<div>
7) The Julia Robinson Math Festival is named in her honor (hmmm- is that a tautology?) Its purpose is to inspire K-12 students to get involved in math. For more on it see <a href="https://en.wikipedia.org/wiki/Julia_Robinson_Mathematics_Festival">here</a>.<br />
<br />
8) (ADDED LATER) Commenter David Williamson pointed out that Julia Robinson did work on the transportation problem. See his comment and his pointer to the paper.<br />
<br />
(ADDED LATER) When I hear <i>Julia Robinson</i> I think <i>Hilbert's 10th problem. </i> I suspect many of you do the same. However, looking at items 6 and 8 above, one realizes that she did research in non-logic branches of math as well.</div>
<div>
<br /></div>
<div>
<br /></div>
<div>
<br /></div>
https://blog.computationalcomplexity.org/2019/12/julia-robinsons-100th-birthday.htmlnoreply@blogger.com (GASARCH)9tag:blogger.com,1999:blog-3722233.post-3436178446517561376Mon, 18 Nov 2019 04:53:00 +00002019-11-17T23:53:55.061-05:00Fields used to be closer together than they are now. Good? Bad?There was a retired software Eng professor that I had heard two very non-controversial rumors about:<br />
<br />
1) He got his PhD in Numerical Analysis<br />
<br />
2) He got his PhD in Compiler Optimization.<br />
<br />
So I asked him which was true.<br />
<br />
The answer: Both! In those days you had to optimize your code to get your NA code to run fast enough.<br />
<br />
We cannot imagine that anymore. Or at least I cannot.<br />
<br />
Over time the fields of computer science advance more so its hard to be master of more than one field. But its not that simple: there has been work recently applying Machine Learning to... well<br />
everything really. Even so, I think the trend is more towards separation. Or perhaps it oscillates.<br />
<br />
I am NOT going to be the grumpy old man (Google once thought I was 70, see <a href="https://blog.computationalcomplexity.org/2018/10/google-added-years-to-my-life.html">here</a>) who says things were better in my day when the fields were closer together. But I will ask the question:<br />
<br />
1) Are people more specialized new? While I think yes since each field has gotten more complicated and harder to master. There are exceptions: Complexity theory uses much more sophisticated mathematics then when I was a grad student (1980-1985), and of course Quantum Computing has lead to more comp sci majors knowing physics.<br />
<br />
2) Is it good for the field that people are specialized? I am supposed to say that it is terrible and that great advances are made when people are interdiscplinary. But there are many more small advances that are made by someone who has a mastery of one (or two) fields.<br />
<br />
3) The PhD Process and the Tenure Process encourage specialization. This I think IS bad since there are different modes of research that should all be respected.'<br />
<br />
<br />https://blog.computationalcomplexity.org/2019/11/fields-used-to-be-closer-together-than.htmlnoreply@blogger.com (GASARCH)3tag:blogger.com,1999:blog-3722233.post-7340761877463675609Mon, 11 Nov 2019 15:09:00 +00002019-11-11T10:09:38.063-05:00A non-moral dilemma about cheating, but it brings up some pointsI often give two versions of an exam and TELL THE STUDENTS I am doing this so that they don't even try to cheat. I've even had two different classes take the midterm at the same time, same room, every other seat, so the person next to you is in a different course. And I TELL THE STUDENTS that I am doing this. A colleague of mine says I shouldn't TELL THE STUDENTS. Here are our arguments<br />
<br />
1) Don't tell: students cheat a lot and this is a way to catch them.<br />
<br />
2) Tell: Dealing with cheating distracts from our mission of teaching so best to be preventative so it does not happen. Less noble- tell them so that you don't have to deal with the cheating issue.<br />
<br />
I have heard of the following case at a diff school some years ago and want your take on it:<br />
there was one question on the midterm that was different on the two exams- the prof changed the key number, but they were the same question really. The prof was in a hurry for some reason and <i>FORGOT TO TELL THE STUDENTS</i>. You can probably guess what happened next, but not what happened after that<br />
<br />
One of the students exams had the solution to THE OTHER PROBLEM on it. Clearly cheating. When called in the student said:<br />
<br />
<i>Since you didn't tell us that they were different exams the cheating claim is unfair!</i><br />
<i><br />
</i> They DID admit their guilt, but they DID NOT have any contrition.<br />
<br />
Options for what penalty to go for:<br />
<br />
1) A 0 on the exam itself<br />
<br />
2) An F in the course<br />
<br />
3) A notation on the transcript indicating Failed-because-cheated. I don't know what that notation was at the schol the story took place, but at UMCP its XF. (Side Note- not clear if someone outside of UMCP looks at a transcript and sees an XF they'll know what the means. But the F part makes it look bad.)<br />
<br />
4) Expulsion from school. (This might not be the profs call- this may depend on if its a first offense.)<br />
<br />
The lack of contrition bothers me, though the prof who told me the story said that the student may have said it out of shock- the first thing that came into their mind. I asked the prof how the student was doing in the class and the prof said, CORRECTLY, that that is irrelevant.<br />
<br />
SO- what penalty would you go for?<br />
<br />
The professor went for XF. The student, at the hearing, once again said<br />
<br />
<br />
<i>Since you didn't tell us that they were different exams the cheating claim is unfair!</i><br />
<br />
The professor told me that he thinks the student was trying to claim it was entrapment, though he had a hard time expressing this coherently. If the student had been a coherent thinker, he probably wouldn't have needed to cheat.<br />
<br />
He got the equivalent of an XF. <br />
<br />
But here is my real question: Should we TELL THE STUDENTS that they are different exams (I think yes) or<br />
should we NOT tell them so can catch them?<br />
<br />
<br />
<br />
<br />
<br />
<br />https://blog.computationalcomplexity.org/2019/11/a-non-moral-dilemma-about-cheating-but.htmlnoreply@blogger.com (GASARCH)11tag:blogger.com,1999:blog-3722233.post-6412925669087119335Mon, 04 Nov 2019 06:04:00 +00002019-11-04T01:04:54.796-05:00Limits of using the web for info- self-reference(I wrote this a while back so when I say `I Googled BLAH' I meant back then. It is prob different now.)<br />
<br />
While the web is a <i>wonderful</i> to find things out there are times when it doesn't quite work. <br />
<ol>
<li> An old blog of Scott Aaronson's had as part of its title <a href="http://scottaaronson.com/blog/?p=240">a Woitian Link</a>. Wanting to find out what <i>a Woitian Link</i> is but not wanting to bother Scott (he's busy enough making comments on Shtetl-Optimized) I went to google and typed in <i>"Woitian Link"</i>. The ONLY hits I got back were to Scotts blog. I finally had to email Scott. He told me that it was referring to the blog <a href="http://www.math.columbia.edu/~woit/wordpress">not even wrong</a> by Peter Woit which often has links that... Well, Scott never told me quite what it was but I'll go there myself and try to figure it out.<br />
</li>
<li> An old blog of mine was <a href="http://weblog.fortnow.com/2007/05/man-who-loved-algorithms.html">the man who loved algorithms</a>. Part of my blog said that I thought the man would be Knuth but it was not. (It was Thomas Kailath) One of the commenters said that it couldn't be Knuth since he was still alive. This made me want to check the original article to see if Thomas Kailath, is also still alive (he is). I didn't have the issue with me at the time so I typed "the man who loved algorithms" into google. The first page of hits all refered to my posting. Eventually I found one to verify that yes, indeed, he was still alive.<br />
</li>
<li> Donald Knuth VOLUME FOUR was originally published in a series of fascicile's. Whats a fascicle? Here the web was helpful- Wikipedia said it was a book that comes out in short pieces, the pieces of which are called `fascicle'. They gave only one example: <i>Donald Knuth's Volume 4 will be coming out in Fascicle.</i> Still, they DID tell me what I want to know. (Note- this was a while back, they have since removed that comment.) For most things the web is great. But for some more obscure things, better off asking someone who knows stuff. </li>
</ol>
<div>
Do you have experiences where you ask the web for a question and you end up in a circle?</div>
https://blog.computationalcomplexity.org/2019/11/limits-of-using-web-for-info-self.htmlnoreply@blogger.com (Unknown)2tag:blogger.com,1999:blog-3722233.post-7436762088132666017Thu, 31 Oct 2019 18:46:00 +00002019-10-31T14:46:40.287-04:00Statistics to ScareSo how do you parse the following paragraph from Monday's NYT <a href="https://www.nytimes.com/2019/10/28/briefing/wildfires-impeachment-facebook.html">Evening Breifing</a>.<br />
<blockquote class="tr_bq">
A study in JAMA Pediatrics this year found that the average Halloween resulted in four additional pedestrian deaths compared with other nights. For 4- to 8-year-olds, the rate was 10 times as high.</blockquote>
The paragraph means the percent increase for pedestrian deaths for 4-8 year olds was ten time the percent increase for people as a whole, a number you cannot determine from the information given. Using the fact that roughly 7% of Americans are in the 4-8 year range, that yields a little under three additional deaths for 4-8 year olds and about one for the other age ranges.<br />
<br />
The <a href="https://dx.doi.org/10.1001/jamapediatrics.2018.4052">paper</a> unfortunately sits behind a firewall. But I found a <a href="http://10.0.3.233/jamapediatrics.2018.4052">press release</a>.<br />
<blockquote class="tr_bq">
Children in the United States celebrate Halloween by going door-to-door collecting candy. New research suggests the popular October 31 holiday is associated with increased pedestrian traffic fatalities, especially among children. Researchers used data from the National Highway Traffic Safety Administration to compare the number of pedestrian fatalities from 1975 to 2016 that happened on October 31 each year between 5 p.m. and 11:59 p.m. with those that happened during the same hours on a day one week earlier (on October 24) and a day one week later (on November 7). During the 42-year study period, 608 pedestrian fatalities happened on the 42 Halloween evenings, whereas 851 pedestrian fatalities happened on the 84 other evenings used for comparison. The relative risk (an expression of probability) of a pedestrian fatality was higher on Halloween than those other nights. Absolute mortality rates averaged 2.07 and 1.45 pedestrian fatalities per hour on Halloween nights and the other evenings, respectively, which is equivalent to the average Halloween resulting in four additional pedestrian deaths each year. The biggest risk was among children ages 4 to 8. Absolute risk of pedestrian fatality per 100 million Americans was small and declined from 4.9 to 2.5 between the first and final decades of the study interval. </blockquote>
Doing the math, we see a 43% increase and a more than quintupling the number of pedestrian deaths for the youngsters. That sounds scary indeed. though it only adds up to a handful of deaths. Moreover the authors didn't take into account the larger number of pedestrians on Halloween, particularly among 4-8 year olds.<br />
<br />
A smaller fraction of people die as pedestrians on Halloween today then on a random day when I was a kid. I wonder if that's because there are fewer pedestrians today.<br />
<br />
Also from the New York Times, a sociologist has found "no evidence that any child had been seriously injured, let alone killed, by strangers tampering with candy." I feel lied to as a kid.<br />
<br />
So the upshot: Tell your kids to take the usual precautions but mostly let them dress up, have fun trick-or-treating and enjoy their candy.https://blog.computationalcomplexity.org/2019/10/statistics-to-scare.htmlnoreply@blogger.com (Lance Fortnow)0