Probability of a graph being connected...

I ran across the following question in a problem I'm working on, and thought I'd ping the collective wisdom of the blog-reader-o-sphere.

Given an undirected graph G with (possibly different) probabilities on edges, consider the usual random process where we pick each edge independently, but with probability p_e (this is the difference from the standard erdos-renyi model).

What is the probability that the resulting graph is connected ?

This seems possibly to have something to do with the spanning tree polytope, but it seems quite nontrivial. In general, I'm given a subset of vertices S in this graph, and want to ask for the probability that S forms a connected component. Making sure that S is disconnected from the rest of the graph is easy, but then the remainder of the probability comes from the answer to the above question.

I should add that the subset connectivity question is trivial if G is a tree: it's the higher connectivity case that makes things harder.

p.s More SoCG posts should be on their way in the next few days after I return.

SoCG 2009: Day 0

At least in my mind, things have been somewhat overshadowed by the sad news of yesterday, thus preventing me (thankfully) from writing the more frivolous posts that I might have penned.

Today was the 25th anniversary celebration for SoCG (1985-2009), and we had four speakers to do a retrospective on the field.

David Dobkin was first, talking about how some of the first geometric algorithms came to be. He interspersed many fun facts about the early days of SoCG:

• One of the reasons CG is tied to the STOC/FOCS community is because when Michael Shamos first asked him where to publish a geometry paper, STOC was the first conference that came to mind.
• The Preparata-Shamos book only came about because (after Shamos left for law school) Ron Graham brokered a deal for Franco Preparata to write a book based on Shamos' thesis.
• SoCG was almost called the Symposium on Computer Geometry (ugh).

It was interesting to see that even way back then, there was serious intersection between numerical algorithms, the graphics and vision folks, and the nascent geometry area. Some things haven't really changed. It also explains (for me) why there is somewhere deep down a sense that CG doesn't wholly situate within the larger algorithms community, but has a core identity that's slightly different.

One point that David made was very interesting. He talked about how Michael Shamos essentially created a problem book from scratch, listing basic problems in the new area of computational geometry, and methodically solving them one by one. He then asserted that it was the creation of this problem book that played a major role in the unification of the area. I think that makes a lot of sense. It's not so much that a list of problems got created. It's not too hard to do that. What I think was the critical factor was the listing of problems within-reach, that encouraged more people to start thinking about them. Muthu is very good at doing this with any field he jumps into, and I think he's able to jumpstart a lot of research for this exact reason. It's not easy to do: the problems have to be core to the area, but still not that difficult to solve.

Micha Sharir went next with a talk on the evolution of work in arrangements. I've always felt that work on arrangements seems to have reached the point of diminishing returns after some point: that new results were mildly interesting, but didn't necessarily hook into algorithm design in a nontrivial way. I still have somewhat of the same opinion after the talk, but it was good to see the evolution of the problems into higher dimensional surface arrangement questions.

Emo Welzl gave a nice overview of the exciting years between 1987-1992 when randomization began to bloom into a powerful tool for doing geometry. Of course, the very first randomized algorithm was a geometric one (Rabin's closest pair algorithm), but the really powerful methods came into being really with Clarkson's work, and the eps-net work of Haussler and Welzl. It was amusing that almost every single paper mentioned in Emo's talk was written or co-written by Ken: just goes to show his profound influence on the field both for new techniques, as well as new results.
For me, another great influence was Raimund Seidel's amazingly lucid exposition of backwards analysis: there's something to be said for crystal-clear writing and the impact it can have.

The final talk was by Kurt Mehlhorn, on the history that led to the development of LEDA and CGAL. I must confess that I've always felt rather intimidated by CGAL and LEDA: there's something about the phrase "traits class" that strikes fear into my heart. But Kurt's talk was immensely enjoyable: he gave several simple examples of inputs where floating point implementations of geometric algorithms fail spectacularly, and really reinforced the importance of precise implementations, something (if I may add) the rest of the algorithms community often can avoid if they're dealing with graphs or numeric data. I REALLY need to weave CGAL into the next incarnation of my geometry class: must be less lazy, must be less lazy, .....

Notes from the conference: I was fervently hoping that the organizers would lower expectation for next year, but no such luck :(. Impeccable organization, food, and free beer. Sigh......

I'll be tweeting occasionally from the conference. If you're reading this at the conference and want to do the same, please the hashtag #socg so all tweets can be collected in one place.

Rajeev Motwani, R.I.P

Rajeev Motwani passed away unexpectedly yesterday. He will be remembered for many things: his influence on the creation of Google, the foundational randomized algorithms book that he wrote with Prabhakar Raghavan, his role in the PCP theorem, and his extensive presence in the Bay Area investor community. Within the theory community, he will also be remembered by the legion of students he trained, including your humble blogger. Update: Ashish Goel @ Stanford has a page where you can also post comments.

The influence an advisor has on their students can be subtle: as a grad student, I spent much of my time resisting, pushing back, trying to find my own voice. But more and more, as I look back, I see how he influenced my taste in problems and the sensibility I bring to my work.

He had incredible breadth to go along with his depth. I remember scouring his web page in the early years of grad school, and seeing papers in robotics, databases, compilers, parallel systems, as well as in algorithms. Having spent time working in more applied areas, I can appreciate now how difficult it must have been to do that, and have the kinds of impact he had. That kind of incisiveness, that could cut to the heart of a modelling problem, was a hallmark of his more "applied" work.

There's something special that comes with the ability to have a great career and train so many students. There are many famous researchers in the field who do one or the other, and Rajeev had a knack of catalysing the best from his students, and helping them succeed no matter what area they happened to work in. To this day, I'll catch myself thinking, "what did Rajeev do in this situation" when I'm interacting with my own students.

As an advisor, the best way to describe him was 'laid-back'. He wasn't the kind to breathe down your neck, or demand regular updates. But I felt the terror all the same when going into his office to describe what I'd been upto. But he'd sit there with those half-closed eyes staring off into space as I spoke, and then the observations would come, carefully crafted, and enough to make me scurry off and think hard before our next meeting.

As a teacher, he was brilliant. The very first time I took a class with him, I saw this. His style of presentation, how he organized his material, and even his impeccable boardwork: these are all things I teach my students today. His lectures weren't flashy: they were solid, and profound, and in his own mellow way, he was able to convey intuition, rigor and beauty with the kind of clarity one dreams of possessing. To flip the truism about doing and teaching around, he did, and taught even better as a result of it.

I had less contact with him after graduation than I should have had. I was doing the whole 'be your own person, strike out on your own' thing. I'd bump into him occasionally at conferences, but as he got more involved in his investment efforts, he stopped attending conferences regularly (or so it seemed) and even that contact dried up. As someone just said to me in an email today morning, 'Life is fleeting'.

It's a strange feeling, to lose your advisor so suddenly like this, and to hear about it on twitter, of all things. I'm not even sure what I'm feeling, except a sense of numbness, and a feeling that something has shifted, permanently, underneath.

To his wife Asha and his family: my deepest condolences.

New(?) NSF policies

While everyone recovers from what appears to be a gripping STOC, I thought I'd flag two NSF-related items that came my way.

The first, via FSP, is on post-doc mentoring. Now I've always been told that the NSF frowns on inserting post-doc support in proposals, but apparently they don't mind it, and they have a new policy in place for proposals including postdoc support:

Starting this year, NSF proposals that request funding for postdoctoral researchers must include a statement about how the postdoc(s) will be mentored. For a brief time this mentoring statement was supposed to be part of the body of the proposal, but, perhaps in response to complaints, the postdoc mentoring text is now a supplementary document, up to a page in length. As with the required Broader Impacts component of proposals, NSF is serious about the mentoring statement: proposals that request funding for postdocs but that do not contain the mentoring supplement will not even be reviewed.

I'm curious as to what experience people have had with postdoc support in proposals, and whether this is really new, or just a restatement of things that were already tacitly known.

The second item affects us more broadly, and perniciously. A new policy guideline of May vintage appears to suggest (it's somewhat ambiguous) that equipment purchased for grants must be MUCH more closely tied to grant activities than previously expected. Specifically, it essentially rules out the purchase of machines for general PI use (like laptops etc), and raises a number of questions about how to purchase software for old machines, how to upgrade new machines etc. Again, I'm curious to know if people have already run afoul of this new rule, and what the deal is.

more on the zig zag product..

I did an impromptu lunch presentation with my research group on expanders to celebrate the Godel Prize, and in the process dug up some useful reading. There's nothing here that's new to folks familiar with the main results, but if you want a reading list to help with grasping the significance of the results, read on.

• Luca Trevisan's series on expanders and their relation to Cayley graphs (one, two, three, four)
• Terry Tao's summary of expanders inspired by an Avi Wigderson talk.
  
• My note from SODA 2007 on the Alon/Schwartz/Schapira improved analysis of the replacement product.
• Dieter van Melkebeek's course on expanders

There are some aspects of this story that are worth drawing out. First of all, it's actually possible (I think) to get the SL = L result without using the zig zag product directly. In fact, stray comment on a post by Lance suggests as much, and with the new analysis of the replacement product this might be even more likely.

This doesn't mean that the zig-zag product is useless of course. In fact, there's a wonderful 'return to start' story here, which I'll attempt to convey. Essentially, as Luca describes, many early expander constructions proceeded via taking some special non-Abelian group and constructing its Cayley graph, which was then shown to be an expander. The zig-zag product is described "combinatorially" as a construction that takes two graphs and makes a third out of them, and one advantage of this representation is that it gives more explicit expander constructions. But it turned out that at the core of this hides a group operator ! In a certain sense, the zig zag product of the Cayley graph of two groups is the Cayley graph of the semidirect product of the groups ! This is a result of Alon, Lubotsky and Wigderson.

Godel Prize

The ACM site isn't updated yet (here's the press release), but Michael M informs us that Vadhan, Reingold and Wigderson just won the Godel prize, most likely for their paper on the zig-zag graph product, which had a major role in and for Reingold's proof that SL = L. These were inspiration for Dinur's combinatorial PCP theorem.

Congratulations !

Joint distributions aren't that bad

I was reading Noam Nisan's exposition of correlated equilibria. It's interesting to note that finding a correlated equilibrium is easy: you have to solve a linear program in the relevant variables of the underlying distribution. This is in contrast to Nash equilibria.

What struck me is that this is a good example of where a joint distribution isn't that bad. In machine learning especially, trying to "learn" a joint distribution is hard firstly because the number of variables blows up, and because of nasty correlations that one has to account for. In fact, the area of variational methods often uses the trick of replacing a joint distribution by the "closest" product distribution, and optimizing over that instead.

Here though, the "replacing by a product distribution" takes you from a correlated equilibrium problem to a Nash equilibrium problem, and now the individual probabilities actually multiply, yielding a nonlinear problem that's PPAD-Complete.

Physicists understand the web better than us, part 28596

A new physics review site. via the baconmeister:

Physicists are drowning in a flood of research papers in their own fields and coping with an even larger deluge in other areas of physics. The Physical Review journals alone published over 18,000 papers last year. How can an active researcher stay informed about the most important developments in physics?

Physics highlights exceptional papers from the Physical Review journals. To accomplish this, Physics features expert commentaries written by active researchers who are asked to explain the results to physicists in other subfields. These commissioned articles are edited for clarity and readability across fields and are accompanied by explanatory illustrations.

Each week, editors from each of the Physical Review journals choose papers that merit this treatment, aided by referee comments and internal discussion. We select commentary authors from around the world who are known for their expertise and communication skills and we devote much effort to editing these commentaries for broad accessibility.

Physics features three kinds of articles: Viewpoints are essays of approximately 1000–1500 words that focus on a single Physical Review paper or PRL letter and put this work into broader context. Trends are concise review articles (3000–4000 words in length) that survey a particular area and look for interesting developments in that field. Synopses (200 words) are staff-written distillations of interesting and important papers each week. In addition, we intend to publish selected Letters to the Editor to allow readers a chance to comment on the commentaries and summaries.

Physics provides a much-needed guide to the best in physics, and we welcome your comments (physics@aps.org).

What an excellent idea !

Kindle DX

Much well-deserved drooling over the Kindle DX. The killer app is native PDF support: as Michael Trick pointed out, the earlier Kindles didn't do too well with math support (the native Kindle document format is not PDF). I could easily see myself using the DX at conferences, rather than lugging around my laptop, or (worse) printing out copies of papers I wanted.

The Kindle has a nice feature that you can email documents to a specific address and have them synced automatically to the device, but it comes at a price ($0.10/document). If you use a direct transfer over USB though, it's free of course.

What I don't understand is why this has taken so long to happen: it seems to me that the academic market is the killer market for the Kindle: can you imagine transferring ALL your PDF papers to the Kindle for reading ? not to mention books ?

p.s for those of you who will no doubt point out that other readers exist that can read PDF, and are puzzled by all the hype over the Kindle, I leave you to your Archos MP3 players and Opera browsers.

p.p.s I spotted my first Kindle in the wild a month ago at a conference. It was rather cute looking. the DX will be much larger of course.

New open access proceedings archive

Via Luca Aceto, news of a new effort to create an open access electronic proceedings. The idea is that you organize your conference/workshop, and apply for inclusion of your proceedings in the EPTCS: you handle the reviewing, they take the papers and manage the long term archiving (via the arxiv).

I'm imagining this will only be useful for small conferences/workshops, but it's a good way of making sure you don't have a dead-link problem a few years later when the person who hosted the website for the conference leaves their institution and forgets to hand over maintainence to someone else. Also, the arxiv imprimatur will make sure the papers will get more visibility than otherwise.

CG Steering Comittee Elections: Part II

Marc van Kreveld has been taking nominations for the next set of members of the CG steering committee. He now has a list of nominees (people nominated at least twice, and willing to serve). His instructions are these:

To vote, send me an e-mail with at most five names from the list below. Put "Vote SC" (or something similar) in the e-mail subject line, or reply to this message. The possibility to vote ends on May 15. Of course, your votes will be kept confidential.

The list is below: much to my embarrassment, I have been nominated. There are many good folks on this list, and I'm not sure explicit campaigning is in good taste, but I will say that I feel the "divide" between CG and the rest of theory has been made too much of a big deal, and does no one any favors. In whatever ways the steering committee can help to keep us involved and participating in larger theory endeavours, I'd do my best to be involved.

If anyone else on the list below wishes to post anything about their suitability for a spot, I'd be happy to host their posting without comment.

And now, here's the list: you will note that all CG bloggers have been nominated :)

• Dan Halperin
• David Eppstein
• David Mount
• Erik Demaine
• Guenter Rote
• Jack Snoeyink
• Jean-Daniel Boissonnat
• Jeff Erickson
• Joseph Mitchell
• Leo Guibas
• Mark de Berg
• Matthew Katz
• Monique Teillaud
• Otfried Cheong
• Rolf Klein
• Sariel Har-Peled
• Sue Whitesides
• Suresh Venkatasubramanian

WADS paper list

As previously blogged, WADS paper list (sans abstracts ! come on, WADS people, get with the program).
Two interesting observations:

• WADS is no longer a workshop ! It's the Algorithms And Data Structures Symposium (ADSS?). I see that years of complaining that workshops get no respect has had an effect.
  
• There seems to be a preponderance of geometry papers (or should I say, OxDE papers :)). Is WADS (ADSS) becoming a satellite CompGeom conference ? this would not be a bad thing at all, considering that SODA is the only current satellite (I kid, I kid). Or maybe WADS (ADSS) is becoming a satellite of SODA/ESA ? that would be reasonable too.
  

Start your engines for Bethesda: STOC early reg deadline Apr 28

Aravind Srinivasan reminds us that the STOC early registration deadline is Apr 28 (only a week away!), so do go ahead and register.

Aravind also notes:

Especially given the current economic climate, ACM is concerned about
getting enough registrants and booked hotel rooms for STOC.

This is particularly pertinent for me because I've been having similar conversations with ACM about SoCG 2010: they are generally concerned about attendance based on data from conferences being organized right now, and have been tamping down attendance estimates as a result.

Complexity book out !

The Arora-Barak complexity book is out ! Of course they've had the PDF version around for a while, and I've been using it so extensively I almost HAVE to buy the book now.

Many/multi-core research

There's been a great deal of chatter on the blogs about the multicore workshop being organized at UMD. I'll assume that everyone already knows about the workshop, and will jump straight to some thoughts.

First, two points. I'm at a department where there's a LOT of excitement about multicore work from a systems end. For the last two years we've had internal departmental panel discussions on various aspects of multicore research (architecture, compilers, programming languages, verification etc) and I've even chipped in little bits on the potential theoretical ramifications.

Secondly, I spent a good few years working on GPU algorithms ( a kind of precursor to things like the Cell, and multicore in general), both on the practical side of implementing algorithms on a GPU, and on the slightly more theoretical side of trying to abstract out the core metaphors defining "GPU-efficient" algorithms.

To an extent, I know whereof I speak, and I have a kind of guarded curiosity about multicore work. I think it's an excellent time to have this workshop. There's huge interest across the board in CS about multicore: the evangelists believe it's a game changer, and even the skeptics agree that it requires some redesign of our thinking about the entire systems "stack" (chip level, memory level, OS level, programming level, etc).

Why I am guarded though ? It's because the models are changing very rapidly. There's the Cell-style SPU model that looks a lot like a stream processing system. There's the Nvidia CUDA programming model that abstracts a very complicated memory hierarchy over an architecture you don't have direct access to, and there are of course all the actual multicore chips for which the interfaces are evolving. I don't think anyone knows what the right abstractions are for how to think about memory access on multicore system (and from a theory perspective, this is probably the key question), and so there's always the danger of settling on a model that changes before you have time to explore it in depth (this was happening a lot in the early days of GPU work).

But I see no reason why that should stop us from paying close attention and chipping in our contributions. I do think there are abstractions that may not capture all the nitty-gritty of what's happening with multicore systems, but capture some higher-order phenomena that aren't affected too much by the day to day changes. And I think that effective multicore memory modelling could have the same impact as I/O and streaming models of computation did (and these contributions have percolated well beyond the theory community).

The trick here is not to think about multicore in terms of 2/4/8/16 cores, but to imagine a system with millions of cores, small amounts of local memory, and a cost for transferring information. One of the limitations of PRAM in my mind is its ignoring of the real cost of memory access, while focusing on the parallelism: I think a careful modelling of memory transfer is what will make multicore algorithmic research interesting, and in that sense it follows the path from I/O to cache-oblivious models, with streaming thrown in for good measure. Even MapReduce and the MUD models might be useful in this regard.

So do we have a clean model ? No. Should theoreticians stay away ? Well that really depends on your style of operation. Some people like jumping in the mud, and some like to wait till structure emerges. That's really up to the individuals. But if NO ONE jumps in, then we essentially make the statement that theoreticians have no interest in computational models that aren't "sexy". If (as I like to think) algorithms is the true God's language of computation in all its forms, then it's inconsistent to just sit on the sidelines.

I think I just talked myself into attending the workshop.

NSF (and twitter)

Although the NSF has lots of new stimulus money for disbursement, allocation to proposals has been stalled for a while as the agency figures out how much money gets to go where etc. And then a few hours ago came this, on the NSF twitter feed:

Finally, movement! Allocations of the FY09 Funds and ARRA are being finalized, and we expect the apportionment from OMB later this week.

Can I just comment on how cool it is that the NSF has a twitter feed ?

Is HAM SANDWICH PPAD-Complete ?

Reading the algorithmic game theory book, I discover that HAM SANDWICH is in PPAD (not surprising in retrospect when you think of Brouwer's fixed point theorem as the canonical PPAD problem). Is HAM SANDWICH PPAD-Complete ?

Update: I should clarify - this is the problem I'm referring to:

Given n sets of 2n points (each) in n dimensions, is there a single hyperplane that bisects each set (i.e divides it into two sets of size n).

In 2D, the problem is to bisect two sets (the ham and the bread).

P vs NP seminar

I'm thinking of topics to discuss over the summer with students here, and decided on introducing people to complexity theory via the question, "Why haven't we solved the P vs NP problem?". The title is a little tongue-in-cheek: the real idea is to use P vs NP to explore some concepts in complexity theory, for an audience that has no real familiarity with the topic.

Thus far, I'm working off the "diagonalization-oracles-boolean-circuits-razborov-rudich" story line, with an addition at the end for algebraization, and P vs NC. But since this isn't my real area of expertise, I'm throwing out a request for suggestions: what topics am I missing when discussing the various attacks on P vs NP ?

p.s I'm using Scott Aaronson's P vs NP survey as a rough starting guide for references.

Committees and conferences...

FOCS 2009 PC size: 20
SODA 2009 PC size: 27
ICDE 2010 PC size: 230
IJCAI 2009 PC size: 600

SoCG 2008 attendance: ~150
SODA 2008 attendance: ~300

It's an impressive feat when a conference PC is larger than an entire other conference. It also explains why everyone has more PC memberships than I do :)

CG Steering Comittee Elections

Via Marc van Kreveld comes the announcement of CG Steering Committee elections. The way it works is that people send nominations to Marc before Apr 14. He screens them, checks if the nominated individuals are willing to serve, and then starts an election on May 1 for 5 candidates to run the committee for the next three years. Deadline for voting is May 14.

The curent committee is:

• Pankaj Agarwal
• Jeff Erickson
• Marc van Kreveld (secretary)
• Joe Mitchell
• Guenter Rote (chair)

and Marc's email address is marc at cs dot uu dot nl.