tag:blogger.com,1999:blog-3722233Sat, 23 Jun 2018 07:35:35 +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)Blogger2592125tag:blogger.com,1999:blog-3722233.post-4397437624918579778Fri, 22 Jun 2018 17:31:00 +00002018-06-22T13:31:33.103-04:00The Muffin ProblemI've been meaning to post on THE MUFFIN PROBLEM for at least a year. Its a project I've been working on for two years, but every time I wanted to post on it I thought.<br />
<br />
<br />
<i>I'm in the middle of a new result. I'll wait until I get it!</i><br />
<br />
However, I was sort of forced to finally post on it since Ken Regan (with my blessing) posted on it. In fact its better this way- you can goto his post for the math and I get to just tell you other stuff.<br />
<i><br /></i>
The problem was first defined by Alan Frank in a math email list in 2009.<br />
<i><br /></i>
I'll define the problem, though for more math details goto Ken's post: <a href="https://rjlipton.wordpress.com/2018/06/21/muffins-and-integers/">here</a>.<br />
<br />
You have m muffins and s students. You want to give each student m/s piece and<br />
divide the muffins to maximize the min piece. Let f(m,s) be the size of the min piece<br />
in an optimal divide-and-distribute procedure.<br />
<br />
Go and READ his post, or skim it, and then come back.<br />
<br />
Okay, you're back. Some informal comments now that you know the problem and the math<br />
<br />
1) I saw the problem in a pamplet at the 12th Gathering for Gardner. Yada Yada Yada I have 8 co-authors and 200 pages, and a paper in FUN with algorihtms You never know when a problem will strike you and be worth working on!<br />
(The 8 coauthors are Guangiqi Cui, John Dickerson, Naveen Dursula, William Gasarch, Erik Metz,<br />
Jacob Prinze, Naveen Raman, Daniel Smolyak, Sung Hyun Yoo. The 200 pages are <a href="ttps://arxiv.org/abs/1709.02452">here</a>. The FUN with algorithms paper, only 20 pages, is <a href="http://drops.dagstuhl.de/opus/volltexte/2018/8806/pdf/LIPIcs-FUN-2018-15.pdf">here</a>)<br />
<br />
2) Many of the co-authors are HS students. The problem needs very little advanced mathematics (though Ken thinks it might connect to some advanced math later). This is a PRO (HS students can work on it, people can understand it) and a CON (maybe harder math would get us more unified results)<br />
<br />
3) The way the research had gone is a microcosm for math and science progress:<br />
<br />
We proved f(m,s) = (m/s)f(s,m) (already known in 2009) by Erich Friedman in that math email list)<br />
<br />
Hence we need only look at m>s.<br />
<br />
First theorem: we got a simple function FC such that<br />
<br />
f(m,s) ≤ FC(m,s)<br />
<br />
for MANY m,s we got f(m,s) = FC(m,s).<br />
<br />
GREAT! - conjecture f(m,s) = FC(m,s)<br />
<br />
We found some exceptions, and a way to get better upper bounds called INT.<br />
<br />
GREAT! - conjecture f(m,s) = MIN(FC(m,s),INT(m,s))<br />
<br />
We found some exceptions, and a way to get better upper bounds called ... We now have<br />
<br />
conjecture<br />
<br />
f(m,s) = MIN(FC(m,s), INT(m,s), ERIK(m,s), JACOB(m,s), ERIKPLUS(m,s), BILL(m,s))<br />
<br />
and it looks like we still have a few exceptions.<br />
<br />
This is how science and math works- you make conjectures which are false but the refutations lead<br />
to better and better results.<br />
<br />
Also, we have over time mechanized the theorems, a project called:<br />
<br />
<i>Making Erik Obsolete</i><br />
<br />
since Erik is very clever at these problems, but we would like to not have to rely on that.<br />
<br />
4) I have worked hard on this problem as is clear from this: <a href="https://www.cs.umd.edu/users/gasarch/BLOGPAPERS/billmuffins.JPG">picture</a><br />
<br />
<br />https://blog.computationalcomplexity.org/2018/06/the-muffin-problem.htmlnoreply@blogger.com (GASARCH)0tag:blogger.com,1999:blog-3722233.post-1193088248712227693Mon, 18 Jun 2018 02:31:00 +00002018-06-18T11:07:40.883-04:00Its good to be mii<div class="separator" style="clear: both; text-align: center;">
<a href="https://3.bp.blogspot.com/-LQZaKnqa-24/Wye95teJDSI/AAAAAAABgmA/MkgtyeUue_w7fa22AHEaYY5127T0bNueACLcBGAs/s1600/WilliamGasarch-MII.jpg" imageanchor="1" style="clear: left; float: left; margin-bottom: 1em; margin-right: 1em;"><img border="0" data-original-height="316" data-original-width="316" height="200" src="https://3.bp.blogspot.com/-LQZaKnqa-24/Wye95teJDSI/AAAAAAABgmA/MkgtyeUue_w7fa22AHEaYY5127T0bNueACLcBGAs/s200/WilliamGasarch-MII.jpg" width="200" /></a></div>
When I taught ugrad Elementary Theory of Computation (Reg, CFL, P, NP, Dec, c.e.) I made 5% of the grade be MEET THE PROF- come to my office, in groups of 3-6 (though sometimes I got 10) just to talk to me. I ask them what there plans are, why they took the course, and they get to ask ME what they want.<br />
<br />
The most common question I got:<br />
<br />
Why is your mii the example of a mii on the Wikipedia entry on mii: <a href="https://en.wikipedia.org/wiki/Mii">here</a> (<a href="https://en.wikipedia.org/w/index.php?title=Mii&oldid=845863614">permalink</a>)<br />
<br />
I was originally hesitant to blog about this because (1) it may go away soon, and (2) I don't know.<br />
<br />
But (1) its been there and stable for a while, and (2) I can speculate:<br />
<br />
1) A prof in my department (not me) made and posted a Wikipedia page about me.<br />
<br />
2) That page used the mii.<br />
<br />
3) The powers that be at Wikipedia took down the mii (along with the list of my grad students who got PhD's). This post is not a rant about this, but I will note that I think they should have allowed the mii since it looks like me. whenever I am going to meet someone at an airport I email them the mii and it always works.<br />
<br />
4) Speculation: since it was on my Wikipedia page this mii was in the public domain and they could easily access it. Hence they used it. Is Wikipedia this arbitrary? Yes.<br />
<br />
5) My darling thinks is unfair that the mii page can use my mii but my page can't. I just think its odd.https://blog.computationalcomplexity.org/2018/06/its-good-to-be-mii.htmlnoreply@blogger.com (GASARCH)4tag:blogger.com,1999:blog-3722233.post-8402524769831420181Thu, 14 Jun 2018 19:44:00 +00002018-06-14T15:44:07.053-04:00Hoteling<div class="" style="clear: both; text-align: left;">
</div>
<div class="separator" style="clear: both; text-align: left;">
Thanks to Grigory Yaroslavtsev for taking over the <a href="https://docs.google.com/spreadsheets/d/1P5okKjeNlvkEEFMzX3l8VcL4SHpWBKNFET-5mPTWfDQ/edit?usp=sharing">Theory Jobs Spreadsheet</a>. Details on <a href="http://grigory.us/blog/theory-jobs-2018/">Grigory's blog</a>. Check out who is going where next year.</div>
<br />
<div class="separator" style="clear: both; text-align: center;">
<a href="https://4.bp.blogspot.com/-WgH8PebkshE/WyKBL8Z2AFI/AAAAAAABghg/X2mIdTBiIqEJ0ywaXEWU7R9EEve36h12wCKgBGAs/s1600/IMG_20180216_154918.jpg" imageanchor="1" style="margin-left: 1em; margin-right: 1em;"><img border="0" data-original-height="1302" data-original-width="1124" height="320" src="https://4.bp.blogspot.com/-WgH8PebkshE/WyKBL8Z2AFI/AAAAAAABghg/X2mIdTBiIqEJ0ywaXEWU7R9EEve36h12wCKgBGAs/s320/IMG_20180216_154918.jpg" width="275" /></a></div>
<br />
<br />
My office has an awesome view of Midtown Atlanta. Midtown has seen considerable construction over the last decade and I get to see the skyline change before my eyes. <a href="https://en.wikipedia.org/wiki/NCR_Corporation">NCR</a> opened an impressive glass building for their new world headquarters just a few months ago not coincidentally a short walk from Georgia Tech. A few weeks ago I got a tour of this facility.<br />
<div class="" style="clear: both; text-align: left;">
<br /></div>
<div class="" style="clear: both; text-align: left;">
Most of the employees in the building do not get their own offices or desks. They have an open floor plan with hoteling. They use an app to reserve a desk up to a few weeks ahead of time. Each desk has a keyboard and two screens that they stick their laptops into. Their cell phones become their main phones. There are many conference rooms of different sizes, even some tiny ones meant for a single person to have a phone call or escape to some quietness.<br />
<br />
Would hoteling work in the academic world? Never, you learn quickly that professors will never give up two things: their office or their parking. When we do talk about hoteling, we talk about a shared office for people who have a main office in a different building.<br />
<br />
With faculty who often travel at far too many conference, or on some days working out of home or coffee shops and rarely using the books in their office, if they have them at all, why do we stick to the old fashioned offices?<br />
<br />
The best academic research require collaboration, between faculty, students, postdocs and other researchers. The best times I've had as a professor is when a student or colleague walks into my office with a question, an idea or sometimes a proof. Better if I have some place to be found and not just a location in an app.<br />
<br />
I'd also miss the view. </div>
https://blog.computationalcomplexity.org/2018/06/hoteling.htmlnoreply@blogger.com (Lance Fortnow)1tag:blogger.com,1999:blog-3722233.post-6021604827359277098Mon, 11 Jun 2018 04:45:00 +00002018-06-11T00:46:54.305-04:00How the Villarino-Gasarch-Regan paper came about(This post overlaps a prior one <a href="http://blog.computationalcomplexity.org/2016/12/the-very-first-ramseyian-theorem.html">here</a>. The paper I am blogging about was also blogged about by Lipton <a href="https://rjlipton.wordpress.com/2018/06/08/hilberts-irreducibility-theorem/">here</a>. The paper itself is on arxiv <a href="https://arxiv.org/abs/1611.06303">here</a>. My slides for a talk I will be giving on this material are <a href="https://www.cs.umd.edu/users/gasarch/hilbertalk.pdf">here</a>)'<br />
<br />
<br />
<br />
Todays post is on how the paper came about. A later post will be about why someone else didn't do it earlier.<br />
<br />
How this paper came about:<br />
<br />
Many years ago Bill noticed that while several books on Ramsey theory (see my prior post for quotes) state that the HCL was the first Ramseyian theorem. I think one source mentioned in passing that Hilbert used it to prove the Hilbert Irreducibility theorem (HIT). Bill could not find a modern English exposition of the proof. So he asked Ken Regan (who not only knows German but can recite The Lewis Carol Poem J<i>abberwocky</i> in German!) to translate it, and then Bill would put it in modern language, and there would be an exposition. Bill got bogged down in some of the math, and they both got bogged down with other things (For Ken catching chess-cheaters, for Bill mentoring HS students, for both of them, blogging.) Many years passed.<br />
<br />
Sometime before 2015 Larry Washington showed me a nice proof that (ignoring mult constants)<br />
<br />
∑ 1/p ≤ ln(ln(n)) + O(1) (the sum is over all primes p ≤n )<br />
<br />
Read that carefully. There are many proofs in the web that the sum isat least ≥ ln(lg n) but I could not find any that the sum was ≤ ln(ln n). Larry Washington told me that the result and<br />
the proof were not new. I told him that, even so, it doesn't seem to be out there. So we agreed to write and and post to arXiv but not publish in a journal. It's <a href="https://arxiv.org/abs/1511.01823">here</a>.<br />
<br />
This arXiv paper caught the attention of Mark since he had an exposition of Merten's proof see <a href="https://arxiv.org/abs/math/0504289">here</a> that that sum diverges. Mertens proof had explicit bounds which are missing from modern proofs.<br />
<br />
I got into an email discussion with Mark about Math and History and I casually mentioned that Ken and I had worked on-and-off on HRL and HIT. A few weeks later he emailed me a translation of the paper. WOW! We worked together on polishing it, combining it with what Ken had done, and later brought Ken back into the project. I say without embarasment that we NEEDED Mark to resolve some of the issues we had and push the paper out the door. A Win-Win-Win.<br />
<br />
And a lesson here--- Larry Washington was reluctant to publish on arXiv a paper on stuff that was already known. I should have told him<br />
<br />
<i>But Larry, if we do that I might find someone to help me finish the Hilbert paper</i><br />
<br />
In a word: Serendipity.https://blog.computationalcomplexity.org/2018/06/how-villarion-gasarch-regan-paper-came.htmlnoreply@blogger.com (GASARCH)0tag:blogger.com,1999:blog-3722233.post-7475523893806375286Wed, 06 Jun 2018 23:40:00 +00002018-06-06T19:40:47.448-04:00I tell my class that P is important because... but is that really true?When teaching P vs NP the questions arises (and if not then I bring it up) what if you have algorithm in P that takes n^{100} time?. Or even n^{5} time which might be too long.<br />
<br />
I have given the following answers for years; however, I post this and will use your comments as a sanity check. In fact, I suspect I am wrong on some points.<br />
<br />
1) IF SAT was in P then something very clever was done. Even if its n^{100} it was very clever. That cleverness will almost surely result in other better algorithms. They may only be better in practice by not in theory (it works in practice- if only we can get it to work in theory :-) ), but it will still work and be a great advance.<br />
<br />
2) IF SAT was in P then perhaps we could USE SAT in P to get a better algorithm for SAT in P. This was the theme of a chapter in Lance Fortnow's book <a href="https://www.amazon.com/Golden-Ticket-NP-Search-Impossible/dp/0691175780/ref=sr_1_1?ie=UTF8&qid=1491666026&sr=8-1&keywords=Lance+Fortnow">The Golden Ticket: P, NP. and the search for the impossible</a> and is also likely behind something I once heard (I think it was from Scott but I can't find it on his blog) <i>If P=NP then math would be easy and we would have already found a proof that P=NP. Hence P ≠ NP</i><br />
<br />
The two above really can't be WRONG or even RIGHT or even NOT EVEN WRONG since they are speculations. The next few is where I need my sanity checked<br />
<br />
3) Whenever a real world natural problem is in P it has a low degree poly algorithm OR there are ideas to make it work in practice, if not in theory. When Lance read a prior version of this post he pointed out that `real world natural problem' is not a well defined term. True. Not sure what to do about that. Even so, is this true? roughly true? Something theorists say to be able to sleep at night?<br />
<br />
4) In the real world people say ``OH- the problem is NP-complete. Better look for approx solutions instead'' Or similar things. While this sounds true since I have never worked in the real world I really don't know. Is that what people say? do?<br />
<br />
5) If Lance proves P=NP next week then the consequences are enormous for real people working on real computing problems. But what if Lance proves P NE NP? Would that affect people working on real computing problems? A long time Carl Smith told me <i>If P NE NP was proven then the proof would have great insight into computing which would have a real affect on real people working on real computing problems</i>. My Darling (who is a Software Engineer) is skeptical of that. What do you think?https://blog.computationalcomplexity.org/2018/06/i-tell-my-class-that-p-is-important.htmlnoreply@blogger.com (GASARCH)15tag:blogger.com,1999:blog-3722233.post-4482978010782675334Fri, 01 Jun 2018 18:09:00 +00002018-06-03T11:14:50.186-04:00BQP not in the Polynomial-Time Hierarchy in Relativized WorldsThe quantum complexity world is a rocking with the paper released yesterday by Ran Raz and Avishay Tal, <a href="https://eccc.weizmann.ac.il/report/2018/107/">Oracle Separation of BQP and PH</a>, resolving a question open since quantum complexity got its start over two decades ago. Scott Aaronson's <a href="https://www.scottaaronson.com/papers/bqpph.pdf">2010 paper</a> that sets some of the groundwork for the Raz-Tal result gives a nice overview of the question.<br />
<br />
All of you readers should be familiar with the P v NP question. P is the set of problems efficiently solvable by a deterministic computer. NP are the problems for which there exists a witness that we can verify quickly. The polynomial-time hierarchy (PH) is the constant alternation generalization of NP that has played a <a href="https://blog.computationalcomplexity.org/2005/06/favorite-theorems-polynomial-time.html">major role in computational complexity</a> So why don't we talk about the P vs PH question? That's just equivalent to P vs NP.<br />
<br />
BQP is the the class of problem efficiently solved by a quantum computer. Since P sits in BQP which sits in PSPACE we can't prove outright any separations for BQP without separating P from PSPACE. We can though get an understanding of complexity by allowing the machines access to the same oracle and seeing what we can separate. We already knew BQP doesn't sit in NP relative to an oracle. Same was true for BPP (efficient probabilistic computation) but BPP is in PH for all oracles as are constant round interactive proofs. So we might expect we can have BQP in PH, BQP solvable with constant alternations, relative to all oracles. Raz and Tal refute that hypothesis.<br />
<br />
Raz and Tal's proof builds on the Forrelation concept developed by <a href="https://www.scottaaronson.com/papers/bqpph.pdf">Aaronson</a> (under the name Fourier Checking) and extended by <a href="https://arxiv.org/abs/1411.5729">Aaronson and Ambainis</a>. The oracle isn't complicated: Pick n numbers x<sub>1</sub>,...,x<sub>n</sub> each x<sub>i</sub> chosen from a normal distribution with mean 0 and variance a small ε > 0. Let y=y<sub>1</sub>,...,y<sub>n</sub> be the <a href="https://en.wikipedia.org/wiki/Hadamard_transform">Hadamard transform</a> applied to x<sub>1</sub>,...,x<sub>n</sub>. You then probabilistically round the x's and y's to 1 or -1. A quantum machine can distinguish this distribution from uniform using the fact that quantum machines can do Hadamards easily and Raz and Tal use Fourier show that low-depth alternating circuits (that capture PH) can't distinguish so easily. The <a href="https://eccc.weizmann.ac.il/report/2018/107">paper</a> is well-written if you want details.<br />
<br />
A few questions for further directions:<br />
<ul>
<li>Can you show a relativized world where P = NP (=PH) but P ≠ BQP? I'd suspect it will be a messy but not too hard generalization of this paper.</li>
<li>How far can you push the Raz-Tal result, i.e., for what function f(n) can we show that BQP cannot be solved by f(n)-alternating polynomial-time Turing machines. Can you show f(n) = n<sup>Ω(1)</sup>?</li>
</ul>
<div>
Also see Scott's <a href="https://www.scottaaronson.com/blog/?p=3827">personal take</a> on this new result.</div>
https://blog.computationalcomplexity.org/2018/06/bqp-not-in-polynomial-time-hierarchy-in.htmlnoreply@blogger.com (Lance Fortnow)2tag:blogger.com,1999:blog-3722233.post-1761435662289905853Thu, 31 May 2018 15:09:00 +00002018-05-31T14:13:25.293-04:00Seventh Grade Math ContestI stumbled upon an old <a href="https://www.lesswrong.com/posts/EdFDwjsLNpgtTMJAp/great-mathematicians-on-math-competitions-and-genius">blog post</a> on the Lesswrong weblog that quotes several famous mathematicians on the connections, or lack thereof, between mathematics competitions and mathematics research. Let me tell you how a seventh grade math contest altered the course of my life.<br />
<br />
In 1975 I attended seventh grade in a middle school in upstate New Jersey. The school divided the students into three tracks, honors, standard and remedial, and I was an unexceptional student in the standard track. We all took a math pretest to determine who would represent the school in a state-wide competition. To everyone's surprise, especially my own, I killed on the test scoring twice as many points as anyone else. The school adjusted my course schedule but because of my not-so-great English skills I became the only student taking honors math and science and standard English and History (with a racist history teacher but that's another story). I think I came in 12th in the state competition.<br />
<br />
I never did well in math contests after that, doing okay but not particularly strong in high school competitions. But the experience drove me to what we now call STEM. I got involved in computers and math in high school which led me to study engineering, <a href="https://blog.computationalcomplexity.org/2005/12/how-i-became-theorist.html">briefly</a>, at Cornell. I did <a href="https://blog.computationalcomplexity.org/2005/12/first-saturday-in-december.html">make the Putnam team</a> as a freshman at Cornell, but scored a zero which pretty much ended my career in math competitions.<br />
<br />
<br />https://blog.computationalcomplexity.org/2018/05/seventh-grade-math-contest.htmlnoreply@blogger.com (Lance Fortnow)0tag:blogger.com,1999:blog-3722233.post-2027657983416254684Wed, 30 May 2018 04:22:00 +00002018-05-30T08:00:37.194-04:00Why is someone emailing me an offer to apply to be chair?I recently go the following email (I blocked out identifying information of who send it and what college is involved. I doubt I needed to legally but... you never know.) I include my comments on the email in cap letters.<br />
<br />
I am NOT flattered by the email. I have LESS regard for those who send it.<br />
<br />
I will say that the school is respectable and I had heard of them. I'm just surprised they heard of me.<br />
<br />
(The letter was typeset fine- if there are problems with typesetting below thats on me.)<br />
<br />
---------------------------------------------------------------<br />
Dear Dr. Gasarch,<br />
<br />
XXX Inc. has been retained to assist XXX University in the search for the<br />
next Chair of the Computer Science and Engineering Department.<br />
<br />
ADMIN EXPERIENCE: RUNNING AN REU PROGRAM. NOT NEARLY ENOUGH.<br />
<br />
Your expertise and accomplishments have come to our attention, and we would appreciate the opportunity to speak with you about this position.<br />
<br />
IF THEY MEAN ADMIN-EXPERTISE, THATS JUST SILLY.<br />
<br />
IF THEY MEAN PAPERS AND SUCH... LETS JUST SAY I AM ON THE OBSCURE END OF THEORY AND WONDER WHAT ACCOMPLISHMENTS THEY MEAN. MY MUFFIN PAPER?<br />
<br />
EXPERTISE: MENTORING HS AND UGRAD STUDENTS. BLOGGING? EXPERT OR NOT I"VE DONE IT FOR A WHILE. NOT THE STUFF OF CHAIR'S.<br />
<br />
Could you suggest some times over the next week that<br />
might work for your schedule? We will be very respectful of your time.<br />
<br />
<br />
XXX is located in XXX, XX where the city’s diverse and growing population puts it in the<br />
Top 10 U.S. cities in population and in the Top 5 fastest growing cities. XXX has an endowment of $1.5B and recently completed a $1.3B campaign. The Computer Science and Engineering Department has been targeted for significant advancement and new faculty hires. The next Department Chair will lead and direct this enhancement.<br />
<br />
<br />
The XXX Metroplex is a dynamic region with leading high-technology companies in the aerospace,<br />
defense, energy, information technology, life sciences, semiconductors, telecommunications,<br />
transportation, and biomedical industries. Some of the top companies and research institutes with a strong presence in the XXX area include LONG LIST OF COMPANIES I HAVE HEARD OF.<br />
<br />
THESE LAST TWO PARAGRAPHS WOULD BE A LOT MORE IMPRESSIVE IF I DIDN"T KNOW THEIR WAY TO PICK CANDIDATES TO ASK TO APPLY WAS SO TERRIBLE.<br />
<br />
Please click here to view a two-minute video in which the President, Provost, and Dean of the<br />
XXX School of Engineering at XXX discuss some of the possibilities for research and growth<br />
that the Chair of Computer Science and Engineering will have the opportunity to develop.<br />
Cybersecurity, particularly, is an identified area for growth and hiring to directly complement the XXX Institute for Cyber Security. A full listing of the qualifications and duties of the position can be found in the profile under “Current Searches” at XXX<br />
<br />
CYBERSECURITY- I HAVE TAUGHT A 1-CREDIT MINI-COURSE IN CRYPTO. I HAVE A SURVEY AND A PAPER ON PRIVATE INFO RETRIEVAL. I DOUBT THAT'S WHY THEY CONTACTED ME.<br />
<br />
<br />
Best,<br />
<br />
XXX<br />
-------------------------------------------------<br />
<br />
So why did they email me? Speculation<br />
<br />
1) They meant to email Lance and got confused.<br />
<br />
2) They cast a VERY wide net. The UPSIDE of doing that so is that they might find someone<br />
they would have overlooked. The DOWNSIDE of doing that is... thats the problem with<br />
spam- there is absolutely no downside.<br />
<br />
3) They emailed every computer science professor who has a wikipedia page? a blog? a book?<br />
Some criteria which I happened to fit.<br />
<div>
<br /></div>
<br />
<br />https://blog.computationalcomplexity.org/2018/05/why-is-someone-emailing-me-offer-to.htmlnoreply@blogger.com (GASARCH)4tag:blogger.com,1999:blog-3722233.post-6550933808686728606Thu, 24 May 2018 15:15:00 +00002018-05-24T11:18:12.595-04:00Kolmogorov Complexity and Causation<div class="tr_bq" style="font-family: sans-serif; font-size: 13px;">
<br /></div>
<div style="font-family: sans-serif; font-size: 13px;">
I got an interesting email question.</div>
<blockquote style="font-family: sans-serif; font-size: 13px;">
Suppose I give you a set of points S of the form (x,y). He suggested ideally they would be pairs of a real numbers. Supposing there is a causal relationship between x and y of some kind, we want to know know if it is more likely that the x value causes the y value or the y value causes the x value. One plausible way to decide what the answer should be is by answering the question <b>is the length of the shortest program which maps the x values to their y values shorter than the length of the shortest program which maps the y values to their x values.</b></blockquote>
<blockquote style="font-family: sans-serif; font-size: 13px;">
So, my intuition says that this is clearly undecidable. I'm actually having a hard time thinking of a proof, so do you happen to know of one or if this problem might actually be decidable?</blockquote>
<blockquote style="font-family: sans-serif; font-size: 13px;">
On a related note, since I'm already writing you about this question, do you happen to know about the complexity of any related questions which involve circuit size instead of program length? </blockquote>
Let's use notation from Kolmogorov complexity, letting C(x|y) be the size of the smallest program that takes y as input and outputs x. Now suppose it is decidable to determine whether C(x|y) > C(y|x). Then find an x of length n such that for all y of length n/3, C(x|y)>C(y|x). Such x exist: For any random x, C(x|y)>= 2n/3 and C(y|x) <= n/3.<br />
<br />
Now I claim C(x)>=n/4 for the x you found. If not we have C(x|y)<=C(x)<n/4 but for some y, C(y|x)>=n/3 since there aren't enough shorter programs to cover all the y's.<br />
<br />
Since there is no computable procedure to find x such that C(x)>=n/4, there can't be decidable procedure to determine whether C(x|y) > C(y|x).<br />
<br />
But does this question relate to causality. Pick a random x from strings of length n and y at random from strings of length n/3. We have C(x|y) > C(y|x) even though there is no causality.<br />
<br />
Instead you could look at the information of y in x, how many bit of x does y help describe, defined by I(y|x) = C(x)-C(x|y). This measure correlation since I(y|x)=0 iff x and y are independent but symmetry of information gives I(y|x)=I(x|y) so no hope for causation.<br />
<br />
In short, Kolmogorov complexity won't give you much on causation--you can't avoid the controlled experiments.<br />
<br />
For your last question, there is a notion of Kolmogorov complexity that roughly corresponds to circuit size, KT(x|y) defined as the sum of the program size and running time minimized over all programs p that take y as an input and output x. I'm guessing it's hard to determine if KT(x|y) < KT(y|x) and you could probably show it under some assumption like secure psuedorandom generators. Also symmetry of information isn't believed to hold for KT complexity so maybe there is something there. Interesting questions.https://blog.computationalcomplexity.org/2018/05/kolmogorov-complexity-and-causation.htmlnoreply@blogger.com (Lance Fortnow)6tag:blogger.com,1999:blog-3722233.post-1382101806799648760Mon, 21 May 2018 02:44:00 +00002018-05-20T22:44:17.759-04:00COMPUTER PROOF vs computer proof- Quadratic VDW theorem<b>Quad VDW Theorem: </b>For all c there exists W=W(c) such that for all c-colorings of {1,...,W} there exists a,d such that a and a+d<sup>2</sup> are the same color.<br />
<br />
What is known about W(c)?<br />
<br />
The first proof of Quad VDW was nonconstructive.<br />
<br />
The second proof was constructive but used VDW's theorem and gave terrible bounds, even for W(2).<br />
<br />
EASY: Show W(2)=5<br />
<br />
ON A HS MATH COMP: Show that for all 3-colorings of {1,...,2003} there exists two numbers a square apart that are the same color.<br />
<br />
One can get a bound less than 100.<br />
<br />
With a lot more detailed work one can get W(3)=29.<br />
<br />
None of above was done with a computer.<br />
<br />
SO- what about W(4)? There are three proofs that W(4) exists:<br />
<br />
a) Prove the QUAD VDW theorem. This gives terrible bounds.<br />
<br />
b) I had some students use SAT solvers and they obtained W(4)=58. I am sure they are right and I am glad to know it (especially since it confirms the general mantra that the bounds from proofs in Ramsey theory tend to be much bigger than the reality) but its somehow unsatisfying. I want a <i>HS proof. </i>I wanted to put it on the MD Math Comp for 2017 but wiser people prevailed.<br />
<br />
c) I gave the problem to a Grad Student Zach Price and he came up with a HS proof-- sort of. Look at the following graph: <a href="https://www.cs.umd.edu/users/gasarch/COURSES/858/S18/qvdw4.pdf">here</a>. It shows that in any 4-coloring of N which does not have two numbers a square apart the same color:<br />
<br />
COL(x) = COL(x+290085289)<br />
<br />
from this one can obtain<br />
<br />
W(4) ≤ 290085289<sup>2</sup> (which is MUCH better than the bound from the proof of Quad VDW) and hence a proof of QVDW that does not need a program, except that to FIND this gadget used a program. I doubt a HS student could do this on an exam.<br />
<br />
Is Zach's proof the HS proof I am looking for?<br />
<br />
PRO- once you see it its easy to verify and does not need a program.<br />
<br />
CON- coming up with it needed a program.<br />
<br />
More to the point: which proof do you like better:<br />
<br />
1) The SAT Solver proof. Not a proof you can see or feel, but gives exact bounds.<br />
<br />
or<br />
<br />
2) Zach's gadget proof. Much worse bound but you can see and feel the proof, and verify it after you know the gadget.<br />
<br />
I prefer Zach's proof.<br />
<br />
<br />https://blog.computationalcomplexity.org/2018/05/computer-proof-vs-computer-proof.htmlnoreply@blogger.com (GASARCH)6tag:blogger.com,1999:blog-3722233.post-2786119715083585690Thu, 17 May 2018 12:37:00 +00002018-05-17T08:37:05.089-04:00The Complexity of the FirmIn 1937, a year after Turing had his <a href="https://www.cs.virginia.edu/~robins/Turing_Paper_1936.pdf">seminal paper</a>, Ronald Coase published a paper <a href="http://dx.doi.org/10.2307/2626876">The Nature of the Firm</a> to give a framework to why we have companies and how large they become. In a perfect market economy we shouldn't need a firm at all, everyone is just an independent contractor and market pricing will drive efficient use of labor. Coase notes there are costs to creating contracts and one can gain efficiencies by avoiding these contracts by having both parties inside the same organization.<br />
<br />
Much of those costs come from complexity, it is impossible to create a contract to cover all possible outcomes and thus contracts are incomplete leading to loopholes and lawsuits.<br />
<br />
In the other direction, having the central organization of a firm has its own costs, from inefficiencies from not using markets to balance supply and demand, to the complexity of the organization processes themselves. In Coase's model, a firm grows to a size that balances the organization and contract costs at the margin.<br />
<br />
So what happens to the sizes of firms when we reduce complexity, as happens with modern computing, from better communication, optimization and data analytics. We see relatively new companies like Google and Amazon getting larger. We also see a number of startups and small companies with very few workers, sometimes just one.<br />
<br />
Computing drops both the cost of central organization and the cost of contracts so the size of a firm depends on circumstance. One can have a tech startup with a small number of workers since they can write apps that run on other people's platforms (like web browsers and on phones) and have the processing done on the cloud where they can scale or not scale as needed. Meanwhile a large company can more easily coordinate and connect using modern technology making it cost efficient to expand.<br />
<br />
As we enter a new age of machine learning and automation, how will that affect the very nature of companies in the future? How about universities, a special kind of firm in itself? How can we harness the tools and ideas from computational complexity to help understand these and other societal changes.https://blog.computationalcomplexity.org/2018/05/the-complexity-of-firm.htmlnoreply@blogger.com (Lance Fortnow)1tag:blogger.com,1999:blog-3722233.post-5638366209732216386Tue, 15 May 2018 03:47:00 +00002018-05-14T23:47:31.696-04:00What does it mean for a student to guess an answer?On my final in Aut Theory I wanted to ask a TRUE/FALSE/UNKNOWN TO SCIENCE<br />
question but did not want them to guess. Hence I had +4 for a right answer, -3 for a wrong answer.<br />
Here is the question:<br />
<br />
------------------------------------------------------------------------------------------<br />
For each of the following say if its TRUE, FALSE, or UNKNOWN TO SCIENCE. No Proof Required BUT you get +4 for every right answer and -3 for every wrong answer and 0 for an answer left blank. So<br />
<br />
DO NOT GUESS!!!!!!!!!!!!!!!!!!!!!!!!!!!<br />
<br />
a) If A is regular and F is a finite set then A UNION F is regular.<br />
<br />
b) If A is in P and F is a finite set then A UNION F is in P.<br />
<br />
c) If A is in NP and F is a finite set then A UNION F is in NP.<br />
<br />
d) If A is decidable and F is a finite set then A UNION F is decidable.<br />
<br />
e) If A is undecidable and F is a finite set then A UNION F is undecidable<br />
-------------------------------------------------------------------------------------------------<br />
<br />
Note that they are all TRUE. A student who (as many did) answered T-T-T-T-F had the following conversation with me:<br />
<br />
BILL: You guessed! I told you DO NOT GUESS!!!!!!!!!!!!<br />
<br />
STUDENT: No. I REASONED that you would not make them all T, so by this reasoning the last one had to be F. I now see that my reasoning is wrong--- you would make them all T, but it was not guessing, it was reasoning.<br />
<br />
I claim the student was guessing, he claims he was not. What do you think?<br />
<br />
Having said that, the following IS a rational strategy:<br />
<br />
If I don't know the answer but it has nothing to with P vs NP then it has to be T or F. In this case guess since exp val is positive. If the answer has to do with P vs NP then do not guess.<br />
<br />
This also raises a question- if they honestly thought (say) e was F I want to just give them 0, whereas if they are guessing or using reasoning about `Bill wouldn't ...' I want to give them -3. But alas, we cannot read their minds or souls.<br />
<br />
<br />
<br />
<div>
<br /></div>
https://blog.computationalcomplexity.org/2018/05/what-does-it-mean-for-student-to-guess.htmlnoreply@blogger.com (GASARCH)10tag:blogger.com,1999:blog-3722233.post-7906942953886075696Fri, 11 May 2018 09:29:00 +00002018-05-11T05:29:12.343-04:00Richard Feynman (1918-1988)<a href="https://3.bp.blogspot.com/-e3h0ABkxT64/WvMxBvu2JmI/AAAAAAABgL4/v969shFo2CUD1Amf-kWoE00uYAuM_WB5QCLcBGAs/s1600/51jL19me4oL._SX330_BO1%252C204%252C203%252C200_.jpg" imageanchor="1" style="clear: right; float: right; margin-bottom: 1em; margin-left: 1em;"><img border="0" data-original-height="499" data-original-width="332" height="320" src="https://3.bp.blogspot.com/-e3h0ABkxT64/WvMxBvu2JmI/AAAAAAABgL4/v969shFo2CUD1Amf-kWoE00uYAuM_WB5QCLcBGAs/s320/51jL19me4oL._SX330_BO1%252C204%252C203%252C200_.jpg" width="211" /></a><br />
When I took cryptography from Manuel Blum, he handed out copies of the chapter "Safecracker Meets Safecracker" from Richard Feynman's book <a href="https://amzn.to/2KPg97V">Surely You're Joking Mr. Feynman</a>. Feynman, the Nobel Prize winning physicist who was born a hundred years ago today, wrote this book not about physics but just a series of stories from different times in his life. This chapter described how Feynman learned how to open locked safes in Los Alamos during the Manhattan Project.<br />
<br />
We all have interesting stories to tell but Feynman finds a way to keep things compelling in a way most scientists could not--even if he sometimes comes off being a bit of a jerk, hence the title. This book inspired me to tell my own stories which occasionally show up in this blog.<br />
<br />
His most important stories form <a href="http://www.feynmanlectures.caltech.edu/">The Feynman Lectures on Physics</a> (free to read online), an amazing explanation of deep physical concepts.<br />
<br />
Richard Feynman's biggest contribution to theoretical computer science comes from a <a href="http://doc.cat-v.org/feynman/simulating-physics/simulating-physics-with-computers.pdf">1981 keynote address</a>.<br />
<blockquote class="tr_bq">
What kind of computer are we going to use to simulate physics? The full description of quantum mechanics for a large system cannot be simulated with a normal computer. And therefore, the problem is, how can we simulate the quantum mechanics? Can you do it with a new kind of computer—a quantum computer?</blockquote>
which begat a <a href="http://dx.doi.org/10.1098/rspa.1992.0167">proof-of-concept paper</a> by David Deutsch and Richard Jozsa which begat Daniel Simon's <a href="https://dx.doi.org/10.1137/S0097539796298637">exponential separation</a> which begat Peter Shor's <a href="https://dx.doi.org/10.1109/SFCS.1994.365700">factoring algorithm</a> which begat billions of research dollars and considerable expectations, real and imagined, for Feynman's vision.https://blog.computationalcomplexity.org/2018/05/richard-feynman-1918-1988.htmlnoreply@blogger.com (Lance Fortnow)1tag:blogger.com,1999:blog-3722233.post-8398865595246396690Wed, 09 May 2018 12:25:00 +00002018-05-09T08:25:15.994-04:00Second of N posts on G4G13. Maybe(Don't forget to vote for SIGACT posistions:<a href="http://www.acm.org/elections/sigs/sigact-election-bios">here</a> 9th workshop on Flexible network design, May 22-25 at College Park, <a href="http://www.cs.umd.edu/fnd2018">here</a>.)<br />
<br />
My first poston G4G13 is arguably <a href="https://blog.computationalcomplexity.org/2018/04/gahering-for-gardner-13-first-or-third.html">here</a>. To see why its debatable, see that post.<br />
<br />
FOXTROT HALF-EMPTY, HALF-FULL PROBLEM, INCLUDING 13 by Thomas Francic Banchoff<br />
<br />
In a Foxtrot cartoon (see <a href="https://www.google.com/search?q=Foxtrot+half+empty&tbm=isch&tbo=u&source=univ&sa=X&ved=0ahUKEwj17IunyvjaAhVptlkKHWBrDOgQ7AkINg&biw=1266&bih=867#imgrc=-Fbl5q_9hwo0RM:">here</a>) Foxtrot has a glass which looks like it is half-full (or half-empty)<br />
and asks people if its half-full or half empty. But the jokes on them!<br />
The class is slightly angled so its actually 5/12 full (or 7/12 empty)<br />
Given the area of the top and bottom What is the angle?<br />
Generalize to other dimensions.<br />
<div>
<br /></div>
<div>
--------------------------------------</div>
HEX PRIMES by Spandan Bandyopadhyay<br />
<br />
Here is an alternative definition of primes that<br />
lends itself to a generalization.<br />
<br />
A number x is PRIME if when there is a rectangle with<br />
integer sides and area x, one of the sides is 1.<br />
<br />
Lets generalize this!<br />
<br />
A number x is TRIPRIME if when there is a triangle with<br />
integer sides of area x, one of the sides is 1.<br />
<br />
Rather than use these prefixes we will go with<br />
<br />
A number x is n-PRIME if when there is a convex n-gon with<br />
integer sides and area x, one of the sides is 1.<br />
<br />
HEXPRIMES are of course 6-primes.<br />
<div>
<br /></div>
<div>
<div>
The problem with 5-minute talks (maybe it should have been 6 minutes)</div>
<div>
is that the concept is intersting but I didn't get to hear much</div>
<div>
about them. And I could not find a paper on line. Note that this</div>
<div>
conference has many non-academics for whome PAPERS are not the</div>
<div>
basic currency so things are more informal. This is GOOD in that</div>
<div>
its more of a free-for-all, but bad for follow up.</div>
<div>
ALL of G4G12's are on You-Tube, so when that happens for G4G13,</div>
<div>
I can follow up on this.</div>
<div>
<br /></div>
<div>
One thing I did manage to write down- 7 is the first HEX-composite.</div>
</div>
<div>
<br /></div>
https://blog.computationalcomplexity.org/2018/05/second-of-n-posts-on-g4g13-maybe.htmlnoreply@blogger.com (GASARCH)0tag:blogger.com,1999:blog-3722233.post-7043308287960261238Thu, 03 May 2018 11:12:00 +00002018-05-03T07:12:46.101-04:00Broader Impacts Redefined<i>The ACM Future of Computing Academy <a href="https://acm-fca.org/2018/03/29/negativeimpacts/" target="_blank">suggests</a> that "peer reviewers should require that papers and proposals rigorously consider all reasonable broader impacts, both positive and negative." Here is the broader impacts section of a future imagined grant proposal.</i><br />
<i><br /></i>My latest cryptocurrency paper will allow people to sell all sorts of paraphernalia, illegal, immoral and fattening, while avoiding paying taxes. Dr. Evil and his minions can move money around the world anonymously to more easily implement their dastardly plans. With this new work bitcoin will increase in value, causing far more mining setups that will deplete the energy resources of the world.<br />
<br />
Since I already own bitcoin, I will get filthy rich, increasing the gap between the one-percenters and the middle-class. I'll buy a fancy car and reprogram the auto-pilot to run over people who get in my way. And all those pesky bicyclists clogging the roads. That would be a positive impact.<br />
<br />
For the rest of humanity my new quantum gravitation algorithm will put all those people out of work. But their misery will be short lived because if anyone tries to run the algorithm, it may cause a small black hole that devours the earth.<br />
<br />
My proposed generic oracle separation would seem to have no impact whatsoever. But what happens if an alien race threatens to destroy the planet unless we find such a separation. I will have saved the earth, a very positive broader impact. Of course a different alien race could visit the earth and deem it mostly harmless until they discover my oracle, realized we have advanced too far and then blow us up before we become a threat.<br />
<br />
In other broader impacts, I will train graduate student to be just like me. Whether this is a positive or negative impact I leave to the reviewers.https://blog.computationalcomplexity.org/2018/05/broader-impacts-redefined.htmlnoreply@blogger.com (Lance Fortnow)3tag:blogger.com,1999:blog-3722233.post-2471016714947552704Mon, 30 Apr 2018 13:03:00 +00002018-05-02T21:51:16.013-04:00Gathering for Gardner 13 - the first or third of many postsI attended G4G13 (Gathering for Gardner- meeting 13). Martin Gardner was the Scientific American Mathematical Recreations columnist from 1956 until 1981. He had a great influence on many math-people of my generation.<br />
<br />
Most of the talks were 5 minutes so they could tell you a problem or thought of interest but not much more. This is GOOD in that I UNDERSTOOD most of the talks! There were also some talks on Magic and on science literacy (or perhaps science illiteracy) which were also interests of Martin Gardner.<br />
<br />
I posted on one <a href="https://blog.computationalcomplexity.org/2018/04/find-8-digits-number-such-that.html">problem</a> and its <a href="https://blog.computationalcomplexity.org/2018/04/the-8-digit-number-i-asked-for.html">solution</a> so this is either my first or third post on G4G13.<br />
<br />
Withouth further ado, here are my descriptions of some of the talks. OR you could just go <a href="http://www.gathering4gardner.org/g4g13-abstracts.pdf">here</a><br />
<br />
<br />
My descriptions are long- I may have lots of posts on G4G13!<br />
<br />
EXTENDING THE 10958 PROBLEM by Bill Ames.<br />
<br />
(paper on arxiv <a href="https://arxiv.org/abs/1302.1479">here</a>)<br />
<br />
In 2014 Taneja proposed the following math problem:<br />
<br />
Take the digits 1,2,3,4,5,6,7,8,9.<br />
<br />
You can put any of +, -, *, /, and powers you want between the digits, or erase the comma to get (for example) 34. Use parenthesis freely. Which natural numbers can you produce?<br />
<br />
Here are some examples:<br />
<br />
1 = 1 + (2 - 3) - (4 - 5) - (6 - 7) + (8 - 9)<br />
<br />
30 = 1 + 2^3 - 4*5 + 6*7 + (8-9)<br />
<br />
Which numbers can you get?<br />
<br />
Taneja got all the numbers between 0 and 11,111 EXCEPT 10958.<br />
<br />
(Is 10958 possible? The talk didn't say.)<br />
<br />
Using other operations- square roots and factorials- you can get 10958. The talk was about adding more operations and getting all numbers between 0 and 111,111<br />
<br />
THIRTEEN BOUNCES by Gary Antonick.<br />
<br />
Since this was G4G13 there were several talks about the number 13. The hotel did not have a 13th floor, and no room was of the form X13 (I was in room 515 and sometimes overshot my room since I assumed it would go 511-513-515, not 511-515). Martin Gardner would have OBJECTED to the lack of a 13th floor and would have condemned triskaidekaphobia (fear of the number 13 and the longest word I ever spelled correctly) as irrational. And he would be right. But I am preaching to the converted (also known as preaching to the choir).<br />
<br />
The talk was about firing a cannoball at a perfect reflector. If the cannon is positioned just right the ball will go back into the cannon. Can you make it do this after taking 13 bounces? What if you an only use a compass and straightedge for your calculations?<br />
<br />
A GRAMMATICAL APPROACH TO THE CURLING NUMBER CONJECTURE by Duane Bailey.<br />
<br />
(For more on the Curling Conjecture Google "Curling Number Conjecture"-- I was going to give a list of papers but there are just too many. There is no wikipedia entry on it, though I did learn about the sport of Curling!)<br />
<br />
Take any finite sequence of integers (we will just use natural numbers) for example<br />
<br />
2 3 2 3<br />
<br />
Write it as X Y Y Y ... Y with as many Y's as possible.<br />
<br />
for example<br />
<br />
(2 3)<sup>2</sup><br />
<br />
The number 2 is the Curling Number of the sequence. Append it to the sequence<br />
<br />
2 3 2 3 2<br />
<br />
Now take the Curling number of this sequence. It is 2 since the sequence is<br />
<br />
2 (3 2)<sup>2</sup><br />
<br />
Append it to the sequence:<br />
<br />
2 3 2 3 2 2<br />
<br />
Now the Curlng number of this sequence is 1 and we stop.<br />
<br />
The conjecture is that if you start with any sequence you will eventually get to 1.<br />
<br />
The talk relates the conjecture to aperiodic grammars.<br />
<div>
<br /></div>
<br />https://blog.computationalcomplexity.org/2018/04/gahering-for-gardner-13-first-or-third.htmlnoreply@blogger.com (GASARCH)5tag:blogger.com,1999:blog-3722233.post-28166366031252403Thu, 26 Apr 2018 14:11:00 +00002018-04-26T10:11:26.264-04:00The 8 digit number I asked for(On June 29th, co-located with STOC, there will be a workshop to celebrate Vijay Vazarani's 60th birthday. See <a href="https://www.cs.umd.edu/users/samir/stoc2018/">here</a>. As computer scientists shouldn't we use 64 as the milestone?)<br />
<br />
<br />
<br />
At Gathering for Gardner 13 Peter Winkler gave a great talk entitled<br />
<br />
Problems that Solve Themselves.<br />
<br />
(The title kind-of gives away how to solve it. And its just the kind of thing Peter Winkler would talk about. Hence I omitted the title and author when I first posted about it)<br />
<br />
I blogged about one of them, asking for the answer. I repeat the problem and answer it:<br />
<br />
Find an 8-digit number<br />
<br />
d_7 d_6 d_5 d_4 d_3 d_2 d_1 d_0<br />
<br />
such that<br />
<br />
d_0 is the number of 0's in the number<br />
<br />
d_1 is the number of 1's in the number<br />
<br />
d_2 is the number of 2's in the number<br />
<br />
.....<br />
<br />
d_6 is the number of 6's in the number<br />
<br />
but<br />
<br />
d_7 is NOT necc the number of 7's<br />
<br />
d_7 is the number of DISTINCT DIGITS in d_7 d_6 d_5 d_4 d_3 d_2 d_1 d_0<br />
<br />
WRONG APPROACH: Work out algebra for the digits, try to force it Actually, I had thought this was the wrong approach but some of the comments on my last blog DID do this.<br />
<br />
RIGHT APPROACH: Take an aribtrary number like<br />
<br />
1 1 1 1 1 1 1 1<br />
<br />
NOW- look at it and count the number of 0's, 1's, ... 6'ls and the number of distinct numbers<br />
For the new number let<br />
<br />
d_0 be the number of 0's in the old number<br />
<br />
....<br />
<br />
d_6 be the number of 6's in the old number<br />
<br />
d_7 be the number of distinct digits<br />
<br />
To get<br />
<br />
1 0 0 0 0 0 8 0<br />
<br />
iterate the process to get<br />
<br />
3 0 0 0 0 0 0 6<br />
<br />
3 1 0 0 0 0 0 6<br />
<br />
4 1 0 0 1 0 1 5<br />
<br />
4 0 1 1 0 0 2 3<br />
<br />
5 0 0 1 1 1 2 2<br />
<br />
4 0 1 0 0 2 3 2<br />
<br />
5 0 0 1 1 2 1 2<br />
<br />
4 0 1 0 0 2 3 2<br />
<br />
5 0 0 1 1 2 1 3<br />
<br />
5 0 1 0 1 1 3 2<br />
<br />
5 0 1 0 1 1 3 2<br />
<br />
AH- this number works!<br />
<br />
Peter Winkle claims that if you start with any 8 digits number this process will converge to a solution within at most 15 steps. I do not think he proved this. But the key here is that by NOT being clever you can easily find the answer. The problem, as the title of the talk says, solves itself!<br />
<br />
How many such numbers are there? Proving the process works? Getting statistics on how long it will take on average? I leave all of this to the reader. (I do not know the answers.) And one can ask all of this for other bases and other condidtions on the digits (though calling them digits is odd since that smacks of base 10- what to use instead of ``digits'' when in another base?)<br />
<br />
<br />
<br />
<br />
<br />
<br />
<br />
<br />https://blog.computationalcomplexity.org/2018/04/the-8-digit-number-i-asked-for.htmlnoreply@blogger.com (GASARCH)1tag:blogger.com,1999:blog-3722233.post-6882571169428038992Mon, 23 Apr 2018 15:56:00 +00002018-04-23T11:56:45.674-04:00Find an 8-digits number such that ....(June 29th, co-located with STOC, will be a workshop to celebrate Vijay Vazarani's 60th birthday. As computer scientists shouldn't we use 64 as the milestone? See <a href="https://www.cs.umd.edu/users/samir/stoc2018/">here</a> for details about the workshop, not about 60 vs 64.)<br />
<br />
I will likely post a lot about Gathering For Gardner 13, but for now I will just give one problem I saw there. I will not say the speaker or the title of the talk as that might be a clue. I'll give the answer in my next post which will be this week<br />
<br />
<br />
Find an 8-digit number<br />
<br />
d_7 d_6 d_5 d_4 d_3 d_2 d_1 d_0<br />
<br />
such that<br />
<br />
d_0 is the number of 0's in the number<br />
<br />
d_1 is the number of 1's in the number<br />
<br />
d_2 is the number of 2's in the number<br />
<br />
.....<br />
<br />
d_6 is the number of 6's in the number<br />
<br />
but<br />
<br />
d_7 is NOT necc the number of 7's<br />
<br />
d_7 is the number of DISTINCT DIGITS in d_7 d_6 d_5 d_4 d_3 d_2 d_1 d_0<br />
<br />
You could prob find such a number by computer search- but don't.<br />
<br />
Feel free to comment. I will not block comments (except those we usually block- usually spam) but by the same token, if you don't want hints, don't read the comments.<br />
<br />
<br />https://blog.computationalcomplexity.org/2018/04/find-8-digits-number-such-that.htmlnoreply@blogger.com (GASARCH)7tag:blogger.com,1999:blog-3722233.post-1823496575543826252Thu, 19 Apr 2018 11:42:00 +00002018-04-19T07:42:08.214-04:00Memory is Hot<div class="separator" style="clear: both; text-align: center;">
<a href="https://4.bp.blogspot.com/-F8VKllvkIEw/WtZGktrPqgI/AAAAAAABf9g/e8z_dKQ6FFgdDR8lzG612cN1iEPauzW7QCLcBGAs/s1600/cross_point_image_for_photo_capsule.jpg" imageanchor="1" style="clear: left; float: left; margin-bottom: 1em; margin-right: 1em;"><img border="0" data-original-height="690" data-original-width="690" height="200" src="https://4.bp.blogspot.com/-F8VKllvkIEw/WtZGktrPqgI/AAAAAAABf9g/e8z_dKQ6FFgdDR8lzG612cN1iEPauzW7QCLcBGAs/s200/cross_point_image_for_photo_capsule.jpg" width="200" /></a></div>
A good number of the faculty candidates interviewing at Georgia Tech have a common theme: Memory. Memory connected to databases, to programming languages, to architecture, to operating systems, to networks and in security. Why all the interest in memory?<br />
<br />
I started asking the candidates. The short answer: We no longer get faster performance from the CPU but new memory technologies can make a large difference.<br />
<br />
Intel and Micron developed a new memory technology they call 3D XPoint ("3D Cross-Point") as diagrammed above, with the memory, in yellow, addressable by choosing the adjacent horizontal and vertical bars. 3D XPoint gives fully bit addressable high-density high-speed non-volatile memory without transistors or electrons. Non-volatile means the memory does not disappear when the power goes off, like a "flash" drive. Intel has announced a 3D XPoint main memory card under the <a href="https://www.intel.com/content/www/us/en/architecture-and-technology/intel-optane-technology.html">Optane</a> brand available this fall. One could use this memory as a full replacement or in conjunction with traditional DRAM in a heterogeneous system.<br />
<br />
What's the big deal? The non-volatility means we can reduce power needed for memory, power being perhaps the biggest bottleneck in computing today. We can have large-scale databases in memory, fast performance with quick crash recovery since the memory isn't lost. 3D XPoint can enable edge or fog computing that brings the power of the cloud closer to the user for applications like virtual reality or self-driving cars where the time to reach a data center can cause unacceptable lag. Like most transformative technologies it will bring opportunities and challenges we can't even imagine now.<br />
<br />
As theorists we need to take a leading role. How can we model 3D XPoint-like memories so we can properly develop algorithms and analyze complexity to understand what these memories can or cannot enable? Theoretical Computer Science can play a large role in adapting to new technologies if it is willing to get into the game.https://blog.computationalcomplexity.org/2018/04/memory-is-hot.htmlnoreply@blogger.com (Lance Fortnow)4tag:blogger.com,1999:blog-3722233.post-4479577380123454466Mon, 16 Apr 2018 23:03:00 +00002018-04-16T20:53:24.486-04:00Is DTIME(n) closed under concat? star? of course not but...(STOC 2018 will offer child care for the first time. I was emailed the following and asked to<br />
pass it on:<br />
<br />
We are pleased to announce that we will provide pooled, subsidized<br />
child care at STOC 2018. The cost will be $40 per day per child for<br />
regular conference attendees, and $20 per day per child for students.<br />
For more detailed information, including how to register for STOC 2018<br />
childcare, see <a href="http://acm-stoc.org/stoc2018/childcare.html">http://acm-stoc.org/stoc2018/childcare.html</a><br />
<br />
Ilias Diakonikolas and David Kempe (local arrangements chairs)<br />
<br />
I tell my class that poly time is nice mathematically since its closed under lots of operations including<br />
concat and *. That is:<br />
<br />
L<sub>1</sub> , L<sub>2</sub> ∈ P implies L<sub>1</sub> L<sub>2</sub> ∈ P.<br />
<br />
unlike DTIME(n) which, as you can see, is NOT closed under concat! After all, the proof that P is closed under concat uses that if p(n) is a poly then np(n) is a poly which does not hold for linear time. If p(n) is O(n) then np(n) is NOT necc O(n).<br />
<br />
But--- thats not a proof that DTIME(n) is not closed under concat! Thats just the observation that the argument for P being closed under concat does not extend to DTIME(n). Perhaps some other argument does.<br />
<br />
I do not believe that. I believe there exists L<sub>1</sub> , L<sub>2</sub> ∈ DTIME(n) such that L<sub>1</sub> L<sub>2</sub> is not in DTIME(n).<br />
<br />
I have not been able to prove this. In fact, the question I pose is not well defined since I need to specify a machine model.<br />
<br />
I pose the following question which may well be known - if so then please leave a comment:<br />
<br />
Find a reasonable machine model (RAM? k-tape TM?) such that DTIME(n) on that model is NOT closed under concat. (Prob use DTIME(O(n))).<br />
<br />
Similar for *<br />
<br />
These are likely hard questions since if L is in DTIME(n) then L* is in NTIME(n), (similar for concat),<br />
so I would be separating DTIME(n) from NTIME(n), which HAS been done, but not with nice natural problems of the type that I seek.https://blog.computationalcomplexity.org/2018/04/is-dtimen-closed-under-concat-star-of.htmlnoreply@blogger.com (GASARCH)1tag:blogger.com,1999:blog-3722233.post-3285440561988482884Fri, 13 Apr 2018 12:01:00 +00002018-04-13T08:01:01.929-04:00Lance and Bill Gather for GardnerEvery two years in Atlanta, recreational mathematicians gather to honor Martin Gardner, whose Scientific American column Mathematical Games through the 60's and the 70's. Those columns inspired budding mathematicians of a certain age including Bill and I.<br />
<br />
Bill came down to this years <a href="http://www.gathering4gardner.org/g4g13-information/">Gathering for Gardner 13</a>. Talks are only six minutes long. Bill talked on the <a href="https://arxiv.org/abs/1709.02452">Muffin Problem</a> right after an 8-year old and right before Stephan Wolfram.<br />
<br />
We also did a short <a href="https://youtu.be/gZtTeGBlOzU">vidcast</a> from the exhibition room.<br />
<br />
<iframe allow="autoplay; encrypted-media" allowfullscreen="" frameborder="0" height="315" src="https://www.youtube.com/embed/gZtTeGBlOzU" width="560"></iframe>https://blog.computationalcomplexity.org/2018/04/lance-and-bill-gather-for-gardner.htmlnoreply@blogger.com (Lance Fortnow)3tag:blogger.com,1999:blog-3722233.post-4480549433045489957Mon, 09 Apr 2018 05:26:00 +00002018-04-09T20:35:45.602-04:00Whan a deep theorem of your Uncles becomes standard should you be sad?(An exposition of Nash-Williams's proof of the Kruskal Tree Theorem is <a href="https://www.cs.umd.edu/users/gasarch/BLOGPAPERS/ktt.pdf">here</a>)<br />
<br />
Andrew Vazsonyi (the mathematician, see <a href="https://en.wikipedia.org/wiki/Andrew_V%C3%A1zsonyi#cite_note-15">here</a>, not the folklorist, see <a href="https://en.wikipedia.org/wiki/Linda_D%C3%A9gh">here</a> for that folklorist's wife) conjectured that the set of trees, under the minor ordering, is a well quasi order. I do not know when he made the conjecture, but he was born in 1916 and the conjecture was solved in 1960, so you can take a guess based on that. We only know he conjectured it since when Joe Kruskal proved it, he credits Vazsonyi and calls it `Vazonyi's conjecture' I do not know if anyone else ever called it that.<br />
After a conjecture is solved it's usually called by the solvers name, not the poser's name, so it's hard to find out anything about Vazsonyi's conjecture when it was a conjecture.<br />
<br />
Joe Kruskal's proof was quite hard and quite deep (are they necc the same? Prob not). See <a href="http://www.ams.org/journals/tran/1960-095-02/S0002-9947-1960-0111704-1/S0002-9947-1960-0111704-1.pdf">here</a> for that paper. Nash-Williams three years later, in 1963, provided a much easier, though still deep proof. (I could not find a free online copy to point to- if you know of one please email me or comment.) Nash-Williams prove is in my writeup.<br />
<br />
Joe Kruskal is Clyde Kruskal's uncle (Joe is also known in our circles for MST). I told Clyde that I made his Uncle's Theorem a problem on my TAKE HOME midterm in graduate Ramsey Theory. He PONDERED- is it sad that this once great theorem is now merely a problem in a course?<br />
<br />
I asked some random students from both my Ramsey Theory class and my Aut theory class for their take on this. Here are the responses.<br />
<br />
<b>Dolapo</b>: (Aut Student) Clyde should stop worrying about his Uncle's legacy and start building his own!<br />
<br />
<b>Ben: </b> (Ramsey Student) Bill proved in class that SUBSEQUENCE is a wqo. GIVEN that, the problem wasn't that hard. Had he not given it to us the problem would be impossible.<br />
<br />
<b>Clyde: </b>Bill, next time you teach the course give them the problem cold- without any prior theorems about wqo.<br />
<br />
<b>Bill:</b> I'd rather not<br />
<br />
<b>Nishant</b>:(Ramsey Student) Clyde should be happy, and know it, and clap his hands! People are still talking about his Uncle's Theorem!<br />
<br />
<b>Bill</b>: If you're happy and you know it clap your hands! Alice is not clapping here hands. Bob is. What can you deduce about Alice and Bob? Never mind, that will be a different post.<br />
<br />
<b>Bill: </b>If I gave the problem on an i<i>n-class exam</i> in a <i>grad course</i> or a <i>take-home</i> exam in an <i>ugrad</i> course THEN you should be sad. But <i>take-home exam</i> in <i>grad-course</i>. That's just right.<br />
<br />
<b>Ben:</b> (Ramsey Student) When are you going to do a post about this?<br />
<br />
<b>Bill: </b>Since my post will include a pointer to a proof of the Kruskal Tree Theorem, I won't post until after you all hand in your take-home midterms.<br />
<br />
<b>Nishant and Ben together: </b>Darn!<br />
<br />
<b>Joshua (</b>TA for Aut Theory): I heard the grad students complaining about the problem being too hard is a sign of a great mathematician. If your grad students complain then kudos to Joe Kruskal!<br />
<br />
<b>Bill</b>: They Didn't comlain<br />
<br />
<b>Clyde</b>: Darn!<br />
<br />
<b>Ajeet</b> (Ramsey Student) It's much harder to CREATE new math then to LEARN new math. I feel our working out this problem, given what you already gave us, was more a LEARNING thing rather than a CREATE thing. Like P vs NP: easier to verify then generate.<br />
<br />
<b>Katherine</b> (Ramsey Student and Clydes Algorithms TA): A bigger problem for Joe Kruskal's legacy is that people in the algorithms class refer to <i>The Kruskal MST algorithm</i> as <i>Clyde's Algorithm</i>.<br />
<br />
<b>Saddiq </b>(Aut Theory Student) If Clyde can test on Kruskal MST on his final (which he did) then you can test on Krusakl Tree theorem on your midterm (which you did).<br />
<br />
Anyway, one lesson here is that fame is fleeting. Very few people are remembered 100 years after their death. So Clyde - I am helping keep your Uncle's memory alive!<br />
<br />
<b>Clyde: </b>Oh Joy<br />
<br />
SO- what do you think? Should Clyde be happy that his Uncle's theorem is on my take him midterm? Should he know it? Should he clap his hands?<br />
<br />
<br />
<b><br /></b>
https://blog.computationalcomplexity.org/2018/04/whan-deep-theorem-of-your-uncles.htmlnoreply@blogger.com (GASARCH)1tag:blogger.com,1999:blog-3722233.post-3104560555660523151Thu, 05 Apr 2018 14:49:00 +00002018-04-05T10:49:40.477-04:00Challenge about NFA for {a^y : y\ne 1000} answered.<br />
Recall that in a prior post I asked<br />
<br />
Is there an NFA for { a<sup>y</sup> : y ≠ 1000 } with substantially less than 1000 states.<br />
<br />
I will now show that any NFA for this set requires 999 states, so essntially 1000. The proof uses Ramsey Theory. I will tell you the little bit of Ramsey Theory that you need.<br />
<br />
NO- the above is false.<br />
<br />
There is an NFA with 60 states. I have a complete exposition <a href="https://www.cs.umd.edu/users/gasarch/BLOGPAPERS/1000.pdf">here</a> and I have a paper (with coauthors) on cofinite unary languages and NFA's <a href="https://www.cs.umd.edu/users/gasarch/BLOGPAPERS/nfa.pdf">here</a>). Generally if you want to only avoid<br />
a<sup>n</sup> the NFA an be done in sqrt(n) + O(\log n) states, but requires sqrt(n) states.<br />
<br />
I sketch the ideas here for the 1000.<br />
<br />
Convention- `reject 988' would mean rejecting a<sup>988</sup>.<br />
<br />
It is easy show the following:<br />
For all n \ge 992 there exists x,y\in N such that n = 32x +33y<br />
<br />
For all x,y 32x+ 33y is NOT = 991.<br />
<br />
If you have an NFA with a 33-loop and a shortcut so you can also to 32 and back to the start<br />
state, this NFA<br />
<br />
accepts all y ≥ 992<br />
<br />
rejects 991<br />
<br />
we have no comment on anything else.<br />
<br />
So if you prepend 9 states to that NFA you will have an NFA that<br />
<br />
accepts all y ≥ 1001<br />
<br />
rejects 1000<br />
<br />
How to get all the numbers < 1000?<br />
<br />
Use mod 3, mod 5, mod 7, mod 11 loops that only accept if the number is NOT equiv to 1000<br />
mod 3, 5, 7, 11, Since 3*5*7*11 > 1000 we have<br />
<br />
if y is rejected then y ≤ 1000, but y \equiv 1000 mod 3*5*7*11, so must have y=1000.<br />
<br />
so 1000 is the only reject.<br />
<br />
Number of states: 1 + 33 + 3 + 5 + 7 + 11 = 60 states.<br />
<br />
I think you can do this in 58, but what is the BEST you can do?<br />
My paper has lower bounds of sqrt(n) so in this case 32.<br />
<br />
This is a GREAT theorem to teach to students in a course that covers regular langs and also P vs NP since the students THINK that an NFA cannot do better - AH BUT IT CAN! - so it gives a concrete example of<br />
<br />
<i>lower bounds are hard since someone may come along with a very clever trick you didn't think of</i><br />
<i><br /></i>
This semester when I had the class VOTE on whether or not there was a small NFA<br />
<br />
48 thought that ANY NFA would require around 1000 states<br />
<br />
One of the best students proved this! or perhaps ``proved'' this<br />
<br />
Only 2 students knew that it could be done with MUCH LESS than 1000 states- and those two are exceptions- one is co-author on the paper (and he tells me that he originally thought it required 1000 when I first showed him the problem) and one is someone who often goes to my old course websites looking for more information and problems to work on (I like that ambition!) and came across material on this. <br />
<br />
I tell them `you thought this was the last lecture on reg langs. It was not. it was the first lecture on P vs NP'<br />
<br />
<br />
<br />
<br />
<br />
<br />https://blog.computationalcomplexity.org/2018/04/challenge-about-nfa-for-ay-yne-1000.htmlnoreply@blogger.com (GASARCH)5tag:blogger.com,1999:blog-3722233.post-2632797971954315737Tue, 03 Apr 2018 18:00:00 +00002018-04-04T01:25:43.381-04:00Challenge: Is there a small NFA for { a^i : i\ne 1000} ?<br />
(Added later- a reader left a comment pointing to a paper with the answer and saying that the problem is not original. My apologies- upon rereading I can see why one would think I was claiming it was my problem. It is not. I had heard the result was folklore but now I have a source! So I thank the commenter and re-iterate that I am NOT claiming it is my problem.)<br />
<br />
<br />
Consider the language<br />
<br />
{L = a<sup>i </sup> : i ≠ 1000 }<br />
<br />
There is a DFA for L of size 1002 and one can prove that there is no smaller DFA.<br />
<br />
What about an NFA? Either:<br />
<br />
a) Show that any NFA for L requires roughly 1000 states<br />
<br />
or<br />
<br />
b) Show that there is a small NFA for L, say less than 500 states<br />
<br />
or<br />
<br />
c) State that you think the question is unknown to science.<br />
<br />
I will reveal the answer in my next post, though its possible that (c) is the answer and the comments will convert it to either (a) or (b).<br />
<br />
Feel free to leave comments with your answers. if you want to work on it without other information then do not read the comments.<br />
<br />
<br />
<br />
<br />
<br />
<br />https://blog.computationalcomplexity.org/2018/04/challenge-is-there-small-nfa-for-ai-ine.htmlnoreply@blogger.com (GASARCH)3tag:blogger.com,1999:blog-3722233.post-4794823229628622346Thu, 29 Mar 2018 16:42:00 +00002018-04-01T09:07:40.979-04:00Almost Famous Quantum Polynomial TimeI have been playing with a new complexity class AFQP, defined in a yet-to-be-published manuscript by Alagna and Fleming. A language L is in AFQP if there is a polynomial-time quantum Turing machine Q such that for all inputs x,<br />
<div>
<ul>
<li>If x is in L, then Q(x) accepts with high probability.</li>
<li>If x is not in L, then Q(x) rejects with high probability.</li>
<li>Q(x) only has O(log |x|) quantumly entangled bits as well as a polynomial amount of "deterministic" memory. </li>
</ul>
<div>
AFQP is meant to capture the state of the art of current quantum technology.<br />
<br /></div>
</div>
<div>
AFQP has several nice properties, capturing the complexity of many open problems.</div>
<div>
<ol>
<li>If BQP is in AFQP then factoring is in BPP.</li>
<li>If one can solve satisfiability in AFQP then the polynomial-time hierarchy collapses.</li>
<li>AFQP is contained in the fifth level of the polynomial-time hierarchy.</li>
<li>If AFQP is in log-space then matching has a deterministic NC algorithm.</li>
<li>Graph isomorphism is in a quasi-polynomial time version of AFQP.</li>
<li>AFQP = PPAD iff Nash Equilibrium has solutions we can find in polynomial time.</li>
</ol>
<div>
The proofs use a clever combination of Fourier analysis and semidefinite programming. </div>
</div>
<div>
<br /></div>
<div>
Where does the name AFQP come from? The authors claim that they didn't name the class after themselves, and instead say it stands for "Almost Famous Quantum Polynomial Time" as it won't get the fame of BQP. More likely it is because it's April the first and I'm feeling a bit Foolish making up a new complexity class that is just P in disguise. </div>
https://blog.computationalcomplexity.org/2018/03/almost-famous-quantum-polynomial-time.htmlnoreply@blogger.com (Lance Fortnow)3