We develop a nonequilibrium many-body theory of the coherent femtosecond nonlinear optical response of the Fermi-edge singularity. We study the role of the dynamical Fermi-sea response in the time evolution of the pump-probe spectra. The electron-hole correlations are treated nonperturbatively with the time-dependent coupled cluster expansion combined with the effective Hamiltonian approach. For short pulse durations, we find a nonexponential decay of the differential transmission during negative time delays, which is governed by the interactions. This is in contrast to the results obtained within the Hartree-Fock approximation, which predicts an exponential decay governed by the dephasing time. We discuss the role of the optically induced dephasing effects in the coherent regime. © 2000 The American Physical Society.