SODA 2009 South Pacific Event

A note from Howard Karloff (please email him for more information):

To SODA '09 attendees:

I have reserved, for SODA attendees and their friends/spouses/significant others, 50 tickets in the loge section at Lincoln Center for the 7:00 PM, Tuesday, Jan. 6 show of "South Pacific," so popular a show that already both Saturday Jan. 3 performances are sold out. If you want to buy one or two tickets, send mail to howard@research.att.com with "South Pacific" as the subject field, specifying the number of tickets you want in the body of the e-mail. Tickets will go to the first SODA attendees who pay by credit card via PayPal. I'll send instructions by e-mail. The tickets are $120 each--the face value is $115, and the extra $5 is to cover the PayPal fee--and are NONREFUNDABLE: once you pay, there will be no refunds. However, I imagine someone at SODA, some random theatregoer, or an ebay user would be thrilled to take tickets to such a popular show off your hands.

So, please, start those e-mails coming. Should the demand far exceed 50 tickets, I may arrange a second outing, to a different play, either Saturday or Tuesday. A few reminders:

"South Pacific" starts at 7PM, not the typical 8PM start
time, on the last day of SODA.

The venue is Lincoln Center, not in the heart of Broadway.

Once you pay, there's no backing out.

See you in New York in a couple months!

Howard Karloff

Announcements

• Sanjeev Khanna reminds us that FOCS early registration deadline is Oct 3, 2008. Get your cheesesteak on !
• CFP for the 2009 sausage convention (with beer!!): Deadline is Nov 24 (abstracts), Dec 1 (papers)

About that whole political outreach business

that I was talking about in this post, here's what I find in my RSS reader today:

The names of seven distinguished scientists nominated by the President to serve on the National Science Board (NSB) were sent to the Senate for confirmation on September 16, 2008. Drawn from industry and universities, and representing a variety of science and engineering disciplines and geographic areas, these four new and three incumbent NSB members were selected for their preeminence in research, education or public service. When confirmed by the Senate, they will serve six-year terms to expire in May of 2014.
...

Diane L. Souvaine, of Massachusetts

Diane Souvaine is a computational geometer, who is professor and department chair of computer science at Tufts University, and holds a secondary appointment in the department of mathematics. Her current research focuses on the design and complexity analysis of geometry algorithms to solve problems from a variety of venues, ranging from computational statistics to geometric modeling to self-assembly of nano-structures. She also directs summer week-long institutes involving computational thinking for middle school mathematics teachers, funded by the Massachusetts Board of Higher Education. From 1992 to mid-1994, she served first as acting associate director and then as acting director of the NSF's Science and Technology Center on Discrete Mathematics and Theoretical Computer Science (DIMACS), while she was associate professor of computer science at Rutgers University. She has been a Fellow at the Radcliffe Institute for Advanced Study, and a member of the School of Mathematics at the Institute for Advanced Study in Princeton, NJ

Very cool indeed...

Loading Image

Click anywhere to cancel

Image is Unavailable

CS advocacy in the political realm

Two articles caught my eye recently:

• A posting on the CCC blog about why computer scientists should publish in magazines like Science, Nature and PNAS
• A Wired Science blog entry about Barack Obama's science advisors (John McCain has not revealed his list of science advisors)

In the first article, Peter Lee makes the argument (with an assist from Peter Harsha) that there are good political reasons for CS folks to publish in Science, Nature and the like (even if many of us snigger at the kinds of CS research that ends up there: I know I have horror stories about articles that are accepted over the objections of the specialist CS reviewers). One argument is that of influence: whether we like it or not, CACM is not the preferred reading material for Congressional aides and staffers that have the ears of elected representatives, but Science/Nature are on the radar. Moreover, these publications have well-honed PR engines to get articles out to reporters: often embarassingly overhyped, but hey, you know what they say about publicity :).

Which brings me to the second article on Barack Obama's science advisors. What's interesting is that 4 of 5 of them are from the life sciences. This is not to demean the importance of life sciences in the current policy environment (GMO crops, stem cells and biofuels are all on the political radar), but there are a good number of technical hot-button issues as well (voting machines, copyright issues, electronic eavesdropping, privacy), and it definitely wouldn't hurt to have a CS-oriented person near the "ear of the man", so to speak, to articulate a view of the importance of these issues and how the research community is dealing with them.

I'm a lowly untenured professor, who used to be a lowly lab researcher, so I have no good ideas on getting personally involved in such matters. But I can see (partially thanks to CCC and the SIGACT Theory group) how advocacy can, over time, lead to fundamental changes in the landscape of support for our efforts, so at the very least, I can consider the idea of disseminating my work (when appropriate) beyond our "incremental" conferences and exhort others to do the same.

SODA list is out

Some happy, some not so happy :)

Kudos to Claire Mathieu and the PC for not only including the list of papers, but also the list of abstracts !! Finally !!

As a public service, here's a TeX-formatted PDF of the list of abstracts, for those who find serif font easier to read than a stream of text on a web page. Warning, it's 44 pages long, and will have formatting errors. I wrote a perl script for the overall parsing and did lots of local fixing by hand for math-mode stuff, but it's not perfect.

Fonts !

John Holbo at CT does a not-review of books on fonts (or faces ? I'm confused now). In any case, this is clearly a book I need to get.

The tensor product trick

Blogging has been slow this summer as I (surprise surprise) was actually working. Today the semester starts, so I expect to be blogging more as I attempt to clear my head from the detritus of semester minutiae.

Terry Tao has a new post up in the "tricks wiki" started by Timothy Gowers. The "trick" can be summarized concisely as: if you want to prove an inequality of the form X < Y, but can only prove X < CY, then take "tensor powers" of the objects X and Y and prove the weaker inequality, and then take a "root".

What's interesting to me is that this is none other than a generalization of the "standard" amplification trick that is most commonly used in hardness results. The easiest application is the proof that CLIQUE admits no absolute approximation: if it did, take graph powers, find the additive-error number, and take square roots, and you have an exact solution (since the value must be integral). Generalizations exist: you can use the same argument to show that CLIQUE admits no constant factor approximation, and even more intricately (invoking the PCP theorem) that independent set has no polynomial-factor approximation.

It makes me wonder what other "standard" analysis tricks draw their lineage from generalizations in the world of "real math". For example, tricks involving building exponentially growing covers tend to show up frequently in topology and analysis.

$10 million for complexity theory...

Via His Quantum Holiness, news comes of the NSF Expeditions awards: each award is $10 million, and four were given out. One of them was for complexity theory, and the team is a star-studded list of complexity and algorithms folks, led by Sanjeev Arora. Here's the blurb:

In their Expedition to Understand, Cope with, and Benefit From Intractability, Sanjeev Arora and his collaborators at Princeton University, Rutgers University, New York University and the Institute for Advanced Study will attack some of the deepest and hardest problems in computer science, striving to bridge fundamental gaps in our understanding about the power and limits of efficient algorithms. Computational intractability, a concept that permeates science, mathematics and engineering, limits our ability to understand nature or to design systems. The PIs hope to better understand the boundary between the tractable and the intractable. This has the potential to revolutionize our understanding of algorithmic processes in a host of disciplines and to cast new light on fields such as quantum computing, secure cryptography and pseudorandomness. The research team plans to draw on ideas from diverse fields including algorithms, complexity, cryptography, analysis, geometry, combinatorics and quantum mechanics

Congratulations ! For getting the award, and demonstrating that hard-core complexity theory CAN get funded...

Update: Sanjeev Arora comments...

Math != calculation, part 537...

From the NYT, on scoring the i-can't-believe-it's-not-a-sport sport of gymnastics:

The new system is heavy on math and employs two sets of judges, an A panel and a B panel, to do the computations. Two A-panel judges determine the difficulty and technical content of each routine. Six B-panel judges score routines for execution, artistry, composition and technique.

The A-panel judges’ scorecards start at zero, and points are added to give credit for requirements, individual skills and skills performed in succession.

The A panel counts only the gymnast’s 10 most difficult skills, which are ranked from easiest to most difficult (from A to G for women and from A to F for men). An A-level skill, like a back handspring in the floor exercise, is worth one-tenth of a point. The value increases by one-tenth of a point for each subsequent level, meaning a B-level skill is worth two-tenths and an F-level is worth six-tenths.

Required elements add a maximum of 2.5 points to the score. Extra points, either one-tenth or two-tenths, are given for stringing skills together.

Each judge adds the marks, then the two reach a consensus. Elite gymnasts usually have a difficulty score in the 6’s; the toughest routines generally have difficulty scores in the high 6’s or 7’s.

[...]
The system rewards difficulty. But the mistakes are also more costly.

Which is where the judges on the B panel come in. They rate the execution, artistry and technique of a routine, starting at a score of 10.0 and deducting for errors.

This score, called an execution score, is where the perfect 10.0 still exists. But reaching it is unlikely.

A slightly bent knee can be a deduction of one-tenth of a point. A more drastically bent knee can cost three-tenths. In this system, the deductions jump from one-tenth to three-tenths to five-tenths. A fall costs a gymnast eight-tenths. In the old system, a fall was a five-tenths deduction.

The highest and the lowest of the judges’ scores are thrown out. The remaining four scores are averaged to obtain the final B-panel score.

On the scoreboard, the final score appears in big numbers, just above the gymnast’s marks for difficulty and execution.

Apart from my grumble about the level of 'math', it's an interesting way of doing the scoring.

I wonder if this could work for conferences: replace 'degree of difficulty' by 'hardness of problem, general hotness of the area, etc', and then you could deduct points for things like

• More than two digits after the decimal point in the approximation ratio
• exponent of running time requires the \frac environment
• More than two parameters in the running time
• Gratuitous use of O() notation to hide dependencies you don't like (yes I'm talking to you, high dimensional clustering folk)
• Requiring your winged pigs to be large in dimension, have extra glitter on the wing tips, and carry golden harps in order to make the horses take off (Hi there, complexity denizens)

The concept of an approximation

We're always searching for new ways to communicate cool ideas in theoryCS to the outside world, and the list gets more and more esoteric each time one thinks about it. But in my interactions with people, people generally unfamiliar with algorithm, and theoretical computer science in general, I'm constantly amazed at how counter-intuitive the very notion of an approximation appears to be.

A typical conversation goes something like this:

Person: Oh this problem is NP-hard so we ran this heuristic
Me: Have you tried approximating it ?
P: What do you mean ? Our heuristic seems to be reasonable.
M: I mean an algorithm that guarantees that it'll get close to optimal.
P: But how can you know that ? It's hard to find the optimal solution, global minimum, yadda yadda yadda...
M: We can often prove an answer is close to OPT without knowing OPT itself.
P: [total silence]

This kind of thing happens often in research conversations, as well as in the classroom (where it's less surprising I guess). In fact, one person was so amazed at the idea that even proving an approximation could be NP-hard that we spent a good semester plowing through the PCP theorem (at least parts of it).

I'm not dissing heuristics: it's often the case that either the approximation guarantees one can show are too weak, or that the claimed bounds don't match the empirical performance. But I do think it's important to at least ask the question of whether provable approximations exist, much in the way people in CS are now reasonable comfortable checking (or asking the resident theoretician !) if a problem is NP-hard.

But you can't ask till you know. This is one of the main reasons I teach a smattering of approximations in my graduate algorithms class (and why I teach some randomization as well). The concept of an approximation (especially when you can't find the actual answer) is a surprisingly slippery conceptual leap, and requires mental agility that goes beyond the standard "algorithms toolkit" that focuses on issues of performance.

The Katayanagi Prize

Via the Baconmeister (er.. the Quantum Pontiff), we hear that Christos Papadimitriou and Erik Demaine have received the Katayanagi Prize. Christos gets it for "research excellence":

The Katyanagi Prize for Research Excellence will be awarded annually to an established researcher with a record of outstanding, and sustained achievement.

and Erik gets it for "emerging research leadership":

The Katyanagi Emerging Leadership Prize will be awarded annually to an individual recognized as an emerging research leader.

Congratulations to both of them, (and do read the Dr. Dobbs interview with Christos, where he shows that he knows what "Guitar Hero" is :))

Edge people...

Bill Gasarch has an interesting post up comparing attendance numbers at SoCG and CCC. He introduces the interesting notion of 'edge people': people in related areas who wouldn't normally attend the conference, but would because of locality.

This of course makes me a little worried about 2010. We have a rather large 'edge' community at the U. of Utah itself within SCI. But Utah as such is fairly geographically isolated (and indeed, there's a general belief that our department suffers a little in perception as a consequence), so we don't get the 'edge' crowd that places like NYC and Maryland potentially get.

I say 'potentially': as always, it's probably possible to get data on this. Specifically, if one had access to historical attendance lists (not numbers) for SoCG, one could first identify candidate 'edge' people (either by subjective eyeballing, or even more numerically as people who only show up "rarely" and publish "rarely"), and then figure if there's a correlation between location and presence of an edge crowd.

Similarly, one might even do this for CCC vs SoCG although as one commenter points out, the larger number of total unique authors on SoCG papers might be sufficient to explain the discrepancy in attendance (Paul Beame's argument about competing conferences is also valid: I couldn't imagine going to FOCS, STOC, SODA and SoCG every single year, in addition to the various DB/data mining conferences I attend).

Women in Computing workshop, and a new blogger

Sorelle Friedler, UMD grad student in geometry, tireless staff volunteer at SoCG 2008, and former AT&T summer visitor, has a new blog. One of the first things she writes about is the Women in Theory workshop at Princeton that ran Jun 14-18. Add the feed, folks !

Money Money Money

(ed: three NSF posts in a row ? maybe you're a little obsessed with funding ?

As CRA and USACM are now reporting, the president just signed a bill that among other things allocates 62.7M in supplemental funding for the NSF. However,...

Funding for the National Science Foundation is split 70/30 between education and research programs at the Foundation with $40 million going toward the Robert Noyce Teacher Scholarship Program, which “seeks to encourage talented science, technology, engineering, and mathematics majors and professionals to become K-12 mathematics and science teachers

Which means that only 22.7M is left to be divvied up among the many directorates. Optimistically, that's roughly 44 new proposals, over ALL of NSF. Hmmm....

An open letter to journals not mirrored by ACM and DBLP

Dear journal,
If it isn't too much of a problem, could you possibly attach a BibTeX link to each article that you list ? For the sake of my cruelly abused fingers ? Could you ? PLEASE ?

NSF Update, continued: limits on submissions

I had heard a rumor about this a few months ago, and now it's confirmed: there will be a CISE-wide limit on the number of proposals submitted by a PI (or co-PI/senior personnel). Here's the relevant text (from the IIS call, but it's part of the coordinated solicitation):

In any contiguous August through December period, an individual may participate as PI, Co-PI or Senior Personnel in no more than two proposals submitted in response to the coordinated solicitation (where coordinated solicitation is defined to include the Information and Intelligent Systems (IIS): Core Programs, the Computer and Network Systems (CNS): Core Programs and the Computing and Communication Foundations (CCF): Core Programs solicitations). For example, between August 2009 and December 2009, an individual may participate as PI, co-PI or Senior Personnel in one proposal submitted to a core program in CCF and in a second proposal submitted to a core program in CNS, or an individual may participate as PI, co-PI or Senior Personnel in two proposals submitted to an IIS core program, etc.

The key difference is this: in the past, each separate solicitation (whether TF, or IIS, or whatever) had its own separate limit on the number of proposals: now the cap is summed over the coordinated solicitation. I expect there to be major rumbling about this.

One saving grace is that this only applies to the coordinated solicitation: other cross-discipline programs have their own separate caps.

The social web makes me dizzy.

1. I have a web page
   
2. I have a blog
3. I have started using twitter.
4. As it so happens, I have a facebook account
5. and I often share interesting items via Google Reader

So far so good. But here's where the fun starts.

1. The shared items from GR appear on my blog
2. Shared items, and blog posts, appear on my web page via lifestream
3. facebook updates appear in GR via an RSS feed
4. blog posts, twitter updates, facebook updates, and GR updates appear on friendfeed
5. I can read friendfeed via the web, or via twhirl, (and also twitter)
6. I can post comments to friendfeed posts via twhirl
7. Someone can post a comment to a blog post seen on friendfeed and the update appears on twhirl. I can reply to this comment and it appears on their friendfeed

It seems that the whole point of the social web is to keep us updating so much that we end up not doing anything worth announcing !

NSF Update

(ed: please ignore if you don't get (or plan to get) funding from the NSF)

A missive from Jeanette Wing sent out today tells of consolidation in the standard solicitations for CCF/CNS/IIS. To quote:

Each of CISE's three divisions will have one solicitation that covers its core activities normally covered in the past by many solicitations. The Coordinated Solicitation will be the simultaneous release of these three solicitations, describing all core research programs within each division.

...

The Cross-Directorate Solicitation will describe cross-cutting research
programs, those with interests that cut across the entire CISE Directorate and are managed entirely within CISE. (Excluded are cross-cutting programs joint between CISE and other entities; see Further Notes.) For FY09-FY10, they will be:

- Data-Intensive Computing
- Network Science and Engineering
- Trustworthy Computing

Main bit of note: the "small" solicitations (i.e for amounts less than 500K) will be due in December. This in all likelihood includes the new Algorithmic Foundations solicitation. This is earlier than the Feb-March deadlines we had the last two years.

The F-1 process

I've been out of grad school long enough that I should know better, but PhD Comics still rings true in a way few comics can (xkcd is another). Of course, now I will find myself identifying more with the bearded old professor than the students, but still...

Today's strip sums up the foreign student visa experience perfectly. What they could have also added was a panel where Tajel explains the umpteenth bazillionth time to a clueless local, "Yes, we need a visa to go to X".

Loading Image

Click anywhere to cancel

Image is Unavailable

FOCS 08 list ?

The FOCS 2008 page has a link for accepted papers, but it's empty for now. We know at least 4 of the papers that got in, but does anyone know of a list ?

Update: that was quick! here it is.