Lance Fortnow's Blog, page 117

A problem on Receiprocals

(I thought I had posted this a while back but I can't find it in past blogs

so I think I did not. I DID post a diff problem on reciprocals.)



Here is the question I graded a while back on a  Maryland Math Olympiad.
I request that you do it and post your answer as a comment- I'll be curious
how your answers compare to the students who took it.
I will post the solutions the students used in my next post and comments
on how they were similar or different than yours.
The students had two hours to do five problems.
This was problem 2.

The inequalities 1/2 + 1/3 + 1/6 = 1 and 1/2 + 1/3 + 1/7 + 1/42 = 1
express 1 as a sum of three (resp. four) reciprocals.



PART A: Find five distinct positive integers a,b,c,d,e  such that


       1/a + 1/b + 1/c + 1/d + 1/e = 1.




PART B: Prove that for any positive integer m GE 3 there exists k distinct positive intgers numbers d1,...,dk such that



1/d1 + 1/d2 + ... + 1/dk = 1.

A Theorist Goes to SOSP

Monday I attended the 24th Symposium on Operating Systems Principles, the lead conference for computer systems research. Why would a nice theorist go to SOSP? Trying to recruit a few good systems faculty for Georgia Tech.



I really enjoyed the day in ways I didn't expect. I found several of the talks interesting, even from a theory perspective. Austin Clements, in the first and one of the best paper talks, said he had a theorem and proof (roughly if operations scale there is an implementation that scales well on multicores), though purposely left the formalization and proof out of the talk and focused on implementations. Kay Ousterhout built on some theoretical tools for job scheduling. In a talk after I left, a group from Texas takes a step towards practical proof-based verifiable computing. I never expected to be cited in a SOSP paper.



When I go to a theory conference I see so many people I know that I don't spend enough time meeting new people. At SOSP, I knew a handful of people and just had a great time talking to people I haven't met before, particularly students.



Only thirty papers get presented in single track in this conference held every two years. STOC/FOCS accepts over 300 papers in the same time period. Having an SOSP paper is a really big deal. Despite having only thirty talks and traditionally held in hard-to-reach places (this year an hour and a half drive from Pittsburgh), there were 628 attendees split 42% students, 42% non-student academics, 15% industry and one member of the press.



The 2013 SOSP is the first ACM conference will fully open proceedings and the authors retained full rights to their paper, the gold standard espoused by many in our community. It didn't come cheap, the conference put up $1100/paper to the ACM to pay for the privilege.

My Pope Number is 2: The Smaller World Hypothesis

I proofread Piergiogrio Odilfreddi's book (which is on Lance's List of Favorite Complexity Books) for which I got a generous acknowledgment. I have also

visited him in Italy, though not for a while. 



Benedict.Pope Emeritus (I think that's what he is still called) broke his silence with a letter to Odilfreddi, see here.



Hence I am two handshakes away from Pope Benedict.  It used to be said that there were Six degrees of separation.-- for all people a,b there is a path of length at most 6 that links them. The graph varies with you you ask, but it tries to pin down that a and b know each other.



Is six now too big? One measure is how many Google hits

`X degrees of separation' gets


Six degrees gets 1,760,000 hits
Five degrees gets 97,300 hits
Four degrees gets 159,000 hits
Three degrees gets 605,000 hits
Two degrees gets 843,000 hits

The last one may not be quite fair- there was an episode of Pokemon

with the title `Two degrees of Separation' and also a company with that name.





How well two people know each other has to be defined carefully.




Erdos Numbers- Put an edge between a and b if they have a paper together.
Bacon Numbers- Put an edge between a and b if they appear in the same movie.
Handshake Numbers (I am not sure its every been called that)- Put an edge between a and b if they have shaken hands.
knows-number (likely not defined). Put a DIRECTED edge from a to b if a will return b's phone calls and/or email.
Twitter Numbers (Not sure if its ever been defined). But a directed edge between a and b if a follows b on twitter.

Odilfreddi may be an articulation point in the handshake graph or the knows-graph since he is in math AND known to the public (at least in Italy) as an outspoken atheist, so he connects two worlds. Another articulation point might be David Seetapun who has a PhD in computability theory (he worked on Recursive Ramsey Theory which is how I know of him), Finance (Goldman Sacks), Gambling in Las Vegas, and swordfish fishing (he won the Golden Fly Tarpon Tournament). He may be the key to connecting mathematicians to fisherman.



The following is probably known but I couldn't find it- what is the longest distance between two websites (number-of-links to go from one to the other)?

The average? Are these numbers getting larger or smaller?



ADDED LATER: Christian Sommer emailed me the following two

RELEVENT links:



Diameter of the web and



Tools to study the web graph



The first link claims the avg diameter of the web is 19.

Andrzej Mostowski (1913-1975)

Andrzej Mostowski was born 100 years ago today. While Mostowski worked in many areas of logic, including early fundamental work on model theory, for our readers he's best known for co-discovering the arithmetic hierarchy, sometimes called the Kleene-Mostowski hierarchy.



The arithmetic hierarchy has a few different equivalent definitions but let's use one based on computability. We define inductively there hierarchies, Σi0, Πi0 and Δi0. Σ00=Π00=Δ00 are the computable sets and



Δi+10 are the sets computable with a Σi0 oracle.

Σi+10 are the sets computably enumerable with a Σi0 oracle.

Πi0 = co-Σi0.


In particular, Δ10 are the computable sets and Σ10 are the computably enumerable sets. The halting problem is Σ10-complete under computable reductions, the set of Turing machines that accepting infinite sets are Π20-complete.






We completely know the structure of the arithmetic hierarchy, for i > 0, Σi0 ≠ Πi0 and for i ≥ 0, Δi0 = Σi+10 ∩ Πi+10.



The arithmetic hierarchy inspired the polynomial-time hierarchy in complexity theory. Unlike the arithmetic hierarchy, separations in the polynomial-time hierarchy remain open and any separation implies P ≠ NP. While we have relativized worlds which do quite a few different separations and collapses in the polynomial-time hierarchy the following remains open: Does there exist a relativized world where the polynomial-time hierarchy looks like the arithmetic hierarchy, i.e., for i > 0, Σip ≠ Πip and for i ≥ 0, Δip = Σi+1p ∩ Πi+1p?

University of Maryland Job Posting Mentions Quantum Computing explicitly!

The University of Maryland at College Park has its job posting up (its been up for a while). You can look at it here. I It lists THREE areas but says that they will take applicants from any area. This is believable since they only listed three. Had they listed (say) seven then I would not believe they are looking at other areas. What is the X such that if they list X then you believe they will take from other areas but if you list X+1 then you don't?



The three areas listed are:




Cybersecurity
Quantum Computing
Natural Lang. Proc.

All three of these seem more particular than I usually see in job postings. That is, I've seen things like  Systems, Theory, AI. SO- is this unusual? I don't quite know--- I haven't been on the market for a long time.

Science and Humanities

David Hollinger, a historian, wrote a recent Chronicle Review article The Wedge Driving Academe's Two Families Apart: Can STEM and the human sciences get along?, one of a number of articles I see talking about the connections between science and humanities and the future of humanities at universities.



Most scientists do find great value in the humanities and I would hope vice-versa. But when funds get tight, different fields talk about their relative importance--it happens between science and humanities broadly, it happens between theory and systems in CS departments with limited slots to hire.



I feel badly for humanities these days. In a tight job market, students and parents think hard about doing a humanities major while universities are trying to find ways to cut costs. I don't have a solution--right now the job market calls for more computer scientists than English majors, but I would hate to see an intellectual core of our academic world shrink away.



Humanities are cheap. A provost once said to me it costs the same to hire five philosophers as one physicist once start-up costs and salary are considered. We should find a way to keep funding the humanities while maintaining the strengths across all fields.



Pushing the bounds of human wisdom is important, whether it be in chemistry or classics. Only when we push in all directions does the ball of knowledge truly expand.

Teaching without a net

As a grad student I was teaching the linear-time Median finding algorithm and I FORGOT

that I needed to solve the more general problem of selection. After less than a minute

of trying to see what was wrong I told them

I am sure that Median IS in linear time. I will consult sources  and redo this tomorrow.

I then did the rest of the lecture (which didn't require knowing the Algorithm for Median) and the next day I did the linear Median Finding Algorithm correctly.



Note that I was teaching well known material. So I KNEW that what I was saying was true even if I couldn't  prove it. I also KNOW that I could look it up. I was TEACHING WITH A NET.



When I taught Grad Algs a few years ago I sometimes didn't quite know how the PROOF went  BUT I knew that the STATEMENTS I made were correct, and the algorithms and proofs were out there. In one case I emailed the original author with a subtle point I was stuck on. (It really was subtle- the author himself had to think about it). TEACHING WITH A NET



Last semester some of my Ramsey Theory course was taught WITHOUT A NET. Not in termsof the statements of theorems, but in my attempt to find easier proofs of theorems--- sometimes my alleged proof DID NOT WORK. And there was no book I could consult, nor person I could ask, to help me out on these new ``proofs''. One of my attempted simplifications (of the Canonical Ramsey Theory) DID NOT pan out in the end.



This semester  I am teaching an honors interdisplinary course on Fair Division (nicknamed 'Cake cutting'). I've pulled material from a  variety of different subfields (math, CS, AI. Yes AI!). So I have put some things together that are ``new''(not worth-publishing-new but new in some sense). Some of them have been wrong, or to be more fair, not quite right. But WHO CAN I ASK? Nobody! This is truely teaching WITHOUT A NET. I have made about 2 incorrect statements (both of which were prefaced with `this might not be quite right') but the bigger effect is that every day I wonder if what I am saying is correct.

The effect on the actual course is mininal-- but my mentality going in ``will I make a mistake today that I cannot recover from'' is... interesting.



What to do if you are wrong? Own up to it ASAP. Every minute you fumble around you lose the classes interest.



Is the course working? I think so-- they are learning and having fun. It helps that they are honors students who chose to take this course.

2013 Fall Jobs Post

Time again for the annual fall jobs post. As always the best places to look for academic CS positions are the job sites at the CRA and the ACM. Also check out the postdoc and other opportunities on the Theory Announcements site and the Intractability Center. It never hurts to check out the webpages of departments or to contact people to see if positions are available.



I encourage everyone who has a job to offer in theoretical computer science at any level to post links in the comments.



Faculty hiring has rebounded nicely and with computer science enrollments expanding, it should continue to be quite robust. Postdocs will still be down from a few years ago.



Good luck to everyone in the market. I look forward to seeing your names in the 2014 spring jobs post.

Who controls what is taught- the dept or the students?

There is a debate about the questions:



To what extent do we give them what they NEED?  what they WANT?





These questions permeate many other discussions of education.



Rather than discuss this profound issue I will discuss a fictional example.




A dept offers one section of Operating Systems (henceforth OS) in the fall and one section in the spring.
The same dept also offers one section of AI (henceforth AI) in the fall and one section in the spring.
They notice after a few years that the OS tends to underfill and the AI course tends to overfill.
Hence they switch to offering OS in the Spring only, and  AI is offered two in the fall and one in the spring.
Over time more students take AI and less take OS. Some of this is interest but some is that AI is easier to fit into a schedule since its always offered and has two sections in the spring.
 All of the teachers are excellent (remember this is fictional) so the quality of teaching is not the issue. The courses are of equal difficulty so this is not the issue. The courses have the same prerequisites so this is no the issue.
The next hiring season they decide to hire someone in AI since they need the teaching help.

The department DID NOT  mean to send the message:

AI is more important than OS.

NOR  did they mean to send the message

 We will let the students decide what is important.

  But the department ended up sending both messages. What should the dept have done? For one they should DECIDE if this is okay with them--- is AI more important than OS? Or more directly, is it okay that students graduate without having a course in OS as  long as they've had a course in AI? They may decide YES- and that would be fine. If they decide NO they could restructure the requirements OR have the advisers give that advice OR just offer less sections of AI.



Does your department fall into this trap--- ending up giving  student's opinions more sway then you intend? 

Shut Down

The NSF core proposal in theoretical computer science, or Algorithmic Foundations as the NSF calls it, has three deadlines this academic year:


Medium proposals ($500k-$1.2m): October 15
Large proposals ($1.2m-$3m): November 19
Small proposals ($0-$500k): January 17


For the most part nearly every core program in computer science has the same deadlines, making it quite an interesting time in CS departments when most of the faculty are all submitting their proposals last minute in January.




Let's talk not about January but about October 15, next Tuesday. Good luck trying to download the proposal call for algorithmic foundations, or the NSF grant proposal guide, or submitting your proposal on Fastlane. All NSF links take you here, where you can read all about what is not happening at the NSF during the government shutdown. So what about October 15?

Once normal operations resume, NSF will issue guidance regarding any funding opportunities that have a deadline or target date that occurs during the government shutdown. Such information will be disseminated via a FastLane Advisory and other electronic methods.

In principle, the government could reopen for business Tuesday morning and the proposals would still be due Tuesday 5 PM. I would guess the deadline would be extended but there is nobody to ask, no one at the NSF to answer the phones and NSF employees are forbidden from responding to or even reading email. At least those that already have grants can keep spending their money, most importantly continuing to fund their students.



These are short term problems, the government will re-open at some point and the NSF will get back to business. But all discussions seem to lead to budget cutting and even just erasing the sequester of last year seems unlikely. The budget crises hasn't stopped Eric Cantor and Lamar Smith from continuing to trash some NSF grants.



Science is too important to be a pawn in politics. Investments in science have given incredible value back to America in terms of jobs and economic growth. Yet somehow science never gets mentioned as a tragedy in the Washington money battles.