We present the first known pivot Gray code for spanning trees of complete graphs, listing all spanning trees such that consecutive trees differ by pivoting a single edge around a vertex. This pivot Gray code thus addresses an open problem posed by Knuth in The Art of Computer Programming, Volume 4 (Exercise 101, Section 7.2.1.6, [Knuth 2011]), rated at a difficulty level of 46 out of 50, and imposes stricter conditions than existing revolving-door or edge-exchange Gray codes for spanning trees of complete graphs. Our recursive algorithm generates each spanning tree in constant amortized time using \(O(n^2)\) space. In addition, we provide a novel proof of Cayley’s formula, \(n^{n-2}\), for the number of spanning trees in a complete graph, derived from our recursive approach. We extend the algorithm to generate edge-exchange Gray codes for general graphs with \(n\) vertices, achieving \(O(n^2)\) time per tree using \(O(n^2)\) space. For specific graph classes, the algorithm can be optimized to generate edge-exchange Gray codes for spanning trees in constant amortized time per tree for complete bipartite graphs, \(O(n)\)-amortized time per tree for fan graphs, and \(O(n)\)-amortized time per tree for wheel graphs, all using \(O(n^2)\) space.

We introduce a novel binary representation to represent integer partitions that offers improved storage efficiency compared to the standard integer representation. We then present a recursive algorithm to generate a cyclic 3-Gray code for integer partitions under this new binary representation with a maximum of k parts. Our algorithm produces each integer partition in constant amortized time per string, using O ( n 2 ) space.

Designing a fallback authentication that is both memorable and strong poses a challenging task due to the need for authentication secrets to remain secure and easily recallable without frequent reinforcement. This could be especially prevalent for cloud computing security and resiliency. Inspired by the robust visual-spatial memory and associative memory of individuals, we introduce AuthZit, a novel system. AuthZit encodes authentication secrets as paths implementing a fault-tolerant algorithm through a 3D map of real-life places, navigated in both first person and 2D bird’s-eye perspective, coupled with a loci-tag (textual secret) associated with the location. Two experiments were conducted to iteratively design and evaluate AuthZit. First, it was observed that visual-spatial secrets are most memorable when navigated through a combination of 3D first-person and 2D bird’s-eye view perspectives. Second, we evaluated AuthZit against security questions and Android’s 9-dot pattern lock across three dimensions: memorability, security, and speed. AuthZit’s complexity-controlled secrets were significantly more memorable after three months, more resilient to shoulder surfing, and close adversaries.

We present a simple framework for constructing$k$-ary de Bruijn sequences, and more generally, universal cycles, via successor rules. The framework is based on the often used method of joining disjoint cycles. It generalizes several previously known de Bruijn sequence constructions based on the pure cycling register and is applied to derive a new construction that is perhaps the simplest of all successors. Furthermore, it generalizes an algorithm to construct binary de Bruijn sequences based on any arbitrary nonsingular feedback function. The framework is applied to derive and prove the correctness of successors to efficiently construct 1) universal cycles for$k$-ary strings of length$n$whose weight is bounded by some$w$and 2) universal cycles for permutations. It has also been subsequently applied to find the first universal cycle constructions for weak orders.

In this paper, we introduce SNudge which is a simple tweak on the user interface of in-display fingerprint authentication to nudge users to wipe their fingerprint and resist smudge attacks. We conducted an IRB-approved user study to evaluate the performance of SNudge in which users prefer to use the SNudge 93.6% of the time. Our results demonstrate that SNudge is an effective and unobtrusive nudge to authenticate.