Bob Ostertag often performs improvised duos and trios. Usually he does with very long-time collaborators, such as Fred Frith or Phil Minton. More recent duos include Roscoe Mitchell and Mazen Kerbaj. In recent years he has maintained an improvisational trio with long-time collaborators Jon Rose and Gerry Hemingway.
Probably his best-known trio is House of Discipline, with Mike Patton and Otomo Yoshihide, which did a raucous set at the Angelica Festival in Bologna in 1997. The set was released by the Festival under the title The Art of FistFucking. Since the track includes Mike Patton, who is a heavy metal celebrity, the track gets far more plays online than anything else Ostertag has done, despite the fact that it was a one-off improvised set.