  Massive 10^6-10^10 Msun black holes (BHs) are ubiquitous in local galactic
nuclei. They were common by the time the Universe is several Gyr old, and many
of them were in place within the first 1~Gyr after the Big Bang. Their quick
assembly has been attributed to mechanisms such as the rapid collapse of gas
into the nuclei of early protogalaxies, accretion and mergers of stellar-mass
BHs accompanying structure formation at early times, and the runaway collapse
of early, ultra-dense stellar clusters. The origin of the early massive BHs
remains an intriguing and long-standing unsolved puzzle in astrophysics. Here
we discuss strategies for discerning between BH seeding models using
electromagnetic observations. We argue that the most direct answers will be
obtained through detection of BHs with masses M<10^5 Msun at redshifts z>10,
where we expect them to first form. Reaching out to these redshifts and down to
these masses is crucial, because BHs are expected to lose the memory of their
initial assembly by the time they grow well above 10^5 Msun and are
incorporated into higher-mass galaxies. The best way to detect 10^4-10^5 Msun
BHs at high redshifts is by a sensitive X-ray survey. Critical constraining
power is augmented by establishing the properties and the environments of their
host galaxies in deep optical/IR imaging surveys. Required OIR data can be
obtained with the JWST and WFIRST missions. The required X-ray flux limits
(down to 10^{-19} erg/s/cm^2) are accessible only with a next-generation X-ray
observatory which has both high (sub-1") angular resolution and high
throughput. A combination of deep X-ray and OIR surveys will be capable of
probing several generic markers of the BH seed scenarios, and resolving the
long-stanging puzzle of their origin. These electromagnetic observations are
also highly synergistic with the information from LISA on high-z BH mergers.
