Video streaming platforms are a major source of information for computer science students, where data structures and algorithms can be illustrated by means of animation. Our Python library, AAnim, aids a content creator in making such videos without any special expertise. Given a list of data structure queries or an input graph, our library creates a high-quality video that illustrates both how the data structure evolves and how these changes occur in the algorithm's pseudocode. The data structure's layout is generated automatically, further alleviating the difficulty in creating such videos. Example animations are available at https://youtube.com/playlist?list=PL-UJL8NI-eS5HQDoomg1rMfou5eO-OwuP.

We consider the problem of finding a cycle in a sparse directed graph G that is promised to be far from acyclic, meaning that the smallest feedback arc set , i.e., a subset of edges whose deletion results in an acyclic graph, in G is large. We prove an information-theoretic lower bound, showing that for N -vertex graphs with constant outdegree, any algorithm for this problem must make Ω̄(N 5/9 ) queries to an adjacency list representation of G . In the language of property testing, our result is an Ω̄(N 5/9) lower bound on the query complexity of one-sided algorithms for testing whether sparse digraphs with constant outdegree are far from acyclic. This is the first improvement on the Ω (√ N ) lower bound, implicit in the work of Bender and Ron, which follows from a simple birthday paradox argument.

We consider the problem of finding a cycle in a sparse directed graph G that is promised to be far from acyclic, meaning that the smallest feedback arc set in G is large. We prove an information-theoretic lower bound, showing that for N-vertex graphs with constant outdegree any algorithm for this problem must make (N5/9) queries to an adjacency list representation of G. In the language of property testing, our result is an (N5/9) lower bound on the query complexity of one-sided algorithms for testing whether sparse digraphs with constant outdegree are far from acyclic. This is the first improvement on the lower bound, implicit in Bender and Ron [BR02], which follows from a simple birthday paradox argument.

In the problem of high-dimensional convexity testing, there is an unknown set S in the n-dimensional Euclidean space which is promised to be either convex or c-far from every convex body with respect to the standard multivariate normal distribution. The job of a testing algorithm is then to distinguish between these two cases while making as few inspections of the set S as possible. In this work we consider sample-based testing algorithms, in which the testing algorithm only has access to labeled samples (x,S(x)) where each x is independently drawn from the normal distribution. We give nearly matching sample complexity upper and lower bounds for both one-sided and two-sided convexity testing algorithms in this framework. For constant c, our results show that the sample complexity of one-sided convexity testing is exponential in n, while for two-sided convexity testing it is exponential in the square root of n.

We present the first computational method that allows ordinary users to create complex twisty joints and puzzles inspired by the Rubik's Cube mechanism. Given a user-supplied 3D model and a small subset of rotation axes, our method automatically adjusts those rotation axes and adds others to construct a "non-blocking" twisty joint in the shape of the 3D model. Our method outputs the shapes of pieces which can be directly 3D printed and assembled into an interlocking puzzle. We develop a group-theoretic approach to representing a wide class of twisty puzzles by establishing a connection between non-blocking twisty joints and the finite subgroups of the rotation group SO(3). The theoretical foundation enables us to build an efficient system for automatically completing the set of rotation axes and fast collision detection between pieces. We also generalize the Rubik's Cube mechanism to a large family of twisty puzzles.

We propose a new algorithm for random-access evaluation of diffusion curve images (DCIs) using the fast multipole method . Unlike all previous methods, our algorithm achieves real-time performance for rasterization and texture-mapping DCIs of up to millions of curves. After precomputation, computing the color at a single pixel takes nearly constant time. We also incorporate Gaussian radial basis functions into our fast multipole representation using the fast Gauss transform. The fast multipole representation is not only a data structure for fast color evaluation, but also a framework for vector graphics analogues of bitmap editing operations. We exhibit this capability by devising new tools for fast diffusion curve Poisson cloning and composition with masks.