Practical consequences of RH ?

When it seemed like Riemann Hypothesis (RH) might be solved (see Lipton-Regan blog entry on RH  here and what it points to for more info) I had the following email exchange with Ajeet Gary (not Gary Ajeet, though I will keep his name in mind for when I want to string together names like George Washington, Washington Irving, Irving Berlin,  with the goal of getting back to the beginning) who is an awesome ugrad at UMCP majoring in Math and CS.

Ajeet: So Bill, now that RH has been solved should I take my credit cards off of Amazon?

Bill: I doubt RH has been solved. And I think you are thinking that from RH you can prove that factoring is in P. That is not known and likely not true.

Ajeet: What are my thoughts and why are they wrong?

Bill: What am I a mind-reader?

Ajeet: Aren't you?

Bill: Oh, Yes, you are right, I am. Here is what you are confusing this with and why, even if you were right you would be wrong.

Ajeet: It just isn't my day.

Bill: Any day you are enlightened is your day. Okay, here are the thoughts you have

a) From the Extended RH (a generalization of RH) you can prove that PRIMES are in P. (This algorithm is slow and not used. PRIMES has a fast algorithm in RP that people do use. Primes was eventually proven to be in P anyway, though again that is a slow algorithm). Note- even though we do not know if ERH is true, one could still RUN the algorithm that it depends on. ERH is only used to prove that the algorithm is in P.

b) There was an episode of Numb3rs where they claimed (1) RH implies Factoring in P-- not likely but not absurd (2) from the proof of RH you could get a FAST algorithm for factoring in a few hours (absurd). I say absurd for two reasons: (i) Going from basic research to application takes a long time, and (ii) See next thought

c) If (RH --> factoring easy) then almost surely the proof would present an algorithm (that can be run even if RH has not been proven) and then a proof that RH --> the algorithm's run time is poly. But I wonder -- is it possible that:

RH--> factoring easy, and

The proof does not give you the algorithm, and

 if you had a proof  or RH then you COULD get the algorithm (though not in a few hours).

I doubt this is the case.

Ajeet: So are there any practical consequences of RH?

Bill: Would you call better bounds on the error term of the prime number theory practical.

Ajeet: YES!

Bill: GREAT! For more on RH see here

2018 Fall Jobs Post

As we do every year at this time, we help you find that perfect academic job. So who's hiring in CS this year? Perhaps we should instead follow the advice of John Regehr.

I said this last year and it's time to say it again:
to save time and energy, will the CS departments NOT hiring faculty this year please speak up?

— John Regehr (@johnregehr) September 28, 2018

For computer science faculty positions best to look at the ads from the CRA and the ACM. For theoretical computer science specific postdoc and faculty positions check out TCS Jobs and Theory Announcements. If you have jobs to announce, please post to the above and/or feel free to leave a comment on this post.

Even if you don't see an ad, almost surely your favorite university is looking to hire computer scientists. Check out their website or email someone at the department.

And (selfish plug) Georgia Tech is looking to hire in theory this year.

Some generally good advice: Make sure you have strong letter writers who know your research well, best if one or two of them come from outside your university. Put all your papers and materials on your website and make sure your Google Scholar page is accurate. Put effort into your job talk and remember you need to sell you research to non-theorists. Good if you can connect to other areas especially machine learning, data science or cybersecurity. Quantum seems hot this year.

Above all have fun! In this computational and data driven world we live in, there is a great job out there for you.

A New ACO Center (guest post by Vijay Vazirani)

Guest Post by Vijay Vazirani

                                                          A New ACO Center!

Last week, I helped launch an ACO Center (Algorithms, Combinatorics and Optimization) at my wonderful new home, UC Irvine. There are only two other such centers, at CMU and Georgia Tech (29 and 27 years old, respectively). My personal belief is that there will be more in the future. Let me justify.

When I joined Georgia Tech in 1995, my research was centered around approximation algorithms, a topic that resonated with its ACO Center. I was able to build on this interest in numerous ways:  by offering new versions of courses on this topic as new results emerged, attracting to GT, for the first time, a large number of top theory PhD students who went on to produce stellar results and start impressive careers of their own. Course notes accumulated over the years eventually lead my book on the topic in 2001. Right after that, I switched to algorithmic game theory, and again ACO became the center of that activity, this time resulting in a co-edited book which had a huge impact on the growth of this area. In short, ACO gave me a lot!  In turn, I believed in it and I worked for it wholeheartedly.

I still believe in ACO and I feel it is very much relevant in today’s research world. Similar to the other two ACOs, our Center at UCI also exploits the natural synergies among TCS researchers from the CS Department, probability and combinatorics researchers from the Math Department, and optimization researchers from the Business School. Additionally, our Center has grown well beyond these boundaries to include a highly diverse collection of faculty (e.g., from the prestigious  Institute for Mathematical Behavioral Sciences) whose common agenda is to utilize the “algorithmic way of thinking”, which is set to revolutionize the sciences and engineering over the course of this century, just as mathematics did in the last. The Center website has further details about its vision and activities.

Many universities are in a massive hiring mode today (especially in CS), e.g., UCI  plans to hire 250 new faculty over the next five years. Centers such as ours present the opportunity of hiring in a more meaningful manner around big themes. They can also be instrumental in attracting not only top students but also top faculty.

A center of excellence such as GT’s ACO does not simply spring up by itself; it requires massive planning, hard work, good taste and able leadership. For the last, I will forever be indebted to Robin Thomas for his highly academic, big vision, classy leadership style which was the main reason ACO remained such a high quality program for so long. Moving forward, will we stay with three ACO Centers or will there be more? I believe the latter, but only time will tell.

John Sidles, Mike Roman, Matt Howell, please email me/hard to get emails of people

John Sidles, Mike Roman, Matt Howell : please email me. at gasarch@cs.umd.edu (my usual email)

I need to ask you about some comments you left on the blog a while back (or emailed me -- I forget which, but I can't find your emails if you did email me). I need you to contact me SOON!

When you do I will tell you whats up and why I decline to say here what this is about.

For my other readers -- it is nothing controversial.


How hard is it to find people's emails on the web?

Sometimes it takes less than 5 minutes

Sometimes it is impossible.

Sometimes I get it by asking someone else who knows, or knows who to ask... etc.

It is rare that more time on the web helps. I do not think I ever spend more than 5 minutes and then found it. I have sometimes used linked-in. I don't have a Facebook account (I was going to put in a link to the latest Facebook privacy breach, but (1) by the time you read this they may have had another one, (2) you all know about it, and (3) when I typed in `Facebook Scandal' to Google I got the Facebook page for the TV show Scandal.)

Should people make their emails public? I can see why one does not want to. The old saying is that if you owe people money you want to be hard to find, but if people owe you money you want to be easy to find.

Contrast email to what people DO put online. A few years ago I needed someone's email address. I found his website. From his website I found out the exact day he lost his virginity. Okay... Didn't need to know that. But I still could not find his email address.  I later asked someone who asked someone etc. and got it. But I was struck by what was private and public. This is NOT a complaint (though I wish it was easier to fine email addresses) just an observation.

Google added years to my life

If you google

gasarch

you used to  get the following:   here

Please go there and notice how old they say I am.

Okay, you are back. You may have noticed that they say I am 68. Gee, I don't feel 68 (I feel younger).

I have no idea how Google got my age wrong.

0) I found about this when I saw my age in an article about the Muffin problem. The article is here. I had been in contact with the author earlier so it was easy to contact him, assure him that I appreciate his throwing scammers and spammers off of my trail by giving me the wrong age, but I wondered why he chose 68. He then apologized (which was not needed) and pointed me to the google thing.

1) My age was  not on my Wikipedia page. Nor was my birth year.

2) I do not recall every telling Google my age -- but then again, Google knows what I search for and perhaps deduced an incorrect age from that (I've been watching a very old Western, Maverick, lately, which may have fooled them. So my plan is working!)

3) Google thinks I published with Hilbert (see here or here) so that would make them think I am 68 years old. Hmm, still to young. If I was a 10-year old math genius in 1938 (Hilbert died in 1943 but since I am not a 68 year old math genius I chose numbers to make it easy) and published with
him then, then I would now be 80. Not 68. So that is not the answer.
(Side question- are any of Hilbert's co-authors still alive?)

Seriously, if anyone has any ideas why Google had it wrong, let me now

4) Lance was outraged at this and hence put my birth year on my Wikipedia page thinking that
would fix it. (I was not outraged, just amused.)

5) It was taken off my page since Lance couldn't prove it.

6) Lance and I  mentioned my age in a blog post and that was proof enough. So our blog is a primary
source. We should use this sparingly -- with great power comes great responsibility. (See here for more on that theme)

7) Other weird internet stuff: What does it take to get a Wikipedia Page? A Nobel Prize in Physics
helps. See: here.

Muffin Math

Lance: It's Friday afternoon and the Dagstuhl workshop has ended. We have some time before we need take off so how about one final typecast.

Bill: Always a good idea.

Lance: First the exciting news, Nitin Saxena won the Shanti Swarup Bhatnagar prize for 2018,

Nitin Saxena

according to the many Indians at Dagstuhl, the most prestigious science prize in the country. The awards were announced on Wednesday during the workshop. He's the S in AKS.

Bill: That's really impressive. He was only two-years old when AKS had log-depth sorting networks.

Lance: Bill, you moron. You're thinking of Ajtai-Komlós-Szemerédi. I'm talking Agrawal-Kayal-Saxena Primes in P, topic of my second ever blog post. Nitin, an undergrad at that time, didn't just sit on his laurels--he has had awesome results on algebraic circuit complexity that truly justify this prize.

Bill: Well congrats to Nitin. Moving on, let's talk math.

Lance: We're at Dagstuhl so we have to call it computer science.

Bill: Ronen Shaltiel gave a great but depressing talk, Indistinguishability by adaptive procedures with advice, and lower bounds on hardness amplification proofs.

Lance: Nobody sings the Dagstuhl Blues.

Bill: Suppose you had a hard function and want to covert it to a harder function, known in the biz as hardness amplification. For constant depth circuits we have hardness results but no known process for amplification. For larger classes, like constant depth circuits with threshold gates, we do know ways to amplify.

Lance: But we have not hardness results there? Where are you going with this?

Bill: Ronen put it nicely, "We can only amplify hardness where we don't have it". Ronen and his colleagues proved results along those lines. Lance, does that depress you.

Lance: Not as much as the sprained ankle that made me miss that talk. My turn to pick a favorite talk. I loved Michael Forbes Hitting Sets for the Closure of Small Circuits. You take algebraic circuits with a parameter epsilon and take the limit as epsilon goes to zero. Forbes and Amir Shpilka show a PSPACE algorithm to find small sets containing non-zeros of these functions. These kinds of functions are studied in the GCT approach to lower bounds.

Bill: What lower bounds is this aiming to solve?

Lance: Showing the computation difference between the determinant and the permanent.

Josh Alman: You've left out the most exciting part of the conference.

Bill and Lance: So Josh, what was that?

Josh Alman: The world debut debut performance of Stud Muffin and Smilin' Sam singing "Do You Work on Muffin Math?"

Lance: That awesome duo looks familiar Bill. Where I have seen them before?

Bill: That Sam can really tickle the ivories.

Lance: And Stud was definitely in the room.

Bill: On that note, take us out.

Lance: In a complex world, keep it simple.

Still Typecasting from Dagstuhl

Lance: Bill, in our typecast earlier this week I said you were older than me. But 68? You don't look day over 66.

Bill: Neither do you. But seriously, why do you think I'm 68?

Lance: I just Google'd "How old is Bill Gasarch?"

Bill: Don't believe everything you read on the Internet. I'm really 58.

Lance: Prove it.

Bill: Here's my driver's license.

Lance: Bill you don't drive. And it literally says "NOT A DRIVER'S LICENSE" on the back. But it is an official State of Maryland Identification card stating that you were born in 1959. Are you saying I should trust the state of Maryland over Google?

Bill: Yes, because they pay my salary. Back to Dagstuhl. Let's talk about the talks. William Hoza gave a nice talk about hitting sets for L (deterministic small space) vs RL (randomized small space)  but when I asked him when will we prove L = RL he said not for fifty years. Grad students are not supposed to be that pessimistic.

Lance: You mean realistic. Though I'd guess more like 10-20 years. I wouldn't even be surprised if NL (nondeterministic log space) = L.

Arpita Korwar: I say 10-15 years.

Bill: Can we put that in the blog?

Lance: Too late. Bill I heard you were the stud muffin this week.

Bill: Yes, I talked about the muffin problem. Got a problem with that?

Lance: Needed milk. I saw this talk two years ago and now you have cool theorems. Who would've thought if you have 24 muffins and 11 people you can allocate 24/11 muffins and the smallest piece is 19/44, and that's the best possible for maximizing the smallest piece.

Bill: I can't believe you actually listened to the talk and didn't fall asleep.

Lance: zzzzzz. Did you say something?

Bill: Never mind. Eric Allender talked about the minimum circuit-size problem: Given a truth-table of a function f is there a circuit for f less that a given size w. The problem is frustrated, just consider the following theorem: if MCSP is NP-complete then EXP does not equal ZPP (exponential time in zero-error probabilistic polynomial-time).

Lance: Do you think EXP = ZPP?

Bill: No, the result only tells us it will be hard to prove MSCP is NP-complete without informing us whether or not it is NP-complete. Allender did show that under projections it isn't NP-complete (Editor's Note: I should have said log-time projections see Eric's comment. SAT and all your favorite NP-complete problems are complete under log-time projections). MSCP might be complete under poly-time reductions but not under weaker reductions.

Lance: Reminds me of the Kolmogorov random strings that are hard for the halting for Turing reductions but not under many-one reductions.

Bill: Everything reminds you of the Kolmogorov strings.

Lance: As they should.

Bill: I liked Michal Koucký's talk on Gray codes.

Lance: Shouldn't that be grey codes. We're not in the UK.

Bill: It's the color you moron. It's named after Frank Gray.

Lance: You are smarter than you look, not bad for a 68 year old. I missed Koucký's talk due to a sports injury, but he did catch me up later.

Bill: I never put Lance and sports in the same sentence before.

Lance: And I never put Bill and driving together. It's a new day for everything. Koucký showed how to easily compute the next element in the Gray code querying few bits as long as the alphabet size is of size 3.

Bill: Which contrasts Raskin's 2017 paper that shows with a binary alphabet you need to query at least half the bits.

Lance: Hey you stole my line.

Bill: That's not possible. You are editing this. I think this typecast has gone long enough. Take us out.

Lance: In a complex world, best to keep it simple.

Lance and Bill go to Dagstuhl: The Riemann Edition

Lance: Welcome to our typecast directly from Dagstuhl in Southwestern Germany for the 2018 edition of the seminar on Algebraic Methods in Computation Complexity. Say hi Bill.

Bill: Hi Bill. So Lance are you disappointed we didn't go to Heisenberg for the Michael Atiyah talk claiming a solution to the Riemann Hypothesis.

Lance: I knew how fast I was going but I got lost going to Heisenberg. I think you mean the Heidelberg Laureate Forum a 100 miles from here. From what I heard we didn't miss much. For those who care here is the video, some twitter threads and the paper.

Bill: Too bad. When I first heard about the claim I was optimistic because (1) László Babai proved that graph isomorphism is in quasipolynomial-time at the age of 65 and (2) since Atiyah was retired he had all this time to work on it. Imagine Lance if you were retired and didn't have to teach or do administration, could you solve P vs NP? (This gets an LOL from Nutan Limaye)

Lance: I'll be too busy writing the great American novel. Before we leave this topic, don't forget about the rest of the Laureate Forum, loads of great talks from famous mathematicians and computer scientists. Why didn't they invite you Bill?

Bill: They did but I rather be at Dagstuhl with you to hear about lower bounds on matrix multiplication from Josh Alman. Oh, hi Josh I didn't see you there.

Josh: Happy to be here, it's my first Dagstuhl. I'm flying around the world from Boston via China to get here. Though my friends say it's not around the world if you stay in the Northern hemisphere. They are a lot of fun at parties. But not as much fun as matrix multiplication.

Bill: So Josh, what do you have to say about matrix multiplication. Is is quadratic time yet?

Josh: Not yet and we show all the current technique will fail.

Bill: Wouldn't Chris Umans disagree?

Kathryn Fenner: You shouldn't pick on Canadians [Ed note: Josh is from Toronto]. Pick on students from your own country.

Josh: (diplomatically) I think Chris Umans has a broader notion of what counts as known methods. There are some groups that aren't ruled out but we don't know how to use them.

Chris: Very well put. The distinction is between powers of a fixed group versus families of groups like symmetric groups. The later one seems like the best place to look.

Lance: Thanks Chris. Josh, what are your impressions of Dagstuhl so far?

Josh: I like the sun and grass. I wish it was easier to get here.

Lance: This is only the first day. You haven't even found the music room yet, past the white room, past the billiard room where Mr. Green was murdered with the candlestick. Oh hi Fred Green. Luckily Dr. Green is still alive. I remember my first Dagstuhl back in February of 1992.

Josh: Two months before I was born.

Lance: Way to make me feel old.

Bill: You are old.

Lance: You are older. Believe it or not six from that original 1992 meeting are here again this week: The two of us, Eric Allender, Vikaurum Arvind, Uwe Schöning and Jacobo Torán. Amazing how accents show up as we talk.

Bill: What did I sleep through this morning before Josh's talk?

Lance: Amnon Ta-Shma talked about his STOC 2017 best paper and Noga Ron-Zewi showed some new results on constructive list-decoding.

Bill: Let's do this again later in the week. Lance, takes us out.

Lance: In a complex world, best to keep it simple.