diff --git a/src/main/java/com/android/tools/r8/Version.java b/src/main/java/com/android/tools/r8/Version.java
index 1041a82..92e7a74 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.5.44";
+  public static final String LABEL = "1.5.45";
 
   private Version() {
   }
diff --git a/src/main/java/com/android/tools/r8/graph/AppInfoWithSubtyping.java b/src/main/java/com/android/tools/r8/graph/AppInfoWithSubtyping.java
index a9773f8..6122236 100644
--- a/src/main/java/com/android/tools/r8/graph/AppInfoWithSubtyping.java
+++ b/src/main/java/com/android/tools/r8/graph/AppInfoWithSubtyping.java
@@ -363,15 +363,31 @@
       }
     }
 
+    Consumer<DexEncodedMethod> addIfNotAbstract =
+        m -> {
+          if (!m.accessFlags.isAbstract()) {
+            result.add(m);
+          }
+        };
+    // Default methods are looked up when looking at a specific subtype that does not override them.
+    // Otherwise, we would look up default methods that are actually never used. However, we have to
+    // add bridge methods, otherwise we can remove a bridge that will be used.
+    Consumer<DexEncodedMethod> addIfNotAbstractAndBridge =
+        m -> {
+          if (!m.accessFlags.isAbstract() && m.accessFlags.isBridge()) {
+            result.add(m);
+          }
+        };
+
     Set<DexType> set = subtypes(method.holder);
     for (DexType type : set) {
       DexClass clazz = definitionFor(type);
-      // Default methods are looked up when looking at a specific subtype that does not
-      // override them, so we ignore interfaces here. Otherwise, we would look up default methods
-      // that are factually never used.
-      if (!clazz.isInterface()) {
+      if (clazz.isInterface()) {
+        ResolutionResult targetMethods = resolveMethodOnInterface(type, method);
+        targetMethods.forEachTarget(addIfNotAbstractAndBridge);
+      } else {
         ResolutionResult targetMethods = resolveMethodOnClass(type, method);
-        targetMethods.forEachTarget(result::add);
+        targetMethods.forEachTarget(addIfNotAbstract);
       }
     }
     return result;
diff --git a/src/main/java/com/android/tools/r8/shaking/Enqueuer.java b/src/main/java/com/android/tools/r8/shaking/Enqueuer.java
index 9f48d56..d02b735 100644
--- a/src/main/java/com/android/tools/r8/shaking/Enqueuer.java
+++ b/src/main/java/com/android/tools/r8/shaking/Enqueuer.java
@@ -7,6 +7,7 @@
 import static com.android.tools.r8.naming.IdentifierNameStringUtils.isReflectionMethod;
 import static com.android.tools.r8.shaking.AnnotationRemover.shouldKeepAnnotation;
 import static com.android.tools.r8.shaking.EnqueuerUtils.extractProgramFieldDefinitions;
+import static com.google.common.base.Predicates.or;
 
 import com.android.tools.r8.Diagnostic;
 import com.android.tools.r8.dex.IndexedItemCollection;
@@ -1298,7 +1299,9 @@
 
   private boolean isInstantiatedOrHasInstantiatedSubtype(DexType type) {
     return instantiatedTypes.contains(type)
-        || appInfo.subtypes(type).stream().anyMatch(instantiatedTypes::contains);
+        || instantiatedLambdas.contains(type)
+        || appInfo.subtypes(type).stream()
+            .anyMatch(or(instantiatedTypes::contains, instantiatedLambdas::contains));
   }
 
   private void markInstanceFieldAsReachable(DexField field, KeepReason reason) {
@@ -1377,42 +1380,61 @@
         interfaceInvoke
             ? appInfo.lookupInterfaceTargets(method)
             : appInfo.lookupVirtualTargets(method);
-    for (DexEncodedMethod encodedMethod : possibleTargets) {
+    for (DexEncodedMethod encodedPossibleTarget : possibleTargets) {
+      DexMethod possibleTarget = encodedPossibleTarget.method;
+      DexClass clazz = appView.definitionFor(possibleTarget.holder);
+      if (clazz == null) {
+        assert false;
+        continue;
+      }
+
+      if (!clazz.isProgramClass()) {
+        // Should only be tracing the program.
+        continue;
+      }
+
       // TODO(b/120959039): The reachable.add test might be hiding other paths to the method.
       SetWithReason<DexEncodedMethod> reachable =
           reachableVirtualMethods.computeIfAbsent(
-              encodedMethod.method.holder, ignore -> newSetWithoutReasonReporter());
-      if (reachable.add(encodedMethod, reason)) {
-        // Abstract methods cannot be live.
-        if (!encodedMethod.accessFlags.isAbstract()) {
-          // If the holder type is instantiated, the method is live. Otherwise check whether we find
-          // a subtype that does not shadow this methods but is instantiated.
-          // Note that library classes are always considered instantiated, as we do not know where
-          // they are instantiated.
-          if (isInstantiatedOrHasInstantiatedSubtype(encodedMethod.method.holder)) {
-            if (instantiatedTypes.contains(encodedMethod.method.holder)) {
-              markVirtualMethodAsLive(encodedMethod,
-                  KeepReason.reachableFromLiveType(encodedMethod.method.holder));
-            } else {
-              Deque<DexType> worklist = new ArrayDeque<>();
-              fillWorkList(worklist, encodedMethod.method.holder);
-              while (!worklist.isEmpty()) {
-                DexType current = worklist.pollFirst();
-                DexClass currentHolder = appView.definitionFor(current);
-                // If this class overrides the virtual, abort the search. Note that, according to
-                // the JVM spec, private methods cannot override a virtual method.
-                if (currentHolder == null
-                    || currentHolder.lookupVirtualMethod(encodedMethod.method) != null) {
-                  continue;
-                }
-                if (instantiatedTypes.contains(current)) {
-                  markVirtualMethodAsLive(encodedMethod, KeepReason.reachableFromLiveType(current));
-                  break;
-                }
-                fillWorkList(worklist, current);
-              }
-            }
+              possibleTarget.holder, ignore -> newSetWithoutReasonReporter());
+      if (!reachable.add(encodedPossibleTarget, reason)) {
+        continue;
+      }
+
+      // Abstract methods cannot be live.
+      if (encodedPossibleTarget.accessFlags.isAbstract()) {
+        continue;
+      }
+
+      // If the holder type is instantiated, the method is live. Otherwise check whether we find
+      // a subtype that does not shadow this methods but is instantiated.
+      // Note that library classes are always considered instantiated, as we do not know where
+      // they are instantiated.
+      if (!isInstantiatedOrHasInstantiatedSubtype(possibleTarget.holder)) {
+        continue;
+      }
+
+      if (instantiatedTypes.contains(possibleTarget.holder)
+          || instantiatedLambdas.contains(possibleTarget.holder)) {
+        markVirtualMethodAsLive(
+            encodedPossibleTarget, KeepReason.reachableFromLiveType(possibleTarget.holder));
+      } else {
+        Deque<DexType> worklist =
+            new ArrayDeque<>(appInfo.allImmediateSubtypes(possibleTarget.holder));
+        while (!worklist.isEmpty()) {
+          DexType current = worklist.pollFirst();
+          DexClass currentHolder = appView.definitionFor(current);
+          // If this class overrides the virtual, abort the search. Note that, according to
+          // the JVM spec, private methods cannot override a virtual method.
+          if (currentHolder == null || currentHolder.lookupVirtualMethod(possibleTarget) != null) {
+            continue;
           }
+          if (instantiatedTypes.contains(current)) {
+            markVirtualMethodAsLive(
+                encodedPossibleTarget, KeepReason.reachableFromLiveType(current));
+            break;
+          }
+          appInfo.allImmediateSubtypes(current).forEach(worklist::addLast);
         }
       }
     }
@@ -1444,18 +1466,6 @@
     }
   }
 
-  private void fillWorkList(Deque<DexType> worklist, DexType type) {
-    if (appInfo.isMarkedAsInterface(type)) {
-      // We need to check if the method is shadowed by a class that directly implements
-      // the interface and go recursively down to the sub interfaces to reach class
-      // implementing the interface
-      appInfo.forAllImplementsSubtypes(type, worklist::addLast);
-      appInfo.forAllExtendsSubtypes(type, worklist::addLast);
-    } else {
-      appInfo.forAllExtendsSubtypes(type, worklist::addLast);
-    }
-  }
-
   private void markSuperMethodAsReachable(DexMethod method, DexEncodedMethod from) {
     // We have to mark the immediate target of the descriptor as targeted, as otherwise
     // the invoke super will fail in the resolution step with a NSM error.
diff --git a/src/test/java/com/android/tools/r8/shaking/interfacebridge/LambdaAbstractMethodErrorTest.java b/src/test/java/com/android/tools/r8/shaking/interfacebridge/LambdaAbstractMethodErrorTest.java
new file mode 100644
index 0000000..48576f5
--- /dev/null
+++ b/src/test/java/com/android/tools/r8/shaking/interfacebridge/LambdaAbstractMethodErrorTest.java
@@ -0,0 +1,48 @@
+// Copyright (c) 2019, 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.shaking.interfacebridge;
+
+import com.android.tools.r8.CompilationFailedException;
+import com.android.tools.r8.TestBase;
+import com.android.tools.r8.TestParameters;
+import com.android.tools.r8.TestParametersCollection;
+import java.io.IOException;
+import java.util.concurrent.ExecutionException;
+import org.junit.Test;
+import org.junit.runner.RunWith;
+import org.junit.runners.Parameterized;
+import org.junit.runners.Parameterized.Parameters;
+
+@RunWith(Parameterized.class)
+public class LambdaAbstractMethodErrorTest extends TestBase {
+
+  private final TestParameters parameters;
+
+  @Parameters(name = "{0}")
+  public static TestParametersCollection data() {
+    return getTestParameters().withDexRuntimes().build();
+  }
+
+  public LambdaAbstractMethodErrorTest(TestParameters parameters) {
+    this.parameters = parameters;
+  }
+
+  @Test
+  public void test_b133457361() throws ExecutionException, CompilationFailedException, IOException {
+    testForR8(parameters.getBackend())
+        .addProgramClassesAndInnerClasses(Main.class)
+        .addProgramClassesAndInnerClasses(Task.class, OuterClass.class)
+        .addKeepMainRule(Main.class)
+        .addOptionsModification(
+            internalOptions -> {
+              internalOptions.enableInlining = false;
+              internalOptions.enableClassInlining = false;
+              internalOptions.enableVerticalClassMerging = false;
+            })
+        .setMinApi(parameters.getRuntime())
+        .run(Main.class.getTypeName())
+        .assertSuccessWithOutput("FOO");
+  }
+}
diff --git a/src/test/java/com/android/tools/r8/shaking/interfacebridge/Main.java b/src/test/java/com/android/tools/r8/shaking/interfacebridge/Main.java
new file mode 100644
index 0000000..5c3fb27
--- /dev/null
+++ b/src/test/java/com/android/tools/r8/shaking/interfacebridge/Main.java
@@ -0,0 +1,12 @@
+// Copyright (c) 2019, 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.shaking.interfacebridge;
+
+public class Main {
+
+  public static void main(String[] args) {
+    OuterClass.startTask(result -> System.out.print(result));
+  }
+}
diff --git a/src/test/java/com/android/tools/r8/shaking/interfacebridge/OuterClass.java b/src/test/java/com/android/tools/r8/shaking/interfacebridge/OuterClass.java
new file mode 100644
index 0000000..af0b8bc
--- /dev/null
+++ b/src/test/java/com/android/tools/r8/shaking/interfacebridge/OuterClass.java
@@ -0,0 +1,29 @@
+// Copyright (c) 2019, 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.shaking.interfacebridge;
+
+public class OuterClass {
+
+  public interface Callback extends Task.OnTaskFinishedListener<String> {
+    @Override
+    void onTaskFinished(String result);
+  }
+
+  private static class ConcreteTask extends Task<String> {
+
+    public ConcreteTask(Callback listener) {
+      super(listener);
+    }
+
+    @Override
+    public String doInBackground() {
+      return "FOO";
+    }
+  }
+
+  public static void startTask(Callback callback) {
+    new ConcreteTask(callback).execute();
+  }
+}
diff --git a/src/test/java/com/android/tools/r8/shaking/interfacebridge/Task.java b/src/test/java/com/android/tools/r8/shaking/interfacebridge/Task.java
new file mode 100644
index 0000000..98204ef
--- /dev/null
+++ b/src/test/java/com/android/tools/r8/shaking/interfacebridge/Task.java
@@ -0,0 +1,30 @@
+// Copyright (c) 2019, 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.shaking.interfacebridge;
+
+public abstract class Task<Result> {
+
+  public interface OnTaskFinishedListener<Result> {
+    void onTaskFinished(Result result);
+  }
+
+  public abstract Result doInBackground();
+
+  public void execute() {
+    onPostExecute(doInBackground());
+  }
+
+  OnTaskFinishedListener<Result> mListener;
+
+  Task(OnTaskFinishedListener<Result> listener) {
+    mListener = listener;
+  }
+
+  public void onPostExecute(Result result) {
+    if (mListener != null) {
+      mListener.onTaskFinished(result);
+    }
+  }
+}