Research in networked control systems raised the importance of understanding what are thetiming requirements for control. In recent years this problem has been attacked from multiple anglesincluding the computation of Maximal Allowable Transmission Intervals, event-triggered, and selftriggered controller implementations. In a self-triggered implementation the controller is responsible forcomputing the next time instant at which the actuator values should be updated by evaluating the controllaw on fresh sensor measurements. One of the main challenges in self-triggered control is how to performthe exact calculation of the time at which these updates should take place. In this paper we present anew technique to compute lower bounds on the self-triggered update times in a computationally lightmanner. We evaluate the algorithm on numerical examples and we observe that the algorithm performswell when compared to other existing methods and provides tight lower bounds on the exact updatetimes. Additionally, we propose a Semidefinite Programming-based technique that produces triggeringconditions that are less conservative than the existing ones and for which the update times are larger.