Randomness by Complexity

Let n be the following number
135066410865995223349603216278805969938881475605667027524485143851526510604859533833940287150571909441798207282164471551373680419703964191743046496589274256239341020864383202110372958725762358509643110564073501508187510676594629205563685529475213500852879416377328533906109750544334999811150056977236890927563 (RSA 1024)

What is the probability that the fifth least significant bit of the smallest prime factor of n is a one? This bit is fully defined--the probability is either one or zero. But if gave me better than 50/50 odds one way or the other I would take the bet, unless you worked for RSA Labs.

How does this jibe with a Frequentist or Bayesian view of probability? No matter how often you factor the number you will always get the same answer. No matter what randomized process was used to generate the original primes, conditioned on n being the number above, the bit is determined.

Whether we flip a coin, shuffle cards, choose lottery balls or use a PRG, we are not creating truly random bits, just a complex process who unpredictability is,we hope, indistinguishable from true randomness. We know from Impagliazzo-Wigderson, and its many predecessors and successors, that any sufficiently complex process can be converted to a PRG indistinguishable from true randomness. Kolmogorov complexity tells us we can treat a single string with no short description as a "random string".

That's how we ground randomness in complexity: Randomness is not some distribution over something not determined, just something we cannot determine.

Is Kim Davis also against Nonconstrutive proofs?

Recall that Kim Davis is the Kentucky clerk who refused to issue marriage licenses for same-sex couples and was cheered on by Mike Huckabee and other Republican candidates for Prez. Had she refused to issue marriage license for couples that had been previously divorced than  Mike Huckabee would not be supporting her, and the Pope wouldn't have a private 15 minute meeting with her telling her to stay strong (NOTE- I wrote this post in that tiny window of time when it was believed she did have such a meeting with the Pope, which is not true. The Pope DID meet with a former student of his who is gay, and that studen'ts partner.) Had she refused to issue marriage licenses to inter-racial couples (this did happen in the years after the Supreme court said that states could not ban interracial marriage, Loving vs Virginia, 1967 ) then ... hmm, I'm curious what would happen. Suffie to say that Mike H and the others would prob not be supporting her.

David Hilbert solved Gordon's problem using methods that were nonconstructive in (I think) the 1890's. This was considered controversial and Gordon famously said this is not math, this is theology. Had someone else solved this problem in 1990 then the fact that the proof is non-constructive might be noted, and the desire for a constructive proof might have been stated, but nobody would think the proof was merely theology.

I don't think the Prob Method was ever controversial; however, it was originally not used much and a paper might highlight its use in the title or abstract. Now its used so often that it would be unusual to point to it as a novel part of a paper. If I maintained a website of Uses of the Prob Method in Computer Science then it would be very hard to maintain since papers use it without commentary.

The same is becoming true of Ramsey Theory. I DO maintain a website of apps of Ramsey Theory to CS (see here) and its geting harder to maintain since using Ramsey Theory is not quite so novel as to be worth a mention.

SO- when does a math technique (e.g., prob method) or a social attuitude (e.g., acceptance of same-sex marriage) cross a threshold where its no longer controversial? Or no longer novel? How can you tell? Is it sudden or gradual? Comment on other examples from Math! CS!

Cancer Sucks

Karsten Schwan said the title quote when we were gathered as a faculty two years ago mourning the Georgia Tech School of Computer Science faculty member Mary Jean Harrold who died from the disease. Karsten just lost his own battle with cancer monday morning and my department is now mourning another great faculty member.

Just a few months ago, Alberto Apostolico, an algorithms professor at Georgia Tech, also passed away from cancer. 

I went back through the obituaries in the blog and we lost quite a few to cancer, often way too young, including Mihai Pătraşcu, Benoît Mandelbrot, Partha Niyogi, Ingo Wegener, Clemens Lautemann and Carl Smith. I just taught Lautemann's proof that BPP is in Σ^p₂∩Π^p₂ in class yesterday.

With apologies to Einstein, God does play dice with people's lives, taking them at random in this cruel way. Maybe someday we'll find a way to cure or mitigate this terrible disease but for now all I can say is Cancer Sucks. 

Venn Diagrams are used (yeah) but abused (boo)

In a prior blog entry I speculated about which math phrases will enter the English Language and will they be used correctly.  I thought Prisoner's Dilemma would enter and be used correctly, but Turing Test and Venn Diagram would not enter.

Since then I've seen Turing Test used, but only because of the movie The Imitation Game. I don't think it will enter the human language until a computer actually passes it for real, which might not be for a while. See this excellent post by Scott Aaronson about a recent bogus claim that a machine passed the Turing Test.

Venn Diagrams seem to be used more (Yeah!) but incorrectly (Boo!)

1) In this article (which inspired this post), about who might replace John Boehner as speaker of the house, there is the following passage:

Option 3: An acceptable and respected conservative like Jeb Hensarling or
Tom Price emerges as speaker. Why these two? First, Paul Ryan doesn’t seem
to want the gig, so that leaves us with only a few options for someone who
fits in the Venn diagram of being enough of an outsider, well liked, and
sufficiently conservative.

Is this correct use? They really mean  the intersection of oustider, well-liked,
and suff conservative. One can picture it and it sort of makes sense, but its not
quite correct mathematically.

2)  In this ad for Venn Beer (in celebration of John Venn's 180th birthday!) they really mean union, not intersection.

3) This Venn Diagram about Vladmir Putin's and your Aunt's record collection doesn't really make sense but I know what they mean and its funny.

4) This Venn Diagram about how to woo women is incorrect, not funny, not mathematically meaningful.

5) This Venn Diagram involved Doctors, Prostitutes, and TSA agents. At first it is funny and seems to make sense. But then you realize that the intersection of Doctors and Prostitutes  is NOT People who make more per hours than you make all day, its actually prostitutes with medical degrees. Its still funny and I see what they are getting at.

6)  This Venn Diagram (it's later in the article) of Republican Candidates for the 2016 nomination for Prez is correct for the math and informative, though one may disagree with some of it (Is Trump really Tea-Party or should he be in his own category of Trumpness?)

21st Century Problems

My youngest daughter, Molly, a high school senior talking colleges with a woman about ten years her senior. The woman remembered all her friends watching the clock so they could go home to check their emails to see if they were accepted. Molly said "Sheesh, you had to go home to check email?"

My other daughter Annie, a college junior, went on an overnight last Thursday to a place without cell phone reception. She spent Friday night with her friends in her class catching up on emails, texts and Facebook messages.

Now back in my day (that being the early 80's) we got our college acceptances and rejections by postal mail, where that one crucial bit of information could be determined by the thickness of the envelope. Some of my friends had their mail held by the post office so they could find out a few hours earlier.

In college I did have email access, in fact I wrote an email system for Cornell. But most students didn't use email so we resorted to other means. Student organizations could hire a service that put posters on key locations throughout campus. Chalk on sidewalks worked particularly well. The personals section of the Cornell Daily Sun served as a campus bulletin board. In my freshman dorm we had phones in our rooms but no answering machines. We did put little whiteboards on our doors so people could leave us messages. We had a lounge on our floor where you could find most people and talk to them in person. You young people should try that more often.

We had to coordinate activities and meeting places ahead of time, if someone was late you waited for them. On the other hand I never had to spend my Friday nights catching up on emails and texts.

When did Mathematicians realize that Fermat did not have a proof of FLT?

I recently came across the following passage which is about  Fermat's Last Theorem (FLT).

Pierre de Fermat had found a proof, but he did not bother to write it down. This is perhaps the most frustrating note in the history of mathematics, particularly as Fermat took his secret to the grave.


AH- so at one time people thought Fermat DID have a proof of FLT.  That is, a proof using just the math of his time, likely a very clever proof. I doubt anyone thinks that Fermat had a proof in this day and age. Actually it has been in fiction: in a 2010 episode Dr. Who episode The eleventh hour, the doctor has to prove to some very smart people that they should take his advice. He does this by showing them Fermat's proof of FLT. Good Science Fiction but highly unlikely as Science Fact. In an episode of ST-TNG  (Title: The Royale. Year: 1989) it is claimed that FLT is still open. Whoops. But in an episode of ST-DSN (Title: Facets. Year: 1995) they refer to `Wiles proof of FLT'.

Wikipedia states: It  is not known whether Fermat had actually found a valid proof for all exponents n, but it appears unlikely. I think that understates the case.


So here is a question for all you math historians out there: When did the math community realize that FLT was really hard?

We have one clue- the quote I began with. Its from... 2013. Whoops. The book is  The Simpsons and their mathematical secrets by Simon Singh (Author of Fermat's Enigma  which is about the quest to proof FLT).  I've read the passages about FLT in the Simpsons book over again to make sure he doesn't someplace say that Fermat prob didn't have a proof. No--- he seems to really say the Fermat had a proof. So whats going on here? Possibilities:

1) I'm wrong. There are serious credible people who think Fermat had a proof and he talked to them; perhaps while working Fermat's Enigma. I find this unlikely- I have never, literally never,  heard of  anyone, not even math cranks, who think Fermat had a simple proof.  Some cranks think THEY have a simple proof, though even that seems far less common after FLT was proven.

2) I'm right. He didn't have anyone who was both serious and credible check his book. I find this unlikely. He has written Fermat's 't Enigma so surely he is in contact with people that are both credible and serious.

3) He did have someone check his book but thought the story was better the way he told it. (This was common on the TV show Numb3rs which never let a mathematical truth get in the way of a good story.)
I find this unlikely since a better way to say it is we'll never know if Fermat had a proof!

One problem with such mistakes is that it destroys his credibility on other math things he writes of. That info about Dr. Who I got from the book, but I suspect its correct. And the stuff about the math that appears in the Simpsons is checkable and seems correct. I give one example: in one episode you see in the background

3987¹² + 4365¹²= 4472¹²

which is correct on a calculator with only 10 digits of precision. Cute! But I have stopped reading any of the math history in the book for fear that I will get incorrect notions in my head.

However, back to my original question: Was there a time when people thought Fermat really had a proof?Was  there a time when people thought there was an easy proof? When did that change?

The Theorems Conference

All too often theoretical computer scientists get more obsessed by proofs than the theorems themselves. I suggest a theorems conference. Here's how it would work:

Authors would submit two versions of a paper. One has the statement of the theorem and why that theorem matters, but no proofs. The second version includes the proofs.

The program committee first makes tentative decisions based on the first version of the paper. If tentatively accepted the PC then looks at the second version. The PC can reject the paper if the the proofs have significant flaws, gaps or readability issues. The PC cannot reject the paper for any other aspect of the proof such as length or lack of technical depth or originality.

This way we truly judge papers based on what they prove--what the results add to the knowledge base of the field.

Of course my plan has many flaws. Some papers with their proofs may have already been posted on archive sites which the PC members could have seen. More likely, the PC will guess the difficulty of the proof and judge the paper based on this perceived difficulty, and not on the theorem itself.

We need a culture shift, away from an emphasis on proofs. That's the only way we can judge our results for the results themselves.

An Open(?) Question about Prime Producting Polynomials Part II in 3-D!

(Apologies- No, this post is not in 3-D)

I posted last week about An Open(?) Question about Prime Producing Polynomails

I got several emails about the post with more information, inspiring this post!
All the math in this post can be found in my writeup  Polynomials and Primes,
unless otherwise specified. NONE of the results are mine.

You can read this post without reading the prior one.

1) KNOWN: Let  f(x) ∈ Z[x]  be  a poly of degree d. Then there exists a non prime in f(x)'s image (actually there are an infinite number of  non primes, in fact there are an infinite number of composites).  If f(1) is prime then of  f(1+mf(1)) as m=0,1,2,... at most 2d-2 of them are prime.

2) Algorithm to find an x such that f(x) is not prime: compute f(1), f(1+f(1)),...,f(1+(2d-2)f(1)) until you find one that is not prime. This takes 2d-1 evals. OPEN(?): Is there a better deterministic algorithm where we measure complexity by number of evals? Since this is a simple model of computation lower bounds might be possible.

3) There is the following randomized algorithm: Eval f(1)- if its not prime you're done. If f(1) is prime then pick a random m where 0≤ m ≤ (2d-2)² and eval f(1+mf(1)). This is non prime with prob 1- (1/(2d-1)).

4) What is it about Z that makes this theorem true? In my write up I show that if D is an integral domain with only a finite number of units (numbers  that have mult inverses) then any poly in D[x] has to produce non-primes infinitely often. (A prime in D is a number a such that if a=bc then either b or c is a unit.)

5) What about if D has an infinite number of units? See this  paper for examples of polynomials over integral domains D such that the poly only takes on  only prime or unit values.

6) What about polys over Q? over R? over C? In my write up I prove similar theorems for Q and then use that to get theorems for C.

7)  Looking at polys in Z[x,y] is much harder, see this survey. 

8) If f(x)∈Z[x] is a poly then does there exist a prime in f(x)'s image? An infinite number of primes? Easy but stupid answer is no: f(x)=2x. Better question: assume that f(x)'s coefficients are rel prime.

Dirichlet's theorem: if GCD(a,b)=1 then ax+b is prime infinitely  often.

Open: is x²  + 1 prime infinitely often?

Designer Chips

A computer architecture researcher talked to me about a role theoretical computer science can play for them: creating a new kind of computer processor. Microprocessors stopped getting faster a decade ago due to energy challenges so computer architects look for new ways to improve performance, moving away from the general-purpose CPU towards processors that handle more specific functions. The GPU, Graphics Processor Unit, has long been around to handle the graphics-intensive needs of modern computers and many have used GPUs for other purposes such as machine learning. These days we can program chips using FPGAs (Field-programming gate arrays) and are nearly at the point of cheaply compiling directly to hardware. How does this change the theory we do?

What kind of specialized chips would speed up our algorithms? If we want to find matchings on graphs, for example, is there some routine one could put in a chip that would lead to a much more efficient algorithm?

On the complexity side, how do we model a computer where we can program the hardware as well as the software? What are the right resource bounds and tradeoffs?

In general our notions of computers are changing, now with multi-core, cloud computing and designer chips. Not only should we focus on applying theory to these new models of computing, but we should think about what future changes in computing could yield more efficient algorithms. Theorists should be involved in planning the future of computing and we're not even doing a great job reacting to changes around us.

An Open(?) question about prime-producing-polynomials

Known Theorem: If f(x)∈ Z[x] is  prime for all nat number inputs then  f(x) is a constant.

NOTE- Recall that if p is a prime then so is -p.

Known Proof: Assume f(x) has degree d. f(1) IS prime.  Let f(1)=p. Look at

 f(1+p), f(1+2p),...,f(1+(2d+1)p).

One can easily show that p divides all of these. Hence if they are all primes then they must all be p or -p. Since there are 2d+1 of them, at least d+1 of them are the same, say p. Hence f is the constant p.

END of known proof.

Note that the proof gives the following theorem:

Let f(x)∈ Z[x] of degree d. We assume f(1)≥ 0. Least a st f(a) is NOT prime is  ≤ 1+(2d+1)p.

(This can prob be improved a bit with some cases, but its good enough for now.)

Recall Euler's poly x²-x+41 produces primes for x=0,...,40. But at 41 you get a composite. This is much smaller than the upper bound 1+(2d+1)p = 1+5*41=206.

Wolfram MathWorld has a  page of other polys in Z[x]  that produces lots of primes initially, but NONE come close to the bound.

QUESTIONS:

Proof a better upper bound.

Proof a better lower bound (Fix d and produce and infinite seq of polys of degree d...)

Close the gap!

If this is already known, then let me know please.

Can also ask for polys in Q[x], R[x], C[x]. For Q[x] and R[x] same theorem is true- no poly can produce all primes. I suspect also true for C[x] but I haven't seen it stated anywhere. (ADDED LATER- Proof for C[x] is easy. First proof
for Q[x] and then by Lagrange interpoloation if a poly has inf many times
where f(integer)=integer, poly is in Q[x].)

You can also NOT include negative primes and see how that changes things.

Whiplashed

I recently watched the movie Whiplash, about a college jazz band director, Fletcher played by J.K. Simmons, who torments his musicians to force them to be their best. The movie focuses on a drummer, Andrew, which makes for a great audio/video feast but in its essentials Whiplash is a story of a professor and his student.

I can imagine playing the role, “Do you think your proof is correct? Yes or No? Are you applying Toda’s theorem correctly or are you using the same crazy logic your dad used when he left your mom?” OK, maybe not.

Nevertheless Fletcher has a point. Too often I’m seeing graduate student doing just enough to get a paper into a conference instead of pushing themselves, trying to do great work and still not being satisfied. Fletcher says the two most dangerous words in the English language are “good job”.  While that might be a little cruel, we do need to push our students and ourselves to take risks in research and be okay in failing. To roughly quote John Shedd and Grace Murray Hopper, "the safest place for a ship is in the harbor, but that’s not what ships are for."

Whiplash had a different kind of scene that definitely hit home. Andrew could not impress his family with the fact that he was lead drummer in the top college jazz band in the nation. I’ve been there, trying to get my mother excited by the fact that I had a STOC paper early in my career. "That's nice dear".

Two candidates that I want to see run for Democratic Nomination

It has been noted that while there are 17 Republican candidates for the nomination, of which 10 have been declared serious by FOX News via the first debate, there are far less democratic candidates for the nomination and only one has been declared serious by the powers that be. This may change if Biden runs.

I want to suggest two Democrats who I think should run. They have not made ANY moves in that direction, so it won't happen... until they see that this blog post endorsing them and they get inspired!

Rush Holt. Was a US Congressman from NJ (NOTE- earlier version of this post incorrectly had him as a US Senator from WV which his father was. Thanks to Dave MB comment for pointing that out.)   He has a PhD in Physics. I want a president who wins a Nobel Prize in something OTHER THAN Peace (T. Roosevelt, Wilson, Carter, Obama have won it for peace, fictional Bartlett on West Wing won if for Economics). I can imagine one winning for Literature. But Physics- that would be awesome! While I doubt Dr. Holt will win one, it would be good to have someone as Prez who knows SOME science so he won't say stupid things about global warning. (Counter question- do the climate change deniers in the Senate really believe what they are saying or not?)  He's also a Quaker, not sure how that plays into all of this. (I had a longer and incorrect passage here, but  thanks to Andy P's comment below I changed it and it is now correct--- I hope.)

Would having a scientist in the Whitehouse be good for Science Funding? I would guess a marginal yes. Would it improve my chance of getting my REU grant renewed? I would guess no.

Sheldon Whitehouse. US Senator from Rhode Island. Look at his name- he was born to be Prez!

You may think these are stupid criteria. You may be right. But is it any better than I voted for X in the primary since X has a better chance of winning in the general (One of Clinton's arguments against Obama in 2008 was that Obama couldn't win since... well, you know) or he looks just like a prez (Warren Harding's main qualification) or he's  Rich and obnoxious (I would say who I am thinking of, but he's been known to sue people).

PACM

I serve on the conference committee of the ACM publications board and we've had extensive discussions on the question of the role of journals in publication venues. A number of CS conferences, though notably not in TCS, are moving to a hybrid publication model where their conference presentations make their way into refereed journal papers. One of our proposals is the creating of a specific venue for these activities, a new Proceedings of the ACM. In the September CACM,  Joseph Konstan and Jack Davidson lay out this proposal, with pros and cons by Kathryn McKinley and David Rosenblum respectively. The community (that means you) is being asked to give their input.

The theory model has not significantly changed since I was a student. Papers submitted to a conference get reviewed but not refereed, the proofs read over usually just enough to feel confident that the theorem is likely correct. Once authors started submitting electronically they could submit entire proofs, though often in an appendix the program committee is not required to read.

The papers appear in a proceedings and to quote from the STOC proceedings preface

The submissions were not refereed, and many of these papers represent reports of continuing research. It is expected that most of them will appear in a more polished and complete form in scientific journals.

A small select number of papers from a conference are invited to a special issue of a journal where they do go through the full referee process. Some, but not most, of the other papers get submitted to journals directly. We don't have the proper incentives for authors to produce a journal version with full and complete proofs.

Should theory conferences move towards a more hybrid or PACM type of model? I'd had several debates with my fellow theorists many of whom feel the advantages of requiring journal-level papers get outweighed by the extra effort and time required by the authors and the reviewers.

Interesting properties of the number 24 on someone's 24th wedding anniversary

The story you are about to read is true. Only the names have been changed to protect the innocent. The Alice and Bob below are not the crypto Alice and Bob.

------------------------------------------------------
BOB (to ALICE): Its our 24th anniversary! Last year when it was our 23rd anniversary we celebrated by having you tell me that 23 was the ONLY number that required 9 cubes so sum to it, and that its open how many cubes you need for large n, though its between 4 and 7. Oh that was fun! What do you have planned for our 24th anniversary!

ALICE (to BOB): I've prepared FIVE facts about 24! Oh, I mean 24, not 24 factorial! We'll see which one you want to discuss.  Here they are:

1) 24 is the largest nat number n such that all nat numbers m ≤  sqrt;(n)   m divides n.

2) 24 is the least nat number that has exactly 8 distinct factors. (1,2,3,4,6,8,12,24)

3) 24 is the ONLY number m≥2 such that 1^2 + 2^2 + ... + m^2 is a square. Its 70^2, so if we are married 70 years, I'll have an interesting fact about 24.

4) Let S be an n-sphere. How many spheres of the same size as S can kiss S? Thats the kissing number, called kiss(n).  kiss(2)=6 (so given a circle you can position 6 identical circles that kiss it), kiss(3)=12 (thats 3-dim), and kiss(4)=24.

5) Its one of the few numbers that is the title of a TV show. 

BOB:  Since its our anniversary I'll go with the kissing number~ Mathematically I'd go with the square thing.
---------------------------------------------------

I am sure that for all numbers ≤ 94 one can come up with some facts of interest. The book Those Fascinating Number has an interesting fact about many numbers. The least number that it has no interesting fact about is 95, but I suspect Alice and Bob won't be married that long.

What are the coolest numbers (mathematically)? See here  for a possible answer. 

 

Crowdsourcing the Truth

A new project Augur aims to create a decentralized prediction market. If this post so moves you, Augur is in the midst of a reputation sale. Don't miss out if you would like to be an Augur reporter.

A prediction market takes a future event, such as Hillary Clinton winning the 2016 Presidential Election, and creates a security that pays off $100 if Hillary wins and $0 otherwise. The market allow buying, selling and short selling the security and the price of the security represents that probability the event will happen. Predictwise, which aggregates prediction markets, has the probability of Hillary winning at 47% as I write this. But there are a limited amount of markets out there for Predictwise to draw from.

Intrade, which shut down due to financial improprieties in 2013, used to run markets on all aspects of elections and other current events. Many other prediction markets have disappeared over time. The Augur team put out a white paper describing their fully decentralized prediction market immune to individuals bringing it down. They build on cryptocurrencies for buying and selling and a group of "reporters" financially incentivized to announce the correct answer for each market.

It's that last part I find the most interesting, instead of having an authority that reports the results, Augur will crowdsource the truth.

A key feature of Augur is tradeable Reputation. The total amount of Reputation is a fixed quantity, determined upon the launch of Augur. Holding Reputation entitles its owner to report on the outcomes of events, after the events occur...Reputation tokens are gained and lost depending on how reliably their owner votes with the consensus.

Consensus may not be "the truth". Reporters are not incentivized to report the truth but what the other reporters will report as the consensus. Those who buy and sell on the market are not betting on the truth but the outcome as it is decided by the consensus of reporters. We have an ungrounded market.

The purchasers of reputation tokens likely won't represent the public at large and biases may come to play. Would this consensus have agreed that Bush won the 2000 election?

What would have the consensus done on the North Korea controversy?

[The Intrade security] allowed speculation on whether North Korea would, by 31 July 2006, successfully fire ballistic missiles that would land outside its airspace. On 5 July 2006 the North Korean government claimed a successful test launch that would have satisfied the prediction, a launch widely reported by world media. [Intrade] declared that the contract's conditions had not been met, because the US Department of Defense had not confirmed the action, and this confirmation was specifically required by the contract. (Other government sources had confirmed the claim, but these were not the sources referenced in the contract.) Traders considered this to be in strict compliance with the stated rule but contrary to the intention of the market (which was to predict the launch event, and not whether the US Defense Department would confirm it).

Since Augur will allow arbitrarily worded contracts on topics such as proofs of P v NP, the consensus reporting may lead to some interesting future blog posts.

Despite my reservations, I'm quite excited to see Augur set up a prediction market system that can't be shut down and wish them all the luck. You have to until October 1 to buy reputation if you want to be deciding the truth instead of just predicting it.

Have we made Progress on P vs NP?

While teaching P vs NP in my class Elementary Theory of Computation (Finite Automata, CFG's, P-NP, Dec-undecid) I was asked  What progress has been made on P vs NP?

I have heard respectable theorists answer this question in several ways:

1) There has been no progress whatsoever- but the problem is only 40 years old, a drop in the mathematical bucket sort.

2) There has been no progress whatsoever- this is terrible since  40 years of 20th and 21st century mathematics is a lot and we already had so much to draw on. We are for the long haul.

3) We have made progress on showing some techniques will not suffice, which is progress--- of a sort.

4) We have made progress on showing P=NP: Barringtons result, FPT, Holographic algorithms, SAT in PCP with O(1) queries.  Too bad- since P NE NP we've made no progress.

5) We have made progress on showing P=NP: Barringtons result, FPT, Holographic algorithms, SAT in PCP with O(1) queries.  We should not be closed minded to the possibliity that P=NP. (NOTE- other theorists say YES WE SHOULD BE CLOSED MINDED.)

6) Note that:

a) We have pathetic lower bounds on real models of computation.

b) We have Meaningful lower bounds on pathetic models of computation.

c) We DO NOT have meaningful lower bounds on real models of computation.

7) Have we made progress? Once the problem is solved we'll be able to look back and say what was progress.

I told the students my view:  We have made progress on showing some techniques will not suffice, which is progress--- of a sort which my class found funny. Then again, students find the fact that there are sets that are undecidable, and sets even harder than that! to be funny too.

What is Theoretical Computer Science?

Moshe Vardi asks a provocative question in Windows on Theory and CACM: "Why doesn't ACM have a SIG for Theoretical Computer Science?" The reaction of myself and many of my fellow Americans is the question has a false premise. SIGACT, the ACM special interest group for algorithms and computation theory, plays this role as stated in its mission:

SIGACT is an international organization that fosters and promotes the discovery and dissemination of high quality research in theoretical computer science (TCS), the formal analysis of efficient computation and computational processes.  TCS covers a wide variety of topics including algorithms, data structures, computational complexity, parallel and distributed computation, probabilistic computation, quantum computation, automata theory, information theory, cryptography, program semantics and verification, machine learning, computational biology, computational economics, computational geometry, and computational number theory and algebra. Work in this field is often distinguished by its emphasis on mathematical technique and rigor.

Theoretical computer science in Europe has a much different balance, putting as much or even more emphasis on automata and logic as it does on algorithms and complexity. So from that point of view (a view shared by Moshe who has strong ties to CS logic) SIGACT does not cover the full range of TCS.

The term "theoretical computer science" just doesn't have a universal meaning. Neither definition is right or wrong, though we all have our biases.

Why does TCS have such a different meaning in Europe and the US? A different research culture and relatively little mixing. Very few North Americans go to grad school, take postdocs or faculty positions in Europe and very few Europeans go the other way, and those that did tended to do algorithms and complexity. Until we started to see web-based archives in the mid 90's, distribution of research between the Europe and US went quite slowly. Things have changed since but by then the different notions of TCS have been set.

SIGACT fully acknowledges that it doesn't do a good job covering the logic community and it has always strongly supported SIGLOG, the special interest group for logic and computation.
I would love to see joint events between SIGACT and SIGLOG. LICS should be part of FCRC with STOC and Complexity or hold a co-located meeting in other years. But SIGACT does do a great job representing the theoretical computer science community in North America.

Ways to deal with the growing number of CS majors.

(Univ of MD at College Park is looking to hire a Comp Sci Lecturer.  Here is the link: HERE)


Univ of MD at College Park will have 2100 students in the CS program next year. Thats... a lot! CS is up across the country which is mostly a good thing but does raise some logistical questions. How are your schools handling the increase in the number of CS students?  Here are some options I've heard people use:

1) Hiring adjuncts who come in, teach a course, and leave is good economically (they don't get paid much) but bad for the long term.  Better to have people that are integrated into the dept (lectures are, see next point). Also, CS is a changing field so you can't just give someone some notes and slides and say TEACH THIS. For Calculus you probably can, and they can even do a good job. Calculus doesn't change as fast, or maybe even at all. I envy my friends in math departments who can count
on a stable first year course that everyone in the dept can teach. They envy CS profs who have the freedom to have diff versions of CS1 in diff schools. Even in diff semesters!

2) Hiring lecturers who are full time and have a high teaching load is good in terms of them being  fully integrated into the dept and being involved with course syllabus changes. Also, if they stay  long term there is stability. If the first year courses are only taught by lecturers this may be  bad abstractly as profs should be in touch with all levels of the dept. I once tried to make this
point over lunch at a Dagstuhl meeting and before I could even finish my point they shouted me down  and asked if I wanted to teach Intro Programming.  I do not, so I'll just shut up now.

3) Don't let profs buy out. I've heard of this at some schools as a way to at least have the profs  that are there teaching. Alternatively only let profs buy out of grad courses. I don't know if either  is a good idea.  For one thing, the money use to buy out can be used to hire someone else.  But that  goes back to point 1- not really good to have part timers.  If other profs teach overloads with the  money that sounds okay. If half of the profs are paying the other half to teach for them, that sounds odd, but I'm not sure its bad. Also, it would never get that extreme.

4) Postdocs sometimes teach a course for extra money. This is good for them for teaching experience  and resume, and if they are teaching a course with someone else this can work well. However, if a  postdocs point is to get more research done, this will of course cut into that.

5) Grad students sometimes teach a course. I knew a grad student in math who was teachng the  junior-course in number theory. I asked her if this was an honor or exploitation. She just said YES.

6) Increase class size. Going from lecturing to 80 to lecturing to 300 might be okay, though (a) you NEED to use powerpoint or similar and have resources on the web, maybe also Piazza, and (b) you NEED to have LOTS of recitations so they at least are small and (c) you NEED to havehigh quality TAs for the recitations. In some schools its even a problem getting ROOMS of that size!

7) HIRE MORE PROFS! Profs have lower teaching loads than lecturers and in CS its harder to teach outside of your area then in (say) Math. (How is it for other fields? If you know, please comment.) Should you hire based on research needs or teaching needs? If a recursive model theorists can teach graphics, that might be a real win if you NEED research in recursive model theory but also
NEED someone to teach graphics.

8) Not a suggestion but a thought- IF many of the new majors aren't very good then many might flunk out of the major in the first year so this is not a problem for Sophmore, Junior, Senior courses. At least at UMPC this does NOT seem to be the case. To rephrase: many of the new majors are good and do not flunk out. I call that good news! But what about at your school?

9) What does your school do? Does it work?

How hard would this cipher be for Eve to crack?

I've been looking at old ciphers since I am teaching a HS course on Crypto. We've done shift, affine, matrix, Playfair, 1-time pad, Vigenere, and then noting that in all of the above Alice and Bob need to meet, we did Diffie-Hellman.

The Playfair Cipher cipher is interesting in that it gives a compact way to obtain a mapping from pairs of letters to pairs of letters that (informally) LOOKS random. Of course NOW it would not be hard for Alice and Bob to AGREE on a random mapping of {a,b,...,z}^2 to{a,b,c,...,z}^2 and use that.   For that matter, Alice and Bob could agree on a random mapping from {a,b,c,...,z}^k to {a,b,c,...,z}^k for some reasonable values of k.

So consider the following cipher with parameter k: Alice and Bob generate a RANDOM 1-1, onto mapping of {a,...,z}^k to {a,...,z}^k. To send a message Alice breaks it into blocks of k and encodes each block using the mapping they agree on.

Question One: How big does k have to be before this is impractical for Alice and Bob?

Question two: If k=1 then Eve can easily break this with Freq analysis of single letters. For k=2 Eve can easily break this with Freq analysis of digraphs (pairs of letters). Is there a value of k such that the distribution of k-grams is not useful anymore? As k goes up does it get easier or harder to crack? I originally thought harder which is why i thought this would be a good code, but frankly I don't really know.Looking over the web it is EASY to find freq of letters and digraphs, but very hard to find any source for freq of (say) 10-grams.  So at the very least Eve would need to build up her own statistics--- but of course she could do this.

SO, here is the question: Is there a value of k such this code is easy for Alice and Bob but Hard for Eve TODAY? How about X years ago?

17 candidates, only 10 in the debate- what to do?

On Thursday Aug 6 there will be Republican debate among 10 of the 17 (yes 17) candidates for the republican nomination.

1) There are 17 candidates. Here is how I remember them: I think of the map of the US and go down the east coast, then over to Texas then up.  That only works for the candidates that are or were Senators or Govenors.  I THEN listthe outsiders.  Hence my order is (listing their last job in government) George Pataki (Gov-NY), Chris Christie (Gov-NY), Rick Santorum (Sen-PA), Rand Paul(Sen KT),JimGilmore(Gov-VA), Lindsay Graham (Sen-SC),Jeb Bush (Gov-FL), Marco Rubio (Sen-FL), Bobby Jindal (Gov-LA), Ted Cruz (Sen-TX), Rick Perry (Gov-TX), Mike Huckabee (Gov-AK), Scott Walker (Gov-Wisc), John Kaisch (Gov-Ohio) Donald Trump (Businessman), Ben Carson (Neurosurgeon), Carly Fiorina (Businesswomen).
9 Govs, 5 Sens, 3 outsiders.

2) Having a debate with 17 candidates would be insane. Hence they decided a while back to have the main debate with the top 10 in the average of 5 polls, and also have a debate with everyone else. There are several problems with this: (a) candidates hovering around slots 9,10,11,12 are closer together than the margin of error, (b) the polls are supposed to measure what the public wants, not dictate things, (c) the polls were likely supposd to determine who the serious candidates are, but note that Trump is leading the polls, so thats not quite right.QUESTION: Lets say that Chris Christie is at 2% with a margin of + or - 3%. Could he really be a -1%?

3) A better idea might be to RANDOMLY partition the field into two groups, one of size 8 and one of size 9, and have two debates that way.What randomizer would they use? This is small enough they really could just put slips of paper in a hat and draw them. If they had many more candidates we might use Nisan-Wigderson.

4) How did they end up with 17 candidates?

a) Being a Candidate is not a well defined notion. What is the criteria to be a candidate? Could Lance Fortnow declare that he is a candidate for the Republian Nomination (or for that matter the Democratic nomination). YES. He's even written some papers on Economics so I'dvote for him over... actually, any of the 17. RUN LANCE RUN! So ANYONE who wants to run can! And they Do! I'm not sure what they can do about this---it would be hard to define ``serious candidate'' rigorously.

b) The debate is in August but the Iowa Caucus isn't until Feb 1. So why have the debate now? I speculate that they wanted to thin out the field early, but this has the opposite effect--- LOTS of candidates now want to get into the debates.

c) (I've heard this) Campaign Finance laws have been gutted by the Supreme court, so if you just have ONE mega-wealthy donor you have enough money to run. Or you can fund yourself (NOTE- while Trump could fund himself, sofar he hasn't had to as the media is covering him so much).

d) Because there are so many, and no dominating front runner, they all think they have a shot at it. So nobody is dropping out. Having a lot of people running makes more people want to run. (All the cool kids are doing it!)