diff --git a/src/main/java/com/android/tools/r8/Version.java b/src/main/java/com/android/tools/r8/Version.java
index 73f0611..9e967a2 100644
--- a/src/main/java/com/android/tools/r8/Version.java
+++ b/src/main/java/com/android/tools/r8/Version.java
@@ -11,7 +11,7 @@
 
   // This field is accessed from release scripts using simple pattern matching.
   // Therefore, changing this field could break our release scripts.
-  public static final String LABEL = "1.2.36";
+  public static final String LABEL = "1.2.37";
 
   private Version() {
   }
diff --git a/src/main/java/com/android/tools/r8/naming/MethodNameMinifier.java b/src/main/java/com/android/tools/r8/naming/MethodNameMinifier.java
index c6729e8..97f1228 100644
--- a/src/main/java/com/android/tools/r8/naming/MethodNameMinifier.java
+++ b/src/main/java/com/android/tools/r8/naming/MethodNameMinifier.java
@@ -14,6 +14,7 @@
 import com.android.tools.r8.shaking.RootSetBuilder.RootSet;
 import com.android.tools.r8.utils.InternalOptions;
 import com.android.tools.r8.utils.MethodSignatureEquivalence;
+import com.android.tools.r8.utils.MethodSignatureRelaxedEquivalence;
 import com.android.tools.r8.utils.Timing;
 import com.google.common.base.Equivalence;
 import com.google.common.base.Equivalence.Wrapper;
@@ -90,11 +91,15 @@
  */
 class MethodNameMinifier extends MemberNameMinifier<DexMethod, DexProto> {
 
-  private final Equivalence<DexMethod> equivalence = MethodSignatureEquivalence.get();
+  private final Equivalence<DexMethod> equivalence;
   private final Map<DexCallSite, DexString> callSiteRenaming = new IdentityHashMap<>();
 
   MethodNameMinifier(AppInfoWithSubtyping appInfo, RootSet rootSet, InternalOptions options) {
     super(appInfo, rootSet, options);
+    equivalence =
+        overloadAggressively
+            ? MethodSignatureEquivalence.get()
+            : new MethodSignatureRelaxedEquivalence(appInfo);
   }
 
   @Override
@@ -337,10 +342,12 @@
   }
 
   private void addStatesToGlobalMapForMethod(
-      DexEncodedMethod method, Set<NamingState<DexProto, ?>> collectedStates,
+      DexEncodedMethod method,
+      Set<NamingState<DexProto, ?>> collectedStates,
       Map<Wrapper<DexMethod>, Set<NamingState<DexProto, ?>>> globalStateMap,
       Map<Wrapper<DexMethod>, Set<DexMethod>> sourceMethodsMap,
-      Map<Wrapper<DexMethod>, NamingState<DexProto, ?>> originStates, DexType originInterface) {
+      Map<Wrapper<DexMethod>, NamingState<DexProto, ?>> originStates,
+      DexType originInterface) {
     Wrapper<DexMethod> key = equivalence.wrap(method.method);
     Set<NamingState<DexProto, ?>> stateSet =
         globalStateMap.computeIfAbsent(key, k -> new HashSet<>());
diff --git a/src/main/java/com/android/tools/r8/utils/MethodSignatureRelaxedEquivalence.java b/src/main/java/com/android/tools/r8/utils/MethodSignatureRelaxedEquivalence.java
new file mode 100644
index 0000000..74d2d98
--- /dev/null
+++ b/src/main/java/com/android/tools/r8/utils/MethodSignatureRelaxedEquivalence.java
@@ -0,0 +1,36 @@
+// Copyright (c) 2018, the R8 project authors. Please see the AUTHORS file
+// for details. All rights reserved. Use of this source code is governed by a
+// BSD-style license that can be found in the LICENSE file.
+package com.android.tools.r8.utils;
+
+import com.android.tools.r8.graph.AppInfo;
+import com.android.tools.r8.graph.DexMethod;
+import com.google.common.base.Equivalence;
+
+/**
+ * Implements an equivalence on {@link DexMethod} that does not take the holder into account but
+ * allow covariant return type: a method in a sub type can return a narrower type.
+ */
+public class MethodSignatureRelaxedEquivalence extends Equivalence<DexMethod> {
+
+  private final AppInfo appInfo;
+
+  public MethodSignatureRelaxedEquivalence(AppInfo appInfo) {
+    this.appInfo = appInfo;
+  }
+
+  @Override
+  protected boolean doEquivalent(DexMethod a, DexMethod b) {
+    return a.name.equals(b.name) && a.proto.parameters.equals(b.proto.parameters)
+        && (a.proto.returnType.equals(b.proto.returnType)
+            || (a.proto.returnType.isStrictSubtypeOf(b.proto.returnType, appInfo)
+                && a.getHolder().isStrictSubtypeOf(b.getHolder(), appInfo))
+            || (b.proto.returnType.isStrictSubtypeOf(a.proto.returnType, appInfo)
+                && b.getHolder().isStrictSubtypeOf(a.getHolder(), appInfo)));
+  }
+
+  @Override
+  protected int doHash(DexMethod method) {
+    return method.name.hashCode() * 31 + method.proto.parameters.hashCode();
+  }
+}
diff --git a/src/test/java/com/android/tools/r8/naming/CovariantReturnTypeInSubInterfaceTest.java b/src/test/java/com/android/tools/r8/naming/CovariantReturnTypeInSubInterfaceTest.java
new file mode 100644
index 0000000..7ba5334
--- /dev/null
+++ b/src/test/java/com/android/tools/r8/naming/CovariantReturnTypeInSubInterfaceTest.java
@@ -0,0 +1,135 @@
+// Copyright (c) 2018, the R8 project authors. Please see the AUTHORS file
+// for details. All rights reserved. Use of this source code is governed by a
+// BSD-style license that can be found in the LICENSE file.
+package com.android.tools.r8.naming;
+
+import static com.android.tools.r8.utils.DexInspectorMatchers.isRenamed;
+import static org.junit.Assert.assertEquals;
+import static org.junit.Assert.assertThat;
+
+import com.android.tools.r8.OutputMode;
+import com.android.tools.r8.TestBase;
+import com.android.tools.r8.ToolHelper;
+import com.android.tools.r8.ToolHelper.ProcessResult;
+import com.android.tools.r8.VmTestRunner;
+import com.android.tools.r8.utils.AndroidApp;
+import com.android.tools.r8.utils.DexInspector;
+import com.android.tools.r8.utils.DexInspector.ClassSubject;
+import com.android.tools.r8.utils.DexInspector.MethodSubject;
+import com.google.common.collect.ImmutableList;
+import java.nio.file.Path;
+import java.util.List;
+import org.junit.Test;
+import org.junit.runner.RunWith;
+
+interface SuperInterface {
+  Super foo();
+}
+
+interface SubInterface extends SuperInterface {
+  @Override
+  Sub foo();
+}
+
+class Super {
+  protected int bar() {
+    return 0;
+  }
+}
+
+class Sub extends Super {
+  @Override
+  protected int bar() {
+    return 1;
+  }
+}
+
+class SuperImplementer implements SuperInterface {
+  @Override
+  public Super foo() {
+    return new Sub();
+  }
+}
+
+class SubImplementer extends SuperImplementer implements SubInterface {
+  @Override
+  public Sub foo() {
+    return (Sub) super.foo();
+  }
+}
+
+class TestMain {
+  public static void main(String[] args) {
+    SubImplementer subImplementer = new SubImplementer();
+    Super sup = subImplementer.foo();
+    System.out.print(sup.bar());
+  }
+}
+
+@RunWith(VmTestRunner.class)
+public class CovariantReturnTypeInSubInterfaceTest extends TestBase {
+
+  private void test(boolean overloadAggressively) throws Exception {
+    String mainName = TestMain.class.getCanonicalName();
+    String aggressive =
+        overloadAggressively ? "-overloadaggressively" : "# Not overload aggressively";
+    List<String> config = ImmutableList.of(
+        "-printmapping",
+        "-useuniqueclassmembernames",
+        aggressive,
+        "-keep class " + mainName + " {",
+        "  public void main(...);",
+        "}",
+        "-keep,allowobfuscation class **.Super* {",
+        "  <methods>;",
+        "}",
+        "-keep,allowobfuscation class **.Sub* {",
+        "  <methods>;",
+        "}"
+    );
+    AndroidApp app = readClasses(
+        SuperInterface.class,
+        SubInterface.class,
+        Super.class,
+        Sub.class,
+        SuperImplementer.class,
+        SubImplementer.class,
+        TestMain.class
+    );
+    AndroidApp processedApp =
+        compileWithR8(app, String.join(System.lineSeparator(), config), options -> {
+          options.enableInlining = false;
+        });
+    DexInspector inspector = new DexInspector(processedApp);
+    ClassSubject superInterface = inspector.clazz(SuperInterface.class);
+    assertThat(superInterface, isRenamed());
+    MethodSubject foo1 = superInterface.method(
+        Super.class.getCanonicalName(), "foo", ImmutableList.of());
+    assertThat(foo1, isRenamed());
+    ClassSubject subInterface = inspector.clazz(SubInterface.class);
+    assertThat(subInterface, isRenamed());
+    MethodSubject foo2 = subInterface.method(
+        Sub.class.getCanonicalName(), "foo", ImmutableList.of());
+    assertThat(foo2, isRenamed());
+    assertEquals(foo1.getFinalName(), foo2.getFinalName());
+
+    ProcessResult javaResult = ToolHelper.runJava(ToolHelper.getClassPathForTests(), mainName);
+    assertEquals(0, javaResult.exitCode);
+    Path outDex = temp.getRoot().toPath().resolve("dex.zip");
+    processedApp.writeToZip(outDex, OutputMode.DexIndexed);
+    ProcessResult artResult = ToolHelper.runArtNoVerificationErrorsRaw(outDex.toString(), mainName);
+    assertEquals(0, artResult.exitCode);
+    assertEquals(javaResult.stdout, artResult.stdout);
+  }
+
+  @Test
+  public void test_notAggressively() throws Exception {
+    test(false);
+  }
+
+  @Test
+  public void test_aggressively() throws Exception {
+    test(true);
+  }
+
+}
diff --git a/src/test/java/com/android/tools/r8/naming/InterfaceRenamingTestRunner.java b/src/test/java/com/android/tools/r8/naming/InterfaceRenamingTestRunner.java
index e1fa3d0..ef6e0c8 100644
--- a/src/test/java/com/android/tools/r8/naming/InterfaceRenamingTestRunner.java
+++ b/src/test/java/com/android/tools/r8/naming/InterfaceRenamingTestRunner.java
@@ -14,12 +14,15 @@
 import com.android.tools.r8.TestBase;
 import com.android.tools.r8.ToolHelper;
 import com.android.tools.r8.ToolHelper.ProcessResult;
+import com.android.tools.r8.VmTestRunner;
 import com.android.tools.r8.origin.Origin;
 import java.nio.file.Path;
 import java.util.Arrays;
 import java.util.List;
 import org.junit.Test;
+import org.junit.runner.RunWith;
 
+@RunWith(VmTestRunner.class)
 public class InterfaceRenamingTestRunner extends TestBase {
   static final Class CLASS = InterfaceRenamingTest.class;
   static final Class[] CLASSES = InterfaceRenamingTest.CLASSES;
diff --git a/src/test/java/com/android/tools/r8/naming/LambdaRenamingTestRunner.java b/src/test/java/com/android/tools/r8/naming/LambdaRenamingTestRunner.java
index c7c74e9..de70177 100644
--- a/src/test/java/com/android/tools/r8/naming/LambdaRenamingTestRunner.java
+++ b/src/test/java/com/android/tools/r8/naming/LambdaRenamingTestRunner.java
@@ -16,6 +16,7 @@
 import com.android.tools.r8.TestBase;
 import com.android.tools.r8.ToolHelper;
 import com.android.tools.r8.ToolHelper.ProcessResult;
+import com.android.tools.r8.VmTestRunner;
 import com.android.tools.r8.utils.DescriptorUtils;
 import com.android.tools.r8.utils.FileUtils;
 import java.io.IOException;
@@ -23,7 +24,9 @@
 import java.nio.file.Paths;
 import org.junit.Before;
 import org.junit.Test;
+import org.junit.runner.RunWith;
 
+@RunWith(VmTestRunner.class)
 public class LambdaRenamingTestRunner extends TestBase {
   static final Class CLASS = LambdaRenamingTest.class;
   static final Class[] CLASSES = LambdaRenamingTest.CLASSES;