Methods, systems, and apparatus, including computer programs encoded on a computer storage medium, for resolving location criteria using user location data. One of the methods includes receiving data identifying an action to be performed in response to received user requests and data identifying location criteria for performing the action; determining a cover sets for possible confidence radii; receiving a plurality of requests, each request being associated with a respective location and a confidence radius for the location; determining, for each of the plurality of requests, whether the location associated with the request is in the cover set corresponding to the confidence radius for the location associated with the request; and for each request for which the location associated with the request is in the cover set for the confidence radius corresponding to the location associated with the request, determining that the location criteria for performing the action are satisfied.