In logics with the Craig interpolation property (CIP) the existence of an interpolant for an implication follows from the validity of the implication. In logics with the projective Beth definability property (PBDP), the existence of an explicit definition of a relation follows from the validity of a formula expressing its implicit definability. From an algorithmic viewpoint, the CIP and PBDP are of interest because they reduce existence problems to validity checking: an interpolant exists if, and only if, an implication is valid and an explicit definition exists if, and only if, a straightforward formula stating implicit definability is valid. The interpolant and explicit definition existence problems are thus not harder than validity. While many logics enjoy the CIP and the PBDP (for instance, first-order logic (FO), propositional logic, intuitionistic logic, and many modal and description logics), there are also many important logics that neither enjoy the CIP nor the PBDP. Examples include modal and description logics with nominals, the twovariable fragment of FO, the guarded fragment of FO, and most Horn-fragments of modal and description logics. In this talk, I will present recent results on the decidability and complexity of interpolant and explicit definition existence for logics that do not enjoy the CIP nor PBDP. For example, we show that the existence of explicit definitions of concept names (and individual names) relative to an ontology in the extension ALCO of ALC with nominals is 2ExpTimecomplete and that the existence of explicit definitions of relation in the guarded fragment is 3ExpTime-complete, thus in both cases by one exponential harder than deduction. The presentation is based on [1,3,2].