tag:blogger.com,1999:blog-3722233Thu, 14 Nov 2019 11:17:11 +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)Blogger2723125tag: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)6tag: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)0tag:blogger.com,1999:blog-3722233.post-3222567344389850699Mon, 28 Oct 2019 14:05:00 +00002019-10-28T10:05:08.179-04:00Random non-partisan thoughts on the Prez Election<br />
This post is non-partisan, but in the interest of full disclosure I disclose that I will almost surely be voting for the Democratic Nominee. And I say <i>almost surely</i> because very weird things could happen.I can imagine a republican saying, in 2015 <i>I will almost surely be voting for the Republican Nominee</i> and then later deciding to not vote for Trump. <br />
<br />
<br />
<i>My Past Predictions</i>: Early on in 2007 I predicted it would be Obama vs McCain and that Obama would win. Was I smart or lucky? Early in 2011 I predicted Paul Ryan would be the Rep. Candidate. Early in 2015 and even into 2016 I predicted that Trump would not get the nomination. After he got the nomination I predicted he would not become president. So, in answer to my first question, I was lucky not smart. Having said all of this I predict that the Dem. candidate will be Warren. Note- this is an honest prediction, not one fueled by what I want to see happen. I predict Warren since she seems to be someone who can bridge the so-called establishment and the so-called left (I dislike the terms LEFT and RIGHT since issues and views change over time). Given my past record I would not take me too seriously. Also, since this prediction is not particularly unusual, if I am right this would NOT be impressive (My Obama prediction was impressive, and my Paul Ryan prediction would have been very impressive had I been right.)<br />
<br />
<i>Electability</i>: My spell checker doesn't think its a word. Actually it shouldn't be a word. It's a stupid concept. Recall<br />
<br />
JFK was unelectable since he was Catholic. <br />
<br />
Ronald Reagan was unelectable because he was too conservative.<br />
<br />
A draft dodging adulterer named Bill Clinton could not possible beat a sitting president who just won a popular war.<br />
<br />
Nobody named Barack Hussein Obama, who is half-black, could possibly get the nomination, never mind the presidency. And Hillary had the nomination locked up in 2008--- she had no any serious challengers. <br />
<br />
(An article in <i>The New Republic</i> in 2007 predicted a brokered convention for the Republicans where Fred Thompson, Mitt Romney, and Rudy Guilliani would split the vote, and at the same time a cake walk for Hillary Clinton with<br />
Barak Obama winning Illinois in the primaries but not much else. Recall that 2008 was McCain vs Obama.)<br />
<br />
Donald Trump will surely be stopped from getting the nomination because, in the end, <a href="https://www.amazon.com/Party-Decides-Presidential-Nominations-American/dp/0226112373/ref=cm_cr_arp_d_product_top?ie=UTF8">The Party Decides</a>.<br />
<br />
Republican voters in 2016 will prefer Rubio to Trump since Marco is more electable AND more conservative. Hence, in the space of Rep. Candidates, Rubio dominates Trump. So, by simple game theory, Trump can't get the nomination. The more electable Rubio, in the 2016 primaries, won Minnesota, Wash DC, and Puerto Rico (Puerto Rico has a primary. Really!) One of my friends thought he also won Guam (Guam?) but I could not find evidence of that on the web. Okay, so why did Trump win? <i>Because voters are not game theorists.</i><br />
<br />
ANYWAY, my point is that how can anyone take the notion of electability seriously when unelectable people have gotten elected?<br />
<br />
<i>Primaries</i>: Dem primary voters are torn between who they want to be president and who can beat Trump. Since its so hard to tell who can beat who, I would recommend voting for who you like and not say stupid things like<br />
<br />
American would never elect a 76 year old socialist whose recently had a heart attack.<br />
<br />
or<br />
<br />
Trump beat a women in 2016 so we can't nominate a women<br />
<br />
or<br />
<br />
America is not ready to elect a gay president yet. (America is never ready to do X until after it does X and then the pundits ret-con their opinions.For example, of course America is ready for Gay-Marriage. Duh.)<br />
<br />
<i>Who won the debate?<br />
</i> Whoever didn't bother watching it :-). I think the question is stupid and has become who got out a clever sound bite. We need sound policy, not sound bites!https://blog.computationalcomplexity.org/2019/09/random-non-partisan-thoughts-on-prez.htmlnoreply@blogger.com (GASARCH)2tag:blogger.com,1999:blog-3722233.post-6670392427379771547Mon, 21 Oct 2019 15:47:00 +00002019-10-21T11:47:23.166-04:00Differentiation and IntegrationRecently there was an excellent xkcd about differentiation and integration, see <a href="https://xkcd.com/2117/">here</a>.<br />
<br />
This brings up thoughts on diff and int:<br />
<br />
1) For some students Integration is when math gets hard.<br />
<br />
Diff (at least on the level of Calc I) is rote memorization. A computer program can EASILY do diff<br />
<br />
Integration by humans requires more guesswork and thought, Computers can now do it very well but I think that it was harder to get to work.<br />
<br />
Someone who has worked on programs for both, please comment.<br />
<br />
2) When I took Honors Calculus back in 1976 (from Jeff Cheeger at SUNY Stonybrook) he made a comment which really puzzled the class, and myself, but later I understood it:<br />
<br />
<i>Integration is easier than Differentiation</i><br />
<br />
The class thought this was very odd since the problem of, GIVEN a function, find its diff was easier than GIVEN a function, find its int. And of course I am talking about the kinds of functions one is<br />
given in Calc I and Calc II, so this is not meant to be a formal statement.<br />
<br />
What he meant was that integration has better mathematical properties than differentiation. For example, differentiating the function f(x)=abs(x) (absolute value of x) is problematic at 0, where it has no problem with integration anywhere (alas, if only our society was as relaxed about integration as f(x)=abs(x) is).<br />
<br />
So I would say that the class and Dr. Cheeger were both right (someone else might say they were both wrong) we were just looking at different notions of easy and hard.<br />
<br />
Are there other cases in math where `easy' and `hard' can mean very different things?<br />
<br />
<br />
<br />
https://blog.computationalcomplexity.org/2019/10/differentiation-and-integration.htmlnoreply@blogger.com (GASARCH)4tag:blogger.com,1999:blog-3722233.post-4529441142077494484Thu, 17 Oct 2019 20:50:00 +00002019-10-17T17:58:08.623-04:002019 Fall Jobs PostStarting PhD students over time would always assume that the computer science academic job market would be a strong or as weak when they graduate as it is when they were starting, and they would always be wrong. That may have changed. We've had such a stretch of strong growth in computer science, starting as we pulled out of the financial crisis in 2012, that students who started in the strong market back then see only a much stronger market today.<br />
<br />
Every fall I recap advice for students, and others, looking for academic jobs. Best source are the ads from the <a href="https://cra.org/ads/">CRA</a> and the <a href="https://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. 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. The CRA just published a <a href="https://cra.org/2019-member-book-full-size">member book</a>, a collection of one pagers for several departments, almost all of which are trying to grow.<br />
<br />
Needless to say we're trying to greatly expand computing at Illinois Tech, come <a href="https://science.iit.edu/computer-science/people/openings#tenure-track">join us</a>.<br />
<br />
Something new this year, CATCS is <a href="https://thmatters.wordpress.com/2019/10/02/a-solicitation-for-tcs-job-market-profiles/">collecting and disseminating</a> profiles of junior theory researchers on the job market this year. Definitely take advantage whether to sign up as a job seeker or to reach out to theorists on the market once the profiles are posted. The CRA also maintains a <a href="https://cra.org/cv-database/">CV database</a> for candidates for academic, industrial and government research positions.<br />
<br />
While this is a job-seekers market, you still need to put your best foot forward. Reach out to professors at conferences, such as the upcoming FOCS. Polish your CV and get your Google Scholar page in good shape. Practice your job talk, a bad one can kill your visit. Research the people you will see during the interview ahead of time, I like to write down one interesting discussion topic for each. You'll need to sell yourself to non-theorists. Data, cybersecurity and quantum are hot this year, highlight your work in those areas without making it look fake.<br />
<br />
In any case have fun! You'll meet lots of interesting people in your job search and eat way too much.https://blog.computationalcomplexity.org/2019/10/2019-fall-jobs-post.htmlnoreply@blogger.com (Lance Fortnow)3tag:blogger.com,1999:blog-3722233.post-4589067189308524430Mon, 14 Oct 2019 02:11:00 +00002019-10-13T22:11:15.690-04:00The Sheldon Conjecture (too late for Problems with a Point)<br />
Chapter 5 of <i>Problems with a Point</i> (by Gasarch and Kruskal) is about how mathematical objects get their names. If it was an e-book that I could edit and add to (is this a good idea or not? later on that) then I would have added the following.<br />
<br />
<b>The Sheldon Conjecture</b><br />
<br />
Background: Nobel Laureate Sheldon Cooper has said that 73 is the best number because<br />
<br />
a) 73 is prime.<br />
<br />
b) 73 is the 21st prime and note that 7*3=21.<br />
<br />
c) The mirror of 73, namely 37, is prime.<br />
<br />
d) 37 is the 12th prime, and 12 is the mirror of 21.<br />
<br />
Sheldon never quite said its the <i>only</i> such number; that was conjectured by Jessie Byrnes, Chris Spicer, and Alyssa Turnquist <a href="http://digital.ipcprintservices.com/article/The_SHELDON_CONJECTURE/2298528/276852/article.html">here</a>. They called it <i>Sheldon's Conjecture</i> probably since Sheldon Cooper <i>should have</i> conjectured it <br />
<br />
Why didn't Sheldon make Sheldon's conjecture? This kind of question has been asked before:<br />
<br />
<br />
<br />
<a href="https://arxiv.org/abs/1701.04718">Could Euler have conjectured the prime number theorem</a><br />
<br />
<a href="https://arxiv.org/abs/1611.06303">Why didn't Hilbert (or others) pursue Ramsey Theory?</a> <br />
<br />
(readers are encouraged to give other examples)<br />
<br />
I doubt we'll be asking this about Sheldon Cooper since he is a fictional character.<br />
<br />
I am delighted that<br />
<br />
a) There is a Sheldon's Conjecture.<br />
<br />
b) It has been solved by Pomerance and Spicer, see <a href="https://math.dartmouth.edu/~carlp/sheldon02132019.pdf">here</a><br />
<br />
Actually (b) might not be so delightful--- once a conjecture is proven its stops being called by the name of the conjecturer. If you don't believe me just ask Vazsonyi or Baudet. If you don't know who they are then (1) see <a href="https://blog.computationalcomplexity.org/2009/08/how-much-credit-should-conjecturer-get_14.html">here</a> and (2) that proves my point. So perhaps I wish it had not been solved so <i>The Sheldon Conjecture</i> would live on as a name.<br />
<br />
Another issue this brings up: Lets say that <i>Problems with a Point</i> was an online book that I was able to edit easily. Then I might add material on <i>The Sheldon Conjecture</i>. And while I am at it, I would add <i>The Monty Hall Paradox</i> to the chapter on how theorems get there names. Plus, I would fix some typos and references. Perhaps update some reference. Now lets say that all books were online and the authors could modify them. Would this be good or bad?<br />
<br />
1) Good- The book would get better and better as errors got removed.<br />
<br />
2) Good- The book would get to include material that is appropriate but came out after it was published.<br />
<br />
3) Good- The book would get to include material that is appropriate but the authors forgot to include the first time around.<br />
<br />
4) Bad- For referencing the book or for book reviews of the book, you are looking at different objects. The current system has First Edition, Second Edition, etc, so you can point to which one you are looking at. The easily-edited books would have more of a continuous update process so harder to point to things. <br />
<br />
5) Bad- When Clyde and I emailed the final version to the publisher we were almost done. When we got the galleys and commented on them we were DONE DONE! For typos and errors maybe I want to fix them online, but entire new sections--- when we're done we are DONE.<br />
<br />
6) Bad- at what point is it (i) a corrected version of the old book, (ii) a new edition of the old book, (iii) an entirely new book? Life is complicated enough.<br />
<br />
I would prob like a system where you can fix errors but can't add new material. Not sure if that's really a clean distinction.<br />
https://blog.computationalcomplexity.org/2019/10/the-sheldon-conjecture-too-late-for.htmlnoreply@blogger.com (GASARCH)3tag:blogger.com,1999:blog-3722233.post-7770596683111395863Thu, 10 Oct 2019 19:47:00 +00002019-10-10T16:22:33.167-04:00William Kruskal's 100th birthdayToday, Oct 10, 2019 is William Kruskal's 100th birthday (he's dead, so no cake. Oh well.) William Kruskal was a great statistician. To honor him we have a guest post by his nephew Clyde Kruskal. We also note that the Kruskal Family is one of the top two math families of all time (see <a href="https://blog.computationalcomplexity.org/2009/02/baseball-families-and-math-families.html">here</a>). William is a reason why the other two Kruskal brothers went into mathematics: As a much older sibling (6 years older than Martin and 8 years older than Joseph), he encouraged their early mathematical development. <br />
<br />
Here are some pictures of William Kruskal and of the Kruskal Family: <a href="https://www.cs.umd.edu/users/gasarch/BLOGPAPERS/billk1.pdf">here</a><br />
<br />
<b>Guest Post by Clyde Kruskal<br />
</b><br />
<br />
I was asked to blog about my uncle, the statistician, William H. Kruskal, on the centennial of his birth. We called him Uncle Bill. He is best known for co-inventing the Kruskal-Wallis test.<br />
<br />
There are two stories that I know about Bill's childhood, which must have been family lore:<br />
<br />
(1) As a young child, Bill was a prolific reader. His reading comprehension outstripped his conversational English. One morning, having just read the word ``schedule'' in a book, and obviously having never heard it pronounced, he sat down to breakfast and asked:<br />
"What is the ske·D<span STYLE="text-decoration:overline">U</SPAN>·l<span STYLE="text-decoration:overline">e</SPAN> for today?"<br />
<br />
(2) My grandparents once had Bill take an occupational assessment test. The tester said that Bill was a very bright child, and should become a traffic engineer to solve the problems with traffic congestion. (This would have been the 1920s!) As you probably know, Uncle Bill did not succeed in ending traffic congestion. Oh well.<br />
<br />
<br />
Recently there has been a controversy over whether to ask about citizenship in the 2020 census. In the late 1900s there was a different controversy: whether to adjust the known undercount statistically. In general, Democrats wanted to adjust the count and Republicans did not (presumably because Democratic states tended to have a larger undercount). A national committee was set up to study the issue, with four statisticians in favor and four against. I was surprised to learn that Uncle Bill was on the commission as one of those against adjustment, since, I thought his political views were more closely aligned with those of the Democrats. He was very principled, basing his views only on statistical arguments. I saw him give a talk on the subject, which seemed quite convincing (but, then again, I did not see the other side). They ended up not adjusting. <br />
<br />
<br />
For more on William Kruskal, in general, and his view on adjusting the census, in particular, see the pointers at the end of this post.<br />
<br />
<br />
I have more to say. I just hope that I am on the ske·D<span STYLE="text-decoration:overline">U</SPAN>·l<span STYLE="text-decoration:overline">e</SPAN> to blog about Uncle Bill at the bicentennial of his birth.<br />
<br />
<br />
<a href="https://www.cs.umd.edu/users/gasarch/BLOGPAPERS/wkruskalleg.pdf">The William Kruskal Legacy: 1919-2005 by Fienberg, Stigler, and Tanur</a><br />
<br />
<a href="http://www-history.mcs.st-and.ac.uk/Biographies/Kruskal_William.html">A short biography of William Kruskal by J.J. O'Connor and E.F. Robertson </a><br />
<br />
<a href="https://www.cs.umd.edu/users/gasarch/BLOGPAPERS/wkruskalfriend.pdf">William Kruskal: Mentor and Friend by Judith Tanur</a><br />
<br />
<a href="https://arxiv.org/pdf/0710.5077.pdf">William Kruskal: My Scholarly and Scientific Model by Stephen Fienberg</a><br />
<br />
<a href="https://www.cs.umd.edu/users/gasarch/BLOGPAPERS/wkruskalconv.pdf">A conversation with William Kruskal by Sandy Zabell</a><br />
<br />
<a href="http://www.loc.gov/law/find/hearings/pdf/00183650932.pdf">Testimony for house subcommittee on census and population for 1990 (see page 140)</a><br />
<br />
<br />
<br />
<br />
<br />
<br />
https://blog.computationalcomplexity.org/2019/10/william-kruskals-100th-birthday.htmlnoreply@blogger.com (GASARCH)0tag:blogger.com,1999:blog-3722233.post-1096889632414067693Mon, 07 Oct 2019 13:56:00 +00002019-10-07T09:56:23.862-04:00What comes first theory or practice? Its Complicated!Having majored in pure math I had the impression that usually the theory comes first and then someone works out something to work in practice. While this is true sometimes it is often NOT true and this will not surprise any of my blog readers. Even so, I want to tell you about some times it surprised me. This says more about my ignorance than about math or applications or whatnot.<br />
<br />
1) Quantum<br />
<br />
a) Factoring was proven to be in BQP way before actual quantum computers could do this in reasonable time (we're still waiting).<br />
<br />
b) Quantum Crypto- This really is out there. I do not know what came first, the theory or the practice. Or if they were in tandem.<br />
<br />
c) (this one is the inspiration for the post) When I first heard the term <i>Quantum Supremacy</i> I thought it meant the desire for a THEOREM that problem A is in BQP but is provably not in P. For example, if someone proved factoring is not in P (unlikely this will be proven, and hey- maybe factoring is in P). Perhaps some contrived problem like those constructed by diagonalization (my spell checker thinks that's not a word. Having worked in computability theory, I think it is. Darn- my spellchecker thinks computability is not word.) Hence when I heard that Google had a paper proving Quantum Supremacy (I do not recall if I actually heard the word <i>proven) </i>I assumed that there was some <i>theoretical </i>breakthrough. I was surprised and not in the slightest disappointed to find out it involved actual quantum computers.<br />
<br />
<b>Question</b>: When the term <i>Quantum Supremacy</i> was first coined, did they mean theoretical, or IRL, or both?<br />
<br />
2) Ramsey Theory<br />
<br />
a) For Ramsey's Theorem and Van Der waerden's theorem and Rado's theorem and others I could name, first a theorem showed a upper bound on a number, then later computers and perhaps some math got better bounds on that number.<br />
<br />
b) Consider the following statement:<br />
<br />
For all c there exists P such that for all c-colorings of {1,...,P} there exists x,y,z the same color such that x<sup>2</sup> +y<sup>2</sup> = z<sup>2</sup>.<br />
<br />
Ronald Graham conjectured the c=2 case and offered $100 in the 1980's. (I do not know if he had any comment on the general case.) I assumed that it would be proven with ginormous bounds on the P(c) function, and then perhaps some reasonable bound would be found by clever programming and some math. (see <a href="https://en.wikipedia.org/wiki/Boolean_Pythagorean_triples_problem">here</a> for the Wikipedia Entry about the problem, which also has pointers to other material).<br />
<br />
Instead the c=2 case was proven with an exact bound, P(2)=7825, by a computer program, in 2016. The proof is 200 terabytes. So my prediction was incorrect.<br />
<br />
As for the result<br />
<br />
PRO: We know the result is true for c=2 and we even know the exact bound. Wow! and for Ramsey Theory its unusual to have exact bounds!<br />
<br />
CON: It would be good to have a human-readable proof. This is NOT an anti-technology statement. For one thing, a human-readable proof might help us get the result for c=3 and beyond.<br />
<br />
3) This item is a cheat in that I knew the empirical results first. However, I will tell you what I am sure I would have thought (and been wrong) had I not know them.<br />
<br />
Given k, does the equation<br />
<br />
<br />
x<sup>3</sup> +y<sup>3</sup> +z<sup>3</sup> = k<br />
<br />
have a solution in Z? I would have thought that some hard number theory would determine<br />
for which k it has a solution (with a proof that does not give the actual solutions) and for then a computer programs would try to find the solutions. Instead (1) some values of k are ruled out by simple mod considerations, and (2) as for the rest, computers have found solutions for some of them. Lipton-Regan (<a href="https://rjlipton.wordpress.com/2019/09/30/writing-33-as-a-sum-of-cubes/">here</a>) and Gasarch (<a href="https://blog.computationalcomplexity.org/2019/04/x-3-y-3-z-3-33-has-solution-in-z-and.html">here</a>) have blogged about the k=33 case. Lipton-Regan also comment on the more recent k=42 case.<br />
<br />
<br />
https://blog.computationalcomplexity.org/2019/10/what-comes-first-theory-or-practice-its.htmlnoreply@blogger.com (GASARCH)4tag:blogger.com,1999:blog-3722233.post-3615744836127152440Thu, 03 Oct 2019 19:41:00 +00002019-10-03T16:08:28.797-04:00Quantum Supremacy: A Guest Post by Abhinav DeshpandeI am delighted to introduce you to Abhinav Deshpande, who is a graduate student at the University of Maryland, studying Quantum Computing. This will be a guest post on the rumors of the recent Google breakthrough on Quantum Supremacy. For other blog posts on this exciting rumor, see <a href="https://www.scottaaronson.com/blog/?p=4317">Scott Aaronson's post</a>, <a href="https://www.scottaaronson.com/blog/?p=4342">Scott Aaronson's second post on it</a>, <a href="https://www.quantamagazine.org/john-preskill-explains-quantum-supremacy-20191002/">John Preskill's quanta article</a>, <a href="https://blog.computationalcomplexity.org/2019/09/quantum-supremacy.html">Fortnow's post</a>,<br />
and there may be others.<br />
<br />
Guest post by Abhinav:<br />
<br />
I (Abhinav) thank Bill Fefferman for help with this post, and Bill Gasarch for inviting me to do a guest post.<br />
<br />
<br />
<b>The quest towards quantum computational supremacy</b><br />
<br />
September saw some huge news in the area of quantum computing, with rumours that the Google AI Lab has achieved a milestone known as 'quantum computational supremacy', also termed 'quantum supremacy' or 'quantum advantage' by some authors. Today, we examine what this term means, the most promising approach towards achieving this milestone, and the best complexity-theoretic evidence we have so far against classical simulability of quantum mechanics. We will not be commenting on details of the purported paper since there is no official announcement or claim from the authors so far.<br />
<br />
<b>What it means</b><br />
<br />
First off, the field of quantum computational supremacy arose from trying to formally understand the differences in the power of classical and quantum computers. A complexity theorist would view this goal as trying to give evidence to separate the complexity classes BPP and BQP. However, it turns out that one can gain more traction from considering the sampling analogues of these classes, SampBPP and SampBQP. These are classes of distributions that can be efficiently sampled on classical and quantum computers, respectively. Given a quantum circuit U on n qubits, one may define an associated probability distribution over 2^n outcomes as follows: apply U to the fiducial initial state |000...0> and measure the resulting state in the computational basis. This produces a distribution D_U.<br />
<br />
A suitable way to define the task of simulating the quantum circuit is as follows<b style="font-style: italic;">:</b><br />
<br />
Input: Description of a quantum circuit U acting on n qubits.<br />
<br />
Output: A sample from the probability distribution D_U obtained by measuring U|000...0> in the computational basis.<br />
<br />
One of the early works in this field was that of <a href="https://arxiv.org/abs/quant-ph/0205133">Terhal and DiVincenzo</a>, which first considered the complexity of sampling from a distribution (weak simulation) as opposed to that of calculating the exact probability of a certain outcome (strong simulation). Weak simulation is arguably the more natural notion of simulating a quantum system, since in general, we cannot feasibly compute the probability of a certain outcome even if we can simulate the quantum circuit. Subsequent works by <a href="https://arxiv.org/abs/1011.3245">Aaronson and Arkhipov</a>, and by <a href="https://arxiv.org/abs/1005.1407">Bremner, Jozsa, and Shepherd</a> established that if there is a classically efficient weak simulator for different classes of quantum circuits, the polynomial hierarchy collapses to the third level.<br />
<br />
<br />
So far, we have only considered the question of exactly sampling from the distribution D_U. However, any realistic experiment is necessarily noisy, and a more natural problem is to sample from a distribution that is not exactly D_U but from any distribution D_O that is ε-close in a suitable distance measure, say the variation distance.<br />
<br />
The aforementioned work by Aaronson and Arkhipov was the first to consider this problem, and they made progress towards showing that a special class of quantum circuits (linear optical circuits) is classically hard to approximately simulate in the sense above. The task of sampling from the output of linear optical circuits is known as boson sampling. At the time, it was the best available way to show that quantum computers may solve some problems that are far beyond the reach of classical computers.<br />
<br />
Even granting that the PH doesn't collapse, one still needs to make an additional conjecture to establish that boson sampling is not classically simulable. The conjecture is that additively approximating the output probabilities of a random linear optical quantum circuit is #P-hard. The reason this may be true is that output probabilities of random linear optical quantum circuits are Permanents of a Gaussian random matrix, and the Permanent is as hard to compute on a random matrix as it is on a worst-case matrix. Therefore, the only missing link is to go from average-case hardness of exact computation to average-case hardness of an additive estimation. In addition, if we make a second conjecture known as the "anti-concentration" conjecture, we can show that this additive estimation is non-trivial: it suffices to give us a good multiplicative estimation with high probability.<br />
<br />
So that's what quantum computational supremacy is about: we have a computational task that is efficiently solvable with quantum computers, but which would collapse the polynomial hierarchy if done by a classical computer (assuming certain other conjectures are true). One may substitute "collapse of the polynomial hierarchy" with stronger conjectures and incur a corresponding tradeoff in the likelihood of the conjecture being true.<br />
<br />
<b>Random circuit sampling</b><br />
<br />
In 2016,<a href="https://arxiv.org/abs/1608.00263"> Boixo et al</a>. proposed to replace the class of quantum circuits for which some hardness results were known (commuting circuits and boson sampling) by random circuits of sufficient depth on a 2D grid of qubits having nearest-neighbour interactions. Concretely, the proposed experiment would be to apply random unitaries from a specified set on n qubits arranged on a 2D grid for sufficient depth, and then sample from the resulting distribution. The two-qubit unitaries in the set are restricted to act between nearest neighbours, respecting the geometric This task is called random circuit sampling (RCS).<br />
<br />
At the time, the level of evidence for the hardness of this scheme was not yet the same as the linear optical scheme. However, given the theoretical and experimental interest in the idea of demonstrating a quantum speedup over classical computers, subsequent works by<a href="https://arxiv.org/abs/1803.04402"> Bouland, Fefferman, Nirkhe and Vazirani</a>, and <a href="https://arxiv.org/abs/1809.06957">Harrow and Mehraban</a> bridged this gap (the relevant work by <a href="https://arxiv.org/abs/1612.05903">Aaronson and Chen</a> will be discussed in the following section). Harrow and Mehraban proved anticoncentration for random circuits. In particular, they showed that a 2-dimensional grid of n qubits achieve anticoncentration in depth O(\sqrt{n}), improving upon earlier results with higher depth due to <a href="https://arxiv.org/abs/1208.0692">Brandao, Harrow and Horodeck</a>i. Bouland et al. proved the same supporting evidence for RCS as that for boson sampling, namely a worst-to-average-case reduction for exactly computing most output probabilities, even without the permanent structure possessed by linear optical quantum circuits.<br />
<br />
<b>Verification</b><br />
<br />
So far, we have not discussed the elephant in the room: of verifying that the output distribution supported on 2^n outcomes. It turns out that there are concrete lower bounds such as those due to Valiant and Valiant, showing that verifying whether an empirical distribution is close to a target distribution is impossible if one has few samples.<br />
<br />
Boixo et al. proposed a way of certifying the fidelity of the purported simulation. Their key observation was to note that if their experimental system is well modelled by a noise model called global depolarising noise, estimating the output fidelity is possible with relatively few outcomes. Under global depolarising noise with fidelity f, the noisy distribution takes the form D_N = f D_U + (1-f) I, where I is the uniform distribution over the 2^n outcomes. Together with another empirical observation about the statistics of output probabilities of the ideal distribution D_U, they argued that computing the following cross-entropy score would serve as a good estimator of the fidelity:<br />
<br />
f ~ H(I, D_U) - H(D_exp, D_U), where H(D_A,D_B) is the cross-entropy between the two distributions: H(D_A, D_B) = -\sum_i p_A log (p_B).<br />
<br />
The proposal here was to experimentally collect several samples from D_exp, classically compute using brute-force the probabilities of these outcomes in the distribution D_U, and estimate the cross-entropy using this information. If the test outputs a high score for a computation on sufficiently many qubits and depth, the claim is that quantum supremacy has been achieved.<br />
<br />
Aaronson and Chen gave alternative form of evidence for the hardness of scoring well on a test that aims to certify quantum supremacy similar to the manner above. This sidesteps the issue of whether a test similar to the one above does indeed certify the fidelity. The specific problem considered was "Heavy Output Generation" (HOG), the problem of outputting strings that have higher than median probability in the output distribution. Aaronson and Chen linked the hardness of HOG to a closely related problem called "QUATH", and conjectured that QUATH is hard for classical computers.<br />
<br />
<b>Open questions</b><br />
<br />
Assuming the Google team has performed the impressive feat of both running the experiment outlined before and classically computing the probabilities of the relevant outcomes to see a high score on their cross-entropy test, I discuss the remaining positions a skeptic might take regarding the claim about quantum supremacy.<br />
<br />
"The current evidence of classical hardness of random circuit sampling is not sufficient to conclude that the task is hard". Assuming that the skeptic believes that the polynomial hierarchy does not collapse, a remaining possibility is that there is no worst-to-average-case reduction for the problem of *approximating* most output probabilities, which kills the proof technique of Aaronson and Arkhipov to show hardness of approximate sampling.<br />
<br />
"The cross-entropy proposal does not certify the fidelity." Boixo et al. gave numerical evidence and other arguments for this statement, based on the observation that the noise is of the global depolarising form. A skeptic may argue that the assumption of global depolarising noise is a strong one.<br />
<br />
"The QUATH problem is not classically hard." In order to give evidence for the hardness of QUATH, Aaronson and Chen examined the best existing algorithms for this problem and also gave a new algorithm that nevertheless do not solve QUATH with the required parameters.<br />
<br />
It would be great if the community could work towards strengthening the evidence we already have for this task to be hard, either phrased as a sampling experiment or together with the verification test.<br />
<br />
Finally, I think this is an exciting time for quantum computing and to witness this landmark event. It may not be the first probe of an experiment that is "hard" to classically simulate, since there are many quantum experiments that are beyond the reach of current classical simulations, but the inherent programmability and control present in the experimental system is what enables the tools of complexity theory to be applied to the problem. A thought that fascinates me is the idea that we may be exploring quantum mechanics in a regime never probed this carefully before, the "high complexity regime" of quantum mechanics. One imagines there are important lessons in physics here.<br />
<br />https://blog.computationalcomplexity.org/2019/10/quantum-supremacy-guest-post-by-abhinav.htmlnoreply@blogger.com (GASARCH)0tag:blogger.com,1999:blog-3722233.post-2892542038915710982Tue, 01 Oct 2019 00:03:00 +00002019-10-09T12:57:05.731-04:00Richard Guy is 103 years old todayRichard Guy is a mathematician. He co-authored the classic book <i>Winning Ways for your Mathematical Plays </i> with Elywn Berlekamp and John Conway.<br />
<br />
On Sept 30 (today) he turned 102. According to <a href="https://en.wikipedia.org/wiki/List_of_centenarians_(scientists_and_mathematicians)">this list </a> he is the oldest living mathematician, and he would need to live to 110 to be the oldest mathematician ever. <br />
<br />
I have met him twice. He was at the Gathering for Gardner Conference as a young 98-year old. I told him that his book Winning Ways had a great influence on me. He asked it if was positive or negative. I later saw him at a Math conference where he went to my talk on The Muffin Problem. So he is still active.<br />
<br />
His Wikipedia site says that he says he regards himself as an Amateur Mathematician. While it is awkward to disagree with how someone sees himself, I'll point out that he is an author or co-author of 11 books, has many papers, and has solved Erdos Problems. He has taught some but I couldn't really find out what his source of income is or was. This takes us back to the word `amateur' which has several meanings:<br />
<br />
Amateur: Someone who does X for the love of X (Amor is Love in Spanish), and not for money. This could be true of Richard Guy. This notion of amateur may be lost on my younger readers since this it used to be a thing to NOT take money since it somehow soils what you do. In those days Olympic athletes could not have played professionally beforehand. We can't imagine that now.<br />
<br />
Amateur: Someone who dabbles in something but is not really that good. This could NOT be true of Richard Guy.<br />
<br />
<br />
<br />
<br />
Aside from games he has also worked in Number Theory. His book <i>Unsolved Problems in Number Theory </i> has inspired many (including me). <br />
<br />
So happy birthday Richard Guy!<br />
<br />
He is the also the oldest living person we have honored on this blog. Second oldest was Katherine Johnson, see <a href="https://blog.computationalcomplexity.org/2018/08/katherine-johnson-1918.html"></a> who is still alive.<br />
<br />
ADDED LATER- some people emailed me if Richard Guy was still actively doing mathematics. Here is a recent paper of his: <a href="https://arxiv.org/abs/1910.03379">here</a>https://blog.computationalcomplexity.org/2019/09/richard-guy-is-102-years-old-today.htmlnoreply@blogger.com (GASARCH)2tag:blogger.com,1999:blog-3722233.post-5706639639416187826Thu, 26 Sep 2019 17:09:00 +00002019-09-26T13:09:18.530-04:00Quantum SupremacyBy now you've probably heard the rumors of Google achieving quantum supremacy. I don't have inside information outside of <a href="https://www.scottaaronson.com/blog/?p=4317">Scott's blog post</a> but it looks like the news should be <a href="https://blog.computationalcomplexity.org/2006/10/embargoed-science.html">embargoed</a> until the release of a Science or Nature paper. These things usually happen on a Tuesday and you'd think they would avoid the news of the Nobel Prize announcements October 7-14.<br />
<br />
Since for now the Google paper doesn't officially exist, we live in an era of Classical Dominance. Any problem that can be solved on a quantum computer today, can be solved just as fast or faster on a traditional computer. Quantum Supremacy, despite its lofty name, is just the negation of Classical Dominance, that there is some problem that a current quantum machine can solve that all our regular machines would require a considerably longer time to solve. This isn't a formal mathematical or scientific definition, so one can debate when or if we cross this threshold and I'm sure <a href="https://gilkalai.wordpress.com/2019/09/23/quantum-computers-amazing-progress-google-ibm-and-extraordinary-but-probably-false-supremacy-claims-google/">people will</a>.<br />
<br />
Quantum Supremacy might not even be a monotone concept. Future classical algorithms might solve the problem quickly, leading us back to Classical Dominance but leaving open the possibility of returning to Quantum Supremacy with another problem.<br />
<br />
Quantum Supremacy is a long way from Quantum Usefulness, where quantum machines can solve problems we care about faster that traditional machines. Quantum computing will truly reach its potential when we can run general quantum algorithms like Shor's algorithm to factor products of large primes. We'll probably never see Quantum Dominance where classical transistors go the way of vacuum tubes.<br />
<br />
Nevertheless, quantum supremacy is an important step and whether or not you think Google has gotten there, I'm sure it's an incredible achievement of science and engineering.https://blog.computationalcomplexity.org/2019/09/quantum-supremacy.htmlnoreply@blogger.com (Lance Fortnow)1tag:blogger.com,1999:blog-3722233.post-6018241016493737863Mon, 23 Sep 2019 13:20:00 +00002019-09-23T09:20:22.649-04:00Applicants to Grad School are too good. Here is why this might be a problem.Sitting around with three faculty we had the following conversation<br />
<br />
ALICE: When I applied to grad school in 1980 they saw a strong math major (that is, I had good grades in hard math courses) but very little programming or any sort of computer science. That kind of person would NOT be admitted today since there are plenty of strong math majors who ALSO have the Comp Sci chops.<br />
<br />
BOB: When I applied to grad school I was a comp sci major but my grades were not that good- A's in system courses, B's and even some C's in math. But I did a Security project that lead to a paper that got into a (minor) systems workshop. Two of my letters bragged a lot about that. (How do I know that? Don't ask.) So I got into grad school in 1989. That kind of person would NOT be admitted today since there are plenty of people who have papers in minor conferences whose grades ARE good in stuff other than their area.<br />
<br />
CAROL: In 1975 I was an English major at Harvard. The summer between my junior and senior year I took a programming course over the summer and did very well and liked it. I then took some math. Then I worked in industry at a computer scientist for 5 years. Then I applied to grad school and they liked my unusual background. Plus I did well on the GRE's. Letters from my boss at work helped me, I don't think they would count letters from industry now. They took a chance on me, and it paid off (I got a PhD) but I don't think they would let someone like me in now since they don't have to take a chance. They can admit people who have done research, have solid backgrounds, and hence are not taking a chance. The irony is that some of those don't finish anyway.<br />
<br />
<br />
1) Are Alice, Bob, and Carol right that they wouldn't be admitted to grad school now? I think they are with a caveat- they might end up in a lower tier grad school then they did end up in. Also, Alice and Bob I am more certain would not end up in the top tier grad schools they did since they can be compared DIRECTLY to other applicants,<br />
where as Carol might be more orthogonal.<br />
<br />
2) I have a sense (backed up my no data) that we are accepting fewer unusual cases than we used to (not just UMCP but across the country) because too many of the applicants are the standard very-good-on-paper applicants. Even the on-paper is not quite fair- they ARE very good for real.<br />
<br />
3) Assume we are taking less unusual cases. Is that bad? I think so as people with different backgrounds (Carol especially) add to the diversity of trains of thought in a program, and that is surely a good thing. If EVERY students is a strong comp sci major who has done some research, there is a blandness to that.<br />
<br />
4) What to do about this? First off, determine if this is really a problem. If it is then perhaps when looking at grad school applicants have some sensitivity to this issue.<br />
<br />
5) For grad school admissions I am speculating. For REU admissions (I have run an REU program for the last 7 years and do all of the admissions myself) I can speak with more experience. The students who apply have gotten better over time and this IS cause for celebration; however, it has made taking unusual cases harder. <br />
<br />
https://blog.computationalcomplexity.org/2019/09/applicants-to-grad-school-are-too-good.htmlnoreply@blogger.com (GASARCH)7tag:blogger.com,1999:blog-3722233.post-6037506695705789893Mon, 16 Sep 2019 13:10:00 +00002019-09-16T09:10:52.374-04:00this paper from 2015 cracks Diffie-Hellman. What to tell the students?I am teaching cryptography this semester for the second time (I taught it in Fall 2019) and will soon tell the students about the paper from 2015:<br />
<a href="https://weakdh.org/imperfect-forward-secrecy.pdf">Imperfect Forward Secrecy: How Diffie-Hellman Fails in Practice</a>. There are 14 authors.<br />
<br />
The upshot is that as Diffie-Hellman was implemented in 2015, many cases were crackable. In summary (and probably too simple):<br />
<br />
DH in a 512-bit group can be cracked by the authors<br />
<br />
DH in a 1024-bit group they speculate can be cracked with nation-state resources. <br />
<br />
<br />
<br />
Is this a big deal? If YES then what is being done, and if NOT then why not?<br />
<br />
I have come up with some statements that I DO NOT KNOW if they are true, but I am ASKING you, to shed some light on the BIG DEAL or NO BIG DEAL question. (Note- Idea for a game show: BIG DEAL or NO BIG DEAL where contestants are asked if a news story is a BIG DEAL or not.)<br />
<br />
So, please comment on the following question:<br />
<br />
1) Since 2015 the people who use DH have upped their game and are now using bigger parameters. (I doubt this is true)<br />
<br />
2) DH is mostly not used on things that hackers are not interested in, so this is not a big deal.<br />
<br />
3) The expertise required to crack DH via this paper is rather difficult, so hackers don't have the skills.<br />
<br />
4) This paper is not a problem for a bad reason: Hackers don't need to use the number field sieve DL algorithm when all they need to do is (1) guess that the pin numer is 1234 or the year the user was born (or close to it), (2) put on a uniform from Geek-Squad or some such organization and claim they are here to help, (3) exploit a known security flaw that the company has not bothered fixing. <br />
<br />
5) The 14 authors have mysteriously disappeared. (I doubt this is true.)<br />
<br />
<br />
(Misc: My spell checker thinks that Diffie and crackable are not words, but Hellman is.)https://blog.computationalcomplexity.org/2019/09/this-paper-from-2015-cracks-diffie.htmlnoreply@blogger.com (GASARCH)7tag:blogger.com,1999:blog-3722233.post-5655789602676044507Mon, 09 Sep 2019 14:55:00 +00002019-09-09T11:03:03.353-04:00Are there any natural problems complete for NP INTER TALLY? NP INTER SPARSE?<br />
Recall:<br />
<br />
A is a <i>tally set</i> if A ⊆ 1<sup>*</sup>. <br />
<br />
<br />
A is a <i>sparse set</i> if there is a polynomial p such that the number of strings of length n is ≤ p(n). <br />
<br />
<br />
If there exists a sparse set A that is NP-hard under m-reductions (even btt-reductions) then P=NP. (See <a href="https://blog.computationalcomplexity.org/2006/04/favorite-theorems-small-sets.html">this post</a>.)<br />
<br />
If there exists a sparse set A that is NP-hard under T-reductions then PH collapses. (See <a href="https://blog.computationalcomplexity.org/2006/11/favorite-theorems-nonuniform.html">this post</a>.)<br />
<br />
Okay then!<br />
<br />
I have sometimes had a tally set or a sparse set that is in NP and I think that its not in P. I would like to prove, or at least conjecture, that it's NP-complete. But alas, I cannot since then P=NP. (Clarification: If my set is NP-complete then P=NP. I do not mean that the very act of conjecturing it would make P=NP. That would be an awesome superpower.)<br />
<br />
So what to do? <br />
<br />
A is <i>NPSPARSE-complete </i> if A is in NP, A is sparse, and for all B that are in NP and sparse, B ≤<sub>m</sub> A.<br />
<br />
Similar for NPTALLY and one can also look at other types of reductions.<br />
<br />
So, can I show that my set is NPSPARSE-complete? Are there any NPSPARSE-complete sets? Are there NATURAL ones? (Natural is a slippery notion- see this <a href="https://blog.computationalcomplexity.org/2004/03/unnatural-post.html">post by Lance</a>.)<br />
<br />
Here is what I was able to find out (if more is known then please leave comments with pointers.)<br />
<br />
1) It was observed by <a href="https://lance.fortnow.com/papers/files/npsparse.pdf">Bhurman, Fenner, Fortnow, van Velkebeek</a> that the following set is NPTALLY-complete:<br />
<br />
Let M<sub>1</sub>, M<sub>2</sub>, ... be a standard list of NP-machines. Let<br />
<br />
A = { 1<sup>(i,n,t)</sup> : M<sub>i</sub>(1<sup>n</sup>) accepts on some path within t steps }'<br />
<br />
The set involves Turing Machines so its not quite what I want.<br />
<br />
<br />
2) <a href="https://www.cs.umd.edu/users/gasarch/BLOGPAPERS/messnertoran.pdf">Messner and Toran</a> show that, under an unlikely assumption about proof systems there exists an NPSPARSE-complete set. The set involves Turing Machines. Plus it uses an unlikely assumption. Interesting, but not quite what I want.<br />
<br />
<br />
3) Buhrman, Fenner, Fortnow, van Melkebeek also showed that there are relativized worlds where there are no NPSPARSE sets (this was their main result). Interesting but not quite what I want. <br />
<br />
4) If A is NE-complete then the tally version: { 1<sup>x</sup> : x is in A } is likely NPTALLY-complete. This may help me get what I want.<br />
<br />
Okay then!<br />
<br />
Are there any other sets that are NPTALLY-complete. NPSPARSE-complete? The obnoxious answer is to take finite variants of A. What I really want a set of such problems so that we can proof other problems NPTALLY-complete or NPSPARSE-complete with the ease we now prove problems NP-complete.<br />
<br />
<br />
<br />
https://blog.computationalcomplexity.org/2019/09/are-there-any-natural-problems-complete.htmlnoreply@blogger.com (GASARCH)1tag:blogger.com,1999:blog-3722233.post-1092995341963635215Thu, 05 Sep 2019 16:03:00 +00002019-09-05T12:04:44.526-04:00TransitioningYou may have noticed, or not, that I haven't posted or tweeted much in the last month. I've had a busy time moving back to Chicago and starting my new position as Dean of the College of Science at Illinois Tech.<br />
<div>
<br /></div>
<div>
Part of that trip involved driving my electric Chevy Bolt from Atlanta to Chicago. You can do it, but it got a bit nerve wracking. There is only one high-speed charging station between Indianapolis and Chicago and you pray the charger outside the Lafayette Walmart actually works (it did). We passed many Tesla charging superstations, I will have to admit they have the better network. </div>
<div>
<br /></div>
<div>
Theoremwise, Ryan Alweiss, Shachar Lovett, Kewen Wu and Jiapeng Zhang had <a href="https://gilkalai.wordpress.com/2019/08/23/amazing-ryan-alweiss-shachar-lovett-kewen-wu-jiapeng-zhang-made-dramatic-progress-on-the-sunflower-conjecture/">significant improvements on the sunflower conjecture</a>. I posted on the sunflower theorem for Richard Rado's <a href="https://blog.computationalcomplexity.org/2006/04/richard-rado-1906-1989.html">centenary</a>. Nice to see there is still some give in it.</div>
<div>
<br /></div>
<div>
I probably will post less often in this new position. Bill asked me "Why is being a dean (or maybe its just the move) more time then being a chair? Were you this busy when you moved and first became chair?"<br />
<br />
When I moved to Atlanta, I moved a year ahead of the rest of the family and rented a condo. We had plenty of time to search for a house in Atlanta and plan the move. Here it all happened in a much more compressed time schedule and, since we've bought a condo, into a much more compressed space.</div>
<div>
<br /></div>
<div>
Being a chair certainly ate up plenty of time but it feels different as dean with a more external focus. I won't give up the blog but you'll probably hear a lot more from Bill than from me at least in the near future.</div>
https://blog.computationalcomplexity.org/2019/09/transitioning.htmlnoreply@blogger.com (Lance Fortnow)1tag:blogger.com,1999:blog-3722233.post-1820902627345115895Tue, 03 Sep 2019 14:56:00 +00002019-09-03T10:56:38.565-04:00Can Mathematicians Fix Iphones? Can anyone?<br />
In my last post I noted that if I am asked (since I am a CS prof)<br />
<br />
<i>Can you fix my iphone</i><br />
<br />
is<br />
<br />
<i>No, I work on the math side of CS</i><br />
<br />
Some readers emailed me (I told them to comment instead but they were worried that other readers would argue with them) that NO, this is a tired and incorrect stereotype. Here are some samples:<br />
<br />
1) People in Mathematics are no better or worse at fixing iphones, fixing cars, programming their VCR's, etc than the public.<br />
<br />
2) For that matter, people in academica, even in practical sounding fields like Systems, are no better.<br />
<br />
3) Is your nephew Jason who used to fix forklifts for a living better at these things then the general public? I asked him. Answer: No, though he is better at fixing forklifts.<br />
<br />
I think something else is going on here. Lets look at fixing your own car. I think this is the sort of thing that some people used to be able to do but now very few can do it. Cars have gotten more complicated. <br />
<br />
Iphones are not quite there yet but its getting that way. <br />
<br />
Of course somethings have gotten easier--- programming a DVR is much easier than programming a VCR. And people can easily use WORD or write programs without having to know any hardware.<br />
<br />
OKAY, after all these random thoughts, here is the question: What do you think? <br />
<br />
Are people in CS or Math or CS theory better at X than the general public where X is NOT CS, Math or CS theory, but something like fixing their cars?<br />
<br />
And<br />
<br />
What has gotten harder? What has gotten easier?<br />
<br />
<br />
<br />
https://blog.computationalcomplexity.org/2019/09/can-mathematicians-fix-iphones-can.htmlnoreply@blogger.com (GASARCH)3tag:blogger.com,1999:blog-3722233.post-8615276220589503260Sun, 25 Aug 2019 17:39:00 +00002019-08-25T14:58:55.179-04:00`Are you a math genius?' `Can you fix my Iphone?' `What do you think about Facebook and Privacy?'<br />
When I meet non-math people and tell them I am a computer science professor I get a range of responses. Here are some and my responses.<br />
<br />
<br />
1) <i>Are you a math genius?</i><br />
<br />
Here is the answer I give:<br />
<br />
<i>I know some things in math, frankly obscure things, that most people in math don't know. On the other hand, I probably can't help your teenage daughter with her trigonometry homework. Academics, like most people, forget what they don't use, and there are some things in math I rarely use, so I've forgotten them.</i><br />
<br />
I wonder how a Fields' Medal winner would answer the question.<br />
<br />
Although the above is the answer I give I really think its an ill defined and pointless question. Its very hard to measure genius or even define what it means (there are exceptions). After a certain age, what you've done is more important than how smart you allegedly are. <br />
<br />
2)<i> Can you fix my iPhone?</i><br />
<br />
That's an easy one: <i>No. I work on the math end of computer science.</i> I don't elaborate.<br />
<br />
3) <i>What do you think of Facebook and privacy?</i><br />
<br />
This is an odd one. I DO have opinions on this but they are NOT better informed just because I'm a comp sci professor. Since I don't have a Facebook account my opinions might be worse informed. So how do I respond? I show them<br />
<br />
<a href="https://www.youtube.com/watch?v=cqggW08BWO0">this Onion News Network Video about how the CIA created Facebook </a><br />
<br />
Some think it's real. They may be right.<br />
<br />
https://blog.computationalcomplexity.org/2019/08/are-you-math-genius-can-you-fix-my.htmlnoreply@blogger.com (GASARCH)9tag:blogger.com,1999:blog-3722233.post-337501791513204418Wed, 07 Aug 2019 19:27:00 +00002019-08-07T15:27:14.876-04:00Obstacles to improving Classical Factoring AlgorithmsIn Samuel Wagstaff's excellent book The Joy of Factoring (see <a href="https://mathcs.clarku.edu/~fgreen/SIGACTReviews/bookrev/47-2.pdf">here</a> for a review) there is a discussion towards the end about why factoring algorithms have not made much progress recently. I<br />
paraphrase it:<br />
<br />
<br />
--------------------------------------------------------<br />
<br />
The time complexities of the fastest known algorithms can be expressed as a formula of the following form (where N is the number to be factored):<br />
<br />
(*) exp(c(ln N)^t (ln(ln N))^{1-t})<br />
<br />
for some constants c and for 0 < t < 1. For the Quadratic Sieve (QS) and Elliptic Curve Method (ECM) t=1/2. For the Number Field Sieve (NFS) t=1/3. The reason for this shape for the time complexity is the requirement of finding one or more smooth numbers (numbers that have only small primes as factors).<br />
<br />
----------------------------------------------------------<br />
<br />
This got me thinking: Okay, there may not be a drastic improvement anytime soon but what about just improving t? Is there a mathematical reason<br />
why an algorithm with (say) t=1/4 has not been discovered? In an earlier era I would have had to write a letter to Dr. Wagstaff to ask him. Buy an envelope, buy a stamp, find his address, the whole nine yards (my younger readers should ask their grandparents what envelopes and stamps were). In the current era I emailed him. And got a response.<br />
<br />
<br />
Samuel Wagstaff:<br />
<br />
The fastest known factoring algorithms find smooth numbers subject to parameter choice(s). In all these algorithms, one parameter choice is the smoothness bound B: a number is smooth if all its prime factors are < B. The NFS has the degree of a polynomial as an additional parameter.<br />
<br />
One analyzes the complexity of these algorithms by estimating the total work required (to find enough smooth numbers) for an arbitrary parameter choice using Dickman's function to predict the density of smooth numbers. Then one uses calculus to find the parameter choice(s) that minimize the total work function. Calculus also yields the optimal values for the parameter(s).<br />
<br />
If you have k parameters to choose, you will get the time complexity (*) with t = 1/(1+k). If you have no parameters (k = 0),you get (*) with t = 1, basically exponential time N^c. With one parameter to optimize, as in CFRAC (continued fractions algorithm) and QS, you get t = 1/2. NFS has two parameters, so t = 1/3. ECM also has t = 1/2 because it uses only one parameter, the smoothness bound B. If you want to get t = 1/4, you have to find a third parameter to optimize. No one has found one yet. That is the answer to your question.<br />
<br />
Note that some choices made in some factoring algorithms don't count as parameters. For example, the number of polynomials used in the multiple-polynomial quadratic sieve, and the upper bound on large primes kept, don't affect t. They affect the running time only in making c smaller. So you have to find a third parameter that matters in order to get (*) with t = 1/4. Or find three completely different new parameters.<br />
<br />
<br />
https://blog.computationalcomplexity.org/2019/08/obstacles-to-improving-classical.htmlnoreply@blogger.com (GASARCH)2tag:blogger.com,1999:blog-3722233.post-5104220537083628124Mon, 29 Jul 2019 00:46:00 +00002019-07-28T20:46:08.367-04:00Turing to be on the Bank of England 50 pound note, giving me an excuse to talk about TuringBILL: Darling, guess who is soon going to be on the Bank of England 50 pound note?<br />
<br />
DARLING: Alan Turing. <br />
<br />
BILL: How did you deduce that? (She is right, see <a href="https://www.bbc.com/news/business-48962557">here</a>.)<br />
<br />
DARLING: Since you asked it, it couldn't be a member of the Royal Family (you don't care about that) or some British Politician (you don't care about that either). It had to be a mathematician or computer scientist.<br />
<br />
BILL: It could have been Hardy. I wonder if Ramanujan could qualify---do they need to be British? At <a href="https://www.bankofengland.co.uk/banknotes/banknote-characters">this website</a> it says<br />
<br />
<br />
<br />
<i>Of course, banknotes need to be universally accepted. We therefore look for UK characters who have made an important contribution to our society and culture through their innovation, leadership or values. We do not include fictional characters, or people who are still living (except the monarch on the front of the note). Finally, we need to have a suitable portrait of the person which will be easy to recognise.</i><br />
<br />
(They spell <i>recognise</i> with an s instead of a z, so spellcheck flagged it, but I won't change it.) <br />
<br />
Note that people on the banknotes have to be <i>UK characters</i>. I honestly don't know if that means they must be citizens.<br />
<br />
OKAY, so here are a few thoughts on Turing.<br />
<br />
1) When I visited Bletchley Park there was a booklet that bragged about the fact that Bletchley Park was much better at cracking codes than Germany because they allowed people to work there based only on ability (unlike Germany) - women worked there, Turing who was Gay worked there. I think this is simplistic. Did any Jews work there (anti-semitism was widespread in England, and the world, at the time)? I doubt any blacks worked there since if they did that would be well known by now (if I am wrong let me know). Women DID work there but was their work respected and used? (I honestly don't know). Did Germany also use women at their codebreaking centers? Was Turing known to be gay (if not then Bletchley gets no points for tolerating him). Was JUST having Turing the reason they could crack codes. Plus I am sure there were other factors aside from merit-only.<br />
<br />
2) Turing was given a Pardon for his ``crimes'' in August 2014. When I see things like this I wonder who was against it and why and if they were an obstacle.<br />
<br />
a) Human Rights Advocate Peter Tatchell noted that its wrong to just single out Turing. Other people prosecuted under that law who did not help beat the German's in WW II should also be pardoned. The government later DID such a pardon in 2017.<br />
<br />
b) Judge Minister Lord McNally objected to the pardon:<br />
<br />
<i>A posthumous pardon was not considered appropriate as Alan Turing was properly convicted of what at the time was a criminal offence. He would have known that his offence was against the law and that he would be prosecuted. It is tragic that Alan Turing was convicted of an offence that now seems both cruel and absurd—particularly poignant given his outstanding contribution to the war effort. However, the law at the time required a prosecution and, as such, long-standing policy has been to accept that such convictions took place and, rather than trying to alter the historical context and to put right what cannot be put right, ensure instead that we never again return to those times.<br />
</i><br />
<br />
While I disagree with him, I do note that, based on what he wrote and his general record, I think he is not saying this from being anti-gay. There is a hard general question here: how does a society right past wrongs? I think pardoning and apologizing is certainly fine, but frankly it seems to weak. What else could a society due? Financial renumeration to living relatives? I don't think giving Inagh Payne (Turing's niece, who I think is still alive) would really help here.<br />
<br />
c) <i>At the bill's second reading in the House of Commons on 29 November 2013, Conservative MP Christopher Chope objected to the bill, delaying its passage<br />
</i><br />
<br />
I couldn't find Chope's reasons. On the one hand, they may be similar to McNally's. On the other hand he is against same sex marriage so its possible (though I do not know this) that he anti-gay and that is why he is against the pardon. If someone can find what his explanation for blocking the Turing bill is, or other evidence that he is anti-gay, please leave it in the comments.<br />
<br />
3) Did the delay matter? I was surprised to find out---Yes. Here is the full passage from Wikipedia:<br />
<br />
<br />
<i>At the bill's second reading in the House of Commons on 29 November 2013, Conservative MP Christopher Chope objected to the bill, delaying its passage. The bill was due to return to the House of Commons on 28 February 2014,[175] but before the bill could be debated in the House of Commons,[176] the government elected to proceed under the royal prerogative of mercy. On 24 December 2013, Queen Elizabeth II signed a pardon for Turing's conviction for "gross indecency", with immediate effect.[17] Announcing the pardon, Lord Chancellor Chris Grayling said Turing deserved to be "remembered and recognised for his fantastic contribution to the war effort" and not for his later criminal conviction.[16][18] The Queen officially pronounced Turing pardoned in August 2014.[177] The Queen's action is only the fourth royal pardon granted since the conclusion of the Second World War.[178] Pardons are normally granted only when the person is technically innocent, and a request has been made by the family or other interested party; neither condition was met in regard to Turing's conviction.[179]</i><br />
<br />
This amazed me! I thought the Queen had NO power (too bad--- I wish she could just say NO BREXIT). Or that she formally has power but if she ever used it, it might be blocked somehow and taken away. So I am surprised she has a power she can use at all.<br />
<br />
4) I wonder if the Pardon had to happen before they put him on the Banknote. I have been told that this is a very American Question--- England has no Constitution and operates more on Custom and Tradition than on written rules. <br />
<br />
5) I had always assumed that Turing committed suicide. Without going into detail, the Wikipedia site on Turing does give intelligent counterarguments to this. See <a href="https://en.wikipedia.org/wiki/Alan_Turing#Death">here</a><br />
https://blog.computationalcomplexity.org/2019/07/turing-to-be-on-bank-of-england-50.htmlnoreply@blogger.com (GASARCH)10tag:blogger.com,1999:blog-3722233.post-7683541918979097623Thu, 25 Jul 2019 20:39:00 +00002019-07-25T16:39:24.106-04:00The Advisor/Advisee RelationshipI've always felt a strong advisor/advisee relationship is the single most important factor in a successful PhD career. At its best, the advisor works closely with the student to successful research agenda and help mentor them through their graduate career and beyond. The advisor/advisee relationship can feel like a parent/child relationship that lasts an entire career. Nothing gives me more pleasure as an academic than to see the success of my current and former students.<br />
<br />
Take your time when picking an advisor. Don't choose an advisor based solely on research area or because they are "famous". Pick the advisor that will best guide you to a successful academic career.<br />
<br />
At its worst, a bad advisor/advisee relationship will destroy your graduate career, making you feel miserable, perhaps dropping out of graduate school or worse, particularly if a student doesn't feel like they are being treated fairly.<br />
<br />
Two incidents prompted this post. On TCS-Stack Exchange, a student has <a href="https://cstheory.stackexchange.com/questions/42704/single-author-papers-against-my-advisors-will/42711">authorship issues</a> with their advisor. Unfortunately these kinds of incidents happen more often than one suspects. If you can't work it out with the advisor, go talk to someone about it, another faculty, the graduate or department chair, a grad student ombudsperson if your institution has one. We care about our students, and will work hard to resolve problems.<br />
<br />
In a much more <a href="https://medium.com/@huixiangvoice/the-hidden-story-behind-the-suicide-phd-candidate-huixiang-chen-236cd39f79d3">tragic event</a>, a student felt it easier to take his own life than feeling that he had to cover up potential academic misconduct. Again, if you ever find yourself in such a situation please reach out. Giving up is never the answer.https://blog.computationalcomplexity.org/2019/07/the-advisoradvisee-relationship.htmlnoreply@blogger.com (Lance Fortnow)10tag:blogger.com,1999:blog-3722233.post-7828284719883166611Mon, 22 Jul 2019 03:00:00 +00002019-07-21T23:00:05.358-04:00Answer to both Infinite Hats Problems from the last post<br />
(This is a joint post with David Marcus. You'll see why later.)<br />
<br />
In a prior I posed two infinite hat problems. Today I post the solutions. Actually this is a copy of my last post with the solutions added, so it is self contained.<br />
<br />
A Hat Problem that you have probably seen:<br />
<br />
1) There are an infinite number of people, numbered 1,2,3,... There are 2 colors of hats. They can all see everyone's hat but their own. <br />
<br />
2) The adversary is going to put hats on all the people. They will guess their own hat color<i> at the same time</i>. <br />
<br />
3) The people can discuss strategy ahead of time, but must use a deterministic strategy and the adversary knows the strategy.<br />
<br />
4) The people want to minimize how many they get wrong. <br />
<br />
5) The adversary puts on hats to maximize how many they get wrong.<br />
<br />
I ask two questions (the answers are in a document I point to) and one meta-question:<br />
<br />
Q1: Is there a solution where they get all but a finite number of the guesses right? (If you have read my prior post on hat puzzles, <a href="https://blog.computationalcomplexity.org/2017/07/two-hat-problems-you-may-or-may-not.html">here</a> then you can do this one.) <br />
<br />
Q2: Is there a solution where they get all but at most (say) 18 wrong.<br />
<br />
<br />
Answers to Q1 and Q2 are <a href="https://www.cs.umd.edu/users/gasarch/BLOGPAPERS/infinitehats.pdf">here</a>.<br />
<br />
How did I get into this problem? I was looking at hat problems a while back. Then I began discussing Q1 and Q2 by email (Does the term <i>discussing</i> have as a default that it is by email?) with David Marcus who had just read the chapter of <a href="https://www.amazon.com/Problems-Point-Exploring-Computer-Science/dp/9813279974">Problems with a Point</a> on hat puzzles. After a few emails back and fourth, he began looking on the web for answers. He found one. There is a website of hat puzzles! It was MY website papers on Hat Puzzles! It is <a href="https://www.cs.umd.edu/users/gasarch/TOPICS/hats/hats.html">here</a>. And on it was a relevant paper <a href="https://www.cs.umd.edu/users/gasarch/TOPICS/hats/infinite-hats-and-ac.pdf">here</a>. We did not find any other source of the problem or its solution. <br />
<br />
Q3: How well known is problem Q2 and the solution? I've seen Q1 around but the only source on Q2 that I know of is that paper, and now this blog post. So, please leave a comment telling me if you have seen Q2 and/or the solution someplace else, and if so where.<br />
<br />
The responses to my last post indicated that YES the problem was out there, but the proof that you could not get all-but-18 was not well known. <br />
<br />
I THINK that all of the proofs that you can't do all-but-18 in the comment of the last post were essentially the same as the solution I pointed to in this blog. I would be interested if there is an alternative proof. <br />
https://blog.computationalcomplexity.org/2019/07/answer-to-both-infinite-hats-problems.htmlnoreply@blogger.com (GASARCH)0tag:blogger.com,1999:blog-3722233.post-6069637759837834972Tue, 16 Jul 2019 23:38:00 +00002019-07-16T19:38:00.557-04:00Guest post by Samir Khuller on attending The TCS Women 2019 meeting<br />
(I will post the solution to the problem in the last blog later in the week---probably Thursday. Meanwhile, enjoy these thoughts from Samir Khuller on the TCS Women 2019 meeting.)<br />
<br />
Guest Post by Samir Khuller:<br />
<br />
Am I even allowed here?” was the first thought that crossed my mind when I entered the room. It was packed with women (over 95%), however a few minutes later, several men had trickled in. I was at the TCS Women spotlight workshop on the day before STOC. Kudos to Barna Saha, Sofya Raskhodnikova, and Virginia Vassilevska Williams for putting this grand (and long needed) event together, which serves as a role model and showcases some of the recent work by rising stars. In addition to the Sun afternoon workshop, the event was followed by both an all women panel and a poster session (which I sadly did not attend).<br />
<br />
<br />
The rising stars talks were given by Naama Ben-David (CMU), Andrea Lincoln (MIT), Debarati Das (Charles University) and Oxana Poburinnaya (Boston U). After a short break the inspirational talk was by Ronitt Rubinfeld from MIT. Ronitt’s talk was on the topic of Program Checking, but she made it inspirational by putting us in her shoes as a young graduate student, three decades back, trying to make a dent in research by working on something that her advisor Manuel Blum, and his senior graduate student Sampath Kannan had been working on, and I must say she made a pretty big dent in the process! She also related those ideas to other pieces of work done since in a really elegant manner and how these pieces of work lead to work on property testing.<br />
<br />
<br />
I am delighted to say that NSF supported the workshop along with companies such as Amazon, Akamai, Google and Microsoft. SIGACT plans to be a major sponsor next year.<br />
<br />
<br />
The Full program for the workshop is at the following URL<a href="https://sigact.org/tcswomen/tcs-women-2019/">here.</a><br />
<br />
https://blog.computationalcomplexity.org/2019/07/guest-post-by-samir-khuller-on.htmlnoreply@blogger.com (GASARCH)12tag:blogger.com,1999:blog-3722233.post-4254868758435665114Mon, 15 Jul 2019 03:12:00 +00002019-07-14T23:12:25.307-04:00Two infinite hat problem and a question about what is ``well known''<br />
This is a joint post with David Marcus. You will see how he is involved in my next post.<br />
<br />
Two infinite hat problems based on one scenario. I am also curious if they are well known.<br />
<br />
1) There are an infinite number of people, numbered 1,2,3,... There are 2 colors of hats. They can all see everyone's hat but their own. <br />
<br />
2) The adversary is going to put hats on all the people. They will guess their own hat color<i> at the same time</i>. <br />
<br />
3) The people can discuss strategy ahead of time, but must use a deterministic strategy and the adversary knows the strategy.<br />
<br />
4) The people want to minimize how many they get wrong. <br />
<br />
5) The adversary puts on hats to maximize how many they get wrong.<br />
<br />
I ask two questions and one meta-question:<br />
<br />
Q1: Is there a solution where they get all but a finite number of the guesses right? (I have blogged about a variant of this one a while back.)<br />
<br />
Q2: Is there a solution where they get all but at most (say) 18 wrong. (My students would say <i>the answer has to be YES or he</i> <i>wouldn't ask it</i>. They don't realize that I work on upper AND lower bounds!)<br />
<br />
Q3: How well known is problem Q1 and the solution? Q2 and the solution? I've seen Q1 and its solution around (not sure where), but the only source on Q2 that I know of is CAN'T TELL YOU IN THIS POST, WILL IN THE NEXT POST. So, please leave a comment telling me if you have seen Q1 or Q2 and solutions. And if so then where.<br />
<br />
Feel free to leave any comments you want; however, I warn readers who want to solve it themselves to not look at the comments, or at my next post.<br />
https://blog.computationalcomplexity.org/2019/07/two-infinite-hat-problem-and-question.htmlnoreply@blogger.com (GASARCH)10tag:blogger.com,1999:blog-3722233.post-1705625191398821823Thu, 11 Jul 2019 17:54:00 +00002019-07-11T15:37:18.780-04:00Degree and SensitivityHao Huang's <a href="https://arxiv.org/abs/1907.00847">proof of the sensitivity conjecture</a> that I <a href="https://blog.computationalcomplexity.org/2019/07/local-kid-makes-history.html">posted on last week</a> relied on a 1992 <a href="https://doi.org/10.1016/0097-3165(92)90060-8">result of Gotsman and Linial</a>. Let's talk about that result.<br />
<br />
Consider the set S={-1,1}<sup>n</sup>. The hypercube of dimension n is the graph with vertex set S and an edge between x = (x<sub>1</sub>,…,x<sub>n</sub>) and y = (y<sub>1</sub>,…,y<sub>n</sub>) in S if there is exactly one i such that x<sub>i</sub> ≠ y<sub>i</sub>. Every vertex has degree n.<br />
<br />
We say a vertex x is odd if x has an odd number of -1 coordinates, even otherwise. Every edge joins an odd and even vertex.<br />
<br />
Let f be a function mapping S to {-1,1}. The sensitivity of f on x is the number of i such that f(x<sub>1</sub>,…,x<sub>i</sub>,…,x<sub>n</sub>) ≠ f(x<sub>1</sub>,…,-x<sub>i</sub>,…,x<sub>n</sub>). The sensitivity of f is the maximum over all x in S of the sensitivity of f on x.<br />
<br />
Let g be the same function as f except that we flip the value on all odd vertices. Notice now that the sensitivity of f on x is the number of i such that g(x<sub>1</sub>,…,x<sub>i</sub>,…,x<sub>n</sub>) = g(x<sub>1</sub>,…,-x<sub>i</sub>,…,x<sub>n</sub>).<br />
<br />
Let G be the induced subgraph of vertices of x such that g(x)=-1 and H be induced subgraph on the set of x such that g(x)=1. The sensitivity of f is the maximum number of neighbors of any vertex in G or H.<br />
<br />
Consider f as a multilinear polynomial over the reals. The sensitivity conjecture states there is some α>0 such that if f has degree n then f has sensitivity at least n<sup>α</sup>.<br />
<br />
Note g(x<sub>1</sub>,…,x<sub>n</sub>)=f(x<sub>1</sub>,…,x<sub>n</sub>)x<sub>1</sub>⋯x<sub>n</sub>. If f has a degree n term, the variables in that term cancel out on S (since x<sub>i</sub><sup>2</sup>=1) and the constant of the degree n term of f becomes the constant term of g. The constant term is just the expected value, so f has full degree iff g is unbalanced.<br />
<br />
GL Assumption: Suppose you have a partition of the hypercube into sets A and B with |A| ≠ |B|, and let G and H be the induced subgraphs of A and B. Then there is some constant α>0 such that there is a node of A or B with at least n<sup>α</sup> neighbors.<br />
<br />
The above argument, due to Gotsman and Linial, shows that the GL assumption is equivalent to the sensitivity conjecture.<br />
<br />
Huang proved that given any subset A of the vertices of a hypercube with |A|>2<sup>n</sup>/2 the induced subgraph has a node of degree at least n<sup>1/2</sup>. Since either A or B in the GL assumption has size greater than 2<sup>n</sup>/2, Huang's result gives the sensitivity conjecture. https://blog.computationalcomplexity.org/2019/07/degree-and-sensitivity.htmlnoreply@blogger.com (Lance Fortnow)0