tag:blogger.com,1999:blog-37222332015-07-06T07:05:15.550-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.comBlogger2290125tag: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.com6tag: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.com1tag: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.com18tag:blogger.com,1999:blog-3722233.post-50291827527167766142015-06-08T14:02:00.002-05:002015-06-08T14:27:48.643-05:00The city where the book publishers resides is Funkytown!A while back when I got back the galleys for a paper the publisher wanted to know the complete postal address of one of the co-authors and also the city where the publisher of a book in he bibliography was printed. The publisher didn't really have a city, so I wrote in FUNKYTOWN. <br />
<br />
Is it important in a paper to have the city that the publisher is in? I am assuming that at one time it was (though I am not sure why even that is) but now it is<br />
completely irrelevant.<br />
<br />
Is it important to have an authors postal address? I can't imagine why nowadays in 2015, though this I can imagine as being important in an earlier era. <br />
<br />
<br />
Question: What information do publishers ask for in galleys that are no longer relevant? Why do they? When will they stop?<br />
<br />
<br />GASARCHhttp://www.blogger.com/profile/06134382469361359081noreply@blogger.com2tag:blogger.com,1999:blog-3722233.post-48578644475764143862015-06-04T10:01:00.002-05:002015-06-08T15:56:58.359-05:00Langs with provably bigger CFG's then CSG's<br />
In a prior blog entry <a href="http://blog.computationalcomplexity.org/2015/05/sizes-of-dfas-nfas-dpdas-ucfg-cfgs-csls.html">HERE</a> I discussed very large differences in the size of machines. I didn't discuss CFG vs CSG so I'll do that now. We assume that the CFGs and CSGs are in Chomsky Normal Form (for CSG this means that RHS is any rule is of length 1 or 2).<br />
<br />
The following are known:<br />
<br />
1) Let PERMn be the set of permutations of {1,...,n} (so PERM3 is {123,132,213,231,312,321}). Then (1) there exists a CSG for PERMn of size O(n<sup>2</sup>), but (2) every CFG for PERMn requires size 2<sup>Ω(n) . </sup>The upper bound is easy, the lower bound is by Ellul, Krawetz, Shallit, Wang <a href="https://cs.uwaterloo.ca/~shallit/Papers/re3.pdf">Here</a>.<br />
<br />
2) Let Wn = { ww : |w|=n}. Then (1) there exists a CSG for Wn of size O(n), but (2) every CFG for Wn requires size 2<sup>Ω(n)</sup>. The upper bound we leave to the reader. Filmus <a href="http://www.cs.toronto.edu/~yuvalf/CFG-LB.pdf">HERE</a> for the lower bound.(ADDED LATER: In Comment Below Filmus (yes, the same one!) claims Wn has a CSG of size O(log n)).<br />
<br />
3) Let Sn = { w : |w|=3n and the numbers of a's, b's, c's in w are all the same}. Then (1) there exists a CSG for Sn of size O(log n) but (2) every CFG for Wn requires size 2<sup>Ω(n)</sup>. The upper bound is from<a href="http://arxiv.org/abs/1503.08847"> Beigel and Gasarch</a> (If you know of an earlier source leave a polite comment.) The lower bound is from Filmus (the ref above).(ADDED LATER- In Comment Below Filmus (yes, the same one!) corrects me, his paper did not show Sn has exp lower bound, and in fact Sn DOES have a CFG of size O(n^3)).<br />
<br />
4) The languages above are (informally) natural. If one goes to unnatural languages then there is a result where the CFG is GINORMOUS: For all f ≤<sub>T</sub> HALT, for all n, there is a lang Ln such that (1) there exists a CSG for Ln of size n, but (2) every CFG for Ln has size ≥ f(n). First proven by Meyer, but a new proof by Beigel and Gasarch is in the paper pointed to above. (See that paper for the history.)<br />
<br />
The results stated above are suitable for an ugrad formal lang theory course.<br />
<br />
Are there natural langs with triple-exp or larger gap between CFG's and CSG's? There are very few techniques to get lower bounds for CFG's (the papers of Ellul et al, and Filmus, are the only ones I know) so new techniques may be needed. Are there even any good candidates for natural languages with small CSG's and really really large CFG's?<br />
<br />
<br />
<br />GASARCHhttp://www.blogger.com/profile/06134382469361359081noreply@blogger.com1tag:blogger.com,1999:blog-3722233.post-28226669243980108032015-06-01T15:46:00.000-05:002015-06-01T15:47:23.996-05:00Award Season<div class="separator" style="clear: both; text-align: center;">
</div>
<div class="separator" style="clear: both; text-align: center;">
</div>
László Babai will receive the <a href="http://www.sigact.org/Prizes/Knuth/citation2015.pdf">2015 Knuth Prize</a> and Daniel Spielman and Shang-Hua Teng will receive the <a href="http://www.sigact.org/Prizes/Godel/citation2015.pdf">2015 Gödel Prize</a>. ACM issued a <a href="http://www.acm.org/press-room/news-releases/2015/knuth-godel-prizes-2015">press release</a> for both awards which will be presented at the upcoming <a href="http://acm-stoc.org/stoc2015/">STOC</a> at <a href="http://fcrc.acm.org/">FCRC</a>.<br />
<br />
Babai did seminal research on interactive proofs, communication complexity, group algorithms and much more. One cannot count the number of PhD theses in mathematics and computer science that can trace themselves back to some initial work by Babai. I was lucky to have Laci Babai as a colleague, mentor and friend during my years at the University of Chicago.<br />
<br />
<div class="separator" style="clear: both; text-align: center;">
</div>
Spielman and Teng, who <a href="http://www.sigact.org/Prizes/Godel/2008.html">received the 2008 Gödel Prize</a> for smooth analysis, won again for three papers using nearly linear time Laplacian solvers for a series of graph problems.<br />
<ul>
<li><a href="http://dx.doi.org/10.1137/08074489X">Spectral sparsification of graphs</a>. SIAM J. Computing 40:981-1025, 2011.</li>
<li><a href="http://dx.doi.org/10.1137/080744888">A local clustering algorithm for massive graphs and its application to nearly linear time graph partitioning</a>. SIAM J. Computing 42:1-26, 2013.</li>
<li><a href="http://dx.doi.org/10.1137/090771430">Nearly linear time algorithms for preconditioning and solving symmetric, diagonally dominant linear systems</a>. SIAM J. Matrix Anal. Appl. 35:835-885, 2014. </li>
</ul>
<div>
The <a href="http://awards.acm.org/">ACM Awards</a> ceremony later this month will have a number of theory related prizes.</div>
<div>
<ul>
<li>Dan Boneh is the recipient of the <a href="http://awards.acm.org/4125431_boneh.pdf">ACM-Infosys Foundation Award in the Computing Sciences</a> for the development of pairing-based cryptography and its application in identity-based encryption.</li>
<li>James Demmel is the recipient of the <a href="http://awards.acm.org/kanellakis/">Paris Kanellakis Theory and Practice Award</a> for his work on numerical linear algebra libraries, including LAPACK.</li>
<li>Charles Leiserson will receive the <a href="http://awards.acm.org/press_releases/kennedy-award-2014.pdf">ACM-IEEE CS Ken Kennedy award</a> for his work on parallel computing.</li>
<li>Jon Kleinberg is the 2014 recipient of the <a href="http://awards.acm.org/award_winners/kleinberg_0032532.cfm">ACM – AAAI Allen Newell Award</a> for social and information networks, information retrieval, and data science, and for bridging computing, economics and the social sciences.</li>
<li>New <a href="http://awards.acm.org/fellow/year.cfm">ACM Fellows</a> include Al Borodin, Faith Ellen, Michael Kearns, Valerie King, Yishay Mansour, Michael Mitzenmacher, Omer Reingold, Ronitt Rubinfeld and Aravind Srinivasan.</li>
</ul>
</div>
Lance Fortnowhttps://plus.google.com/101693130490639305932noreply@blogger.com1tag:blogger.com,1999:blog-3722233.post-56342915632350767602015-05-28T13:06:00.000-05:002015-05-28T13:06:15.336-05:00Who wins this bet?<br />
Alice and Bob are at an auction and Alice wants to buy an encyclopedia set from 1980. Bob says <i>don't buy that, you'll never use it. In this age of Wikipedia and Google and THE WEB. </i>Alice says <i>you don't know that. </i>They agree that Alice will spend no more than $20.00 on it (and she does win it at $20.00) and that:<br />
<br />
If Alice does not use the encyclopedia within 5 years then she owes Bob $10.00. If she does use it then Bob owes Alice $10.00.<br />
<br />
3 years later its really cold outside. Alice's house is not that well insulated. So she takes carpets against the bottom cracks in the door and weights them down with the volumes of the encyclopedia. This helps her keep warm and cuts down on her heating bill.<br />
<br />
Alice says<i> I used the encyclopedia. Pay up! In your face! I used them! You were wrong!</i><br />
<br />
Bob says <i>You didn't use them to look anything up. So that doesn't count.</i><br />
<br />
Alice and Bob are asking YOU do decide. So leave comments either way and whoever has more votes before my next post wins! Feel free to leave reasons as well to persuade the other readers.<br />
<br />
<br />
<br />
<br />
<br />
<br />GASARCHhttp://www.blogger.com/profile/06134382469361359081noreply@blogger.com18tag:blogger.com,1999:blog-3722233.post-27239232689334672182015-05-25T09:56:00.000-05:002015-05-25T09:56:16.748-05:00John Nash (1928-2015)John Nash and his wife Alicia <a href="http://www.nytimes.com/2015/05/25/science/john-nash-a-beautiful-mind-subject-and-nobel-winner-dies-at-86.html">died in a taxi accident</a>, returning from the airport after he received the Abel prize in Norway. The public knew John Nash as the "Beautiful Mind" of book and screen, but we knew him as one of the great geniuses of the 20th century. Rakesh Vohra <a href="http://www.gametheorysociety.org/">captures</a> Nash's life and work, including his amazing <a href="http://blog.computationalcomplexity.org/2012/02/nash-and-nsa.html">letters to the NSA</a>.<br />
<br />
I briefly met John Nash at some MIT alumni events in New Jersey when I lived there (even though neither of us were MIT undergrads). He would come with his wife and son, the son wearing a winter coat no matter the season. Nash just seemed like any other introverted scientist and was happy to talk though understating his research ("I did some work in game theory") and never revealing the challenging life he led.<br />
<br />
Now that John and Alicia have found their final equilibrium, may we remember them and Nash's vision of using mathematics to understand the world we live in.Lance Fortnowhttps://plus.google.com/101693130490639305932noreply@blogger.com0tag:blogger.com,1999:blog-3722233.post-5897486578271957162015-05-21T18:56:00.000-05:002015-05-21T18:58:48.727-05:00An Intentional and an Unintentional teaching experiment regarding proving the number of primes is infinite.<br />
I taught Discrete Math Honors this semester. Two of the days were cancelled entirely because of snow (the entire school was closed) and four more I couldn't make because of health issues (I'm fine now). People DID sub for me those two and DID do what I would have done. I covered some crypto which I had not done in the past.<br />
<br />
Because of all of this I ended up not covering the proof that the primes were infinite until the last week.<br />
<br />
INTENTIONAL EXPERIMENT: Rather than phrase it as a proof by contradiction I phrased it, as I think Euclid did, as<br />
<br />
Given primes p1,p2,...,pn you can find a prime NOT on the list. (From this it easily follows that the primes are infinite.)<br />
<br />
Proof: the usual one, look at p1xp2x...xpn + 1 and either its prime or it has a prime factor not on the list.<br />
<br />
The nice thing about doing it this way is that there are EASY examples where p1xp2x...xpn+1 is NOT prime<br />
<br />
(e.g., the list is {2,5,11} yields 2x5x11 + 1 = 111 = 3 x 37, so 3 and 37 are both not in {2,5,11})<br />
<br />
<br />
where as if you always use the the product of the first n primes then add 1, you don't get to a non-prime until 2x3x5x7x11x13 + 1 = 30031 = 59x 509.<br />
<br />
They understood the proof better than prior classes had, even prior honors classes. <br />
<br />
UNINTENTIONAL: Since I did the proof at the end of the semester they ALREADY had some proof maturity, more so than had I done it (as I usually do) about 1/3 of the way through the course.<br />
<br />
They understood the proof better than prior classes had, even prior honors classes. Hence I should proof all of the theorems the last week! :-)<br />
<br />
But seriously, they did understand it better, but I don't know which of the two factors, or what combination caused it. Oh well.<br />
<br />
<br />GASARCHhttp://www.blogger.com/profile/06134382469361359081noreply@blogger.com2tag:blogger.com,1999:blog-3722233.post-36034312688700412952015-05-18T19:24:00.000-05:002015-05-23T16:00:41.613-05:00Theory Jobs 2015In the fall we <a href="http://blog.computationalcomplexity.org/2014/10/2014-fall-jobs-post.html">list theory jobs</a>, in the spring we see who got them. Like <a href="http://blog.computationalcomplexity.org/2014/05/theory-jobs-2014.html">last year</a>, I created a fully editable <a href="https://docs.google.com/spreadsheets/d/14pOq1dEI5X77LoSFQIMC0B0x-TZMv4rRrGiC3WFMqA0/edit?usp=sharing">Google Spreadsheet</a> to crowd source who is going where. Ground rules:<br />
<ul>
<li>I set up separate sheets for faculty, industry and postdoc/visitors.</li>
<li>People should be connected to theoretical computer science, broadly defined.</li>
<li>Only add jobs that you are absolutely sure have been offered and accepted. This is not the place for speculation and rumors.</li>
<li>You are welcome to add yourself, or people your department has hired.</li>
</ul>
This document will continue to grow as more jobs settle. So check it often.<br />
<br />
<iframe frameborder="0" height="750" src="https://docs.google.com/spreadsheets/d/14pOq1dEI5X77LoSFQIMC0B0x-TZMv4rRrGiC3WFMqA0/pubhtml?widget=true&headers=false" width="575"></iframe>
<a href="https://docs.google.com/spreadsheets/d/14pOq1dEI5X77LoSFQIMC0B0x-TZMv4rRrGiC3WFMqA0/edit?usp=sharing">Edit</a>Lance Fortnowhttps://plus.google.com/101693130490639305932noreply@blogger.com16tag:blogger.com,1999:blog-3722233.post-83220097666258651322015-05-14T08:34:00.001-05:002015-05-14T08:39:35.094-05:00Fiftieth Anniversary of the Publication of the seminal paper on Computational Complexity<table align="center" cellpadding="0" cellspacing="0" class="tr-caption-container" style="margin-left: auto; margin-right: auto; text-align: center;"><tbody>
<tr><td style="text-align: center;"><a href="http://1.bp.blogspot.com/-sMoKiQvVwB8/VVEMTLT-beI/AAAAAAAA2VQ/LMLeAxFklRg/s1600/GE.jpg" imageanchor="1" style="margin-left: auto; margin-right: auto;"><img border="0" height="281" src="http://1.bp.blogspot.com/-sMoKiQvVwB8/VVEMTLT-beI/AAAAAAAA2VQ/LMLeAxFklRg/s400/GE.jpg" width="400" /></a></td></tr>
<tr><td class="tr-caption" style="text-align: center;">Juris Hartmanis and Richard Stearns in a photo dated May 1963. The main theorem from their paper is on the board later improved by <a href="http://doi.acm.org/10.1145/321356.321362">Hennie and Stearns</a>. Photo courtesy of Richard Stearns.</td></tr>
</tbody></table>
The seminal paper of Juris Hartmanis and Richard Stearns, <a href="http://dx.doi.org/10.2307/1994208">On the Computational Complexity of Algorithms</a>, appeared in the Transactions of the American Mathematical Society in the May 1965 issue. This paper gave the name to the field of Computational Complexity which I took for the name of this blog. <a href="http://amturing.acm.org/award_winners/hartmanis_1059260.cfm">Hartmanis</a> and <a href="http://amturing.acm.org/award_winners/stearns_1081900.cfm">Stearns</a> received the Turing Award in 1993 for this work.<br />
<br />
I've mentioned this paper several times in the blog before, including as a <a href="http://blog.computationalcomplexity.org/2005/02/favorite-theorems-seminal-paper.html">favorite theorem</a>. Hartmanis and Stearns first formalized and truly popularized the idea of measuring time and other resources as a function the problem size, laying the foundation for virtually every paper in computational complexity and algorithms to follow.<br />
<br />
Both <a href="http://dx.doi.org/10.1109/MAHC.1981.10005">Hartmanis</a> and <a href="http://dx.doi.org/10.1007/978-1-4612-4478-3_2">Stearns</a> wrote about those early days. The main breakthroughs for their paper started in November 1962 and on December 31 Hartmanis wrote in his logbook "This was a good year," A good year indeed.Lance Fortnowhttps://plus.google.com/101693130490639305932noreply@blogger.com4tag:blogger.com,1999:blog-3722233.post-19819222115270369002015-05-11T07:59:00.000-05:002015-06-22T13:20:49.883-05:00The law of the excluded middle of the road republicans<br />
In the book <i>Hail to the Chiefs </i>about the presidents, when pointing to a race between two people who had no business being president (I think it was Franklin Pierce vs Winfield Scott) wrote something like <i>That's the thing about elections, someone has to win. </i><br />
<br />
<i> </i>Looking at the republicans running for the nomination I can (with the help of reading many of Nate Silver's Columns) tell you why, for each one, they can't win the nomination. Note that this is not a partisan thing. But again, someone has to win. Is it possible to have the statements<br />
<br />
A1 can't win AND A2 can't win AND .... AND An can't win<br />
<br />
and yet someone wins?<br />
<br />
Here is a list of the candidates and why they can't win.<br />
<br />
<ol>
<li>Jeb Bush is what passes for a front runner nowadays. Has the money, does not have the party (very few endorsements), and not doing well in polls in Iowa or New Hampshire, the first two states. Possibly because he does not hate Obama enough. Its an interesting question of whether the party, the people, or the money pick the candidate. In the past its been the party and the money together, but that might be changing. CAN"T WIN: Viewed as too moderate by the people who go to Caucus's. Also some people may be put off by the family name. THOUGHT: If H CLINTON was not the likely Democratic candidate, thus making the family name thing a less of an issue in the general, I don't think he would have run at all. </li>
<li>Marco Rubio. Running for president for the first time is hard. The republicans rarely nominate someone who hadn't run before (W in 2000, Ford in 1976 which is an outlier since he was prez). Perhaps the voters/party/money like someone they are familiar with OR perhaps first timers make mistakes. CAN"T WIN: Will make some mistake and some might think its not his turn since he's so young. Also, Senators have it rough since they sometimes vote for bills in funny ways, TRIVIA: The electoral college reps from state X cannot cast both the Prez and Veep vote for people both from state X. So you won't see a Bush-Rubio or Rubio-Bush ticket.</li>
<li>Rick Perry. He lost in 2012 because either he was too soft on immigrants (he supported some sort of Dream Act) or because of his Whoops moment in a debate. Frankly I have sympathy on that one--- I also sometimes forget which cabinet positions I want to get rid of. He has tried to cure both of his problems by flip-flopping (or evolving) on immigration and by wearing glasses so at least he looks smart. CAN"T WIN: His past failure makes him not look that serious this time around, and he will likely have another WHOOPS moment.</li>
<li>Scott Walker. Like Rubio but might be in better shape because he's a governor. Still, people in his home state are beginning to turn on him, a bad sign. He may soon have the same problem that Gov Brownback of Kansas has--- you promise to cut taxes, close loopholes, and cut spending, and that might actually be a good idea if done right, but you cut taxes , don't close loopholes, cut spending in stupid places like education, run up a big debt, destroy your states economy, and ... get re-elected. CAN"T WIN: Having not run before Walker will say something stupid. And as a gov of a moderate state I suspect some moderate things he did may be a problem for hard core republican voters.Plus his states current problems may be an issue.</li>
<li>Ted Cruz. Which of these quotes did Ted Cruz really say and which did I hear in some satirical setting (as a fan of The Daily Show, The Colbert Report, John Oliver's show, The Capitol Steps, others, I lose track of where I heard what) (1) <i>There was no ebola before Obamacare, </i>or (2)<i> Net neutrality is Obamacare for the internet.</i> I'll answer at the end of the post. He is now using Obamacare himself. . CAN"T WIN: A niche candidate with a small but loyal set of supporters. Not enough CAVEAT: Might be running to get some points of view out there like Adlai Stevenson and Barry Goldwater, though they got all the way to the nomination which I doubt he can. </li>
<li>Rand Paul. Interesting mathematically: an authenticity/electability tradeoff. Some people are attracted to his libertarianism, authenticity and consistency, but not enough to get him anywhere close to the nomination. So he changes some of his positions to be more mainstream but less libertarian, authentic, and consistent. Alas, those who trade their integrity for electability end up with neither. CAN"T WIN: His evolving views might lose him his base but not gain him any establishment cred. Also he has the chicken-egg problem in that even people who like him don't think he can win the general election. (Ted Cruz and others on this list may also have this problem.)</li>
<li>Mike Huckabee. Won't get much support beyond his Social Conservative base. His stance on Same Sex Marriage will hurt him outside of the social conservatives, especially in 2015 (as opposed to his last run in 2008). I'm surprised he's running- he got what he wanted from his last run, a show on FOX News. CAN"T WIN: Was a moderate on some economic and immigration issues (he may also `evolve' which won't work), a conservative on social issues, is just the wrong mix for current republican primary voters. Note that many candidates are trying to avoid the Same Sex Marriage question as they know that being opposed to it will hurt them in the general. Plus some don't want to be on the wrong side of history (or as the kids say WSOH) . Politics- sometimes you're forced to have a public opinion that you disagree with and know will make you be on the WSOH , but you're stuck with it. I think Huckabee is sincere in his opposition to same sex marriage but he must surely know he's on the WSOH.</li>
<li>Ben Carson. I suspect he is actually running to be a FOX News commentator. At that he might succeed. CAN"T WIN: First timer, never ran for anything, he'll be a curiosity not a candidate. Which of the following did he say: <i>(1) Obama is a sociopath (2) Obamacare is like slavery</i>. This may even hurt him with the Republican hard core who want someone who can win. CAVEAT: is being African-American going to help or hurt? I doubt his campaign will get far enough to tell. The other candidates and the debate panelists (in the sanctioned debates) will treat him with kid gloves to avoid being called racist.</li>
<li>Carly Fiorina. She said that our founding fathers did not intend there to be a political class, what we now call politicians. They intended for ordinary people (like the president of HP), for the good of their community, to serve in office. She left out that the founding fathers also did not intend for women to be president. CAN"T WIN: First timer, never ran for anything. (correction added later: She ran for Senator of Califorina. She got the nomination but lost to Incumbent Barbara Boxer.) CAVEAT: is being female going to help or hurt? I doubt her campaign will get far enough to tell. The other candidates and debate panelists (in the sanctioned debates) will treat her with kid gloves to avoid being called sexist. HER HOOK: She claims that as a women she can neutralize H Clinton' women-advantage in the general. Interesting that she is making an electability argument instead of a policy argument, given that she has no chance of being elected.</li>
<li>Chris Christie. CAN"T WIN: Hated inside of New Jersey. Hated outside of New Jersey.</li>
<li>Bobby Jindal. Once said the Republicans have to stop being the stupid party. Later said some stupid things about Muslims in America. CAN"T WIN: If he ran as the moderate sane voice who will rescue the party from itself, he might get some traction. If he runs as anything else he has too much competition. Also a first-time-runner which is hard. </li>
<li>Lindsey Graham. CAN"T WIN: Has worked with democrats which should be a PRO but it's a CON. </li>
<li>John Kasich. Gov of Ohio. CAN"T WIN: Not that well known. Democrats have nominated unknowns (B Clinton, B Obama) but republicans almost never do (W might count).</li>
<li>Donald Trump (ADDED LATER). Some people say that corporate America controls this country. If we make Donald Trump Prez we're just cutting out the middle-man. Won't get the nomination--- over half of republicans say they would never vote for him--- but his running is a fairwell gift to Jon Stewart.</li>
<li>Rick Santrum (ADDED LATER). Against Birth Control? Really? Google him to find other reasons he can't win. Odd thing- usually the person who came in second the last time around has a pretty good shot at getting the nomination this time around, but the fact that he came in second last time may be a sign of how weak the field was last time. </li>
<li>George Pataki (ADDED LATER) Would be at home in the deomocratic party. I want to see him callenge Hillary from the right. Oh, he's a republican? But he's pro-choice, pro-gay, anti-gun, and doesn't seem to hate Obama. </li>
<li>Rob Portman. (ADDED LATER) I saw him on a list of possible nominees. Not under `declared', not under `exploratory committee) (Chris Christee and Scott Walker are still exploring, which surprised me- I thought they already declared), but on a list of `No indication'. Not sure why he's on any list; however, as Rick Perry taught us last time (and this is not a joke) you need to start early. </li>
</ol>
<br />
There may be more (Donald Trump anyone? ADDED LATER- When I first posted this mentioning Donald Trump was supposed to be a joke. But political satire and reality may have finally merged with a reality-TV star running for Prez). But my point is that it seems like nobody can win, yet someone has to. Do you know other examples where A OR B OR C has to be true, yet none of A,B,C look plausible?<br />
<br />
I can phrase this another way:<br />
<br />
novices can't win (e.g., Ben Carson) AND first timers can't win (e.g., Mario Rubio) AND too moderate can't win (e.g., perecption of Jeb) AND unknowns can't win (e.g., John Kasich).<br />
<br />
They all can't be right, but looking at it `first timers' is prob the weak link in my reasoning. I could replace it with `inexperienced politician'. Even so, sure looks like nobody can win.<br />
<br />
Ted Cruz: Both of the quotes I attribute to him he really did say.<br />
<br />
I don't know Ben Carson's original quote but he backtracked to <i>Obama reminds you of a</i> <i>psychopath,</i><br />
which is much better than saying Obama IS a psychopath . But he never said sociopath, so the quote I gave is NOT from Ben Carson.<br />
<br />
On Obamacare he said <i>its the worst thing to happen in America since slavery. </i>But later<br />
opposite-of-backtracking said it was <i>in a way like slavery because it robs you of your ability to control your own life.</i><br />
<br />
<br />GASARCHhttp://www.blogger.com/profile/06134382469361359081noreply@blogger.com8tag:blogger.com,1999:blog-3722233.post-22793479942388396222015-05-07T06:30:00.000-05:002015-05-07T06:30:04.109-05:00The Virtuous CycleLast week we have a celebration of the new CS graduates at Georgia Tech where each graduating student says what their plans are for next year. Other than the few going to grad school, they all have great jobs but the difference I see this year is how many are staying in Atlanta. Any CS student who wants to stay in Atlanta can find a great job in Atlanta.<br />
<div>
<br /></div>
<div>
A large number of companies are moving their headquarters or established large facilities in the Atlanta area and the reasons they give almost always include the students and researchers at Georgia Tech. We're starting to grow a good start-up culture here as well. </div>
<div>
<br /></div>
<div>
Companies in Atlanta want our students and our research. That helps add to the prestige of Georgia Tech which in turn draws more companies. A virtuous cycle. A similar story is playing out in several other cities across the country and I even saw it in tiny but growing Bozeman where I visited Montana State earlier this week. Computer Science these days plays a major role if not the largest role in many of these industries.<br />
<br />
All this growth leads to challenges such as finding the people and resources to meet the growing demands. All told though a good problem to have.<br />
<br />
We don't want the success of the STEM fields to come at the expense of the rest of academics. It shouldn't have to be CS vs Classics, Physics or Philosophy. How we make it all successful will be the great challenge in higher education in the years to come.</div>
Lance Fortnowhttps://plus.google.com/101693130490639305932noreply@blogger.com1tag:blogger.com,1999:blog-3722233.post-44784240318615647772015-05-04T20:29:00.000-05:002015-06-12T14:40:36.702-05:00Sizes of DFAs, NFAs, DPDAs, UCFG, CFGs, CSLs.<br />
If A is a decider (e.g, DFA) or generator (e.g., CFG) then L(A) is the language that it decides or generates.<br />
<br />
The following are well known:<br />
<br />
L(DFA) = L(NDFA) ⊂ L(DPDA) ⊂ L(PDA) ⊂ L(CSL).<br />
<br />
We are concerned with the <i>size </i>of these devices. For a DFA and NDFA the size is<br />
the number of states, for a DPDA, PDA the size is the sum of the stack alphabet and the number of states, and for CSL its the number of nonterminals. <br />
<br />
If D and E are two classes of devices (e.g., DFAs and DPDAs) then <i>a bounding function for (D,E) </i>is a function f such that if L is recognized by both a D-device and an E-device, and L is recognized by an E-device of size n, then it is recognized by a D-device of size ≤ f(n). We abbreviate b-fun<br />
<br />
Readers of this column likely know that f(n)=2^n is a b-fun for (DFA,NFA) and prob know that this is tight. Below are some results that I suspect many readers don't know. Some of them may be suitable for inclusion in an undergrad theory class. In what is below ≤ means Turing-Less-Than-Or-Equal.<br />
<br />
<ol>
<li> <a href="http://www.cs.umd.edu/~gasarch/BLOGPAPERS/stearnspda.pdf">Stearns</a> showed that f(n) = n^{n^{n^{O(n)}}} is a b-fun for (DFA,DPDA).</li>
<li> <a href="http://dx.doi.org/10.1145/321864.321865">Valiant </a>improved this to double exp for a b-fun for (DFA,DPDA).</li>
<li> <a href="http://people.csail.mit.edu/meyer/economy-of-description.pdf">Meyer and Fischer</a> showed the 2^n lower bound for (DFA,NDFA). They also showed a lower bound of 2^{2^{O(n)}} for (DFA,DPDA). I think the question of closing the gap between Valiant's result and the Meyer-Fischer result is still open; however, if you know a ref please leave a comment.</li>
<li><a href="http://www.cs.umd.edu/~gasarch/BLOGPAPERS/valiantpda.pdf">Valiant</a> showed that the if f is a b-fun for (DPDA,UCFG) then HALT ≤ f.</li>
<li><a href="http://ecommons.library.cornell.edu/bitstream/1813/7319/1/76-277.pdf">Schmidt</a> showed that if f is a b-fun for (UCFG,CFG) then HALT ≤ f. </li>
<li><a href="http://www.cs.umd.edu/~gasarch/BLOGPAPERS/hartpda.pdf">Hartmanis</a> showed that if f is a b-fun for (DPDA,PDA) then HALT ≤ f</li>
<li><a href="http://www.cs.umd.edu/~gasarch/BLOGPAPERS/haypda.pdf">Hay </a> showed that if f is a b-fun for (DPDA,PDA) then f is NOT computable-in-HALT. </li>
<li><a href="http://arxiv.org/pdf/1503.08847v2.pdf">Beigel and Gasarch </a>prove a general theorem from which they obtain the following: (a) if f is a b-fun for (DPDA,PDA) then f ≤_INF. (It is easy to show that there exists a b-fun f ≤ INF for (DPDA,PDA) so the Turing degree is now precise), and (b) if f is a b-fun for (PDA,CSL) then SAME AS PART (a).</li>
</ol>
Results 3,4,5,6,7 can be restated in the following way--- we'll do result 6 as an example:<br />
<br />
<i>If f ≤ HALT then there exists infinitely many n such that there exists L_n such that (a) L_n is DPDA, (b) there is a PDA for L_n of size n, (c) any DPDA for L_n is of size at least f(n). </i><br />
<br />
<i> </i>Are there any ``for almost all n '' type bounds? There are but they are much weaker. The following theorems are from the Beigel-Gasarch paper pointed to above.<br />
<br />
<ol>
<li>For almost all n there exists a cofinite (hence DPDA) L_n that has a PDA of size O(n) but any DPDA for it has size 2^2^{n^{Ω(1)}}. </li>
<li>Same as point 1 but for PDA,CSL.</li>
</ol>
<br />
Both results 1,2 above use natural languages in that they are not created for the sole purpose of proving the theorem, no diagonalization (my spell check says thats spelled wrong but I think its spelled right). Using a construction Beigel-Gasarch obtained (Meyer probably had the result 40 years earlier with a diff proof, see the Beigel-Gasarch paper for historical details) that if f ≤ HALT then for almost all n there is a lang L_n such that L_n has a CSL of size n but any PDA for it is of size at least f(n). <br />
<br />
<br />
<br />
<br />
<ol>
</ol>
<br />
<br />GASARCHhttp://www.blogger.com/profile/06134382469361359081noreply@blogger.com1tag:blogger.com,1999:blog-3722233.post-71664435962178324242015-04-29T18:50:00.000-05:002015-04-29T18:50:48.696-05:00Is Logarithmic Space Closed Under Kleene Star?A Georgia Tech student asked the title question in an introductory theory course. The instructor asked his TA, the TA asked me and I asked the oracle of all things log space, Eric Allender. Eric didn't disappoint and pointed me to Burkhard Monien’s <a href="http://dx.doi.org/10.1007/3-540-07407-4_15">1975 theorem</a><br />
<blockquote class="tr_bq">
L is closed under Kleene star if and only if L = NL.</blockquote>
L here is the set of problems solved in deterministic O(log n) space and NL is the nondeterministic counterpart. For a set of strings A, <a href="http://en.wikipedia.org/wiki/Kleene_star">Kleene star</a>, denoted A<sup>*</sup> is the set of all finite concatenations of strings of A. For example if A = {00,1} then A<sup>*</sup> = {ε, 1, 00, 11, 001, 100, 111, 0000, 0011, 1100, …} where ε is the zero-length string.<br />
<br />
Kleene star comes up in regular expressions but also makes for many a good homework problem.<br />
<ol>
<li>Show that if A is in NL then A<sup>*</sup> is also in NL.</li>
<li>Show that if A is in P then A<sup>*</sup> is also in P.</li>
<li>Show that if A is c.e. (recognizable) then A<sup>*</sup> is also c.e.</li>
</ol>
Problem 1 above is equivalent to saying NL is closed under Kleene star and implies the “if” part of Monien’s result. Here is a simple proof of the other direction that L closed under Kleene star implies L = NL.<br />
<br />
Consider the following NL-complete problem: The set of triples (G,s,t) such that G is a directed graph with a restriction that all edges (i,j) have i<j and there is a path from node s to node t.<br />
<br />
Define the following language<br />
<blockquote class="tr_bq">
B = {G#i+1#G#i+2#...#G#j# | there is an edge (i,j) in G}</blockquote>
B is computable in log space and the string G#s+1#G#s+2#…#G#t# is in B<sup>*</sup> if and only if there is a path from node s to node t. QED<br />
<br />
Allender, Arvind and Mahajan <a href="http://dx.doi.org/10.1007/s00224-003-1077-7">give some generalizations</a> to log-space counting classes and also notes that there are languages computable in AC<sup>0</sup> (constant-depth circuits) whose Kleene star is NL-complete. B above is one such set.Lance Fortnowhttps://plus.google.com/101693130490639305932noreply@blogger.com9tag:blogger.com,1999:blog-3722233.post-29077361809870792092015-04-27T12:20:00.000-05:002015-04-27T12:20:40.782-05:00Advice on running a theory dayLast semester I ran a THEORY DAY AT UMCP. Below I have ADVICE for people running theory days. Some I did, some I didn't do but wish I did, and some are just questions you need to ask yourself.<br />
<br />
1) Picking the day- I had two external speakers (Avrim Blum and Sanjeev Arrora) so I was able to ask THEM what day was good for THEM. Another way is to pick the DAY first and then asking for speakers.<br />
<br />
2) Number of external speakers- We had two, and the rest were internal. The external speakers had hour-long talks, the internal had 20-minute talks. This worked well; however, one can have more or even all external speakers.<br />
<br />
3) Whoever is paying for it should be told of it towards the beginning of the process.<br />
<br />
4) Lunch- catered or out? I recommend catered if you can afford it since good time for people to all talk. See next point.<br />
<br />
5) If its catered you need a head count so you need people to register. The number you get may be off- you may want to ask when they register if they want lunch. Then add ten percent.<br />
<br />
6) Tell the guest speakers what time is good for them to arrive before they make plans so you can coordinate their dinner the previous night.<br />
<br />
7) If have the money and energy do name tags ahead of time. If not then just have some sticky tags and a magic marker.<br />
<br />
8) Guest speakers- getting them FROM Amtrak or Airport to dinner/hotel --- give them a personal lift (they may be new to the city and a bit lost). Getting them from the event back TO the airport or amtrak, can call airline limo and taxi. (though if can give a ride, that's of course good.)<br />
<br />
9) Pick a day early and stick with it. NO day is perfect, so if someone can't make it, or there is a faculty meeting that day, then don't worry about it.<br />
<br />
10) Have website, speakers, all set at least a month ahead of time. Advertise on theory-local email lists, blogs you have access to, and analogs of theory-local for other places (I did NY, NJ, PA). Also email people to spread the word.<br />
<br />
11) Advertise to ugrads. Students are the future!<br />
<br />
12) If you are the organizer you might not want to give a talk since you'll be too busy doing other things.<br />
<br />
13) Well established regular theory days (e.g., NY theory day) can ignore some of the above as they already have things running pretty well. <br />
<br />
<br />GASARCHhttp://www.blogger.com/profile/06134382469361359081noreply@blogger.com2tag:blogger.com,1999:blog-3722233.post-21642034489444041592015-04-24T06:20:00.000-05:002015-04-24T06:20:14.944-05:00Fifty Years of Moore's LawGordon Moore formulated his <a href="http://en.wikipedia.org/wiki/Moore%27s_law">famous law</a> in a <a href="http://www.cs.utexas.edu/~fussell/courses/cs352h/papers/moore.pdf">paper</a> dated fifty years and five days ago. We all have seen how Moore's law has changed real-world computing, but how does it relate to computational complexity?<br />
<br />
In complexity we typically focus on running times but we really care about how large a problem we can solve in current technology. In one of my <a href="http://blog.computationalcomplexity.org/2002/12/note-on-running-times.html">early posts</a> I showed how this view can change how we judge running time improvements from faster algorithms. Improved technology also allows us to solve bigger problems. This is one justification for asymptotic analysis. For polynomial-time algorithms a doubling of processor speed gives a constant multiplicative factor increase in the size of the problem we can solve. We only get an additive factor for an exponential-time algorithm.<br />
<br />
Although Moore's law continues, computers have stopped getting faster ten years ago. Instead we've seen the rise of new technologies: GPUs and other specialized processors, multicore, cloud computing and more on the horizon.<br />
<br />
The complexity and algorithmic communities are slow to catch up. With some exceptions, we still focus on single-core single-thread algorithms. Rather we need to find good models for these new technologies and develop algorithms and complexity bounds that map nicely into our current computing reality.Lance Fortnowhttps://plus.google.com/101693130490639305932noreply@blogger.com1tag:blogger.com,1999:blog-3722233.post-19035159363835680552015-04-22T08:47:00.003-05:002015-04-23T08:47:01.936-05:00The New Oracle Result! The new circuit result! which do you care about?You have likely heard of the new result by Ben Roco, and Li-Yang on random oracles (<a href="http://arxiv.org/abs/1504.03398">see here for preprint)</a> from either <a href="http://blog.computationalcomplexity.org/2015/04/ph-infinite-under-random-oracle.html">Lance </a>or <a href="http://www.scottaaronson.com/blog/?p=2272">Scott</a> or some other source:<br />
<br />
Lance's headline was <i>PH infinite under random oracle</i><br />
<br />
Scott's headline was <i>Two papers </i>but when he stated the result he also stated it as a random oracle result.<br />
<br />
The paper itself has the title<br />
<br />
<i>An average case depth hierarchy theorem for Boolean circuits</i> <br />
<br />
and the abstract is: <br />
<br />
We prove an average-case depth hierarchy theorem for Boolean circuits over
the standard basis of <span class="MathJax_Preview"></span><span class="MathJax" id="MathJax-Element-1-Frame" role="textbox"><nobr><span class="math" id="MathJax-Span-1" style="display: inline-block; width: 2.795em;"><span style="display: inline-block; font-size: 129%; height: 0px; position: relative; width: 2.153em;"><span style="clip: rect(1.405em, 1000em, 2.422em, -0.456em); left: 0em; position: absolute; top: -2.261em;"><span class="mrow" id="MathJax-Span-2"><span class="texatom" id="MathJax-Span-3"><span class="mrow" id="MathJax-Span-4"><span class="mi" id="MathJax-Span-5" style="font-family: MathJax_SansSerif;">A</span><span class="mi" id="MathJax-Span-6" style="font-family: MathJax_SansSerif;">N</span><span class="mi" id="MathJax-Span-7" style="font-family: MathJax_SansSerif;">D</span></span></span></span><span style="display: inline-block; height: 2.261em; width: 0px;"></span></span></span><span style="border-left: 0em solid; display: inline-block; height: 1.034em; overflow: hidden; vertical-align: -0.069em; width: 0px;"></span></span></nobr></span>, <span class="MathJax_Preview"></span><span class="MathJax" id="MathJax-Element-2-Frame" role="textbox"><nobr><span class="math" id="MathJax-Span-8" style="display: inline-block; width: 1.823em;"><span style="display: inline-block; font-size: 129%; height: 0px; position: relative; width: 1.4em;"><span style="clip: rect(1.384em, 1000em, 2.444em, -0.429em); left: 0em; position: absolute; top: -2.261em;"><span class="mrow" id="MathJax-Span-9"><span class="texatom" id="MathJax-Span-10"><span class="mrow" id="MathJax-Span-11"><span class="mi" id="MathJax-Span-12" style="font-family: MathJax_SansSerif;">O</span><span class="mi" id="MathJax-Span-13" style="font-family: MathJax_SansSerif;">R</span></span></span></span><span style="display: inline-block; height: 2.261em; width: 0px;"></span></span></span><span style="border-left: 0em solid; display: inline-block; height: 1.09em; overflow: hidden; vertical-align: -0.098em; width: 0px;"></span></span></nobr></span>, and <span class="MathJax_Preview"></span><span class="MathJax" id="MathJax-Element-3-Frame" role="textbox"><nobr><span class="math" id="MathJax-Span-14" style="display: inline-block; width: 2.795em;"><span style="display: inline-block; font-size: 129%; height: 0px; position: relative; width: 2.153em;"><span style="clip: rect(1.384em, 1000em, 2.444em, -0.396em); left: 0em; position: absolute; top: -2.261em;"><span class="mrow" id="MathJax-Span-15"><span class="texatom" id="MathJax-Span-16"><span class="mrow" id="MathJax-Span-17"><span class="mi" id="MathJax-Span-18" style="font-family: MathJax_SansSerif;">N</span><span class="mi" id="MathJax-Span-19" style="font-family: MathJax_SansSerif;">O</span><span class="mi" id="MathJax-Span-20" style="font-family: MathJax_SansSerif;">T</span></span></span></span><span style="display: inline-block; height: 2.261em; width: 0px;"></span></span></span><span style="border-left: 0em solid; display: inline-block; height: 1.09em; overflow: hidden; vertical-align: -0.098em; width: 0px;"></span></span></nobr></span> gates.
Our hierarchy theorem says that for every <span class="MathJax_Preview"></span><span class="MathJax" id="MathJax-Element-4-Frame" role="textbox"><nobr><span class="math" id="MathJax-Span-21" style="display: inline-block; width: 3.142em;"><span style="display: inline-block; font-size: 129%; height: 0px; position: relative; width: 2.422em;"><span style="clip: rect(1.405em, 1000em, 2.56em, -0.451em); left: 0em; position: absolute; top: -2.261em;"><span class="mrow" id="MathJax-Span-22"><span class="mi" id="MathJax-Span-23" style="font-family: MathJax_Math; font-style: italic;">d<span style="display: inline-block; height: 1px; overflow: hidden; width: 0.003em;"></span></span><span class="mo" id="MathJax-Span-24" style="font-family: MathJax_Main; padding-left: 0.278em;">≥</span><span class="mn" id="MathJax-Span-25" style="font-family: MathJax_Main; padding-left: 0.278em;">2</span></span><span style="display: inline-block; height: 2.261em; width: 0px;"></span></span></span><span style="border-left: 0em solid; display: inline-block; height: 1.212em; overflow: hidden; vertical-align: -0.247em; width: 0px;"></span></span></nobr></span>, there is an explicit
<span class="MathJax_Preview"></span><span class="MathJax" id="MathJax-Element-5-Frame" role="textbox"><nobr><span class="math" id="MathJax-Span-26" style="display: inline-block; width: 0.781em;"><span style="display: inline-block; font-size: 129%; height: 0px; position: relative; width: 0.592em;"><span style="clip: rect(1.657em, 1000em, 2.433em, -0.463em); left: 0em; position: absolute; top: -2.261em;"><span class="mrow" id="MathJax-Span-27"><span class="mi" id="MathJax-Span-28" style="font-family: MathJax_Math; font-style: italic;">n</span></span><span style="display: inline-block; height: 2.261em; width: 0px;"></span></span></span><span style="border-left: 0em solid; display: inline-block; height: 0.723em; overflow: hidden; vertical-align: -0.084em; width: 0px;"></span></span></nobr></span>-variable Boolean function <span class="MathJax_Preview"></span><span class="MathJax" id="MathJax-Element-6-Frame" role="textbox"><nobr><span class="math" id="MathJax-Span-29" style="display: inline-block; width: 0.712em;"><span style="display: inline-block; font-size: 129%; height: 0px; position: relative; width: 0.538em;"><span style="clip: rect(1.394em, 1000em, 2.627em, -0.429em); left: 0em; position: absolute; top: -2.261em;"><span class="mrow" id="MathJax-Span-30"><span class="mi" id="MathJax-Span-31" style="font-family: MathJax_Math; font-style: italic;">f<span style="display: inline-block; height: 1px; overflow: hidden; width: 0.06em;"></span></span></span><span style="display: inline-block; height: 2.261em; width: 0px;"></span></span></span><span style="border-left: 0em solid; display: inline-block; height: 1.313em; overflow: hidden; vertical-align: -0.334em; width: 0px;"></span></span></nobr></span>, computed by a linear-size depth-<span class="MathJax_Preview"></span><span class="MathJax" id="MathJax-Element-7-Frame" role="textbox"><nobr><span class="math" id="MathJax-Span-32" style="display: inline-block; width: 0.712em;"><span style="display: inline-block; font-size: 129%; height: 0px; position: relative; width: 0.538em;"><span style="clip: rect(1.405em, 1000em, 2.432em, -0.451em); left: 0em; position: absolute; top: -2.261em;"><span class="mrow" id="MathJax-Span-33"><span class="mi" id="MathJax-Span-34" style="font-family: MathJax_Math; font-style: italic;">d<span style="display: inline-block; height: 1px; overflow: hidden; width: 0.003em;"></span></span></span><span style="display: inline-block; height: 2.261em; width: 0px;"></span></span></span><span style="border-left: 0em solid; display: inline-block; height: 1.047em; overflow: hidden; vertical-align: -0.082em; width: 0px;"></span></span></nobr></span> formula,
which is such that any depth-<span class="MathJax_Preview"></span><span class="MathJax" id="MathJax-Element-8-Frame" role="textbox"><nobr><span class="math" id="MathJax-Span-35" style="display: inline-block; width: 3.976em;"><span style="display: inline-block; font-size: 129%; height: 0px; position: relative; width: 3.068em;"><span style="clip: rect(1.349em, 1000em, 2.672em, -0.39em); left: 0em; position: absolute; top: -2.261em;"><span class="mrow" id="MathJax-Span-36"><span class="mo" id="MathJax-Span-37" style="font-family: MathJax_Main;">(</span><span class="mi" id="MathJax-Span-38" style="font-family: MathJax_Math; font-style: italic;">d<span style="display: inline-block; height: 1px; overflow: hidden; width: 0.003em;"></span></span><span class="mo" id="MathJax-Span-39" style="font-family: MathJax_Main; padding-left: 0.222em;">−</span><span class="mn" id="MathJax-Span-40" style="font-family: MathJax_Main; padding-left: 0.222em;">1</span><span class="mo" id="MathJax-Span-41" style="font-family: MathJax_Main;">)</span></span><span style="display: inline-block; height: 2.261em; width: 0px;"></span></span></span><span style="border-left: 0em solid; display: inline-block; height: 1.429em; overflow: hidden; vertical-align: -0.392em; width: 0px;"></span></span></nobr></span> circuit that agrees with <span class="MathJax_Preview"></span><span class="MathJax" id="MathJax-Element-9-Frame" role="textbox"><nobr><span class="math" id="MathJax-Span-42" style="display: inline-block; width: 0.712em;"><span style="display: inline-block; font-size: 129%; height: 0px; position: relative; width: 0.538em;"><span style="clip: rect(1.394em, 1000em, 2.627em, -0.429em); left: 0em; position: absolute; top: -2.261em;"><span class="mrow" id="MathJax-Span-43"><span class="mi" id="MathJax-Span-44" style="font-family: MathJax_Math; font-style: italic;">f<span style="display: inline-block; height: 1px; overflow: hidden; width: 0.06em;"></span></span></span><span style="display: inline-block; height: 2.261em; width: 0px;"></span></span></span><span style="border-left: 0em solid; display: inline-block; height: 1.313em; overflow: hidden; vertical-align: -0.334em; width: 0px;"></span></span></nobr></span> on <span class="MathJax_Preview"></span><span class="MathJax" id="MathJax-Element-10-Frame" role="textbox"><nobr><span class="math" id="MathJax-Span-45" style="display: inline-block; width: 7.656em;"><span style="display: inline-block; font-size: 129%; height: 0px; position: relative; width: 5.922em;"><span style="clip: rect(1.403em, 1000em, 2.726em, -0.39em); left: 0em; position: absolute; top: -2.315em;"><span class="mrow" id="MathJax-Span-46"><span class="mo" id="MathJax-Span-47" style="font-family: MathJax_Main;">(</span><span class="mn" id="MathJax-Span-48" style="font-family: MathJax_Main;">1</span><span class="texatom" id="MathJax-Span-49"><span class="mrow" id="MathJax-Span-50"><span class="mo" id="MathJax-Span-51" style="font-family: MathJax_Main;">/</span></span></span><span class="mn" id="MathJax-Span-52" style="font-family: MathJax_Main;">2</span><span class="mo" id="MathJax-Span-53" style="font-family: MathJax_Main; padding-left: 0.222em;">+</span><span class="msubsup" id="MathJax-Span-54" style="padding-left: 0.222em;"><span style="display: inline-block; height: 0px; position: relative; width: 0.99em;"><span style="clip: rect(1.658em, 1000em, 2.433em, -0.45em); left: 0em; position: absolute; top: -2.261em;"><span class="mi" id="MathJax-Span-55" style="font-family: MathJax_Math; font-style: italic;">o</span><span style="display: inline-block; height: 2.261em; width: 0px;"></span></span><span style="left: 0.484em; position: absolute; top: -1.734em;"><span class="mi" id="MathJax-Span-56" style="font-family: MathJax_Math; font-size: 70.7%; font-style: italic;">n</span><span style="display: inline-block; height: 1.884em; width: 0px;"></span></span></span></span><span class="mo" id="MathJax-Span-57" style="font-family: MathJax_Main;">(</span><span class="mn" id="MathJax-Span-58" style="font-family: MathJax_Main;">1</span><span class="mo" id="MathJax-Span-59" style="font-family: MathJax_Main;">)</span><span class="mo" id="MathJax-Span-60" style="font-family: MathJax_Main;">)</span></span><span style="display: inline-block; height: 2.315em; width: 0px;"></span></span></span><span style="border-left: 0em solid; display: inline-block; height: 1.429em; overflow: hidden; vertical-align: -0.392em; width: 0px;"></span></span></nobr></span> fraction of all inputs must have size <span class="MathJax_Preview"></span><span class="MathJax" id="MathJax-Element-11-Frame" role="textbox"><nobr><span class="math" id="MathJax-Span-61" style="display: inline-block; width: 6.962em;"><span style="display: inline-block; font-size: 129%; height: 0px; position: relative; width: 5.383em;"><span style="clip: rect(1.152em, 1000em, 2.619em, -0.456em); left: 0em; position: absolute; top: -2.207em;"><span class="mrow" id="MathJax-Span-62"><span class="mi" id="MathJax-Span-63" style="font-family: MathJax_Main;">exp</span><span class="mo" id="MathJax-Span-64"></span><span class="mo" id="MathJax-Span-65" style="font-family: MathJax_Main;">(</span><span class="texatom" id="MathJax-Span-66"><span class="mrow" id="MathJax-Span-67"><span class="msubsup" id="MathJax-Span-68"><span style="display: inline-block; height: 0px; position: relative; width: 2.82em;"><span style="clip: rect(1.657em, 1000em, 2.433em, -0.463em); left: 0em; position: absolute; top: -2.261em;"><span class="mi" id="MathJax-Span-69" style="font-family: MathJax_Math; font-style: italic;">n</span><span style="display: inline-block; height: 2.261em; width: 0px;"></span></span><span style="left: 0.592em; position: absolute; top: -2.247em;"><span class="texatom" id="MathJax-Span-70"><span class="mrow" id="MathJax-Span-71"><span class="mi" id="MathJax-Span-72" style="font-family: MathJax_Main; font-size: 70.7%;">Ω</span><span class="mo" id="MathJax-Span-73" style="font-family: MathJax_Main; font-size: 70.7%;">(</span><span class="mn" id="MathJax-Span-74" style="font-family: MathJax_Main; font-size: 70.7%;">1</span><span class="texatom" id="MathJax-Span-75"><span class="mrow" id="MathJax-Span-76"><span class="mo" id="MathJax-Span-77" style="font-family: MathJax_Main; font-size: 70.7%;">/</span></span></span><span class="mi" id="MathJax-Span-78" style="font-family: MathJax_Math; font-size: 70.7%; font-style: italic;">d<span style="display: inline-block; height: 1px; overflow: hidden; width: 0.002em;"></span></span><span class="mo" id="MathJax-Span-79" style="font-family: MathJax_Main; font-size: 70.7%;">)</span></span></span><span style="display: inline-block; height: 1.884em; width: 0px;"></span></span></span></span></span></span><span class="mo" id="MathJax-Span-80" style="font-family: MathJax_Main;">)</span><span class="mo" id="MathJax-Span-81" style="font-family: MathJax_Main;">.</span></span><span style="display: inline-block; height: 2.207em; width: 0px;"></span></span></span><span style="border-left: 0em solid; display: inline-block; height: 1.614em; overflow: hidden; vertical-align: -0.392em; width: 0px;"></span></span></nobr></span> This
answers an open question posed by Hastad in his Ph.D. thesis.
<br />
Our average-case depth hierarchy theorem implies that the polynomial
hierarchy is infinite relative to a random oracle with probability 1,
confirming a conjecture of Hastad, Cai, and Babai. We also use our result
to show that there is no "approximate converse" to the results of Linial,
Mansour, Nisan and Boppana on the total influence of small-depth circuits, thus
answering a question posed by O'Donnell, Kalai, and Hatami.
<br />
A key ingredient in our proof is a notion of \emph{random projections} which
generalize random restrictions.<br />
<br />
Note that they emphasize the circuit aspect.<br />
<br />
In Yao's paper where he showed PARITY in constant dept requires exp size the title was<br />
<br />
<i>Separating the polynomial hiearchy by oracles</i><br />
<br />
Hastad's paper and book had titles about circuits, not oracles.<i> </i><br />
<br />
When Scott showed that for a random oracle P^NP is properly in Sigma_2^p the title was<br />
<br />
<i>Counterexample to the general Linial-Nissan Conjecture</i><br />
<br />
However the abstarct begins with a statement of the oracle result.<br />
<br />
SO, here is the real question: What is more interesting, the circuit lower bounds or the oracle results that follow? The authors titles and abstracts might tell you what they are thinking, then again they might not. For example, I can't really claim to know that Yao cared about oracles more than circuits.<br />
<br />
Roughly speaking the Circuit results are interesting since they are actual lower bounds, often on reasonable models for natural problems (both of these statements can be counter-argued), oracle results are interesting since they give us a sense that certain proof teachniques are not going to work. Random oracle results are interesting since for classes like these (that is not well defined) things true for random oracles tend to be things we think are true.<br />
<br />
But I want to hear from you, the reader: For example which of PARITY NOT IN AC_0 and THERE IS AN ORACLE SEP PH FROM PSPACE do you find more interesting? Is easier to motivate to other theorists? To non-theorists (for non-theorists I think PARITY).GASARCHhttp://www.blogger.com/profile/06134382469361359081noreply@blogger.com3tag:blogger.com,1999:blog-3722233.post-805317759709032632015-04-16T08:14:00.000-05:002015-04-16T08:14:04.261-05:00PH Infinite Under a Random OracleBenjamin Rossman, Rocco Servedio and Li-Yang Tan show <a href="http://arxiv.org/abs/1504.03398">new circuit lower bounds</a> that imply, among other things, that the polynomial-time hierarchy is infinite relative to a random oracle. What does that mean, and why is it important?<br />
<br />
The polynomial-time hierarchy can be defined inductively as follows: Σ<sup>P</sup><sub>0 </sub>= P, the set of problems solvable in polynomial-time. Σ<sup>P</sup><sub>i+1 </sub>= NP<sup>Σ<sup>P</sup><sub>i</sub></sup>, the set of problems computable in nondeterministic polynomial-time that can ask arbitrary questions to the previous level. We say the polynomial-time hierarchy is infinite if Σ<sup>P</sup><sub>i+1 </sub>≠ Σ<sup>P</sup><sub>i</sub> for all i and it collapses otherwise.<br />
<br />
Whether the polynomial-time hierarchy is infinite is one of the major assumptions in computational complexity and would imply a large number of statements we believe to be true including that NP-complete problems do not have small circuits and that Graph Isomorphism is not co-NP-complete.<br />
<br />
We don't have the techniques to settle whether or not the polynomial-time hierarchy is infinite so we can look at relativized worlds, where all machines have access to the same oracle. The Baker-Gill-Solovay oracle that makes P = NP also collapses the hierarchy. Finding an oracle that makes the hierarchy infinite was a larger challenge and required new results in circuit complexity.<br />
<br />
In 1985, Yao in his paper <a href="http://dx.doi.org/10.1109/SFCS.1985.49">Separating the polynomial-time hierarchy by oracles</a> showed that there were functions that had small depth d+1 circuits but large depth d circuits which was needed for the oracle. Håstad gave a <a href="http://dx.doi.org/10.1145/12130.12132">simplified</a> proof. Cai <a href="http://dx.doi.org/10.1145/12130.12133">proved</a> that PSPACE ≠ Σ<sup>P</sup><sub>i</sub> for all i even if we choose the oracle at random (with probability one). Babai later and independently <a href="http://dx.doi.org/10.1016/0020-0190(87)90036-6">gave a simpler proof</a>.<br />
<br />
Whether a randomly chosen oracle would make the hierarchy infinite required showing the depth separation of circuits in the average case which remained open for three decades. Rossman, Servedio and Tan solved that circuit problem and get the random oracle result as a consequence. They build on Håstad's proof technique of randomly restricting variables to true and false. Rossman et al. generalize to a random projection method that projects onto a new set of variables. <a href="http://arxiv.org/abs/1504.03398">Read their paper</a> to see all the details.<br />
<br />
In 1994, Ron Book <a href="http://dx.doi.org/10.1016/0020-0190(94)00157-X">showed</a> that if the polynomial-time hierarchy was infinite that it remained infinite relativized to a random oracle. Rossman et al. thus gives even more evidence to believe that the hierarchy is indeed infinite, in the sense that if they had proven the opposite result than the hierarchy would have collapsed.<br />
<br />
I <a href="http://dx.doi.org/10.1016/S0020-0190(99)00034-4">used</a> Book's paper to show that a number of complexity hypothesis held simultaneously with the hierarchy being infinite, now a trivial consequence of the Rossman et al. result. I can live with that.Lance Fortnowhttps://plus.google.com/101693130490639305932noreply@blogger.com4