This was almost certainly my fault, but as I look at the implementation of Sets.cartesianProduct, I think its `contains` method made the assumption that `ImmutableSet.asList().indexOf` was O(1), which is no longer the case for Android.  It should probably get a specific `contains` implementation that actually is O(sets), not O(sets*setSize).
implements NavigableSet<E>, Serializable {
    private final NavigableSet<E> delegate;
    private final SortedSet<E> unmodifiableDelegate;
    UnmodifiableNavigableSet(NavigableSet<E> delegate) {
      this.delegate = checkNotNull(delegate);
      this.unmodifiableDelegate = Collections.unmodifiableSortedSet(delegate);
    }
    @Override