tag:blogger.com,1999:blog-37222332015-09-01T10:34:16.031-05:00Computational ComplexityComputational Complexity and other fun stuff in math and computer science from Lance Fortnow and Bill GasarchLance Fortnowhttps://plus.google.com/101693130490639305932noreply@blogger.comBlogger2306125tag:blogger.com,1999:blog-3722233.post-80331204329023926182015-08-30T22:26:00.001-05:002015-09-01T10:31:35.712-05:00Two candidates that I want to see run for Democratic NominationIt has been noted that while there are 17 Republican candidates for the nomination, of which 10 have been declared serious by FOX News via the first debate, there are far less democratic candidates for the nomination and only one has been declared serious by the powers that be. This may change if Biden runs. <br />
<br />
I want to suggest two Democrats who I think should run. They have not made ANY moves in that direction, so it won't happen... until they see that this blog post endorsing them and they get inspired!<br />
<br />
<b>Rush Holt</b>. Was a US Congressman from NJ (NOTE- earlier version of this post incorrectly had him as a US Senator from WV which his father was. Thanks to Dave MB comment for pointing that out.) He has a PhD in Physics. I want a president who wins a Nobel Prize in something OTHER THAN Peace (T. Roosevelt, Wilson, Carter, Obama have won it for peace, fictional Bartlett on West Wing won if for Economics). I can imagine one winning for Literature. But Physics- that would be awesome! While I doubt Dr. Holt will win one, it would be good to have someone as Prez who knows SOME science so he won't say stupid things about global warning. (Counter question- do the climate change deniers in the Senate really believe what they are saying or not?) He's also a Quaker, not sure how that plays into all of this. (I had a longer and incorrect passage here, but thanks to Andy P's comment below I changed it and it is now correct--- I hope.)<br />
<br />
Would having a scientist in the Whitehouse be good for Science Funding? I would guess a marginal yes. Would it improve my chance of getting my REU grant renewed? I would guess no.<br />
<br />
<b>Sheldon Whitehouse</b>. US Senator from Rhode Island. Look at his name- he was born to be Prez!<br />
<br />
You may think these are stupid criteria. You may be right. But is it any better than I voted for X in the primary since X has a better chance of winning in the general (One of Clinton's arguments against Obama in 2008 was that Obama couldn't win since... well, you know) or he looks just like a prez (Warren Harding's main qualification) or he's Rich and obnoxious (I would say who I am thinking of, but he's been known to sue people).GASARCHhttp://www.blogger.com/profile/06134382469361359081noreply@blogger.com6tag:blogger.com,1999:blog-3722233.post-62725569789020590432015-08-27T07:01:00.000-05:002015-08-27T07:01:36.112-05:00PACMI serve on the conference committee of the ACM publications board and we've had extensive discussions on the question of the role of journals in publication venues. A number of CS conferences, though notably not in TCS, are moving to a hybrid publication model where their conference presentations make their way into refereed journal papers. One of our proposals is the creating of a specific venue for these activities, a new Proceedings of the ACM. In the September CACM, Joseph Konstan and Jack Davidson <a href="http://cacm.acm.org/magazines/2015/9/191173-should-conferences-meet-journals-and-where/fulltext">lay out this proposal</a>, with <a href="http://cacm.acm.org/magazines/2015/9/191177-the-pros-and-cons-of-the-pacm-proposal/fulltext">pros</a> and <a href="http://cacm.acm.org/magazines/2015/9/191179-the-pros-and-cons-of-the-pacm-proposal/fulltext">cons</a> by Kathryn McKinley and David Rosenblum respectively. The community (that means you) is being asked to <a href="https://www.surveymonkey.com/r/PACM2015">give their input</a>.<br />
<br />
The theory model has not significantly changed since I was a student. Papers submitted to a conference get reviewed but not refereed, the proofs read over usually just enough to feel confident that the theorem is likely correct. Once authors started submitting electronically they could submit entire proofs, though often in an appendix the program committee is not required to read.<br />
<br />
The papers appear in a proceedings and to quote from the STOC proceedings preface<br />
<blockquote class="tr_bq">
The submissions were not refereed, and many of these papers represent reports of continuing research. It is expected that most of them will appear in a more polished and complete form in scientific journals.</blockquote>
A small select number of papers from a conference are invited to a special issue of a journal where they do go through the full referee process. Some, but not most, of the other papers get submitted to journals directly. We don't have the proper incentives for authors to produce a journal version with full and complete proofs.<br />
<br />
Should theory conferences move towards a more hybrid or PACM type of model? I'd had several debates with my fellow theorists many of whom feel the advantages of requiring journal-level papers get outweighed by the extra effort and time required by the authors and the reviewers.Lance Fortnowhttps://plus.google.com/101693130490639305932noreply@blogger.com8tag:blogger.com,1999:blog-3722233.post-61169467101637407312015-08-23T21:38:00.001-05:002015-08-23T21:38:42.504-05:00Interesting properties of the number 24 on someone's 24th wedding anniversary<br />
The story you are about to read is true. Only the names have been changed to protect the innocent. The Alice and Bob below are not the crypto Alice and Bob.<br />
<br />
------------------------------------------------------<br />
BOB (to ALICE): Its our 24th anniversary! Last year when it was our 23rd anniversary we celebrated by having you tell me that 23 was the ONLY number that required 9 cubes so sum to it, and that its open how many cubes you need for large n, though its between 4 and 7. Oh that was fun! What do you have planned for our 24th anniversary!<br />
<br />
ALICE (to BOB): I've prepared FIVE facts about 24! Oh, I mean 24, not 24 factorial! We'll see which one you want to discuss. Here they are:<br />
<br />
1) 24 is the largest nat number n such that all nat numbers m ≤ sqrt;(n) m divides n.<br />
<br />
2) 24 is the least nat number that has exactly 8 distinct factors. (1,2,3,4,6,8,12,24)<br />
<br />
3) 24 is the ONLY number m≥2 such that 1^2 + 2^2 + ... + m^2 is a square. Its 70^2, so if we are married 70 years, I'll have an interesting fact about 24.<br />
<br />
4) Let S be an n-sphere. How many spheres of the same size as S can kiss S? Thats the kissing number, called kiss(n). kiss(2)=6 (so given a circle you can position 6 identical circles that kiss it), kiss(3)=12 (thats 3-dim), and kiss(4)=24.<br />
<br />
5) Its one of the few numbers that is the title of a TV show. <br />
<br />
BOB: Since its our anniversary I'll go with the kissing number~ Mathematically I'd go with the square thing.<br />
---------------------------------------------------<br />
<br />
I am sure that for all numbers ≤ 94 one can come up with some facts of interest. The book <a href="http://www.amazon.com/dp/0821848070/?tag=googhydr-20&hvadid=40073556007&hvpos=1t1&hvexid=&hvnetw=g&hvrand=7999853277492080378&hvpone=42.02&hvptwo=&hvqmt=b&hvdev=c&ref=pd_sl_1jc6z4vgp3_b">Those Fascinating Number</a> has an interesting fact about many numbers. The least number that it has no interesting fact about is 95, but I suspect Alice and Bob won't be married that long.<br />
<br />
What are the coolest numbers (mathematically)? See <a href="http://planetmath.org/toptencoolestnumbers">here</a> for a possible answer. <br />
<br />
<a href="http://www.amazon.com/dp/0821848070/?tag=googhydr-20&hvadid=40073556007&hvpos=1t1&hvexid=&hvnetw=g&hvrand=7999853277492080378&hvpone=42.02&hvptwo=&hvqmt=b&hvdev=c&ref=pd_sl_1jc6z4vgp3_b"><br /></a>GASARCHhttp://www.blogger.com/profile/06134382469361359081noreply@blogger.com8tag:blogger.com,1999:blog-3722233.post-23815917590784444672015-08-20T07:18:00.001-05:002015-08-20T07:18:43.625-05:00Crowdsourcing the TruthA new project <a href="http://www.augur.net/">Augur</a> aims to create a decentralized prediction market. If this post so moves you, Augur is in the midst of a <a href="https://sale.augur.net/">reputation sale</a>. Don't miss out if you would like to be an Augur reporter.<br />
<br />
A prediction market takes a future event, such as Hillary Clinton winning the 2016 Presidential Election, and creates a security that pays off $100 if Hillary wins and $0 otherwise. The market allow buying, selling and short selling the security and the price of the security represents that probability the event will happen. <a href="http://www.predictwise.com/">Predictwise</a>, which aggregates prediction markets, has the <a href="http://www.predictwise.com/politics/2016president">probability of Hillary winning</a> at 47% as I write this. But there are a limited amount of markets out there for Predictwise to draw from.<br />
<br />
Intrade, which <a href="http://blog.computationalcomplexity.org/2013/03/goodbye-old-friends.html">shut down</a> due to financial improprieties in 2013, used to run markets on all aspects of elections and other current events. Many other prediction markets have disappeared over time. The Augur team put out a <a href="http://augur.link/augur.pdf">white paper</a> describing their fully decentralized prediction market immune to individuals bringing it down. They build on cryptocurrencies for buying and selling and a group of "reporters" financially incentivized to announce the correct answer for each market.<br />
<br />
It's that last part I find the most interesting, instead of having an authority that reports the results, Augur will crowdsource the truth.<br />
<blockquote class="tr_bq">
A key feature of Augur is tradeable Reputation. The total amount of Reputation is a fixed quantity, determined upon the launch of Augur. Holding Reputation entitles its owner to report on the outcomes of events, after the events occur...Reputation tokens are gained and lost depending on how reliably their owner votes with the consensus.</blockquote>
Consensus may not be "the truth". Reporters are not incentivized to report the truth but what the other reporters will report as the consensus. Those who buy and sell on the market are not betting on the truth but the outcome as it is decided by the consensus of reporters. We have an ungrounded market.<br />
<br />
The purchasers of reputation tokens likely won't represent the public at large and biases may come to play. Would this consensus have agreed that Bush won the 2000 election?<br />
<br />
What would have the consensus done on the <a href="https://en.wikipedia.org/w/index.php?title=Intrade&oldid=651267155#Disputes">North Korea controversy</a>?<br />
<blockquote class="tr_bq">
[The Intrade security] allowed speculation on whether North Korea would, by 31 July 2006, successfully fire ballistic missiles that would land outside its airspace. On 5 July 2006 the North Korean government claimed a successful test launch that would have satisfied the prediction, a launch widely reported by world media. [Intrade] declared that the contract's conditions had not been met, because the US Department of Defense had not confirmed the action, and this confirmation was specifically required by the contract. (Other government sources had confirmed the claim, but these were not the sources referenced in the contract.) Traders considered this to be in strict compliance with the stated rule but contrary to the intention of the market (which was to predict the launch event, and not whether the US Defense Department would confirm it).</blockquote>
Since Augur will allow arbitrarily worded contracts on topics such as proofs of P v NP, the consensus reporting may lead to some interesting future blog posts.<br />
<br />
Despite my reservations, I'm quite excited to see Augur set up a prediction market system that can't be shut down and wish them all the luck. You have to until October 1 to <a href="https://sale.augur.net/">buy reputation</a> if you want to be deciding the truth instead of just predicting it.Lance Fortnowhttps://plus.google.com/101693130490639305932noreply@blogger.com2tag:blogger.com,1999:blog-3722233.post-3679392301978059012015-08-16T21:39:00.001-05:002015-08-16T21:39:31.599-05:00Have we made Progress on P vs NP?While teaching P vs NP in my class Elementary Theory of Computation (Finite Automata, CFG's, P-NP, Dec-undecid) I was asked <i>What progress has been made on P vs NP?</i><br />
<br />
I have heard respectable theorists answer this question in several ways:<br />
<br />
1) There has been no progress whatsoever- but the problem is only 40 years old, a drop in the mathematical bucket sort.<br />
<br />
2) There has been no progress whatsoever- this is terrible since 40 years of 20th and 21st century mathematics is a lot and we already had so much to draw on. We are for the long haul.<br />
<br />
3) We have made progress on showing some techniques will not suffice, which is progress--- of a sort.<br />
<br />
4) We have made progress on showing P=NP: Barringtons result, FPT, Holographic algorithms, SAT in PCP with O(1) queries. Too bad- since P NE NP we've made no progress.<br />
<br />
5) We have made progress on showing P=NP: Barringtons result, FPT, Holographic algorithms, SAT in PCP with O(1) queries. We should not be closed minded to the possibliity that P=NP. (NOTE- other theorists say YES WE SHOULD BE CLOSED MINDED.)<br />
<br />
6) Note that:<br />
<br />
a) We have pathetic lower bounds on real models of computation.<br />
<br />
b) We have Meaningful lower bounds on pathetic models of computation.<br />
<br />
c) We DO NOT have meaningful lower bounds on real models of computation.<br />
<br />
7) Have we made progress? Once the problem is solved we'll be able to look back and say what was progress.<br />
<br />
I told the students my view: <i>We have made progress on showing some techniques will not suffice, which is progress--- of a sort</i> which my class found funny. Then again, students find the fact that there are sets that are undecidable, and sets even harder than that! to be funny too.GASARCHhttp://www.blogger.com/profile/06134382469361359081noreply@blogger.com8tag:blogger.com,1999:blog-3722233.post-7319871520105756442015-08-13T07:45:00.003-05:002015-08-13T07:45:44.367-05:00What is Theoretical Computer Science?Moshe Vardi asks a provocative question in <a href="http://windowsontheory.org/2015/06/09/why-doesnt-acm-have-a-sig-for-theoretical-computer-science-guest-post-by-moshe-vardi/">Windows on Theory</a> and <a href="http://cacm.acm.org/magazines/2015/8/189832-why-doesnt-acm-have-a-sig-for-theoretical-computer-science/fulltext">CACM</a>: "Why doesn't ACM have a SIG for Theoretical Computer Science?" The reaction of myself and many of my fellow Americans is the question has a false premise. <a href="http://www.sigact.org/">SIGACT</a>, the ACM special interest group for algorithms and computation theory, plays this role as stated in its mission:<br />
<blockquote class="tr_bq">
SIGACT is an international organization that fosters and promotes the discovery and dissemination of high quality research in theoretical computer science (TCS), the formal analysis of efficient computation and computational processes. TCS covers a wide variety of topics including algorithms, data structures, computational complexity, parallel and distributed computation, probabilistic computation, quantum computation, automata theory, information theory, cryptography, program semantics and verification, machine learning, computational biology, computational economics, computational geometry, and computational number theory and algebra. Work in this field is often distinguished by its emphasis on mathematical technique and rigor.</blockquote>
Theoretical computer science in Europe has a much different balance, putting as much or even more emphasis on automata and logic as it does on algorithms and complexity. So from that point of view (a view shared by Moshe who has strong ties to CS logic) SIGACT does not cover the full range of TCS.<br />
<br />
The term "theoretical computer science" just doesn't have a universal meaning. Neither definition is right or wrong, though we all have our biases.<br />
<br />
Why does TCS have such a different meaning in Europe and the US? A different research culture and relatively little mixing. Very few North Americans go to grad school, take postdocs or faculty positions in Europe and very few Europeans go the other way, and those that did tended to do algorithms and complexity. Until we started to see web-based archives in the mid 90's, distribution of research between the Europe and US went quite slowly. Things have changed since but by then the different notions of TCS have been set.<br />
<br />
SIGACT fully acknowledges that it doesn't do a good job covering the logic community and it has always strongly supported <a href="http://siglog.hosting.acm.org/">SIGLOG</a>, the special interest group for logic and computation.<br />
I would love to see joint events between SIGACT and SIGLOG. LICS should be part of FCRC with STOC and Complexity or hold a co-located meeting in other years. But SIGACT does do a great job representing the theoretical computer science community in North America.Lance Fortnowhttps://plus.google.com/101693130490639305932noreply@blogger.com8tag:blogger.com,1999:blog-3722233.post-16836630899097143802015-08-10T12:29:00.003-05:002015-08-10T12:29:31.978-05:00Ways to deal with the growing number of CS majors.(Univ of MD at College Park is looking to hire a Comp Sci Lecturer. Here is the link: <a href="http://www.cs.umd.edu/job/2015/lecturer-computer-science">HERE)</a><br />
<br />
<br />Univ of MD at College Park will have 2100 students in the CS program next year. Thats... a lot! CS is up across the country which is mostly a good thing but does raise some logistical questions. How are your schools handling the increase in the number of CS students? Here are some options I've heard people use:<br /><br />1) Hiring adjuncts who come in, teach a course, and leave is good economically (they don't get paid much) but bad for the long term. Better to have people that are integrated into the dept (lectures are, see next point). Also, CS is a changing field so you can't just give someone some notes and slides and say TEACH THIS. For Calculus you probably can, and they can even do a good job. Calculus doesn't change as fast, or maybe even at all. I envy my friends in math departments who can count<br />on a stable first year course that everyone in the dept can teach. They envy CS profs who have the freedom to have diff versions of CS1 in diff schools. Even in diff semesters!<br /><br />2) Hiring lecturers who are full time and have a high teaching load is good in terms of them being fully integrated into the dept and being involved with course syllabus changes. Also, if they stay long term there is stability. If the first year courses are only taught by lecturers this may be bad abstractly as profs should be in touch with all levels of the dept. I once tried to make this <br />point over lunch at a Dagstuhl meeting and before I could even finish my point they shouted me down and asked if I wanted to teach Intro Programming. I do not, so I'll just shut up now.<br /><br />3) Don't let profs buy out. I've heard of this at some schools as a way to at least have the profs that are there teaching. Alternatively only let profs buy out of grad courses. I don't know if either is a good idea. For one thing, the money use to buy out can be used to hire someone else. But that goes back to point 1- not really good to have part timers. If other profs teach overloads with the money that sounds okay. If half of the profs are paying the other half to teach for them, that sounds odd, but I'm not sure its bad. Also, it would never get that extreme.<br /><br />4) Postdocs sometimes teach a course for extra money. This is good for them for teaching experience and resume, and if they are teaching a course with someone else this can work well. However, if a postdocs point is to get more research done, this will of course cut into that.<br /><br />5) Grad students sometimes teach a course. I knew a grad student in math who was teachng the junior-course in number theory. I asked her if this was an honor or exploitation. She just said YES.<br /><br />6) Increase class size. Going from lecturing to 80 to lecturing to 300 might be okay, though (a) you NEED to use powerpoint or similar and have resources on the web, maybe also Piazza, and (b) you NEED to have LOTS of recitations so they at least are small and (c) you NEED to havehigh quality TAs for the recitations. In some schools its even a problem getting ROOMS of that size!<br /><br />7) HIRE MORE PROFS! Profs have lower teaching loads than lecturers and in CS its harder to teach outside of your area then in (say) Math. (How is it for other fields? If you know, please comment.) Should you hire based on research needs or teaching needs? If a recursive model theorists can teach graphics, that might be a real win if you NEED research in recursive model theory but also<br />NEED someone to teach graphics.<br /><br />8) Not a suggestion but a thought- IF many of the new majors aren't very good then many might flunk out of the major in the first year so this is not a problem for Sophmore, Junior, Senior courses. At least at UMPC this does NOT seem to be the case. To rephrase: many of the new majors are good and do not flunk out. I call that good news! But what about at your school?<br /><br />9) What does your school do? Does it work?<br /><br />
<br />GASARCHhttp://www.blogger.com/profile/06134382469361359081noreply@blogger.com4tag:blogger.com,1999:blog-3722233.post-14425029598256756432015-08-06T06:56:00.000-05:002015-08-06T06:56:00.431-05:00How hard would this cipher be for Eve to crack?I've been looking at old ciphers since I am teaching a HS course on Crypto. We've done shift, affine, matrix, Playfair, 1-time pad, Vigenere, and then noting that in all of the above Alice and Bob need to meet, we did Diffie-Hellman.<br />
<br />
The <a href="https://en.wikipedia.org/wiki/Playfair_cipher">Playfair Cipher</a> cipher is interesting in that it gives a compact way to obtain a mapping from pairs of letters to pairs of letters that (informally) LOOKS random. Of course NOW it would not be hard for Alice and Bob to AGREE on a random mapping of {a,b,...,z}^2 to{a,b,c,...,z}^2 and use that. For that matter, Alice and Bob could agree on a random mapping from {a,b,c,...,z}^k to {a,b,c,...,z}^k for some reasonable values of k.<br />
<br />
So consider the following cipher with parameter k: Alice and Bob generate a RANDOM 1-1, onto mapping of {a,...,z}^k to {a,...,z}^k. To send a message Alice breaks it into blocks of k and encodes each block using the mapping they agree on.<br />
<br />
Question One: How big does k have to be before this is impractical for Alice and Bob?<br />
<br />
Question two: If k=1 then Eve can easily break this with Freq analysis of single letters. For k=2 Eve can easily break this with Freq analysis of digraphs (pairs of letters). Is there a value of k such that the distribution of k-grams is not useful anymore? As k goes up does it get easier or harder to crack? I originally thought harder which is why i thought this would be a good code, but frankly I don't really know.Looking over the web it is EASY to find freq of letters and digraphs, but very hard to find any source for freq of (say) 10-grams. So at the very least Eve would need to build up her own statistics--- but of course she could do this.<br />
<br />
SO, here is the question: Is there a value of k such this code is easy for Alice and Bob but Hard for Eve TODAY? How about X years ago?<br />
<br />
<br />GASARCHhttp://www.blogger.com/profile/06134382469361359081noreply@blogger.com3tag:blogger.com,1999:blog-3722233.post-5655240575934015352015-08-02T16:14:00.000-05:002015-08-02T16:14:28.643-05:0017 candidates, only 10 in the debate- what to do?<br />On Thursday Aug 6 there will be Republican debate among 10 of the 17 (yes 17) candidates for the republican nomination.<br /><br />1) There are 17 candidates. Here is how I remember them: I think of the map of the US and go down the east coast, then over to Texas then up. That only works for the candidates that are or were Senators or Govenors. I THEN listthe outsiders. Hence my order is (listing their last job in government) George Pataki (Gov-NY), Chris Christie (Gov-NY), Rick Santorum (Sen-PA), Rand Paul(Sen KT),JimGilmore(Gov-VA), Lindsay Graham (Sen-SC),Jeb Bush (Gov-FL), Marco Rubio (Sen-FL), Bobby Jindal (Gov-LA), Ted Cruz (Sen-TX), Rick Perry (Gov-TX), Mike Huckabee (Gov-AK), Scott Walker (Gov-Wisc), John Kaisch (Gov-Ohio) Donald Trump (Businessman), Ben Carson (Neurosurgeon), Carly Fiorina (Businesswomen).<br />9 Govs, 5 Sens, 3 outsiders.<br /><br />2) Having a debate with 17 candidates would be insane. Hence they decided a while back to have the main debate with the top 10 in the average of 5 polls, and also have a debate with everyone else. There are several problems with this: (a) candidates hovering around slots 9,10,11,12 are closer together than the margin of error, (b) the polls are supposed to measure what the public wants, not dictate things, (c) the polls were likely supposd to determine who the serious candidates are, but note that Trump is leading the polls, so thats not quite right.QUESTION: Lets say that Chris Christie is at 2% with a margin of + or - 3%. Could he really be a -1%?<br /><br />3) A better idea might be to RANDOMLY partition the field into two groups, one of size 8 and one of size 9, and have two debates that way.What randomizer would they use? This is small enough they really could just put slips of paper in a hat and draw them. If they had many more candidates we might use Nisan-Wigderson.<br /><br />4) How did they end up with 17 candidates?<br /><br />a) Being a Candidate is not a well defined notion. What is the criteria to be a candidate? Could Lance Fortnow declare that he is a candidate for the Republian Nomination (or for that matter the Democratic nomination). YES. He's even written some papers on Economics so I'dvote for him over... actually, any of the 17. RUN LANCE RUN! So ANYONE who wants to run can! And they Do! I'm not sure what they can do about this---it would be hard to define ``serious candidate'' rigorously.<br />
<br />b) The debate is in August but the Iowa Caucus isn't until Feb 1. So why have the debate now? I speculate that they wanted to thin out the field early, but this has the opposite effect--- LOTS of candidates now want to get into the debates.<br /><br />c) (I've heard this) Campaign Finance laws have been gutted by the Supreme court, so if you just have ONE mega-wealthy donor you have enough money to run. Or you can fund yourself (NOTE- while Trump could fund himself, sofar he hasn't had to as the media is covering him so much).<br /><br />d) Because there are so many, and no dominating front runner, they all think they have a shot at it. So nobody is dropping out. Having a lot of people running makes more people want to run. (All the cool kids are doing it!)<br /><br />
<br />GASARCHhttp://www.blogger.com/profile/06134382469361359081noreply@blogger.com2tag:blogger.com,1999:blog-3722233.post-49108312608882674182015-07-28T22:44:00.000-05:002015-07-28T22:44:14.763-05:00Explain this Scenario in Jeapardy and some more thoughts<br />
In the last post I had the following scenario:<br />
<br />
Larry, Moe, and Curly are on Jeopardy.<br />
<br />
Going into Final Jeopardy:<br />
<br />
Larry has $50,000, Moe has $10,000, Curly has $10,000<br />
<br />
Larry bets $29,999, Moe bets $10,000, Curly bets $10,000<br />
<br />
These
bets are ALL RATIONAL and ALL MATTER independent of what the category
is. For example, these bets make sense whether the category is THE THREE
STOOGES or CIRCUIT LOWER BOUNDS.<br />
<br />
Explain why this is.<br />
<br />
EXPLANATION: You were probably thinking of ordinary Jeopardy where the winner gets whatever he gets, and the losers take-home is based ONLY on their rank (2000 for second place, 1000 for first place). Hence Larry's bet seems risky since he may lose 29,999 and Moe and Curly's bets seem irrelevant (or barely relelvent- they both want to finish in second)<br />
<br />
BUT- these are Larry, Moe, Curly, The Three Stooges. This is CELEBRITY JEOPARDY! The rules for money are different. First place gets MAX of what he wins, and 50,000. So Larry has NOTHING TO LOSE by betting 29,999. Second and Third place BOTH get MAX of what they win and 10,000. So Moe and Curly have NOTHING TO LOSE by betting 10,000. (I suspect they do this because the money goes to a charity chosen by the celebrity).<br />
<br />
SIDE NOTE: I saw Celebrity Jeopardy and wanted to verify the above before posting. So I looked on the web for the rules for Celebrity Jeopardy. THEY WERE NO WHERE TO BE FOUND! A friend of mine finally found a very brief you-tube clip of Penn Jillette wining Celeb Jeopardy and a VERY BRIEF look at the final scores and how much money everyone actually got. Thats how I verified what I thought were the rules for celebrity jeopardy.<br />
<br />
IF I am looking up a theorem in Recursive Ramsey theory and can't find it on the web I am NOT surprised at all since that would be somewhat obscure (9 times out of 10 when I look up something in Ramsey Theory it points to one of the Ramsey Theory Websites that I maintain. Usually is there!). But the rules for final Jeopardy -- I would think that is not so obscure. Rather surprised it was not on the web.<br />
<br />GASARCHhttp://www.blogger.com/profile/06134382469361359081noreply@blogger.com4tag:blogger.com,1999:blog-3722233.post-63272778190579095382015-07-27T17:22:00.001-05:002015-07-27T21:33:05.534-05:00Explain this Scenario on Jeopardy<br />
Ponder the following:<br />
<br />
Larry, Moe, and Curly are on Jeopardy.<br />
<br />
Going into Final Jeopardy:<br />
<br />
Larry has $50,000, Moe has $10,000, Curly has $10,000<br />
<br />
Larry bets $29,999, Moe bets $10,000, Curly bets $10,000<br />
<br />
These bets are ALL RATIONAL and ALL MATTER independent of what the category is. For example, these bets make sense whether the category is THE THREE STOOGES or CIRCUIT LOWER BOUNDS.<br />
<br />
Explain why this is.<br />
<br />
I'll answer in my next post or in the comments of this one<br />
depending on... not sure what it depends on.<br />
<br />GASARCHhttp://www.blogger.com/profile/06134382469361359081noreply@blogger.com6tag:blogger.com,1999:blog-3722233.post-59730966078017412172015-07-23T08:07:00.000-05:002015-07-23T13:12:48.644-05:00New Proof of the Isolation LemmaThe isolation lemma of <a href="http://dx.doi.org/10.1007/BF02579206">Mulmuley, Vazirani and Vazirani</a> says that if we take random weights for elements in a set system, with high probability there will be a unique set of minimum weight. Mulmuley et al. use the isolation lemma to randomly reduce matching to computing the determinant. The isolation lemma also gives an alternative proof to <a href="http://blog.computationalcomplexity.org/2006/09/favorite-theorems-unique-witnesses.html">Valiant-Vazirani</a> that show how to randomly reduce NP-complete problems to ones with a unique solution.<br>
<br>
Noam Ta-Shma, an Israeli high school student (and son of Amnon), recently <a href="http://eccc.hpi-web.de/report/2015/080/">posted</a> a new proof of the isolation lemma. The MVV proof is not particularly complicated but it does require feeling very comfortable with independent random variables. Ta-Shma's proof is a more straight-forward combinatorial argument.<br>
<br>
Suppose you have a set system over a universe of n elements. Give each element i, a weight w<sub>i</sub> uniformly chosen between 1 and m. The weight of a set is the sum of the weights of the elements of that set. Ta-Shma shows that there is a unique minimum weighted set with probability at least (1-1/m)<sup>n</sup>, which beats out the bound of (1-n/m) given by MVV.<br>
<br>
Here is a sketch of his proof: Suppose all the w<sub>i</sub>'s had weights between 2 and m. Let S be the lexicographically minimal weight set given these weights. Consider the function φ(w), defined on weights with all the w<sub>i</sub> at least 2, as the following:<br>
<ul>
<li>φ(w)<sub>i</sub> = w<sub>i</sub> -1 if i is in S</li>
<li>φ(w)<sub>i</sub> = w<sub>i</sub> if i is not in S</li>
</ul>
<div>
Note that S is the unique minimal set now in the weights φ(w)<sub>i</sub>. Moreover φ is 1-1 for we can recover w from φ(w) by taking the unique minimal weight set in φ(w) and adding one to the weight of each element in that set.</div>
<div>
<br></div>
<div>
So we have the probability that random weights yield a unique minimum set is at least<br>
<div style="text-align: center;">
|range(φ)|/m<sup>n</sup> = |domain(φ)|/m<sup>n</sup> = (m-1)<sup>n</sup>/m<sup>n</sup> = (1-1/m)<sup>n</sup>.</div>
</div>
<div style="text-align: left;">
<br></div>
<div style="text-align: left;">
Read all the details in Ta-Shma's <a href="http://eccc.hpi-web.de/report/2015/080/">paper</a>.</div>
Lance Fortnowhttps://plus.google.com/101693130490639305932noreply@blogger.com2tag:blogger.com,1999:blog-3722233.post-26015464353910003172015-07-21T12:53:00.000-05:002015-07-22T16:13:26.525-05:00Hartley Rogers, Author of the first Textbook on Recursion Theory, passes awayHartley Rogers Jr passed away on July 17, 2015 (last week Friday as I write this).He was 89 and passed peacefully.<br />
<br />
For our community Rogers is probably best known for his textbook on Recursion Theory which I discuss below. He did many other things, for which I refer you to<br />
his Wikipedia page <a href="https://en.wikipedia.org/wiki/Hartley_Rogers,_Jr.">here</a>.<br />
<br />
His book was:<br />
<br />
<b>The theory of recursive functions and effective computability.</b><br />
<br />
It was first published in 1967 but a paperback version came out in 1987.<br />
<br />
It was probably the first textbook in recursion theory. It was fairly broad. Here are the chapter headings and some comments.<br />
Recursive functions<br />
<br />
Unsolvable problems (The first edition came out before Hilbert's tenth problem was solved),<br />
<br />
Purpose: Summary,<br />
<br />
Recursive invariants, <br />
<br />
Recursive and recursively enumerable sets,<br />
<br />
Reducibilities,<br />
<br />
One-One Reducibilities; Many-one Reducibilities, (Maybe its just me but I can't imagine caring if the reduction is 1-1 or m-1.)<br />
<br />
Truth-Table Reducibilities;simple sets, (``simple sets are not simple'' was a quote from Herbert Gelernter who taught me my first course in recursion theory.)<br />
<br />
Turing Reducibilities; hypersimple sets,<br />
<br />
Post's Problem; incomplete sets. (Posts problem was to find an r.e. set that is neither recursive nor Turing-complete. when I tell people there such a set they they often say `Oh, Like Ladner's Theorem.' Thats true but backwards. Its still open to find a NATURAL set that is incomplete, though they prob don't exist and its hard to pin that down.)<br />
<br />
The Recursion Theorem, <br />
<br />
Recursively enumerable sets as a lattice,<br />
<br />
Degrees of unsolvability,<br />
<br />
The Arithmetic Hierarchy (Part 1),<br />
<br />
The Arithmetic Hierarchy (Part 2),<br />
<br />
The Analytic Hierarchy.<br />
<br />
Looking over his book I notice the following<br />
<br />
1) He thanks Noam Chomsky (a linguist) and Burton Dreben (A philosopher). I think we are more specialized now. Would it be surprising if a text in recursion theory written now thanked people who are not in math?<br />
<br />
2) He thanks his typist. I think that people who write math books now type it themselves. I wonder if novelists also now type it themselves.<br />
<br />
3) I think that Soare's book replaced it as THE book that young recursion theorists read. (Are there young recursion theorists?) Soare's book is chiefly on r.e. degree theory, Rogers book is broader. When Rogers wrote his book much less was known (no 0'''-arguments, very little on random sets). It was possible to have most of what was known in one book. That would be hard now, though Odilfreddi book comes close. Note that Odilfreddi book is in two volumes with a third one to be finished... probably never.<br />
<br />
<br />
<br />
<br />
<br />
One personal note- I had a course on Recursion theory taught by Herbert Gelernter at Stonybrook (my ugrad school) in the Fall of 1979. We covered the first six chapters of Rogers text. It was a great course from a great book taught by a great teacher and set me on the path to do work in recursion-theoretic complexity theory. GASARCHhttp://www.blogger.com/profile/06134382469361359081noreply@blogger.com3tag:blogger.com,1999:blog-3722233.post-6976292263687740022015-07-16T07:40:00.000-05:002015-07-16T07:40:40.359-05:00Microsoft Faculty SummitLast week I participated in my first <a href="http://research.microsoft.com/en-us/um/redmond/events/fs2015/default.aspx">Microsoft Faculty Summit</a>, an annual soiree where Microsoft brings about a hundred faculty to Redmond to see the latest in Microsoft Research. I love these kinds of meetings because I enjoy getting the chance to talk to computer scientists across the broad spectrum of research. Unlike other field, CS hasn't had a true annual meeting since the 80's so it takes events like this to bring subareas together. "Unlike other fields" is an expression we say far too often in computer science.<br />
<br />
This was the first summit since the closing of the Silicon Valley lab and the reorganization of MSR into NExT (New Experiences and Technologies) led by Peter Lee and MSR Labs led by Jeannette Wing. Labs focusing on long-term research while NExT tries to put research into Microsoft products. Peter gave the example of real-time translation into Skype already <a href="http://www.skype.com/en/translator-preview/">available</a> for public preview. Everyone in MSR emphasized that Microsoft will remain committed to open long-term research and said the latest round of cuts (<a href="http://news.microsoft.com/2015/07/08/satya-nadella-email-to-employees-on-sharpening-business-focus/">announced</a> while the summit was happening) will not affect research.<br />
<br />
<a href="https://www.microsoft.com/microsoft-hololens/en-us">HoloLens</a> had the most excitement, a way to manipulate virtual three-dimensional images. Unfortunately the summit didn't have HoloLenses for us to try out but I did get a cool HoloLens T-shirt. While one expects the most interest in HoloLens for gaming, Microsoft emphasized the educational aspect. Microsoft has a <a href="http://research.microsoft.com/en-us/projects/hololens/">call for proposals</a> for research and education uses for HoloLens.<br />
<br />
I didn't go to many of the parallel sessions, instead spending the time networking with colleagues old and new. I did really enjoy the <a href="http://research.microsoft.com/en-us/um/redmond/events/fs2015/demofest-abstracts.aspx">research showcase</a> which highlight many of the research projects. I tried out the Skype translator, failing a reverse Turing test because I thought I was talking to a computer but it was really a Spanish speaking human. My colleagues at MSR NYC were showing off their <a href="https://prediction.microsoft.com/">wisdom of the crowds</a>. Microsoft is moving their defunct academic search directly into Bing and Cortana. I tried Binging myself on the prototype and it did indeed list my research papers but not my homepage and this blog. They said they'll fix that in future updates.<br />
<br />
Monica Lam showed off her latest social messaging system <a href="http://www.omlet.me/">Omlet</a> to improve privacy by keeping data on the Omlet server for no longer than two weeks though I was more excited by their open API. Feel free to Omlet me.<br />
<br />
While the meeting had its share of hype (quantum computers to solve world hunger), I really enjoyed the couple of days in Redmond. Despite the SVC closing, Microsoft is still one of the few companies that has labs focused on true basic research.Lance Fortnowhttps://plus.google.com/101693130490639305932noreply@blogger.com10tag:blogger.com,1999:blog-3722233.post-75396555539075162012015-07-13T08:40:00.000-05:002015-07-13T08:40:38.876-05:00Is there an easier proof? A less messy proof? <br />
Consider the following statement:<br />
<br />
BEGIN STATEMENT:<br />
<br />
For all a,b,c, the equations<br />
<br />
x + y + z = a<br />
<br />
x<sup>2</sup> +y<sup>2</sup> + z<sup>2</sup> = b<br />
<br />
x<sup>3</sup> + y<sup>3</sup> + z<sup>3</sup> = c<br />
<br />
has a unique solution (up to perms of x,y,z). <br />
<br />
END STATEMENT<br />
<br />
One can also look at this with k equations, k variables, and powers 1,2,...,k.<br />
<br />
The STATEMENT is true. One can use Newton's identities (see <a href="https://en.wikipedia.org/wiki/Newton%27s_identities">here</a>) to obtain from the sums-of-powers all of the symmetric functions of x,y,z (uniquely). One can then form a polynomial which, in the k=3 case, is<br />
<br />
W^3 -(x+y+z)W^2 + (xy+xz+yz)W - xyz = 0<br />
<br />
whose roots are what we seek.<br />
<br />
I want to prove an easier theorem in an easier way that avoids using Newton's identities. Here is what I want to prove:<br />
<br />
Given those equations above (or the version with k-powers), and told that a,b,c are nonzero natural numbers, I want to prove that there is at most one natural-number solution for (x,y,z) (OR for x1,...,xk in the k-power case).<br />
<br />
Its hard to say `I want an easier proof' when the proof at hand really isn't that hard. And I don't want to say I want an `elementary' proof- I just want to avoid the messiness of Newton's identities. I doubt I can formalize what I want but, as <a href="https://en.wikipedia.org/wiki/I_know_it_when_I_see_it">Potter Stewart </a>said, I'll know it when I see it.<br />
<br />
<br />
<br />
<br />GASARCHhttp://www.blogger.com/profile/06134382469361359081noreply@blogger.com2tag:blogger.com,1999:blog-3722233.post-76133703129041547802015-07-09T08:53:00.000-05:002015-07-09T08:53:04.529-05:00Will Our Understanding of Math Deteriorate Over Time?Scientific American <a href="http://www.scientificamerican.com/article/researchers-race-to-rescue-the-enormous-theorem-before-its-giant-proof-vanishes/">writes</a> about rescuing the enormous theorem (classification of finite simple groups) before the proof vanishes. How can a proof vanish?<br />
<br />
In mathematics and theoretical computer science, we read research papers primarily to find research questions to work on, or find techniques we can use to prove new theorems. What happens to a research area then when researchers go elsewhere?<br />
<br />
In a <a href="http://mathoverflow.net/a/44213">response</a> to a question about how can one contribute to mathematics, Bill Thurston notes that our knowledge of mathematics can deteriorate over time.<br />
<blockquote class="tr_bq">
Mathematical understanding does not expand in a monotone direction. Our understanding frequently deteriorates as well. There are several obvious mechanisms of decay. The experts in a subject retire and die, or simply move on to other subjects and forget. Mathematics is commonly explained and recorded in symbolic and concrete forms that are easy to communicate, rather than in conceptual forms that are easy to understand once communicated. Translation in the direction conceptual -> concrete and symbolic is much easier than translation in the reverse direction, and symbolic forms often replaces the conceptual forms of understanding. And mathematical conventions and taken-for-granted knowledge change, so older texts may become hard to understand. In short, mathematics only exists in a living community of mathematicians that spreads understanding and breaths life into ideas both old and new.</blockquote>
Once a research area fills out, researchers tend to move on to new and different ideas. Much of the research in the theoretical CS community in the 50's, 60's and 70's have been lost to journal articles, now nicely digitized but rarely downloaded.<br />
<br />
What will happen with complexity classes once people stop studying them? You already don't see that many recent papers on complexity classes, even in the Computational Complexity Conference. A victim of our own success and failures: We settled most of the easy questions and the rest are very hard. As my generation retires, the classes may retire as well, outside of a couple of the biggies like P and NP. The old papers will still be out there, and you can always look up the classes in the <a href="https://complexityzoo.uwaterloo.ca/Complexity_Zoo">zoo</a> or on Wikipedia, but the understanding that goes with people studying these classes, and why we cared about them, may deteriorate just like computer programs that go unattended.Lance Fortnowhttps://plus.google.com/101693130490639305932noreply@blogger.com11tag:blogger.com,1999:blog-3722233.post-45817556126158889842015-07-05T20:29:00.000-05:002015-07-05T20:29:49.889-05:00Does Bob Deserve the lavish acknowledgement: A problem in Logic<br />
Alice and Carol are real mathematicians.<br />
Bob is an English major who does not know any mathematics. <br />
<br />
<br />
(This story is based on a true incident.)<br />
<br />
Alice writes a math paper. Carol reads it and offers corrections of style and grammar and how-to-say-things. She also helps simplify some of the proofs. She does not deserve a co-authorship but Alice does of course write in the acknowledgements<br />
<br />
<i>I would like to thank Carol for proofreading and for help with some of the proofs.</i><br />
<br />
Bob points out that this is silly --- if she would like to thank Carol then do so. So Alice changes it to<br />
<br />
<i>I thank Carol for proofreading and for help with some of the proofs.</i><br />
<br />
Even though Bob does not understand the math he begins reading the paper. He finds a few grammar mistakes, some points of style, and even a math mistake:<br />
<br />
BOB: Alice, this sentence mentions A1 and A2, is A1 the steak sauce?<br />
<br />
ALICE: Its A sub 1 and no it is not the steak sauce.<br />
<br />
BOB: But later in the sentence there is a reference to A? Maybe its implicit what A is and I don't get it since I don't know the math, but it does look funny.<br />
<br />
ALICE: Well pierce my ears and call be drafty! You're right! It should be A1, A2, and A_1 ∩ A_2.<br />
<br />
SO, in the end Bob DID proofread the paper and DID help. Alice wants to include him in the acknowledgements. She modifies the ack to<br />
<br />
<i>I thank Bob and Carol for proofreading and help with some of the proofs</i>.<br />
<br />
Is that correct? Bob just did proofreading, and Carol did proofreading AND helped with some proofs. In logical terms<br />
<br />
If B did X and C did X and Y then<br />
<br />
B AND C did X AND Y<br />
<br />
does seem correct.<br />
<br />
But is also seems misleading. Alice could separate it out:<br />
<br />
<i>I thank Carol for proofreading and help with some of the proofs.</i><br />
<i> </i><i>I thank Bob and Carol for proofreading.</i><br />
<br />
<i> </i>Thats more accurate but also more cumbersome.<br />
<br />
But my real question is, is the I THANK BOB AND CAROL... statement correct or incorrect? In logic correct, in English, perhaps not. We could ask Bob who is an English major and maybe get a paper out of it which Carol can proofread!<br />
<i><br /></i>GASARCHhttp://www.blogger.com/profile/06134382469361359081noreply@blogger.com8tag:blogger.com,1999:blog-3722233.post-40886268057236708602015-07-02T06:56:00.001-05:002015-07-02T06:56:53.888-05:00Goodbye SIGACT and CRATuesday I served my last day on two organizations, the <a href="http://www.sigact.org/">ACM SIGACT</a> Executive Committee and the <a href="http://cra.org/">CRA</a> Board of Directors.<br />
<br />
I spent ten years on the SIGACT (Special Interest Group on Algorithms and Computation Theory) EC, four years as vice-chair, three years as chair and three years as ex-chair, admittedly not so active those last three years. SIGACT is the main US academic organization for theoretical computer science and organizes STOC as its flagship conference. I tried to do <a href="http://futureofstoc.blogspot.com/">big things</a>, managed a few smaller things (ToCT, a few more accepted papers in STOC, poster sessions, workshops, moving Knuth and Distinguished Service to annual awards, an award for best student presentation, a tiered PC), some of them stuck and some of them didn't. Glad to see a<a href="http://blog.computationalcomplexity.org/2015/06/changing-stoc.html"> new movement</a> to try big changes to meet the main challenge that no conference, including STOC, really brings the theory community together anymore. As Michael Mitzenmacher becomes chair and Paul Beame takes my place as ex-chair, I wish them them and SIGACT well moving forward.<br />
<br />
The Computing Research Association's main efforts promotes computing research to industry and government and increasing the diversity in computing research. It's a well-run organization and we can thank them particularly for helping improve the funding situation for computing in difficult financial times. The CRA occasionally puts out <a href="http://cra.org/resources/bp-memos/">best practices memos</a> like a <a href="http://cra.org/resources/bp-view/best_practices_memo_evaluating_scholarship_in_hiring_tenure_and_promot/">recent one</a> recommending quality over quantity for hiring and promotion. Serving on the board, I most enjoyed interacting with computer scientists from across the entire field, instead of just hanging with theorists at the usual conferences and workshops.<br />
<br />
One advantage of leaving these committees: I can now kibbitz more freely on the theory community and computing in general. Should be fun.Lance Fortnowhttps://plus.google.com/101693130490639305932noreply@blogger.com0tag:blogger.com,1999:blog-3722233.post-39886190067534171942015-06-28T21:21:00.000-05:002015-06-28T21:21:11.538-05:00When do we care about small improvements?<br />
A while back complexity blog, Shtetl-optimized , and GLL all blogged about the improved matrix mult algorithms (Complexityblog: <a href="http://blog.computationalcomplexity.org/2011/11/matrix-mult-you-heard-it-here-third.html">here</a>, Shtetl-optimized: <a href="http://www.scottaaronson.com/blog/?p=839">here</a>, GLL <a href="https://rjlipton.wordpress.com/2011/11/29/a-breakthrough-on-matrix-product/">here</a>) of Stothers/Williams. It may have been on other theory blogs as well (if you know then let me know). We denote Matrix Mult Algorithm by MMA, and we use n<sup>a</sup> instead of O(n<sup>a</sup>). All the papers we refer to can be found either <a href="https://en.wikipedia.org/wiki/Coppersmith%E2%80%93Winograd_algorithm">here</a> or <a href="https://en.wikipedia.org/wiki/Matrix_multiplication#Algorithms_for_efficient_matrix_multiplication">here</a>.<br />
<br />
1987: Cooper and Winograd get MMA in n<sup>2.375477</sup><br />
<br />
2010: Stothers gets MMA in n<sup>2.374</sup><br />
<br />
2011: Williams gets MMA in n<sup>2.3728642</sup><br />
<br />
(Williams and Stother were ind, though Williams used some of Stother's stuff to simplify her proofs for the final version.)<br />
<br />
This Stothers/Williams results were a big deal! Williams paper got into STOC and, as mentioned above, three blogs reported on it AS SOON AS it was public. <br />
<br />
Fast forward to<br />
<br />
2014: Le Gall gets MMA in n<sup>2.3728639</sup>. Wikipedia says that this MMA is a simplificaion of Williams algorithm.<br />
<br />
The 2014 result may or may not be interesting (thats a tautology!). But what strikes me is that I came across it in 2015 and had not heard of it. I emailed Lance to ask if he had heard of it, he had not. I don't quite know if Lance and I not knowing about means its not that well known, but its at least on indicator.<br />
<br />
ALL of which brings us back to the title of this blog: When do we care about small improvements?<br />
<br />
<ol>
<li>We care about a small improvement if the result in question has been stuck where it was for a long time. This was the case for Stothers/Williams MMA and also for when the approx for metric TSP went from approx of 3/2 to approx of (3/2 - c) (see <a href="http://blog.computationalcomplexity.org/2010/12/breakthrough-in-algorithms-improved.html">here</a>).</li>
<li>We care about small improvements if they illustrate an a new technique. The leaf-counting technique for lower bounds on number-of-comparisons for finding the ith largest gave clean proofs and (I think) small improvements to known results. (Leaf Counting technique in brief: Any Dec Tree for MAX has EVERY branch is of length at least n-1 hence 2^{n-2} leaves. Take a tree for ith largest. For all x_1,...,x_{i-1} prune the tree by having these elements beat anything else. How they compare to each other determine arbitrarily. This results in a MAX tree for n-i elements and hence has 2^{n-i} leaves.All such trees have disjoint sets of leaves. So original tree has at least (n choose i)2^{n-i} leaves, hence has a branch of length log_2( (n choose i)2^{n-i}) = n+ ilog n - i. Was this better than what was known at the time? Not sure but the proof was much simpler.)</li>
<li>We care about small improvements if they tell you that a natural upper or lower bound is NOT true (I can't seem to get the numbered lists right so regard the following items as subitems of this one.)</li>
</ol>
<ol>
<li>Bent/ John showed that Median required 2n - 2sqrt(n) - O(log n) comparisons and then later Dor and Zwick improved this to (2+ 1/2^50)n. (I can't seem to find a free online version of this- if you do please leave a comment.)</li>
<li> Schonage, Paterson, Pippenger had median in 3n + o(n), and Dor and Zwick (not a typo- same people) improved this to 2.95n + o(n). (I can't seem to find a free online version of this- if you do please leave a comment.)</li>
<li>In both cases, especially (1), the improvement is really small and unimportant; however, knowing that 2n is NOT the lower bound and 3n is NOT the upper bound is worth knowing. Hence exact complexity is NOT going to be the nice number 2n or 3n. The only nice number between 2 and 3 is e, so lets hope its en. (I think I read that 2.5n is the actual conjecture. 2.5 is nice, but e is nicer.)</li>
</ol>
<br />
<br />
<br />
<br />
<br />
<br />GASARCHhttp://www.blogger.com/profile/06134382469361359081noreply@blogger.com2tag:blogger.com,1999:blog-3722233.post-82489777572227672262015-06-25T07:33:00.000-05:002015-06-25T07:33:01.394-05:00Changing STOCAt the recently completed STOC and the previous FOCS, much of the discussion revolved around reforming the conferences. You read the <a href="http://windowsontheory.org/tag/stoc-focs-reform/">discussion and comments</a> on Windows on Theory and I've also been cc'd on several very long email threads.<br />
<br />
STOC, as the flagship conference of ACM SIGACT, should be the focal point of the community, the place where researchers circle their calendars and make sure they attend the event. You see that at SOSP for the systems community or SIGCOMM for networking. But not STOC, smaller than it was thirty years ago when the theory community had a fraction of the people we have today.<br />
<br />
Instead STOC has become a conference for its authors, to give researchers a prestigious line in their CVs. While authors get to present their papers, STOC is no longer a primary place for dissemination, better served by <a href="http://arxiv.org/">arXiv</a> and <a href="http://eccc.hpi-web.de/">ECCC</a>.<br />
<br />
The problem is conference overload. We have two top theory conferences a year, STOC and FOCS, not to mention SODA, Computational Complexity and so many others. Conferences are expensive in both time and money and we can't afford to attend too many. People often choose more specialized conferences and workshops where they can focus on talking to people in their specialized research areas.<br />
<br />
SOSP on the other hand meets only once every two years, accepts only thirty papers and gets 600 attendees.<br />
<br />
The only true solution would merge and/or eliminate conferences. We don't need two major theory conferences a year. But that's not politically feasible.<br />
<br />
So the talk is of a Theory Festival centered around STOC in 2017, to make an event that all theorists would want to attend. What that theory festival should or should not do is the topic of all the discussion. I'm not going to talk about the various proposals but I encourage strong experimentation to get us out of this bad equilibrium. Otherwise we end up with status quo and status quo does not bring our community together.<br />
<br />Lance Fortnowhttps://plus.google.com/101693130490639305932noreply@blogger.com3tag:blogger.com,1999:blog-3722233.post-47860934655745057532015-06-22T13:15:00.000-05:002015-06-22T13:15:49.094-05:00Learning from teaching a HS student Schur's theorem on change<br />
(All the math this post refers to is in my manuscript which is <a href="http://www.cs.umd.edu/~gasarch/BLOGPAPERS/schur.pdf">here.)</a><br />
<br />
Recall Schur's theorem on making change as stated in wikipedia and other source:<br />
<br />
<i>Let a1,...,aL be rel prime coin denominations. Then the number of ways to make n cents</i><br />
<i>change is n<sup>L-1</sup> /(L-1)!a1a2...aL + Θ(n<sup>L-2</sup>).</i><br />
<br />
The proof I knew (from Wilfs book on generating functions) was not difficult; however,it involved roots of unity, partial fractions, Taylor series, and Generating functions. I needed to present the proof to a HS students who was in precalc. The writeup above is what I finally came up with. A few points.<br />
<br />
<ol>
<li>HS students, or at least mine, knew complex numbers. Hence roots-of-unity was okay. The proof of Schur's theorem has another plus: he had asked me just recently how complex numbers could be used in the real world since they weren't... real. I said the are often used as an intermediary on the way to a real solution and gave him an example of a cubic equation where you spot a complex solution and use it to obtain the real solutions. Schur's theorem is a more sophisticated example of using complex numbers to get a result about reals (about naturals!) so that's a win.</li>
<li>Partial Fractions. If the student had had calculus then he would know what partial fractions were and believe me when I said they always work. But since he had not had calculus I prepared a proof that they worked. Then I realized--- I have never seen a proof that they work! This is a matter of timing- I saw them in High School Calculus in 1975 which was taught without proofs (just as well, analysis is a bad first-proof course) and I didn't quite realize that the techniques they taught us aren't quite a proof that it works. I came up with my own proof (I can't imagine its original but I have not found a ref) in 2015. That's 40 years between seeing a concept and proving that it works. A personal record.</li>
<li>Taylor Series. I needed the Taylor series for 1/(1-x)^b (just for b a natural). I came up with a proof that does not use calculus and that a HS student could follow. Very happy that I was forced to do do this. Actually uses a nice combinatorial identity!</li>
<li>The lemmas about partial fractions and about Taylor series are of course very very old. Are my proofs new? I doubt it though I have not been able to find a reference. If you know one please leave a polite comment.</li>
<li>Having gone through the proof so carefully I noticed something else the proof yields: Let M be the LCM of a1,...,aL. For all 0\le r\le M-1 there is a poly p of degree L-1 such that if n\equiv r mod M then p(n) is the number of ways to make change of n cents. I suspect this is known but could not find a ref (again- if you know one then please leave a polite comment.)</li>
</ol>
Moral of the story: By working with a HS student I was forced to find a proof for partial frac deomp, find a non-calc proof of a Taylor series, and obtain an interesting corollary. Hence this is already a win!<br />
<br />GASARCHhttp://www.blogger.com/profile/06134382469361359081noreply@blogger.com1tag:blogger.com,1999:blog-3722233.post-14773356600228528692015-06-18T11:59:00.000-05:002015-06-18T11:59:07.680-05:00FCRC ComplexityOn Wednesday at FCRC, the Complexity, STOC and EC (Economics and Computation) conferences all have sessions, a smorgasbord of talks, but tough decisions on what session to attend. Here's one you might have misses, the EC paper <a href="http://dx.doi.org/10.1145/2764468.2764515">Why Prices Need Algorithms</a> by Roughgarden and Talgam-Cohen that has a nice application of complexity to the existence of equilibrium, not whether the equilibrium is hard to compute but whether it exists.<div>
<br /></div>
<div>
Roughly Roughgarden and Talgam-Cohen show if a certain kind of a pricing equilibrium holds then one can get an efficient algorithm for a certain kind of reduction. Under reasonable complexity assumptions (like P <> NP) such reductions can't exist and so neither can the equilibrium.</div>
<div>
<br /></div>
<div>
Late Wednesday came the Complexity business meeting, the first open business meeting of the now unaffiliated Computational Complexity Conference. There were 84 attendees, a little bit down from last FCRC but higher than last year. There were 30 papers accepted out of 110 submissions. The 2016 conference will be held in Tokyo May 29-June 1.</div>
<div>
<br /></div>
<div>
There was much discussion on where Complexity will be in 2017 and on which journal will get the special issue for the next three years. Watch my twitter to see when they get set.</div>
<div>
<br /></div>
<div>
<br /></div>
<div>
<div>
<br /></div>
<div>
<br /></div>
</div>
Lance Fortnowhttps://plus.google.com/101693130490639305932noreply@blogger.com0tag:blogger.com,1999:blog-3722233.post-89348337115533045012015-06-16T15:53:00.001-05:002015-06-16T15:53:46.279-05:00STOC Business MeetingThis week I'm at the <a href="http://fcrc.acm.org/">Federated Computing Research Conference</a> in Portland, a collection of many mostly ACM conferences. Last night was the STOC business meeting.<br />
<br />
The meeting had beer but the beer had no alcohol. Not an auspicious start.<br />
<br />
289 registrants, a bit lower than the past few STOCs. With EC and Complexity at the same conference you would think STOC would draw larger but it doesn't.<br />
<br />
The conference had 93 accepted papers out of 347 papers. Best papers (copied from proceedings):<br />
The papers “Exponential Separation of Information and Communication for Boolean Function”, by Anat Ganor, Gillat Kol and Ran Raz, “2-Server PIR with sub-polynomial communication” by Zeev Dvir and Sivakanth Gopi, and “Lower bounds on the size of semidefinite programming relaxations ” by James Lee, Prasad Raghavendra and David Steurer, were selected for the STOC Best Paper Award. The paper “Inapproximability of Nash Equilibrium”, by Aviad Rubinstein, was selected for the Danny Lewin Best Student Paper Award.<br />
<br />
These and the 2015 STOC papers are publicly accessible via <a href="http://acm-stoc.org/stoc2015/toc.html">acm-stoc.org/stoc2015/toc.html</a> forever. part of a new <a href="http://acm-stoc.org/">STOC website</a> with a history of past conferences.<br />
<br />
Babai and Spielman and Teng officially received the awards we've <a href="http://blog.computationalcomplexity.org/2015/06/award-season.html">mentioned below</a>. The distinguished service award went to Avi Wigderson.<br />
<br />
As of July 1 we have a new SIGACT Executive Committee: Paul Beame (ex-Chair), Anna Karlin, Michael Mitzenmacher (Chair), Toni Pitassi, Eric Vigoda, Ryan Williams<br />
<br />
Lots of useful information about funding and more in Salil Vadhan's <a href="https://thmatters.files.wordpress.com/2015/06/catcs-report-stoc-2015.pptx">CATCS Report</a>.<br />
<br />
Upcoming conferences:<br />
<br />
<ul>
<li><a href="http://www.cs.cmu.edu/~venkatg/FOCS-2015-cfp.html">FOCS 2015</a> October 17-20 in Berkeley</li>
<li><a href="https://www.siam.org/meetings/da16/">SODA 2016</a> January 1012 in Arlington, VA.Abstract deadline July 1</li>
<li>STOC 2016 - Cambridge, MA June 18-21 collocated with SoCG</li>
<li>STOC 2017 - Potential "Theory Festival" - see below</li>
<li>STOC 2018 - 50th STOC possibly near Marina del Ray, the home of the first STOC</li>
</ul>
<div>
The business meeting ended with a discussion about a "Theory Festival" for STOC 2017. The goal is to get STOC to be a "must attend" meeting the way SOSP is for systems and SIGCOMM for networking. Check out the many discussions on Boaz Barak's <a href="http://windowsontheory.org/tag/stoc-focs-reform/">blog</a>.</div>
Lance Fortnowhttps://plus.google.com/101693130490639305932noreply@blogger.com0tag:blogger.com,1999:blog-3722233.post-60999405314115326682015-06-14T21:12:00.001-05:002015-06-16T11:49:29.234-05:00First issue of SIGACT news where I wasn't the editor. But...<br />
I posted at some earlier time that I was resigning from the editorship of SIGACT NEWS book review column, and handing the reins over to Fred Green (who is older than me, so `handing over the reins' might not be quite right).<br />
<br />
You can find the column on Fred's webpage <a href="http://mathcs.clarku.edu/~fgreen/">here</a>.<br />
<br />
I wish him well of course. He's off to a great start:<br />
<br />
<ol>
<li><b>The Cult of Pythagoras: Math and Myths</b>
by Alberto A. Martinez. Review by Bill Gasarch.
</li>
<li><b>Infinitesimal:
How a dangerous mathematical theory shaped the modern world</b>,
by Amir Alexander. Review by Bill Gasarch.
</li>
<li><b>Martin Gardner in the Twenty-First Century</b>,
edited by Michael Henle and Brian Hopkins. Review by Bill Gasarch.
</li>
<li><b>Algorithmic Barriers Falling: P=NP?</b>, and
<b>The Essential Knuth</b>, both by Edgar Daylight. Review by Bill Gasarch.
</li>
<li><b>Love and Math: The Heart of Hidden Reality</b>
by Edward Frenkel. Review by Bill Gasarch.
</li>
<li><b>Structure and Randomness: Pages from Year One of a Mathematical Blog</b> by Terence Tao. Review by Bill Gasarch. </li>
</ol>
Why so many reviews by... me?! Fred writes that its a tribute to my service which is of course true and appreciated. But I also note that when I was editor it would have been... odd? impolite? to have all of the columns by me in a single issue. But having Fred do it is fine. When Fred resigns 17 years from now (not to give away his age, but I think he'll retire before then), perhaps his successor will do that same.<br />
<br />
There are still books to review! Here is a list of books I still have in my office. If you want to review them email both gasarch@cs.umd.edu, fgreen@clarku.edu.<br />
Email the books and also your physical address to send it to.<br />
ALGORITHMS<br />
<br />
ReCombinatorics: The algorithmics of ancestral recombination graphs and<br />
phylogenic networks by Gusfield.<br />
<br />
<br />
Tractability: Practical approach to Hard Problems. Edited by Bordeaux, Hamadi, Kohli.<br />
<br />
Recent progress in the Boolean Domain. Edited by Bernd Steinbach<br />
<br />
<br />
PROGRAMMNG LANGUAGES<br />
<br />
Selected Papers on Computer Languages by Donald Knuth.<br />
<br />
MISC COMP SCI<br />
<br />
Introduction to reversible computing by Perumalla.<br />
<br />
<br />
Digital Logic Design: A Rigorous Approach by Even and Medina<br />
<br />
CoCo: The colorful history of Tandy's Underdog Computer by Boisy Pitre and<br />
Bill Loguidice.<br />
<br />
MATH AND HISTORY<br />
<br />
Professor Stewart's Casebook of Mathematical Mysteries by Ian Stewart.<br />
<br />
The Golden Ratio and Fibonacci Numbers by Richard Dunlap.<br />
<br />
<br />
<br />
Mathematics Galore! The first five years of the St. Marks Institue of Mathematics by Tanton.<br />
<br />
Mathematics Everywhere. Edited by Aigner and Behrends.<br />
<br />
An Epsiodic History of Mathematics: Mathematical Culture Through Problem Solving by Krantz.<br />
<br />
Proof Analysis: A Contribution to Hilbert's Last Problem by Negri and Von Plato.<br />
<br />
<br />
<br />
<br />
<br />
<br />GASARCHhttp://www.blogger.com/profile/06134382469361359081noreply@blogger.com2tag:blogger.com,1999:blog-3722233.post-79280804826446147952015-06-11T07:37:00.000-05:002015-06-12T12:35:38.318-05:00A Metric Group Product<div dir="ltr" style="margin-bottom: 0pt; margin-top: 0pt;">
<span style="font-family: Arial;"><span style="font-size: 14.6666669845581px; line-height: 20.2399997711182px; white-space: pre-wrap;"><i>A guest post by Dylan McKay, recently graduated from Georgia Tech and soon to be PhD student at Stanford. </i></span></span><br />
<span style="font-family: Arial;"><span style="font-size: 14.6666669845581px; line-height: 20.2399997711182px; white-space: pre-wrap;"><i><br /></i></span></span>
<span style="font-family: Arial;"><span style="font-size: 14.6666669845581px; line-height: 20.2399997711182px; white-space: pre-wrap;">[Editor's Note: Turns out the given solution <a href="http://blog.computationalcomplexity.org/2015/06/a-metric-group-product.html?showComment=1434130382494#c1863051852889917210">doesn't work</a> and whether a metric group product over the non-negative reals exists remains open.]</span></span></div>
<div dir="ltr" style="line-height: 1.38; margin-bottom: 0pt; margin-top: 0pt;">
<span style="background-color: transparent; color: black; font-family: Arial; font-size: 14.666666666666666px; font-style: normal; font-variant: normal; font-weight: normal; text-decoration: none; vertical-align: baseline; white-space: pre-wrap;"><br /></span></div>
<div dir="ltr" style="line-height: 1.38; margin-bottom: 0pt; margin-top: 0pt;">
<span style="background-color: transparent; color: black; font-family: Arial; font-size: 14.666666666666666px; font-style: normal; font-variant: normal; font-weight: normal; text-decoration: none; vertical-align: baseline; white-space: pre-wrap;">Here a cute puzzle motivated by a pair of undergrads and their poor understanding of what the phrase “Algebraic Geometry” really should mean:</span><br />
<span style="background-color: transparent; color: black; font-family: Arial; font-size: 14.666666666666666px; font-style: normal; font-variant: normal; font-weight: normal; text-decoration: none; vertical-align: baseline; white-space: pre-wrap;"><br /></span></div>
<div dir="ltr" style="line-height: 1.38; margin-bottom: 0pt; margin-top: 0pt;">
<span style="background-color: transparent; color: black; font-family: Arial; font-size: 14.666666666666666px; font-style: normal; font-variant: normal; font-weight: normal; text-decoration: none; vertical-align: baseline; white-space: pre-wrap;">Find a function </span><span style="background-color: transparent; color: black; font-family: Arial; font-size: 14.666666666666666px; font-style: normal; font-variant: normal; font-weight: bold; text-decoration: none; vertical-align: baseline; white-space: pre-wrap;">f </span><span style="background-color: transparent; color: black; font-family: Arial; font-size: 14.666666666666666px; font-style: normal; font-variant: normal; font-weight: normal; text-decoration: none; vertical-align: baseline; white-space: pre-wrap;">from the nonnegative reals to the nonnegative reals that satisfies the group axioms and the metric axioms, or prove that there is no such function. That is, find an </span><span style="background-color: transparent; color: black; font-family: Arial; font-size: 14.666666666666666px; font-style: normal; font-variant: normal; font-weight: bold; text-decoration: none; vertical-align: baseline; white-space: pre-wrap;">f:RxR→R</span><span style="background-color: transparent; color: black; font-family: Arial; font-size: 14.666666666666666px; font-style: normal; font-variant: normal; font-weight: normal; text-decoration: none; vertical-align: baseline; white-space: pre-wrap;"> such that </span><span style="background-color: transparent; color: black; font-family: Arial; font-size: 14.666666666666666px; font-style: normal; font-variant: normal; font-weight: bold; text-decoration: none; vertical-align: baseline; white-space: pre-wrap;">(R,f)</span><span style="background-color: transparent; color: black; font-family: Arial; font-size: 14.666666666666666px; font-style: normal; font-variant: normal; font-weight: normal; text-decoration: none; vertical-align: baseline; white-space: pre-wrap;"> is a group and a metric space. (I am using </span><span style="background-color: transparent; color: black; font-family: Arial; font-size: 14.666666666666666px; font-style: italic; font-variant: normal; font-weight: bold; text-decoration: none; vertical-align: baseline; white-space: pre-wrap;">R</span><span style="background-color: transparent; color: black; font-family: Arial; font-size: 14.666666666666666px; font-style: normal; font-variant: normal; font-weight: normal; text-decoration: none; vertical-align: baseline; white-space: pre-wrap;"> to refer to the set of nonnegative real numbers).</span><br />
<span style="background-color: transparent; color: black; font-family: Arial; font-size: 14.666666666666666px; font-style: normal; font-variant: normal; font-weight: normal; text-decoration: none; vertical-align: baseline; white-space: pre-wrap;"><br /></span></div>
<span style="font-family: Arial; font-size: 14.6666666666667px; line-height: 1.38; white-space: pre-wrap;">As a quick reminder, the group axioms are:</span><br />
<span style="color: black; font-family: Arial; font-size: 14.6666666666667px; vertical-align: baseline; white-space: pre-wrap;"><br /></span>
<span style="color: black; font-family: Arial; font-size: 14.6666666666667px; vertical-align: baseline; white-space: pre-wrap;">- Closure: </span><span style="color: black; font-family: Arial; font-size: 14.6666666666667px; font-weight: bold; vertical-align: baseline; white-space: pre-wrap;">f(a,b)</span><span style="color: black; font-family: Arial; font-size: 14.6666666666667px; vertical-align: baseline; white-space: pre-wrap;"> must be in </span><span style="color: black; font-family: Arial; font-size: 14.6666666666667px; font-weight: bold; vertical-align: baseline; white-space: pre-wrap;">R</span><br />
<div dir="ltr" style="line-height: 1.38; margin-bottom: 0pt; margin-top: 0pt;">
<span style="background-color: transparent; color: black; font-family: Arial; font-size: 14.666666666666666px; font-style: normal; font-variant: normal; font-weight: normal; text-decoration: none; vertical-align: baseline; white-space: pre-wrap;">- Identity: There must exist an element </span><span style="background-color: transparent; color: black; font-family: Arial; font-size: 14.666666666666666px; font-style: normal; font-variant: normal; font-weight: bold; text-decoration: none; vertical-align: baseline; white-space: pre-wrap;">e</span><span style="background-color: transparent; color: black; font-family: Arial; font-size: 14.666666666666666px; font-style: normal; font-variant: normal; font-weight: normal; text-decoration: none; vertical-align: baseline; white-space: pre-wrap;"> such that for all </span><span style="background-color: transparent; color: black; font-family: Arial; font-size: 14.666666666666666px; font-style: normal; font-variant: normal; font-weight: bold; text-decoration: none; vertical-align: baseline; white-space: pre-wrap;">a</span><span style="background-color: transparent; color: black; font-family: Arial; font-size: 14.666666666666666px; font-style: normal; font-variant: normal; font-weight: normal; text-decoration: none; vertical-align: baseline; white-space: pre-wrap;">, </span><span style="background-color: transparent; color: black; font-family: Arial; font-size: 14.666666666666666px; font-style: normal; font-variant: normal; font-weight: bold; text-decoration: none; vertical-align: baseline; white-space: pre-wrap;">f(e,a)=f(a,e)=a</span></div>
<div dir="ltr" style="line-height: 1.38; margin-bottom: 0pt; margin-top: 0pt;">
<span style="background-color: transparent; color: black; font-family: Arial; font-size: 14.666666666666666px; font-style: normal; font-variant: normal; font-weight: normal; text-decoration: none; vertical-align: baseline; white-space: pre-wrap;">- Associative: for all </span><span style="background-color: transparent; color: black; font-family: Arial; font-size: 14.666666666666666px; font-style: normal; font-variant: normal; font-weight: bold; text-decoration: none; vertical-align: baseline; white-space: pre-wrap;">a,b,c,</span><span style="background-color: transparent; color: black; font-family: Arial; font-size: 14.666666666666666px; font-style: normal; font-variant: normal; font-weight: normal; text-decoration: none; vertical-align: baseline; white-space: pre-wrap;"> </span><span style="background-color: transparent; color: black; font-family: Arial; font-size: 14.666666666666666px; font-style: normal; font-variant: normal; font-weight: bold; text-decoration: none; vertical-align: baseline; white-space: pre-wrap;">f(f(a,b),c) = f(a,f(b,c))</span></div>
<div dir="ltr" style="line-height: 1.38; margin-bottom: 0pt; margin-top: 0pt;">
<span style="background-color: transparent; color: black; font-family: Arial; font-size: 14.666666666666666px; font-style: normal; font-variant: normal; font-weight: normal; text-decoration: none; vertical-align: baseline; white-space: pre-wrap;">- Inverse: for all </span><span style="background-color: transparent; color: black; font-family: Arial; font-size: 14.666666666666666px; font-style: normal; font-variant: normal; font-weight: bold; text-decoration: none; vertical-align: baseline; white-space: pre-wrap;">a</span><span style="background-color: transparent; color: black; font-family: Arial; font-size: 14.666666666666666px; font-style: normal; font-variant: normal; font-weight: normal; text-decoration: none; vertical-align: baseline; white-space: pre-wrap;">, there must exist a </span><span style="background-color: transparent; color: black; font-family: Arial; font-size: 14.666666666666666px; font-style: normal; font-variant: normal; font-weight: bold; text-decoration: none; vertical-align: baseline; white-space: pre-wrap;">b</span><span style="background-color: transparent; color: black; font-family: Arial; font-size: 14.666666666666666px; font-style: normal; font-variant: normal; font-weight: normal; text-decoration: none; vertical-align: baseline; white-space: pre-wrap;"> such that </span><span style="background-color: transparent; color: black; font-family: Arial; font-size: 14.666666666666666px; font-style: normal; font-variant: normal; font-weight: bold; text-decoration: none; vertical-align: baseline; white-space: pre-wrap;">f(a,b)=e</span><br />
<span style="background-color: transparent; color: black; font-family: Arial; font-size: 14.666666666666666px; font-style: normal; font-variant: normal; font-weight: bold; text-decoration: none; vertical-align: baseline; white-space: pre-wrap;"><br /></span></div>
<div dir="ltr" style="line-height: 1.38; margin-bottom: 0pt; margin-top: 0pt;">
<span style="background-color: transparent; color: black; font-family: Arial; font-size: 14.666666666666666px; font-style: normal; font-variant: normal; font-weight: normal; text-decoration: none; vertical-align: baseline; white-space: pre-wrap;">And the metric axioms are:</span><br />
<span style="background-color: transparent; color: black; font-family: Arial; font-size: 14.666666666666666px; font-style: normal; font-variant: normal; font-weight: normal; text-decoration: none; vertical-align: baseline; white-space: pre-wrap;"><br /></span></div>
<div dir="ltr" style="line-height: 1.38; margin-bottom: 0pt; margin-top: 0pt;">
<span style="background-color: transparent; color: black; font-family: Arial; font-size: 14.666666666666666px; font-style: normal; font-variant: normal; font-weight: bold; text-decoration: none; vertical-align: baseline; white-space: pre-wrap;">- f(a,b) = 0 iff a=b</span></div>
<div dir="ltr" style="line-height: 1.38; margin-bottom: 0pt; margin-top: 0pt;">
<span style="background-color: transparent; color: black; font-family: Arial; font-size: 14.666666666666666px; font-style: normal; font-variant: normal; font-weight: bold; text-decoration: none; vertical-align: baseline; white-space: pre-wrap;">- f(a,b) <= f(a,c) + f(c,b)</span></div>
<div dir="ltr" style="line-height: 1.38; margin-bottom: 0pt; margin-top: 0pt;">
<span style="background-color: transparent; color: black; font-family: Arial; font-size: 14.666666666666666px; font-style: normal; font-variant: normal; font-weight: bold; text-decoration: none; vertical-align: baseline; white-space: pre-wrap;">- f(a,b) = f(b,a)</span><br />
<span style="background-color: transparent; color: black; font-family: Arial; font-size: 14.666666666666666px; font-style: normal; font-variant: normal; font-weight: bold; text-decoration: none; vertical-align: baseline; white-space: pre-wrap;"><br /></span></div>
<div dir="ltr" style="line-height: 1.38; margin-bottom: 0pt; margin-top: 0pt;">
<span style="background-color: transparent; color: black; font-family: Arial; font-size: 14.666666666666666px; font-style: normal; font-variant: normal; font-weight: normal; text-decoration: none; vertical-align: baseline; white-space: pre-wrap;">One really bizarre thing about this supposed function is that, what this metric does is essentially guarantee that, given some number x, every other number has a distance from x that is unique -- no other number is exactly that distance away! This is quite counterintuitive to how we think about distance. Each number is its own distance from 0, though, which is very much in line with intuition.</span><br />
<span style="background-color: transparent; color: black; font-family: Arial; font-size: 14.666666666666666px; font-style: normal; font-variant: normal; font-weight: normal; text-decoration: none; vertical-align: baseline; white-space: pre-wrap;"><br /></span></div>
<div dir="ltr" style="line-height: 1.38; margin-bottom: 0pt; margin-top: 0pt;">
<span style="background-color: transparent; color: black; font-family: Arial; font-size: 14.666666666666666px; font-style: normal; font-variant: normal; font-weight: normal; text-decoration: none; vertical-align: baseline; white-space: pre-wrap;">(If you want to solve the puzzle yourself, don't read any further until you do! Unless you want some hints, in which case, look at the next paragraph.)</span><br />
<span style="background-color: transparent; color: black; font-family: Arial; font-size: 14.666666666666666px; font-style: normal; font-variant: normal; font-weight: normal; text-decoration: none; vertical-align: baseline; white-space: pre-wrap;"><br /></span></div>
<div dir="ltr" style="line-height: 1.38; margin-bottom: 0pt; margin-top: 0pt;">
<span style="background-color: transparent; color: black; font-family: Arial; font-size: 14.666666666666666px; font-style: normal; font-variant: normal; font-weight: normal; text-decoration: none; vertical-align: baseline; white-space: pre-wrap;">We can, however, make some other observations that point us in the right direction. For instance, </span><span style="background-color: transparent; color: black; font-family: Arial; font-size: 14.666666666666666px; font-style: normal; font-variant: normal; font-weight: bold; text-decoration: none; vertical-align: baseline; white-space: pre-wrap;">f(e,e) = 0</span><span style="background-color: transparent; color: black; font-family: Arial; font-size: 14.666666666666666px; font-style: normal; font-variant: normal; font-weight: normal; text-decoration: none; vertical-align: baseline; white-space: pre-wrap;"> from the metric axioms and </span><span style="background-color: transparent; color: black; font-family: Arial; font-size: 14.666666666666666px; font-style: normal; font-variant: normal; font-weight: bold; text-decoration: none; vertical-align: baseline; white-space: pre-wrap;">f(e,e) = e</span><span style="background-color: transparent; color: black; font-family: Arial; font-size: 14.666666666666666px; font-style: normal; font-variant: normal; font-weight: normal; text-decoration: none; vertical-align: baseline; white-space: pre-wrap;"> from the group axioms, so you get that </span><span style="background-color: transparent; color: black; font-family: Arial; font-size: 14.666666666666666px; font-style: normal; font-variant: normal; font-weight: bold; text-decoration: none; vertical-align: baseline; white-space: pre-wrap;">e = 0</span><span style="background-color: transparent; color: black; font-family: Arial; font-size: 14.666666666666666px; font-style: normal; font-variant: normal; font-weight: normal; text-decoration: none; vertical-align: baseline; white-space: pre-wrap;">. From this and the metric axioms, you get that every element must be it’s own inverse! </span><br />
<span style="background-color: transparent; color: black; font-family: Arial; font-size: 14.666666666666666px; font-style: normal; font-variant: normal; font-weight: normal; text-decoration: none; vertical-align: baseline; white-space: pre-wrap;"><br /></span></div>
<div dir="ltr" style="line-height: 1.38; margin-bottom: 0pt; margin-top: 0pt;">
<span style="background-color: transparent; color: black; font-family: Arial; font-size: 14.666666666666666px; font-style: normal; font-variant: normal; font-weight: normal; text-decoration: none; vertical-align: baseline; white-space: pre-wrap;">Here, we are reminded of a pretty familiar and trusty function, this exclusive-or (XOR) function! And indeed, this will lead us a to a solution.</span><br />
<span style="background-color: transparent; color: black; font-family: Arial; font-size: 14.666666666666666px; font-style: normal; font-variant: normal; font-weight: normal; text-decoration: none; vertical-align: baseline; white-space: pre-wrap;"><br /></span></div>
<div dir="ltr" style="line-height: 1.38; margin-bottom: 0pt; margin-top: 0pt;">
<span style="background-color: transparent; color: black; font-family: Arial; font-size: 14.666666666666666px; font-style: normal; font-variant: normal; font-weight: normal; text-decoration: none; vertical-align: baseline; white-space: pre-wrap;">Here is our candidate function:</span><br />
<span style="background-color: transparent; color: black; font-family: Arial; font-size: 14.666666666666666px; font-style: normal; font-variant: normal; font-weight: normal; text-decoration: none; vertical-align: baseline; white-space: pre-wrap;"><br /></span></div>
<div dir="ltr" style="line-height: 1.38; margin-bottom: 0pt; margin-top: 0pt;">
<span style="background-color: transparent; color: black; font-family: Arial; font-size: 14.666666666666666px; font-style: normal; font-variant: normal; font-weight: normal; text-decoration: none; vertical-align: baseline; white-space: pre-wrap;">Consider x and y in their binary representations. If they do not have the same number of bits to the left of the decimal point (or should it be called the binary point?), pad the one with fewer such bits with 0’s so they have the same number of such bits. Then </span><span style="background-color: transparent; color: black; font-family: Arial; font-size: 14.6666666666667px; font-style: normal; font-variant: normal; text-decoration: none; vertical-align: baseline; white-space: pre-wrap;"><b>f(x,y)</b></span><span style="background-color: transparent; color: black; font-family: Arial; font-size: 14.666666666666666px; font-style: normal; font-variant: normal; font-weight: normal; text-decoration: none; vertical-align: baseline; white-space: pre-wrap;"> will be the number represented in binary by the bit-wise exclusive or of these two strings (maintaining the same number of bits to the left of the decimal point, of course). And there we have it: our function! </span><br />
<span style="background-color: transparent; color: black; font-family: Arial; font-size: 14.666666666666666px; font-style: normal; font-variant: normal; font-weight: normal; text-decoration: none; vertical-align: baseline; white-space: pre-wrap;"><br /></span></div>
<div dir="ltr" style="line-height: 1.38; margin-bottom: 0pt; margin-top: 0pt;">
<span style="background-color: transparent; color: black; font-family: Arial; font-size: 14.666666666666666px; font-style: normal; font-variant: normal; font-weight: normal; text-decoration: none; vertical-align: baseline; white-space: pre-wrap;">Now of course, we still need to prove that it satisfies the axioms. But if you do not believe that it does, work it out for yourself! Each axiom is pretty simple to check, especially as we are (for the most part) familiar with this as an extension of an idea for some smaller groups. Well, all of them except our good friend the triangle inequality. This one actually isn’t too bad, but if you have trouble, I will include a hint at the bottom of the post.</span><br />
<span style="background-color: transparent; color: black; font-family: Arial; font-size: 14.666666666666666px; font-style: normal; font-variant: normal; font-weight: normal; text-decoration: none; vertical-align: baseline; white-space: pre-wrap;"><br /></span></div>
<div dir="ltr" style="line-height: 1.38; margin-bottom: 0pt; margin-top: 0pt;">
<span style="background-color: transparent; color: black; font-family: Arial; font-size: 14.666666666666666px; font-style: normal; font-variant: normal; font-weight: normal; text-decoration: none; vertical-align: baseline; white-space: pre-wrap;">Anyway, I hope you liked our puzzle!</span><br />
<span style="background-color: transparent; color: black; font-family: Arial; font-size: 14.666666666666666px; font-style: normal; font-variant: normal; font-weight: normal; text-decoration: none; vertical-align: baseline; white-space: pre-wrap;"><br /></span></div>
<div dir="ltr" style="line-height: 1.38; margin-bottom: 0pt; margin-top: 0pt;">
<span style="background-color: transparent; color: black; font-family: Arial; font-size: 14.666666666666666px; font-style: normal; font-variant: normal; font-weight: normal; text-decoration: none; vertical-align: baseline; white-space: pre-wrap;">Thanks!</span><br />
<span style="background-color: transparent; color: black; font-family: Arial; font-size: 14.666666666666666px; font-style: normal; font-variant: normal; font-weight: normal; text-decoration: none; vertical-align: baseline; white-space: pre-wrap;"><br /></span></div>
<div dir="ltr" style="line-height: 1.38; margin-bottom: 0pt; margin-top: 0pt;">
<span style="background-color: transparent; color: black; font-family: Arial; font-size: 14.666666666666666px; font-style: normal; font-variant: normal; font-weight: normal; text-decoration: none; vertical-align: baseline; white-space: pre-wrap;">-Dylan</span><br />
<span style="background-color: transparent; color: black; font-family: Arial; font-size: 14.666666666666666px; font-style: normal; font-variant: normal; font-weight: normal; text-decoration: none; vertical-align: baseline; white-space: pre-wrap;"><br /></span></div>
<div dir="ltr" style="line-height: 1.38; margin-bottom: 0pt; margin-top: 0pt;">
<span style="background-color: transparent; color: black; font-family: Arial; font-size: 14.666666666666666px; font-style: normal; font-variant: normal; font-weight: normal; text-decoration: none; vertical-align: baseline; white-space: pre-wrap;">Hint for triangle inequality: XOR and addition are really similar, but there is a key difference between them that make a XOR b <= a + b.</span></div>
Lance Fortnowhttps://plus.google.com/101693130490639305932noreply@blogger.com18