Subset-sum-difference problem Consider the following problem:

SUBSET-SUM-DIFFERENCE: Let $S=\{s_1,\dots,s_n\}$ be a set of $n$ integers and $t$ be a "target" integer. Are there two disjoint subsets of $S$ (call them subsets $I$ and $J$) such that $\sum_{i \in I}s_i - \sum_{j \in J} s_j=t$.

The Meet-in-the-Middle algorithm will solve this problem in $\Theta(3^{n/2})$ time. Is there an exact and deterministic algorithm which solves this problem in $o(3^{n/2})$ time?
Maybe.

Becker, Coron, and Joux [EUROCRYPT 2011 describe an algorithm to solve random hard instances of Subset Sum (in fact, the more general Knapsack problem) in $\tilde{O}(2^{0.291n})$ time, beating the "meet in the middle" time bound $\tilde{O}(2^{n/2})$ by Shamir and Schroeppel [SICOMP 1981].  (Here, $\tilde{O}(f(n))$ is standard shorthand for $O(f(n)\operatorname{polylog} f(n))$.)

More recently, Dinur, Dunkelman, Keller, and Shamir [Crypto 2012], which establish better time-space tradeoffs (but do not improve worst-case running times) for a general class of cryptography problems that includes Knapsack.  Becker's techniques rely crucially on the observation that addition is both commutative and associative, but Dinur's techniques do not; for example, they also derive faster algorithms for solving random hard instances of permutation puzzles like the Rubik's cube.

It seems likely that Dinur's techniques would imply faster algorithms for (at least random hard instances of) your problem.