This article led me to the homepage for Wombat Voting, which has implemented an end-to-end cryptographically verifiable voting system that will be used in the primary election for one of Israel’s political parties (Meretz). Alon Rosen is the faculty member in charge of the project, and the system is built on top of a mix-net (“Verificatum”) developed by Douglas Wikstrom.

It’s always nice to see cryptographic protocols developed by the research community actually being used in practice.

1. Cybersecurity Research Experience for Undergraduates in Science and Engineering at the University of Maryland (Note: I am one of the faculty mentors for this.)

2. Women in Theory Workshop

See below for more details.

Cybersecurity Research Experience for Undergraduates in Science and Engineering at the University of Maryland

We are looking for Cybersecurity Scholars for the 2012 summer research experience for undergraduates (REU) program at the University of Maryland.

APPLICATION DEADLINE: February 15, 2012

The Clark School of Engineering at the University of Maryland is seeking applications for scholars to become integral members of team-based research projects in cybersecurity coordinated by faculty in the Maryland Cybersecurity Center (MC2). Students majoring in engineering, computer science, math, and physical science are strongly encouraged to apply.

Teams conduct research from June 4 through August 3, 2012. The program offers multiple tiers of mentorship and training in team skills and project organization, as well as addressing issues of concern to women and minorities in science and engineering. Each Scholar receives a $4,500 stipend, a $300 food allowance, and housing. Funding is available for transportation.

For additional information and applications, please review the Cybersecurity REU website or contact Dr. Michel Cukier (mcukier@umd.edu or 301-314-2804).

This program is funded by the National Science Foundation and the Clark School of Engineering.

Women in Theory Workshop

Calling all Women PhD Students (and a few undergrads). We will be having our bi-annual Women in Theory (WIT) Workshop this year in Princeton. The dates are June 23-27, 2012.

Applications are due on Feb 29, 2012.

See here for all the relevant information.

Hoping to see you in June!
Shubhangi Saraf, Lisa Zhang, Moses Charikar, and Tal Rabin

I’ve seen too many workshops/talks with this (or a similar) title, where it was clear that the answer (“yes, of course!”) was a foregone conclusion.

In that light, I was pleased to see from the list of speakers, titles, and (especially) abstracts that this upcoming workshop on the theme appears like it will take a more nuanced approach.

I wish I could go, actually, but the timing (right at the beginning of the semester) is terrible.

(Followup to my previous post. This is the last on this topic — I promise!)

Overall I was fairly pleased with how the complexity course I taught this past semester went. Still, there are are few things I would change, or at least that I would like to change, the next time I teach it.

What would I add?

At the beginning of the semester, I had planned to cover more material. There are of course several topics I could add, but what struck me the most looking back over the course was that, with one exception, I didn’t cover a single result from after 1995. Somehow that seems wrong, and I’d like to fix it. Any suggestions for what new(er) results to add? My personal constraints are: (1) it should be a topic that is (relatively) easy to motivate for students from outside TCS, and (2) it should be something where I can cover the full proof, or at least a full proof of the main components, in some “reasonable” number of lectures, conditioned on the other material I already cover. (I don’t like presenting “high-level overviews” of results, which is why I wouldn’t cover Williams’s recent ACC0 lower bound, for example.)

As far as my personal interests go, I would probably spend more time on time- and space-bounded derandomization (including Reingold’s result that SL=L), and possibly average-case complexity. Perhaps I could cover Dinur’s proof of the PCP theorem. I had also planned to cover the (old!) proof that TIME(t) is contained in SPACE(t/log t), and may finally get to that next time.

The only other (minor) thing I would add is a proof of oblivious TM simulation. I didn’t cover it this time around because I didn’t think the result was worth the tedious details of the proof. But oblivious simulation seems necessary (or at least highly beneficial) for several other results, and important enough in its own right, that I think I will add it next time.

What would I cut?

Unfortunately, for every topic added some other topic must be taken away. (This year, for example, I cut Mahaney’s theorem and didn’t feel any loss.) So what goes?

• For starters, I think some lectures can be compressed: my first three lectures, for example, (where I introduce Turing machines, P, NP, and NP-completeness) could surely be compressed to two, and I probably don’t need two lectures to prove IP=PSPACE.
• I may cut my half-lecture discussion on time-space tradeoffs for SAT. I like the result a lot (and will be sad to see it go), and the fact that there is a relatively simple proof is nice, but somehow I don’t find the proof very illuminating and it seems disconnected from other material.
• As discussed extensively here, I am going to pass on teaching Ladner’s theorem next time. (Though I will still mention the result.) I may cut the discussion of the BGS relativization of P vs. NP, though I consider that result important enough that I would think twice before doing so.
• I’d be ok with losing the lecture on zero knowledge. Cool as zero knowledge is, I consider it a “crypto” topic rather than a “complexity” topic.
• I taught Toda’s theorem for the first time this year, but think I will cut it next time around. For one thing, I was not able to convince myself (or the students) why the result is fundamentally interesting — on the face of it, the theorem just relates two complexity classes that are both much more powerful than P. The only argument I can see in its favor is that it shows the power of #P, but I think one’s intuition already says that #P is pretty powerful, and the proof of Toda’s theorem is way too messy to justify this benefit. (I realize that Toda’s theorem has historical significance, but I don’t think that justifies covering it now.)

Other suggestions?

I taught Complexity Theory this past semester, and spent an inordinate amount of time — really, too much time — writing detailed lecture notes for each class. I figure I may as well advertise them in the hopes that others will find them useful. The full set of notes (almost 130 pages!) is available here.

Standard disclaimer: While the notes themselves are in excellent shape, I did not do much “final polishing” before posting them online. In particular, I am inconsistent with how I handle references and I apologize to anyone who feels their work has been slighted.

Comments (and corrections) on the notes are very welcome!

In writing up my final exam for the complexity class I am teaching, I realize (once again) how much I hate writing exams. I just don’t see a good way to do it. All I really want to do is test students’ understanding of the material, not how “clever” they are. On the other hand, I don’t want to ask completely trivial questions either. But there don’t seem to be very many questions that fall in the “sweet spot” in the middle. (Sigh.)

The Dept. of Computer Science at UMD has two openings for faculty positions in cybersecurity. Cryptographers are welcome to apply (last year we interviewed several), and anyone who wants more information is welcome to contact me directly.

We also have an ongoing search for a director for our cybersecurity center.

I’m teaching complexity theory this fall. (Check out my syllabus and lecture notes!) I’ve fallen about half a lecture behind where I thought I would be at this point, so to catch up I’m debating whether to omit Ladner’s theorem. Should I? Here are the main reasons I was originally planning to cover it:

1. It is a famous result.
2. The proof is not very difficult (so it doesn’t take a lot of time to cover); though see below.
3. It is in Chapter 3 of the Arora-Barak book, which I am roughly following.

On the other hand, once I thought about omitting it, I came up with stronger reasons not to cover it:

1. To me it seems like a “so what?” result. So there are languages in NP\P that are not NP-complete…who cares? (It is a natural question, but the result isn’t very satisfying because you get a completely ridiculous language.) I am also unaware of any interesting results that are proved by relying on Ladner’s theorem.
2. I find the proof extremely technical, messy, and un-illuminating.
3. I am not aware of the specific techniques being useful in some other context, certainly not for anything I was planning to teach later on this semester.

It is worth comparing Ladner’s theorem to the two other results in Chapter 3 of Arora-Barak (that I will cover this semester): hierarchy theorems, and the [BGS] result that the P vs. NP question does not relativize. Point-by-point:

1. I think both these results are very important in their own right. Moreover, hierarchy theorems are invoked frequently in proofs of other results. The [BGS] result is interesting as an illustration of being able to rule out a particular approach to solving a problem.
2. The proofs of both these results are somewhat technical, but I find them much cleaner than the proof of Ladner’s theorem. I think they also both have a pretty clear high-level intuition (something I find lacking in the proof of Ladner’s theorem).
3. The techniques used are applicable elsewhere (though not anywhere later in my class). The hierarchy theorems offer a clear demonstration of diagonalization (and, of course, are useful starting points when trying to prove other hierarchy theorems). Oracle separations were in vogue a decade or two ago in complexity, and are still popular (though in a different sense) in cryptography. I could imagine that when starting to work on many complexity questions, even today, a first question would be to ask whether the statement you are trying to prove relativizes.

I guess I’ve managed to convince myself not to cover it this semester. Anyone want to try to convince me otherwise?

(One of several arguments against writing journal papers, actually, but I’ll save that for another post.)

Conference version: 2005
Submitted to journal: 2008
Accepted to journal (pending revisions): 2010
Revised version submitted: Feb. 2011
Revised version accepted: June 2011
Final manuscript submitted: September 8, 2011
Publication date: ??
(sigh)

I will have a postdoc position available in my group starting Sept. 1. This will be a 1-year position, with the possibility of extending it to a second year. Shorter-term visits, or start dates after Sept. 1, can also be considered.

The position is fairly open. In particular, I would encourage applicants who work on more applied aspects of computer/network security in addition to those who work on cryptography. Students in the areas of information theory, game theory, or complexity-theoretic aspects of cryptography will also be considered.

If you are interested, please send me an email with a copy of your CV, a short research statement, and the name of at least one reference.