Abstract:
The temperature behaviour in the range 22\degree C to 500\degree C of the dielectric permittivity in the infrared range is investigated for CaF2, BaF2 and Al2O3 through reflectivity measurements. The dielectric permittivity is retrieved by fitting reflectivity spectra with a model taking into account multiphonon contributions. The results extrapolated from the measurements are applied to predict a temperature-dependent atom-surface van der Waals interaction. We specifically consider as the atom of interest Cs (8P3/2), the most relevant virtual couplings of which, fall in the range of thermal radiation and are located in the vicinity of the reststrahlen band of fluoride materials.

Abstract:
The standard tabulation techniques for logic programming presuppose fixed order of computation. Some data-driven control should be introduced in order to deal with diverse contexts. The present paper describes a data-driven method of constraint transformation with a sort of compilation which subsumes accessibility check and last-call optimization, which characterize standard natural-language parsing techniques, semantic-head-driven generation, etc.

Abstract:
I present an algorithm that, given a number $n \geq 1$, computes a compact representation of the set of all noncrossing acyclic digraphs with $n$ nodes. This compact representation can be used as the basis for a wide range of dynamic programming algorithms on these graphs. As an illustration, along with this note I am releasing the implementation of an algorithm for counting the number of noncrossing acyclic digraphs of a given size. The same tabulation can be modified to count other classes of combinatorial structures, including weakly connected noncrossing acyclic digraphs, general noncrossing digraphs, noncrossing undirected graphs.

Abstract:
Randomized algorithms are often enjoyed for their simplicity, but the hash functions used to yield the desired theoretical guarantees are often neither simple nor practical. Here we show that the simplest possible tabulation hashing provides unexpectedly strong guarantees. The scheme itself dates back to Carter and Wegman (STOC'77). Keys are viewed as consisting of c characters. We initialize c tables T_1, ..., T_c mapping characters to random hash codes. A key x=(x_1, ..., x_q) is hashed to T_1[x_1] xor ... xor T_c[x_c]. While this scheme is not even 4-independent, we show that it provides many of the guarantees that are normally obtained via higher independence, e.g., Chernoff-type concentration, min-wise hashing for estimating set intersection, and cuckoo hashing.

Abstract:
Randomized algorithms are often enjoyed for their simplicity, but the hash functions employed to yield the desired probabilistic guarantees are often too complicated to be practical. Here we survey recent results on how simple hashing schemes based on tabulation provide unexpectedly strong guarantees. {\em Simple tabulation hashing\/} dates back to Zobrist [1970]. Keys are viewed as consisting of $c$ characters and we have precomputed character tables $h_1,...,h_c$ mapping characters to random hash values. A key $x=(x_1,...,x_c)$ is hashed to $h_1[x_1] \oplus h_2[x_2].....\oplus h_c[x_c]$. This schemes is very fast with character tables in cache. While simple tabulation is not even 4-independent, it does provide many of the guarantees that are normally obtained via higher independence, e.g., linear probing and Cuckoo hashing. Next we consider {\em twisted tabulation\/} where one input character is "twisted" in a simple way. The resulting hash function has powerful distributional properties: Chernoff-Hoeffding type tail bounds and a very small bias for min-wise hashing. This is also yields an extremely fast pseudo-random number generator that is provably good for many classic randomized algorithms and data-structures. Finally, we consider {\em double tabulation\/} where we compose two simple tabulation functions, applying one to the output of the other, and show that this yields very high independence in the classic framework of Carter and Wegman [1977]. In fact, w.h.p., for a given set of size proportional to that of the space consumed, double tabulation gives fully-random hashing. We also mention some more elaborate tabulation schemes getting near-optimal independence for given time and space. While these tabulation schemes are all easy to implement and use, their analysis is not.

Abstract:
A random hash function $h$ is $\varepsilon$-minwise if for any set $S$, $|S|=n$, and element $x\in S$, $\Pr[h(x)=\min h(S)]=(1\pm\varepsilon)/n$. Minwise hash functions with low bias $\varepsilon$ have widespread applications within similarity estimation. Hashing from a universe $[u]$, the twisted tabulation hashing of P\v{a}tra\c{s}cu and Thorup [SODA'13] makes $c=O(1)$ lookups in tables of size $u^{1/c}$. Twisted tabulation was invented to get good concentration for hashing based sampling. Here we show that twisted tabulation yields $\tilde O(1/u^{1/c})$-minwise hashing. In the classic independence paradigm of Wegman and Carter [FOCS'79] $\tilde O(1/u^{1/c})$-minwise hashing requires $\Omega(\log u)$-independence [Indyk SODA'99]. P\v{a}tra\c{s}cu and Thorup [STOC'11] had shown that simple tabulation, using same space and lookups yields $\tilde O(1/n^{1/c})$-minwise independence, which is good for large sets, but useless for small sets. Our analysis uses some of the same methods, but is much cleaner bypassing a complicated induction argument.

Abstract:
The power of two choices is a classic paradigm used for assigning $m$ balls to $n$ bins. When placing a ball we pick two bins according to some hash functions $h_0$ and $h_1$, and place the ball in the least full bin. It was shown by Azar et al.~[STOC'94] that for $m = O(n)$ with perfectly random hash functions this scheme yields a maximum load of $\lg \lg n + O(1)$ with high probability. The two-choice paradigm has many applications in e.g.~hash tables and on-line assignment of tasks to servers. In this paper we investigate the two-choice paradigm using the very efficient simple tabulation hashing scheme. This scheme dates back to Zobrist in 1970, and has since been studied by P\v{a}tra\c{s}cu and Thorup [STOC'11]. P\v{a}tra\c{s}cu and Thorup claimed without proof that simple tabulation gives an expected maximum load of $O(\log\log n)$. We improve their result in two ways. We show that the expected maximum load, when placing $m = O(n)$ balls into two tables of $n$ bins, is at most $\lg\lg n + O(1)$. Furthermore, unlike with fully random hashing, we show that with simple tabulation hashing, the maximum load is not bounded by $\lg \lg n + O(1)$, or even $(1+o(1))\lg \lg n$ with high probability. However, we do show that it is bounded by $O(\log \log n)$ with high probability, which is only a constant factor worse than the fully random case. Previously, such bounds have required $\Omega(\log n)$-independent hashing, or other methods that require $\omega(1)$ computation time. Our analysis relies on classifying the dependencies between keys when using simple tabulation. We show, as a corollary, that these methods can be used to give good bounds for any constant moment.

Abstract:
Simple tabulation dates back to Zobrist in 1970. Keys are viewed as c characters from some alphabet A. We initialize c tables h_0, ..., h_{c-1} mapping characters to random hash values. A key x=(x_0, ..., x_{c-1}) is hashed to h_0[x_0] xor...xor h_{c-1}[x_{c-1}]. The scheme is extremely fast when the character hash tables h_i are in cache. Simple tabulation hashing is not 4-independent, but we show that if we apply it twice, then we get high independence. First we hash to intermediate keys that are 6 times longer than the original keys, and then we hash the intermediate keys to the final hash values. The intermediate keys have d=6c characters from A. We can view the hash function as a degree d bipartite graph with keys on one side, each with edges to d output characters. We show that this graph has nice expansion properties, and from that we get that with another level of simple tabulation on the intermediate keys, the composition is a highly independent hash function. The independence we get is |A|^{Omega(1/c)}. Our space is O(c|A|) and the hash function is evaluated in O(c) time. Siegel [FOCS'89, SICOMP'04] proved that with this space, if the hash function is evaluated in o(c) time, then the independence can only be o(c), so our evaluation time is best possible for Omega(c) independence---our independence is much higher if c=|A|^{o(1)}. Siegel used O(c)^c evaluation time to get the same independence with similar space. Siegel's main focus was c=O(1), but we are exponentially faster when c=omega(1). Applying our scheme recursively, we can increase our independence to |A|^{Omega(1)} with o(c^{log c}) evaluation time. Compared with Siegel's scheme this is both faster and higher independence. Our scheme is easy to implement, and it does provide realistic implementations of 100-independent hashing for, say, 32 and 64-bit keys.

Abstract:
A tabulation-based hash function maps a key into d derived characters indexing random values in tables that are then combined with bitwise xor operations to give the hash. Thorup and Zhang (2004) presented d-wise independent tabulation-based hash classes that use linear maps over finite fields to map a key, considered as a vector (a,b), to derived characters. We show that a variant where the derived characters are a+b*i for i=0,..., q-1 (using integer arithmetic) yielding (2d-1)-wise independence. Our analysis is based on an algebraic property that characterizes k-wise independence of tabulation-based hashing schemes, and combines this characterization with a geometric argument. We also prove a non-trivial lower bound on the number of derived characters necessary for k-wise independence with our and related hash classes.

Abstract:
The stochastic driving force exerted by a single molecular motor (e.g., a kinesin, or myosin) moving on a periodic molecular track (microtubule, actin filament, etc.) is discussed from a general viewpoint open to experimental test. An elementary "barometric" relation for the driving force is introduced that (i) applies to a range of kinetic and stochastic models, (ii) is consistent with more elaborate expressions entailing explicit representations of externally applied loads and, (iii) sufficiently close to thermal equilibrium, satisfies an Einstein-type relation in terms of the velocity and diffusion coefficient of the (load-free) motor. Even in the simplest two-state models, the velocity-vs.-load plots exhibit a variety of contrasting shapes (including nonmonotonic behavior). Previously suggested bounds on the driving force are shown to be inapplicable in general by analyzing discrete jump models with waiting time distributions.