Lance Fortnow's Blog, page 114
February 12, 2014
IEEE and the Conference on Computational Complexity
Dieter van Melkebeek, current conference chair of the IEEE Conference on Computational Complexity has set up a forum to discuss the future affiliation of the conference. Read over the manifesto and update. You can give general comments on the the about post. Dieter discusses three options:
Remain with IEEE
Have a joint ACM/IEEE conference in some fashion.
Become an unaffiliated conference.
For most of you this shouldn't matter at all. Most of you readers have never attended the complexity conference (though you ought to give it a try sometime) and those that do would probably continue attending no matter who sponsors the meeting.
There has been a go-it-yourself tendency in this field so as not to pay any organization fees and to publish papers in an open-access format. Just realize this approach has some potential downfalls.
Without a sponsor, the conference and in particular the organizing committee, is fully responsible for any deficit. One bad hotel contract can sink a conference. To guard against this, you'll need to budget a surplus far larger than IEEE or ACM would require. Also IEEE and ACM can use their influence to get better deals such as on hotels.
You'll need considerably more volunteer time from faculty to handle the larger administrative load. This time doesn't show up in the financial calculation but it is a real expense.
Having a sponsoring organization gives a set of checks and balances to guarantee that the conference retains a consistent mission and be fiscally responsible. If a conference is solo and the organizing committee drops the ball, the conference just disappears.
I'm not recommendation here, just trying to point out some pitfalls that usually don't get discussed. I'll stay out of the actual debate on the future sponsorship of CCC and leave that to the younger generation.
Remain with IEEE
Have a joint ACM/IEEE conference in some fashion.
Become an unaffiliated conference.
For most of you this shouldn't matter at all. Most of you readers have never attended the complexity conference (though you ought to give it a try sometime) and those that do would probably continue attending no matter who sponsors the meeting.
There has been a go-it-yourself tendency in this field so as not to pay any organization fees and to publish papers in an open-access format. Just realize this approach has some potential downfalls.
Without a sponsor, the conference and in particular the organizing committee, is fully responsible for any deficit. One bad hotel contract can sink a conference. To guard against this, you'll need to budget a surplus far larger than IEEE or ACM would require. Also IEEE and ACM can use their influence to get better deals such as on hotels.
You'll need considerably more volunteer time from faculty to handle the larger administrative load. This time doesn't show up in the financial calculation but it is a real expense.
Having a sponsoring organization gives a set of checks and balances to guarantee that the conference retains a consistent mission and be fiscally responsible. If a conference is solo and the organizing committee drops the ball, the conference just disappears.
I'm not recommendation here, just trying to point out some pitfalls that usually don't get discussed. I'll stay out of the actual debate on the future sponsorship of CCC and leave that to the younger generation.
February 9, 2014
Superbowl underdogs and overdogs
(Stephen Colbert tells me that NFL guards their copyright of the name of the game they played on Sunday, which is why stores say they have a `big game sale on beer'. I will get around this the same way he does. I hope he doesn't sue.)
In Superb owl XLVIII (48) (one of the few uses of Roman Numerals left) Denver was the favorite but got beaten. This is not so unusual and they were not a favorite by much-just 2.5 points. But they lost 43-8. That sounds unusual--- for the favorite to get completely whomped (spellcheck thinks that's not a word, but spellcheck doesn't even think spellcheck is a word).
So- how uncommon is it for the favorite to get whomped? We would need a rigorous definition of whomped. I'll say two touchdowns, or 14 points. A list of all of the superb owl games and what the spread was and what happened is here. I summarize:
The underdog WON 15 times. The most surprising was probably when the NY Jets were an 18-point underdog to the Baltimore Colts in Supeb owl III in 1969 and won 16-7. Good thing they won since Joe Namath (the NY Jets QB) guaranteed victory.
In 2010, Superb owl 44, Indianapolis was a 5 points favorite over the New Orleans Saints but the Saints whomped 31-17.
In 2003, Superb owl 37, Tampa Bay was a 4 point underdog to Oakland. Tampa Bay whomped by winning 48-21.'
In 1988, Supeb owl 22, Washington was a 3 point underdog to Denver, but Washington whomped 42-10.
In 1984, Superb owl 18, LA was a 3-point underdog to Washington, but LA whomped 38-9.
In 1981, Superb owl 15, Oakland was a 3 point underdog to Philadelphia, but Oakland Whomped 27-10.
In 1970, Superb owl 4, Kansas City was a 12 point underdog to Minnesoda, but whomped 23-7. The reason they were an underdog is that people still though the AFC to be the lesser league and didn't remember that in Superb Owl 3 the AFC won (though didn't whomp).
So the underdog has whomped 5 times. That is FAR MORE than I would have thought. Does this show that underdogs are undervalued? Not sure since if an underdog wins it doesn't matter by how much for the betting, where as if a favorite wins it matters by how much for the point spread.
This may also call into question if point-spread is the best way to express `this teams is that much better than that team'. One issue (though it was NOT an issue in Superb owl 48) is that if a team is behind
then they may use a high-risk high-reward strategy which, if it fails, they lose my a lot. The phrase one may hear is ``the game was closer than the score''. Note that for baseball they don't do point spreads, they do odds instead. Should Football follow that? What are the PROS and CONS of points spread vs odds?
The cliche is `I watch the game for the commercials' I actually skip the game and watch the `best of superb owl commercials' that come the week before the game.
In Superb owl XLVIII (48) (one of the few uses of Roman Numerals left) Denver was the favorite but got beaten. This is not so unusual and they were not a favorite by much-just 2.5 points. But they lost 43-8. That sounds unusual--- for the favorite to get completely whomped (spellcheck thinks that's not a word, but spellcheck doesn't even think spellcheck is a word).
So- how uncommon is it for the favorite to get whomped? We would need a rigorous definition of whomped. I'll say two touchdowns, or 14 points. A list of all of the superb owl games and what the spread was and what happened is here. I summarize:
The underdog WON 15 times. The most surprising was probably when the NY Jets were an 18-point underdog to the Baltimore Colts in Supeb owl III in 1969 and won 16-7. Good thing they won since Joe Namath (the NY Jets QB) guaranteed victory.
In 2010, Superb owl 44, Indianapolis was a 5 points favorite over the New Orleans Saints but the Saints whomped 31-17.
In 2003, Superb owl 37, Tampa Bay was a 4 point underdog to Oakland. Tampa Bay whomped by winning 48-21.'
In 1988, Supeb owl 22, Washington was a 3 point underdog to Denver, but Washington whomped 42-10.
In 1984, Superb owl 18, LA was a 3-point underdog to Washington, but LA whomped 38-9.
In 1981, Superb owl 15, Oakland was a 3 point underdog to Philadelphia, but Oakland Whomped 27-10.
In 1970, Superb owl 4, Kansas City was a 12 point underdog to Minnesoda, but whomped 23-7. The reason they were an underdog is that people still though the AFC to be the lesser league and didn't remember that in Superb Owl 3 the AFC won (though didn't whomp).
So the underdog has whomped 5 times. That is FAR MORE than I would have thought. Does this show that underdogs are undervalued? Not sure since if an underdog wins it doesn't matter by how much for the betting, where as if a favorite wins it matters by how much for the point spread.
This may also call into question if point-spread is the best way to express `this teams is that much better than that team'. One issue (though it was NOT an issue in Superb owl 48) is that if a team is behind
then they may use a high-risk high-reward strategy which, if it fails, they lose my a lot. The phrase one may hear is ``the game was closer than the score''. Note that for baseball they don't do point spreads, they do odds instead. Should Football follow that? What are the PROS and CONS of points spread vs odds?
The cliche is `I watch the game for the commercials' I actually skip the game and watch the `best of superb owl commercials' that come the week before the game.
February 6, 2014
Favorite Theorems: Connecting in Log Space
We start the favorite theorems with a result that might surprise many is still less than ten years old.
Undirected Connectivity in Log-Space by Omer Reingold (PDF)
Intuitively, this result says you can tell if two points are connected in a complex maze by only having to remember the equivalent of a constant number of locations in the maze. Reingold's algorithm builds an expander graph based on the zig-zag construction in a very clever way that uses very little space to construct and to check that two points connect.
In 1979, Aleliunas, Karp, Lipton, Lovász and Rackoff showed that one can solve s-t connectivity in randomized logarithmic space by taking a random walk on the graph. My last favorite theorem from 2004 talked about derandomizing space algorithms and before Reingold the best algorithm for s-t connectivity required log4/3 space. Indepently of Reingold, Vladimir Trifonov gave a O(log n log log n) space algorithm for s-t connectivity, a victim of bad timing.
One neat implication of Reingold's result is a new and simpler characterization of log-space as the set of problems expressible in first-order logic with ordering and symmetric transitive closure.
After Reingold's result we might have expected solutions to a number of related problems but we didn't see much progress.
Can every randomized log-space algorithm be derandomized in log space?
Do there exist log-space computable universal traversal sequences?
Can we solve directed s-t connectivity better than Savitch?
Can we modify Reingold's algorithm to bring log space into NC1?
Undirected Connectivity in Log-Space by Omer Reingold (PDF)
Intuitively, this result says you can tell if two points are connected in a complex maze by only having to remember the equivalent of a constant number of locations in the maze. Reingold's algorithm builds an expander graph based on the zig-zag construction in a very clever way that uses very little space to construct and to check that two points connect.
In 1979, Aleliunas, Karp, Lipton, Lovász and Rackoff showed that one can solve s-t connectivity in randomized logarithmic space by taking a random walk on the graph. My last favorite theorem from 2004 talked about derandomizing space algorithms and before Reingold the best algorithm for s-t connectivity required log4/3 space. Indepently of Reingold, Vladimir Trifonov gave a O(log n log log n) space algorithm for s-t connectivity, a victim of bad timing.
One neat implication of Reingold's result is a new and simpler characterization of log-space as the set of problems expressible in first-order logic with ordering and symmetric transitive closure.
After Reingold's result we might have expected solutions to a number of related problems but we didn't see much progress.
Can every randomized log-space algorithm be derandomized in log space?
Do there exist log-space computable universal traversal sequences?
Can we solve directed s-t connectivity better than Savitch?
Can we modify Reingold's algorithm to bring log space into NC1?
February 3, 2014
Contribute to the Martin Gardner Centennial
Dana Richards emailed us about a place to write how Martin Gardner influenced you. You can leave such comments here. I left a comment there, but I expand it for this blog entry.
When I got interested in mathematics in high school I went to the public library looking for math books (this was before Al Gore invented the internet). I found some books by Martin Gardner and began reading them. They were just right for the level of math I was on at the time. My very first proof that I read on my own (outside of a class) was in those books- the proof that (in the terminology I use now) a graph is Eulerian iff every vertex has even degree.
I learned about SOMA cubes (I bought a set and did every puzzle in the book in about 2 days.This is the only evidence that as a kid I was good at math). I learned the unexpected hanging paradox which confused me then (and still does). I learned the hercules-hydra game and other games that go on for a LOOOOOOOOOONG time. They are related to things in logic. I also learned about NIM games which I have used as a starting point for several student projects.
There have been some conferences in his honors, the Gathering-for-Gardner. I had the pleasure of reviewing some of the books from it. (My review is here.) These articles show that while his work was recreational this is not a well defined term- some if relates to very important and deep mathematics, and some deep math has arisen from such problems. The books also have articles about Gardner the Magician.
In the 2000's some of his books were reprinted and I was asked to review them for my SIGACT News book review column. I took this opp to do a joint review of several math recreational books. What a delight to reread his books and contrast them to those of his successors. And I STILL learned some math that I didn't know from them. (My review is here.)
Shortly before a column appears I always email the authors-of-books, authors-of-reviews, and publishers a first draft of my column. His publisher told me that he didn't use email (he was in his 90's!) so I postal mailed him my review. He read it, corrected some typos, but otherwise was quite happy with the review. He died a few months later. I was happy to have some contact, albeit short, with the man who helped keep me interested in math in high school and beyond.
When I got interested in mathematics in high school I went to the public library looking for math books (this was before Al Gore invented the internet). I found some books by Martin Gardner and began reading them. They were just right for the level of math I was on at the time. My very first proof that I read on my own (outside of a class) was in those books- the proof that (in the terminology I use now) a graph is Eulerian iff every vertex has even degree.
I learned about SOMA cubes (I bought a set and did every puzzle in the book in about 2 days.This is the only evidence that as a kid I was good at math). I learned the unexpected hanging paradox which confused me then (and still does). I learned the hercules-hydra game and other games that go on for a LOOOOOOOOOONG time. They are related to things in logic. I also learned about NIM games which I have used as a starting point for several student projects.
There have been some conferences in his honors, the Gathering-for-Gardner. I had the pleasure of reviewing some of the books from it. (My review is here.) These articles show that while his work was recreational this is not a well defined term- some if relates to very important and deep mathematics, and some deep math has arisen from such problems. The books also have articles about Gardner the Magician.
In the 2000's some of his books were reprinted and I was asked to review them for my SIGACT News book review column. I took this opp to do a joint review of several math recreational books. What a delight to reread his books and contrast them to those of his successors. And I STILL learned some math that I didn't know from them. (My review is here.)
Shortly before a column appears I always email the authors-of-books, authors-of-reviews, and publishers a first draft of my column. His publisher told me that he didn't use email (he was in his 90's!) so I postal mailed him my review. He read it, corrected some typos, but otherwise was quite happy with the review. He died a few months later. I was happy to have some contact, albeit short, with the man who helped keep me interested in math in high school and beyond.
January 29, 2014
Snow Days
An unexpected snowstorm hits the city in the middle of a workday. The roads get hopelessly clogged and I'm lucky to get home--many others just abandoned their cars, or slept in them. I'm talking about Valentine's Day, February 14, 1990 in Chicago. But the same story hit Atlanta yesterday. One big difference--Georgia Tech is closed today and tomorrow because the city can't handle the ice. The University of Chicago was open on February 15th.
When these events happen, people wonder about the planning. Was it wise for all schools and businesses to shut down about the same time, early yesterday afternoon? Lots of blame to go around (and having CNN based in Atlanta guarantees coverage) but it is not clear that any plan would have done much better--how do you get millions of people safely home with dangerous roads and a limited public transit system? One of these times you wish P = NP and you can just find the right algorithm. One of the issues is that freak mid-day snowstorms don't happen that often, the last major one in Atlanta was 1982.
Meanwhile back in Chicago, schools were closed earlier this week, not for snow but for cold. But it was that cold on a regular basis back in the 90's. Global warming has changed expectations, as so brilliantly illustrated in this xkcd.
When these events happen, people wonder about the planning. Was it wise for all schools and businesses to shut down about the same time, early yesterday afternoon? Lots of blame to go around (and having CNN based in Atlanta guarantees coverage) but it is not clear that any plan would have done much better--how do you get millions of people safely home with dangerous roads and a limited public transit system? One of these times you wish P = NP and you can just find the right algorithm. One of the issues is that freak mid-day snowstorms don't happen that often, the last major one in Atlanta was 1982.
Meanwhile back in Chicago, schools were closed earlier this week, not for snow but for cold. But it was that cold on a regular basis back in the 90's. Global warming has changed expectations, as so brilliantly illustrated in this xkcd.
January 27, 2014
Fermat's Last Theorem and Large Cardinals. Really!
A brilliant math ugrad at UMCP, Doug, is also a creative writer who
wants to work on large cardinals. His creative writing may help him there.
We had the following conversation:
DOUG: The proof of Fermat's last theorem depends on the existence
of certain large cardinals and hence is not in ZFC.
BILL: That is not true.
DOUG: Have you read the proof?
BILL: No, however, if that were true I would know it. See this blog entry.
DOUG: Why would you know it?
BILL: If FLT required LCs then
a) Number theorists would be nervous.
b) Logicians would be ecstatic
c) The math community would not have announced to the world that FLT was solved.
d) Wiles would not have collected his prize money for solving it.
e) Again, I would know it.
DOUG: All compelling arguments. Even so, FLT requires LCs.
BILL: I will bet you five dollars that the current proof of FLT does not depend on LCs.
DOUG: Uh. Your counter arguments are compelling.
BILL: So... no bet?
DOUG: Uh. No.
The next day I got an email from Doug with the subject heading
I cheated myself out of five dollars.
Doug found this article, What does it take to prove Fermat's Last Theorem? Grothendieck and the logic of number theory by Colin McLarty, from 2009.The article says that YES the current proof of FLT DOES depend on LCs. Note that the proof is quite long and uses lots of other stuff that is sort of buried in it. So--- whats the catch?Why aren't number theorists nervous and logicians ecstatic? According to the article anyone who reads the proof of FLT and wanted to could unwind it and get it down to ZFC (and likely down to PA). But nobody has bothered yet.Hence nobody is nervous or ecstatic.
I will take their word for it, but it does make ME nervous. NOT about FLT which I am sure enough people have looked at (and looked at the background literature) that it really can be made to work in ZFC.I am more worried about papers that are not quite so looked at as having LC assumptions that are hidden from the reader that cannot be easily removed.
However KUDOS to Doug for telling me something in math that I did not know and should have. I will treat him to a more-than-five-dollar-lunch.
Postscript: AH, the article was right: FLT was proven using ordinary set theory last year. (See here) by Colin McLarty (I assume its the same person). I will still take Doug to lunch- in a stupid, pedantic, technical sense I was right- the current (2014) proof of FLT did not use LC. But for the real issue of there being any problem at all, I was clearly wrong. Only a logician would say I was right. Hmm- Doug is a logician. Its up to him. (Hmm- my spell checker allows `Hmm' but not `Hmmm')
January 23, 2014
What will we wrought?
When I went to college in the early 80's, students protested against college endowments invested in companies that had business in apartheid South Africa. My mother worked as a statistician for one of those companies. An interesting dilemma, do I support a policy that hurts the company that is indirectly helping to put me through college?
Now my daughter is in college and worrying that the computing revolution will make it hard to find a job once she graduates and making her consider those job prospects in the major she chooses. And what am I? Chair of a computer science department that helps push that revolution forward.
Computing gets quite a bit of blame these days for the widening income gap between the have and the have nots, and jobs taken over by automation, but without causing a corresponding need for other types of jobs, other than those that serve computation itself. Are those fears real? We can't answer that question yet, positively or negatively. Time will tell.
For now, we just need to do our jobs, making computing better but also understanding and mitigating the negative effects of computing. We need to make sure that computing technology becomes a growing sea that raises all boats, and not just making the world better for the technological elite.
While I stand in awe in how computer science has changed the world, I hope we don't ever end up with CS leaders getting together and saying "What have we wrought?"
Now my daughter is in college and worrying that the computing revolution will make it hard to find a job once she graduates and making her consider those job prospects in the major she chooses. And what am I? Chair of a computer science department that helps push that revolution forward.
Computing gets quite a bit of blame these days for the widening income gap between the have and the have nots, and jobs taken over by automation, but without causing a corresponding need for other types of jobs, other than those that serve computation itself. Are those fears real? We can't answer that question yet, positively or negatively. Time will tell.
For now, we just need to do our jobs, making computing better but also understanding and mitigating the negative effects of computing. We need to make sure that computing technology becomes a growing sea that raises all boats, and not just making the world better for the technological elite.
While I stand in awe in how computer science has changed the world, I hope we don't ever end up with CS leaders getting together and saying "What have we wrought?"
January 20, 2014
We don't care about Ballroom Dancing. Should we?
YOU got into your undergrad school because not only were you good at Math but you were on
the Fencing Team and in the Latin Club (so you could taunt your opponents in Latin: ouyah allcay athay an alestrabay!). Also you had a letter from your principal who never had you for a class but can comment on your leadership since you organized a pep rally for the football team. Why does UNDERGRAD admissions care about these things? Because, while they want good students, they also want to build a community of scholars of different interests and abilities.
YOU apply to grad school in Computer Science. Hey, it worked once maybe it will work again! You write about being in the ballroom dancing club and you have a letter from the Dean, who never had you in a class,
but you worked in his office and he can attest that you are a good leader and a hard worker.
Does the admissions committee care? NO. The only things we care about are CS, MATH, and RESEARCH. A letter from someone not in math or science is worthless. Some exceptions and thoughts:
If you recorded ballroom dancing and made a project out of how to teach it using some interesting new technology this IS good. This is likely an Human-computer-interaction project; however, I would care about this no matter what field you are going into.
If you have an interest in Nat Lang Proc and know Linguistics I would care. I would think that knowing a foreign language would also be good.
If you are going to go into Human computer Interaction then Psychology helps.
If you are going to do Quantum Computing then Physics is good. However, whatever you do Physics is good as its more evidence of math ability.
For ugrad its been said that if your parents are powerful OR donors you may have an easier time getting into some UGRAD schools. What about Grad school? I've honestly never seen a case of this so I honestly don't know.
I know a student who is an excellent math major but also a creative writer. I doubt this will help him.
but should it?
I once saw in a students application a letter from his preacher attesting to his fine moral character.
Do we care? should we? How about the other way around- if someone was an EXCELLENT programmer and math person but served 8 years for armed robbery would we care? This might not be fair since perhaps he reformed.
but my real question is- for grad admissions we don't care about Ballroom Dancing or other misc.
Is this a mistake? If someone was NOT as good at math BUT a better writer, should we take them?
the Fencing Team and in the Latin Club (so you could taunt your opponents in Latin: ouyah allcay athay an alestrabay!). Also you had a letter from your principal who never had you for a class but can comment on your leadership since you organized a pep rally for the football team. Why does UNDERGRAD admissions care about these things? Because, while they want good students, they also want to build a community of scholars of different interests and abilities.
YOU apply to grad school in Computer Science. Hey, it worked once maybe it will work again! You write about being in the ballroom dancing club and you have a letter from the Dean, who never had you in a class,
but you worked in his office and he can attest that you are a good leader and a hard worker.
Does the admissions committee care? NO. The only things we care about are CS, MATH, and RESEARCH. A letter from someone not in math or science is worthless. Some exceptions and thoughts:
If you recorded ballroom dancing and made a project out of how to teach it using some interesting new technology this IS good. This is likely an Human-computer-interaction project; however, I would care about this no matter what field you are going into.
If you have an interest in Nat Lang Proc and know Linguistics I would care. I would think that knowing a foreign language would also be good.
If you are going to go into Human computer Interaction then Psychology helps.
If you are going to do Quantum Computing then Physics is good. However, whatever you do Physics is good as its more evidence of math ability.
For ugrad its been said that if your parents are powerful OR donors you may have an easier time getting into some UGRAD schools. What about Grad school? I've honestly never seen a case of this so I honestly don't know.
I know a student who is an excellent math major but also a creative writer. I doubt this will help him.
but should it?
I once saw in a students application a letter from his preacher attesting to his fine moral character.
Do we care? should we? How about the other way around- if someone was an EXCELLENT programmer and math person but served 8 years for armed robbery would we care? This might not be fair since perhaps he reformed.
but my real question is- for grad admissions we don't care about Ballroom Dancing or other misc.
Is this a mistake? If someone was NOT as good at math BUT a better writer, should we take them?
January 16, 2014
Favorite Theorems: Introduction
I was invited to give a talk at the FST&TCS conference held in December 1994 in Madras (now Chennai). As I searched for a topic, I realized I was just finishing up my first decade as a computational complexity theorist so I decided to recap the past decade by listing My favorite ten complexity theorems of the past decade (PDF). Not so much to choose winners, but use the theorems to survey the great research during those past ten years.
In 2004, I repeated the exercise in my then young blog for the years 1995-2004. In 2005, I went back in time and chose my favorite theorems from the first decade of complexity (1965-1974) and in 2006 I covered 1975-1984, completing the backlog of the entire history of computational complexity.
Now in 2014 we start again, recapping my favorite theorems from 2005-2014, one a month from February through November with a recap in December. These theorems are chosen by a committee of one, a reward only worth the paper they are not written on. I choose theorems not primarily for technical depth, but because they change the way we think about complexity. I purposely choose theorems with breadth in mind, using each theorem to talk about the progress of a certain area in complexity. I hope you'll be presently surprised by progress we've made in complexity over the past decade.
In 2004, I repeated the exercise in my then young blog for the years 1995-2004. In 2005, I went back in time and chose my favorite theorems from the first decade of complexity (1965-1974) and in 2006 I covered 1975-1984, completing the backlog of the entire history of computational complexity.
Now in 2014 we start again, recapping my favorite theorems from 2005-2014, one a month from February through November with a recap in December. These theorems are chosen by a committee of one, a reward only worth the paper they are not written on. I choose theorems not primarily for technical depth, but because they change the way we think about complexity. I purposely choose theorems with breadth in mind, using each theorem to talk about the progress of a certain area in complexity. I hope you'll be presently surprised by progress we've made in complexity over the past decade.
January 14, 2014
A short History of Crypto
I taught a 3-week summer course to High School Students called
which did some theory. One thing I did was the following storyline:
Shift Cipher
Affine Cipher
Gen perm cipher (any perm of a,b,c,...,z
PROOF that perm is unbreakable: Eve has to go through all 26! possibilities
PROOF that perm IS breakable: Freq analysis. Moral of the story: Any proof that a system is unbreakable makes some assumptions that Eve might not agree to. Hence proving security is tricky.
Matrix Ciphers. PROOF that if you use a big enough matrix its unbreakable. Sort-of true for ciphertext only (though I doubt really proven). PROOF that requires going through all possibile nxn matrices that have det rel prime to 26 to crack it using plaintext only. PROOF that this is NOT true (I leave that to my reader).
Vig Cipher. Proof that its unbreakble, Proof that you can break it
I was very happy with this since it really instilled in them that proofs of security are nontrivial and always have assumptions. That does not mean they are not worth anything, but you want to get the assumptions explicit to if (or even WHEN) the system is broken, you can see what assumption needs to be attended to for the next iteration. One caution- these were VERY GOOD students so they GOT IT. They didn't mistake the false proofs for real ones.
(NOTE-- I never teach the cows paradox - all cows are the same color- when
doing induction since half the class will think induction can prove anything and the other half will think that all cows are the same color.)
I then encapsulated all of this with what I call A SHORT HISTORY OF CRYPTO:
For i=1 to infinity
Alice and Bob: We have a cipher that nobody can crack
Alice and Bob: We have PROVEN that it can't be cracked
Eve: I just cracked it
Alice and Bob: Whoops.
(I later did Diffie-Hellman in the class which I will talk about in a later blog.)
Computer Science: A Hands Off Approach
which did some theory. One thing I did was the following storyline:
Shift Cipher
Affine Cipher
Gen perm cipher (any perm of a,b,c,...,z
PROOF that perm is unbreakable: Eve has to go through all 26! possibilities
PROOF that perm IS breakable: Freq analysis. Moral of the story: Any proof that a system is unbreakable makes some assumptions that Eve might not agree to. Hence proving security is tricky.
Matrix Ciphers. PROOF that if you use a big enough matrix its unbreakable. Sort-of true for ciphertext only (though I doubt really proven). PROOF that requires going through all possibile nxn matrices that have det rel prime to 26 to crack it using plaintext only. PROOF that this is NOT true (I leave that to my reader).
Vig Cipher. Proof that its unbreakble, Proof that you can break it
I was very happy with this since it really instilled in them that proofs of security are nontrivial and always have assumptions. That does not mean they are not worth anything, but you want to get the assumptions explicit to if (or even WHEN) the system is broken, you can see what assumption needs to be attended to for the next iteration. One caution- these were VERY GOOD students so they GOT IT. They didn't mistake the false proofs for real ones.
(NOTE-- I never teach the cows paradox - all cows are the same color- when
doing induction since half the class will think induction can prove anything and the other half will think that all cows are the same color.)
I then encapsulated all of this with what I call A SHORT HISTORY OF CRYPTO:
For i=1 to infinity
Alice and Bob: We have a cipher that nobody can crack
Alice and Bob: We have PROVEN that it can't be cracked
Eve: I just cracked it
Alice and Bob: Whoops.
(I later did Diffie-Hellman in the class which I will talk about in a later blog.)
Lance Fortnow's Blog
- Lance Fortnow's profile
- 4 followers
Lance Fortnow isn't a Goodreads Author
(yet),
but they
do have a blog,
so here are some recent posts imported from
their feed.
