Getting Stuff Done

I am a strong believer in discussion. Not just as a means to an end, but as important for itself. From that perspective, I think the discussion on double-blind reviewing was extremely productive (and I hope it will continue). I appreciated that comments were well-thought out and sincere, even if I didn't agree with them. But now I wonder, how do we take this discussion to a broader audience? As a first step, I'd be interested in getting more people within the theory community to be talking and thinking about these issues. Perhaps this is really a request to other bloggers to keep the conversation going.

More generally, how can we transfer conversations (online or in person) into action? Again, I wish to point out that often these conversations are important for themselves, still, sometimes once some amount of agreement is reached, the topics discussed merit action on a broader scale. Two examples, off the top of my head, of times when moving discussion to action has worked:

1. Yesterday, I spent some time standing in a hallway at Maryland talking to a fellow CS grad student. For awhile, I've been thinking in the back of my head about starting a thesis support group. I mentioned this to him and he was enthusiastic. We've organized the first meeting for this coming Friday and sent out announcements about it. Even if only the two of us show up, I consider this a success.
   
2. After tossing around the idea of holding a student-only conference event for SoCG (and it not happening), I posted about the possibility for future conferences. I got a positive response and it sounded at the time like it might actually happen for SoCG 2010. (Of course, I haven't been paying any attention to this in awhile, so I don't really know. Suresh?)
   

Both of these examples had the advantage of requiring little effort and a small number of people to be interested. What if that isn't true? Suppose we decided to try to continue the discussion of double-blind reviewing and possibly to try to start using it. How would that happen? A vote at the business meeting seems like a later step in the process. Discussion seems like the first step. What happens in the middle?

Double-Blind Reviewing

Updated 2/22/09: Added problems 5-8 as I understand them from the comments. These are mostly just extensions of 1-4, but I'm trying to make that more clear.

Michael discussed conflict of interest issues last week (in relation to STOC PC discussions). For me, the discussion brought up the question of why we don't use double-blind reviewing, thus handling the bias issue that is at the heart of conflicts of interest in a way that's been shown to reduce bias. And I do mean shown, I'm not just guessing that it might reduce bias, it's been shown to reduce bias against female authors (I'm willing to extrapolate from that that it reduces bias in general). I know that many people are against using double-blind reviewing for theory conferences. I don't understand why. Here are my guesses about what objections might be, and the reasons that I don't agree with them or understand them.

1. I, the author, am too lazy to anonymize my paper
   It doesn't really take any extra work to do basic anonymization of a paper. Most people refer to themselves in the third person when talking about their past work anyway. We don't have large continuing software projects, so we don't need to anonymize the names of those. These seem like the only real pieces of the paper that can reasonably be anonymized.
   
2. I, the PC member, am too lazy to deal with anonymized papers
   Having never been a PC member, I don't understand this potential argument.
   
3. It wouldn't actually be possible, everyone would know who's paper it was anyway
   Again, double-blind reviewing has been shown to reduce bias. As scientists, it seems that we should respect the research and not just decide that this would happen.
   
4. I, the author, want to be able to post a copy of my paper on my website as soon as I submit it.
   This does seem like an issue that would need to be dealt with. In general, I don't think that most reviewers/PC members would actually go trying to find the paper they're reviewing to determine whose it is. Authors could be asked not to post information and/or reviewers could be asked not to look for it. I'm not convinced that the web-based version of this problem is significantly worse than the traditional version where colleagues know what each other are working on.
   
5. We're better/smarter than other fields and don't actually have a problem with bias affecting which papers we accept.
   See #2 and #6. Also, without some sort of research to back this up, if you make this argument I'm likely to assume that you don't have the necessary social science background to accurately support this claim. (I certainly don't.)
   
6. The identity of the authors helps to determine if the paper will have an impact/ turn out in hindsight to have been good.
   This is an argument I do understand and find logical, but I strongly disagree with it. I believe the work should stand on its own. Perhaps I should actually have phrased this problem as I, the reviewer, am too lazy to take the time to fully read and consider the paper. I think this raises some interesting issues about the quality of reviewing, and perhaps revisions to that process also should be considered. But I admit that I may be missing something here, having not reviewed a large number of papers. Still, I imagine that most of us would be wary of a conference that explicitly stated that it took the reputations of the authors into account. If we're not willing to explicitly state the rules by which we do this, we shouldn't do it at all (again, because it's obviously biased).
   
7. Our reactions to double-blind reviewing are based on emotions. Some people find it fair and rigorous. Some people find it insulting and limiting.
   This also makes sense to me. I'm clearly in the first category, and don't understand the second. I believe it's a compliment to authors that their work can stand on its own, without having their name get the work through (see #6). I don't find it at all limiting (see #4 and #8).
   
8. If we can't do it perfectly, we shouldn't do it at all.
   See #3 and #4. Of course there are always going to be reviewers who guess the authors (correctly or incorrectly). There might even be reviewers who are already familiar with the work because it was posted online already. In some ways, it becomes up to the authors to determine if the reviewers will know that it's their paper - those of us who are on the negative end of the bias spectrum or just believe in this process can choose to really be careful so that reviewers won't know it's our paper. But whatever happens, there will be some papers that actually remain anonymous and are judged only according to the work done. I'm fine with a system that's better even if it's not perfect. Similarly, I recognize that this won't suddenly fix all the problems women in computing face. It's still no reason not to fix this one.
   

In general, it seems to me like not too much work for a known reward.

(A nice overview of the issues can be found in an editorial in Nature.)

Free CG Journal?

Dense outliers currently has a poll up about starting a free computational geometry journal. Go vote!

SoCG Accepted Papers

The SoCG notifications just went out, and included a list of accepted papers. Sadly, there is only one paper on kinetic data, and though it looks interesting, it's not mine. Here's the list.

-----

Micha Sharir. An Improved Bound on the Number of Unit Area Triangles

Boris Bukh, Jiri Matousek and Gabriel Nivasch. Lower bounds for weak epsilon-nets and stair-convexity

Joachim Giesen, Balint Miklos, Mark Pauly and Camille Wormser. The Scale Axis Transform

Francis Y. L. Chin, Zeyu Guo and He Sun. Minimum Manhattan Network is NP-Complete

Eyal Ackerman, Jacob Fox, J\'anos Pach and Andrew Suk. On Grids in Topological Graphs

Mohammad Abam and Mark de Berg. Kinetic Spanners in R^d

Naoki Katoh and Shin-ichi Tanigawa. A Proof of the Molecular Conjecture

Frédéric Chazal, David Cohen-Steiner, Marc Glisse, Leonidas Guibas and Steve Oudot. Proximity of Persistence Modules and their Diagrams

Mark de Berg, Herman Haverkort and Constantinos Tsirogiannis. Visibility Maps of Realistic Terrains have Linear Smoothed Complexity

Gaiane Panina and Ileana Streinu. Flattening single-vertex origami: the non-expansive case

Oswin Aichholzer, Wolfgang Aigner, Franz Aurenhammer, Thomas Hackl, Bert Juettler, Margot Rabl and Elisabeth Pilgerstorfer. Divide-and-Conquer for Voronoi Diagrams Revisited

Marc Pouget, Sylvain Lazard, Elias Tsigaridas, Fabrice Rouillier, Luis Peñaranda and Jinsan Cheng. On the topology of planar algebraic curves

Sylvain Pion, Vicente H. F. Batista, David L. Millman and Johannes Singler. Parallel Geometric Algorithms for Multi-Core Computers

Pankaj Kumar Agarwal, Esther Ezra and Micha Sharir. Near-Linear Approximation Algorithms for Geometric Hitting Sets

Sandor Fekete, Dietmar Fey, Marcus Komann, Alexander Kroeller, Marc Reichenbach and Christiane Schmidt. Distributed Vision with Smart Pixels

Gunnar Carlsson, Vin de Silva and Dmitriy Morozov. Zigzag Persistent Homology and Real-valued Functions

Mikael Vejdemo-Johansson and Vin de Silva. Persistent cohomology and circular coordinates.

Andrea Vattani. k-means requires exponentially many iterations even in the plane

Natasa Jovanovic, Jan Korst, Ramon Clout, Verus Pronk and Ludo Tolhuizen. Candle in the Woods: Asymptotic Bounds on Minimum Blocking Sets

Bernard Chazelle and Wolfgang Mulzer. Computing Hereditary Convex Structures

Nabil Mustafa, Saurabh Ray, Abdul Basit and Sarfraz Raza. Centerpoints, Tverberg's Technique, and Related Problems

Nabil Mustafa and Saurabh Ray. PTAS for geometric hitting set problems via Local Search

Jean-Daniel Boissonnat, Olivier Devillers and Samuel Hornus. An efficient implementation of the Delaunay triangulation and it's graph in medium dimension

Sang Won Bae and Kyung-Yong Chwa. The Geodesic Farthest-Site Voronoi Diagram in a Polygonal Domain with Holes

Chuanjiang Luo, Jian Sun and Yusu Wang. Integral Estimation from Point Cloud in $\real^d$: a Geometric View

David Eppstein, Elena Mumford, Bettina Speckmann and Kevin Verbeek. Area-Universal Rectangular Layouts

Andrea Francke and Michael Hoffmann. Maximum Degree Four Euclidean Minimum Spanning Tree is NP-hard

rom pinchasi. Halving Lines and Measure Concentration in the Plane

Tamal Dey and Kuiyu Li. Cut Locus and Topology from Surface Point Data

Marc van Kreveld and Rodrigo Silveira. Embedding Rivers in Polyhedral Terrains

Mashhood Ishaque, Bettina Speckmann and Csaba Toth. Shooting permanent rays among disjoint polygons in the plane

Chandra Chekuri, Ken Clarkson and Sariel Har-Peled. On the Multi-Cover Problem in Geometric Settings

Timothy Chan and Sariel Har-Peled. Approximation Algorithms for Maximum Independent Set of Pseudo-Disks

Bernd Gärtner and Martin Jaggi. Core-Sets for Polytope Distance

Kasturi Varadarajan. Epsilon Nets and Union Complexity

Timothy M. Chan and Eric Y. Chen. Optimal In-Place Algorithms for 3-d Convex Hulls and 2-d Segment Intersection

luc habert and michel pocchiola. Arrangements of double pseudolines

Friedrich Eisenbrand, Nicolai Haehnle and Thomas Rothvoss. Diameter of Polyhedra: Limits of Abstraction

Chee Yap and Long Lin. Parametrizability and Nonlocal Isotopy: An Approach to Efficient Approximation of Nonsingular Curves

Erin Chambers, Jeff Erickson and Amir Nayyeri. Minimum Cuts and Shortest Homologous Cycles

Don Sheehy and Gary Miller. Approximate Center Points with Proofs

Csaba Toth. Binary Plane Partitions for Disjoint Line Segments

Peyman Afshani, Chris Hamilton and Norbert Zeh. Cache-Oblivious Range Reporting With Optimal Queries Requires Superlinear Space

Glencora Borradaile, James Lee and Anastasios Sidiropoulos. Randomly removing g handles at once

Peyman Afshani, Chris Hamilton and Norbert Zeh. A Unified Approach for Cache-Oblivious Range Reporting and Approximate Range Counting

STOC accepted CG papers

The list of STOC 2009 accepted papers was posted on Friday. Happily, they also provided an html version with abstracts. Below are the computational geometry related papers I noticed on the list (and then happily stole from the html source).

• Small-size ε-Nets for Axis-Parallel Rectangles and Boxes
  
  Boris Aronov, Esther Ezra and Micha Sharir
  
  We show the existence of ε-nets of size O((1/ε) log log (1/ε)) for planar point sets and axis-parallel rectangular ranges. The same bound holds for points in the plane with "fat" triangular ranges, and for point sets in 3-space and axis-parallel boxes; these are the first known non-trivial bounds for these range spaces. Our technique also yields improved bounds on the size of ε-nets in the more general context considered by Clarkson and Varadarajan. For example, we show the existence of ε-nets of size O((1/ε) log log log (1/ε)) for the "dual" range space of "fat" regions and planar point sets. Plugging our bounds into the technique of Brönnimann and Goodrich, we obtain improved approximation factors (computable in randomized polynomial time) for the hitting set or the set cover problems associated with the corresponding (primal or dual) range spaces.
  


• Private Coresets
  
  Dan Feldman, Amos Fiat, Haim Kaplan and Kobbi Nissim
  
  We forge a link between coresets, that have found use in a vast host of geometric settings, and differentially private databases that can answer any number of queries without compromising privacy — queries of the same class well approximated by the coreset. Such queries imply efficient privacy preserving optimization algorithms for a wide range of optimization problems but are also of independent interest. We give (computationally inefficient) transformations from any coreset for queries with low generalized sensitivity to differentially private databases for the same queries. This greatly extends the work of Blum, Ligett, and Roth [BLR08], and McSherry and Talwar [MT07].
  
  We define the notion of private coresets, which are simultaneously both coresets and differentially private. We produce computationally efficient private coresets for k-median and k-mean in R^d, i.e., efficient differentially private databases for such queries. Private coresets also imply efficient coalition proof mechanisms and error resilient data structures.
  
  Unlike coresets which only have a multiplicative approximation factor, we prove that private coresets must have a (small) additive error.
  


• Explicit construction of a small ε-net for linear threshold functions
  
  Yuval Rabani and Amir Shpilka
  
  We give explicit constructions of ε nets for linear threshold functions on the binary cube and on the unit sphere. The size of the constructed nets is polynomial in the dimension n and in 1/ε. To the best of our knowledge no such constructions were previously known. Our results match, up to the exponent of the polynomial, the bounds that are achieved by probabilistic arguments.
  
  As a corollary we also construct subsets of the binary cube that have size polynomial in n and covering radius of n/2 - c\sqrt{n log n}, for any constant c. This improves upon the well known construction of dual BCH codes that only guarantee covering radius of n/2 - c\sqrt{n}.
  


• Every planar graph is the intersection graph of segments in the plane
  
  Jeremie Chalopin and Daniel Goncalves
  
  Given a set S of segments in the plane, the intersection graph of S is the graph with vertex set S in which two vertices are adjacent if and only if the corresponding two segments intersect. We prove a conjecture of Scheinerman (PhD Thesis, Princeton University, 1984) that every planar graph is the intersection graph of some segments in the plane.
  

Jury Morality

Not only was I chosen for jury duty, I was chosen for the jury. I was surprised by this, though I'm not sure why (perhaps since I was 39th in the queue). I suppose if they left a lawyer on the jury, I'm comparatively very little threat.

The deliberations were interesting, and the whole process left me wondering about the morality of the system. Because it appears that justice and morality are two very different things. Should they be? This was actually a major sticking point in our deliberations. We were deadlocked.

There's a classic psychology scenario (used, I believe, to understand through their answer what stage of moral reasoning a subject has reached) that goes something like this:

A man's wife is very very sick. Without a certain very expensive medicine she will die. The man does not have enough money for the medicine. Should he steal it?

My modifications to the scenario assume that he does steal the medicine (or, since he's innocent until proven guilty, is found with the medicine in his possession).

1. Should he be found guilty of the crime?
   
2. What if he first talked to the owner of the store, who refused to help him out, put him on a payment plan, etc? Is he still guilty if he steals it?
   
3. What if it turns out the owner of the store was actually an undercover cop who could have given him the medicine, but wanted to make an arrest?
   
4. What if the undercover cop says the guy stole the medicine while the man says the cop opened the door and told him it was "on the house?"
   

My take on this is that in only the fourth case is there cause for reasonable doubt. But I don't like it.