Friday, June 22, 2018

The Muffin Problem

I've been meaning to post on THE MUFFIN PROBLEM for at least a year. Its a project I've been working on for two years, but every time I wanted to post on it I thought.

I'm in the middle of a new result. I'll wait until I get it!

However, I was sort of forced to finally post on it since Ken Regan (with my blessing) posted on it. In fact its better this way- you can goto his post for the math and I get to just tell you other stuff.

The problem was first defined by Alan Frank in a math email list in 2009.

I'll  define the problem, though for more math details goto Ken's post:  here.

You have m muffins and s students. You want to give each student m/s piece and
divide the muffins to maximize the min piece. Let f(m,s) be the size of the min piece
in an optimal divide-and-distribute procedure.

Go and READ his post, or skim it, and then come back.

Okay, you're back. Some informal comments now that you know the problem and the math

1) I saw the problem in a pamplet at the 12th Gathering for Gardner. Yada Yada Yada I have 8 co-authors and 200 pages, and a paper in FUN with algorihtms You never know when a problem will strike you and be worth working on!
(The 8 coauthors are Guangiqi Cui, John Dickerson, Naveen Dursula, William Gasarch, Erik Metz,
Jacob Prinze, Naveen Raman, Daniel Smolyak, Sung Hyun Yoo. The 200 pages are here. The FUN with algorithms paper, only 20 pages, is here)

2) Many of the co-authors are HS students. The problem needs very little advanced mathematics (though Ken thinks it might connect to some advanced math later). This is a PRO (HS students can work on it, people can understand it) and a CON (maybe harder math would get us more unified results)

3) The way the research had gone is a microcosm for math and science progress:

We proved f(m,s) = (m/s)f(s,m)  (already known in 2009) by Erich Friedman in that math email list)

Hence we need only look at m>s.

First theorem: we got a simple function FC such that

f(m,s)  ≤ FC(m,s)

for MANY m,s we got f(m,s) = FC(m,s).

GREAT! - conjecture f(m,s) = FC(m,s)

We found some exceptions, and a way to get better upper bounds called INT.

GREAT! - conjecture f(m,s) = MIN(FC(m,s),INT(m,s))

We found some exceptions, and a way to get better upper bounds called ... We now have


f(m,s) = MIN(FC(m,s), INT(m,s), ERIK(m,s), JACOB(m,s), ERIKPLUS(m,s), BILL(m,s))

and it looks like we still have a few exceptions.

This is how science and math works- you make conjectures which are false but the refutations lead
to better and better results.

Also, we have over time mechanized the theorems, a project called:

Making Erik Obsolete

since Erik is very clever at these problems, but we would like to not have to rely on that.

4) I have worked hard on this problem as is clear from this: picture

Sunday, June 17, 2018

Its good to be mii

When I taught  ugrad  Elementary Theory of Computation (Reg, CFL, P, NP, Dec, c.e.) I made 5% of the grade be MEET THE PROF- come to my office, in groups of 3-6 (though sometimes I got 10) just to talk to me. I ask them what there plans are, why they took the course, and they get to ask ME what they want.

The most common question I got:

              Why is your mii the example of a mii on the Wikipedia entry on mii: here (permalink)

I was originally hesitant  to blog about this because (1) it may go away soon, and (2) I don't know.

But (1) its been there and stable for a while, and (2) I can speculate:

1) A prof in my department (not me) made and posted a Wikipedia page about me.

2) That page used the mii.

3) The powers that be at Wikipedia took down the mii (along with the list of my grad students who got PhD's).  This post is not a rant about this, but I will note that I think they should have allowed the mii since it looks like me. whenever I am going to meet someone at an airport I email them the mii and it always works.

4) Speculation: since it was on my Wikipedia page this mii was in the public domain and they could easily access it. Hence they used it. Is Wikipedia this arbitrary? Yes.

5) My darling thinks is unfair that the mii page can use my mii but my page can't. I just think its odd.

Thursday, June 14, 2018


Thanks to Grigory Yaroslavtsev for taking over the Theory Jobs Spreadsheet. Details on Grigory's blog. Check out who is going where next year.

My office has an awesome view of Midtown Atlanta. Midtown has seen considerable construction over the last decade and I get to see the skyline change before my eyes. NCR opened an impressive glass building for their new world headquarters just a few months ago not coincidentally a short walk from Georgia Tech. A few weeks ago I got a tour of this facility.

Most of the employees in the building do not get their own offices or desks. They have an open floor plan with hoteling. They use an app to reserve a desk up to a few weeks ahead of time. Each desk has a keyboard and two screens that they stick their laptops into. Their cell phones become their main phones. There are many conference rooms of different sizes, even some tiny ones meant for a single person to have a phone call or escape to some quietness.

Would hoteling work in the academic world? Never, you learn quickly that professors will never give up two things: their office or their parking. When we do talk about hoteling, we talk about a shared office for people who have a main office in a different building.

With faculty who often travel at far too many conference, or on some days working out of home or coffee shops and rarely using the books in their office, if they have them at all, why do we stick to the old fashioned offices?

The best academic research require collaboration, between faculty, students, postdocs and other researchers. The best times I've had as a professor is when a student or colleague walks into my office with a question, an idea or sometimes a proof. Better if I have some place to be found and not just a location in an app.

I'd also miss the view. 

Monday, June 11, 2018

How the Villarino-Gasarch-Regan paper came about

(This post overlaps a prior one here. The paper I am blogging about was also blogged about by Lipton here. The paper itself is on arxiv here. My slides for a talk I will be giving on this material are here)'

Todays post is on how the paper came about. A later post will be about why someone else didn't do it earlier.

How this paper came about:

Many years ago Bill noticed that while several books on Ramsey theory (see my prior post for quotes) state that the HCL was the first Ramseyian theorem. I think one source mentioned in passing that Hilbert used it to prove the Hilbert Irreducibility theorem (HIT). Bill could not find a modern English exposition of the proof.  So he asked Ken Regan (who not only knows German but can recite The Lewis Carol Poem Jabberwocky in German!) to translate it, and then Bill would put it in modern language, and there would be an exposition. Bill got bogged down in some of the math, and they both got bogged down with other things (For Ken catching chess-cheaters, for Bill mentoring HS students, for both of them, blogging.) Many years passed.

Sometime before 2015 Larry Washington showed me a nice proof that (ignoring mult constants)

∑ 1/p ≤ ln(ln(n)) + O(1) (the sum is over all primes p ≤n )

Read that carefully. There are many proofs in the web that the sum isat least  ≥ ln(lg n) but I could not find any that the sum was ≤ ln(ln n).  Larry Washington told me that the result and
the proof were not new. I told him that, even so, it doesn't seem to be out there. So we agreed to write and and post to arXiv but not publish in a journal. It's here.

This arXiv paper caught the attention of Mark since he had an exposition of Merten's proof  see here that that sum diverges. Mertens proof had explicit bounds which are missing from modern proofs.

I got into an email discussion with Mark about Math and History and I casually mentioned that Ken and I had worked on-and-off on HRL and HIT.  A few weeks later he emailed me a translation of the paper.  WOW! We worked together on polishing it, combining it with what Ken had done, and later brought Ken back into the project. I say without embarasment that we NEEDED Mark to resolve some of the issues we had and push the paper out the door. A Win-Win-Win.

And a lesson here--- Larry Washington was reluctant to publish on arXiv a paper on stuff that was already known. I should have told him

But Larry, if we do that I might find someone to help me finish the Hilbert paper

In a word: Serendipity.

Wednesday, June 06, 2018

I tell my class that P is important because... but is that really true?

When teaching P vs NP  the questions arises (and if not then I bring it up) what if you have algorithm in P that takes n^{100} time?. Or even n^{5} time which might be too long.

I have given the following answers for years; however, I post this and will use your comments as a sanity check. In fact, I suspect I am wrong on some points.

1) IF SAT was in P then something very clever was done. Even if its n^{100} it was very clever. That cleverness will almost surely result in other better algorithms. They may only be better in practice by not in theory (it works in practice- if only we can get it to work in theory :-) ), but it will still work and be a great advance.

2) IF SAT was in P then perhaps we could USE SAT in P to get a better algorithm for SAT in P. This was the theme of a chapter in Lance Fortnow's book The Golden Ticket: P, NP. and the search for the impossible and is also likely behind something I once heard (I think it was from Scott but I can't find it on his blog)  If P=NP then math would be easy and we would have already found a proof that P=NP. Hence P ≠ NP

The two above really can't be WRONG or even RIGHT or even NOT EVEN WRONG since they are speculations. The next few is where I need my sanity checked

3) Whenever a real world natural problem is in P it has a low degree poly algorithm OR there are ideas to make it work in practice, if not in theory. When Lance read a prior version of this post he pointed out that `real world natural problem' is not a well defined term. True. Not sure what to do about that. Even so, is this true? roughly true? Something theorists say to be able to sleep at night?

4) In the real world people say ``OH- the problem is NP-complete. Better look for approx solutions instead''  Or similar things. While this sounds true since I have never worked in the real world I really don't know. Is that what people say? do?

5) If Lance proves P=NP next week then the consequences are enormous for real people working on real computing problems. But what if Lance proves P NE NP? Would that affect people working on real computing problems? A long time Carl Smith told me If P NE NP was proven then the proof would have great insight into computing which would have a real affect on real people working on real computing problems. My Darling (who is a Software Engineer) is skeptical of that. What do you think?

Friday, June 01, 2018

BQP not in the Polynomial-Time Hierarchy in Relativized Worlds

The quantum complexity world is a rocking with the paper released yesterday by Ran Raz and Avishay Tal, Oracle Separation of BQP and PH, resolving a question open since quantum complexity got its start over two decades ago. Scott Aaronson's 2010 paper that sets some of the groundwork for the Raz-Tal result gives a nice overview of the question.

All of you readers should be familiar with the P v NP question. P is the set of problems efficiently solvable by a deterministic computer. NP are the problems for which there exists a witness that we can verify quickly. The polynomial-time hierarchy (PH) is the constant alternation generalization of NP that has played a major role in computational complexity So why don't we talk about the P vs PH question? That's just equivalent to P vs NP.

BQP is the the class of problem efficiently solved by a quantum computer. Since P sits in BQP which sits in PSPACE we can't prove outright any separations for BQP without separating P from PSPACE. We can though get an understanding of complexity by allowing the machines access to the same oracle and seeing what we can separate. We already knew BQP doesn't sit in NP relative to an oracle. Same was true for BPP (efficient probabilistic computation) but BPP is in PH for all oracles as are constant round interactive proofs. So we might expect we can have BQP in PH, BQP solvable with constant alternations, relative to all oracles. Raz and Tal refute that hypothesis.

Raz and Tal's proof builds on the Forrelation concept developed by Aaronson (under the name Fourier Checking) and extended by Aaronson and Ambainis. The oracle isn't complicated: Pick n numbers x1,...,xn each xi chosen from a normal distribution with mean 0 and variance a small ε > 0. Let y=y1,...,yn be the Hadamard transform applied to x1,...,xn. You then probabilistically round the x's and y's to 1 or -1. A quantum machine can distinguish this distribution from uniform using the fact that quantum machines can do Hadamards easily and Raz and Tal use Fourier show that low-depth alternating circuits (that capture PH) can't distinguish so easily. The paper is well-written if you want details.

A few questions for further directions:
  • Can you show a relativized world where P = NP (=PH) but P ≠ BQP? I'd suspect it will be a messy but not too hard generalization of this paper.
  • How far can you push the Raz-Tal result, i.e., for what function f(n) can we show that BQP cannot be solved by f(n)-alternating polynomial-time Turing machines. Can you show f(n) = nΩ(1)?
Also see Scott's personal take on this new result.

Thursday, May 31, 2018

Seventh Grade Math Contest

I stumbled upon an old blog post on the Lesswrong weblog that quotes several famous mathematicians  on the connections, or lack thereof, between mathematics competitions and mathematics research. Let me tell you how a seventh grade math contest altered the course of my life.

In 1975 I attended seventh grade in a middle school in upstate New Jersey. The school divided the students into three tracks, honors, standard and remedial, and I was an unexceptional student in the standard track. We all took a math pretest to determine who would represent the school in a state-wide competition. To everyone's surprise, especially my own, I killed on the test scoring twice as many points as anyone else. The school adjusted my course schedule but because of my not-so-great English skills I became the only student taking honors math and science and standard English and History (with a racist history teacher but that's another story). I think I came in 12th in the state competition.

I never did well in math contests after that, doing okay but not particularly strong in high school competitions. But the experience drove me to what we now call STEM. I got involved in computers and math in high school which led me to study engineering, briefly, at Cornell. I did make the Putnam team as a freshman at Cornell, but scored a zero which pretty much ended my career in math competitions.

Wednesday, May 30, 2018

Why is someone emailing me an offer to apply to be chair?

I recently go the following email (I blocked out identifying information of who send it and what college is involved. I doubt I needed to legally but... you never know.) I include my comments on the email in cap letters.

I am NOT flattered by the email. I have LESS regard for those who send it.

I will say that the school is respectable and I had heard of them. I'm just surprised they heard of me.

(The letter was typeset fine- if there are problems with typesetting below thats on me.)

Dear Dr. Gasarch,

XXX Inc. has been retained to assist XXX University in the search for the
next Chair of the Computer Science and Engineering Department.


Your expertise and accomplishments have come to our attention, and we would appreciate the opportunity to speak with you about this position.




Could you suggest some times over the next week that
might work for your schedule? We will be very respectful of your time.

XXX is located in XXX, XX where the city’s diverse and growing population puts it in the
Top 10 U.S. cities in population and in the Top 5 fastest growing cities. XXX has an endowment of $1.5B and recently completed a $1.3B campaign. The Computer Science and Engineering Department has been targeted for significant advancement and new faculty hires. The next Department Chair will lead and direct this enhancement.

The XXX Metroplex is a dynamic region with leading high-technology companies in the aerospace,
defense, energy, information technology, life sciences, semiconductors, telecommunications,
transportation, and biomedical industries. Some of the top companies and research institutes with a strong presence in the XXX area include LONG LIST OF COMPANIES I HAVE HEARD OF.


Please click here to view a two-minute video in which the President, Provost, and Dean of the
XXX School of Engineering at XXX discuss some of the possibilities for research and growth
that the Chair of Computer Science and Engineering will have the opportunity to develop.
Cybersecurity, particularly, is an identified area for growth and hiring to directly complement the XXX Institute for Cyber Security. A full listing of the qualifications and duties of the position can be found in the profile under “Current Searches” at XXX




So why did they email me? Speculation

1) They meant to email Lance and got confused.

2) They cast a VERY wide net. The UPSIDE of doing that so is that they might find someone
they would have overlooked. The DOWNSIDE of doing that is... thats the problem with
spam- there is absolutely no downside.

3) They emailed every computer science professor who has a wikipedia page? a blog? a book?
Some criteria which I happened to fit.