In a seminal paper from 1985, Sistla and Clarke showed
that satisfiability for Linear Temporal Logic (LTL) is either
NP-complete or PSPACE-complete, depending on the set of temporal
operators used

If, in contrast, the set of propositional operators is restricted, the
complexity may ... more >>>

We prove that the integrality gap after tightening the standard LP relaxation for Vertex Cover with Omega(sqrt(log n/log log n)) rounds of the SDP LS+ system is 2-o(1).

more >>>

We examine the communication required for generating random variables
remotely. One party Alice will be given a distribution D, and she
has to send a message to Bob, who is then required to generate a
value with distribution exactly D. Alice and Bob are allowed
to share random bits generated ... more >>>