Systems of Lines: Applications of Algebraic Combinatorics

Worcester Polytechnic Institute, Worcester MA

Investigators

Abstract

This NSF award supports a mathematical research workshop entitled "Systems of Lines: Applications of Algebraic Combinatorics" to be held at Worcester Polytechnic Institute from August 10, 2015 to August 14, 2015. This workshop will bring together experts from around the world who study three subjects that are not obviously related but have deep connections between them. The organizers aim to foster cross-collaboration among mathematicians, computer scientists and physicists in order to identify common problems, tools and techniques among seemingly disparate applications of mathematics. Experts in algebraic combinatorics apply tools from algebra, graph theory and optimization to study error-correcting codes, spherical codes and highly regular designs for use in statistics and computer science. Quantum information theorists face problems of measuring and (approximately) replicating finite-dimensional quantum systems in their work on quantum algorithms, quantum cryptography and quantum state tomography. Signal processing experts employ compressive sensing to efficiently reconstruct a sparse signal through undersampling in a carefully designed manner. Data scientists now use ideas from compressive sensing for dimension reduction and the efficient handling of very large data sets. The URL for this workshop is http://users.wpi.edu/~martin/MEETINGS/WPILinesWorkshop.html Beginning with the breakthrough work of Candes, Tao and Donoho in 2004, significant advances have been made over the past decade or so in the reconstruction of sparse signals while sampling below the Nyquist-Shannon limit. Beyond signal processing applications such as MRI, this theory has found new utility in the handling of big data. Matrices with the restricted isometry property (RIP) and random projections now enable effective dimension reduction which greatly enhances our ability to make useful inferences from large-scale data sets. Meanwhile, systems of lines play an important role in quantum information theory where mutually unbiased bases (MUBs) and symmetric informationally complete positive operator-valued measures (SIC-POVMs) promise to provide optimal measurements for finite-dimensional quantum states. Unfortunately, very little is known about how to construct these objects. All of these applications can be couched in the language of algebraic combinatorics where spherical codes and Grassmannian packings naturally arise in the theory of association schemes, in algebraic coding theory and the study of graph eigenvalues. By bringing people together from compressive sensing, quantum information theory, and algebraic combinatorics, this workshop will enable the application of tools and results from each area to the other and help identify the outstanding problems common to all three subdisciplines.