Search

This paper describes new, simple, recursive methods of construction for orientable sequences, i.e. periodic binary sequences in which any $n$ -tuple occurs at most once in a period in either direction. As has been previously described, such sequences have potential applications in automatic position-location systems, where the sequence is encoded onto a surface and a reader needs only examine $n$ consecutive encoded bits to determine its location and orientation on the surface. The only previously described method of construction (due to Dai et al.) is somewhat complex, whereas the new techniques are simple to both describe and implement. The methods of construction cover both the standard ‘infinite periodic’ case, and also the aperiodic, finite sequence, case. Both the new methods build on the Lempel homomorphism, first introduced as a means of recursively generating de Bruijn sequences. [ABSTRACT FROM AUTHOR]

In this paper, we present two new families of APN functions. The first family is in bivariate form $\big (x^{3}+xy^{2}+ y^{3}+xy, x^{5}+x^{4}y+y^{5}+xy+x^{2}y^{2} \big)\,\,\vphantom {_{\int _{\int }}}$ over ${\mathbb F}_{2^{m}}^{2}$. It is obtained by adding certain terms of the form $\sum _{i}(a_{i}x^{2^{i}}y^{2^{i}},b_{i}x^{2^{i}}y^{2^{i}})$ to a family of APN functions recently proposed by Gölo&gcaron;lu. The $\vphantom {_{\int _{\int }}}$ second family has the form $L(z)^{2^{m}+1}+vz^{2^{m}+1}$ over ${\mathbb F}_{{2^{3m}}}$ , which generalizes a family of APN functions by Bracken et al. from 2011. By calculating the $\Gamma $ -rank of the constructed APN functions over ${\mathbb F}_{2^{8}}$ and ${\mathbb F}_{2^{9}}$ , we demonstrate that the two families are CCZ-inequivalent to all known families. In addition, the two new families cover two known sporadic APN instances over ${\mathbb F}_{2^{8}}$ and ${\mathbb F}_{2^{9}}$ , which were found by Edel and Pott in 2009 and by Beierle and Leander in 2021, respectively. [ABSTRACT FROM AUTHOR]

In a recent work, Beierle, Brinkmann and Leander presented a recursive tree search for finding APN permutations with linear self-equivalences in small dimensions. In this paper, we describe how this search can be adapted to find many new instances of quadratic APN functions. In particular, we found 12,921 new quadratic APN functions in dimension eight, 35 new quadratic APN functions in dimension nine and five new quadratic APN functions in dimension ten up to CCZ-equivalence. Remarkably, two of the 35 new APN functions in dimension nine are APN permutations. Among the 8-bit APN functions, there are three extended Walsh spectra that do not correspond to any of the previously-known quadratic 8-bit APN functions and, surprisingly, there exist at least four CCZ-inequivalent 8-bit APN functions with linearity 27, i.e., the highest possible non-trivial linearity for quadratic functions in dimension eight. [ABSTRACT FROM AUTHOR]

We formulate and study the problem of ON-OFF privacy. ON-OFF privacy algorithms enable a user to continuously switch his privacy between ON and OFF. An obvious example is the incognito mode in internet browsers. But beyond internet browsing, ON-OFF privacy can be a desired feature in most online applications. The challenge is that the statistical correlation over time of a user’s online behavior can lead to leakage of information. We consider the setting in which a user is interested in retrieving the latest message generated by one of $N$ sources. The user’s privacy status can change between ON and OFF over time. When privacy is ON the user wants to hide his request. Moreover, since the user’s requests depend on personal attributes such as age, gender, and political views, they are typically correlated over time. As a consequence, the user cannot simply ignore privacy when privacy is OFF. We model the correlation between user’s requests by an $N$ state Markov chain. The goal is to design query schemes with optimal download rate, that preserve privacy in an ON-OFF privacy setting. In this paper, we present inner and outer bounds on the achievable download rate for $N$ sources. We also devise an efficient algorithm to construct an ON-OFF privacy scheme achieving the inner bound and prove its optimality in the case $N=2$ sources. For $N > 2$ , finding tighter outer bounds and efficient constructions of ON-OFF privacy schemes that would achieve them remains an open question. [ABSTRACT FROM AUTHOR]

We study the problem of off-policy evaluation in the multi-armed bandit model with bounded rewards, and develop minimax rate-optimal procedures under three settings. First, when the behavior policy is known, we show that the Switch estimator, a method that alternates between the plug-in and importance sampling estimators, is minimax rate-optimal for all sample sizes. Second, when the behavior policy is unknown, we analyze performance in terms of the competitive ratio, thereby revealing a fundamental gap between the settings of known and unknown behavior policies. When the behavior policy is unknown, any estimator must have mean-squared error larger—relative to the oracle estimator equipped with the knowledge of the behavior policy— by a multiplicative factor proportional to the support size of the target policy. Moreover, we demonstrate that the plug-in approach achieves this worst-case competitive ratio up to a logarithmic factor. Third, we initiate the study of the partial knowledge setting in which it is assumed that the minimum probability taken by the behavior policy is known. We show that the plug-in estimator is optimal for relatively large values of the minimum probability, but is sub-optimal when the minimum probability is low. In order to remedy this gap, we propose a new estimator based on approximation by Chebyshev polynomials that provably achieves the optimal estimation error. Numerical experiments on both simulated and real data corroborate our theoretical findings. [ABSTRACT FROM AUTHOR]

We consider a multi-hypothesis testing problem involving a $K$ -armed bandit. Each arm’s signal follows a distribution from a vector exponential family. The actual parameters of the arms are unknown to the decision maker. The decision maker incurs a delay cost for delay until a decision and a switching cost whenever he switches from one arm to another. His goal is to minimise the overall cost until a decision is reached on the true hypothesis. Of interest are policies that satisfy a given constraint on the probability of false detection. This is a sequential decision making problem where the decision maker gets only a limited view of the true state of nature at each stage, but can control his view by choosing the arm to observe at each stage. An information-theoretic lower bound on the total cost (expected time for a reliable decision plus total switching cost) is first identified, and a variation on a sequential policy based on the generalised likelihood ratio statistic is then studied. Due to the vector exponential family assumption, the signal processing at each stage is simple; the associated conjugate prior distribution on the unknown model parameters enables easy updates of the posterior distribution. The proposed policy, with a suitable threshold for stopping, is shown to satisfy the given constraint on the probability of false detection. Under a continuous selection assumption, the policy is also shown to be asymptotically optimal in terms of the total cost among all policies that satisfy the constraint on the probability of false detection. [ABSTRACT FROM AUTHOR]

In a fault tolerant quantum computer, quantum codes are expected to serve the conflicting purposes of protecting quantum information while also allowing that information to be manipulated by fault-tolerant gates. We introduce a new technique for placing limitations on such gates, and apply this technique to a class of quantum codes known as hypergraph product codes contained within the vertical sector. These codes are constructed from input which is a pair of classical linear codes, and generalize the Kitaev surface code which is the hypergraph product of classical repetition codes. We provide a necessary condition on these input codes, under which the resulting hypergraph product code has transversal gates limited to the Clifford group. We conjecture that this condition is satisfied by all $[n,k,d]$ Gallagher codes with $d\ge 3$ and $k\le n/2$. This work is a generalization of an argument due to Bravyi and König, and we also conjecture this is a refinement of the recent notion of disjointness due to Jochym-O’Connor et al. [ABSTRACT FROM AUTHOR]

In multi-stream sequential change-point detection it is assumed that there are $M$ processes in a system and at some unknown time, an occurring event changes the distribution of the samples of a particular process. In this article, we consider this problem under a sampling control constraint when one is allowed, at each point in time, to sample a single process. The objective is to raise an alarm as quickly as possible subject to a proper false alarm constraint. We show that under sampling control, a simple myopic-sampling-based sequential change-point detection strategy is second-order asymptotically optimal when the number $M$ of processes is fixed. This means that the proposed detector, even by sampling with a rate $1/M$ of the full rate, enjoys the same detection delay, up to some additive finite constant, as the optimal procedure. Simulation experiments corroborate our theoretical results. [ABSTRACT FROM AUTHOR]