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.

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.

ADMIN EXPERIENCE: RUNNING AN REU PROGRAM. NOT NEARLY ENOUGH.

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

IF THEY MEAN ADMIN-EXPERTISE, THATS JUST SILLY.

IF THEY MEAN PAPERS AND SUCH... LETS JUST SAY I AM ON THE OBSCURE END OF THEORY AND WONDER WHAT ACCOMPLISHMENTS THEY MEAN. MY MUFFIN PAPER?

EXPERTISE: MENTORING HS AND UGRAD STUDENTS. BLOGGING? EXPERT OR NOT I"VE DONE IT FOR A WHILE. NOT THE STUFF OF CHAIR'S.

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.

THESE LAST TWO PARAGRAPHS WOULD BE A LOT MORE IMPRESSIVE IF I DIDN"T KNOW THEIR WAY TO PICK CANDIDATES TO ASK TO APPLY WAS SO TERRIBLE.

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

CYBERSECURITY- I HAVE TAUGHT A 1-CREDIT MINI-COURSE IN CRYPTO. I HAVE A SURVEY AND A PAPER ON PRIVATE INFO RETRIEVAL. I DOUBT THAT'S WHY THEY CONTACTED ME.


Best,

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.

Kolmogorov Complexity and Causation

I got an interesting email question.

Suppose I give you a set of points S of the form (x,y). He suggested ideally they would be pairs of a real numbers. Supposing there is a causal relationship between x and y of some kind, we want to know know if it is more likely that the x value causes the y value or the y value causes the x value. One plausible way to decide what the answer should be is by answering the question is the length of the shortest program which maps the x values to their y values shorter than the length of the shortest program which maps the y values to their x values.

So, my intuition says that this is clearly undecidable. I'm actually having a hard time thinking of a proof, so do you happen to know of one or if this problem might actually be decidable?

On a related note, since I'm already writing you about this question, do you happen to know about the complexity of any related questions which involve circuit size instead of program length? 

Let's use notation from Kolmogorov complexity, letting C(x|y) be the size of the smallest program that takes y as input and outputs x. Now suppose it is decidable to determine whether C(x|y) > C(y|x). Then find an x of length n such that for all y of length n/3, C(x|y)>C(y|x). Such x exist: For any random x, C(x|y)>= 2n/3 and C(y|x) <= n/3.

Now I claim C(x)>=n/4 for the x you found. If not we have C(x|y)<=C(x)<n/4 but for some y, C(y|x)>=n/3 since there aren't enough shorter programs to cover all the y's.

Since there is no computable procedure to find x such that C(x)>=n/4, there can't be decidable procedure to determine whether C(x|y) > C(y|x).

But does this question relate to causality. Pick a random x from strings of length n and y at random from strings of length n/3. We have C(x|y) >  C(y|x) even though there is no causality.

Instead you could look at the information of y in x, how many bit of x does y help describe, defined by I(y|x) = C(x)-C(x|y). This measure correlation since I(y|x)=0 iff x and y are independent but symmetry of information gives I(y|x)=I(x|y) so no hope for causation.

In short, Kolmogorov complexity won't give you much on causation--you can't avoid the controlled experiments.

For your last question, there is a notion of Kolmogorov complexity that roughly corresponds to circuit size, KT(x|y) defined as the sum of the program size and running time minimized over all programs p that take y as an input and output x. I'm guessing it's hard to determine if KT(x|y) < KT(y|x) and you could probably show it under some assumption like secure psuedorandom generators. Also symmetry of information isn't believed to hold for KT complexity so maybe there is something there. Interesting questions.

COMPUTER PROOF vs computer proof- Quadratic VDW theorem

Quad VDW Theorem: For all c there exists W=W(c) such that for all c-colorings of {1,...,W} there exists a,d such that a and a+d² are the same color.

What is known about W(c)?

The first proof of Quad VDW was nonconstructive.

The second proof was constructive but used VDW's theorem and gave terrible bounds, even for W(2).

EASY: Show W(2)=5

ON A HS MATH COMP: Show that for all 3-colorings of {1,...,2003} there exists two numbers a square apart that are the same color.

One can get a bound less than 100.

With a lot more detailed work one can get W(3)=29.

None of above was done with a computer.

SO- what about W(4)?  There are three proofs that W(4) exists:

a) Prove the QUAD VDW theorem. This gives terrible bounds.

b) I had some students use SAT solvers and they obtained W(4)=58. I am sure they are right and I am glad to know it (especially since it confirms the general mantra that the bounds from proofs in Ramsey theory tend to be much bigger than the reality) but its somehow unsatisfying. I want a HS proof. I wanted to put it on the MD Math Comp for 2017 but wiser people prevailed.

c) I gave the problem to a Grad Student Zach Price and he came up with a HS proof-- sort of.  Look at the following graph: here.  It shows that in any 4-coloring of N which does not have two numbers a square apart the same color:

COL(x) = COL(x+290085289)

from this one can obtain

W(4) ≤ 290085289²  (which is MUCH better than the bound from the proof of Quad VDW) and hence a proof of QVDW that does not need a program, except that to FIND this gadget used a program.  I doubt a HS student could do this on an exam.

Is Zach's proof the HS proof I am looking for?

PRO- once you see it its easy to verify and does not need a program.

CON- coming up with it needed a program.

More to the point: which proof do you like better:

1) The SAT Solver proof.  Not a proof you can see or feel, but gives exact bounds.

or

2) Zach's gadget proof. Much worse bound but you can see and feel the proof, and verify it after you know the gadget.

I prefer Zach's proof.

The Complexity of the Firm

In 1937, a year after Turing had his seminal paper, Ronald Coase published a paper The Nature of the Firm to give a framework to why we have companies and how large they become. In a perfect market economy we shouldn't need a firm at all, everyone is just an independent contractor and market pricing will drive efficient use of labor. Coase notes there are costs to creating contracts and one can gain efficiencies by avoiding these contracts by having both parties inside the same organization.

Much of those costs come from complexity, it is impossible to create a contract to cover all possible outcomes and thus contracts are incomplete leading to loopholes and lawsuits.

In the other direction, having the central organization of a firm has its own costs, from inefficiencies from not using markets to balance supply and demand, to the complexity of the organization processes themselves. In Coase's model, a firm grows to a size that balances the organization and contract costs at the margin.

So what happens to the sizes of firms when we reduce complexity, as happens with modern computing, from better communication, optimization and data analytics. We see relatively new companies like Google and Amazon getting larger. We also see a number of startups and small companies with very few workers, sometimes just one.

Computing drops both the cost of central organization and the cost of contracts so the size of a firm depends on circumstance. One can have a tech startup with a small number of workers since they can write apps that run on other people's platforms (like web browsers and on phones) and have the processing done on the cloud where they can scale or not scale as needed. Meanwhile a large company can more easily coordinate and connect using modern technology making it cost efficient to expand.

As we enter a new age of machine learning and automation, how will that affect the very nature of companies in the future? How about universities, a special kind of firm in itself? How can we harness the tools and ideas from computational complexity to help understand these and other societal changes.

What does it mean for a student to guess an answer?

On my final in Aut Theory I wanted to ask a TRUE/FALSE/UNKNOWN TO SCIENCE
question but did not want them to guess. Hence I had +4 for a right answer, -3 for a wrong answer.
Here is the question:

------------------------------------------------------------------------------------------
For each of the following say if its TRUE, FALSE, or UNKNOWN TO SCIENCE. No Proof Required BUT you get +4 for every right answer and -3 for every wrong answer and 0 for an answer left blank. So

                DO NOT GUESS!!!!!!!!!!!!!!!!!!!!!!!!!!!

a) If A is regular and F is a finite set then A UNION F is regular.

b) If A is in P and F is a finite set then A UNION F is in P.

c) If A is in NP and F is a finite set then A UNION F is in NP.

d) If A is decidable and F is a finite set then A UNION F is decidable.

e) If A is undecidable and F is a finite set then A UNION F is undecidable
-------------------------------------------------------------------------------------------------

Note that they are all TRUE. A student who (as many did) answered T-T-T-T-F had the following conversation with me:

BILL: You guessed! I told you DO NOT GUESS!!!!!!!!!!!!

STUDENT: No. I REASONED that you would not make them all T, so by this reasoning the last one had to be F. I now see that my reasoning is wrong--- you would make them all T, but it was not guessing, it was reasoning.

                I claim the student was guessing, he claims he was not. What do you think?

Having said that, the following IS a rational strategy:

If I don't know the answer but it has nothing to with P vs NP then it has to be T or F. In this case guess since exp val is positive.  If the answer has to do with P vs NP then do not guess.

This also raises a question- if they honestly thought (say) e was F I want to just give them 0,  whereas if they are guessing or using reasoning about `Bill wouldn't ...' I want to give them -3. But alas, we cannot read their minds or souls.

Richard Feynman (1918-1988)

When I took cryptography from Manuel Blum, he handed out copies of the chapter "Safecracker Meets Safecracker" from Richard Feynman's book Surely You're Joking Mr. Feynman. Feynman, the Nobel Prize winning physicist who was born a hundred years ago today, wrote this book not about physics but just a series of stories from different times in his life. This chapter described how Feynman learned how to open locked safes in Los Alamos during the Manhattan Project.

We all have interesting stories to tell but Feynman finds a way to keep things compelling in a way most scientists could not--even if he sometimes comes off being a bit of a jerk, hence the title. This book inspired me to tell my own stories which occasionally show up in this blog.

His most important stories form The Feynman Lectures on Physics (free to read online), an amazing explanation of deep physical concepts.

Richard Feynman's biggest contribution to theoretical computer science comes from a 1981 keynote address.

What kind of computer are we going to use to simulate physics? The full description of quantum mechanics for a large system cannot be simulated with a normal computer. And therefore, the problem is, how can we simulate the quantum mechanics? Can you do it with a new kind of computer—a quantum computer?

which begat a proof-of-concept paper by David Deutsch and Richard Jozsa which begat Daniel Simon's exponential separation which begat Peter Shor's factoring algorithm which begat billions of research dollars and considerable expectations, real and imagined, for Feynman's vision.

Second of N posts on G4G13. Maybe

(Don't forget to vote for SIGACT posistions:here  9th workshop on Flexible network design, May 22-25 at College Park, here.)

My first poston G4G13 is arguably here. To see why its debatable, see that post.

FOXTROT HALF-EMPTY, HALF-FULL PROBLEM, INCLUDING 13 by Thomas Francic Banchoff

In a Foxtrot cartoon (see here) Foxtrot has a glass which looks like it is half-full (or half-empty)
and asks people if its half-full or half empty. But the jokes on them!
The class is slightly angled so its actually 5/12 full (or 7/12 empty)
Given the area of the top and bottom What is the angle?
Generalize to other dimensions.

--------------------------------------

HEX PRIMES by Spandan Bandyopadhyay

Here is an alternative definition of primes that
lends itself to a generalization.

A number x is PRIME if when there is a rectangle with
integer sides and area x, one of the sides is 1.

Lets generalize this!

A number x is TRIPRIME if when there is a triangle with
integer sides of area x, one of the sides is 1.

Rather than use these prefixes we will go with

A number x is n-PRIME if when there is a convex n-gon with
integer sides and area x, one of the sides is 1.

HEXPRIMES are of course 6-primes.

The problem with 5-minute talks (maybe it should have been 6 minutes)

is that the concept is intersting but I didn't get to hear much

about them. And I could not find a paper on line. Note that this

conference has many non-academics for whome PAPERS are not the

basic currency so things are more informal. This is GOOD in that

its more of a free-for-all, but bad for follow up.

ALL of G4G12's are on You-Tube, so when that happens for G4G13,

I can follow up on this.

One thing I did manage to write down- 7 is the first HEX-composite.

Broader Impacts Redefined

The ACM Future of Computing Academy suggests that "peer reviewers should require that papers and proposals rigorously consider all reasonable broader impacts, both positive and negative." Here is the broader impacts section of a future imagined grant proposal.

My latest cryptocurrency paper will allow people to sell all sorts of paraphernalia, illegal, immoral and fattening, while avoiding paying taxes. Dr. Evil and his minions can move money around the world anonymously to more easily implement their dastardly plans. With this new work bitcoin will increase in value, causing far more mining setups that will deplete the energy resources of the world.

Since I already own bitcoin, I will get filthy rich, increasing the gap between the one-percenters and the middle-class. I'll buy a fancy car and reprogram the auto-pilot to run over people who get in my way. And all those pesky bicyclists clogging the roads. That would be a positive impact.

For the rest of humanity my new quantum gravitation algorithm will put all those people out of work. But their misery will be short lived because if anyone tries to run the algorithm, it may cause a small black hole that devours the earth.

My proposed generic oracle separation would seem to have no impact whatsoever. But what happens if an alien race threatens to destroy the planet unless we find such a separation. I will have saved the earth, a very positive broader impact. Of course a different alien race could visit the earth and deem it mostly harmless until they discover my oracle, realized we have advanced too far and then blow us up before we become a threat.

In other broader impacts, I will train graduate students to be just like me. Whether this is a positive or negative impact I leave to the reviewers.