« August 2005 | Main | October 2005 »

Posted at 06:42 PM in Games | Permalink | Comments (0)

Reblog
(0)
| |

I just finished an interview with one of the editors of UIUC's alumni magazine about teaching algorithms, which is incredibly flattering, but also very scary. The interview itself was very friendly and relaxed, but now that it's done I'm nervously replaying everything I said in my head, worrying that I sounded like a pompous ass, or a clueless idiot, or a poclumpelousess idasisot. ("Algorithms are really cool! Honest! Really! Internet! Human genome! Google! And...um... you know... stuff. But mostly they're just totally keen!") Sure, at one level I know they're not going to rake me across the coals. ("Hey, alumni! Look at this professor we found! Ha ha ha, doesn't he look stupid? Now give us money.") But still, I'm scared.

Oh dear pasta, she took my *picture*! Aaaaaaaahhh!!!

Posted at 03:49 PM in Random | Permalink | Comments (3)

Reblog
(0)
| |

No, really.

I've been corresponding with the publishers Reed Elsevier about their involvement in the arms trade. Reed Elsevier is an academic publisher, which also has a subsidary company, Spearhead Exhibitions, which hosts DSEi - the world's largest arms fair. You can see what I've written to Reed Elsevier, and what they've written back, elsewhere on this blog (one, two, three, four).

Ideolect has a couple more recent followup posts. See also Crooked Timber and UK IndyMedia.

Among other things, Reed Elsevier is the publisher of Lancet, Lexis Nexis, and quite a few overpriced mathematics and theoretical computer science journals.

Lovely. Just lovely.

[first link via 39orangestreet]

Posted at 09:22 PM | Permalink | Comments (4)

Reblog
(0)
| |

[via Bitch, PhD]

Posted at 07:59 PM in Random | Permalink | Comments (0)

Reblog
(0)
| |

As an anonymous passerby points out, the call for papers is out for the 22nd Annual ACM Symposium on Computational Geometry, which will be in Sedona, Arizona.

Titles and abstracts are due **November 23, 2005**; the actual 10-page papers are due **December 5, 2005**. Presumably the two-week gap is meant to let us ~~actually write~~ keep polisihing our papers while the program committee ~~sharpen their knives~~ split up the reviewing duties.

Nice idea. Very well-intentioned. I predict chaos.

Video and multimedia submissions are due **March 1, 2006**.

Posted at 08:58 AM in Computational Geometry | Permalink | Comments (0)

Reblog
(0)
| |

Lance, Suresh, and Sariel all point to the list of accepted SODA papers. Here, for your edification and amazement, is the subset of comptuational geometry papers on this list, in alphabetical order by author. I'm sure this list is neither complete nor exclusive; in several cases, I made an educated guess from the title and list of authors.

And yes, I am classifying metric embedding results as computational geometry, despite their criminal near-total absense at SOCG. Metrics are geometry, almost by definition.

- The Hunting of the Bump: On Maximizing Statistical Discrepancy

Deepak Agarwal and Jeff Phillips and Suresh Venkatasubramanian - Coresets for Approximating the Extent of Shallow Levels

Pankaj K. Agarwal and Sariel Har-Peled and Hai Yu - On the Number of Plane Graphs

Oswin Aichholzer and Thomas Hackl and Clemens Huemer and Ferran Hurtado and Hannes Krasser and Birgit Vogtenhuber - Local versus Global Properties of Metric Spaces

Sanjeev Arora and Laszlo Lovasz and Ilan Newman and Yuval Rabani and Santosh Vempala - Finding the Depth Order of Fat Objects

Mark de Berg and Chris Gray - Simultaneous Diagonal Flips in Plane Triangulations

Prosenjit Bose and Jurek Czyzowicz and Zhicheng Gao and Pat Morin and David R. Wood - Spanners for Doubling Metrics with Small Hop Diameter

T-H. Hubert Chan and Anupam Gupta - A Dynamic Data Structure for 3-d Convex Hulls and 2-d Nearest Neighbor Queries

Timothy M. Chan - The Space Complexity of Pass-Efficient Algorithms for Clustering Census Data

Kevin L. Chang and Ravi Kannan - On k-Median Clustering in High Dimensions

Ke Chen - Anisotropic Surface Meshing

Siu-Wing Cheng and Tamal K. Dey and Edgar A. Ramos and Rephael Wenger - Tightening Non-simple Paths and Cycles on Surfaces

Éric Colin de Verdière and Jeff Erickson - An algorithmic Friedman-Pippenger theorem on tree embeddings and applications to routing

Domingos Dellamonica Jr. and Yoshiharu Kohayakawa - Matrix Approximation and Projective Clustering via Volume Sampling

Amit Deshpande and Luis Rademacher and Santosh Vempala and Grant Wang - Analysis of Incomplete Data and an Inner-Dimension Helly Theorem

Jie Gao and Michael Langberg and Leonard J. Schulman - Linear programming and unique sink orientations

Bernd Gärtner and Ingo Schurr - Correlation Clustering with a Fixed Number of Clusters

Ioannis Giotis and Venkatesan Guruswami - Finding Large Sticks and Potatoes in Polygons

Olaf Hall-Holt and Matthew Katz and Piyush Kumar and Joseph S. B. Mitchell and Arik Sityon - An asymptotic approximation algorithm for 3D-strip packing

Klaus Jansen and Roberto Solis-Oba - Searching in dynamic three-dimensional convex hulls and planar Voronoi diagrams, and approximate range counting

Haim Kaplan and Micha Sharir - Max-Tolerance Graphs as Intersecton Graphs: Cliques, Cycles, and Recognition

Michael Kaufmann and Jan Kratochvil and Katharina Lehmann and Amarendran Subramanian - Generating all vertices of a polyhedron is hard.

Khachiyan, Boros, Borys, Elbassioni, Gurvich - A Near-Tight Approximation Lower Bound and Algorithm for the Kidnapped Robot Problem

Sven Koenig and Apurva Mudgal and Craig Tovey - Improved lower bounds for embeddings into L_1

Robert Krautghamer and Yuval Rabani - Deterministic boundary recognition and topology extraction for large sensor networks

A. Kroeller and S.P. Fekete and D. Pfisterer and S. Fischer - Trees, Markov convexity, and finding near-optimal embeddings

James R. Lee and Assaf Naor and Yuval Peres - Morphing Orthogonal Planar Graph Drawings

Anna Lubiw and Mark Petrick and Michael J. Spriggs - Metric Cotype

Manor Mendel and Assaf Naor - Entropy based Nearest Neighbor Search in High Dimensions

Rina Panigrahy - On the Number of Crossing-Free Matchings, (Cycles, and Partitions)

Micha Sharir and Emo Welzl - On The Chromatic Number of Some Geometric Hypergraphs

Shakhar Smorodinsky - A Semidefinite Programming Approach to Tensegrity Theory and Realizability of Graphs

Anthony Man-Cho So and Yinyu Ye

Posted at 12:04 PM in Computational Geometry | Permalink | Comments (7)

Reblog
(0)
| |

A beleaguered Michael Brown said Friday he doesn't know why he was removed from his onsite command of Hurricane Katrina relief efforts, but he does know the first thing he'll do when he returns to Washington.''I'm going to go home and walk my dog and hug my wife, and maybe get a good Mexican meal and a stiff margarita and a full night's sleep,'' Brown told The Associated Press. ''And then I'm going to go right back to FEMA and continue to do all I can to help these victims.''

Heh. Improbable Research pointedly recalls the 2000 IgNobel Prize in Psychology, awarded to David Dunning and Justin Kreuger for their fascinating paper “Unskilled and Unaware of It: How Difficulties in Recognizing One's Own Incompetence Lead to Inflated Self-Assessments” [pdf]. Dunning and Kreuger subjected several dozen undergraduates to written tests on humor, grammar, and logic; they also asked the students to rate their own abilities relative to their peers and to predict their test scores. Not surprisingly, *everybody* thought that their abilities were above average. Students who preformed best slightly underestimated their ability; students who preformed worst grossly overestimated theirs.

Of course, the Lake Wobegon Effect is no surprise to anyone who has taught freshmen or non-majors, dealt with incompetent (but invariably "experienced") teachers or administrators, argued with intelligent design "experts", or read a newspaper in the last five years. The hardest thing for many people to learn, especially in a subject that they've never seriously encountered before, is that they *don't* know what's going on, that their opinions are *not* facts, that their intuition is *not* proof. This is especially frustrating in math and CS theory classes, where the students have the tools to check whether their answers are correct, if only they'd think to try them. It's almost impossible to actually learn anything if you don't realize that you have something to learn. The first step, as they say, is to admit that you have a problem.

That's one of the reasons for my "I don't know" policy—an answer of "I don't know" on any homework or exam question is worth 25% partial credit. A blank response doesn't count; to get the partial credit, you must explicitly acknowledge your ignorance. (The other reason, of course, is that it cuts way back on random nonsense maybe-I'll-get-pity-credit-for-stumbling-on-the-right-keywords answers, which makes grading *much* easier.)

Dunning and Kreuger's conclusion suggests a few possible causes for the Lake Wobegon effect. (References removed.)

One puzzling aspect of our results is how the incompetent fail, through life experience, to learn that they are unskilled. This is not a new puzzle. Sullivan, in 1953, marveled at "the failure of learning which has left their capacity for fantastic, self-centered delusions so utterly unaffected by a life-long history of educative events." With that observation in mind, it is striking that our student participants overestimated their standing on academically oriented tests as familiar to them as grammar and logical reasoning. Although our analysis suggests that incompetent individuals are unable to spot their poor performances themselves, one would have thought negative feedback would have been inevitable at some point in their academic career. So why had they not learned?One reason is that people seldom receive negative feedback about their skills and abilities from others in everyday life. Even young children are familiar with the notion that "if you do not have something nice to say, don't say anything at all." Second, the bungled robbery attempt of McArthur Wheeler not withstanding, some tasks and settings preclude people from receiving self-correcting information that would reveal the suboptimal nature of their decisions. Third, even if people receive negative feedback, they still must come to an accurate understanding of why that failure has occurred. The problem with failure is that it is subject to more attributional ambiguity than success. For success to occur, many things must go right: The person must be skilled, apply effort, and perhaps be a bit lucky. For failure to occur, the lack of any one of these components is sufficient. Because of this, even if people receive feedback that points to a lack of skill, they may attribute it to some other factor.

Can you say social promotion? Grade inflation? Sure, I knew you could.

This is one of the reasons I find the current administration so scary. If the media is to be believed, George II surrounds himself with yes-men. He doesn't tolerate criticism in his environment, no matter how tangential. Conservative voters are drawn to his strong convictions, but those convictions never seemed to be tempered by honest criticism. He doesn't admit that he makes mistakes. He apparently doesn't believe that he *might* be wrong.

Is it any wonder, then, that Bush's hand-picked FEMA director did such a bad job? Given this environment in Washington, is anyone *surprised* that Brown doesn't know why he was removed from his post?

Posted at 02:02 PM in Academia, Politics | Permalink | Comments (8)

Reblog
(0)
| |

I'm visiting the University of Waterloo on September 19, for Masud Hasan's PhD defense. I'm also giving a talk about shortest homotopic paths.

September 19 is International Talk Like a Pirate Day.

So, aye, I be practicing me parlay on optimizin' treasure maps by tiling ~~the universal cover~~ Fiddler's Green with an infinite number of ~~right-angled octagons~~ pieces o' eight. Arrrr! Batten down the hatches and hoist the mizzen-mast! (An' if ye scurvy dogs and landlubbers be havin' suggestions on the best way t'explain homotopy or shortest paths t' gentlemen o' fortune, speak now, or it's the plank fer the lot o'ye.)

Should Masud pass his defense if *he* doesn't talk like a pirate?

Posted at 10:50 AM in Random | Permalink | Comments (1)

Reblog
(0)
| |

Shripad describes his move from UIUC to TU-Eindhoven.

Posted at 09:59 AM | Permalink | Comments (0)

Reblog
(0)
| |

The results for SODA 2006 are slowly being released. According to Cliff Stein, 135 of the 432 submitted papers were accepted. This is an acceptance rate of 31.25%, which is significantly higher than last year's overall rate of 28%, but slightly lower than last year's 32% acceptance rate for long submissions. In other words, no surprises.

No list of accepted papers has been announced yet. Stay tuned!

Posted at 07:10 PM in Theoretical computer science | Permalink | Comments (3)

Reblog
(0)
| |

- Eight brass monkeys from the ancient, sacred, holy crypts of Egypt
- Three talks at SOCG
- Computational topology at SOCG 2013
- Busy busy
- SOCG votes to leave ACM
- Computational Advertising at UIUC
- Applied and computational topology: ATMCS 5
- SOCG(T) 2012
- SOCG 2012 call for papers, videos, and multimedia
- Geometry and topology at SODA 2012

## Recent Comments