Matthew Gibson-Lopez

Quantum computing has generated significant excitement for its potential to solve certain problems exponentially faster than classical computers, but the underlying physics often makes the field seem inaccessible to algorithms researchers. This talk provides a streamlined introduction to quantum algorithms designed specifically for computer scientists and mathematicians. We'll develop a minimal mathematical framework that captures the essential computational features of quantum systems while glossing over physical details. Through a concrete example of a simple function evaluation problem, we'll see how quantum superposition can reduce the number of queries needed to solve a problem—providing genuine computational advantage with elegant mathematical reasoning. The presentation assumes familiarity with classical algorithms but no prior knowledge of quantum mechanics or quantum computing.

Computer processors inspired by the human brain, known as neuromorphic computers, are often hailed for energy efficient AI/ML computation, but at an architectural level they also offer a unique computational model that's event-driven and massively parallel. These properties distinguish neuromorphic algorithm design from traditional algorithm design, offering potential theoretical and practical benefits. In this seminar, Dr. Severa will (1) provide an overview of neuromorphic computing, (2) discuss a computational viewpoint for spiking neural networks on neuromorphic architectures, and (3) build mathematically rigorous spiking neural algorithms for classic computer science tasks such as sorting, shortest path, and triangle finding.

The Linear Code Equivalence Problem (LCE) asks whether there is a linear isometry mapping one linear code to another. In this talk, I will first describe new (provable) algorithms for LCE and its variant, the Permutation Code Equivalence Problem (PCE). In particular, I will describe a randomized algorithm for solving PCE and LCE on worst-case input codes over arbitrary finite fields F_q of block length n in roughly 2^{n/2} time. This builds on and improves work of Babai (SODA 2011) and Nowakowski (PQCrypto 2025). In particular, a similar randomized algorithm of Nowakowski solves LCE in 2^{n/2} time, but only on random codes over fields of order q >= 7. I will then turn to giving reductions between code equivalence variants, and between code equivalence and isomorphism problems on graphs and lattices. Based on two joint works: (1) with Drisana Bhatia, Jean-François Biasse, Medha Durisheti, Lucas LaBuff, Vincenzo Pallozzi Lavorante, and Philip Waitkevich, and (2) with Kaung Myat Htay Win.

Tensors are a fundamental data structure in many scientific contexts, such as time series analysis (signature path tensors) and materials science (stress-strain tensor) among many others. Improving our ability to produce and handle these tensors is essential to efficiently solve these problems. In this talk, we show how exploiting the symmetries in these problems of the underlying functions mapping tensors to tensors. More concretely, we show equivariant machine learning architectures on tensors that exploit the fact that, in many cases, these tensor-functions are equivariant functions with respect to the diagonal action of the orthogonal, Lorentz, and/or symplectic groups on tensors. Finally, we demonstrate our results on three problems coming from time series analysis, material science and theoretical computer science. Our numerical experiments demonstrate that our equivariant models perform better than corresponding non-equivariant baselines.

This is joint work with Wilson G. Gregory, Nicholas F. Marshall, Andrew S. Lee, and Soledad Villar.

A segment tree is a versatile tree-based data structure over intervals or line segments efficiently supporting several computational operations such as stabbing query, segment arrangement, and planar point location, both theoretically and practically. Polygon clipping is a basic operation in domains such as Computer Graphics, Computer-aided Design, and Geographic Information Science (GIS). Given two polygons with n vertices, polygon clipping algorithms find the geometric intersection or union in O(n²) time using Foster's all-to-all edge intersection testing and O((n+k) log n) time using Vatti's sweep line-based method, where k is the number of intersections. No known segment tree implementation, including the CGAL library, supports intersection finding or polygon clipping. We extended the segment tree leveraging Chaselle's PRAM-model augmentation, parallelized the construction of our augmented segment tree, and employed it to find line segment intersections for polygon clipping while handling degenerate cases. Augmented segment tree eliminates 99% of non-intersecting edge pairs compared to 63% by the state-of-the-art filtering based on common minimum bounding rectangle method employed in Foster's GPU-based implementation. This, coupled with Ω(n log n) work on a single CPU core, beats Foster's GPU performance with O(n²) work. Our OpenMP directive based multi-core implementation achieves up to 4X relative speedup for clipping two polygons with 182K vertices and 5X speedup for five polygons with 398K vertices. We also offloaded the parallel kernels to a GPU using OpenACC achieving performance competitive with Foster's GPU implementation. Our profiling indicates limitations of the compiler directives and potential for superior performance by employing pthread/cuda libraries.