diff --git a/src/main/java/com/android/tools/r8/graph/DexItemFactory.java b/src/main/java/com/android/tools/r8/graph/DexItemFactory.java
index feef8f7..91b1dc7 100644
--- a/src/main/java/com/android/tools/r8/graph/DexItemFactory.java
+++ b/src/main/java/com/android/tools/r8/graph/DexItemFactory.java
@@ -729,8 +729,10 @@
   }
 
   public DexCallSite createCallSite(
-      DexString methodName, DexProto methodProto,
-      DexMethodHandle bootstrapMethod, List<DexValue> bootstrapArgs) {
+      DexString methodName,
+      DexProto methodProto,
+      DexMethodHandle bootstrapMethod,
+      List<DexValue> bootstrapArgs) {
     // Call sites are never equal and therefore we do not canonicalize.
     assert !sorted;
     DexCallSite callSite = new DexCallSite(methodName, methodProto, bootstrapMethod, bootstrapArgs);
diff --git a/src/main/java/com/android/tools/r8/ir/desugar/LambdaDescriptor.java b/src/main/java/com/android/tools/r8/ir/desugar/LambdaDescriptor.java
index b7653fa..94bf56c 100644
--- a/src/main/java/com/android/tools/r8/ir/desugar/LambdaDescriptor.java
+++ b/src/main/java/com/android/tools/r8/ir/desugar/LambdaDescriptor.java
@@ -98,9 +98,10 @@
         if (target == null) {
           target = appInfo.lookupDirectTarget(method);
         }
-        assert target == null ||
-            (implHandle.type.isInvokeInstance() && isInstanceMethod(target)) ||
-            (implHandle.type.isInvokeDirect() && isPrivateInstanceMethod(target));
+        assert target == null
+            || (implHandle.type.isInvokeInstance() && isInstanceMethod(target))
+            || (implHandle.type.isInvokeDirect() && isPrivateInstanceMethod(target))
+            || (implHandle.type.isInvokeDirect() && isPublicizedInstanceMethod(target));
         return target;
       }
 
@@ -129,12 +130,17 @@
 
   private boolean isInstanceMethod(DexEncodedMethod encodedMethod) {
     assert encodedMethod != null;
-    return !encodedMethod.accessFlags.isConstructor() && !encodedMethod.accessFlags.isStatic();
+    return !encodedMethod.accessFlags.isConstructor() && !encodedMethod.isStaticMethod();
   }
 
   private boolean isPrivateInstanceMethod(DexEncodedMethod encodedMethod) {
     assert encodedMethod != null;
-    return encodedMethod.accessFlags.isPrivate() && isInstanceMethod(encodedMethod);
+    return encodedMethod.isPrivateMethod() && isInstanceMethod(encodedMethod);
+  }
+
+  private boolean isPublicizedInstanceMethod(DexEncodedMethod encodedMethod) {
+    assert encodedMethod != null;
+    return encodedMethod.isPublicized() && isInstanceMethod(encodedMethod);
   }
 
   final MethodAccessFlags getAccessibility() {
diff --git a/src/main/java/com/android/tools/r8/optimize/ClassAndMemberPublicizer.java b/src/main/java/com/android/tools/r8/optimize/ClassAndMemberPublicizer.java
index eaeb1ee..04f8a3b 100644
--- a/src/main/java/com/android/tools/r8/optimize/ClassAndMemberPublicizer.java
+++ b/src/main/java/com/android/tools/r8/optimize/ClassAndMemberPublicizer.java
@@ -18,11 +18,13 @@
 import com.android.tools.r8.utils.Timing;
 import com.google.common.base.Equivalence;
 import com.google.common.base.Equivalence.Wrapper;
-import com.google.common.collect.Sets;
 import java.util.ArrayList;
+import java.util.HashSet;
 import java.util.LinkedHashSet;
 import java.util.List;
+import java.util.Map;
 import java.util.Set;
+import java.util.concurrent.ConcurrentHashMap;
 import java.util.concurrent.ExecutionException;
 import java.util.concurrent.ExecutorService;
 import java.util.concurrent.Future;
@@ -31,12 +33,11 @@
   private final DexApplication application;
   private final AppInfo appInfo;
   private final RootSet rootSet;
-  private final GraphLense previuosLense;
+  private final GraphLense previousLense;
   private final PublicizedLenseBuilder lenseBuilder;
 
   private final Equivalence<DexMethod> equivalence = MethodSignatureEquivalence.get();
-  // TODO(b/72109068): finer-grained naming spaces, e.g., per-tree.
-  private final Set<Wrapper<DexMethod>> methodPool = Sets.newConcurrentHashSet();
+  private final Map<DexClass, MethodPool> methodPools = new ConcurrentHashMap<>();
 
   private ClassAndMemberPublicizer(
       DexApplication application,
@@ -46,7 +47,7 @@
     this.application = application;
     this.appInfo = appInfo;
     this.rootSet = rootSet;
-    this.previuosLense = previousLense;
+    this.previousLense = previousLense;
     lenseBuilder = PublicizerLense.createBuilder();
   }
 
@@ -74,9 +75,8 @@
     timing.begin("Phase 1: collectMethods");
     try {
       List<Future<?>> futures = new ArrayList<>();
-      // TODO(b/72109068): finer-grained naming spaces will need a different class visiting.
       application.classes().forEach(clazz ->
-          futures.add(executorService.submit(collectMethodPerClass(clazz))));
+          futures.add(executorService.submit(computeMethodPoolPerClass(clazz))));
       ThreadUtils.awaitFutures(futures);
     } finally {
       timing.end();
@@ -88,17 +88,35 @@
     publicizeType(appInfo.dexItemFactory.objectType);
     timing.end();
 
-    return lenseBuilder.build(appInfo, previuosLense);
+    return lenseBuilder.build(appInfo, previousLense);
   }
 
-  private Runnable collectMethodPerClass(DexClass clazz) {
+  private Runnable computeMethodPoolPerClass(DexClass clazz) {
     return () -> {
+      MethodPool methodPool = methodPools.computeIfAbsent(clazz, k -> new MethodPool());
       clazz.forEachMethod(encodedMethod -> {
         // We will add private instance methods when we promote them.
         if (!encodedMethod.isPrivateMethod() || encodedMethod.isStaticMethod()) {
-          methodPool.add(equivalence.wrap(encodedMethod.method));
+          methodPool.seen(equivalence.wrap(encodedMethod.method));
         }
       });
+      if (clazz.superType != null) {
+        DexClass superClazz = application.definitionFor(clazz.superType);
+        if (superClazz != null) {
+          MethodPool superPool = methodPools.computeIfAbsent(superClazz, k -> new MethodPool());
+          superPool.linkSubtype(methodPool);
+          methodPool.linkSupertype(superPool);
+        }
+      }
+      if (clazz.isInterface()) {
+        clazz.type.forAllImplementsSubtypes(implementer -> {
+          DexClass subClazz = application.definitionFor(implementer);
+          if (subClazz != null) {
+            MethodPool childPool = methodPools.computeIfAbsent(subClazz, k -> new MethodPool());
+            childPool.linkInterface(methodPool);
+          }
+        });
+      }
     };
   }
 
@@ -118,7 +136,6 @@
       }
     }
 
-    // TODO(b/72109068): Can process sub types in parallel.
     type.forAllExtendsSubtypes(this::publicizeType);
   }
 
@@ -152,21 +169,22 @@
 
       // We can't publicize private instance methods in interfaces or methods that are copied from
       // interfaces to lambda-desugared classes because this will be added as a new default method.
-      // TODO(b/72109068): It might be possible to transform it into static methods, though.
+      // TODO(b/111118390): It might be possible to transform it into static methods, though.
       if (holder.isInterface() || accessFlags.isSynthetic()) {
         return false;
       }
 
+      MethodPool methodPool = methodPools.get(holder);
       Wrapper<DexMethod> key = equivalence.wrap(encodedMethod.method);
-      if (methodPool.contains(key)) {
+      if (methodPool.hasSeen(key)) {
         // We can't do anything further because even renaming is not allowed due to the keep rule.
         if (rootSet.noObfuscation.contains(encodedMethod)) {
           return false;
         }
-        // TODO(b/72109068): Renaming will enable more private instance methods to be publicized.
+        // TODO(b/111118390): Renaming will enable more private instance methods to be publicized.
         return false;
       }
-      methodPool.add(key);
+      methodPool.seen(key);
       lenseBuilder.add(encodedMethod.method);
       accessFlags.unsetPrivate();
       accessFlags.setFinal();
@@ -186,4 +204,51 @@
     accessFlags.setPublic();
     return false;
   }
+
+  // Per-class collection of method signatures, which will be used to determine if a certain method
+  // can be publicized or not.
+  static class MethodPool {
+    private MethodPool superType;
+    private final Set<MethodPool> interfaces = new HashSet<>();
+    private final Set<MethodPool> subTypes = new HashSet<>();
+    private final Set<Wrapper<DexMethod>> methodPool = new HashSet<>();
+
+    MethodPool() {
+    }
+
+    synchronized void linkSupertype(MethodPool superType) {
+      assert this.superType == null;
+      this.superType = superType;
+    }
+
+    synchronized void linkSubtype(MethodPool subType) {
+      boolean added = subTypes.add(subType);
+      assert added;
+    }
+
+    synchronized void linkInterface(MethodPool itf) {
+      boolean added = interfaces.add(itf);
+      assert added;
+    }
+
+    synchronized void seen(Wrapper<DexMethod> method) {
+      boolean added = methodPool.add(method);
+      assert added;
+    }
+
+    boolean hasSeen(Wrapper<DexMethod> method) {
+      return hasSeenUpwardRecursive(method) || hasSeenDownwardRecursive(method);
+    }
+
+    private boolean hasSeenUpwardRecursive(Wrapper<DexMethod> method) {
+      return methodPool.contains(method)
+          || (superType != null && superType.hasSeenUpwardRecursive(method))
+          || interfaces.stream().anyMatch(itf -> itf.hasSeenUpwardRecursive(method));
+    }
+
+    private boolean hasSeenDownwardRecursive(Wrapper<DexMethod> method) {
+      return methodPool.contains(method)
+          || subTypes.stream().anyMatch(subType -> subType.hasSeenDownwardRecursive(method));
+    }
+  }
 }
diff --git a/src/test/java/com/android/tools/r8/accessrelaxation/AccessRelaxationTest.java b/src/test/java/com/android/tools/r8/accessrelaxation/AccessRelaxationTest.java
index 027b7e8..53a8c31 100644
--- a/src/test/java/com/android/tools/r8/accessrelaxation/AccessRelaxationTest.java
+++ b/src/test/java/com/android/tools/r8/accessrelaxation/AccessRelaxationTest.java
@@ -171,10 +171,13 @@
     assertNotPublic(dexInspector, Base.class,
         new MethodSignature("foo2", STRING, ImmutableList.of()));
 
-    // Sub1#bar1(int) can't be publicized due to Base#bar1(int).
-    assertNotPublic(dexInspector, Sub1.class,
+    // Sub?#bar1(int) can be publicized as they don't bother each other.
+    assertPublic(dexInspector, Sub1.class,
+        new MethodSignature("bar1", STRING, ImmutableList.of("int")));
+    assertPublic(dexInspector, Sub2.class,
         new MethodSignature("bar1", STRING, ImmutableList.of("int")));
 
+    // Sub2#bar2(int) is unique throughout the hierarchy, hence publicized.
     assertPublic(dexInspector, Sub2.class,
         new MethodSignature("bar2", STRING, ImmutableList.of("int")));
   }
diff --git a/src/test/java/com/android/tools/r8/accessrelaxation/privateinstance/Base.java b/src/test/java/com/android/tools/r8/accessrelaxation/privateinstance/Base.java
index fd1fd1c..6325c78 100644
--- a/src/test/java/com/android/tools/r8/accessrelaxation/privateinstance/Base.java
+++ b/src/test/java/com/android/tools/r8/accessrelaxation/privateinstance/Base.java
@@ -30,19 +30,10 @@
     return foo2();
   }
 
-  private synchronized String bar1(int i) {
-    throw new AssertionError("Sub1#bar1(int) will not use this signature.");
-  }
-
   public void dump() {
     System.out.println(foo());
     System.out.println(foo1());
     System.out.println(foo2());
-    try {
-      bar1(0);
-    } catch (AssertionError e) {
-      // expected
-    }
   }
 
 }
diff --git a/src/test/java/com/android/tools/r8/accessrelaxation/privateinstance/Sub1.java b/src/test/java/com/android/tools/r8/accessrelaxation/privateinstance/Sub1.java
index 4cbbf11..317aaff 100644
--- a/src/test/java/com/android/tools/r8/accessrelaxation/privateinstance/Sub1.java
+++ b/src/test/java/com/android/tools/r8/accessrelaxation/privateinstance/Sub1.java
@@ -22,11 +22,7 @@
   public void dump() {
     System.out.println(foo1());
     System.out.println(foo1(0));
-    try {
-      System.out.println(bar1(0));
-    } catch (Throwable e) {
-      System.out.println(e.getClass().getName());
-    }
+    System.out.println(bar1(0));
   }
 
 }
diff --git a/src/test/java/com/android/tools/r8/accessrelaxation/privateinstance/Sub2.java b/src/test/java/com/android/tools/r8/accessrelaxation/privateinstance/Sub2.java
index 8c4e01e..039e3ac 100644
--- a/src/test/java/com/android/tools/r8/accessrelaxation/privateinstance/Sub2.java
+++ b/src/test/java/com/android/tools/r8/accessrelaxation/privateinstance/Sub2.java
@@ -10,6 +10,14 @@
     return "Sub2::foo2()";
   }
 
+  private synchronized String bar1(int i) {
+    return "Sub2::bar1(" + i + ")";
+  }
+
+  public String pBar1() {
+    return bar1(1);
+  }
+
   private synchronized String bar2(int i) {
     return "Sub2::bar2(" + i + ")";
   }
@@ -23,6 +31,11 @@
     System.out.println(foo2());
     System.out.println(foo2(0));
     System.out.println(bar2(0));
+    try {
+      bar1(0);
+    } catch (AssertionError e) {
+      // expected
+    }
   }
 
 }