Potential Topics

Scientists, mathematicians, and engineers have an increasing need to write efficient computer programs but they tend to use specific languages for technical computing like Matlab or Mathematica rather than general purpose languages. The suggested reference discusses the properties a general purpose language would need to be able to also handle technical computing – one possibility for allowing efficient technical computing involves a powerful type system and dispatch system to enable generic, staged, and higher-order programming.

Required Background: First year CS at the level of CS 135 and 136.

Sometimes some non-integers like $e^{π} - π = 19.9990999791...$ are curiously close to integers. While often this is just a numerical coincidence, sometimes there is a clear mathematical reason for certain numbers to be almost integers. Pisot numbers, which are special types of algebraic integers, provide a systematic means to construct almost integers that approximate integers at an exponential rate. Of course, Pisot numbers are interesting on their own right and an interested speaker can also venture into the connections to Beta expansions (see the 2nd and 3rd references below), or fractals (see the 4th reference below).

Required Background: Basic analysis at the level of 147 and 138, algebra at the level of 145. Any other background depends on the direction the speaker takes with this topic.

It was realized in the 1960s that mathematical logic provides a suitable language to formulate properties of programs. This idea was formalized by Hoare who developed Hoare logic as a means to prove program correctness. However, this technique didn't apply directly to concurrent programs. An alternative approach called Temporal Logic was proposed by Amir Pneuli in 1977 which did provide a means to reason about concurrent programs. This topic studies this and then delves into the fundamental ideas behind model checking.

Required Background: Basics of computer science at the level of CS 146, Logic at the level of CS 245.

This topic studies the connection between Gödel’s incompleteness theorems and turing machines and how each implies the other

The ever-increasing amount of information that needs to be processed has led to the development of Complex Event Processing systems such as Apache Storm or Twitter Heron. These systems distribute a workload over many machines in a cluster, and offer both efficiency and fault-tolerance.

Volker Strassen showed that $n^3$ matrix multiplication was not optimal in 1969. Since then, new algorithms such as Coppersmith-Winograd have further improved the time complexity of matrix multiplication. It is conjectured that matrix multiplication is possible in $O(n^{2+ɛ})$ for any $ɛ>0$, however small. This is one of the few remaining open problems in finite-dimensional linear algebra.

Compressed sensing is about minimizing the information gathered and stored by sensors, reducing the need for file compression later on for transmission. This can reduce costs for certain applications, such as non-visible wavelength cameras.

Constructive mathematics, or mathematics without the law of the excluded middle, is becoming more popular thanks to connections with computer science, category theory, and topology. Its logical foundations may be initially difficult to grasp for those used to a classical system.

This topic studies the beautiful connection between continued fractions and the famous Farey tessekation of the hyperbolic plane.

Permutation matrices for which all $\frac{n(n-1)}{2}$ displacements between all pairs of 1s are distinct are known as Costas arrays, and these have important applications in sonar. The Welch construction of Costas arrays uses concepts from number theory, whereas the Lempel-Golomb construction uses concepts from field theory.

Data are rarely perfect. Robust data science tools must have ways to deal with missing data. However, this is not always easy. A balance must be struck between performance and convenience.

Expander graphs are sparse graphs with strong connectivity properties and finds applications in complexity theory, designing of computer networks and the theory of error-correcting codes.

Physicist Enrico Fermi was known for his impressive order-of-magnitude estimation. He was famously able to estimate the yield of the Trinity test atomic bomb to about a factor of two. Why is Fermi estimation so useful and accurate? What are the techniques to make better approximations? How can and do scientists, mathematicians, engineers, and others use Fermi estimation in their work?

A Galois field is a finite field and are used in a variety of applications, including in classical coding theory and cryptography algorithms. This topic studies how to efficiently optimize arithmetic in such fields.

Users often choose passwords that are easy to remember but also easy to guess. Both textual and graphical passwords have failed to provide a viable solution to this usability-security tension. It thus remains a critical challenge in password research to design an authentication scheme that is resilient to guessing attacks while offering good memorability.

The second topic studies which billiard table shapes are optimal.

The Gillespie Algorithm for stochastic equations is used heavily in a number of fields of applied mathematics, in particular computational systems biology.

Most programming languages provide a floating-point type. What is floating point, and how does it work? What caveats should programmers be aware of?

Aesthetically appealing fractal art can be created through interesting mathematical processes, including contraction mappings on metric spaces. Several well known fractals can be formalized mathematically and also appreciated visually. A talk on this subject would explore both mathematical and artistic aspects.

Jupyter Notebooks are a must-have for any data scientist or engineer. They are available for a wide variety of programming languages, particularly Python.

This topic studies sphere packing and the connection to lattices and linear codes.

Originally developed to model plant growth, L-systems are a logical approach to various scientific questions, as well as one of many ways to generate artistically pleasing fractals.

This topic studeis an interesting connection between combinatorics and determinants.

In 1960, A.F. Bartholomay wrote about a mathematical model of chemical reaction mechanisms using set theory.

This topic studies the proof of Monsky's theorem that it is not possible to dissect a square into an odd number of triangles of equal area.

Persistent (or purely function) data structures are those whose operations do not mutate the existing data structure, but rather create a new data structure that might share some state. These data structures are useful because there is no need to copy memory; rather the data structure can be shared among multiple objects. Techniques for making these data structures fast, memory-efficient, or real-time are an active area of research in functional programming.

Queueing theory is the mathematical study of waiting lines, or queues. In queueing theory, a model is constructed so that queue lengths and waiting time can be predicted. Queueing theory is generally considered a branch of operations research because the results are often used when making business decisions about the resources needed to provide a service.

Given two strings, we can write a computer program to tell them apart. A special kind of very simple computer program that accepts or rejects strings, using only a finite number of states while reading the string, is called a deterministic finite automaton. (These deterministic finite automata can also be expressed as a regular expression.) For any two strings of length $n$, there is some deterministic finite automaton (or regular expression) that recognizes one and not the other, and there is some smallest one. In the worst case, it is known (Robson 1989) that any two strings of length $n$ can be separated by an automaton of size $O(n^{2/5} (\log n)^{3/5})$, but this is not known to be optimal. The optimal upper bound remains an open problem.

Sparse matrices are frequently used in scientific and numerical computation. How do they work? What new findings have there been? Speakers are encouraged to specialize this broad topic to a particular subfield of interest.

A game is played by two players called the angel and the devil. It is played on an infinite chessboard (or equivalently the points of a 2D lattice). The angel has a power k (a natural number 1 or higher), specified before the game starts. The board starts empty with the angel at the origin. On each turn, the angel jumps to a different empty square which could be reached by at most k moves of a chess king, i.e. the distance from the starting square is at most k in the infinity norm. The devil, on its turn, may add a block on any single square not containing the angel. The angel may leap over blocked squares, but cannot land on them. The devil wins if the angel is unable to move. The angel wins by surviving indefinitely.

The angel problem is: can an angel with high enough power win?

Required Background: Basic analysis at the level of 147 and algebra at the level of 145.

Naturally growing coral and crochet share an interesting trait in common: they help visualize hyperbolic planes. This talk might explore aspects of geometry, art and craft, or biology.

The famous Lotka-Volterra equations model the population of a predator and a prey, which are of course closely related. Stochastic variations on the Lotka-Volterra equations can be an illuminating introduction to the methods used to solve stochastic differential equations.

Tropical geometry is a combinatorial shadow of algebraic geometry, offering new polyhedral tools to compute invariants of algebraic varieties. It is based on tropical algebra, where the sum of twonumbers is their minimum and the product is their sum. This turnspolynomials into piecewise-linear functions, and their zero sets into polyhedralcomplexes.

The LLVM Compiler Infrastructure Project now powers a wide variety of software, including major programming languages including Rust and Julia, as well as compilers for the popular C and C++ programming languages. Understanding how LLVM works, and being able to read some LLVM bytecode, is extremely useful for optimizing code.

The Unique Games Conjecture, if true, implies that many problems that lack exact polynomial time solutions also lack approximate polynomial time solutions. It was formulated by Subhash Khot in 2002 and is still unsolved.

One of the most exciting mathematical discoveries in the early 1990s was the Wilf-Zeilberger (WZ) algorithm that can be used for proving, evaluating, and discovering identities involving hypergeometric terms automatically by computer. And unlike computerized proof techniques in other areas, the computerized proofs generated by this method provides a certificate for the validity of a combinatorial identity, called a WZ-pair.

Required Background: Combinatorics at the level of Math 249, Calculus at the level of Math 147.

Computer science is, fundamentally, about abstraction and efficiency. A programmer would rather use high-level bricks to build a product than worry about low-level details. Regrettably, the use of high-level bricks often comes at a cost in efficiency, forcing programmers to worry about low-level details. Recently, many programming languages have begun to stress the importance of zero-cost abstractions: ways to construct high-level bricks with zero efficiency cost.